Contexto: Soy un programador con algo (casi olvidada) experiencia en estadística de cursos universitarios. Recientemente me encontré con http://akinator.com y pasé un tiempo intentando hacer que fallara. ¿Y quién no? :)
Decidí averiguar cómo podría funcionar. Después de buscar en Google y leer publicaciones de blogs relacionadas y añadir algo de mi (limitado) conocimiento en la mezcla resultante, llegué al siguiente modelo (estoy seguro de que usaré la notación incorrecta, por favor no me maten por eso):
Hay Sujetos (S) y Preguntas (Q). El objetivo del predictor es seleccionar el sujeto S que tiene la mayor probabilidad a posteriori de ser el sujeto en el que el usuario está pensando, dadas las preguntas y respuestas recopiladas hasta ahora.
Sea el juego G un conjunto de preguntas realizadas y respuestas dadas: $\{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)}$.
La probabilidad previa para los sujetos ($P(S)$) podría ser solo el número de veces que se ha adivinado el sujeto dividido por el número total de juegos.
Haciendo la suposición de que todas las respuestas son independientes, podríamos calcular la probabilidad de que el sujeto S dada la partida G sea así:
$P(G|S) = \prod_{i=1..n} P(\{q_i, a_i\} | S)$
Podríamos calcular el $P(\{q_i, a_i\} | S)$ si hacemos un seguimiento de qué preguntas y respuestas se dieron cuando el usuario pensó en un sujeto específico:
$P({q, a} | S) = \frac{la\ respuesta\ a\ fue\ dada\ a\ la\ pregunta\ q\ en\ el\ juego\ cuando\ S\ fue\ el\ sujeto}{número\ de\ veces\ que\ se\ hizo\ la\ pregunta\ q\ en\ los\ juegos\ que\ involucraban\ a\ S}$
Ahora, $P(S|G)$ define una distribución de probabilidad sobre los sujetos y cuando necesitamos seleccionar la próxima pregunta debemos elegir aquella para la cual el cambio esperado en la entropía de esta distribución sea máximo:
$argmax_j (H[P(S|G)] - \sum_{a=sí,no,tal vez...} H[P(S|G \vee \{q_j, a\})]$
Intenté 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 el $P(S|G)$ después de cada movimiento y de calcular la distribución actualizada $P(S|G \vee \{q_j, a\})$ para la selección de preguntas.
Sospecho que simplemente elegí el modelo incorrecto, limitado por los límites de mi conocimiento. O, tal vez, hay un error en las matemáticas. Por favor, ilumínenme: ¿con qué debería familiarizarme, o cómo cambiar el predictor para que pueda manejar millones de sujetos y miles de preguntas?
