Wikipedia

Inducción de lenguajes regulares

En la teoría de 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 de un conjunto dado de cadenas de ejemplos. Aunque Mark E. Gold ha demostrado que no todos los lenguajes regulares se pueden aprender de esta manera (ver la identificación de lenguaje en el límite), varios enfoques se han investigado para una variedad de subclases. Estos están bosquejados en este artículo. Para aprender sobre gramáticas más generales, ver Inducción de gramáticas.

Ejemplo editar

Un lenguaje regular se define como un conjunto (finito o infinito) de cadenas que pueden describirse mediante uno de los formalismos matemáticos llamado "autómata finito", "gramática regular" o "expresión regular", que tienen el mismo poder expresivo. Como este último formalismo conduce a notaciones más cortas, será introducido y utilizado aquí. Dado un conjunto (E) de símbolos (también llamado alfabeto), una expresión regular puede ser cualquiera de

  • ∅ (denotando el conjunto vacío de cadenas),
  • ε (denotando el conjunto unitario que contiene la cadena vacía),
  • a (dónde a es cualquier carácter en Σ; denotando el conjunto unitario conteniendo una cadena de un solo carácter),
  • r+s (dónde r y s son expresiones regulares más sencillas; denotando la unión de su conjunto)
  • r⋅s (denotando el conjunto de todas las concatenaciones posibles de cadenas de los conjuntos de r y s),
  • r+ (denotando el conjunto de n-concatenaciones de cadenas del conjunto de r, para cualquier n≥1), o
  • r* (de modo similar, denotando el conjunto de n-concatenaciones de cadenas, pero también incluyendo la cadena vacía, vista como una 0-concatenación).

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 (con cero inicial permitido), mientras que 1⋅ ( 0 + 1) * ⋅ 0 denota el conjunto (infinito) de todos los números binarios pares (sin ceros iniciales).

Dado un conjunto de cadenas (también llamadas "ejemplos positivos"), la tarea de la inducción de lenguajes regulares 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*, que corresponde a la caracterización informal "un uno seguido de muchos (incluso puede que ninguno) ceros". Sin embargo, (0 + 1)* y 1 + (1⋅0) + (1⋅0⋅0) es otra expresión regular, que denotan (suponiendo que Σ = {0,1}) el más grande y el más pequeño conjunto que contiene las cadenas dadas, llamados sobregeneralización y subgeneralización triviales, respectivamente. Algunos enfoques funcionan en una configuración extendida donde también se da un conjunto de cadenas de "ejemplos negativos"; luego, se debe encontrar una expresión regular que genere todos los ejemplos positivos, pero ninguno de los negativos.

 
Enrejado de autómata generando las cadenas 1, 10, y 100 (ejemplos positivos). Para cada una de las cadenas de ejemplo negativas 11, 1001, 101, y 0, se muestra la sección final del autómata que lo genera. El único autómata que genera todo de { 1, 10, 100 }, pero nada de { 11, 1001, 101, 0 } es el autómata inferior trivial y el correspondiendo a la expresión regular 1⋅0*.

Enrejado de autómata editar

Dupont et al. ha demostrado que el conjunto de todos los autómatas finitos estructuralmente completos[note 1]​ que generan un conjunto de cadenas de ejemplo dado forma un enrejado, con el autómata subgeneralizado trivial y el autómata sobregeneralizado trivial como elementos inferior y superior, respectivamente. Cada miembro de este enrejado puede obtenerse factorizando el autómata subgeneralizado mediante una relación de congruencia apropiada. La imagen muestra un ejemplo para la cadena de entrada anterior {1, 10, 100}. Cada autómata se denota con una expresión regular equivalente. Para la subgeneralización trivial en el nodo inferior, la forma del autómata también se colorea en gris, y consta de los estados a, b, c y d. El autómata de cada nodo es el resultado de factorizar el autómata inferior por la relación de congruencia que se muestra en gris debajo del nodo.

Si se dan cadenas de ejemplos positivas y negativas, Dupont et al. construye el enrejado a partir de los ejemplos positivos, y luego investiga el límite de separación entre los autómatas que generan ejemplos negativos y los que no. Los más interesantes son los autómatas inmediatamente debajo de la frontera.[1]​ En la imagen, se muestran los límites de separación para las cadenas de ejemplo negativas 11, 1001, 101, 0.

Coste y Nicolas presentan un método de búsqueda propio dentro de este enrejado, que relacionan con el paradigma de espacio de versiones de Mitchell. Para encontrar el límite de separación, usan un algoritmo de coloreado gráfico sobre la relación de desigualdad de estado inducida por los ejemplos negativos.[2]​ Más tarde, investigan varias relaciones de ordenamiento en el conjunto de todas las fusiones de estado posibles.[3]​

Kudo y Shimbo usan la representación por factorizaciones de autómata para proporcionar un marco único para los siguientes enfoques:

Cada uno de estos enfoques corresponde a un tipo particular de relaciones de congruencia usadas para factorizar.[5]​

Enfoques editar

Lenguajes k-reversibles editar

Angluin considera los autómatas regulares "k-reversibles", esto es, autómatas deterministas en los que se puede llegar a cada estado desde a lo sumo un estado siguiendo una cadena de transiciones 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: ∀a0,...,ak ∈ Σ ∀s1, s2 ∈ Q: δ*(s1,a0...ak) = δ*(s2,a0...ak) ⇒ s1 = s2, donde δ* es la extensión homomórfica de δ a palabras arbitrarias. Angluin proporciona un algoritmo de orden cúbico para aprender el lenguaje k-reversible más pequeño a partir de un conjunto dado de palabras de entrada; para k = 0, el algoritmo tiene incluso una complejidad casi lineal.[6]​[7]​ La unicidad de estado requerida después de dados k+1 símbolos obliga a unificar estados del autómata, lo que conduce a una generalización adecuada diferente del autómata subgeneralizado trivial. Este algoritmo se ha utilizado para aprender partes simples de la sintaxis en inglés;[8]​ más tarde, se ha proporcionado una versión incremental.[9]​ Otro enfoque basado en un autómata k-reversible es el método de agrupamiento de cola.[10]​

Autómata sucesor editar

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 dos estados de los caracteres adyacentes.[11]​ Por ejemplo, el conjunto de entrada {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 la repetición de cada carácter inmediatamente a un Kleene + y luego incluye para cada personaje el conjunto de sus posibles predecesores en su estado. Los autómatas sucesores pueden aprender exactamente la clase de los lenguajes locales. Dado que cada lenguaje regular es la imagen homomórfica de un lenguaje local, las gramáticas de la primera clase se pueden aprender levantando, si se proporciona un homomorfismo adecuado (según la aplicación). En particular, existe tal homomorfismo para la clase de lenguajes aprendidos por 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]​

 
Derivación de Brzozowski (en el fondo rojo) de un conjunto de cadenas de un diccionario con respecto a "con"
 
Ilustración del lema de bombeo para un autómata regular.

Aproximaciones tempranas editar

Chomsky y Miller (1957)[15]​ utilizaron el lema del bombeo: supusieron que una parte v de una cadena de entrada uvw y trataron de construir un ciclo correspondiente en el autómata para ser aprendido; usando consultas de membresía, preguntan, para k apropiado, cuál de las cadenas uw, uvvw, uvvvw, ..., uvkw también Pertenece al lenguaje que se 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 al lema de bombeo.[16]​

Autónoma de cubrimiento editar

Câmpeanu et al. entiende 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 =, 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 dicho 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 cubrimiento 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]​ Con base en esta relación, cuya falta de transitividad[note 2]​ causa problemas técnicos considerables, dan un algoritmo O(n4)[note 3]​ para construir desde F un autómata A de cobertura de conteo de estado mínimo. Además, para la unión, intersección y diferencia de dos lenguajes finitos, proporciona operaciones correspondientes en su autómata de cubrimiento.[18]​[19]​ Păun et al. mejora la complejidad temporal a O(n2).[20]​

Autómata residual editar

Para un conjunto S de cadenas y una cadena u, la derivación de Brzozowskiu−1S se define como el conjunto de todas las cadenas de reposo que se pueden obtener de una cadena en S cortando su prefijo u (si es posible), formalmente: u−1S = { v ∈ Σ*: uv ∈ S }, cf. foto.[21]​ Denis et al. define un autómata residual como un autómata finito no determinista A donde cada estado q corresponde a una derivación de Brzozowski de su lenguaje aceptado L(A), formalmente: ∀q∈Q ∃u∈Σ*: L(A,q) = u−1L(A), donde L(A,q) denota el lenguaje aceptado de q como estado de inicio.

Muestran que cada lenguaje regular se genera mediante un autómata residual mínimo determinado de manera única. Sus estados son derivaciones de Brzozowski ∪-indecomposables, 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 suponiendo entradas de muestra óptimas. Proporcionan un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata de su muestra característica de cadenas de entrada positivas y negativas.[22]​[23]​

Expresiones regulares reducidas editar

Brill define una expresión regular reducida como cualquiera de

  • a (donde a es cualquier carácter en Σ; denotando el conjunto unitario que contiene la cadena del carácter a),
  • ¬a (denotando cualquier otro carácter en Σ excepto a),
  • • (denotando cualquier carácter en Σ)
  • a*, (¬a)*, o •* (denotando arbitrariamente muchos, posiblemente cero, repeticiones de caracteres del conjunto de un, ¬a, o •, respectivamente), o
  • r⋅s (donde r y s son expresiones regulares más sencillas; denotando el conjunto de todas las concatenaciones posibles de cadenas de los conjuntos de r y 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 para los errores de ortografía en inglés,[note 4]​ en lugar de las consideraciones teóricas sobre la capacidad de aprendizaje de las clases de los lenguajes. En consecuencia, utiliza heurística para podar la acumulación de árboles, lo que lleva a una mejora considerable en el tiempo de ejecución.[24]​

Aplicaciones editar

Notas editar

  1. ↑ i.e. autómata finito sin estados y transiciones innecesarios con respecto a un conjunto dado de cadenas.
  2. ↑ Por ejemplo, F = { aab, baa, aabb } conduce a aab ~ aabb (solo z=ε necesita ser chequeado para esto) y aabb ~ baa (de forma similar), pero no aab ~ baa (debido a z=b). Sin embargo, de acuerdo con Câmpeanu et al. (2001, Lemma 1, p.5), x ~ y ∧ y ~ z → x ~ z se aplica a las cadenas x, y, z con |x| ≤ |y| ≤ |z|.
  3. ↑ donde n es el número de estados de un autómata finito determinista AF tal que L(AF) = F.
  4. ↑ Por ejemplo: Reemplace "past" por "passed" en el contexto "(¬t⋅o)*⋅SINGULAR_NOUN⋅past"

Referencias editar

  1. ↑ P. Dupont; L. Miclet; E. Vidal (1994). «What is the Search Space of the Regular Inference?». En R. C. Carrasco; J. Oncina, eds. Proceedings of the Second International Colloquium on Grammatical Inference (ICGI): Grammatical Inference and Applications. LNCS 862. Springer. pp. 25-37. 
  2. ↑ F. Coste; J. Nicolas (1997). «Regular Inference as a Graph Coloring Problem». Proc. ICML Workshop on Grammatical Inference, Automata Induction, and Language Acquisition. 
  3. ↑ F. Coste; J. Nicolas (1998). «How Considering Incompatible State Mergings May Reduce the DFA Induction Search Tree». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 199-210. 
  4. ↑ Dominique Luzeaux (Aug 1997). «A Universal Approach to Positive Regular Grammar Inference». Proc. 15th World IMACS Congress on Scientific Computation, Modelling and Applied Mathematics. Archivado desde el original el 13 de enero de 2005. Consultado el 20 de noviembre de 2017. 
  5. ↑ M. Kudo; M. Shimbo (1988). «Efficient Regular Grammatical Inference Techniques by the Use of Partial Similarities and Their Logical Relationships». Pattern Recognition 21: 401-409. doi:10.1016/0031-3203(88)90053-2. 
  6. ↑ D. Angluin (1981). «A Note on the Number of Queries Needed to Identify Regular Languages». Information and Control 51: 76-87. doi:10.1016/s0019-9958(81)90090-5. 
  7. ↑ D. Angluin (1982). «Inference of Reversible Languages». J. ACM 293: 741-765. 
  8. ↑ Robert C. Berwick; Samuel F. Pilato (1987). «Learning Syntax by Automata Induction». Machine Learning 2 (1): 9-38. doi:10.1007/bf00058753. 
  9. ↑ Rajesh Parekh; Codrin Nichitiu; Vasant Honavar (Jan 1997). A Polynomial Time Incremental Algorith for Regular Grammar Inference (Technical report). AI Research Group, Iowa State Univ. p. 14. TR 97-03
  10. ↑ L. Miclet; C. Faure (1985). Reconnaissance des Formes Structrelle: Dèveloppement et Tendances (Technical report). INRIA.
  11. ↑ F. Vernadat; M. Richetin (1984). «Regular Inference for Syntactic Pattern Recognition: A Case Study». Proc. 7th International Conference on Pattern Recognition (ICPR). pp. 1370-1372. 
  12. ↑ P. Garcia; E. Vidal; F. Casacuberta (1987). «Local Languages, The Successor Method, and a Step Towards a General Methodology for the Inference of Regular Grammars». IEEE Trans. on Pattern Analysis and Machine Intelligence 9. 
  13. ↑ Takashi Yokomori (Oct 1989). «Learning Context-Free Languages Efficiently». En K.P. Jantke, ed. Proc. Int. Workshop AII. LNAI 397. Springer. pp. 104-123. 
  14. ↑ Satoshi Kobayashi; Takashi Yokomori (1994). «Learning Concatenations of Locally Testable Languages from Positive Data». En Setsuo Arikawa; Klaus P. Jantke, eds. Proc. 5th ALT. LNAI 872. Springer. pp. 405-422. 
  15. ↑ N. Chomsky; G.A Miller (1957). Pattern Conception (Technical report). ASTIA. Document AD110076.
  16. ↑ R. Solomonoff (Jun 1959). «A New Method for Discovering the Grammars of Phrase Structure Languages». Proc. Int. Conf. on Information Processing. R.Oldenbourg. pp. 285-290. 
  17. ↑ This relation generalizes the relation RF from the Myhill-Nerode theorem. It has been investigated in more detail in sect.3 of: Cynthia Dwork; Larry Stockmeyer (1990). «A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata». SIAM Journal on Computing 19 (6): 1011-1023. doi:10.1137/0219069. 
  18. ↑ a b Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). «Minimal Cover-Automata for Finite Languages». En J.-M. Champarnaud; D. Maurel; D. Ziadi, eds. Proc. Workshop on Implementing Automata (WIA). LNCS 1660. Springer. pp. 43-56. doi:10.1007/3-540-48057-9_4. 
  19. ↑ Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (2001). «Minimal Cover-Automata for Finite Languages». Theoretical Computer Science 267: 3-16. doi:10.1016/s0304-3975(00)00292-9. 
  20. ↑ Andrei Păun; Nicolae Sântean; Sheng Yu (Sep 2001). «An O(n2) Algorithm for Constructing Minimal Cover Automata for Finite Languages». En Sheng Yu; Andrei Păun, eds. Proc. 5th Int. Conf. on Implementation and Application of Automata (CIAA). LNCS 2088. Springer. pp. 243-251. ISBN 978-3-540-42491-8. 
  21. ↑ Janusz A. Brzozowski (1964). «Derivatives of Regular Expressions». JACM 11: 481-494. doi:10.1145/321239.321249. 
  22. ↑ François Denis; Aurélien Lemay; Alain Terlutte (2000). «Learning Regular Languages Using Non Deterministic Finite Automata». En Arlindo L. Oliveira, ed. Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI. LNCS 1891. Springer. pp. 39-50. ISBN 3-540-41011-2. 
  23. ↑ François Denis; Aurélien Lemay; Alain Terlutte (2001). «Learning Regular Languages using RFSA». Proc. ALT '01. 
  24. ↑ a b Eric Brill (2000). «Pattern–Based Disambiguation for Natural Language Processing». Proc. EMNLP/VLC. 
  25. ↑ Alvis Brazma; Inge Jonassen; Jaak Vilo; Esko Ukkonen (1998). «Pattern Discovery in Biosequences». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 257-270. 
  26. ↑ M.S. Waterman, ed. (Jan 1989). Mathematical Methods for DNA Sequences. CRC Press. ISBN 084936664X. 
  27. ↑ Fernando Pereira; Yves Schabes (1992). «Inside-Outside Reestimation for partially Bracketed Corpora». Proc. 30th Ann. Meeting of the Assoc. for Comp. Linguistics. pp. 128-135. 
  28. ↑ Helena Ahonen (Nov 1996). Generating Grammars for Structured Documents Using Grammatical Inference Methods (Ph.D.). Report. A-1996-4. University of Helsinki, Department of Computer Science. 
  29. ↑ Stephen Watkinson (1997). Copia archivada (Master). Dept. of AI, Univ. Edinburgh. Archivado desde el original el 4 de junio de 2001. Consultado el 20 de noviembre de 2017.  |title= y |título= redundantes (ayuda)
  30. ↑ Pedro P. Cruz-Alcázar; Enrique Vidal (1998). «Learning Regular Grammars to Model Musical Style: Comparing Different Coding Schemes». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 211-222. 
  31. ↑ Alexander S. Saidi; Souad Tayeb-bey (1998). «Grammatical Inference in Document Recognition». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 175-186. ISBN 3-540-64776-7. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Inducción_de_lenguajes_regulares&oldid=155250413»