Je suis tombé par hasard (sur internet, on tombe toujours sur quelque chose "par hasard") sur Akinator, le Génie du Web. Le principe ? Vous pensez à un personnage fictif ou réel, vous répondez aux questions du Génie et il devine à qui vous pensiez. A vue de nez, le taux de réussite est certainement supérieur à 95%.

Le résultat est impressionnant et bluffant, surtout quand on choisit des personnages peu connus. L'algorithme tourne également avec des choses (objets et concepts), mais la base de données est moins fournie, donc ça fonctionne un peu moins bien.

Je vous invite à essayer avant de lire la suite, puisque je vais expliquer la façon dont ça fonctionne (ou plus modestement, la façon dont j'imagine que cela fonctionne), et ça risque de rendre moins sympathique ce Génie !

Comme j'imagine la chose, le Génie s'appuie sur une base de données (BDD). Plus les utilisateurs s'en servent, plus la BDD s'enrichit, et plus la certitude liée aux informations contenues dans la BDD augmente. Autrement dit, l'algorithme permet :

- l'apprentissage (en rajoutant dans la BDD des éléments)

- la vérification (en corrigeant dans la BDD les éléments déjà présent)

J'imagine que cette BDD se compose essentiellement d'une table (1) qui contient en entrée les noms des personnages connus et les questions. A l'intersection, on trouve un nombre qui indique la réponse (0 valant pour 'non', 1 pour 'oui' et les valeurs intermédiaires indiquant une probabilité). Cette table ressemblerait à quelque chose comme ça :

Les choix possibles dans les réponses qui sont "vraisemblablement" ou "probablement pas" vaudraient dans ce schéma 0,66 et 0,33. Au fur et à mesure qu'on précise des réponses, l'algorithme peut éliminer des personnages, ce qui lui permet d'éliminer également toutes les questions pour lesquelles la réponse (pour les personnages restants, non éliminés) est 'non'.

Il reste à ajouter une nouvelle table dans la BDD, pour enregistrer la fréquence d'utilisation (l'utilité) des questions posées. L'algorithme va ainsi choisir, pour la première question, une des questions les plus fréquentes. En fonction de la réponse, il va éliminer une grande partie de personnages. Cela lui permet d'éliminer les questions qui sont exclusives de celles déjà posées.

Dans l'exemple ci-dessus, la question "Votre personnage est-il réel ?" est exclusive de la question "Votre personnage est-il un héros de bande dessinée ?" parce qu'aucun personnage ne répond 'oui' aux deux questions. De la même manière, les questions "a-t-il un rapport avec le milieu de la chanson ?" et "est-il toujours vivant ?" ne sont pas exclusives l'une de l'autre car il existe au moins un personnage pour lequel la réponse est 'oui' aux deux questions.

Tout ceci revient à créer un arbre avec les questions, les questions les plus proches de la racine étant les plus fréquentes. Quand on choisit une branche, on exclut un certain nombre de questions - même s'il n'est pas exclu que certaines questions se retrouvent sur plusieurs branches.

Le point le plus délicat est de gérer une certaine tolérance à l'erreur. Si on répond à toutes les questions de manière correcte, mais complètement faux à une question arbitraire, la plupart du temps Akinator trouvera la bonne réponse. Sur la page "Dernières parties", quand on clique sur une des lignes, on peut voir la liste des réponses données pour chaque question, et la réponse attendue. (2)

Concernant l'apprentissage, il est possible de proposer au Génie un nouveau personnage. Cela se fait en répondant à une série de questions, et à la fin, quand on constate l'échec du Génie, en lui précisant le nom du personnage. Il peut alors rajouter une colonne, et inscrire les réponses qu'on a déjà données.

De même, s'il trouve le personnage, l'utilisateur a répondu à des questions qui n'ont peut-être servi à rien parce qu'il en ignorait la réponse. Il peut alors enregistrer les réponses.

Le plus délicat est sans doute d'ajouter une nouvelle question, car d'une part la BDD ne contiendra aucune réponse pour cette question, et d'autre part, elle va commencer avec une utilité paramétrée à 0, donc elle va être appelée très peu souvent, ce qui va ralentir le remplissage de la BDD.

(1) J'ai initialement confondu abusivement table et base de données. J'ai rectifié pour bien faire le distinguo...

(2) Il y a quelques jeux amusants à faire à ce sujet. Je me suis par exemple amusé à répondre aux 10 premières questions en pensant à Napoléon, et aux dix suivantes en pensant à Léonard de Vinci... Le résultat ? Victor Hugo... Si on répond aux questions impaires en pensant à Napoléon et aux questions paire sen pensant à de Vinci, on arrive à... André Le Nôtre.

Pour éviter de polluer la base de données, si on fait ça, il vaut mieux cliquer sur "Non ce n'est pas ça" à la fin...