Me refiero específicamente a las familias de idiomas que admiten cadenas arbitrariamente largas, no conjunciones sobre n bits o listas de decisiones o cualquier otro lenguaje "simple" contenido en {0,1} ^ n.
Estoy preguntando acerca de los lenguajes regulares "autómatas-teóricos" en lugar de los "lógicos-teóricos": algo así como los lenguajes comprobables por partes, los lenguajes de altura inicial cero, los lenguajes comprobables localmente, ese tipo de cosas. El parámetro de complejidad relevante n es el tamaño del DFA mínimo de aceptación. Entonces, en pocas palabras: ¿hay una familia interesante de DFA de n-estados que se sabe que es eficiente para aprender PAC?
Respuestas:
Hay un resultado reciente sobre la capacidad de aprendizaje polinomial pac de conjuntos semilineales en LICS 2010: Parikh Images of Regular Languages: Complexity and Applications . Supongo que esto no es lo que estás buscando.
También debería echar un vistazo al artículo de Clark y Thollard: Aprendizaje de PAC de autómatas deterministas deterministas probabilísticos
fuente
Este documento da una buena pista sobre el resultado del aprendizaje de PAC para idiomas por partes: Aprendizaje de idiomas separables linealmente
El trabajo de Clark & Thollard fue refinado por Castro & Gavalda de una manera que se adapta a lo que está buscando: hacia un autómata finito determinista probabilístico probabilístico factible
Y este trabajo es una buena respuesta a la pregunta inicial: Sobre la capacidad de aprendizaje de los ideales aleatorios . Es probable que uno de los autores sea la misma persona que anteriormente hizo la pregunta aquí, pero encontré esta página trabajando en ese problema y acabo de encontrar este documento: podría ayudar a otros tener esta referencia.
fuente