Как работают 20 вопросов AI алгоритмы?

Question

Простые онлайн-игры с 20 вопросами, основанные на невероятно точном ИИ.

Как они так хорошо угадывают?

Answer 1

Вы можете думать об этом как о алгоритме двоичного поиска. В каждой итерации мы задаем вопрос, который должен исключить примерно половину возможных вариантов выбора слова. Если имеется всего N слов, то мы можем ожидать ответа после log2 (N) вопросов.

При 20 вопросах мы должны оптимально найти слово среди 2 ^ 20 = 1 миллиона слов.

Одним из простых способов устранения выбросов (неправильных ответов) было бы, вероятно, использовать что-то вроде RANSAC . Это будет означать, что вместо учета всех вопросов, на которые даны ответы, вы случайным образом выбираете меньшее подмножество, которого достаточно, чтобы дать вам один ответ. Теперь вы повторяете это несколько раз с разными случайными подгруппами вопросов, пока не увидите, что большую часть времени вы получаете один и тот же результат. тогда вы знаете, что у вас есть правильный ответ.

Конечно, это лишь один из многих способов решения этой проблемы.

Answer 2

Рекомендую прочитать об игре здесь: http://en.wikipedia.org/wiki/Twenty_Questions

В частности, раздел Компьютеры:

Игра предполагает, что информация (как измерено энтропией Шеннона статистика) требуется для идентификации Произвольный объект составляет около 20 бит. игра часто используется в качестве примера, когда учить людей информации теория. Математически, если каждый вопрос структурирован для устранения половина объектов, 20 вопросов позволить опрашивающему различать между 2 ²⁰ или 1 048 576 предметов. Соответственно наиболее эффективным Стратегия для двадцати вопросов заключается в задавать вопросы, которые разделят поле оставшихся возможностей примерно в два раза каждый раз. Процесс аналог бинарного поиска алгоритм в информатике.

Answer 3

Дерево решений поддерживает этот тип приложений напрямую. Деревья решений обычно используются в искусственном интеллекте.

Дерево решений - это двоичное дерево, которое задает «лучший» вопрос в каждой ветви, чтобы различать коллекции, представленные его левым и правым потомками. Лучший вопрос определяется некоторым алгоритмом обучения, который создатели приложения из 20 вопросов используют для построения дерева. Затем, как отмечают другие плакаты, дерево глубиной 20 уровней дает вам миллион вещей.

Простой способ определить «лучший» вопрос в каждой точке - найти свойство, которое наиболее равномерно делит коллекцию на две части. Таким образом, когда вы получаете ответ «да» или «нет» на этот вопрос, вы избавляетесь от примерно половины коллекции на каждом этапе. Таким образом, вы можете приблизить бинарный поиск.

Википедия дает более полный пример:

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

И некоторые общие сведения:

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

Answer 4

Он объявляет себя «нейронной сетью в Интернете», и в этом заключается ключ. Вероятно, он сохраняет вероятности вопроса / ответа в запасной матрице. Используя эти вероятности, он может использовать алгоритм дерева решений, чтобы определить, какой вопрос задать, который лучше всего сузит следующий вопрос. Как только он сузит число возможных ответов до нескольких десятков, или если он уже достиг 20 вопросов, он начнет считывать наиболее вероятные.

Действительно интригующим аспектом 20q.net является то, что в отличие от большинства известных мне алгоритмов дерева решений и нейронных сетей, 20q поддерживает разреженную матрицу и постепенные обновления.

Редактировать: Оказывается, ответ был в сети все это время. Робин Бургенер, изобретатель, подробно описал свой алгоритм в своей заявке на патент 2005 .

Answer 5

Используется алгоритм обучения.

k-NN является хорошим примером одного из них.

Википедия: алгоритм k-ближайших соседей