Para aqueles que ainda não sabem, Akinator é um jogo de computador e aplicativo para celular criado pela empresa francesa: Elokence.
O objectivo do Akinator é adivinhar um personagem real ou fictício. Para adivinhar o personagem que o jogador está pensando, Akinator faz uma série de perguntas e o jogador pode responder com ‘Sim’,’ Não sei’, ‘Não’, ‘Provavelmente’ e ‘Provavelmente’ não , então o programa determina a melhor pergunta.
Para cada resposta, Akinator calcula a melhor pergunta para fazer ao jogador e finalmente dá um palpite sobre quem este jogador está pensando. Se o primeiro palpite não estiver correto, Akinator continua a fazer perguntas, e assim por diante, até três palpites; o primeiro sendo geralmente depois de 15-20 perguntas. Se o terceiro palpite ainda não estiver correto, o jogador é solicitado a adicionar o personagem em uma base de dados.
O algoritmo usado para a seleção de perguntas foi totalmente desenvolvido pela empresa francesa mencionada acima, o que foi mantido em segredo. Entretanto, é relativamente fácil encontrar artigos que descrevem como o algoritmo foi construído e como ele é usado no Akinator. Neste artigo, vou mostrar uma maneira simples e divertida de entender este algoritmo.
Akinator Working
Akinator usa Árvores de Decisão, assim como Métodos Probabilísticos ou Aprendizagem de Reforço. Este artigo, irá focar em dois importantes algoritmos de Árvore de Decisão; Indução Incremental de Árvores de Decisão 3 (ID3) e ID4.
Para mais informações sobre a Árvore de Decisão, veja o artigo “Tree Models Fundamental Concepts”
Incremental Induction of Decision Trees 3 (ID3)
A ideia básica do algoritmo ID3 é construir uma Árvore de Decisão usando uma busca de cima para baixo e gananciosa através dos conjuntos dados para testar cada atributo em cada nó da árvore.
Se você quiser entender melhor o ID3, você pode ver o artigo: “Exemplo”: Compute the Impurity using Entropy and Gini Index”
Para encontrar uma maneira ideal de classificar um conjunto de aprendizagem, é necessário minimizar as questões feitas (ou seja, minimizar a profundidade da árvore). Assim, precisamos de alguma função que possa medir quais perguntas fornecem a divisão mais equilibrada. A métrica do Ganho de Informação é essa função, ou seja, o Ganho de Informação é a diferença entre a Medida de Impureza do conjunto inicial (i.e, quando ainda não foi dividida) e a média ponderada da Medida de Impureza após a divisão do conjunto (no artigo anterior “Modelos de Árvore Conceitos Fundamentais” estudamos que Gini e Entropia são medidas de impureza):
Onde Entropia(S) é o valor de Impureza antes da divisão dos dados e Entropia(S,X) é a impureza após a divisão.
Em Information Gain, há duas operações principais durante a construção de árvores:
- Avaliação de partições para cada atributo e seleção da melhor partição e,
- Criação de partições usando a melhor partição.
Uma coisa muito importante que você deve sempre entender é que a complexidade está na determinação da melhor partição para cada atributo e como dito anteriormente, baseado em Entropia ou Gini, nós podemos computar o Ganho de Informação.
Hence, usando Information Gain,o algoritmo usado na árvore ID3 é o seguinte:
- Se todas as instâncias são de exatamente uma classe, então a árvore de decisão é um nó de resposta contendo o nome dessa classe.
- Outra classe,
(a) Defina a(melhor) para ser um atributo (ou recurso) com o menor Gain-score.
(b) Para cada valor V(best,i) de a(best), faça crescer um ramo de a(best) para uma árvore de decisão construída recursivamente a partir de todas aquelas instâncias com valor V(best,i) de atributo a(best).
ID4
Um outro algoritmo importante é o ID4. Eles argumentam que este algoritmo aceita uma nova instância de treinamento e então atualiza a árvore de decisão, o que evita reconstruir a árvore de decisão para que uma estrutura de dados global tenha sido mantida na árvore original.
O procedimento básico de atualização do algoritmo ID4 é dado abaixo.
inputs: Uma árvore de decisão, Uma instância
output: Uma árvore de decisão
- Para cada atributo de teste possível no nó atual, atualize a contagem de instâncias positivas ou negativas para o valor desse atributo na instância de treinamento.
- Se todas as instâncias observadas no nó atual forem positivas (negativas), então a Árvore de decisão no nó atual é um nó de resposta contendo um “+” (“-“) para indicar uma instância positiva (negativa).
- Outra,
(a) Se o nó atual for um nó de resposta, então altere-o para um nó de decisão contendo um teste de atributo com a menor pontuação de Ganho.
(b) Caso contrário, se o nó de decisão atual contém um teste de atributo que não tem o menor Gain-score, então
- Mude o teste de atributo para um com o menor Gain-score.
- Descartar todas as sub-árvores existentes abaixo do nó de decisão.
Atualize novamente a Árvore de decisão abaixo do nó de decisão atual ao longo do ramo do valor do atributo teste atual que ocorre na descrição da instância. Cresça o ramo se necessário.
Para mais informações sobre a Árvore de decisão veja: “Árvore de Modelos Conceitos Fundamentais” e “Exemplo: Calcule a Impureza usando Entropia e Índice de Gini”