Aprendizaje automático sin contraejemplos

13

En el marco de aprendizaje de autómatas de Angluin , un estudiante tiene como objetivo aprender un lenguaje regular LΣ haciendo dos tipos de preguntas a su maestro:

Consultas de palabras: dado wΣ , ¿es wL ?

Consultas de equivalencia: dado un lenguaje KΣ , ¿es K=L ? Si no, el profesor da un contraejemplo, es decir, una palabra wKLLK .

Usando el algoritmo de Angluin, el estudiante aprende L con polinomios muchas consultas en el número de estados del DFA mínimo de L y el tamaño de los contraejemplos.

Ahora, considere un escenario restringido donde el maestro ya no da contraejemplos. ¿Todavía es posible aprender L con un número polinómico de consultas? Supongo que este no es el caso porque para cada secuencia de consultas y respuestas de longitud polinómica, uno puede encontrar varios idiomas regulares consistentes con las respuestas.

¿Alguien ve cómo probar esto?

usuario49692
fuente

Respuestas:

20

w{0,1}nMw{w}2n1

n+1M

Aria
fuente
1

De hecho, Mark Gold demostró esta afirmación en su artículo seminal "Identificación del idioma en el límite". Este es un resultado bastante conocido ahora. Puede encontrar más información sobre esto en el libro de Colin de La Higuera sobre Inferencia gramatical.

Manevich romano
fuente