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

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 de ejemplos que proporciona un usuario interactivamente, tal vez seleccionando partes de un texto o seleccionando marcadores de inicio o finalización.

¿Es posible? ¿Hay algoritmos, palabras clave, etc. para los que puedo buscar en Google?

EDIT : gracias por las respuestas, pero no me interesan las herramientas que proporciona esta función. Estoy buscando información teórica, como artículos, tutoriales, código fuente, nombres de algoritmos, para que pueda crear algo para mí mismo.

Answer 1

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

Answer 2

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

La herramienta en línea

Regex Generator ++ genera una expresión regular a partir de los ejemplos proporcionados utilizando un algoritmo de búsqueda GP. El algoritmo de GP se basa en una aptitud multiobjetivo que conduce a un rendimiento más alto y una estructura de solución más simple (Occam's Razor). Esta herramienta es una aplicación demostrativa del Machine Lerning Lab, Trieste Univeristy (Universit & # 224; degli studi di Trieste). Consulte el tutorial en video aquí .

Este es un proyecto de investigación para que pueda leer sobre los algoritmos utilizados aquí .

¡He aquí! :-)

Encontrar una expresión regular / solución significativa a partir de ejemplos es posible 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 artículos 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 hombre (humano), mirando los ejemplos, puede decir: " los códigos de los ítems 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 entender bien el problema. Cuando se aplica la solución generada por el hombre \ 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é es una coincidencia y qué no es una coincidencia deseada: - es decir:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

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

Answer 3

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

Suponga que proporciona los ejemplos 111111 y 999999, si la computadora generara:

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 ones y nueves [19?{6}
4. Una expresión regular que coincida con cualquiera de los 6 dígitos \d{6}
5. Cualquiera de los tres anteriores, con límites de palabras, p. ej. \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 maneras en que los ejemplos pueden generalizarse en una expresión regular. La única forma en que la computadora puede construir una expresión regular predecible es exigirle que enumere todas las posibles coincidencias. 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 " cualquiera de los seis dígitos " ;. En la sintaxis de expresiones regulares, esto se convierte en \ d {6}.

Cualquier método para 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 es facilitar la creación y prueba de la descripción de alto nivel. En lugar de usar la sintaxis de expresión regular tersa directamente, 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.

Es ciertamente posible crear una herramienta que use texto de muestra junto con las pautas proporcionadas por el usuario para generar una expresión regular. La parte difícil al diseñar una herramienta de este tipo 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 en sí mismas, y sin restringir la herramienta a trabajos de expresiones regulares comunes o expresiones regulares simples.

Answer 4

Sí, sin duda 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 + ")<*>quot;;

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

   return regex;
}

El problema es que hay un número infinito de expresiones regulares que coincidirán con una lista de ejemplos. Este código proporciona la expresión regular más simple / más estúpida del conjunto, básicamente coincide con cualquier cosa en la lista de ejemplos positivos (y nada más, incluido cualquiera 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 incluso así, el usuario tendría que proporcionar entradas muy buenas para asegurarse de que la expresión resultante era la correcta. / p>

Answer 5

Creo que el término es "inducción". Quieres 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, tendrías que dejar que el programa le haga preguntas al usuario de sí / no hasta que esté contenido).

Answer 6

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

Answer 7

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

Como han mencionado otros, 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 obtener más información sobre el tema.

Answer 8

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

La pregunta es más complicada de lo que piensa, 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 escupir siempre la misma respuesta. Esto supone un número infinito de entradas, y no da absolutamente ninguna responsabilidad sobre cuándo el programa llegará a su decisión. Además, no puede saber cuándo ha llegado a su decisión, ya que podría seguir produciendo algo diferente más adelante.

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

Answer 9

He investigado en Google y CiteSeer y encontré estas técnicas / documentos:

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

También el "conjunto regular de aprendizaje de consultas y contraejemplos de Dana Angluin" Parece prometedor, pero no pude encontrar una versión para PS o PDF, solo citas y documentos de seminarios.

Parece que este es un problema difícil incluso en el nivel teórico.

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. Afortunadamente, este es un espacio de lógica bastante finito, por lo que no sería tan complejo como enseñar a un programa a poder ver objetos o algo así.