Разработка алгоритма двадцати вопросов

Question

Я заинтересован в написании алгоритма двадцати вопросов , аналогичного тому, который используется akinator и, в меньшей степени, 20q.net . Кажется, что последний фокусируется больше на объектах, явно советуя вам не думать о людях или местах. Можно сказать, что akinator является более общим, позволяя вам думать буквально обо всем, включая абстракции, такие как «мой брат».

Проблема в том, что я не знаю, какой алгоритм используют эти сайты, но из того, что я прочитал, они, похоже, используют вероятностный подход, при котором вопросы получают определенную пригодность на основе того, сколько раз они привели к правильные догадки. Этот ТАК вопрос представляет несколько приемов, но довольно расплывчато, и мне было бы интересно более подробно.

Итак, что может быть точным и эффективным алгоритмом для игры в двадцать вопросов?

Меня интересуют подробности относительно:

1. Какой вопрос задать дальше.
2. Как правильно угадать в конце 20 вопросов.
3. Как вставить новый объект и новый вопрос в базу данных.
4. Как эффективно запрашивать (1, 2) и обновлять (3) базу данных.

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

Answer 1

Ну, через три года я сделал это (хотя я не работал над этим полный рабочий день).Я разместил грубую реализацию на http://twentyquestions.azurewebsites.net/, если кому-то интересно (пожалуйста, пока не учите этому слишком много неправильных вещей!).

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

Мои основные идеи следуют.Если кому-то будет интересно, я тоже поделюсь кодом, просто свяжитесь со мной.В конце концов я планирую сделать его открытым исходным кодом, но как только я сделаю немного больше тестов и доработок.Итак, мои идеи:

• Entities таблица, в которой хранятся воспроизводимые символы и объекты;
• a Questions таблица, в которой хранятся вопросы, которые также отправляются пользователями;
• и EntityQuestions таблица содержит отношения сущность-вопрос.Это содержит количество раз, когда каждый ответ был дан на каждый вопрос по отношению к каждой сущности (ну, те, для которых вопрос был задан в любом случае).Он также имеет поле «Фитнес», используемое для ранжирования вопросов от «более общего» до «более конкретного»; таблица
• a GameEntities используется для ранжирования объектов в соответствии с ответами, приведенными таким образом.далеко для каждой продолжающейся игры.Ответ A на вопрос Q подталкивает все сущности, для которых большинство ответит на вопрос Q, является A;
• Первый задаваемый вопрос выбирается из тех, у кого наибольшая суммасоответствия по таблице EntityQuestions ;
• Каждый следующий вопрос выбирается из вопросов с наивысшей пригодностью, связанной с самыми высокими на данный момент записями в таблице GameEntities.Вопросы, на которые ожидаемый ответ - «Да», предпочтительнее даже до пригодности, потому что у них больше шансов консолидировать текущий объект с самым высоким рейтингом;
• Если система совершенно уверена в ответе еще до того, как все 20 вопросов былиспросил, он начнет задавать вопросы, не связанные с его ответом, чтобы узнать больше об этом объекте.Это сделано в круговой манере из глобального пула вопросов прямо сейчас. Дискуссия: - это круговой штраф или он должен быть полностью случайным?
• Преждевременные ответы также даются при определенных условиях и вероятностях;
• Предположения даются на основерейтинг в GameEntities .Это позволяет системе также учитывать ложь, потому что она никогда не исключает какую-либо возможность, а только уменьшает вероятность того, что она ответит;
• После каждой игры статистика пригодности и ответов обновляется соответственно: значения пригодности для сущностиколичество вопросов-ответов уменьшается, если игра была проиграна, и увеличивается в противном случае.

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

Answer 2

Я пытаюсь написать реализацию на Python с использованием наивной байесовской сети для обучения и минимизации ожидаемой энтропии после того, как на вопрос дан ответ, в качестве критерия для выбора вопроса (с эпсилоновой возможностью выбора случайного вопроса для изученияподробнее об этом вопросе), следуя идеям в http://lists.canonical.org/pipermail/kragen-tol/2010-March/000912.html. Я поместил то, что я получил до сих пор, на github .

1. Желательно выбирать вопросы с низким ожидаемым ожиданием энтропии,(Для того, чтобы собрать что-то быстро, я украл у ε-жадного многорукого бандита, изучая и используя: С вероятностью 1 – ε: задайте вопрос с наименьшим ожидаемым энтропийным ожиданием. С вероятностью ε: Задайте любой случайный вопрос. Однако этот подходкажется, далеко от оптимального.)
2. Поскольку мой подход - байесовская сеть, я получаю вероятности объектов и могу запросить наиболее вероятный объект.
   • Новый объект добавляется в качестве нового столбца в матрицу вероятностей, с низкой априорной вероятностью и ответами на вопросы, которые даны, если даны, или как угаданы байесовской сетью, если не даны.(Я ожидаю, что эта вторая часть будет работать намного лучше, если я добавлю обучение по структуре Байеса вместо простого наивного Байеса.)
   • Аналогичным образом, новый вопрос - это новая строка в матрице.Если это происходит из-за пользовательского ввода, вероятно, известно лишь очень мало вероятностей ответа, остальное нужно угадать.(В общем, если вы можете получить объекты, запрашивая свойства, вы можете получить свойства, спрашивая, есть ли у этих объектов их или нет, и преобразование между ними по существу является теоремой Байеса и в простейшем случае разбивается на транспонирование.качество должно снова улучшиться, когда сеть приобретет соответствующую структуру.)
3. (Это проблема, так как я вычисляю много вероятностей. Моя цель - сделать это с использованием разреженного тензора, ориентированного на базу данныхрасчеты, оптимизированные для работы с взвешенными ориентированными ациклическими графами.)

Answer 3

Это очень интересный вопрос. К сожалению, у меня нет полного ответа, позвольте мне записать идеи, которые я мог бы предложить через 10 минут:

• Если вы можете вдвое сократить количество доступных ответов на каждый вопрос, вы можете различить 2 ^ 20 ~ 1 миллион «объектов». Ваш сет, вероятно, будет больше, поэтому можно предположить, что иногда вам нужно сделать предположение .
• Вы хотите максимизировать утилиту . Некоторые объекты выбираются чаще, чем другие. Если вы хотите делать правильные предположения, вы должны учитывать вес каждого объекта (= вероятность того, что этот объект будет выбран) при создании дерева.
• Если вы немного доверяете своим пользователям, вы можете получать знания, основываясь на их ответах. Это также означает, что вы не можете использовать дерево static , чтобы задавать вопросы, потому что тогда вы получите ответы на те же вопросы ... и вы не узнаете ничего нового, если столкнетесь с тем же объектом.
• Если простой вопрос не может разделить набор на две половины, вы можете объединить их, чтобы получить лучшие результаты: например: «является ли объект зеленым или синим?». "зеленый или имеет круглую форму?"

Answer 4

Было бы интересно посмотреть, насколько хорошо вам подойдет алгоритм на основе дерева решений.Хитрость здесь только в изучении / сортировке дерева.Я хотел бы отметить, что это то, что я помню из класса ИИ и работы студента в рабочей группе ИИ, и его следует брать с полубольцевой крупой (или самородком) соли.

Чтобы ответить на вопросы:

1. Вы просто гуляете по дереву:)
2. Это большой недостаток деревьев решений.У вас была бы только одна догадка, которую можно прикрепить к конечным узлам дерева на глубине 20 (или раньше, если дерево еще разрежено).
3. Есть целые книги, посвященные этой теме.Насколько я помню из класса AI, вы всегда стараетесь минимизировать энтропию, поэтому вы хотите задавать вопросы, которые в идеале делят набор оставшихся объектов на два набора одинакового размера.Боюсь, вам придется искать это в книгах по искусственному интеллекту.
4. Деревья решений очень эффективны на этапе запроса, так как вы буквально ходите по дереву и следуете ветвям «да» или «нет» вкаждый узел.Эффективность обновления зависит от применяемого алгоритма обучения.Возможно, вы сможете сделать это в автономном режиме, как в пакетном обновлении ночью или что-то в этом роде.