Limites mais baixos para aprendizado na consulta de associação e no modelo de contra-exemplo

Dana Angluin ( 1987 ; pdf ) define um modelo de aprendizado com perguntas sobre membros e questões teóricas (contra-exemplos a uma função proposta). Ela mostra que uma linguagem regular representada por um DFA mínimo de estados pode ser aprendida em tempo polinomial (onde as funções propostas são DFAs) com O ( m n 2 ) consultas de associação e no máximo n - 1 consultas de teoria ( m é o tamanho do maior contra-exemplo fornecido pelo tutor). Infelizmente, ela não discute limites inferiores.$n$$O(mn^2)$$n−1$$m$

Podemos generalizar um pouco o modelo assumindo um tutor mágico que possa verificar a igualdade entre funções arbitrárias e fornecer contra-exemplos, se diferentes. Então podemos perguntar o quão difícil é aprender aulas maiores do que as línguas comuns. Estou interessado nesta generalização e na restrição original a idiomas regulares.

Existem limites inferiores conhecidos no número de consultas no modelo de associação e contra-exemplo?

Estou interessado em limites mais baixos no número de consultas de membros, de teoria ou de trocas entre as duas. Estou interessado em limites inferiores para qualquer classe de funções, mesmo para classes mais complicadas que as linguagens regulares.

Se não houver limites inferiores: existem barreiras conhecidas para provar limites inferiores de consulta neste modelo?

Perguntas relacionadas

Existem melhorias no algoritmo de Dana Angluin para aprender conjuntos regulares

$NP \neq coNP$

$O(n)$$O(n^2+ n \log m)$

Uma maneira fácil de obter limites mais baixos é a teoria da informação. Você pode descobrir quantos alvos distintos existem e quantos bits uma consulta fornece, etc. Esses limites superiores se aproximam, mas não existem. Também há questões em que é preciso pensar sobre como os "contra-exemplos" chegam ao aluno. Um contra-exemplo bem escolhido pode fornecer muitas informações.

Atualização para a discussão acima : Angluin e Dohrn abordam a questão da aprendizagem com contra-exemplos aleatórios em um artigo recente .