L'inférence grammaticale (ou induction grammaticale, en anglais ou ). est le processus, en apprentissage automatique, consistant à apprendre une grammaire formelle — généralement sous la forme d'un ensemble de règles de réécriture ou productions, ou bien sous celle d'un automate fini ou d'un autre type d'automate — à partir d'un ensemble d'observations, construisant ainsi un modèle rendant compte des caractéristiques des objets observés. Plus généralement, l'inférence grammaticale est la branche de l'apprentissage automatique dans laquelle l'espace des instances est constitué d'objets combinatoires discrets tels que des chaînes, des arbres et des graphes.
Classes de grammaires
L'inférence grammaticale s'est souvent concentrée sur le problème de l'apprentissage d'automates finis de divers types (voir l'article pour le détail de ces approches), car il existe des algorithmes efficaces pour ce problème depuis les années 1980.
Depuis le début du , ces approches ont été étendues au problème de l'inférence de grammaires non contextuelles et de formalismes plus riches, comme les grammaires non contextuelles multiples et les grammaires non contextuelles multiples parallèles. Parmi les autres classes de grammaires pour lesquelles l'inférence grammaticale a été étudiée figurent les , les grammaires non contextuelles stochastiques., les grammaires contextuelles et les langages de motifs.
Modèles d'apprentissage
La forme la plus simple d'apprentissage est celle où l'algorithme reçoit seulement un ensemble d'exemples tirés du langage considéré : le but est d'apprendre le langage à partir d'exemples de celui-ci (et, plus rarement, de contre-exemples, c'est-à-dire d'exemples qui n'appartiennent pas au langage). D'autres modèles d'apprentissage ont toutefois été étudiés. Une variante fréquemment étudiée est celle où l'apprenant peut poser des requêtes d'appartenance, comme dans le modèle d'apprentissage par requêtes exactes ou modèle de l'enseignant minimalement adéquat () introduit par Angluin..
Méthodes
Il existe une grande variété de méthodes d'inférence grammaticale. Deux sources classiques sont Fu (1977) et Fu (1982). Duda, Hart et Stork (2001) consacrent également une brève section au problème et citent plusieurs références ; la méthode élémentaire par essais et erreurs qu'ils présentent est décrite ci-dessous. Pour les approches visant à inférer en particulier des sous-classes de langages réguliers, voir . Un manuel plus récent est celui de de la Higuera (2010), qui couvre la théorie de l'inférence grammaticale des langages réguliers et des automates finis. D'Ulizia, Ferri et Grifoni proposent une étude des méthodes d'inférence grammaticale pour l'apprentissage des langues naturelles..
Induction de grammaires probabilistes
Il existe plusieurs méthodes d'induction de grammaires non contextuelles probabilistes...
Inférence grammaticale par essais et erreurs
La méthode proposée à la section 8.7 de Duda, Hart et Stork (2001) consiste à deviner successivement des règles de grammaire (productions) et à les tester sur des observations positives et négatives. L'ensemble de règles est étendu de façon à pouvoir engendrer chaque exemple positif ; mais si un ensemble de règles donné engendre aussi un exemple négatif, il doit être écarté. Cette approche particulière peut être caractérisée comme du « test d'hypothèses » et présente une certaine similitude avec l'algorithme de l'espace de versions de Mitchell. Le texte de Duda, Hart et Stork (2001) fournit un exemple simple qui illustre bien le procédé, mais la viabilité d'une telle approche par essais et erreurs non guidée pour des problèmes plus conséquents est douteuse.
Inférence grammaticale par algorithmes génétiques
L'induction grammaticale par algorithmes évolutionnistes est le processus consistant à faire évoluer une représentation de la grammaire d'un langage cible au moyen d'un processus évolutif. Les grammaires formelles peuvent aisément être représentées par des structures arborescentes de règles de production susceptibles d'être soumises à des opérateurs évolutionnaires. Les algorithmes de ce type sont issus du paradigme de la programmation génétique introduit par John Koza. D'autres travaux anciens sur des langages formels simples utilisaient la représentation par chaînes binaires des algorithmes génétiques, mais la structure intrinsèquement hiérarchique des grammaires exprimées en EBNF a fait des arbres une approche plus souple.
Koza représentait les programmes Lisp sous forme d'arbres. Il a pu trouver des analogues aux opérateurs génétiques au sein de l'ensemble standard des opérateurs sur les arbres. Par exemple, l'échange de sous-arbres correspond au processus de croisement génétique, où des sous-chaînes d'un code génétique sont transplantées dans un individu de la génération suivante. La qualité (fitness) est mesurée en évaluant la sortie des fonctions du code Lisp. Des analogies similaires entre la représentation arborescente en Lisp et la représentation des grammaires sous forme d'arbres ont rendu possible l'application des techniques de programmation génétique à l'induction grammaticale.
Dans le cas de l'induction grammaticale, la transplantation de sous-arbres correspond à l'échange de règles de production permettant l'analyse de phrases d'un langage. L'opérateur de qualité de la grammaire repose sur une mesure de sa performance à analyser un groupe de phrases du langage cible. Dans une représentation arborescente d'une grammaire, un symbole terminal d'une règle de production correspond à une feuille de l'arbre. Ses nœuds parents correspondent à un symbole non terminal (par exemple un syntagme nominal ou un syntagme verbal) de l'ensemble de règles. Finalement, le nœud racine peut correspondre à un non-terminal « phrase ».
Inférence grammaticale par algorithmes gloutons
Comme tous les algorithmes gloutons, les algorithmes gloutons d'inférence grammaticale prennent, de manière itérative, les décisions qui semblent les meilleures à chaque étape. Les décisions prises portent généralement sur la création de nouvelles règles, la suppression de règles existantes, le choix d'une règle à appliquer ou la fusion de règles existantes. Comme il existe plusieurs façons de définir « l'étape » et « le meilleur », il existe aussi plusieurs algorithmes gloutons d'inférence grammaticale.
Les algorithmes suivants, qui engendrent une grammaire non contextuelle, prennent leur décision après chaque symbole lu : l'algorithme Lempel-Ziv-Welch crée une grammaire non contextuelle de manière déterministe, de sorte qu'il suffit de stocker la règle de départ de la grammaire engendrée ; l'algorithme Sequitur et ses variantes. Les algorithmes suivants, qui engendrent également une grammaire non contextuelle, lisent d'abord la séquence de symboles entière avant de prendre des décisions : l'encodage par paires d'octets () et ses optimisations.
Apprentissage distributionnel
Une approche plus récente repose sur l'apprentissage distributionnel. Les algorithmes utilisant ces approches ont été appliqués à l'apprentissage de grammaires non contextuelles et de langages faiblement contextuels, et il a été démontré qu'ils sont corrects et efficaces pour de larges sous-classes de ces grammairesClark et Eyraud (2007), Journal of Machine Learning Research ; Ryo Yoshinaka (2011), Theoretical Computer Science..
Apprentissage des langages de motifs
Angluin définit un motif comme « une chaîne de symboles constants de Σ et de symboles variables issus d'un ensemble disjoint ». Le langage d'un tel motif est l'ensemble de toutes ses instances closes non vides, c'est-à-dire toutes les chaînes résultant du remplacement cohérent de ses symboles variables par des chaînes non vides de symboles constantsLe langage d'un motif comportant au moins deux occurrences d'une même variable n'est pas rationnel, en vertu du lemme de l'étoile.. Un motif est dit descriptif pour un ensemble fini de chaînes en entrée si son langage est minimal (au sens de l'inclusion) parmi tous les langages de motifs contenant l'ensemble d'entrée.
Angluin donne un algorithme polynomial qui calcule, pour un ensemble de chaînes en entrée, tous les motifs descriptifs à une variable xx peut apparaître plusieurs fois, mais aucune autre variable y ne peut apparaître.. Pour ce faire, elle construit un automate représentant tous les motifs potentiellement pertinents ; au moyen d'arguments élaborés sur les longueurs de mots, qui reposent sur le fait que x est la seule variable, le nombre d'états peut être considérablement réduit..
Erlebach donnent une version plus efficace de l'algorithme d'apprentissage de motifs d'Angluin, ainsi qu'une version parallélisée.. Arimura montrent qu'une classe de langages obtenue à partir d'unions limitées de motifs peut être apprise en temps polynomial..
Théorie des motifs
La théorie des motifs, formulée par Ulf Grenander., est un formalisme mathématique décrivant la connaissance du monde sous forme de motifs. Elle se distingue des autres approches de l'intelligence artificielle en ce qu'elle ne commence pas par prescrire des algorithmes et des dispositifs pour reconnaître et classer des motifs ; elle prescrit plutôt un vocabulaire pour articuler et reformuler les concepts de motifs dans un langage précis.
Outre ce nouveau vocabulaire algébrique, son approche statistique était novatrice par son objectif de : identifier les variables cachées d'un jeu de données en utilisant des données réelles plutôt que des stimuli artificiels, ce qui était courant à l'époque ; formuler des distributions a priori pour les variables cachées et des modèles pour les variables observées, qui forment les sommets d'un graphe de type gibbsien ; étudier le caractère aléatoire et la variabilité de ces graphes ; créer les classes fondamentales de modèles stochastiques en énumérant les déformations des motifs ; synthétiser (échantillonner) à partir des modèles, et pas seulement analyser des signaux avec eux. De couverture mathématique large, la théorie des motifs embrasse l'algèbre et la statistique, ainsi que des propriétés topologiques locales et entropiques globales.
Applications
Le principe de l'induction grammaticale a été appliqué à d'autres aspects du traitement automatique du langage naturel et a notamment servi (parmi de nombreux autres problèmes) à l'analyse sémantique, à la compréhension du langage naturel, à la traduction automatique à base d'exemples, à l'acquisition du langage, à la et à la détection d'anomalies.
Voir aussi Articles connexes
Traduction automatique à base d'exemples
Complexité de Kolmogorov
Grammaire linéaire
Notes et références Notes
Références
Bibliographie
Lien externe QSMM — analyseurs adaptatifs pour l'induction de grammaires non contextuelles par modèle.
Catégorie:Traitement automatique du langage naturel Catégorie:Linguistique informatique Catégorie:Apprentissage automatique Catégorie:Langage formel