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

Dans son article phare de 1987, Dana Angluin présente un algorithme temporel polynomial pour l’apprentissage d’un DFA à partir de requêtes d’appartenance et de requêtes théoriques (contre-exemples d’un DFA proposé).

Elle montre que si vous essayez d'apprendre un DFA minimal avec états et que votre plus grand contre-exemple est de longueur , vous devez alors faire requêtes d'adhésion et au plus requêtes théoriques.m O ( m n 2 ) n - $n$$m$$O(mn^2)$$n - 1$

Y at-il eu des améliorations significatives sur le nombre de requêtes nécessaires pour apprendre un ensemble régulier?

Références et questions connexes

• Dana Angluin (1987) "Apprentissage des ensembles normaux à partir de requêtes et de contre-exemples", Infortmation and Computation 75: 87-106

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

Dans sa réponse sur cstheory.SE, Lev Reyzin m’a orienté vers la thèse de Robert Schapire qui améliore la liaison aux requêtes d’appartenance à dans la section 5.4.5. Le nombre de requêtes de contre-exemple reste inchangé. L'algorithme utilisé par Schapire diffère par ce qu'il fait après une requête contre-exemple.$O(n^2 + n\log m)$

Esquisse de l'amélioration

Au plus haut niveau, Schapire oblige de l’algorithme d’Angluin à avoir la condition supplémentaire que pour un fermé et chaque si alors . Cela garantit que et permet également la cohérence propriété de l'algorithme de Angluin trivial pour satisfaire. Pour ce faire, il doit gérer les résultats d'un contre-exemple différemment.( S , E , T ) s 1 , s 2 ∈ S s 1 ≠ s 2 r o w ( s 1 ) ≠ r o w ( s 2 ) | S | ≤ $(S,E,T)$$(S,E,T)$$s_1, s_2 \in S$$s_1 \neq s_2$$row(s_1) \neq row(s_2)$$|S| \leq n$

Étant donné un contre , Angluin simplement ajouté et tous ses préfixes à . Schapire fait quelque chose de plus subtil en ajoutant à la place un seul élément à . Ce nouvel fera en sorte que ne soit pas fermé au sens angluin et que la mise à jour pour obtenir la fermeture introduise au moins une nouvelle chaîne dans tout en gardant toutes les lignes distinctes. La condition sur est:z S e e e ( S , E , T ) S $z$$z$$S$$e$$E$$e$$(S,E,T)$$S$$e$

Où est la fonction de sortie, est l'état initial et la règle de mise à jour du véritable DFA "inconnu". Autrement dit, doit servir de témoin pour distinguer l’avenir de de .q 0 δ e s s ′$o$$q_0$$\delta$$e$$s$$s'a$

Pour comprendre ce partir de nous effectuons une recherche binaire pour déterminer une sous-chaîne telle que etde telle sorte que le comportement de notre machine conjecturée diffère selon le caractère saisi. Plus en détail, nous allons laisser la chaîne correspondant à l'état atteint dans notre machine conjecturée en suivant . Nous utilisons la recherche binaire (c’est de là que vient le ) pour trouver un tel que . En d'autres termes,z r i z = p i r i 0 ≤ | p i | = i < | z | S i p i connecte m k o ( δ ( q 0 , s k r k ) ) ≠ o ( δ ( q 0 , s k + 1 r k + 1 ) r $e$$z$$r_i$$z = p_ir_i$$0 \leq |p_i| = i < |z|$$s_i$$p_i$$\log m$$k$$o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$ e$r_{k+1}$distingue deux états que nos machines conjecturé trouve équivalentes et ainsi satisfait à la condition sur , donc nous ajoutons à .$e$$E$

Je ne sais pas si ma réponse est toujours pertinente. Récemment, il a été décrit la mise en œuvre d'un nouvel algorithme appelé Observation Pack ou, dans certaines circonstances, Discrimination Tree de Falk Howar. Cet algorithme est similaire à L * mais utilise Rivest-Shapire ou une autre méthode (voir Steffen et Isberner) pour la décomposition du traitement contre-exemple; et il utilise une structure de données, un arbre de discrimination (un arbre binaire) pour effectuer efficacement un "tamisage", à savoir l'insertion d'une transition-A (où A est chaque symbole de l'alphabet) d'un nouvel état trouvé jusqu'à ce qu'il n'y ait pas de fermeture . Cet algorithme existe en deux versions: OneGlobally et OneLocally selon que le suffixe fondé dans la décomposition est ajouté ou non à chaque composant (le ratio derrière l'algorithme est que tous les préfixes d'un composant sont équivalents à un préfixe court et représentent le même état dans la cible en fonction des suffixes trouvés. Plus tard, avec un nouveau contre-exemple, un nouveau suffixe identifiant au moins 2 préfixes d’un même composant est créé, ce qui entraîne une scission de ce composant en deux composants). Avec OneLocally, le nombre de requêtes d’appartenance est beaucoup moins important, mais le nombre de requêtes d’équivalence peut considérablement augmenter avec une cible DFA de grande taille. OneGlobally a plutôt un nombre de requêtes d'appartenance toujours inférieur à L * (mais supérieur à OneLocally) et un nombre similaire de requêtes d'équivalences à L * Plus tard, avec un nouveau contre-exemple, un nouveau suffixe identifiant au moins 2 préfixes d’un même composant est détecté. Cela provoque une scission de ce composant en deux composants). Avec OneLocally, le nombre de requêtes d’appartenance est beaucoup moins important, mais le nombre de requêtes d’équivalence peut considérablement augmenter avec une cible DFA de grande taille. OneGlobally a plutôt un nombre de requêtes d'appartenance toujours inférieur à L * (mais supérieur à OneLocally) et un nombre similaire de requêtes d'équivalences à L * Plus tard, avec un nouveau contre-exemple, un nouveau suffixe identifiant au moins 2 préfixes d’un même composant est détecté. Cela provoque une scission de ce composant en deux composants). Avec OneLocally, le nombre de requêtes d’appartenance est beaucoup moins important, mais le nombre de requêtes d’équivalence peut considérablement augmenter avec une cible DFA de grande taille. OneGlobally a plutôt un nombre de requêtes d'appartenance toujours inférieur à L * (mais supérieur à OneLocally) et un nombre similaire de requêtes d'équivalences à L *

Je sais qu’il existe également un autre algorithme: l’algorithme TTT, qui est meilleur que le pack d’observation également, mais je n’en ai pas une bonne connaissance.