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, gramática) de un idioma regular a partir de un conjunto dado de cadenas de ejemplos. Aunque E. Mark Gold ha demostrado que no todos los idiomas regulares se pueden aprender de esta manera (ver la identificación del idioma en el límite ), se han investigado enfoques para una variedad de subclases. Están esbozados en este artículo. Para aprender gramáticas más generales, consulte Introducción a la gramática .
Ejemplo
Un lenguaje regular se define como un conjunto (finito o infinito) de cadenas que pueden describirse mediante uno de los formalismos matemáticos llamados " autómatas finitos ", " gramática regular " o " expresión regular ", todos los cuales tienen el mismo poder expresivo. . Dado que este último formalismo conduce a notaciones más breves, se introducirá y utilizará aquí. Dado un conjunto Σ de símbolos (también conocido como alfabeto), una expresión regular puede ser cualquiera de
- ∅ (que denota el conjunto vacío de cadenas),
- ε (que denota el conjunto singleton que contiene solo la cadena vacía),
- a (donde a es cualquier carácter en Σ; denota el conjunto singleton que solo contiene la cadena de un solo carácter a ),
- r + s (donde r y s son, a su vez, las expresiones regulares más simples; denotan la unión de su conjunto)
- r ⋅ s (que denota el conjunto de todas las posibles concatenaciones de cadenas de r 'sy s ' s),
- r + (que denota el conjunto de n repeticiones de cadenas del conjunto de r , para cualquier n ≥1), o
- r * (denota de manera similar el conjunto de n repeticiones, pero también incluye la cadena vacía, vista como repetición 0 veces).
Por ejemplo, usando Σ = {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 el cero inicial), 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 crear 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 muchos ceros arbitrariamente (quizás incluso ninguno) ". 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 llamó a la trivial sobregeneralización 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 encontrará una expresión regular que genere todos los ejemplos positivos, pero ninguno de los negativos.
Celosía de autómatas
Dupont y col. 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 elemento 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 la 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, formando una red. Al mapear [nota 2] cada equivalencia E con el cociente correspondiente del lenguaje autómata L ( A a, b, c, d / E ) se obtiene el conjunto parcialmente ordenado que se muestra en la imagen. El idioma de cada nodo se indica mediante una expresión regular. El lenguaje puede ser reconocido por autómatas cocientes con 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 adecuado del del nodo superior.
Si se dan cadenas de ejemplo tanto positivas como negativas, Dupont et al. construya la celosía a partir de los ejemplos positivos y luego investigue el límite de separación entre los autómatas que generan algún ejemplo negativo y los que no. Los más interesantes son los autómatas que se encuentran inmediatamente debajo del borde. [1] En la imagen, los bordes de separación se muestran para las cadenas de ejemplo negativo 11 ( verde ), 1001 ( azul) , 101 ( cian ) y 0 ( rojo ).
Coste y Nicolas presentan un método de búsqueda propio dentro del enrejado, 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 gráficos en la relación de desigualdad de estado inducida por los ejemplos negativos. [2] Posteriormente, investigan varias relaciones de ordenamiento en el conjunto de todas las posibles fusiones de estados. [3]
Kudo y Shimbo utilizan la representación mediante factorizaciones automatizadas para proporcionar un marco único para los siguientes enfoques (esbozados a continuación ):
- k-lenguajes reversibles y el enfoque de seguimiento de "agrupación de cola",
- Autómatas sucesores y el método predecesor-sucesor, y
- enfoques basados en el bombeo (integración de marcos desafiada por Luzeaux, [4] sin embargo).
Se muestra que cada uno de estos enfoques corresponde a un tipo particular de relaciones de equivalencia utilizadas para la factorización. [5]
Enfoques
k -lenguajes reversibles
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 el extensión homomórfica de δ a palabras arbitrarias. Angluin proporciona un algoritmo cúbico para el aprendizaje del lenguaje k- reversible más pequeño 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 dados símbolos obliga a unificar los estados de los autómatas, lo que lleva a una generalización adecuada diferente del autómata trivial subgeneralizado. Este algoritmo se ha utilizado para aprender partes simples de la sintaxis del inglés; [8] más tarde, se ha proporcionado una versión incremental. [9] Otro enfoque basado en k -autómatas reversibles es el método de agrupamiento de cola . [10]
Autómatas sucesores
A partir de un conjunto dado de cadenas de entrada, Vernadat y Richetin construyen un autómata sucesor , que consta de 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 idiomas locales . Dado que cada idioma regular es la imagen homomórfica de un idioma local, las gramáticas de la clase anterior se pueden aprender levantando , si se proporciona un homomorfismo apropiado (según la aplicación prevista) . En particular, existe tal homomorfismo para la clase de lenguas que se aprenden mediante el método predecesor-sucesor. [12] La capacidad de aprendizaje de los idiomas locales se puede reducir a la de los idiomas k- reversibles. [13] [14]
Enfoques tempranos
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 que se va a aprender; utilizando consultas de membresía preguntan, por k apropiado , cuál de las cadenas uw , uvvw , uvvvw , ..., uv k w también pertenece al lenguaje que se va 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 . [dieciséis]
Cubrir autómatas
Câmpeanu y col. aprender un autómata finito como una representación compacta de un gran lenguaje finito. Dado tal lenguaje F , buscan un autómata de cobertura A tal que su lenguaje L ( A ) cubre 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 de no más de l . Si existe tal autómata de cobertura, F está determinado únicamente 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 y y , Câmpeanu et al. defina 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 largos que l . [17] A partir de esta relación, cuya falta de transitividad [nota 3] provoca 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 mínimo de estados. Además, para la unión, intersección y diferencia de dos lenguajes finitos, proporcionan las operaciones correspondientes en sus autómatas de cobertura. [18] [19] Păun y col. mejorar la complejidad del tiempo a O ( n 2 ). [20]
Autómatas residuales
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 que se pueden obtener de una cadena en S cortando su prefijo u (si es posible), formalmente: u −1 S = { v ∈ Σ * : uv ∈ S } , cf. imagen. [21] Denis y col. definir un autómata residual como un autómata finito no determinista A donde cada estado q corresponde a un derivado 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.
Muestran que cada lenguaje regular es generado por un autómata residual mínimo determinado de forma única. Sus estados son derivados de Brzozowski ∪ -indescomponibles, 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 se pueden aprender en tiempo polinomial, incluso asumiendo entradas de muestra óptimas. Proporcionan un algoritmo de aprendizaje para autómatas residuales y demuestran que aprende el autómata a partir de su muestra característica de cadenas de entrada positivas y negativas. [22] [23]
Aprendizaje de consultas
Los lenguajes regulares no se pueden aprender en tiempo polinomial usando solo consultas de membresía [24] o usando solo consultas de equivalencia. [25] Sin embargo, Angluin ha demostrado que los lenguajes regulares se pueden aprender 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ó más tarde para generar un NFA ( autómatas finitos no deterministas ) en lugar de un DFA ( autómatas finitos deterministas ), a través de un algoritmo denominado NL *. [27] Este resultado se generalizó aún más y se diseñó un algoritmo que genera un AFA ( autómatas finitos alternos ) denominado AL *. [28] Cabe señalar 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]
Expresiones regulares reducidas
Brill define una expresión regular reducida como cualquiera de
- a (donde a es cualquier carácter en Σ; denota el conjunto singleton que solo contiene la cadena de un solo carácter a),
- ¬ a (que denota cualquier otro carácter en Σ excepto a ),
- • (que denota cualquier carácter individual en Σ)
- a * , (¬ a ) * , o • * (que denota arbitrariamente muchas, posiblemente cero, repeticiones de caracteres del conjunto de a , ¬ a o •, respectivamente), o
- r ⋅ s (donde rys son, a su vez, expresiones regulares reducidas más simples; denota el conjunto de todas las posibles concatenaciones de cadenas de r 'sy s ' s).
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 prefijos aceptados. Su objetivo es aprender las reglas de corrección de los errores de ortografía en inglés, [nota 5] en lugar de consideraciones teóricas sobre la capacidad de aprendizaje de las clases de idiomas. En consecuencia, usa heurística para podar la acumulación de árboles, lo que lleva a una mejora considerable en el tiempo de ejecución. [30]
Aplicaciones
- Encontrar patrones comunes en descripciones de estructuras de ADN y ARN [31] [32] ( Bioinformática )
- Modelado de la adquisición del lenguaje natural por humanos [33]
- Aprendizaje de descripciones estructurales de documentos de ejemplo estructurados, en particular Definiciones de tipo de documento (DTD) de documentos SGML [34]
- Aprendizaje de la estructura de piezas musicales [35] [36]
- Obtención de representaciones compactas de lenguajes finitos [18]
- Clasificación y recuperación de documentos [37]
- Generación de reglas de corrección dependientes del contexto para errores gramaticales en inglés [30]
Notas
- ^ es decir, autómatas finitos sin estados y transiciones innecesarios, con respecto al conjunto de cadenas de entrada dado
- ^ Este mapeo no es un homomorfismo de celosía , sino solo un mapeo monótono .
- ^ Por ejemplo, F = { AAB , BAA , aabb } conduce a aab ~ AABB (sólo z = varepsilon necesidades para ser considerado para comprobar esto) y aabb ~ BAA (de manera similar), pero no aab ~ BAA (debido al caso z = b ). Según Câmpeanu et al. (2001, Lema 1, p.5), sin embargo x ~ y ∧ y ~ z → x ~ z es válido para las cadenas x , y , z con | x | ≤ | y | ≤ | z |.
- ^ donde n es el número de estados de un DFA A F tal que L ( A F ) = F
- ^ Por ejemplo: Reemplaza " pasado " por " pasado " en el contexto "(¬ t ⋅ o ) * ⋅ SINGULAR_NOUN ⋅ pasado "
Referencias
- ^ P. Dupont; L. Miclet; E. Vidal (1994). "¿Cuál es el espacio de búsqueda de la inferencia regular?". En RC Carrasco; J. Oncina (eds.). Actas del Segundo Coloquio Internacional sobre Inferencia Gramatical (ICGI): Inferencia y Aplicaciones Gramaticales . LNCS. 862 . Saltador. págs. 25–37. CiteSeerX 10.1.1.54.5734 .
- ^ F. Coste; J. Nicolas (1997). "Inferencia regular como un problema de coloración de gráficos". Proc. Taller ICML sobre inferencia gramatical, inducción de autómatas y adquisición de lenguaje . págs. 9–7. CiteSeerX 10.1.1.34.4048 .
- ^ F. Coste; J. Nicolas (1998). "Cómo la consideración de fusiones de estados incompatibles puede reducir el árbol de búsqueda de inducción de DFA". En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, IV Coloquio Internacional, ICGI . LNCS. 1433 . Saltador. págs. 199–210. CiteSeerX 10.1.1.34.2050 .
- ^ Dominique Luzeaux (agosto de 1997). "Un enfoque universal para la inferencia gramatical regular positiva" . Proc. XV Congreso Mundial IMACS sobre Computación Científica, Modelado y Matemática Aplicada .
- ^ M. Kudo; M. Shimbo (1988). "Técnicas eficientes de inferencia gramatical regular mediante el uso de similitudes parciales y sus relaciones lógicas". Reconocimiento de patrones . 21 (4): 401–409. doi : 10.1016 / 0031-3203 (88) 90053-2 .
- ^ D. Angluin (1981). "Una nota sobre el número de consultas necesarias para identificar idiomas regulares" . Información y control . 51 : 76–87. doi : 10.1016 / s0019-9958 (81) 90090-5 .
- ^ D. Angluin (1982). "Inferencia de lenguajes reversibles". J. ACM . 293 (3): 741–765. CiteSeerX 10.1.1.232.8749 . doi : 10.1145 / 322326.322334 .
- ^ Robert C. Berwick; Samuel F. Pilato (1987). "Aprendizaje de sintaxis por inducción de autómatas" . Aprendizaje automático . 2 (1): 9–38. doi : 10.1007 / bf00058753 .
- ^ Rajesh Parekh; Codrin Nichitiu; Vasant Honavar (enero de 1997). Un algoritmo incremental de tiempo polinomial para la inferencia gramatical regular (informe técnico). Grupo de Investigación de Inteligencia Artificial, Univ. Del Estado de Iowa. pag. 14. TR 97-03.
- ^ L. Miclet; C. Faure (1985). Reconnaissance des Formes Structurelle: Développement et Tendances (Informe técnico). INRIA.
- ^ F. Vernadat; M. Richetin (1984). "Inferencia regular para el reconocimiento de patrones sintácticos: un estudio de caso". Proc. VII Conferencia Internacional sobre Reconocimiento de Patrones (ICPR) . págs. 1370-1372.
- ^ P. García; E. Vidal; F. Casacuberta (1987). "Lenguas locales, el método sucesor y un paso hacia una metodología general para la inferencia de gramáticas regulares". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 9 .
- ^ Takashi Yokomori (octubre de 1989). "Aprendizaje eficiente de idiomas libres de contexto". En KP Jantke (ed.). Proc. En t. Taller AII . LNAI. 397 . Saltador. págs. 104-123. doi : 10.1007 / 3-540-51734-0_54 . ISBN 978-3-540-51734-4.
- ^ Satoshi Kobayashi; Takashi Yokomori (1994). "Aprendizaje de concatenaciones de idiomas comprobables localmente a partir de datos positivos". En Setsuo Arikawa; Klaus P. Jantke (eds.). Proc. 5th ALT . LNAI. 872 . Saltador. págs. 405–422. CiteSeerX 10.1.1.52.4678 .
- ^ N. Chomsky; GA Miller (1957). Concepción de patrones (informe técnico). ASTIA. Documento AD110076.
- ^ R. Solomonoff (junio de 1959). "Un nuevo método para descubrir las gramáticas de los lenguajes de estructura de frases". Proc. En t. Conf. sobre Tratamiento de la Información . R.Oldenbourg. págs. 285–290.
- ^ Esta relación generaliza la relación R F del teorema de Myhill-Nerode . Se ha investigado con más detalle en la sección 3 de: Cynthia Dwork; Larry Stockmeyer (1990). "Una brecha de complejidad de tiempo para autómatas de estado finito probabilísticos bidireccionales" . Revista SIAM de Computación . 19 (6): 1011–1023. doi : 10.1137 / 0219069 .
- ^ a b Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). "Autómatas de cobertura mínima para lenguajes finitos". En J.-M. Champarnaud; D. Maurel; D. Ziadi (eds.). Proc. Taller de Implementación de Autómatas (WIA) (PDF) . LNCS . 1660 . Saltador. págs. 43–56. CiteSeerX 10.1.1.37.431 . doi : 10.1007 / 3-540-48057-9_4 . ISBN 978-3-540-66652-3.
- ^ Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (2001). "Autómatas de cobertura mínima para lenguajes finitos". Informática Teórica . 267 (1–2): 3–16. doi : 10.1016 / s0304-3975 (00) 00292-9 .
- ^ Andrei Păun; Nicolae Sântean; Sheng Yu (septiembre de 2001). "Un algoritmo O (n 2 ) para la construcción de autómatas de cobertura mínima para lenguajes finitos". En Sheng Yu; Andrei Păun (eds.). Proc. 5th Int. Conf. sobre Implementación y Aplicación de Autómatas (CIAA) (PDF) . LNCS. 2088 . Saltador. págs. 243-251. ISBN 978-3-540-42491-8.
- ^ Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145 / 321239.321249 .
- ^ François Denis; Aurélien Lemay; Alain Terlutte (2000). "Aprendizaje de idiomas regulares mediante autómatas finitos no deterministas". En Arlindo L. Oliveira (ed.). Inferencia gramatical: Algoritmos y aplicaciones, V Coloquio Internacional, ICGI . LNCS. 1891 . Saltador. págs. 39–50. CiteSeerX 10.1.1.13.5559 . ISBN 978-3-540-41011-9.
- ^ François Denis; Aurélien Lemay; Alain Terlutte (2001). "Aprendizaje de idiomas regulares usando RFSA" (PDF) . Proc. ALT '01 .
- ^ Angluin, Dana (1995). "¿Cuándo no ayudarán las consultas de membresía? (Resumen extendido)" . 23º Simposio Anual ACM sobre Teoría de la Computación .
- ^ Angluin, Dana (1990). "Resultados negativos para consultas de equivalencia" . Aprendizaje automático . 5 .
- ^ Angluin, Dana (1987). "Aprendizaje de conjuntos regulares a partir de consultas y contraejemplos" . Información y Computación . 75 .
- ^ Bollig; Habermehl; Kern; Leucker (2009). "Aprendizaje estilo angluin de NFA" (PDF) . 21ª Conferencia Conjunta Internacional sobre Inteligencia Artificial .
- ^ Angluina; Eisenstat; Fisman (2015). "Aprendizaje de idiomas regulares a través de autómatas alternos" . XXIV Conferencia Conjunta Internacional sobre Inteligencia Artificial .
- ^ Mayer, AR; Stockmeyer, Larry J. (1995). "La complejidad de los problemas de palabras, esta vez con intercalado" . Información y Computación . 115 .
- ^ a b Eric Brill (2000). "Desambiguación basada en patrones para el procesamiento del lenguaje natural" (PDF) . Proc. EMNLP / VLC .
- ^ Alvis Brazma; Inge Jonassen; Jaak Vilo; Esko Ukkonen (1998). "Descubrimiento de patrones en biosecuencias". En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, IV Coloquio Internacional, ICGI . LNCS. 1433 . Saltador. págs. 257-270.
- ^ MS Waterman, ed. (Enero de 1989). Métodos matemáticos para secuencias de ADN . Prensa CRC. ISBN 978-0849366642.
- ^ Fernando Pereira; Yves Schabes (1992). "Reestimación de adentro hacia afuera para corpora parcialmente entre corchetes" . Proc. 30th Ann. Reunión de la Assoc. para Comp. Lingüística . págs. 128-135.
- ^ Helena Ahonen (noviembre de 1996). Generación de gramáticas para documentos estructurados mediante métodos de inferencia gramatical (PDF) (Ph.D.). Informe. A-1996-4. Universidad de Helsinki, Departamento de Ciencias de la Computación. Archivado desde el original (PDF) el 12 de febrero de 2020.
- ^ Stephen Watkinson (1997). Inducción de la sintaxis musical (Master). Departamento de IA, Univ. Edimburgo. Archivado desde el original el 4 de junio de 2001.
- ^ Pedro P. Cruz-Alcázar; Enrique Vidal (1998). "Aprendizaje de gramáticas regulares para modelar el estilo musical: comparar diferentes esquemas de codificación" (PDF) . En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, IV Coloquio Internacional, ICGI . LNCS. 1433 . Saltador. págs. 211-222.
- ^ Alexander S. Saidi; Souad Tayeb-bey (1998). "Inferencia gramatical en el reconocimiento de documentos". En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, IV Coloquio Internacional, ICGI . LNCS. 1433 . Saltador. págs. 175-186. ISBN 978-3-540-64776-8.