Akinator.com и Наивный байесовский классификатор

12

Контекст: я программист с некоторым (наполовину забытым) опытом в области статистики из университетских курсов. Недавно я наткнулся на http://akinator.com и провел некоторое время, пытаясь заставить его потерпеть неудачу. А кто не был? :)

Я решил выяснить, как это может работать. После поиска в Google и прочтения соответствующих сообщений в блоге и добавления некоторых моих (ограниченных) знаний в результирующий микс, я придумаю следующую модель (я уверен, что я буду использовать неправильную запись, пожалуйста, не убивайте меня за это):

Есть Предметы (S) и Вопросы (Q). Цель предсказателя состоит в том, чтобы выбрать субъект S, который имеет наибольшую апостериорную вероятность быть тем субъектом, о котором думает пользователь, с учетом вопросов и ответов, собранных до сих пор.

Пусть игра G будет набором вопросов и ответов: .{Q1,a1},{Q2,a2},,,{QN,aN}

Тогда предиктор ищет .п(S|грамм)знак равноп(грамм|S)*п(S)п(грамм)

Приоритет для предметов ( ) может быть просто числом угаданных предметов, деленным на общее количество игр.п(S)

Предполагая, что все ответы независимы, мы могли бы вычислить вероятность субъекта S для игры G следующим образом:

п(грамм|S)знак равноΠязнак равно1 ..Nп({Qя,aя}|S)

Мы могли бы вычислить если бы мы отслеживали, какие вопросы и ответы были даны, когда использовались, хотя и по данной теме:п({Qя,aя}|S)

п(Q,a|S)знак равноaNsвесер a весas граммяvеN Tо QUеsTяоN Q яN Tчасе граммaме весчасеN S весas Tчасе sUбJесTNUмбер ое Tямеs Q весas asКеd яN Tчасе граммaмеs яNvоLvяNграмм S

Теперь определяет распределение вероятностей по субъектам, и когда нам нужно выбрать следующий вопрос, мы должны выбрать тот, для которого ожидаемое изменение энтропии этого распределения является максимальным:п(S|грамм)

aрграмммaИксJ(ЧАС[п(S|грамм)]-Σaзнак равноYеs,Nо,мaYбе,,,ЧАС[п(S|грамм{QJ,a})]

Я пытался реализовать это, и это работает. Но, очевидно, что по мере увеличения числа субъектов производительность снижается из-за необходимости пересчитывать после каждого хода и вычислять обновленное распределение для выбор вопроса.P ( S | G { q j , a } )п(S|грамм)п(S|грамм{QJ,a})

Я подозреваю, что я просто выбрал неправильную модель, будучи ограниченным пределами моих знаний. Или, может быть, есть ошибка в математике. Пожалуйста, просветите меня: с чем я должен ознакомиться, или как изменить предиктор, чтобы он мог справиться с миллионами субъектов и тысячами вопросов?

искусный
источник
4
Я сомневаюсь, что это Наивный Байес, скорее, какое-то дерево решений расширяется каждый раз, когда не удается распознать кого-то.
1
Разве такое дерево решений не будет слишком громоздким для обновления? Кроме того, я не вижу простого способа учесть случайно-неправильные / честно-ошибочные ответы и все же правильно получить их в итоге с помощью дерева решений
ADEpt
5
Похоже на реинкарнацию двадцатилетнего гадателя с 20 вопросами, теперь на 20q.net . Вот популярное объяснение того, как это работает mentalfloss.com/blogs/archives/13725
Ярослав Булатов
5
Извините, но я думаю, что использование «искусственного интеллекта» и «нейронных сетей» без какого-либо контекста Харди считается объяснением. И я не понимаю, как можно использовать нейронную сеть для такого рода вещей - например, какой будет функция вывода?
ADEpt
Привет @ADEpt, Прошло много времени с тех пор, как вопрос был задан, но можете ли вы поделиться исходным кодом для реализации у вас там назад?
Приха

Ответы:

10

Эта игра похожа на 20 вопросов на http://20q.net , которые, как сообщает создатель, основаны на нейронной сети. Вот один из способов структурирования такой сети, подобный нейронной сети, описанной в векторах описания концепции и игре из 20 вопросов .

Вы бы

  1. Фиксированное количество вопросов, причем некоторые вопросы помечены как «окончательные» вопросы.
  2. Одна единица ввода на вопрос, где 0/1представляет no/yesответ. Первоначально установлено значение0.5
  3. Одна выходная единица на вопрос, сигмовидная клетка сжимается в диапазон 0..1
  4. Скрытый слой, соединяющий все входные единицы со всеми выходными единицами.

Единицы ввода для вопросов, на которые даны ответы, устанавливаются в 0 или 1, и предполагается, что нейронная сеть была обучена, чтобы выходные единицы измерения выходили в значения, близкие к 1, для вопросов, которые дали ответ «Да» с учетом набора существующих ответов.

На каждом этапе вы выбираете вопрос, в котором NNнаименее уверены, т. Е. Соответствующая единица вывода близка 0.5, задаете вопрос и устанавливаете соответствующий блок ввода в ответ. На последнем этапе вы выбираете единицу вывода из списка «последний вопрос» со значением, наиболее близким к 1.

Каждая игра из 20 вопросов дает 20 точек данных, которые можно использовать для обновления NNвесов с помощью обратного распространения, т. Е. Вы обновляете весы, чтобы выходные данные текущей нейронной сети соответствовали истинному ответу, учитывая все предыдущие заданные вопросы.

Ярослав Булатов
источник
7

Я не думаю, что это действительно проблема классификации. 20 вопросов часто называют проблемой сжатия . Это на самом деле лучше соответствует последней части вашего вопроса, где вы говорите об энтропии.

См. Главу 5.7 ( книги Google )

Cover, TM and Joy, AT (2006) Элементы теории информации

а также кодирование Хаффмана . Эта статья, которую я нашел на arXiv, также может быть интересна.

Гилл, Дж. Т. и Ву, В. (2010) «Двадцать вопросов, на которые игра всегда заканчивается, да» http://arxiv.org/abs/1002.4907

Для простоты предположим, что да / нет вопросов (тогда как akinator.com позволяет, может быть, не знаю). Предположим, что каждый возможный субъект (который знает akinator.com) может быть уникально идентифицирован последовательностью вопросов и ответов «да / нет» - по сути, двоичным вектором.

Заданные вопросы (и их ответы) определяют рекурсивное разбиение пространства предметов. Это разбиение также соответствует древовидной структуре. Внутренние вершины дерева соответствуют вопросам, а листья соответствуют предметам. Глубина листьев - это количество вопросов, необходимых для однозначной идентификации предмета. Вы можете (тривиально) идентифицировать каждый известный предмет, задавая все возможные вопросы. Это не интересно, потому что есть потенциально сотни вопросов.

Связь с кодированием Хаффмана заключается в том, что он дает оптимальный (при определенной вероятностной модели) способ построения дерева таким образом, чтобы средняя глубина была (почти) минимальной. Другими словами, он говорит вам, как организовать последовательность вопросов (построить дерево) так, чтобы количество вопросов, которые вам нужно было задать, в среднем было небольшим. Он использует жадный подход.

Конечно, для akinator.com есть нечто большее, чем эта, но основная идея состоит в том, что вы можете рассматривать проблему с точки зрения дерева и пытаться минимизировать среднюю глубину его листьев.

vqv
источник
Это хорошее начало, но я думаю, что есть еще проблема. Например: как они получают ответы на вопросы? Предположительно они используют ответы, данные предыдущими игроками (проблема обучения с подкреплением), и в этом случае мы сталкиваемся с компромиссом при выборе вопроса, который (а) решает проблему для текущего игрока, и (б) предоставляет информацию для будущих игроков.
Саймон Бирн
На первый взгляд, умение проводить аналогию между 20 вопросами и кодированием Хаффмана зависит от умения задавать «круговые вопросы». То есть вместо "Ты когда-нибудь был героем в космосе?" мы задаем «общие» вопросы, такие как «Был ли он когда-либо в космосе, или он мужчина, или лысый, или был в кино, или ... (100500 других вариантов)?» Я прав? Если это так, то я, вероятно, должен отредактировать свой вопрос, чтобы было ясно, что я заинтересован в разновидности «спрашивай один за другим»
ADEpt
я0
@vqv: Re: «Я не думаю, что это действительно проблема классификации. 20 вопросов часто называют проблемой сжатия». Разве статистический вывод и сжатие информации не связаны напрямую?
Ян
@Yang Ты имеешь в виду аргумент Йормы Риссаннен? Статистический вывод и сжатие информации используют вероятностные модели для описания неопределенности, однако их перспективы и перспективы исследователей в этих областях, как правило, очень разные. Что я хочу сказать выше, так это то, что 20 вопросов можно более естественно сформулировать как проблему сжатия (в частности, кодирование источника), а не проблему классификации. … Продолжение ниже
vqv