Inducción de lenguajes regulares
# 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

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

Dupont et al. ha demostrado que el conjunto de todos los autómatas finitos estructuralmente completos 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. 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. Más tarde, investigan varias relaciones de ordenamiento en el conjunto de todas las fusiones de estado posibles.

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

* Lenguajes k-reversibles y el enfoque de seguimiento de "agrupamiento de cola",
* Autómata sucesor y el método predecesor-sucesor, y
* Enfoques basados en el bombeo (sin embargo, la integración del marco es cuestionada por Luzeaux).

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

## Enfoques

### Lenguajes k-reversibles

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: $∀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 δ* 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. 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; más tarde, se ha proporcionado una versión incremental. Otro enfoque basado en un autómata k-reversible es el método de agrupamiento de cola.

### Autómata sucesor

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. 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. La capacidad de aprendizaje de los lenguajes locales se puede reducir a la de los lenguajes k-reversibles.

* 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

Chomsky y Miller (1957) 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, ..., $uv^kw$ 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.

### Autónoma de cubrimiento

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. Con base en esta relación, cuya falta de transitividad causa problemas técnicos considerables, dan un algoritmo O(n4) 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. Păun et al. mejora la complejidad temporal a O(n2).

### Autómata residual

Para un conjunto S de cadenas y una cadena u, la derivación de Brzozowski $u^{−1}S$ 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^{−1}S$ = { v ∈ $Σ^*:$ uv ∈ S }, cf. foto. 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^{−1}L(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.

### Expresiones regulares reducidas

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, 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.

## Aplicaciones

* Encontrar patrones comunes en las descripciones de estructura de ADN y ARN (Bioinformática)
* Modelando la adquisición del lenguaje natural por los humanos.
* Aprendizaje de descripciones estructurales de documentos de ejemplo estructurados, en particular Definiciones de Tipo de Documento (DTD) a partir de documentos SGML.
* Aprender la estructura de las piezas de música.
* Obtener representaciones compactas de lenguajes finitos.
* Clasificación y recuperación de documentos.
* Generación de reglas de corrección dependientes del contexto para errores gramaticales en inglés.
