Limites inférieures pour l'apprentissage dans la requête d'appartenance et le modèle de contre-exemple

Dana Angluin ( 1987 ; pdf ) définit un modèle d'apprentissage avec des requêtes d'appartenance et des requêtes théoriques (contre-exemples d'une fonction proposée). Elle montre qu'un langage régulier qui est représenté par un DFA minimal de états peut être appris en temps polynomial (où les fonctions proposées sont des DFA) avec$n$ requêtes d'appartenance et au plus n - 1 requêtes théoriques ( m est la taille du plus grand contre-exemple fourni par le tuteur). Malheureusement, elle ne discute pas des limites inférieures.$O(mn^2)$$n−1$$m$

Nous pouvons généraliser légèrement le modèle en supposant un tuteur magique qui peut vérifier l'égalité entre les fonctions arbitraires et fournir des contre-exemples s'ils sont différents. Ensuite, nous pouvons demander à quel point il est difficile d'apprendre des classes plus grandes que les langues normales. Je m'intéresse à cette généralisation et à la restriction d'origine aux langues régulières.

Existe-t-il des limites inférieures connues sur le nombre de requêtes dans le modèle d'appartenance et de contre-exemple?

Je m'intéresse aux limites inférieures du nombre de requêtes d'adhésion, de requêtes théoriques ou de compromis entre les deux. Je m'intéresse aux bornes inférieures pour n'importe quelle classe de fonctions, même pour les classes plus compliquées que les langages ordinaires.

S'il n'y a pas de bornes inférieures: existe-t-il des bariers connus pour prouver les limites inférieures des requêtes dans ce modèle?

Questions connexes

Y a-t-il des améliorations sur l'algorithme de Dana Angluin pour l'apprentissage des ensembles réguliers

$NP \neq coNP$

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

La théorie de l'information est un moyen facile d'obtenir des limites inférieures. Vous pouvez déterminer le nombre de cibles distinctes et le nombre de bits qu'une requête vous donne, etc. Ces limites supérieures se rapprochent mais ne sont pas là. Il y a aussi des questions auxquelles il faut penser quant à la façon dont les «contre-exemples» arrivent à l'apprenant. Un contre-exemple bien choisi peut donner beaucoup d'informations.

Mise à jour de la discussion ci - dessus : Angluin et Dohrn abordent la question de l'apprentissage avec des contre-exemples aléatoires dans un article récent .