En la teoría del aprendizaje computacional , la inducción de lenguajes regulares se refiere a la tarea de aprender una descripción formal (por ejemplo, una gramática) de un lenguaje regular a partir de un conjunto dado de cadenas de ejemplo. Aunque E. Mark Gold ha demostrado que no todos los lenguajes regulares pueden aprenderse de esta manera (véase la identificación de lenguajes en el límite ), se han investigado enfoques para una variedad de subclases. Se describen en este artículo. Para el aprendizaje de gramáticas más generales, consulte Inducción gramatical .
Un lenguaje regular se define como un conjunto (finito o infinito) de cadenas que se pueden describir mediante uno de los formalismos matemáticos llamados " autómata finito ", " gramática regular " o " expresión regular ", todos los cuales tienen el mismo poder expresivo. Dado que el último formalismo conduce a notaciones más cortas, se presentará y utilizará aquí. Dado un conjunto Σ de símbolos (también conocido como alfabeto), una expresión regular puede ser cualquiera de
Por ejemplo, utilizando Σ = {0,1}, la expresión regular (0+1+ε)⋅(0+1) denota el conjunto de todos los números binarios con uno o dos dígitos (se permite cero a la izquierda), mientras que 1⋅(0+1) * ⋅0 denota el conjunto (infinito) de todos los números binarios pares (sin ceros a la izquierda).
Dado un conjunto de cadenas (también llamadas "ejemplos positivos"), la tarea de la inducción del lenguaje regular es llegar a una expresión regular que denote un conjunto que las contenga todas. Como ejemplo, dado {1, 10, 100}, una descripción "natural" podría ser la expresión regular 1⋅0 * , correspondiente a la caracterización informal " un 1 seguido de arbitrariamente muchos (quizás incluso ninguno) 0 ". Sin embargo, (0+1) * y 1+(1⋅0)+(1⋅0⋅0) es otra expresión regular, que denota el conjunto más grande (asumiendo Σ = {0,1}) y el más pequeño que contiene las cadenas dadas, y se denominan sobregeneralización trivial y subgeneralización , respectivamente. Algunos enfoques funcionan en un entorno extendido donde también se da un conjunto de cadenas de "ejemplo negativo"; luego, se debe encontrar una expresión regular que genere todos los ejemplos positivos, pero ninguno de los negativos.
Dupont et al. han demostrado que el conjunto de todos los autómatas finitos estructuralmente completos [nota 1] que generan un conjunto de entrada dado de cadenas de ejemplo forma una red , con el autómata trivial subgeneralizado y el autómata trivial sobregeneralizado como elementos inferior y superior, respectivamente. Cada miembro de esta red se puede obtener factorizando el autómata subgeneralizado mediante una relación de equivalencia apropiada .
Para el conjunto de cadenas de ejemplo anterior {1, 10, 100}, la imagen muestra en su parte inferior el autómata subgeneralizado A a,b,c,d en gris , que consta de los estados a , b , c y d . En el conjunto de estados {a,b,c,d}, existen un total de 15 relaciones de equivalencia, que forman una red. Al asignar [nota 2] cada equivalencia E al lenguaje de autómata cociente correspondiente L ( A a,b,c,d / E ) se obtiene el conjunto parcialmente ordenado que se muestra en la imagen. El lenguaje de cada nodo se denota mediante una expresión regular. El lenguaje puede ser reconocido por autómatas cocientes con respecto a diferentes relaciones de equivalencia, todas las cuales se muestran debajo del nodo. Una flecha entre dos nodos indica que el lenguaje del nodo inferior es un subconjunto propio del del nodo superior.
Si se dan cadenas de ejemplo positivas y negativas, Dupont et al. construyen la red a partir de los ejemplos positivos y luego investigan el borde de separación entre los autómatas que generan algún ejemplo negativo y los que no lo hacen. Los más interesantes son aquellos autómatas inmediatamente debajo del borde. [1] En la imagen, se muestran los bordes de separación para las cadenas de ejemplo negativas 11 ( verde ), 1001 ( azul) , 101 ( cian ) y 0 ( rojo ).
Coste y Nicolas presentan un método de búsqueda propio dentro de la red, que relacionan con el paradigma del espacio de versiones de Mitchell . Para encontrar el borde de separación, utilizan un algoritmo de coloración de grafos sobre la relación de desigualdad de estados inducida por los ejemplos negativos. [2] Posteriormente, investigan varias relaciones de ordenación sobre el conjunto de todas las posibles fusiones de estados. [3]
Kudo y Shimbo utilizan la representación mediante factorizaciones de autómatas para brindar un marco único para los siguientes enfoques (esquematizados a continuación):
Se demuestra que cada uno de estos enfoques corresponde a un tipo particular de relaciones de equivalencia utilizadas para la factorización. [5]
Angluin considera los llamados autómatas regulares " k -reversibles", es decir, autómatas deterministas en los que cada estado puede alcanzarse desde como máximo un estado siguiendo una cadena de transición de longitud k . Formalmente, si Σ, Q y δ denotan el alfabeto de entrada, el conjunto de estados y la función de transición de un autómata A , respectivamente, entonces A se llama k -reversible si: ∀ a 0 , ..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , a 0 ... a k ) = δ * ( s 2 , a 0 ... a k ) ⇒ s 1 = s 2 , donde δ * significa la extensión homomórfica de δ a palabras arbitrarias. Angluin da un algoritmo cúbico para el aprendizaje del lenguaje k -reversible más pequeño a partir de un conjunto dado de palabras de entrada; para k = 0, el algoritmo tiene una complejidad casi lineal. [6] [7] La unicidad de estado requerida después de k + 1 símbolos dados obliga a unificar los estados del autómata, lo que conduce a una generalización adecuada diferente del autómata trivial subgeneralizado. Este algoritmo se ha utilizado para aprender partes simples de la sintaxis inglesa; [8] más tarde, se ha proporcionado una versión incremental. [9] Otro enfoque basado en autómatas k -reversibles es el método de agrupamiento de colas . [10]
A partir de un conjunto dado de cadenas de entrada, Vernadat y Richetin construyen un llamado autómata sucesor , que consiste en un estado para cada carácter distinto y una transición entre los estados de cada dos caracteres adyacentes. [11] Por ejemplo, el conjunto de entrada singleton { aabbaabb } conduce a un autómata correspondiente a la expresión regular ( a + ⋅ b + ) * .
Una extensión de este enfoque es el método predecesor-sucesor que generaliza cada repetición de carácter inmediatamente a un Kleene + y luego incluye para cada carácter el conjunto de sus posibles predecesores en su estado. Los autómatas sucesores pueden aprender exactamente la clase de lenguajes locales . Dado que cada lenguaje regular es la imagen homomórfica de un lenguaje local, las gramáticas de la clase anterior se pueden aprender mediante el levantamiento , si se proporciona un homomorfismo apropiado (dependiendo de la aplicación prevista) . En particular, existe un homomorfismo de este tipo para la clase de lenguajes que se pueden aprender mediante el método predecesor-sucesor. [12] La capacidad de aprendizaje de los lenguajes locales se puede reducir a la de los lenguajes k -reversibles. [13] [14]
Chomsky y Miller (1957) [15] utilizaron el lema de bombeo : adivinan una parte v de una cadena de entrada uvw e intentan construir un ciclo correspondiente en el autómata a aprender; utilizando consultas de pertenencia preguntan, para un k apropiado , cuál de las cadenas uw , uvvw , uvvvw , ..., uv k w también pertenece al lenguaje a aprender, refinando así la estructura de su autómata. En 1959, Solomonoff generalizó este enfoque a los lenguajes libres de contexto , que también obedecen a un lema de bombeo . [16]
Câmpeanu et al. aprenden un autómata finito como una representación compacta de un lenguaje finito grande. Dado dicho lenguaje F , buscan un llamado autómata de cobertura A tal que su lenguaje L ( A ) cubra F en el siguiente sentido: L ( A ) ∩ Σ ≤ l = F , donde l es la longitud de la cadena más larga en F , y Σ ≤ l denota el conjunto de todas las cadenas no más largas que l . Si existe tal autómata de cobertura, F está determinado de forma única por A y l . Por ejemplo, F = { ad , read , reread } tiene l = 6 y un autómata de cobertura correspondiente a la expresión regular ( r ⋅ e ) * ⋅ a ⋅ d .
Para dos cadenas x e y , Câmpeanu et al. definen x ~ y si xz ∈ F ⇔ yz ∈ F para todas las cadenas z de una longitud tal que tanto xz como yz no sean más largas que l . [17] Basándose en esta relación, cuya falta de transitividad [nota 3] causa considerables problemas técnicos, dan un algoritmo O ( n 4 ) [nota 4] para construir a partir de F un autómata de cobertura A de recuento de estados mínimo. Además, para la unión, intersección y diferencia de dos lenguajes finitos proporcionan operaciones correspondientes en sus autómatas de cobertura. [18] [19] Păun et al. mejoran la complejidad temporal a O ( n 2 ). [20]
Para un conjunto S de cadenas y una cadena u , la derivada de Brzozowski u −1 S se define como el conjunto de todas las cadenas en reposo obtenibles de una cadena en S cortando su prefijo u (si es posible), formalmente: u −1 S = { v ∈ Σ * : uv ∈ S } , cf. figura. [21] Denis et al. definen un autómata residual como un autómata finito no determinista A donde cada estado q corresponde a una derivada de Brzozowski de su lenguaje aceptado L ( A ), formalmente: ∀ q ∈ Q ∃ u ∈Σ * : L ( A , q ) = u −1 L ( A ), donde L ( A , q ) denota el lenguaje aceptado de q como estado inicial.
Demuestran que cada lenguaje regular es generado por un autómata residual mínimo determinado de forma única. Sus estados son derivados de Brzozowski ∪ -indecomponibles, y puede ser exponencialmente más pequeño que el autómata determinista mínimo. Además, muestran que los autómatas residuales para lenguajes regulares no pueden aprenderse en tiempo polinomial, incluso suponiendo entradas de muestra óptimas. Ofrecen un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata a partir de su muestra característica de cadenas de entrada positivas y negativas. [22] [23]
Los lenguajes regulares no pueden aprenderse en tiempo polinomial utilizando solo consultas de membresía [24] o utilizando solo consultas de equivalencia. [25] Sin embargo, Angluin ha demostrado que los lenguajes regulares pueden aprenderse en tiempo polinomial utilizando consultas de membresía y consultas de equivalencia, y ha proporcionado un algoritmo de aprendizaje denominado L* que hace exactamente eso. [26] El algoritmo L* se generalizó posteriormente para generar un NFA ( autómata finito no determinista ) en lugar de un DFA ( autómata finito determinista ), a través de un algoritmo denominado NL*. [27] Este resultado se generalizó aún más y se ideó un algoritmo que genera un AFA ( autómata finito alternante ) denominado AL*. [28] Se observa que los NFA pueden ser exponencialmente más concisos que los DFA, y que los AFA pueden ser exponencialmente más concisos que los NFA y doblemente exponencialmente más concisos que los DFA. [29] El algoritmo L* y sus generalizaciones tienen implicaciones significativas en el campo de la teoría de autómatas y el aprendizaje formal de lenguajes, ya que demuestran la viabilidad de aprender de manera eficiente modelos de autómatas más expresivos, como NFA y AFA, que pueden representar lenguajes de manera más concisa y capturar patrones más complejos en comparación con los DFA tradicionales.
Brill define una expresión regular reducida como cualquiera de
Dado un conjunto de cadenas de entrada, construye paso a paso un árbol con cada rama etiquetada por una expresión regular reducida que acepta un prefijo de algunas cadenas de entrada, y cada nodo etiquetado con el conjunto de longitudes de los prefijos aceptados. Su objetivo es aprender reglas de corrección para errores ortográficos en inglés, [nota 5] en lugar de consideraciones teóricas sobre la capacidad de aprendizaje de las clases de lenguaje. En consecuencia, utiliza heurísticas para podar la construcción del árbol, lo que conduce a una mejora considerable en el tiempo de ejecución. [30]