¿Encontrar la expresión regular mínima es un problema de NP completo?

Estoy pensando en el siguiente problema: quiero encontrar una expresión regular que coincida con un conjunto particular de cadenas (por ejemplo, direcciones de correo electrónico válidas) y que no coincida con otras (direcciones de correo electrónico no válidas).

Supongamos que por expresión regular nos referimos a una máquina de estados finitos bien definida, no estoy familiarizado con la terminología exacta, pero estemos de acuerdo en alguna clase de expresiones permitidas.

En lugar de crear manualmente la expresión, quiero darle un conjunto de ejemplos positivos y un conjunto de ejemplos negativos.

Luego debería aparecer una expresión que coincida con los +, rechace los - y sea mínima en un sentido bien definido (¿número de estados en los autómatas?).

Mis preguntas son:

• ¿Se ha considerado este problema, cómo se puede definir de una manera más concreta y se puede resolver de manera eficiente? ¿Podemos resolverlo en tiempo polinómico? ¿Está NP completo, podemos aproximarlo de alguna manera? ¿Para qué clases de expresiones funcionaría? Agradecería cualquier puntero a los libros de texto, artículos o tal que discutan este tema.
• ¿Está relacionado de alguna manera con la complejidad de Kolmogorov?
• ¿Está relacionado de alguna manera con el aprendizaje? Si la expresión regular es consistente con mis ejemplos, en virtud de que es mínima, ¿podemos decir algo sobre su poder de generalización en ejemplos aún no vistos? ¿Qué criterio de minimidad sería más adecuado para esto? ¿Cuál sería más eficiente? ¿Tiene esto alguna conexión con el aprendizaje automático? Una vez más, cualquier puntero sería útil ...

Perdón por la pregunta desordenada ... Apúntame en la dirección correcta para resolver esto. Gracias !

Sí, es NP-Hard. Pitt y Warmuth mostraron que encontrar el DFA más pequeño consistente con una muestra dada no puede aproximarse dentro de para cualquier constante , a menos que .$OPT^k$$k$$P = NP$

Con respecto a la pregunta de aprendizaje: Kearns y Valiant demostraron que puede codificar RSA en un DFA. Por lo tanto, incluso si los ejemplos etiquetados provienen de la distribución uniforme, ser capaz de generalizar a ejemplos futuros (incluso viniendo de la distribución uniforme) rompería el RSA. Por lo tanto, creemos que en el peor de los casos, tener ejemplos etiquetados no ayuda a aprender un DFA (en el modelo PAC). Este es uno de los resultados clásicos de dureza criptográfica para el aprendizaje.

Ambos problemas están entrelazados debido a lo que llamamos el Teorema de la Navaja de Occam . Básicamente establece que si tenemos un procedimiento para encontrar la hipótesis más pequeña de una clase dada que sea consistente con una muestra etiquetada por una hipótesis de la misma clase, entonces podemos PAC aprender esa clase. Entonces, dado el resultado de la dureza RSA, ¡esperaríamos que encontrar el DFA más pequeño y consistente sea difícil en general!

Para agregar un resultado de aprendizaje positivo, Angluin demostró que puedes aprender un DFA si puedes inventar tus propios ejemplos, pero requiere el poder adicional de poder preguntar "¿es correcta mi hipótesis actual?" Este también fue un trabajo fundamental en el aprendizaje.

Para responder a su otra pregunta, todo esto está relacionado con la complejidad de Kolmogorov, ya que el problema de aprendizaje se vuelve más fácil cuando la representación canónica del DFA objetivo tiene poca complejidad.

Respondo los aspectos relacionados con el aprendizaje de la pregunta.

Este problema parece llamarse "aprendizaje de DFA" en la literatura.

Gold [Gol78] mostró que es NP-completo decidir, dados k ∈ℕ y dos conjuntos finitos P y N de cadenas, si existe un autómata determinista de estado finito (DFA) con a lo sumo k estados que acepten cada cadena en P y ninguna de las cadenas en N . El documento [PH01] parece discutir problemas relacionados con esta motivación (puede haber muchos más; esto surgió cuando intenté encontrar documentos relevantes con Google).

Referencias

[Gol78] E Mark Gold. Complejidad de la identificación del autómata a partir de datos dados. Información y control , 37 (3): 302–320, junio de 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh y Vasant Honavar. Aprendizaje de DFA a partir de ejemplos simples. Machine Learning , 44 (1–2): 9–35, julio de 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

A lo largo de esta discusión, se ha asumido que encontrar una expresión regular mínima equivale a encontrar un FSM mínimo que reconozca el lenguaje, pero estas son dos cosas diferentes. Si no recuerdo mal, un DFA se puede minimizar en el tiempo polinómico, mientras que encontrar una expresión regular mínima que represente un lenguaje regular determinado es muy difícil para PSPACE. Este último es uno de esos resultados que pertenecen al folklore de Automata Theory, pero cuya prueba no se puede encontrar en ninguna parte. Creo que se afirma como un ejercicio en el libro de Papadimitrou.

Vea también esta publicación de desbordamiento de pila. El libro que está buscando parece ser Introducción a la teoría de la computación de Michael Sipser.

Estás haciendo un par de preguntas diferentes, por lo que debes responderlas una a la vez:

Is finding a minimal Finite State Machine for a language L NP-complete?

No, no lo es. La publicación Stack Overflow analiza un ingenuo algoritmo n ^ 2 para reducir un FSM a su tamaño mínimo. (Trabajando hacia atrás desde los estados de detención, combine estados que sean "idénticos" en un sentido preciso).

Aparentemente (no seguí el enlace), hay un algoritmo n log n para hacer esto.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

A medida que lo redacta, su conjunto de entrenamiento describe un lenguaje finito . Los idiomas finitos se asignan trivialmente a un FSM: cree un conjunto lineal de estados que terminen en un estado de detención para cada cadena en su idioma, sin necesidad de bucles. Luego, ejecute el algoritmo de minimización FSM en la máquina resultante.

Is this a good way to build a classifier?

Yo no diría eso. Minimizar el FSM no cambia su poder discriminativo, ese es el punto. El FSM mínimo acepta exactamente el conjunto de cadenas como cualquier FSM no mínimo equivalente.

En general, las expresiones regulares no son adecuadas para clasificar datos nuevos. Para cualquier conjunto de entrenamiento finito, obtendrá un RE / FSM que coincide solo con los ejemplos positivos en ese conjunto, sin capacidad de generalizar a nuevos datos. Nunca he visto un enfoque que intente encontrar un lenguaje regular infinito que coincida con algún corpus de entrenamiento.

Para el aprendizaje automático, estaría buscando algo como un ingenuo clasificador de Bayes, un árbol de decisión, una red neuronal o algo más exótico. Inteligencia artificial de Russell y Norvig : un enfoque moderno es un lugar tan bueno como cualquier otro para encontrar una visión general de las técnicas de aprendizaje automático (y mucho, mucho más).