Chaîne de Markov, bot, et conversation - Partie 1

Publié le 11 Juin 2008

En mathématiques, une chaîne de Markov est un processus stochastique possédant la propriété markovienne. Dans un tel processus, la prédiction du futur à partir du présent ne nécessite pas la connaissance du passé. Elles ont pris le nom de leur découvreur, Andrei Markov.

Merci pour l'info.

...

Un peu plus (ou moins) sérieusement, les chaînes de Markov permettent de faire des trucs assez rigolo. Comme generer du texte, après une période d'apprentissage et même tenter (et échouer pitoyablement) de tenir une conversation. Il peut arriver qu'il arrive  à dire un truc sencé, mais ca sera le pur fruit du hasard... ou presque.

Avant d'aller plus en avant, je vais reprendre l'exemple de wikipedia :



On prend le cas d'un hamster, amnésique (c'est important, voir la definition au debut du post), qui ne se rappelle pas de ce qu'il faisait la minute d'avant, et qui est capable de faire 3 choses :
- dormir dans ses copeaux.
- manger.
- jouer dans sa roue.

Ces 3 "états" sont representés par les points bleus.
Les fleches représentent le passage d'un état a l'autre.
Les chiffres representent les probabilités de passage d'un etat a l'autre, 1 etant 100%

On considère que toutes les minutes on va laisser le hasard decider de ce qu'il va faire la minute suivante.
On voit qu'il y a des fleches qui pointent vers elle meme, ce qui veut dire "on continue la meme activité" (on ne change pas d'etat).

A la première minute on va considerer que le hamster dort dans ses copeaux (il faut bien partir d'un etat initial).
A la minute suivante :
- il a 90% de chance de continuer a dormir (la fleche 0.9 qui pointe sur elle même)
- 5% de chance de manger
- 5% de chance de faire de l'exercice

On lance les dés... hop ! Il va manger.
II mange pendant 1 minute.
A la minute suivant, on recommence.
On constate que l'etat "mangeoire" n'a pas de fleche vers elle-même, cela veut dire qu'il ne mangera jamais pendant 2 minute d'affilée.
30% de chance d'aller faire de l'exerice.
70% de chance d'aller dormir
0% de continuer a manger.

Je vous laisse deviner pour l'etat "exercice", ca marche pareil.


Maintenant... comment appliquer cela à la generation de texte ?
Pas si compliqué... On remplace les etats par des mots.

prenons un texte d'exemple pour illustrer mon propos :
Bonjour, ca va ?
Bonjour, ca roule !
Super, ca fait plaisir de te voir.


Bon, j'ai simplifié a l'extreme hein. Pour pouvoir faire les calculs de tête.
On constate :
"bonjour" a 100% de chance d'etre suivis du mot "ca"
"ca" a 33% de chance d'etre suivi du mot "va", 33% du mot "roule", 33% du mot "fait".
"super" a 100% de chance d'etre suivi du mot  "ca".
Et ainsi de suite... pour chaque mot. Tache horriblement répetitive, domaine dans lequel l'ordinateur est très largement superieur au cerveau humain. Donc c'est pas un problème.

Ensuite, on prend un mot de depart, on choisi le mot suivant (en tenant compte des probabilité), et on recommence a partir de ce 2ème mot pour en choisir un 3ème. puis un 4ème a partir du 3ème, et etc ...

Ce generateur ne connait aucune règle grammaticale, aucune règle syntaxique, il n'a pas la moindre idée de ce qu'il écrit. Quand il choisi le 3ème mot, il ne tiens pas compte du 1er. Autrement dit, il choisi le mot qui suit, sans tenir compte du mot qui precede. Ce qui peut generer des phrases particulièrement décousue ;)
Mais... étant donné qu'il se base sur ce qu'il a appris, il peut arriver qu'il genere des phrases qui tiennent la route.

Par exemple, j'fais bouffer "Discours de la methode" descarte à un tel generateur et il m'a pondu :
Or j'avoue que les mouvements dans lesquels je ne me reste plus distinctement connoître, comme indivisible;

Bon... c'est pas le meilleur exemple... Descarte étant déjà particulierement complexe à la base, ca ne pouvai pas donner grand chose de bon.

Si on recommence mais avec le contenu de ce post, c'est deja mieux :
70% de ce qui est très largement superieur au cerveau humain.
c'est pas de manger - il choisi le hamster dort dans sa roue.
"super" a 90% de faire les mouvements dans lesquels je vous laisse deviner pour l'etat "exercice", ca marche pareil.


Y'a du mieux !!
Cependant le générateur demande beaucoup d'amélioration, sans toucher au principe de base.
Par exemple, il considère "bonjour" et "bonjour," (avec une virgule) comme etant 2 mots differents, ce qui fout en l'air les probabilités. Mais ca se corrige (considerer chaque ponctuation comme un mot a part entière et les faire entrer dans les tables de probabilités, ignorer completement les ponctuations ouvrante-fermante comme les parenthèse, les guillemets.

Pour eviter ce genre de choses : 0% de chance de chance d'etre suivi du post), qui veut dire qu'il va laisser le passage d'un hamster, amnésique (c'est important, voir la meme activité" (on ne change pas le cas d'un hamster, amnésique (c'est important, voir la definition au cerveau humain.

ou : On prend un tel generateur ne connait aucune règle grammaticale, aucune règle grammaticale, aucune règle grammaticale, aucune règle syntaxique, il peut arriver qu'il faisait la base, ca roule ! Super, ca va faire 3 "états" sont representés par exemple, j'fais bouffer "Discours de texte ? Pas un mot de depart, on prend un mot qui ne change pas compte du 1er.

A suivre dans la partie 2 : comment implémenter ca dans un programme. (on va y retrouver des jolies structures comme dans l'article sur 010 Editor. (en essayant de simplifier au mieux).

Rédigé par kerunix Flan

Publié dans #y'a de l'idée

Repost 0