¿Hay mejoras en el algoritmo de Dana Angluin para aprender conjuntos regulares?

33

En su artículo seminal de 1987, Dana Angluin presenta un algoritmo de tiempo polinómico para aprender un DFA a partir de consultas de membresía y consultas teóricas (contraejemplos a un DFA propuesto).

Ella muestra que si está tratando de aprender un DFA mínimo con estados, y su contraejemplo más grande es de longitud , entonces necesita hacer consultas de membresía y, como máximo, consultas teóricas.m O ( m n 2 ) n - 1nmO(mn2)n1

¿Ha habido mejoras significativas en la cantidad de consultas necesarias para aprender un conjunto regular?


Referencias y preguntas relacionadas

Artem Kaznatcheev
fuente
Con suerte, @DominikFreydenberger aparece en algún momento en el futuro. Él sabrá.
Raphael
2
Sospecho que @LevReyzin también sabría la respuesta ... y fue por eso que originalmente consideré preguntar por teoría, pero creo que debería ayudar a hacer crecer este nuevo sitio.
Artem Kaznatcheev
No es una respuesta a la pregunta, pero aún puede ser útil: [ citeulike.org/user/erelsegal-halevi/article/9275508 Un núcleo universal para aprender idiomas regulares]
Erel Segal-Halevi
gracias por el enlace @Erel, pero no entiendo cómo se relaciona. El núcleo universal de Kontorovich no es eficientemente computable, y el modelo de aprendizaje no tiene contraejemplos.
Artem Kaznatcheev

Respuestas:

15

En su respuesta sobre cstheory.SE, Lev Reyzin me dirigió a la tesis de Robert Schapire que mejora el enlace a las consultas de membresía en la sección 5.4.5. El número de consultas de contraejemplo permanece sin cambios. El algoritmo que utiliza Schapire difiere en lo que hace después de una consulta de contraejemplo.O(n2+nlogm)


Bosquejo de la mejora.

En el nivel más alto, Schapire obliga del algoritmo de Angluin a tener la condición adicional de que para un cerrado ( S , E , T ) y cada s 1 , s 2S si s 1s 2 entonces r o w ( s 1 ) r o w ( s 2 ) . Esto garantiza que | S |(S,E,T)(S,E,T)s1,s2Ss1s2row(s1)row(s2) y también hace que laconsistenciacaracterística del algoritmo de Angluin trivial de satisfacer. Para garantizar esto, tiene que manejar los resultados de un contraejemplo de manera diferente.|S|n

Dado un contraejemplo , Angluin simplemente añadido z y todas sus prefijos a S . Schapire hace algo más sutil en lugar de añadir un solo elemento de correo a E . Esta nueva e hará que ( S , E , T ) no se cierre en el sentido de Angluin y la actualización para cerrar con introducir al menos una nueva cadena a S mientras se mantienen distintas las filas. La condición en e es:zzSeEe(S,E,T)Se

s,sS,aΣs.trow(s)=row(sa)ando(δ(q0,se))o(δ(q0,sae))

Donde es la función de salida, q 0 es el estado inicial y δ la regla de actualización del verdadero DFA 'desconocido'. En otras palabras, e debe servir como testigo para distinguir el futuro de s de s a .oq0δmissa

Para calcular esta desde z , hacemos una búsqueda binaria para descubrir una subcadena r i tal que z = p i r i y 0 | p i | = i < | z | tal que el comportamiento de nuestra máquina conjeturada difiere en función de un carácter de entrada. Con más detalle, dejamos que s i ser la cadena que corresponde al estado alcanzado en nuestra máquina conjeturado siguiendo p i . Utilizamos la búsqueda binaria (aquí es donde el registro mezriz=piri0|pi|=i<|z|sipilogmko(δ(q0,skrk))o(δ(q0,sk+1rk+1)rk+1eE

Artem Kaznatcheev
fuente
5

No sé si mi respuesta sigue siendo relevante. Recientemente se ha descrito la implementación de un nuevo algoritmo llamado Paquete de observación o, en algunas circunstancias, Discrimination Tree por Falk Howar. Este algoritmo es como L * pero usa Rivest-Shapire u otro método (vea Steffen e Isberner) para manejar la descomposición del contraejemplo; y utiliza una estructura de datos, un árbol de discriminación (un árbol binario) para hacer eficientemente un "tamiz", es decir, la inserción de una transición A (donde A es cada símbolo del alfabeto) de un nuevo estado encontrado hasta que no haya cierre . Este algoritmo existe en dos versiones: OneGlobally y OneLocally según si el sufijo fundado en la descomposición se agrega a cada componente o no (la relación detrás del algoritmo es que todos los prefijos en un componente son equivalentes a un prefijo corto y representan el mismo estado en el objetivo de acuerdo con los sufijos encontrados en este momento. Más tarde, con un nuevo contraejemplo, se encuentra un nuevo sufijo que discrimina al menos 2 prefijos de un mismo componente. Esto causa una división de ese componente en dos componentes). Con OneLocally hay muchas menos consultas de membresía, pero el número de consultas de equivalencia puede aumentar drásticamente con DFA de gran objetivo. Por el contrario, OneGlobally tiene una cantidad de consultas de membresía siempre menor que L * (pero mayor que OneLocally) y una cantidad similar de consultas de equivalencias que L * Más tarde, con un nuevo contraejemplo, se encuentra un nuevo sufijo que discrimina al menos 2 prefijos de un mismo componente. Esto causa una división de ese componente en dos componentes). Con OneLocally hay muchas menos consultas de membresía, pero el número de consultas de equivalencia puede aumentar drásticamente con DFA de gran objetivo. Por el contrario, OneGlobally tiene una cantidad de consultas de membresía siempre menor que L * (pero mayor que OneLocally) y una cantidad similar de consultas de equivalencias que L * Más tarde, con un nuevo contraejemplo, se encuentra un nuevo sufijo que discrimina al menos 2 prefijos de un mismo componente. Esto causa una división de ese componente en dos componentes). Con OneLocally hay muchas menos consultas de membresía, pero el número de consultas de equivalencia puede aumentar drásticamente con DFA de gran objetivo. Por el contrario, OneGlobally tiene una cantidad de consultas de membresía siempre menor que L * (pero mayor que OneLocally) y una cantidad similar de consultas de equivalencias que L *

Sé que también existe otro algoritmo: el algoritmo TTT que es mejor que el Observation Pack también, pero no tengo un buen conocimiento del mismo. El algoritmo TTT debería ser el estado del arte

Umbert
fuente
Gracias por esta respuesta! ¿Tiene una referencia en papel para el algoritmo Howar y para TTT?
Artem Kaznatcheev el
Esto para el enlace del Paquete de observación Howar y esto para el enlace del algoritmo TTT TTT Puede encontrar la implementación en LearLib (el Paquete de observación se llama allí Árbol de discriminación)
Umbert