Existem famílias de línguas formais conhecidas por serem verdadeiramente aprendidas pelo PAC?

9

Quero dizer especificamente famílias de idiomas que admitem seqüências arbitrariamente longas - não conjunções sobre n bits ou listas de decisão ou qualquer outra linguagem "simples" contida em {0,1} ^ n.

Estou perguntando sobre as linguagens regulares "teóricas dos autômatos", em oposição às linguagens "teóricas da lógica": algo como as linguagens testáveis ​​por partes, linguagens com zero de altura inicial, linguagens testáveis ​​localmente, esse tipo de coisa. O parâmetro de complexidade relevante n é o tamanho do DFA mínimo aceitável. Então, de forma sucinta: existe uma família interessante de DFAs do estado n que é sabidamente capaz de aprender com eficiência no PAC?

Aryeh
fonte
11
você já olhou para as questões relacionadas: cstheory.stackexchange.com/questions/1401/... e cstheory.stackexchange.com/questions/153/... , bem como esta resposta
Suresh Venkat
11
esta pergunta também pode ser relevante: cstheory.stackexchange.com/questions/1854
Lev Reyzin

Respostas:

4

Há um resultado recente sobre a aprendizagem polinomial do pac de conjuntos semilineares no LICS 2010: Imagens Parikh de Idiomas Regulares: Complexidade e Aplicações . Eu acho que isso não é o que você está procurando.

Você também deve dar uma olhada no artigo de Clark e Thollard: Aprendizagem por PAC de autômatos determinísticos probabilísticos de estados finitos

Sylvain Peyronnet
fonte
2
Certo, eu estou familiarizado com o papel de Clark e Thollard - mas eles fazem suposições de distribuição de modo que não é verdade PAC ...
Aryeh
1

Este artigo fornece uma boa dica sobre o resultado da aprendizagem do PAC para idiomas por partes: Aprendendo idiomas separáveis ​​linearmente

O trabalho de Clark & ​​Thollard foi refinado por Castro & Gavalda de uma maneira que se encaixa no que você está procurando: Rumo a autômatos finitos determinísticos probabilísticos de aprendizagem de PAC possíveis

E este trabalho é uma boa resposta da pergunta inicial: sobre a capacidade de aprender os ideais de reprodução aleatória . É provável que um dos autores seja a mesma pessoa que fez a pergunta aqui anteriormente, mas eu encontrei esta página trabalhando nesse problema e acabei de encontrar este artigo: pode ajudar outros a ter essa referência.

user14249
fonte
3
Meu palpite é que @Aryeh está ciente de pelo menos dois destes trabalhos :)
Lev Reyzin
Na verdade, eu me lembro vagamente da coautoria nº 1 e nº 3 ... Nenhuma delas fornece resultados positivos da PAC do tipo sobre o qual perguntei. No nº 1, exigimos uma margem, que é uma quantidade dependente da distribuição. No # 3, apresentamos fortes resultados negativos.
Aryeh