AMIBE (AMIBE is a Markov IRC Bot for Enjoyment) est un petit projet Java que j'ai mené, en essayant d'apprendre par moi même les bases du langage. Le but étant de réaliser un bot IRC capable de générer des phrases "syntaxiquement correcte" à partir de l'environnement dans lequel il évolue, sur le principe des chaînes de Markov.

Principe general

AMIBE est un bot qui "apprend" à parler, au fur et à mesure qu'on lui parle. Il enregistre la structure de chaque phrases qui lui sont présentées dans un arbre, qu'on peut voir comme un dictionnaire à plusieurs niveaux. Il se servira de ces informations pour générer une phrase dont la structure sera correcte. Ce bot ne parlera pas dans une langue bien spécifique, il parlera dans la langue qu'on lui parle.

Supposons qu'on lui soumette la phrase ça va bien. Le bot ajoutera une nouvelle entrée à son arbre : ça. Cette nouvelle entrée aura comme branche va, qui aura comme branche bien. Si la phrase suivante est ça me va, alors une nouvelle branche sera rajouté à ça, contenant me, qui aura comme branche va. En procédant de la sorte pour chaque phrase, le bot construira sa base de donnée de structure syntaxique et de vocabulaire.

La géneration d'une phrase se fait autour d'un mot donné, par exemple ça. D'après la base de donnée du bot, ça est suivi de que et ça - que est suivant suivi de je. ça - que - je est souvent suivi de suis et ça - que - je - suis est souvent suivi de là. De la même manière, en marchant à reculons sur l'arbre, on voit que ça - que - je - suis - là est souvent précédé par pour et que pour - ça - que - je - suis - là est précédé par c'est. On obtient donc la phrase c'est pour ça que je suis là.

Pour générer facilement une réponse, on utilise un mot de la phrase soumise au bot. L'idéal, pour générer une phrase ayant un sens, serait de repérer le ou les mots porteurs de sens de la phrase, pour mettre de coté les mots comme "le","la","des","ça". Il se trouve que les mots que l'on cherche à éliminer sont en général les plus courant et donc les plus connus par le bot. On va donc générer la phrase autour du mot de la phrase soumise que le bot connait le moins.

Fonctionnement de l'apprentissage

Arbre des mots suivants

Supposons qu'une phrase est envoyée au bot : salut mon ami le bot. Dans un premier temps la phrase va être découpée en unités syntaxiques : mots, ponctuations, liens internet, pseudonymes, etc. Ensuite, la suite d'unités ainsi formée est étudiée dans une certaines fenêtre, par exemple une fenêtre de 3 unités. On étudie donc dans un premier temps salut - mon - ami. On rempli l'arbre à partir de cette fenêtre d'étude, ou chaque unité est le fils de l'unité qui la précède. Puis on décale la fenêtre d'une unité, pour obtenir mon - ami - le. De la même manière, on rempli l'arbre, et on répète le processus jusqu'à avoir étudié chaque unités. On obtient alors l'arbre suivant :

On remarque qu'au premier niveau de l'arbre, on dispose du "dictionnaire" des unités connus par le robot : salut, mon, ami, ., le et bot. Chaque unité dispose également d'un compteur, qui compte le nombre de fois que cette unité a été rencontrée. Pour l'instant, ce compteur est à 1 pour chaque unité.

Maintenant, une seconde phrase est envoyée au bot : Mon ami est malade. De la même manière, on découpe la phrase en unités, est la suite d'unité est étudié sur une fenêtre de 3 unités. On commence par mon - ami - est. La branche mon existe déjà, donc on ne crée pas de nouvelle branche. En revanche, on incremente le compteur pour mon, qui passe à 2. De la même manière, ami comme fils de mon existe déjà. On ne crée pas de nouvelle branche à ce niveau et on incremente le compteur. En revanche est n'existe pas comme fils de ami. On crée donc une nouvelle branche est. On analyse ainsi toute la phrase, pour obtenir ce nouvel arbre.

On remarque que le compteur de chaque noeud ayant un fils est la somme des compteurs de tout ses fils. De cette manière, on remplis progressivement l'arbre, en analysant chaque phrase reçue

Abre des mots précédents

Avec l'arbre construit, on peut facilement trouver les mots qui suivent un mot donné. Ainsi je sait que ami peut être suivi par le qui est suivi par bot qui est suivi par ." qui n'est suivi par rien. Mais il est plus compliqué de trouver les mots qui précedent. C'est possible, mais l'arbre n'as pas été construit pour le permettre, donc l'opération serait compliquée. On va donc construire un autre arbre, qui permet de trouver facilement les mots qui précedent un mot donné. Et le processus est exactement le même que pour l'arbre des mots suivant ... mais avec la phrase à l'envers.

La phrase salut mon ami le bot. devient .tob el ima nom tulas. En analysant la phrase de la même manière que précédemment, on trouve que tob est suivi de el qui est suivi de ima, etc. On obtiens ainsi un nouvel arbre

En lisant cet arbre, on voit que ima suit nom qui suit tulas. Donc ami est précédé par mon qui est précédé par salut. On obtient ainsi notre arbre des mots précédents. Cette arbre est rempli de la même manière que l'arbre suivant, mais avec chaque phrase "à l'envers".

Fonctionnement de la generation de phrase

Maintenant que la phase d'apprentissage a été effectuée, on peut générer une phrase à partir de l'arbre suivant :

Générer la graine

La phrase de réponse est générée à partir d'un mot, la graine. De ce mot, de proche en proche, on peut générer la phrase. Mais comment choisir cette graine ? La phrase généré doit dépendre du message envoyé au robot, donc la graine dépends de ce message. Dans l'idéal, il faudra isoler le prédicat de la phrase, ou des mots porteurs de sens. Les unités les plus employés étant les ponctuations, ou les déterminants et mots de liaisons (et, le, du, etc.), il faut chercher le mot le moins connu de la phrase. De cette manière on a plus de chance de tomber sur un mot fort.

Pour trouver le mot le moins connu, on ne s'occupe que de la partie droite du dictionnaire, et principalement du premier étage. C'est sur le premier étage qu'on trouve les plus fort "poids" pour chaque mot. Par exemple, pour le mot ami, selon la branche il aura comme poids 1 ou 2. Et sur la branche de premier niveau, il a comme poids 2. On a ainsi le "degré de connaissance" du mot. Plus le poids pour le mot au premier niveau est grand, plus il est connu. Ainsi ami est plus connu que malade.

Pour chaque unité du message reçu, on vérifie si elle est presente dans l'arbre (si elle n'est pas présente, la bot ne le connait pas, donc ne pourra pas générer une phrase à partir de cette unité), et si elle l'est on regarde son coefficient. On garde l'unité qui a le coefficient le plus petit : c'est l'unité connue la moins connue par le bot. On s'en servira de graine pour generer la phrase de réponse. Pour la phrase ce bot est mon ami., la graine sera bot ou est, qui ont des coefficient identiques. Dans ce cas, on en choisi une au hasard.

Générer la réponse

A partir de la graine, on va dans un premier temps trouver les mots qui suivent, puis les mots qui précèdent. Supposons que la graine utilisée est : ami. Selon l'arbre, après ami vient le ou est. Chacun ayant un poids identique, on choisi au hasard est (si les poids avaient été différents, on aurait choisi le plus lourd). La réponse est maintenant ami est. On cherche alors quel unité suit ami - est. D'après l'arbre, c'est malade. La réponse est maintenant ami est malade. On cherche alors l'unité qui vient après ami - est - malade. On ne trouve rien, car la profondeur de l'arbre est de 3. On cherche alors l'unité qui vient après est - malade, et on trouve . ce qui donne comme réponse ami est malade . On cherche alors ce qui vient après est - malade - . pour ne rien trouver. Comme après malade - . et . seul. Donc la phrase se termine ici.

Pour le moment, la phrase de réponse est ami est malade. On va trouver les mots qui précèdent cette suite d'unités en inversant cette phrase (.sedalam tse ima) et en appliquant le même principe que précédemment, mais avec la partie gauche de l'arbre. Après sedalam - tse - ima, on ne trouve rien. On cherche donc après tse - ima, pour trouver nom. La phrase de réponse est maintenant .sedalam tse ima nom. On cherche après tse - ima - nom, on ne trouve rien. On cherche donc après ima - nom, pour trouver tulas. Après ima - nom - tulas ne vient rien, comme après nom - tulas et tulas. On dispose donc d'une phrase de réponse : .sedalam tse ima nom tulas. On inverse à nouveau l'ordre des lettres, et on trouve salut mon ami est malade.

Photo : cype_applejuice