Como funcionam os algoritmos de IA de 20 questões?

Jogos online simples de 20 questões alimentados por uma IA assustadoramente precisa.

Como eles adivinham tão bem?

Você pode pensar nisso como o algoritmo de pesquisa binária. Em cada iteração, fazemos uma pergunta, que deve eliminar aproximadamente metade das opções de palavras possíveis. Se houver um total de N palavras, podemos esperar obter uma resposta após log2 (N) perguntas.

Com 20 perguntas, devemos ser capazes de encontrar uma palavra entre 2 ^ 20 = 1 milhão de palavras.

Uma maneira fácil de eliminar outliers (respostas erradas) seria provavelmente usar algo como RANSAC . Isso significaria que, em vez de levar em consideração todas as perguntas que foram respondidas, você escolhe aleatoriamente um subconjunto menor, que é o suficiente para lhe dar uma única resposta. Agora você repete isso algumas vezes com diferentes subconjuntos aleatórios de perguntas, até ver que na maioria das vezes, está obtendo o mesmo resultado. então você sabe que tem a resposta certa.

É claro que essa é apenas uma das muitas maneiras de resolver esse problema.

Uma árvore de decisão suporta esse tipo de aplicativo diretamente. Árvores de decisão são comumente usadas em inteligência artificial.

Uma árvore de decisão é uma árvore binária que faz a "melhor" pergunta em cada ramo para distinguir entre as coleções representadas por seus filhos esquerdo e direito. A melhor pergunta é determinada por algum algoritmo de aprendizado que os criadores do aplicativo de 20 perguntas usam para construir a árvore. Então, como outros pôsteres apontam, uma árvore de 20 níveis de profundidade fornece um milhão de coisas.

Uma maneira simples de definir "a melhor" pergunta em cada ponto é procurar uma propriedade que divida a coleção pela metade da maneira mais uniforme. Dessa forma, ao obter uma resposta sim / não para essa pergunta, você se livra de cerca de metade da coleção em cada etapa. Desta forma, você pode aproximar a pesquisa binária.

A Wikipedia dá um exemplo mais completo:

http://en.wikipedia.org/wiki/Decision_tree_learning

E algumas informações gerais:

http://en.wikipedia.org/wiki/Decision_tree

Recomendo ler sobre o jogo aqui: http://en.wikipedia.org/wiki/Twenty_Questions

Em particular a seção de Computadores:

O jogo sugere que a informação (medida pela estatística de entropia de Shannon) necessária para identificar um objeto arbitrário é de cerca de 20 bits. O jogo é frequentemente usado como exemplo ao ensinar as pessoas sobre a teoria da informação. Matematicamente, se cada pergunta for estruturada para eliminar metade dos objetos, 20 perguntas permitirão ao questionador distinguir entre 2 ²⁰ ou 1.048.576 assuntos. Conseqüentemente, a estratégia mais eficaz para as vinte perguntas é fazer perguntas que dividirão o campo das possibilidades restantes aproximadamente pela metade a cada vez. O processo é análogo a um algoritmo de busca binária em ciência da computação.

Ela se autodenomina "a rede neural na internet" e é aí que está a chave. Provavelmente armazena as probabilidades de pergunta / resposta em uma matriz sobressalente. Usando essas probabilidades, é capaz de usar um algoritmo de árvore de decisão para deduzir qual pergunta fazer que melhor restringiria a próxima pergunta. Uma vez que ele reduz o número de respostas possíveis para algumas dezenas, ou se já atingiu 20 perguntas, ele começa a ler o mais provável.

O aspecto realmente intrigante do 20q.net é que, ao contrário da maioria dos algoritmos de árvore de decisão e rede neural que conheço, o 20q suporta uma matriz esparsa e atualizações incrementais.

Edit: Acontece que a resposta está na rede esse tempo todo. Robin Burgener, o inventor, descreveu seu algoritmo em detalhes em seu pedido de patente de 2005 .

Ele está usando um algoritmo de aprendizado.

k-NN é um bom exemplo de um deles.

Wikipedia: algoritmo do vizinho mais próximo k