Akinator.com et Naive Bayes classifier

Contexte: Je suis un programmeur avec une expérience (à moitié oubliée) en statistiques de cours uni. Récemment, je suis tombé sur http://akinator.com et j'ai passé un certain temps à essayer de le faire échouer. Et qui ne l'était pas? :)

J'ai décidé de découvrir comment cela pouvait fonctionner. Après avoir googlé et lu des articles de blog connexes et ajouté certaines de mes connaissances (limitées) dans le mix résultant, je trouve le modèle suivant (je suis sûr que j'utiliserai la mauvaise notation, ne me tuez pas pour cela):

Il y a des sujets (S) et des questions (Q). Le but du prédicteur est de sélectionner le sujet S qui a la plus grande probabilité postérieure d'être le sujet auquel l'utilisateur pense, compte tenu des questions et des réponses recueillies jusqu'à présent.

Soit le jeu G un ensemble de questions posées et de réponses données: .$\{q_1, a_1\}, \{q_2, a_2\} ... \{q_n, a_n\}$

Le prédicteur recherche alors .$P(S|G) = \frac{P(G|S) * P(S)}{P(G)}$

Priorité aux sujets ( ) pourrait être juste le nombre de fois que le sujet a été deviné divisé par le nombre total de jeux.$P(S)$

En faisant l'hypothèse que toutes les réponses sont indépendantes, nous pourrions calculer la probabilité du sujet S étant donné le jeu G comme ceci:

$P(G|S) = \prod_{i=1..n} P(\{q_i, a_i\} | S)$

Nous pourrions calculer le si nous gardons une trace des questions et des réponses qui ont été données lorsque les utilisateurs ont pensé à un sujet donné:$P(\{q_i, a_i\} | S)$

$P({q, a} | S) = \frac{answer\ a\ was\ given\ to\ question\ q\ in\ the\ game\ when\ S\ was\ the\ subject}{number\ of\ times\ q\ was\ asked\ in\ the\ games\ involving\ S}$

Maintenant, définit une distribution de probabilité sur les sujets et lorsque nous devons sélectionner la question suivante, nous devons sélectionner celle pour laquelle le changement attendu dans l'entropie de cette distribution est maximal:$P(S|G)$

$argmax_j (H[P(S|G)] - \sum_{a=yes,no,maybe...} H[P(S|G \vee \{q_j, a\})]$

J'ai essayé de mettre en œuvre cela et cela fonctionne. Mais, évidemment, à mesure que le nombre de sujets augmente, les performances se dégradent en raison de la nécessité de recalculer le après chaque déplacement et de calculer la distribution mise à jour pour sélection des questions.P ( S | G ∨ { q j , a } $P(S|G)$$P(S|G \vee \{q_j, a\})$

Je soupçonne que j'ai simplement choisi le mauvais modèle, étant contraint par les limites de mes connaissances. Ou, peut-être, il y a une erreur dans les calculs. Veuillez m'éclairer: à quoi dois-je me familiariser ou comment changer le prédicteur pour qu'il puisse faire face à des millions de sujets et des milliers de questions?

Ce jeu ressemble à 20 questions sur http://20q.net , dont le créateur rapporte qu'il est basé sur un réseau de neurones. Voici une façon de structurer un tel réseau, similaire au réseau neuronal décrit dans les vecteurs de description du concept et le jeu de 20 questions .

Vous auriez

1. Un nombre fixe de questions, avec certaines questions marquées comme des questions «finales».
2. Une unité d'entrée par question, où 0/1représente la no/yesréponse. Initialement défini sur0.5
3. Une unité de sortie par question, sigmoïde écrasé dans une plage de 0..1
4. Couche cachée reliant toutes les unités d'entrée à toutes les unités de sortie.

Les unités d'entrée pour les questions auxquelles on a répondu sont définies sur 0 ou 1, et l'hypothèse est que le réseau de neurones a été formé pour que les valeurs des unités de sortie produisent des valeurs proches de 1 pour les questions qui ont une réponse "Oui" compte tenu d'un ensemble de réponses existantes.

À chaque étape, vous choisiriez la question qui NNest la moins sûre, c'est-à-dire que l'unité de sortie correspondante est proche 0.5, posez la question et définissez l'unité d'entrée correspondante sur la réponse. À la dernière étape, vous choisissez une unité de sortie dans la liste "question finale" avec la valeur la plus proche de 1.

Chaque jeu de 20 questions donne 20 points de données que vous pouvez utiliser pour mettre à jour NNles poids avec rétropropagation, c'est-à-dire que vous mettez à jour les poids pour que les sorties du réseau neuronal actuel correspondent à la vraie réponse compte tenu de toutes les questions précédentes posées.

Je ne pense pas que ce soit vraiment un problème de classification. 20 questions sont souvent caractérisées comme un problème de compression . Cela correspond en fait mieux à la dernière partie de votre question où vous parlez d'entropie.

Voir le chapitre 5.7 ( Google books ) de

Cover, TM and Joy, AT (2006) Éléments de théorie de l'information

et également le codage Huffman . Cet article que j'ai trouvé sur arXiv peut également être intéressant.

Gill, JT et Wu, W. (2010) "Vingt Questions Les Jeux se terminent toujours par Oui" http://arxiv.org/abs/1002.4907

Pour plus de simplicité, supposez des questions oui / non (alors que akinator.com le permet, peut-être, je ne sais pas). Supposons que chaque sujet possible (ce que sait akinator.com) peut être identifié de manière unique par une séquence de questions / réponses oui / non - essentiellement un vecteur binaire.

Les questions posées (et leurs réponses) définissent une partition récursive de l'espace des sujets. Ce partitionnement correspond également à une arborescence. Les sommets intérieurs de l'arbre correspondent à des questions, et les feuilles correspondent à des sujets. La profondeur des feuilles correspond exactement au nombre de questions nécessaires pour identifier le sujet de manière unique. Vous pouvez (trivialement) identifier chaque sujet connu en posant toutes les questions possibles. Ce n'est pas intéressant car il y a potentiellement des centaines de questions.

Le lien avec le codage de Huffman est qu'il donne un moyen optimal (sous un certain modèle probabiliste) de construire l'arbre de sorte que la profondeur moyenne soit (presque) minimale. En d'autres termes, il vous indique comment organiser la séquence de questions (construire un arbre) afin que le nombre de questions que vous devez poser soit en moyenne petit. Il utilise une approche gourmande.

Il y a bien sûr plus sur akinator.com que cela, mais l'idée de base est que vous pouvez penser au problème en termes d'arbre et essayer de minimiser la profondeur moyenne de ses feuilles.