На Хабре уже несколько раз всплывала тема Акинатора, в том числе и с тегом не знаю как оно работает. Я на него наткнулся недавно и, разумеется, был восхищен. Затем, как вероятно и многим другим, мне в голову пришла мысль: «А как же это работает?» Ответа на этот вопрос я нигде не нашел, а потому задался целью написать аналогичную по функциональности программу, разобравшись по ходу дела что к чему.
Первым делом стоит разобраться, что в действительности означают слова «аналогичная по функциональности программа». Подумав немного, я выделил следующие требования:
Если бы не прощение ошибок, добиться желаемого можно было бы довольно просто. Например, можно было бы хранить дерево ответов на вопросы, в котором внутренние вершины соответствовали бы вопросам, а листы — ответам. Процесс игры тогда выглядел бы как спуск от корня к одному из листов. Тем не менее, с прощением ошибок этот алгоритм справляться не будет. Да и вопросы балансировки дерева возникают.
В каком-то смысле дерево — это очень «механистический», «машинный» способ игры, крайне неустойчивый к малейшим неточностям. Нам же нужно играть так, как стал бы играть рациональный человек. Тем, кто более-менее знаком с теорией вероятности, должно быть известно, что у нее существует так называемая Байесовская интерпретация, а также основанный на ней Байесовский подход. В основе этого подхода лежит описание знаний с помощью распределений случайных величин с последующим преобразованием априорных знаний в апостериорные на основе наблюдений при помощи знаменитой формулы Байеса. Более того, такой подход является единственным обобщением классической алгебры логики на случай неопределенности (об этом можно прочитать, например, тут). Это наводит многих ученых на мысль, что Байесовский подход является эталоном рационального мышления. Что же, нам только этого и нужно. Попробуем применить его к нашей задаче.
Итак, вспоминаем формулу Байеса: 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).
Оказывается, что такой подход позволяет очень быстро отбрасывать нерелевантные вопросы, сосредотачиваясь на самом главном. В каком-то смысле этот метод является обобщением метода «деления пополам» в вероятностной постановке. Посмотреть, как все это работает вместе, можно на видео ниже.
Надеюсь, информация из этой небольшой статьи показалась кому-нибудь из вас интересной. На самом деле, прежде всего эта статья должна обратить ваше внимание на мощь (пусть и простейшей) математики в решении плохо формализуемых задач. Использование Байесовского подхода к теории вероятности и теории информации в ваших программах может сделать их более рациональными, но в то же время и более человечными :)
Функциональные требования
Первым делом стоит разобраться, что в действительности означают слова «аналогичная по функциональности программа». Подумав немного, я выделил следующие требования:
- Программа должна обучаться. Совершенно очевидно, что нельзя научить программу распознавать несколько сотен тысяч персонажей путем ручного ввода ответов на вопросы для каждого из них. Вернее, теоретически это возможно, но мы будем искать более красивые решения. Очевидная альтернатива этому подходу — учиться на ходу, пользуясь ответами пользователей. Это наша программа должна уметь.
- Программа должна прощать ошибки. Очевидно, мнение пользователей по поводу ответов на некоторые вопросы может значительно разниться. Простой пример: отчаянный гомофоб и простой человек загадывают Брэда Питта. На вопрос «Ваш персонаж сексуален?» первый, вероятно, ответит отрицательно, в то время как большинство людей — иначе. Однако это небольшое расхождение никак не должно помешать нашей программе выяснить истину.
- Программа должна с умом выбирать вопросы. Есть много стратегий, определяющих вопросы, которые нужно задавать. Например, можно задать вообще все вопросы (вот только их довольно много). Можно задавать случайные вопросы, но и тогда, скорее всего, к ответу придется идти очень долго. А можно стараться выбирать очередной вопрос так, чтобы узнать при ответе на него как можно больше информации. Именно это мы и будем пытаться делать.
Алгоритмы
Если бы не прощение ошибок, добиться желаемого можно было бы довольно просто. Например, можно было бы хранить дерево ответов на вопросы, в котором внутренние вершины соответствовали бы вопросам, а листы — ответам. Процесс игры тогда выглядел бы как спуск от корня к одному из листов. Тем не менее, с прощением ошибок этот алгоритм справляться не будет. Да и вопросы балансировки дерева возникают.
В каком-то смысле дерево — это очень «механистический», «машинный» способ игры, крайне неустойчивый к малейшим неточностям. Нам же нужно играть так, как стал бы играть рациональный человек. Тем, кто более-менее знаком с теорией вероятности, должно быть известно, что у нее существует так называемая Байесовская интерпретация, а также основанный на ней Байесовский подход. В основе этого подхода лежит описание знаний с помощью распределений случайных величин с последующим преобразованием априорных знаний в апостериорные на основе наблюдений при помощи знаменитой формулы Байеса. Более того, такой подход является единственным обобщением классической алгебры логики на случай неопределенности (об этом можно прочитать, например, тут). Это наводит многих ученых на мысль, что Байесовский подход является эталоном рационального мышления. Что же, нам только этого и нужно. Попробуем применить его к нашей задаче.
Байесовская модель
Итак, вспоминаем формулу Байеса: 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).
Оказывается, что такой подход позволяет очень быстро отбрасывать нерелевантные вопросы, сосредотачиваясь на самом главном. В каком-то смысле этот метод является обобщением метода «деления пополам» в вероятностной постановке. Посмотреть, как все это работает вместе, можно на видео ниже.
Итог
Надеюсь, информация из этой небольшой статьи показалась кому-нибудь из вас интересной. На самом деле, прежде всего эта статья должна обратить ваше внимание на мощь (пусть и простейшей) математики в решении плохо формализуемых задач. Использование Байесовского подхода к теории вероятности и теории информации в ваших программах может сделать их более рациональными, но в то же время и более человечными :)
