Если чесно, то ничего он не сканирует. И это чистой воды
математика: а точнее ее раздел
комбинаторика. Принцип работы сего всезнайки основан на
Баесовской модели, в основе которой лежит описание знаний с помощью распределений случайных величин с последующим преобразованием априорных знаний в апостериорные на основе наблюдений при помощи знаменитой формулы Байеса. Более того, такой подход является единственным обобщением классической алгебры логики на случай неопределенности. Это наводит многих ученых на мысль, что
Байесовский подход является эталоном рационального мышления.
Итак, формула Байеса:
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 варианта ответа: «да», «нет», «не знаю» и «возможно частично»).
Результатом есть простая формулу, которая отображает набор пар вопрос/ответ и некоторую сущность в вероятность, что при данных ответах на вопросы была загадана именно эта сущность. Пересчитав эту вероятность для всех объектов в нашей базе данных после ответа на новый вопрос можно видеть, какие из них больше похожи на загаданный объект на настоящий момент. Более того, обучение нашей модели реализуется довольно просто: нужно просто для каждой сущности в базе хранить информацию о том, какие вопросы про нее задавались и сколько ответов каждого из типов дали пользователи. После каждой игры эту информацию можно обновлять, основываясь на ответах пользователя. Также, для учета «популярности» персоны в базе нужно хранить число раз, которое персона была загадана.
Re: Он знает все :)
