Пользователь
0,0
рейтинг
15 февраля 2010 в 22:20

Акинатор и математика

На Хабре уже несколько раз всплывала тема Акинатора, в том числе и с тегом не знаю как оно работает. Я на него наткнулся недавно и, разумеется, был восхищен. Затем, как вероятно и многим другим, мне в голову пришла мысль: «А как же это работает?» Ответа на этот вопрос я нигде не нашел, а потому задался целью написать аналогичную по функциональности программу, разобравшись по ходу дела что к чему.

Функциональные требования


Первым делом стоит разобраться, что в действительности означают слова «аналогичная по функциональности программа». Подумав немного, я выделил следующие требования:
  • Программа должна обучаться. Совершенно очевидно, что нельзя научить программу распознавать несколько сотен тысяч персонажей путем ручного ввода ответов на вопросы для каждого из них. Вернее, теоретически это возможно, но мы будем искать более красивые решения. Очевидная альтернатива этому подходу — учиться на ходу, пользуясь ответами пользователей. Это наша программа должна уметь.
  • Программа должна прощать ошибки. Очевидно, мнение пользователей по поводу ответов на некоторые вопросы может значительно разниться. Простой пример: отчаянный гомофоб и простой человек загадывают Брэда Питта. На вопрос «Ваш персонаж сексуален?» первый, вероятно, ответит отрицательно, в то время как большинство людей — иначе. Однако это небольшое расхождение никак не должно помешать нашей программе выяснить истину.
  • Программа должна с умом выбирать вопросы. Есть много стратегий, определяющих вопросы, которые нужно задавать. Например, можно задать вообще все вопросы (вот только их довольно много). Можно задавать случайные вопросы, но и тогда, скорее всего, к ответу придется идти очень долго. А можно стараться выбирать очередной вопрос так, чтобы узнать при ответе на него как можно больше информации. Именно это мы и будем пытаться делать.

Алгоритмы


Если бы не прощение ошибок, добиться желаемого можно было бы довольно просто. Например, можно было бы хранить дерево ответов на вопросы, в котором внутренние вершины соответствовали бы вопросам, а листы — ответам. Процесс игры тогда выглядел бы как спуск от корня к одному из листов. Тем не менее, с прощением ошибок этот алгоритм справляться не будет. Да и вопросы балансировки дерева возникают.

В каком-то смысле дерево — это очень «механистический», «машинный» способ игры, крайне неустойчивый к малейшим неточностям. Нам же нужно играть так, как стал бы играть рациональный человек. Тем, кто более-менее знаком с теорией вероятности, должно быть известно, что у нее существует так называемая Байесовская интерпретация, а также основанный на ней Байесовский подход. В основе этого подхода лежит описание знаний с помощью распределений случайных величин с последующим преобразованием априорных знаний в апостериорные на основе наблюдений при помощи знаменитой формулы Байеса. Более того, такой подход является единственным обобщением классической алгебры логики на случай неопределенности (об этом можно прочитать, например, тут). Это наводит многих ученых на мысль, что Байесовский подход является эталоном рационального мышления. Что же, нам только этого и нужно. Попробуем применить его к нашей задаче.

Байесовская модель


Итак, вспоминаем формулу Байеса: P(A|B) = P(B|A)P(A)/P(B). А теперь словами. Пусть нам нужно оценить вероятность того, что произошло событие A, при условии, что событие B точно произошло (то есть мы его гарантированно пронаблюдали; именно поэтому B часто называют наблюдением). По формуле Байеса эта вероятность пропорциональна произведению двух других. Первая из них, P(B|A), называется правдоподобием и показывает, с какой вероятностью событие B происходит при условии, что произошло A. Второй множитель, P(A), — это так называемая априорная вероятность события A, то есть вероятность, что оно в принципе произойдет (вне зависимости от B). По сути, эта вероятность отражает информацию, которую мы знали об A до того, как узнали о том, что произошло B. В знаменателе формулы также присутствует величина P(B), которая в данном случае просто играет роль нормировочного коэффициента и может быть проигнорирована.

Использовать эту формулу в контексте игры в вопросы довольно легко. Давайте считать, что Ai — это событие вида «вы загадали объект i», где i может быть как Споком, так и Девой Марией. Поскольку B — это наблюдение относительно Ai, то естественно было бы считать, что B состоит из ответов на вопросы. Единственный вариант, который я тут вижу, — это представить B в виде совместного события «На вопрос Q1 был дан ответ A1, ..., на вопрос Qk был дан ответ Ak». Тогда P(Ai|B) будет для объекта i показывать вероятность того, что был загадан именно он (с учетом того, что пользователь дал ответы на k вопросов). Это именно та величина, которая нас интересует. Выбрав объект с максимальным значением P(Ai|B), можно, если значение P(Ai|B) достаточно велико, попробовать использовать его в качестве догадки.

Априорную вероятность P(Ai) можно рассматривать как частный случай P(Ai|B) при k=0. Иначе говоря, это вероятность, что игрок загадал объект i при условии, что вопросов задано не было, и мы вообще ничего не знаем. С одной стороны, можно было бы дать всем объектам равные P(Ai), т.к. это честно. С другой стороны, Барака Обаму наверняка будут загадывать намного чаще, чем Холдена Колфилда. Поэтому при прочих равных (то есть когда мы не можем различить объекты), следует выбирать именно Обаму. Следовательно, естественной оценкой P(Ai) будет отношение числа игр, когда был загадан X, к общему их числу.

Правдоподобие P(B|Ai) тоже получает удобную интерпретацию. Только прежде нужно воспользоваться одним небольшим трюком — предположить условную независимость ответов на вопросы при условии Ai (несколько грубое, но очень удобное для нас упрощение). В переводе на русский это значит, что по предположению вероятность P(B|Ai) может быть записана в виде произведения (по j) вероятностей P(Bj|Ai), где Bj — событие вида «На вопрос Qj был дан ответ Aj». P(Bj|Ai) в этом случае будет отношением числа раз, когда при загаданном объекте i на вопрос Qj был дан ответ Aj к числу раз, когда при загаданном объекте i в принципе был задан вопрос Qj. В целях избежания нулевых и неопределенных вероятностей предлагаю дополнительно считать, что изначально на каждый из вопросов каждый из вариантов ответов был дан по разу. То есть в случае, если вопрос Qj еще ни разу не задавался об объекте i, P(Bj|Ai) будет равно 1/Nj, где Nj — число вариантов ответа на вопрос Qj (я, к слову, использовал для всех вопросов одни и те же 4 варианта ответа: «да», «нет», «не знаю» и «вопрос не имеет смысла»).

Подведем промежуточный итог. Мы нашли простую формулу, которая отображает набор пар вопрос/ответ и некоторую сущность в вероятность, что при данных ответах на вопросы была загадана именно эта сущность. Пересчитав эту вероятность для всех объектов в нашей базе данных после ответа на новый вопрос можно видеть, какие из них больше похожи на загаданный объект на настоящий момент. Более того, обучение нашей модели реализуется довольно просто: нужно просто для каждой сущности в базе хранить информацию о том, какие вопросы про нее задавались и сколько ответов каждого из типов дали пользователи. После каждой игры эту информацию можно обновлять, основываясь на ответах пользователя. Также, для учета «популярности» персоны в базе нужно хранить число раз, которое персона была загадана.

Выбор вопросов, информация и энтропия


Ну что же, осталось только понять, какие вопросы лучше задавать. Естественно, задавать нужно те вопросы, которые дают больше информации. Но разве мы можем как-то эту информацию измерить? Оказывается, что да. Для этого можно воспользоваться понятием информационной энтропии. Если говорить грубо, но понятно, то информационная энтропия — это такая характеристика распределения случайной величины (измеряемая, как и информация, в битах), которая показывает, насколько мы не уверены в том, какое значение эта случайная величина примет. Например, если случайная величина принимает значение 1 с вероятностью 0.99, и значение 0 — с вероятностью 0.01, то энтропия такого распределения будет очень близка к нулю. Если же случайная величина принимает, к примеру, значения 0 и 1 с равными вероятностями 0.5 (орел или решка), то энтропия такой случайной величины будет равна 1 биту (это как раз то количество информации, которое мы должны получить, чтобы устранить неопределенность).

Ладно, давайте выбирать каждый раз тот вопрос, ответ на который сильнее всего уменьшит энтропию распределения P(Ai|B), которое как раз и отвечает за наши знания о том, кого загадал игрок. Тут сразу возникает еще одна проблема: вообще говоря, разные ответы на один и тот же вопрос могут уменьшать энтропию по разному. Что же делать? Предлагается находить тот вопрос, для которого ожидаемое уменьшение энтропии будет максимальным. Ожидаемое уменьшение энтропии показывает, насколько «в среднем» уменьшится энтропия, если мы зададим некоторый вопрос. Чтобы не писать здесь еще несколько абзацев текста, приведу формулу, по которой эту величину можно посчитать. Желающие без труда поймут, почему она имеет такой вид. Итак, нужно каждый раз задавать такой вопрос j, для которого величина H[P(Ai|B, <Qj,Yes>)]P(<Qj,Yes>) +… + H[P(Ai|B, <Qj,No>)]P(<Qj,No>) минимальна. Через H[P] тут обозначена энтропия распределения вероятности P, а через "<Qj,Ans>" — событие «на вопрос Qj дан ответ Ans». Величину P(<Qj,Ans>) можно легко найти по формуле полной вероятности, просуммировав ее, обусловленную по всем известным объектам. То есть P(<Qj,Ans>) = sum(i) P(<Qj,Ans>|Ai) P(Ai|B).

Оказывается, что такой подход позволяет очень быстро отбрасывать нерелевантные вопросы, сосредотачиваясь на самом главном. В каком-то смысле этот метод является обобщением метода «деления пополам» в вероятностной постановке. Посмотреть, как все это работает вместе, можно на видео ниже.



Итог


Надеюсь, информация из этой небольшой статьи показалась кому-нибудь из вас интересной. На самом деле, прежде всего эта статья должна обратить ваше внимание на мощь (пусть и простейшей) математики в решении плохо формализуемых задач. Использование Байесовского подхода к теории вероятности и теории информации в ваших программах может сделать их более рациональными, но в то же время и более человечными :)
Борис Янгель @hr0nix
карма
41,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (76)

  • +2
    • –5
      и чего?
    • +5
      Да, это определенно экспертная система, если вы об этом. Существует много способов построения экспертных систем, и это — один из них.
  • –19
    Блин, ребят, вам еще не надоело? Какой Байес? Это веб интерпретация игры «угадай животное». Алгоритм встречался практически в каждом старом учебнике по программированию. Вот здесь есть реализация на VBA для Excel: www.pcmag.ru/library/detail.php?ID=11018
    • +19
      Случай о котором вы говорите автор тоже описал в самом начале. Игра «угадай животное» построена на простом бинарном дереве. И этот механизм ничего не сможет угадать если пользователь даст хотя бы один неправильный ответ.

      Автору большое спасибо. Статья интересная. Вроде все простые вещи, а получается маленькое волшебство :) Такими примерами хорошо школьников заинтересовывать математикой…
      • +6
        Упс… точно, впредь наука — сначала прочитай потом коммент пиши. Только вот не всегда получается, исправляюсь — прочитал, таки автор прав — плюсанул…
  • 0
    Написание подобного рода программ на Prolog входит у нас в курс Искусственного Интеллекта.
    • +5
      Вы допускаете ту же ошибку, что и комментатор выше. Пролог — это язык логического программирования. На нем очень легко сделать экспертную систему поверх базы знаний, где характеристики объектов задаются областями истинности предикатов. Но Пролог никак (насколько мне известно) не помогает при реализации вероятностной интерпретации этой задачи (которая, в свою очередь, куда как более устойчива к неточностям).
      • –2
        Как я далек от всего этого… )
    • 0
      5 курс специальности 230105?
    • 0
      Программы (подобного рода), которые входили у вас в курс СИИ, входили туда последний год. Со след. года введем что-нибудь посерьёзнее :) Вероятностной интерпретации, естественно, там не было.
      А представленная выше байесовская модель входила у вас в курс Распознавания образов :)
  • +2
    Я удивлен. Акинатор угадал Ноама Хомского.
    Может им можно Хауса заменить?
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Я так понимаю, про это вот тут можно почитать, если на Springer есть доступ.
        • 0
          Это не статья, это список публикаций по теме. И тысячи их.
          • 0
            Ну я и имел в виду, что по ссылке нечто, что содержит в себе информацию о том, что можно почитать по теме. Забыл упомянуть про один уровень косвенности.
      • +7
        Медицина — это едва ли не первое (исторически) применение экспертным системам, семидесятые годы.
        Я не помню, как там конкретно происходила история, но «золотой век» экспертных систем считается уже прошедшим. То есть создали какие-то программы, они до сих пор работают. Но дальше какой-то теоретический потолок.
        • 0
          Потолок такой, что их алгоритмы создаются не командой, а отдельными особо одаренными личностями. ЭС MYCIN писалась на lisp'е кандидатом наук в течение шести лет. В иных случаях доходило и до десятилетия.
      • +5
        Почему нельзя опираться? Я думаю что с такой же процентной долей вероятности как и на первом приеме у доктора.
        Знаете как врачи у нас в больницах диагнозы ставят?
        — Болит живот?
        — Да
        — Воду из под крана пил?
        — Да
        Волчанка Гастрит

        зы
        Идея для стартапа, кстати, неплохая.
        • +5
          Так вроде есть таких сервисов куча. Вот например.
          • 0
            эта штука за 5 минут отгадала то что мне врач говорил (3 дня обследований) +1
            • 0
              Полагаю, что врач во время вашего отсутствия шарился по интернету :) Или просил сына это сделать :)
              • 0
                Это вряд ли. Врачи как огня боятся, что компьютер может быть умнее их, они ни за что не воспользуются такой подсказкой.
          • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Я подозреваю что это было реализовано еще в 80-х :)
        • +1
          В начале 70-х. Классика MYCIN
      • 0
        Я думаю любая область поиска на основании дерева вопросов может быть реализована подобным образом. Взять тот же самый виндовый траблшутер. Идея вроде неплохая и чайникам может быть помогла бы. Но существующая реализация (точнее та, которую я видел лет 8 назад :) это просто ппц.

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

        Вообще, подобный механизм очень хорошо подходит для задач «ищу то, сам не знаю чего»
    • 0
      Буратино угадал только с третьей попытки, сперва предложив Ивана-дурака и Щелкунчика.
      • 0
        У меня с первого раза. Может, Вы его слишком давно смотрели?
  • 0
    Скорее всего основа там Ensemble, так как проще заточить какой-нибудь лёгкий Байес на конкретный тип/случай, чем пытаться простым алгоритмом охватить все варианты.
  • 0
    Удивительно, как быстро все забыли про 20q.net.
  • 0
    Когда натыкаюсь на Акинатор мечтаю о том, что бы кто нибудь сделал такой же или подобный инструмент в современных ОС. Чтобы путем ответа на вопросы он подсказывал как настроить ту или иную программу или железку или как избавиться от определенной ошибки.
    • 0
      Проблема пользователей как раз в том, что они не знают, что им надо в большинстве случаев. Поэтому ответы на вопросы, по меньшей мере, будут не точны. А для админов — нас тогда не надо будет в природе
      • +1
        Так система и ориентирована на нечеткие вопросы. Более того, апроксимируя вопросы по «среднестатистическому чайнику», можно в итоге получить более эффективную систему.

        Ну например, известная шутка про то, что для пользователя монитор — это и есть компьютер. Соответственно, экспертная система может заранее быть готова к вопросам «у меня компьютер сломался» или «процессор пищит», подразумевая что проблема вовсе не там, где думает пользователь.
    • 0
      Ну так а troubleshooting wizard в винде — это не оно?

      Не помню, чтобы он мне хоть раз помог толком, но старался :)
      • 0
        Почитайте мои посты выше. Проблема в том, что его составляли люди. Просто эмпирически. И вопросов там от силы сотня. А если бы система была составлена большой толпой и оформлена в виде веб сервиса, то тогда вообще была бы очень ценным инструментом.
        • 0
          Дело в том, что в Акинаторе ты изначально знаешь ответ на свой вопрос. И если Акинатор не угадает — ты его обучишь. И за счет миллионов таких вот пользователей он и учится, и показывает такие выдающиеся результаты.

          А если миллион пользователей напишет «у меня пищит процессор» — то ничем это, увы, не закончится. Так же как и в медицине. А если держать админов/докторов, которые после списка вопросов будут реально обследовать пациента и вводить в базу правильный ответ на каждый конкретный user case — и поток информации для обучения сократится в сотни раз.
  • +2
    За Холдена стало обидно :(
    • +1
      Такова жизнь =(
  • 0
    Формула Байеса — это да! Недавно был на одной конференции, там был больше всего был впечатлен докладом о разработке системы подбора отелей. Разработчики использовали Байесовы нейронные сети для того, чтобы попытаться угадать, что же на самом деле хотел пользователь (а не что он ввел в качесте параметров поиска). И в итоге пользователь мог пометить, что хочет жить на берегу моря, а получить предложение об отеле чуть ли не в горах, — и с радостью забронировать номер!
    • +5
      Что за Байесовские нейронные сети? Я знаю Байесовские сети и нейронные сети, но не вместе.
  • +2
    Огромное спасибо за статью!
  • +1
    Я фигею! Загадал Ельцына и после вопросов о русской национальности и принадлежности к политике, спросил много ли пьют мой персонаж… Вот так вот разработчики думают о русских политиках.
    • 0
      Вот и отличный пример почему обычное дерево тут не применимо.
    • +2
      Скорее пользователи, а не разработчики.
    • +4
      Нет, вопросы подбираются в зависимости от имеющейся информации. Ну или как написано в топике, вопрос выбирается из условия минимизации ожидания энтропии.
      Таким образом, у него бывают вопросы, содержащие половину ответа.
  • +1
    Спасибо за статью, очень интересно! Побольше бы таких на хабре.
    • +1
      Не за что. Буду стараться =)
  • 0
    я так понимаю программу Вы написали?
    И просить исходники просто глупо, да?
    • 0
      Нет, совсем не глупо =) Просто она пока далека от идеала, и я ее выкладывать не стал. Но исходники и прилагающуюся к ним базу знаний могу выслать всем желающим, отписывайтесь тут.

      Точнее будет сказать, что от идеала далека база знаний, потому что почти всю ее составлял один человек (которому за это была обещана и впоследствии куплена бас-гитара) =) В любом случае, решающий движок реализован и работает по формулам, описанным в статье.
      • +1
        А не хотите запустить аналогичный Акинатору сервис?
        • +2
          Ну, прям аналогичный Акинатору наверное не стоит. Все-таки есть уже сам Акинатор =) А вот почитав комментарии выше, я подумал, что идея онлайн-траблшутера, который будет не только подсказывать решения проблем, но и самостоятельно обучаться, не так уж плоха. Надо об этом интенсивней поразмыслить на досуге.
          • 0
            Хм, даже еще лучше. Желаю успехов!
            P.S. Ну и добавлю спасибо за статью, не знал, что формула Байеса применяется где-то кроме задачек по терверу. :)
            • 0
              Про формулу Байеса — это вы зря :) Она, например, лежит в основе подавляющего большинства методов, используемых в современном компьютерном зрении. Ну и еще в миллионе других областей используется.
      • 0
        А можно мне исходники? ^_^
        Я димплом пишу по матметодам. Мне эти вещи будут ооочень полезны.
        За статью спасибо. Весьма интересно.
        • 0
          Скажите мне свой адрес, и я отправлю.

          А диплом по матметодам — это как? По всем матметодам? :)
          • 0
            Ответил в личку
  • +1
    Очень круто! Поздравляю с успешной реализацией :)
  • 0
    А откуда брали списки персонажей и списки вопросов?
    Неужели вбивали руками с нуля?
    • 0
      Я пообещал купить другу бас-гитару, если он добавит в базу знаний 500 персонажей вместе с вопросами. Ну и сам еще постарался немного =)
      • 0
        Гитару-то купили? :))
        • 0
          Купили =)
  • 0
    Говорите: «Байесовская модель», «Выбор вопросов, информация и энтропия»?

    Но меня впечатлило это: habrahabr.ru/blogs/crazydev/72832/

    «Акинатор» на батнике :D
  • 0
    Я писал не так давно систему очень подобную этой, более похожую на Яндекс-гуру. В принципе смысл тот же, только система работает не за счет существующей базы, а база наполняется за счет ответов пользователей. На самом деле всё просто, если кого заинтересует могу поделиться идеей.
  • 0
    Великолепная статья, я восхищен красотой математического решения.

    А есть ли тут кто-нибудь умный, кто подсказал бы, как программе вычислить P(<Qj,Ans>|Ai)?
    • 0
      Не знаю, насколько я умный, но подсказать могу.

      P(<Qj,Ans>|Ai) дословно читается как «вероятность того, что на вопрос Qj был дан ответ Ans при условии, что загадан был Ai. Эту вероятность мы оцениваем на основе предыдущих ответов пользователей как долю ответов Ans на вопрос Qj про Ai среди всех возможных ответов на этот вопрос для Ai.
      • 0
        Вы умный. Спасибо.
      • 0
        А не подскажете ли еще насчет вот какого момента. В статье говорится, что для того, чтобы выбрать вопрос, который выгоднее всего задать, следует, перебирая j, вычислить суммы H[P(Ai|B, <Qj,Yes>)]P(<Qj,Yes>) + … + H[P(Ai|B, <Qj,No>)]P(<Qj,No>) и потом найти минимальную из них. А какое значение i тут следует подставлять? «Sum(i)» в формуле нет, а подставлять какое-то одно конкретное значение i вроде бы нелогично, потому что в момент выбора вопроса еще неизвестно с достаточной вероятностью, какой персонаж загадан. Как же быть?
        • 0
          Я вас отправлю вот сюда =)
          • 0
            Спасибо! С помощью этого документа смог полностью разобраться.
  • 0
    Я надеюсь, автор статьи еще читает комментарии.
    Спасибо за интересный материал!

    Хотел бы тоже попросить у вас исходники и базу знаний, если можно.
    Адрес почты, куда высылать, отправил вам в сообщения с пометкой «Код «Акинатор и математика»».
    Извиняюсь за беспокойство!

  • 0
    Господа, я попал в дурацкую ситуацию: в процессе переезда между компами я потерял исходники и базу знаний от этого проекта. Не мог бы кто-нибудь из тех, кому я отправлял исходники и базу, переслать мне их обратно? =)
    • 0
      Нашлось.
  • 0
    Скиньте, пожалуйста, если можете, исходники и базу знаний на loguntsov@gmail.com. Заранее спасибо.
  • 0
    А у кого есть идеи насчет того как Акинатор сохраняет промежуточный результат при «общении» с конкретным пользователем? То есть, допустим, я ответил на 1-й вопрос. Алгоритм просчитал вероятности для персонажей из своей базы, исходя из этого просчитал, какой вопрос задать следующим, ну и задал его :)

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

    Так вот где он эти вероятности хранит?
    • 0
      Скорее всего у себя в памяти хранит сессию по вашей партии.
      Так же допустим вариант, что набор ответов хранится у вас и каждый раз передается ему, где он накатывает ответы на всю базу персонажей.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.