En el post anterior, os presenté a Akinator, un programa online que, tras hacernos una serie de preguntas, nos mostraba aquel personaje en el que estuviéramos pensando, al estilo de 20p, el programa de Cuatro, o de 20q, que también mostramos por aquí en alguna ocasión.

Discutimos por qué no era posible que el funcionamiento de dicho programa se basase en una búsqueda en una amplia base de datos, y terminé comentando que este post daría la respuesta parcial, puesto que lo que comentaré a continuación es un acercamiento a la técnica que está por detrás (por supuesto, la implementación concreta puede variar en matices).

Primero conviene definir lo que es un árbol de decisión, al menos para que se entienda intuitivamente. Y podemos entender por árbol de decisión a aquella estructura de datos (aunque siempre es implementable a traves de reglas if-then) jerárquica, en la que un nodo superior tiene descendientes, que a su vez poseen otros descendientes, y que éstos nunca se unen con sus nodos superiores.

Con un árbol de este estilo, bien construido, se pueden ir haciendo preguntas desde más generales (más arriba del arbol), a más específicas (más abajo), trazando un camino que nos llevará a una hoja del árbol (un nodo sin descendientes), el cual supondrá la solución al problema. Tenemos por tanto una buena estructura que, de estar bien construida, puede guiarnos a través de un relativo número corto de preguntas hacia una solución. El problema aquí es evidentemente cómo construir tal árbol, y cómo hacer que aprenda, o que se modifique automáticamente para que añada otras preguntas u otros nodos que puedan ser solución también.

El problema del aprendizaje lo voy a dejar para otra ocasión, porque de momento con entender cómo se puede construir eficientemente un árbol de búsqueda será suficiente para tener una idea más intuitiva del funcionamiento de Akinator.

En cuanto a la construcción, vamos a pensar en qué es lo que nos interesa, para ir construyendo una explicación desde ahí. Tenemos información en bruto, y queremos construir un árbol de decisión con el cual podamos “ordenar” dicha información. Nos interesa que las preguntas más generales (las de más arriba del árbol), limiten lo más posible las soluciones restantes, o dicho de otro modo, que eliminen más opciones, y queremos que ocurra esto durante todo el camino que se trazará, para converger lo más rapidamente posible a una solución.

En esta situación necesitamos de algún mecanismo que nos haga saber qué información es más valiosa a la hora de discernir cómo colocarla; podemos verlo como aquella información que nos da más información, que aunque parezca una redundancia es la respuesta. Respuesta que viene dada precisamente a raíz de la teoría de la información de Shannon, en la que se define entropía como la cantidad de información que aporta un valor “x”. Y que matemáticamente se expresa como:

Con ayuda precisamente de la entropía podemos obtener, a partir de un conjunto de variables (que serían los posibles caminos a seguir), qué variable en concreto expresa mayor información (qué camino limita más el espacio de soluciones, de modo que podamos ir montando la estructura del árbol).

Para entender el concepto en concreto, voy a tratar de aplicarlo al caso de Akinator. En el pasado post comenté que tras realizar las preguntas a un compañero, o pensándolas nosotros mismos, caeríamos en la cuenta de que son varios personajes los que pueden coincidir con la “descripción” que ofrece el par pregunta-respuesta. Ahora supongamos que Akinator funcionase adivinando colores, así de simple. Tras un número N de interacciones con Akinator, éste tendría guardado el número de colores que habrá elegido la gente a lo largo de dichas interacciones. Supongamos que tras realizar 10000 preguntas, la gente ha elegido el rojo 8000 veces. Esto es 8000/10000 veces, lo que supone una mayoritaria elección por el rojo. Si aplicamos la fórmula, teniendo en cuenta que la variable en este caso es “Xrojo”, y que la probabilidad de “Xrojo”, es 8000/10000, tenemos que la entropía es mucho menor que para algún otro color cuya probabilidad fuese más baja. Es decir, nos aporta más información saber si el color es el verde, que si es el rojo, puesto que el rojo es más probable. Ahora pensemos en el momento en el que Akinator tiene que darnos una respuesta: gracias a la división que se ha hecho haciendo uso de la entropía, hemos convergido a un número X de soluciones finales, y ahora Akinator está en disposición de pensar que la respuesta que estamos pensando es la más probable, o la que más gente haya pensado antes.

Por tanto, la entropía supone una herramienta que podemos utilizar para construir árboles de decisión, de modo que incluyamos las preguntas más acertadas, que serán aquellas cuya respuesta nos aporte mayor cantidad de información, lo cual supone que limita más la respuesta (reduce en mayor medida el espacio de soluciones restantes).

Quinlan desarrolla el algoritmo ID3 (que se basa en lo explicado pero con algunos cambios), como medio para construir árboles de decisión. Como suele ser habitual, el post se alarga más de lo recomendable, asi que lo dejamos para el siguiente, en el cual trataré de construir un árbol por medio del ID3.