Clasificador Akinator.com y Naive Bayes

Contexto: soy un programador con experiencia (medio olvidada) en estadísticas de cursos uni. Recientemente me topé con http://akinator.com y pasé un tiempo tratando de hacerlo fallar. ¿Y quién no? :)

He decidido averiguar cómo podría funcionar. Después de buscar en Google y leer publicaciones de blog relacionadas y agregar algo de mi conocimiento (limitado) a la mezcla resultante, se me ocurre el siguiente modelo (estoy seguro de que usaré la notación incorrecta, no me maten por eso):

Hay temas (S) y preguntas (Q). El objetivo del predictor es seleccionar el sujeto S que tiene la mayor probabilidad posterior de ser el sujeto en el que el usuario está pensando, dadas las preguntas y respuestas recopiladas hasta el momento.

Deje que el juego G sea un conjunto de preguntas y respuestas: .$\{q_1, a_1\}, \{q_2, a_2\} ... \{q_n, a_n\}$

Entonces el predictor está buscando .$P(S|G) = \frac{P(G|S) * P(S)}{P(G)}$

Antes de las asignaturas ( ) podría ser solo la cantidad de veces que se ha adivinado la asignatura dividida por la cantidad total de juegos.$P(S)$

Suponiendo que todas las respuestas son independientes, podríamos calcular la probabilidad del sujeto S dado el juego G así:

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

Podríamos calcular la si realizamos un seguimiento de qué preguntas y respuestas se dieron cuando los usuarios han pensado en el tema dado:$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}$

Ahora, define una distribución de probabilidad sobre los sujetos y cuando necesitamos seleccionar la siguiente pregunta tenemos que seleccionar aquella para la cual el cambio esperado en la entropía de esta distribución es máximo:$P(S|G)$

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

He intentado implementar esto y funciona. Pero, obviamente, a medida que aumenta el número de sujetos, el rendimiento se degrada debido a la necesidad de recalcular la después de cada movimiento y calcular la distribución actualizada para selección de preguntasP ( S | G ∨ { q j , a } $P(S|G)$$P(S|G \vee \{q_j, a\})$

Sospecho que simplemente he elegido el modelo incorrecto, estando limitado por los límites de mi conocimiento. O, tal vez, hay un error en las matemáticas. Por favor, ilumíneme: ¿con qué debería familiarizarme o cómo cambiar el predictor para que pueda hacer frente a millones de sujetos y miles de preguntas?

Este juego se parece a 20 preguntas en http://20q.net , que según el creador se basa en una red neuronal. Aquí hay una forma de estructurar dicha red, similar a la red neuronal descrita en los vectores de descripción del concepto y el juego de 20 preguntas .

Tu tendrias

1. Un número fijo de preguntas, con algunas preguntas marcadas como preguntas "finales".
2. Una unidad de entrada por pregunta, donde 0/1representa la no/yesrespuesta. Inicialmente establecido en0.5
3. Una unidad de salida por pregunta, sigmoide aplastada en 0..1 rango
4. Capa oculta que conecta todas las unidades de entrada a todas las unidades de salida.

Las unidades de entrada para las preguntas que han sido respondidas se establecen en 0 o 1, y se supone que la red neuronal ha sido entrenada para hacer que las unidades de salida emitan valores cercanos a 1 para las preguntas que tienen una respuesta "Sí" dado un conjunto de respuestas existentes.

En cada etapa, elegiría la pregunta de la que NNesté menos seguro, es decir, que la unidad de salida correspondiente esté cerca 0.5, haga la pregunta y establezca la unidad de entrada correspondiente a la respuesta. En la última etapa, elige una unidad de salida de la lista de "preguntas finales" con el valor más cercano a 1.

Cada juego de 20 preguntas proporciona 20 puntos de datos que puede usar para actualizar NNlos pesos con propagación hacia atrás, es decir, actualiza los pesos para hacer que las salidas de la red neuronal actual coincidan con la respuesta verdadera, dadas todas las preguntas anteriores formuladas.

No creo que sea realmente un problema de clasificación. 20 preguntas a menudo se caracterizan como un problema de compresión . En realidad, esto coincide mejor con la última parte de su pregunta cuando habla de entropía.

Consulte el Capítulo 5.7 ( Google books ) de

Cover, TM and Joy, AT (2006) Elementos de la teoría de la información

y también codificación de Huffman . Este artículo que encontré en arXiv también puede ser de interés.

Gill, JT y Wu, W. (2010) "Los juegos de veinte preguntas siempre terminan con Sí" http://arxiv.org/abs/1002.4907

Por simplicidad, asuma preguntas sí / no (mientras que akinator.com permite, tal vez, no sé). Suponga que cada sujeto posible (lo que sabe akinator.com) puede identificarse de manera única mediante una secuencia de preguntas y respuestas de sí / no, esencialmente un vector binario.

Las preguntas que se hacen (y sus respuestas) definen una partición recursiva del espacio de los sujetos. Esta partición también corresponde a una estructura de árbol. Los vértices interiores del árbol corresponden a preguntas, y las hojas corresponden a temas. La profundidad de las hojas es exactamente el número de preguntas requeridas para identificar de forma única el tema. Puede (trivialmente) identificar cada tema conocido haciendo todas las preguntas posibles. Eso no es interesante porque potencialmente hay cientos de preguntas.

La conexión con la codificación Huffman es que proporciona una forma óptima (bajo cierto modelo probabilístico) de construir el árbol de modo que la profundidad promedio sea (casi) mínima. En otras palabras, le dice cómo organizar la secuencia de preguntas (construir un árbol) para que el número de preguntas que necesita hacer sea, en promedio, pequeño. Utiliza un enfoque codicioso.

Por supuesto, hay más en akinator.com que esto, pero la idea básica es que puedes pensar en el problema en términos de un árbol y tratar de minimizar la profundidad promedio de sus hojas.