Aprendizaje de Máquinas de Estados Finitos

Una máquina de estados finitos (autómata finito) es un modelo de cómputo con un conjunto finito de estados, un alfabeto de entrada, una función de transición que indica a qué estado se pasa ante cada símbolo, un estado inicial y estados de aceptación. Kleene demostró en 1956 que estos autómatas reconocen exactamente los lenguajes regulares. Diseñar uno a mano, fijando sus estados y transiciones, es rutina en compiladores, protocolos de red o control industrial.

El aprendizaje de máquinas de estados finitos es otra cosa: no consiste en programar el autómata, sino en inferirlo a partir de datos. Es el objeto de la inferencia gramatical, y confundir ambas tareas, usar una FSM prediseñada y aprender una, es el error de fondo que esta entrada corrige.

Qué significa aprender un autómata

Aprender una FSM es recuperar sus estados y transiciones a partir de ejemplos del comportamiento que debe capturar: cadenas que el sistema acepta y cadenas que rechaza, o registros de secuencias observadas. El objetivo suele ser el autómata determinista mínimo compatible con esos datos, porque es el más simple y el que mejor generaliza. No se supone conocida la estructura de estados; precisamente esa estructura es lo que hay que descubrir.

Aprender frente a diseñar: dos problemas distintos

Hay dos escenarios. En el aprendizaje pasivo se recibe un conjunto fijo de ejemplos etiquetados. Gold demostró en 1978 que hallar el autómata más pequeño consistente con un conjunto de ejemplos positivos y negativos es un problema NP-completo: sin más, no hay algoritmo eficiente conocido. En el aprendizaje activo, el aprendiz interroga a un oráculo. El algoritmo L* de Dana Angluin (1987) aprende un autómata finito determinista en tiempo polinómico mediante dos tipos de consulta a un «maestro mínimamente adecuado»: consultas de pertenencia («¿acepta el sistema esta cadena?») y consultas de equivalencia («¿es correcto este autómata? y si no, dame un contraejemplo»). La diferencia de dificultad entre ambos escenarios es central y la versión anterior la ignoraba.

Autómatas y redes neuronales: relación y límites

El vínculo entre autómatas y redes neuronales es antiguo: ya Kleene, sobre las neuronas de McCulloch y Pitts, mostró que las redes finitas equivalen a autómatas finitos. Pero la equivalencia con las arquitecturas modernas no es incondicional. Una RNN idealizada, con precisión ilimitada, es Turing-completa (Siegelmann y Sontag, 1992); con la precisión finita real colapsa a un comportamiento de estados finitos. No es lo mismo poder implementar un autómata que ser uno. Weiss, Goldberg y Yahav (2018) explotaron esta relación: usando L* con la RNN entrenada como oráculo aproximado, extraen un autómata que describe su dinámica; ese autómata aproxima a la red, no la iguala. Presentar RNN, LSTM, Transformers y el Differentiable Neural Computer como equivalentes funcionales de una FSM, como hacía la versión previa, es incorrecto: los Transformers no tienen estado recurrente y operan sobre una ventana de contexto acotada, y el DNC de DeepMind (Graves y otros, 2016) añade una memoria externa para superar precisamente el límite de memoria finita, de modo que no es una FSM aprendible. Queda abierto cuándo, y con qué garantías, una red neuronal admite una descripción fiel como autómata finito.