Induction des langages réguliers - Induction of regular languages

Dans la théorie de l'apprentissage informatique , l' induction de langues régulières fait référence à la tâche d'apprendre une description formelle (par exemple la grammaire) d'une langue régulière à partir d'un ensemble donné de chaînes d'exemple. Bien que E. Mark Gold ait montré que tous les langages réguliers ne peuvent pas être appris de cette façon (voir identification du langage dans la limite ), des approches ont été étudiées pour une variété de sous-classes. Ils sont esquissés dans cet article. Pour apprendre des grammaires plus générales, voir Grammar induction .

Exemple

Un langage régulier est défini comme un ensemble (fini ou infini) de chaînes qui peuvent être décrites par l'un des formalismes mathématiques appelés « automate fini », « grammaire régulière », ou « expression régulière », qui ont tous le même pouvoir expressif . Ce dernier formalisme conduisant aux notations les plus courtes, il sera introduit et utilisé ici. Étant donné un ensemble Σ de symboles (alias alphabet), une expression régulière peut être l'un des

  • (désignant l'ensemble vide de chaînes),
  • ε (désignant l'ensemble singleton contenant uniquement la chaîne vide),
  • a (où a est n'importe quel caractère dans Σ ; désignant l'ensemble singleton contenant juste la chaîne à un seul caractère a ),
  • r + s (où r et s sont, à leur tour, des expressions régulières plus simples ; dénotant l'union de leur ensemble)
  • r ⋅ s (représentant l'ensemble de tous les possibles concaténations de chaînes de r « s et l » ensemble de s),
  • r + (désignant l'ensemble des répétitions n fois de chaînes de l'ensemble de r , pour tout n ≥1), ou
  • r * (désignant de la même manière l'ensemble des répétitions n fois, mais incluant également la chaîne vide, considérée comme une répétition 0 fois).

Par exemple, en utilisant Σ = { 0,1 }, l'expression régulière (0+1+ε)⋅(0+1) désigne l'ensemble de tous les nombres binaires à un ou deux chiffres (zéro non significatif autorisé), tandis que 1⋅( 0+1) * ⋅0 désigne l'ensemble (infini) de tous les nombres binaires pairs (pas de zéros non significatifs).

Étant donné un ensemble de chaînes (également appelées « exemples positifs »), la tâche de l'induction en langage régulier est de trouver une expression régulière qui désigne un ensemble les contenant toutes. A titre d'exemple, étant donné { 1, 10, 100 }, une description "naturelle" pourrait être l'expression régulière 1⋅0 * , correspondant à la caractérisation informelle " a 1 suivi d'un nombre arbitraire (voire aucun) 0es ". Cependant, (0+1) * et 1+(1⋅0)+(1⋅0⋅0) est une autre expression régulière, désignant le plus grand (en supposant Σ={0,1}) et le plus petit ensemble contenant les chaînes données et appelé trivial surgénéralisation et undergeneralization , respectivement. Certaines approches fonctionnent dans un cadre étendu où un ensemble de chaînes « d'exemple négatif » est également fourni ; ensuite, une expression régulière doit être trouvée qui génère tous les exemples positifs, mais aucun des exemples négatifs.

Treillis d'automates

Ordre partiel des automates générant les chaînes 1, 10 et 100 (exemples positifs). Pour chacune des chaînes d'exemple négatives 11, 1001, 101 et 0, l' ensemble supérieur d'automates qui la génèrent est affiché. Les seuls automates qui génèrent tous { 1, 10, 100 }, mais aucun de { 11, 1001, 101, 0 } sont l'automate du bas trivial et celui correspondant à l'expression régulière 1⋅0 * .

Dupont et al. ont montré que l'ensemble de tous les automates finis structurellement complets générant un ensemble d'exemples de chaînes d'entrée donné forme un treillis , avec l'automate trivial sous-généralisé et l'automate trivial surgénéralisé comme élément inférieur et supérieur, respectivement. Chaque membre de ce réseau peut être obtenu en factorisant l'automate sous-généralisé par une relation d'équivalence appropriée .

Pour l'exemple de jeu de chaînes ci-dessus { 1, 10, 100 }, l'image montre en bas l'automate sous-généralisé A a,b,c,d en gris , composé des états a , b , c et d . Sur l'ensemble d'états { a,b,c,d }, un total de 15 relations d'équivalence existent, formant un treillis. La mise en correspondance de chaque équivalence E avec le langage automate quotient correspondant L ( A a,b,c,d / E ) obtient l'ensemble partiellement ordonné montré dans l'image. La langue de chaque nœud est indiquée par une expression régulière. Le langage peut être reconnu par des automates quotients par rapport à différentes relations d'équivalence, qui sont toutes montrées sous le nœud. Une flèche entre deux nœuds indique que la langue du nœud inférieur est un sous-ensemble approprié de celle du nœud supérieur.

Si des chaînes d'exemple positives et négatives sont données, Dupont et al. construire le treillis à partir des exemples positifs, puis étudier la frontière de séparation entre les automates qui génèrent des exemples négatifs et ceux qui n'en génèrent pas. Les plus intéressants sont ces automates immédiatement en dessous de la frontière. Dans l'image, des bordures de séparation sont affichées pour les exemples de chaînes négatives 11 ( vert ), 1001 ( bleu) , 101 ( cyan ) et 0 ( rouge ).

Coste et Nicolas présentent une méthode de recherche propre au sein du treillis, qu'ils mettent en relation avec le paradigme de l' espace des versions de Mitchell . Pour trouver la frontière de séparation, ils utilisent un algorithme de coloration de graphe sur la relation d'inégalité d'état induite par les exemples négatifs. Plus tard, ils étudient plusieurs relations d'ordre sur l'ensemble de toutes les fusions d'états possibles.

Kudo et Shimbo utilisent la représentation par factorisations d'automates pour donner un cadre unique pour les approches suivantes (esquissées ci-dessous ) :

Chacune de ces approches correspond à un type particulier de relations d'équivalence utilisées pour la factorisation.

Approches

k -langues réversibles

Angluin considère des automates réguliers dits « k -réversibles », c'est-à-dire des automates déterministes dans lesquels chaque état peut être atteint à partir d'au plus un état en suivant une chaîne de transition de longueur k . Formellement, si Σ, Q , et ô désignent l'alphabet d'entrée, l'ensemble de l' état, et la fonction de transition d'un automate A , respectivement, alors A est appelé k -Réversible si: ∀ a 0 , ..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , un 0 ... a k ) = δ * ( s 2 , un 0 ... a k ) ⇒ de 1 = s 2 , où ô * moyen le l' extension homomorphic de δ à des mots arbitraires. Angluin donne un algorithme cubique pour l'apprentissage du plus petit langage k- réversible à partir d'un ensemble donné de mots d'entrée ; pour k =0, l'algorithme a même une complexité presque linéaire. L'unicité d'état requise après k +1 symboles donnés force l'unification des états de l'automate, conduisant ainsi à une généralisation appropriée différente de l'automate sous-généralisé trivial. Cet algorithme a été utilisé pour apprendre des parties simples de la syntaxe anglaise ; plus tard, une version incrémentielle a été fournie. Une autre approche basée sur les automates k- réversibles est la méthode de clustering de queue .

Automates successeurs

À partir d'un ensemble donné de chaînes d'entrée, Vernadat et Richetin construisent un automate successeur , composé d'un état pour chaque caractère distinct et d'une transition entre chacun des états de deux caractères adjacents. Par exemple, l'ensemble d'entrée singleton { aabbaabb } conduit à un automate correspondant à l' expression régulière ( a + ⋅ b + ) * .

Une extension de cette approche est la méthode prédécesseur-successeur qui généralise immédiatement chaque répétition de caractère à un Kleene + et inclut ensuite pour chaque caractère l'ensemble de ses prédécesseurs possibles dans son état. Les automates successeurs peuvent apprendre exactement la classe des langues locales . Puisque chaque langue régulière est l'image homomorphe d'une langue locale, les grammaires de la première classe peuvent être apprises en soulevant , si un homomorphisme approprié (selon l'application envisagée) est fourni. En particulier, il existe un tel homomorphisme pour la classe des langues apprenantes par la méthode prédécesseur-successeur. L'apprenabilité des langues locales peut être réduite à celle des k -langues réversibles.

Dérivée de Brzozowski (sur fond rouge) d'une chaîne de dictionnaire définie par rapport à " con "
Illustration du lemme de pompage pour les automates réguliers

Approches précoces

Chomsky et Miller (1957) ont utilisé le lemme de pompage : ils devinent une partie v d'une chaîne d'entrée uvw et essaient de construire un cycle correspondant dans l'automate à apprendre ; à l'aide de requêtes d'appartenance, ils demandent, pour le k approprié , laquelle des chaînes uw , uvvw , uvvvw , ..., uv k w appartient également au langage à apprendre, affinant ainsi la structure de leur automate. En 1959, Solomonoff a généralisé cette approche aux langages sans contexte , qui obéissent également à un lemme de pompage .

Couvrir les automates

Campeanu et al. apprendre un automate fini en tant que représentation compacte d'un grand langage fini. Étant donné un tel langage F , ils recherchent un automate dit de couverture A tel que son langage L ( A ) couvre F dans le sens suivant : L ( A ) ∩ Σ ≤ l = F , où l est la longueur de la chaîne la plus longue dans F , et Σ de ploi désigne l'ensemble de toutes les chaînes ne dépasse pas l . Si un tel automate de couverture existe, F est uniquement déterminé par A et l . Par exemple, F = { ad , read , reread } a l =6 et un automate de couverture correspondant à l'expression régulière ( r ⋅ e ) * ⋅ a ⋅ d .

Pour deux chaînes x et y , Câmpeanu et al. définir x ~ y si xz ∈ F ⇔ yz ∈ F pour toutes les chaînes z d'une longueur telle que les deux xz et yz ne sont pas plus longtemps que l . Sur la base de cette relation, dont l'absence de transitivité pose des problèmes techniques considérables, ils donnent un algorithme O ( n 4 ) pour construire à partir de F un automate de couverture A de nombre d'états minimal. De plus, pour l'union, l'intersection et la différence de deux langages finis, ils fournissent des opérations correspondantes sur leurs automates de couverture. Păun et al. améliorer la complexité temporelle à O ( n 2 ).

Automates résiduels

Pour un ensemble S de chaînes et une chaîne u , la dérivée de Brzozowski u −1 S est définie comme l'ensemble de toutes les chaînes restantes pouvant être obtenues à partir d'une chaîne dans S en coupant son préfixe u (si possible), formellement : u −1 S = { v ∈ Σ * : uv ∈ S } , cf. photo. Denis et al. définir un automate résiduel comme un automate fini non déterministe A où chaque état q correspond à une dérivée de Brzozowski de son langage accepté L ( A ), formellement : ∀ q ∈ Q ∃ u ∈Σ * : L ( A , q ) = u − 1 L ( A ) , où L ( A , q ) désigne la langue acceptée à partir de q comme état de départ.

Ils montrent que chaque langage régulier est généré par un automate résiduel minimal déterminé de manière unique. Ses états sont des dérivés de Brzozowski ∪ -indecomposables, et il peut être exponentiellement plus petit que l'automate déterministe minimal. De plus, ils montrent que les automates résiduels pour les langages réguliers ne peuvent pas être appris en temps polynomial, même en supposant des entrées d'échantillon optimales. Ils donnent un algorithme d'apprentissage pour les automates résiduels et prouvent qu'il apprend l'automate à partir de son échantillon caractéristique de chaînes d'entrée positives et négatives.

Apprentissage des requêtes

Les langues régulières ne peuvent pas être apprises en temps polynomial en utilisant uniquement des requêtes d'appartenance ou en utilisant uniquement des requêtes d'équivalence. Cependant, Angluin a montré que les langues régulières peuvent être apprises en temps polynomial en utilisant des requêtes d'appartenance et des requêtes d'équivalence, et a fourni un algorithme d'apprentissage appelé L* qui fait exactement cela. L'algorithme L* a ensuite été généralisé pour produire un NFA ( automates finis non déterministes ) plutôt qu'un DFA ( automates finis déterministes ), via un algorithme appelé NL*. Ce résultat a été encore généralisé et un algorithme qui génère un AFA ( automates finis alternés ) appelé AL* a été conçu. Il est à noter que les NFA peuvent être exponentiellement plus succincts que les DFA, et que les AFA peuvent être exponentiellement plus succincts que les NFA et doublement exponentiellement plus succincts que les DFA.

Expressions régulières réduites

Brill définit une expression régulière réduite comme étant l'une des

  • a (où a est n'importe quel caractère dans Σ ; désignant l'ensemble singleton contenant juste la chaîne à un seul caractère a),
  • ¬ a (désignant tout autre caractère unique dans Σ sauf a ),
  • • (désignant n'importe quel caractère unique dans Σ)
  • a * , (¬ a ) * , ou • * (désignant arbitrairement plusieurs, éventuellement zéro, répétitions de caractères de l'ensemble de a , ¬ a , ou •, respectivement), ou
  • r ⋅ s (où r et s sont, à leur tour, des expressions régulières réduites plus simples ; désignant l'ensemble de toutes les concaténations possibles de chaînes de l'ensemble de r et s ).

Étant donné un ensemble de chaînes d'entrée, il construit étape par étape un arbre avec chaque branche étiquetée par une expression régulière réduite acceptant un préfixe de certaines chaînes d'entrée, et chaque nœud étiqueté avec l'ensemble de longueurs de préfixes acceptés. Il vise à apprendre des règles de correction pour les fautes d'orthographe en anglais, plutôt qu'à des considérations théoriques sur l'apprentissage des cours de langue. Par conséquent, il utilise des heuristiques pour élaguer l'arborescence, conduisant à une amélioration considérable du temps d'exécution.

Applications

Remarques

Les références