Existe-t-il des familles de langues formelles connues pour être véritablement apprenables par PAC?

9

Je veux dire spécifiquement les familles de langues qui admettent des chaînes arbitrairement longues - pas des conjonctions sur n bits ou des listes de décisions ou tout autre langage "simple" contenu dans {0,1} ^ n.

Je pose des questions sur les langages normaux "théoriques des automates" par opposition aux langages "théoriques logiques": quelque chose comme les langages testables par morceaux, les langages à hauteur de début zéro, les langages testables localement, ce genre de choses. Le paramètre de complexité pertinent n est la taille du DFA accepteur minimal. Donc, en résumé: existe-t-il une famille intéressante de DFA à n états qui est connue pour être efficacement apprenable par PAC?

automata-theory machine-learning lg.learning Aryeh
la source
1
avez-vous examiné les questions connexes: cstheory.stackexchange.com/questions/1401/… et cstheory.stackexchange.com/questions/153/… , ainsi que cette réponse
Suresh Venkat
1
cette question pourrait également être pertinente: cstheory.stackexchange.com/questions/1854
Lev Reyzin

Réponses:

4

Il y a un résultat récent sur la pac-learning polynomiale des ensembles semi-linéaires au LICS 2010: Parikh Images of Regular Languages: Complexity and Applications . Je suppose que ce n'est pas ce que vous recherchez.

Vous devriez également jeter un coup d'œil à l'article de Clark et Thollard: PAC-learnability of Probabilistic Deterministic Finite State Automata

Sylvain Peyronnet
la source
2
Bon, je connais le papier de Clark et Thollard - mais ils font des hypothèses de distribution donc ce n'est pas vrai PAC ...
Aryeh
1

Cet article donne une bonne idée du résultat de l'apprentissage PAC pour les langues par morceaux: Apprendre des langues séparables linéairement

Le travail de Clark & ​​Thollard a été affiné par Castro & Gavalda d'une manière qui peut correspondre à ce que vous recherchez: Vers un PAC-learning probabiliste faisable d'automates finis déterministes déterministes

Et ce travail est une bonne réponse à la question initiale: sur la capacité d'apprentissage des idéaux aléatoires . L'un des auteurs est probablement la même personne qui a déjà posé la question ici, mais j'ai trouvé cette page en travaillant sur ce problème et je viens de trouver ce document: cela pourrait aider d'autres à avoir cette référence.

user14249
la source
3
Je suppose que @Aryeh connaît au moins deux de ces articles :)
Lev Reyzin
En effet, je me souviens vaguement de la co-rédaction n ° 1 et n ° 3 ... Aucune de celles-ci ne donne des résultats PAC positifs du type que j'ai demandé. Dans # 1, nous avons besoin d'une marge, qui est une quantité dépendante de la distribution. Dans # 3, nous donnons de forts résultats négatifs.
Aryeh