Fonctionnement d'Akinator

[Nightmare]

Bonjour :happy3:

Je pense que la plupart d'entre vous connaissent le fameux "génie du web" Akinator qui a l'art de deviner après une série de question (parfois farfelues) le personnage auquel vous pensez.

Je me suis posé la question comme tout le monde de savoir comment ça marchait. Bien entendu j'ai pensé à quelques trucs mais beaucoup de questions sur le fonctionnement sont obscures. Je voulais savoir ce que vous en pensiez et quelle était votre théorie sur le fonctionnement de ce "génie" !

On se doute tous qu'à la base c'est juste un tableau de critère où chaque colonne est parsemée de noms, en suivant les réponses le génie procède à une sorte de dichotomie, seulement je ne crois pas que ce soit si simple que ça, pour les raisons suivantes :

Premièrement, lorsque le génie nous pose une question, on a pas seulement le choix entre "oui" et "non", on peut aussi choisir "probablement que oui", "probablement que non" et "je ne sais pas".

Les choix "oui" et "non" facilitent l'orientation du robot vers une bonne réponse mais pour le reste, je ne vois pas trop comment il peut réfléchir. Il y a-t-il une question de probabilité?

Deuxièmement, il s'avère que lorsque l'on donne une réponse fausse (par exemple si l'on pense à "George Clooney" et qu'on clique sur "oui" à la question "A-t-il moins de 20 ans?"), pourvu qu'on en donne pas trop, il peut tout de même trouver la bonne réponse. On élimine donc la théorie simple du "on vire tous les noms qui correspondent pas au critère".

Troisièmement, il faut rajouter un paramètre de donnée, le joueur. En effet, lorsque Akinator ne trouve pas la solution, il demande au joueur de le donner. A ce moment là, plusieurs possibilités. Soit le nom est déjà dans la base de donnée et dans ce cas je ne sais pas vraiment comment le programme réagit (va-t-il chercher à améliorer les critères qui décrivent le personnage ou va-t-il considérer que le joueur a simplement mal répondu aux questions et ne rien changer à la base de donnée). Soit le nom n'est pas dans la base et il va surement le rajouter.

Bref, le fonctionnement semble délicat, les programmeurs ont dû y passer énormément de temps.

Avez-vous donc des idées quant au fonctionnement de ce qui pourrait être un monstre de foire informatique?

:happy3:

[uztop]

Bonjour,

je ne connaissais pas Akinator, mais j'ai deja joue avec 20q.net qui est plus ancien je crois et fonctionne sur le meme principe (20 questions pour deviner l'objet ou autre auquel tu penses)
Ils n'expliquent pas grand chose sur le principe de fonctionnement, si ce n'est que ca fonctionne avec un reseau de neurones; si tu as le courage de lire, l'article wikipedia explique un peu comment ca marche.
L'interet de ce systeme est qu'il permet un apprentissage (tu remarqueras que s'il n'a pas trouve, il te demande quelle etait la reponse) et que ce n'est pas sensible aux petites erreurs.

[Nightmare]

Salut :happy3:

Oula ça a l'air compliqué, il n'y a pas un résumé simple?

(tu remarqueras que s'il n'a pas trouve, il te demande quelle etait la reponse)

Oui c'est ce dont je parlais dans mon encadré :happy3:

[uztop]

Salut :happy3:
Oula ça a l'air compliqué, il n'y a pas un résumé simple?

Je ne sais pas, j'aimerais être capable de résumer ça ...
J'ai du avoir une ou deux heures de cours en tout à dessus en école d'ingé, et j'ai évidemment tout oublié.
En gros, un "neurone" possède n entrées et une sortie (il est d'ailleurs possible d'avoir une rétroaction de la sortie en entrée) et il calcule la somme pondérée des n entrées:
Chacun des e(i) vaut 0 ou 1; les sont des coefficients de pondération.
Si F est supérieur à un certain seuil, le neurone est activé et sa sortie vaut 1, sinon elle vaut 0.
Pour l'apprentissage, ça se fait en modifiant les coefficients

[kazeriahm]

In my opinion, c'est un cheminement dans un graphe. Cherche "théorie des graphes" sur Wikipédia ou Google pour un p'tit apercu (des tonnes et des tonnes de trucs sont écrits la dessus dans la littérature, cherche aussi recherche opérationelle).

Un graphe est représenté graphiquement par des sommets et des arrêtes liant ces sommets.

Arkinator te pose des questions assez générales au début (personnage francais ? décédé ? homme ? femme ? artiste ?) avant de spécifier les questions, une fois qu'il a bien cerné à quel groupe de gens appartenait ton perso.

Imagine toi que le programme parcourt le branchage d'un arbre en commencant par sa "base". La première question lui dit sur laquelle des deux branches il doit partir, et ainsi de suite. Plus il avance dans l'arborescence, moins il reste de persos susceptibles d'être les bons, il trouve un point commun entre ces persos et pose une question qui permet de les différentier (d'où certaines questions absurdes parfois du style "votre personnage a t il peur de l'eau ?").

Pour pouvoir revenir sur des critères erronés (l'exemple que tu as donné avec George Clooney), il se garde une petite marge de sécurité, il s'autorise à revenir une ou deux branches en arrière et ainsi à aller voir ce qui se passe dans ces autres branchages. C'est pour ca qu'il peut trouver un mec même si tu as menti.

Quand tu y penses, c'est pas si fou que ca. Imagine que les 20 questions qu'il pose soient toujours les mêmes, et que tu ne puisses répondre que oui ou non. Un personnage est caractérisé par les 20 réponses aux questions. Donc il peut stocker 2^20 personnages avec ce procédé soit de l'ordre de un million de persos...

Demande toi comment Mappy fait pour t'indiquer le chemin le plus court entre Trifouilli les Bains et YoupiLand. C'est le même procédé. Les villes sont les sommets du graphe, elles sont reliées entre elles sont proches, on value l'arc les reliant selon que la liaison se fasse par autoroute, départementale, etc...

Le seul travail à faire est de lancer un algo qui trouve le chemin le plus court dans ce programme.

C'est à peu près le même principe, et c'est un problème assez bien connu maintenant (on a pas de réponse exacte au problème théorique mais les algorithmes numériques fonctionnent bien, la preuve).

J'éspère que c'est clair et pas trop lourd...

[Nightmare]

Merci à tous les 2 :happy3:

Alors, neurones ou graphe? En un sens les neurones semblent être des sortes de graphes.

Kazeriahm > Ton explication est claire, je fais de la théorie des graphes cette année (enfin, faudrait que jme pointe au moins au TD pour prétendre en faire...) donc j'ai saisi le concept et la modélisation du programme par les graphes est intéressante mais je ne pense pas que ce soit cela. Cela voudrait dire qu'en un sens il y a un fil conducteur dans les questions, ce qui, après plusieurs essais, ne semblent pas être le cas. Ce qu'on peut dire c'est qu'effectivement au bout d'un moment les questions sont plus fines, mais je pense qu'il y a un moment déclancheur, ce n'est pas juste le fait qu'on approche du haut de l'arbre. Par exemple lorsqu'on a répondu à plusieurs questions et que plusieurs personnages colle, le programme va chercher une question qui pourrait permettre de supprimer le plus de candidat, ce qui ne semble pas pouvoir être réalisable par un graphe...

[uztop]

oui mais ce que tu proposes ne permet pas vraiment d'apprentissage et n'est pas tolérant aux erreurs (enfin je crois). C'est ces deux caractéristiques qui rendent 20q ou Akinator très intéressants.
Ils disent d'ailleurs sur leur site que c'est un réseau de neurones qui est utilisé : http://stage.20q.net/flat/rbqanda.html
Par contre, je ne connais pas assez bien pour être capable d'expliquer (et de comprendre vraiment) comment ça fonctionne.

[kazeriahm]

en fait la modélisation par un graphe donne un cadre très général. Ce cadre posé, la question est comment circuler dans le graphe ? Autrement dit, comment faire pour prendre une décision, ou comme tu l'as dit toi même, comment ne garder qu'un nombre minimal de branches candidates ?

Pour Mappy la règle est de minimiser soit le cout, soit le temps, etc...

Après, si tu veux virer un grand nombre de candidats avec une question, tu prends le risque que je te réponde dans le mauvais sens du poil (c'est à dire que je vire la minorité et que je garde la majorité, les questions étant fermées).

Sur 20 questions il a le temps de te faire suer jusqu'à trouver le bon gars. D'ailleurs généralement quand il a pas réussi à bien s'orienter à partir de la 14-15ème question, il est cuit, il a plus le temps de différencier.

Enfin bon après je suis pas un expert du tout mais ca me semble être le cadre le plus naturel pour aborder le problème. Beaucoup de problèmes peuvent être modélisés par la théorie des graphes (les programmes d'échecs par exemple !)

[kazeriahm]

je connaissais pas 20q, c'est vachement mieux expliqué que l'autre. Pour moi l'apprentissage consiste juste à rajouter des fruits à l'arbre et l'ajout de question consiste à ajouter des valuations aux branches de l'arbre.

[uztop]

oui, à mon avis 20q fonctionne avec le même algo.
Ce qui me fait dire que ça ne peut pas être un arbre est la tolérance aux erreurs: je viens de faire le test avec Chirac: à la question est-il vivant, j'ai répondu "non" et Akinator a quand même trouvé la réponse; je ne pense pas qu'avec le parcours d'un arbre on puisse réussir à faire ça.

[kazeriahm]

bé justement en fait (rien de définitif dans ce que je dis, je vois ca d'après ce que je sais) je pense que l'algo explore une branche principale mais s'accorde le droit de revenir un ou deux noeuds en arrière (c'est à dire qu'il explore ce qui se serait passé si on avait répondu 1-x à la place de x, pour x la/les réponse/s d'avant. Si il trouve dans ces retours en arrière quelque chose qui correspond mieux, il prend)

[Nightmare]

Kazeriahm > Et comment fonctionne l'avancée dans l'abre? Il y a la difficulté supplémentaire qu'il y a 5 réponses possibles et non plus "oui" ou "non" ... Que se passe-t-il lorsqu'on répond "probablement" ?

[Nightmare]

Parce que justement tu parles de "répondre 1-x à la place de x" mais le système de réponse n'est pas binaire...

[kazeriahm]

en fait cette méthode a un nom dont je ne me rappelle plus, un truc comme bench and quelquechose.

J'avais vaguement vu ca dans un tout autre cadre :
on cherche à calculer le maximum d'une fonction linéaire sur un convexe fermé borné C de R^n. On fait tourner l'algorithme dit du simplexe, pas de problème, on trouve la/les solutions à coordonnées réelles.

Si maintenant on s'intéresse au maximum de cette fonction sur les points de coordonnées entières, on est bien emmerdé, la méthode ne marche plus. On est alors obligé de parcourir certains accroissements de la fonction pour des accroissement entier des coordonnées. Si on se rend compte que ca marchera pas, on retourne en arrière (il y a un critère pour ca).

Bon je me rappelle pas de la méthode en détail ca remonte à loin mais ca existe

[kazeriahm]

quand tu lui dis probablement il fait comme si tu avais dit oui mais il s'autorise encore plus à revenir en arrière.

Quand tu lui dis je sais pas, il cherche un autre noeud voisin

[Nightmare]

Admettons qu'il s'autorise ces retours en arrière dont tu parles, comment est donc définie la marge d'erreur. A partir de quel moment va-t-il se fixer une branche et admettre que c'est la bonne? Parce que si jamais il s'accorde toujours le droit de revenir en arrière en admettant que chaque réponse puisse être fausse, il ne donnerait jamais la solution.

[kazeriahm]

les seuils sont fixés par les programmateurs. A chaque fois qu'on progresse, on oublie les branches trop éloignées qu'on avait exploré en background.

Quand tu dis oui mon personnage a gagné la coupe du monde, c'est que forcément il était footballeur, il va pas revenir la dessus et progresser

[busard_des_roseaux]

bj,

pour gérer certaines affirmations fausses, il emploie peut-être une logique floue où les valeurs de vérité Vrai,Faux appartiennent à l'intervalle ?

question bête: il y a pas une "arnaque" qui consisterait à entretenir un fichier de stats indiquant qu'à un instant donné , la mode est aux questions sur Britney Spear et que Michèle Morgan est en chute libre ?

[kazeriahm]

quand il hésite entre n personnages, il fait son choix en regardant celui qui a été le plus souvent choisi mais il est capable de trouver des mecs pas trop trop connus. D'ailleurs il m'a trouvé des gars comme Gauss ou Poincaré qui sont pas trop des people

[leon1789]

Avant tout, je dois dire que je n'y connais rien en la matière, donc désolé si je dis des bêtises.

Il y les anti-spams qui "apprennent" et "détectent". Mais là, je joue sur 20q.net (merci Imod), et je trouve ça vraiment très impressionnant. Ok, il y a des proba derrière, des coefficients qui évoluent, des réseaux de neurones, etc. mais c'est quand même très réussi ! :++: