Para los que aún no lo conocen ,Akinator es un juego de ordenador y una aplicación para móviles creada por la empresa francesa: Elokence.
El objetivo de Akinator es adivinar un personaje real o ficticio. Para adivinar el personaje que el jugador está pensando, Akinator hace una serie de preguntas y el jugador puede responder con ‘Sí’, ‘No sé’, ‘No’, ‘Probablemente’ y ‘Probablemente’ no , entonces el programa determina la mejor pregunta.
Por cada respuesta, Akinator calcula la mejor pregunta para hacer al jugador y, finalmente, da una suposición de en quién está pensando este jugador. Si la primera respuesta no es correcta, Akinator continúa preguntando, y así sucesivamente hasta tres respuestas, la primera de las cuales es generalmente después de 15-20 preguntas. Si la tercera adivinanza sigue sin ser correcta, se pide al jugador que añada el personaje en una base de datos.
El algoritmo utilizado para la selección de las preguntas fue totalmente desarrollado por la empresa francesa mencionada anteriormente, que se ha mantenido en secreto. Sin embargo, es relativamente fácil encontrar artículos que describen cómo se construyó el algoritmo y cómo se utiliza en Akinator. En este artículo, le mostraré una forma sencilla y divertida de entender este algoritmo.
Funcionamiento de Akinator
Algunos artículos declaran que Akinator utiliza Árboles de Decisión, así como Métodos Probabilísticos o Aprendizaje por Refuerzo. Este artículo, se centrará en dos importantes algoritmos de Árboles de Decisión; Inducción Incremental de Árboles de Decisión 3 (ID3) e ID4.
Para más información sobre el Árbol de Decisión, ver el artículo «Modelos de Árbol Conceptos Fundamentales»
Inducción Incremental de Árboles de Decisión 3 (ID3)
La idea básica del algoritmo ID3 es construir un Árbol de Decisión utilizando una búsqueda codiciosa de arriba hacia abajo a través de los conjuntos dados para probar cada atributo en cada nodo del árbol.
Si quieres entender mejor ID3, puedes ver el artículo «Ejemplo: Calcular la impureza usando la entropía y el índice de Gini»
Para encontrar una forma óptima de clasificar un conjunto de aprendizaje, es necesario minimizar las preguntas formuladas (es decir, minimizar la profundidad del árbol). Por lo tanto, necesitamos alguna función que pueda medir qué preguntas proporcionan la división más equilibrada. La métrica de ganancia de información es una función de este tipo, es decir, la ganancia de información es la diferencia entre la medida de impureza del conjunto inicial (es decir cuando aún no ha sido dividido) y la media ponderada de la Medida de Impureza después del conjunto dividido (En el artículo anterior «Modelos de Árbol Conceptos Fundamentales» hemos estudiado que Gini y Entropía son medidas de impureza):
Donde Entropía(S) son los valores de Impureza antes de dividir los datos y Entropía(S,X) es la impureza después de la división.
En Information Gain, hay dos operaciones principales durante la construcción del árbol:
- Evaluación de las divisiones para cada atributo y selección de la mejor división y,
- Creación de particiones utilizando la mejor división.
Una cosa muy importante que siempre debe entender es que la complejidad radica en la determinación de la mejor división para cada atributo y como decir antes, sobre la base de Entropía o Gini, podemos calcular la ganancia de información.
Por lo tanto, utilizando la ganancia de información, el algoritmo utilizado en el árbol ID3 es el siguiente:
- Si todas las instancias son de exactamente una clase, entonces el árbol de decisión es un nodo de respuesta que contiene el nombre de esa clase.
- De lo contrario,
(a) Definir a(mejor) para ser un atributo (o característica) con el menor Gain-score.
(b) Para cada valor V(mejor,i) de a(mejor), hacer crecer una rama desde a(mejor) hasta un árbol de decisión construido recursivamente a partir de todas las instancias con valor V(mejor,i) del atributo a(mejor).
ID4
Otro algoritmo importante es ID4. Argumentan que este algoritmo acepta una nueva instancia de entrenamiento y luego actualiza el árbol de decisión, lo que evita reconstruir el árbol de decisión para que se haya mantenido una estructura de datos global en el árbol original.
El procedimiento básico de actualización del árbol del algoritmo ID4 se da a continuación.
Inputs: Un árbol de decisión, Una instancia
Salida: Un árbol de decisión
- Para cada posible atributo de prueba en el nodo actual, actualiza el conteo de instancias positivas o negativas para el valor de ese atributo en la instancia de entrenamiento.
- Si todas las instancias observadas en el nodo actual son positivas (negativas), entonces el Árbol de Decisión en el nodo actual es un nodo de respuesta que contiene un «+» («-«) para indicar una instancia positiva (negativa).
- De lo contrario,
(a) Si el nodo actual es un nodo de respuesta, entonces cámbielo a un nodo de decisión que contenga una prueba de atributo con la menor puntuación de Ganancia.
(b) En caso contrario, si el nodo de decisión actual contiene una prueba de atributos que no tiene la puntuación de ganancia más baja, entonces
- Cambia la prueba de atributos por una con la puntuación de ganancia más baja.
- Descarta todos los subárboles existentes por debajo del nodo de decisión.
Actualiza de forma recursiva el Árbol de Decisión por debajo del nodo de decisión actual a lo largo de la rama del valor del atributo de la prueba actual que aparece en la descripción de la instancia. Haga crecer la rama si es necesario.
Para más información sobre el Árbol de Decisión vea: «Conceptos fundamentales de los modelos de árbol «y «Ejemplo: Calcular la impureza utilizando la entropía y el índice de Gini»
.