Как работают алгоритмы ИИ 20 вопросов?
простые онлайн-игры из 20 вопросов, работающих на устрашающе точный ИИ.
как они так хорошо думаю?
5 ответов:
вы можете думать об этом как о бинарном алгоритме поиска. На каждой итерации мы задаем вопрос, который должен исключить примерно половину возможных вариантов слов. Если есть всего N слов, то мы можем ожидать получить ответ после log2(N) вопросов.
с 20 вопросом мы должны оптимально найти слово среди 2^20 = 1 миллиона слов.
один простой способ устранить выбросы (неправильные ответы) было бы, вероятно, использовать что-то вроде RANSAC. Это означало бы, что вместо учета всех вопросов, на которые были даны ответы, вы случайным образом выбираете меньшее подмножество, которого достаточно, чтобы дать вам один ответ. Теперь вы повторяете это несколько раз с разными случайными подмножествами вопросов, пока не увидите, что большую часть времени вы получаете тот же результат. тогда вы знаете, что у вас есть правильный ответ.
конечно, это только один из многих способов решения этой проблемы.
Я рекомендую прочитать об игре здесь:http://en.wikipedia.org/wiki/Twenty_Questions
в частности, раздел компьютеры:
игра предполагает, что информация (как измеряется энтропией Шеннона статистика) требуется для идентификации произвольный объект, составляет около 20 бит. Этот игра часто используется в качестве примера при обучение людей информации теория. Математически, если каждый вопрос построен таким образом, чтобы исключить половина объектов, 20 вопросов разрешить вопрос отличить между 220 или 1.048.576 предметам. Соответственно, наиболее эффективны стратегия для двадцати вопросов заключается в том, чтобы задавайте вопросы, которые разделят поле оставшихся возможностей примерно пополам каждый раз. Процесс является аналогом двоичного поиска алгоритм в информатике.
дерево решений поддерживает этот вид приложения напрямую. Деревья принятия решений обычно используются в искусственном интеллекте.
дерево решений-это двоичное дерево, которое задает "лучший" вопрос в каждой ветви, чтобы различать коллекции, представленные его левыми и правыми дочерними элементами. Лучший вопрос определяется некоторым алгоритмом обучения, который создатели приложения 20 вопросов используют для построения дерева. Затем, как указывают другие плакаты, дерево глубиной 20 уровней дает вам миллион вещей.
простой способ определить" лучший " вопрос в каждой точке-найти свойство, которое наиболее равномерно делит коллекцию на половину. Таким образом, когда вы получаете ответ "Да/нет" на этот вопрос, вы избавляетесь от половины коллекции на каждом шаге. Таким образом, вы можете приблизить двоичный поиск.
Википедия дает более полное пример:
http://en.wikipedia.org/wiki/Decision_tree_learning
и некоторые общие справочная информация:
Он называет себя" нейронной сетью в интернете", и в этом заключается ключ. Вероятно, он хранит вероятности вопросов/ответов в запасной матрице. Используя эти вероятности, он может использовать алгоритм дерева решений, чтобы вывести, какой вопрос задать, который лучше всего сузит следующий вопрос. Как только он сужает число возможных ответов до нескольких десятков, или если он уже достиг 20 вопросов, то он начинает считывать наиболее вероятные.
действительно интригует аспект 20q.net в отличие от большинства алгоритмов дерева решений и нейронной сети, о которых я знаю, 20q поддерживает разреженную матрицу и инкрементные обновления.
Edit: оказывается, ответ был в сети все это время. Робин Бургенер, изобретатель, подробно описал свой алгоритм в своей подача заявки на патент 2005.