Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
4 janvier 2011 2 04 /01 /janvier /2011 16:42

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 :


Question Personnage A Personnage B Personnage C
Votre personnage est-il célèbre ? 1 0 1
Votre personnage est-il un homme ? 1 1 0
Votre personnage est-il réel ? 1 0 1

Votre personnage est-il un héros de bande dessinée ?

0 1 0
Votre personnage  a-t-il fait  de la politique ? 1 0 0
Votre personnage  est-il  un leader religieux ? 0 0 0
Votre personnage a-t-il un rapport avec le milieu de la chanson ? 0 0 1
Votre personnage  est-t-il  toujours vivant ? 0 0 1
Votre personnage est-il millionnaire ? 0 1 1

 

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...

Partager cet article

Repost 0
Published by Christophe - dans Geek
commenter cet article

commentaires

bob 06/08/2011 09:56


Bonjour, très bonne explication !
Cependant je ne comprend pas bien comment faire pour choisir une question une fois que la première à été proposée et que des résultats ai été supprimé.
Pourriez vous éclaircir ce point ?

Merci d'avance


Christophe 17/08/2011 19:59



Bonjour et merci.


Je suppose que toutes les questions en mémoire sont "notées" suivant leur pertinence. Les questions qui sont posées à l'utilisateur sont donc tirées aléatoirement au sort parmi les questions les
plus pertinentes qui restent plausibles en fonction des réponses passées de l'utilisateur.


Quant à la manière dont la "pertinence" d'une question est évaluée, je dirais qu'elle est directement reliée à la façon dont elle découpe une population. Les questions binaires (mort / vivant)
sont par exemple plus pertinentes que des questions à choix multiples (cheveux bruns / blonds / roux...). De même, la question du sexe, homme ou femme, est très pertinente, car elle coupe la
population en deux ; en une seule question, on peut diviser par deux l'ensemble des réponses possibles...



Isa 05/01/2011 17:58


le plus compliqué avec une BDD, c'est pas de s'en servir, c'est de la concevoir ;)

chouette explication ceci dit, encore un mythe du web qui s'écroule ^^


Christophe 05/01/2011 18:19



Je trouvais ça plutôt amusant de les concevoir... enfin c'est la partie la plus intéressante du travail !


Pour l'exploitation de la base, la maintenance est souvent assez pénible si on n'a pas construit un bon outil dès le départ. J'ai des mauvais souvenirs avec l'intranet de mon école...



Claire 05/01/2011 17:37


Ouais enfin, j'ai eu un "cours" où on nous a expliqué vite fais comment elle fonctionnait la BDD biodiversité, ça avait pas l'air si simple que ce que tu décris. Y'avait des histoires de plusieurs
tableaus, avec des croisements dynamiques...j'avoue que j'ai pas tt suivi !!!!


Christophe 05/01/2011 18:00



Le travail sur une BDD peut rapidement devenir compliqué, si on commence à créer un vrai modèle conceptuel de données. Mais ça, ça dépend bien sûr de l'usage qu'on va avoir de la base...


Ici, j'ai abusivement confondu les termes BDD (qui regroupe plusieurs tables) et une table précise, que je donne en exemple. Je vais corriger ça...



Claire 05/01/2011 17:20


ben je pensais pas que c'était si compliqué une BDD, ça à l'air tellement simple quand je rentre les infos pour compléter la BDD biodiversité !!!!


Christophe 05/01/2011 17:35



Une BDD n'est pas très compliquée, ça n'est jamais rien de plus qu'un tableau qui stocke des infos. Mais les choses ont tendance à devenir compliquées quand c'est moi qui les explique, je
crois...



A Propos

  • : Christophe
  • Christophe
  • : Un blog qui parle de tout et de rien. Technologie, société et internet, mes (més)aventures, mes rencontres.
  • Contact

Archives