regex - ¿Es posible que una computadora "aprenda" una expresión regular mediante ejemplos proporcionados por el usuario?

artificial-intelligence theory

Question

¿Es posible que una computadora "aprenda" una expresión regular mediante ejemplos proporcionados por el usuario?

Para aclarar:

• No quiero aprender expresiones regulares.
• Quiero crear un programa que "aprenda" una expresión regular a partir de ejemplos proporcionados interactivamente por un usuario, tal vez seleccionando partes de un texto o seleccionando marcadores de inicio o final.

¿Es posible? ¿Hay algoritmos, palabras clave, etc. que pueda buscar en Google?

EDITAR : Gracias por las respuestas, pero no estoy interesado en las herramientas que ofrecen esta característica. Estoy buscando información teórica, como documentos, tutoriales, código fuente, nombres de algoritmos, para poder crear algo para mí.

Answer 1

@Yuval es correcto. Estás viendo la teoría del aprendizaje computacional, o "inferencia inductiva".

La pregunta es más complicada de lo que piensas, ya que la definición de "aprender" no es trivial. Una definición común es que el alumno puede escupir respuestas cuando lo desee, pero eventualmente, debe dejar de escupir respuestas o siempre escupir la misma respuesta. Esto supone una cantidad infinita de entradas, y no da absolutamente nada cuando el programa llegue a su decisión. Además, no se puede decir cuándo HA llegado a su decisión, porque aún podría mostrar algo diferente más tarde.

Según esta definición, estoy bastante seguro de que los idiomas regulares son aprendibles. Por otras definiciones, no tanto ...

Answer 2

Creo que el término es "inducción". Desea inducir una gramática regular.

No creo que sea posible con un conjunto finito de ejemplos (positivos o negativos). Pero, si recuerdo correctamente, se puede hacer si hay un Oracle que se puede consultar. (Básicamente, debe dejar que el programa le haga preguntas al usuario si / no hasta que haya contenido).

Answer 3

El libro Introducción a la teoría del aprendizaje computacional contiene un algoritmo para aprender un autómata finito. Como cada idioma regular es equivalente a un autómata finito, es posible aprender algunas expresiones regulares de un programa. Kearns y Valiant muestran algunos casos en los que no es posible aprender un autómata finito. Un problema relacionado es aprender modelos ocultos de Markov , que son autómatas probabilísticos que pueden describir una secuencia de caracteres. Tenga en cuenta que la mayoría de las "expresiones regulares" modernas que se utilizan en los lenguajes de programación son en realidad más fuertes que los lenguajes comunes y, por lo tanto, a veces más difíciles de aprender.

Answer 4

Es posible que desee jugar un poco con este sitio, es bastante genial y parece que hace algo similar a lo que está diciendo: http://txt2re.com

Answer 5

Hay un lenguaje dedicado a problemas como este, basado en prólogo. Se llama progol .

Como otros han mencionado, la idea básica es el aprendizaje inductivo, a menudo llamado ILP ( programación de lógica inductiva ) en círculos de IA.

El segundo enlace es el artículo de wiki sobre ILP, que contiene una gran cantidad de material de origen útil si está interesado en aprender más sobre el tema.

Answer 6

Investigué un poco sobre Google y CiteSeer y encontré estas técnicas / artículos:

• Identificación del idioma en el límite
• Probablemente el aprendizaje sea aproximadamente correcto

También "Aprender conjuntos regulares de consultas y contraejemplos" de Dana Angluin parece prometedor, pero no pude encontrar una versión de PS o PDF, solo citas y documentos de seminarios.

Parece que este es un problema complicado incluso en el nivel teórico.

Answer 7

Ningún programa de computadora podrá generar una expresión regular significativa basada únicamente en una lista de coincidencias válidas. Déjame mostrarte por qué.

Supongamos que proporciona los ejemplos 111111 y 999999, en caso de que la computadora genere:

1. Una expresión regular que coincida exactamente con esos dos ejemplos: (111111|999999)
2. Una expresión regular que coincida con 6 dígitos idénticos (/d)/1{5}
3. Una expresión regular que coincida con 6 unidades y nueves [19]{6}
4. Una expresión regular que coincida con 6 dígitos /d{6}
5. Cualquiera de los tres anteriores, con límites de palabras, por ejemplo, /b/d{6}/b
6. Cualquiera de los tres primeros, no precedido o seguido por un dígito, por ejemplo, (?<!/d)/d{6}(?!/d)

Como puede ver, hay muchas formas en que los ejemplos pueden generalizarse en una expresión regular. La única forma de que la computadora genere una expresión regular predecible es exigirle que liste todas las coincidencias posibles. Entonces podría generar un patrón de búsqueda que coincida exactamente con esas coincidencias.

Si no desea enumerar todas las coincidencias posibles, necesita una descripción de nivel superior. Eso es exactamente lo que las expresiones regulares están diseñadas para proporcionar. En lugar de proporcionar una larga lista de números de 6 dígitos, simplemente le dice al programa que coincida con "seis dígitos". En la sintaxis de expresión regular, esto se convierte en / d {6}.

Cualquier método de proporcionar una descripción de nivel superior que sea tan flexible como las expresiones regulares también será tan complejo como las expresiones regulares. Todas las herramientas como RegexBuddy pueden hacer para facilitar la creación y prueba de la descripción de alto nivel. En lugar de usar directamente la sintaxis de expresiones regulares lacras, RegexBuddy le permite usar bloques de construcción simples en inglés. Pero no puede crear la descripción de alto nivel para usted, ya que no puede saber mágicamente cuándo debe generalizar sus ejemplos y cuándo no.

Sin duda, es posible crear una herramienta que utiliza texto de muestra junto con las directrices proporcionadas por el usuario para generar una expresión regular. La parte más difícil en el diseño de dicha herramienta es cómo le pide al usuario la información de guía que necesita, sin hacer que la herramienta sea más difícil de aprender que las expresiones regulares, y sin restringir la herramienta a trabajos regulares de expresiones regulares o expresiones regulares simples.

Answer 8

Sí, ciertamente es "posible"; Aquí está el pseudo-código:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they''re excluded by definition

   return regex;
}

El problema es que hay un número infinito de expresiones regulares que coincidirá con una lista de ejemplos. Este código proporciona la expresión regular más simple / más estúpida del conjunto, básicamente haciendo coincidir cualquier cosa en la lista de ejemplos positivos (y nada más, incluido ninguno de los ejemplos negativos).

Supongo que el verdadero desafío sería encontrar la expresión regular más corta que coincida con todos los ejemplos, pero aun así, el usuario tendría que proporcionar muy buenas entradas para asegurarse de que la expresión resultante fuera "la correcta".

Answer 9

Sí, es posible, podemos generar expresiones regulares a partir de ejemplos (texto -> extracciones deseadas). Esta es una herramienta en línea que funciona y que hace el trabajo: http://regex.inginf.units.it/

La herramienta en línea Regex Generator ++ genera una expresión regular a partir de ejemplos proporcionados utilizando un algoritmo de búsqueda GP. El algoritmo GP es impulsado por una aptitud multiobjetivo que conduce a un mayor rendimiento y una estructura de solución más simple (Navaja de Occam). Esta herramienta es una aplicación demostrativa de Machine Lerning Lab, Universidad de Trieste (Università degli studi di Trieste). Por favor mira el video tutorial here .

Este es un proyecto de investigación para que pueda leer acerca de los algoritmos utilizados here .

¡Mirad! :-)

Es posible encontrar una expresión / solución significativa de los ejemplos si, y solo si, los ejemplos proporcionados describen bien el problema. Considere estos ejemplos que describen una tarea de extracción, estamos buscando códigos de elementos particulares; los ejemplos son pares de texto / extracción:

"The product code il 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Un tipo (humano), mirando los ejemplos, puede decir --es decir: "los códigos de los elementos son cosas como / d ++ - 345 [AB]"

Cuando el código del artículo es más permisivo pero no hemos proporcionado otros ejemplos, no tenemos pruebas para comprender bien el problema. Al aplicar la solución generada por el ser humano / d ++ - 345 [AB] al siguiente texto, falla:

"On the back of the item there is a code: 966-347Z"

Debe proporcionar otros ejemplos para describir mejor qué coincide y cuál no es una coincidencia deseada: --ie:

"My phone is [phone] , and the phone product id is 966-347Z" -> "966-347Z"

El número de teléfono no es una identificación del producto, esta puede ser una prueba importante.

Answer 10

Si es posible que una persona aprenda una expresión regular, entonces es fundamentalmente posible para un programa. Sin embargo, ese programa deberá estar correctamente programado para poder aprender. Por suerte, este es un espacio de la lógica bastante finito, por lo que no sería tan complejo como enseñar un programa para poder ver objetos o algo así.