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

103

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

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

Папа варбокс
источник
Кажется, это 20 лучших вопросов по ИИ, которые я когда-либо видел. В противном случае я бы связался с одним из других.
Daddy Warbox
1
Отлично. Хотя, насколько я могу судить, Akinator, кажется, догадывается гораздо более интуитивно, чем 20q.net. Меня интересует, что делает его, так сказать, «умным».
Daddy Warbox
1
я понятия не имел, что эта штука существует в сети. К моему удивлению, он угадал «шишку» с третьей попытки! Впечатляет
Петер Перхач
3
+1 - определенно связано с программированием и хороший вопрос.
Адам Дэвис,
@JeffAtwood, на какую статью вы пытались дать ссылку?
antony.trupe

Ответы:

55

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

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

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

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

Йог
источник
4
Эта простая программа достаточно хорошо демонстрирует то, о чем вы говорите. Попав туда, вы можете щелкнуть codeссылку, чтобы увидеть ее: openbookproject.net/py4fun/animal/animal.html
Ноктис Скайтауэр,
Доступен ли такой ИИ в качестве услуги? Что, если бы я мог предоставить все вопросы и ответы и позволить ему их найти?
tggagne
А как вы называете такой алгоритм? У него есть название?
tggagne
25

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

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

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

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

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

И немного общей предыстории:

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

Натан Шивели-Сандерс
источник
2
+1, замечу, что это был один из комментариев в статье Этвуда.
cgp
1
Это правда, хотя в BASIC-программе Animal нет алгоритма обучения, чтобы определять, какие вопросы использовать и как высоко в дереве их ставить. Производительность с обученным деревом решений должна быть намного лучше. (Я согласен с комментатором, что вопросы, которые получил Этвуд, очень похожи на то, что они были сгенерированы оригинальным алгоритмом Animal, а не нейронной сетью.)
Натан Шивели-Сандерс,
24

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

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

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

cgp
источник
2
Это кое-что объясняет. Но если учесть неправильные ответы и общую двусмысленность, это все еще кажется не таким простым.
Daddy Warbox
1
Если вы посмотрели ссылку, то увидите, что это не совсем вопрос типа «да / нет», который может каждый раз делить поле пополам. Хотя ваш ответ верен на 20 вопросов, я думаю, что ответ Шона более точен, простой алгоритм обучения ближайшего соседа и достаточный пользовательский ввод позволяют получить очень точные результаты.
z -
Ах, правда, они похожи, но определенно ближайший сосед имеет больше смысла.
cgp
12

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

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

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

Cerin
источник
6

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

k-NN - хороший пример одного из них.

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

Шон Мейсон
источник
4
Является ли алгоритм ближайшего соседа хорошим выбором в этом случае? Казалось бы, это было бы слишком снисходительным к неправильным ответам и могло бы привести к огромному количеству измерений, многие из которых не имеют данных. (Я предполагаю использование расстояния Хэмминга и одного измерения на вопрос.) Дерево решений кажется более естественным.
Килотан
1
Теория обучения - правильный ответ - неважно, что она дает менее «точные» ответы, потому что она основана на ошибках, которые каждый склонен делать, что на самом деле помогает лучше угадывать.
Джонатан Плэкетт