Pour chaque réponse, Akinator calcule la meilleure question à poser au joueur et donne enfin une supposition sur la personne à laquelle ce joueur pense. Si la première supposition n’est pas correcte, Akinator continue à poser des questions, et ainsi de suite jusqu’à trois suppositions ; la première étant généralement après 15-20 questions. Si la troisième supposition n’est toujours pas correcte, le joueur est invité à ajouter le personnage dans une base de données.

L’algorithme utilisé pour la sélection des questions a été totalement développé par la société française mentionnée ci-dessus, qui a été gardée secrète. Cependant, il est relativement facile de trouver des articles qui décrivent comment l’algorithme a été construit et comment il est utilisé dans Akinator. Dans cet article, je vais vous montrer une façon simple et amusante de comprendre cet algorithme.

Akinator Working

Certains articles déclarent qu’Akinator utilise des arbres de décision, ainsi que des méthodes probabilistes ou l’apprentissage par renforcement. Cet article, se concentrera sur deux algorithmes importants d’arbre de décision ; l’Induction incrémentale des arbres de décision 3 (ID3) et ID4.

Pour plus d’informations sur l’arbre de décision, voir l’article « Modèles d’arbres Concepts fondamentaux »

Induction incrémentale des arbres de décision 3 (ID3)

L’idée de base de l’algorithme ID3 est de construire un arbre de décision en utilisant une recherche descendante et avide à travers les ensembles donnés pour tester chaque attribut sur chaque nœud de l’arbre.

Si vous voulez mieux comprendre ID3, vous pouvez voir l’article :  » Exemple : Calculer l’impureté en utilisant l’entropie et l’indice de Gini. »

Pour trouver une façon optimale de classer un ensemble d’apprentissage, il est nécessaire de minimiser les questions posées(c’est-à-dire minimiser la profondeur de l’arbre). Ainsi, nous avons besoin d’une fonction qui peut mesurer quelles questions fournissent le fractionnement le plus équilibré. La métrique du gain d’information est une telle fonction, c’est-à-dire que le gain d’information est la différence entre la mesure d’impureté de l’ensemble initial (c’est-à-dire, lorsqu’il n’a pas encore été fractionné) et la moyenne pondérée de la mesure d’impureté après l’ensemble fractionné (Dans l’article précédent « Concepts fondamentaux des modèles d’arbres », nous avons étudié que le Gini et l’Entropie sont des mesures d’impureté) :

Où Entropie(S) est les valeurs d’impureté avant la division des données et Entropie(S,X) est l’impureté après la division.

Dans le gain d’information, il y a deux opérations principales pendant la construction de l’arbre :

• Évaluation des fractionnements pour chaque attribut et sélection du meilleur fractionnement et,
• Création de partitions en utilisant le meilleur fractionnement.

Une chose très importante que vous devez toujours comprendre est que la complexité réside dans la détermination du meilleur fractionnement pour chaque attribut et comme dit précédemment, sur la base de l’Entropie ou du Gini, nous pouvons calculer le gain d’information.

Donc, en utilisant le gain d’information, l’algortihm utilisé dans l’arbre ID3 est le suivant :

1. Si toutes les instances sont d’exactement une classe, alors l’arbre de décision est un nœud de réponse contenant ce nom de classe.
2. Sinon,

(a) Définissez a(meilleur) comme étant un attribut (ou une caractéristique) avec le score de gain le plus bas.

(b) Pour chaque valeur V(meilleur,i) de a(meilleur), faire croître une branche de a(meilleur) à un arbre de décision construit récursivement à partir de toutes les instances avec la valeur V(meilleur,i) de l’attribut a(meilleur).

ID4

Un autre algorithme important est ID4. Selon eux, cet algorithme accepte une nouvelle instance d’apprentissage puis met à jour l’arbre de décision, ce qui évite de reconstruire l’arbre de décision pour lequel une structure de données globale a été conservée dans l’arbre original.

La procédure de mise à jour de l’arbre de l’algorithme ID4 de base est donnée ci-dessous.

Entrées : Un arbre de décision, Une instance

sortie : Un arbre de décision

1. Pour chaque attribut de test possible au nœud courant, mettre à jour le compte d’instances positives ou négatives pour la valeur de cet attribut dans l’instance d’entraînement.
2. Si toutes les instances observées au nœud actuel sont positives (négatives), alors l’arbre de décision au nœud actuel est un nœud de réponse contenant un « + » (« -« ) pour indiquer une instance positive (négative).
3. Sinon,

(a) Si le nœud actuel est un nœud de réponse, alors changez-le en un nœud de décision contenant un test d’attribut avec le score de gain le plus bas.

(b) Sinon, si le nœud de décision actuel contient un test d’attribut qui n’a pas le score de gain le plus bas, alors

• Changez le test d’attribut en un test ayant le score de gain le plus bas.
• Eliminez tous les sous-arbres existants sous le nœud de décision.

Mettez à jour récursivement l’arbre de décision sous le nœud de décision actuel le long de la branche de la valeur de l’attribut de test actuel qui apparaît dans la description de l’instance. Faites croître la branche si nécessaire.

Pour plus d’informations sur l’arbre de décision, voir : « Concepts fondamentaux des modèles d’arbres « et « Exemple : Calculer l’impureté en utilisant l’entropie et l’indice de Gini »

.