Какой алгоритм стоит за игрой Akinator?
10 Desmond Hume [2012-11-30 19:59:00]
Меня всегда удивляло, как приложение Akinator могло угадать персонажа, задав сразу несколько вопросов. Поэтому я задаюсь вопросом, какой алгоритм или метод позволяют это сделать? Есть ли имя для этого класса алгоритмов и где я могу узнать больше о них?
algorithm statistics artificial-intelligence machine-learning
5 ответов
17 amit [2012-11-30 20:05:00]
Да, есть имя для этого класса алгоритмов - он называется алгоритмы классификации в поле машинное обучение. Деревья принятия решений являются одним из примеров алгоритма классификации.
В этой проблеме классификации функции алгоритма являются ответами на вопрос.
Решение вопроса о том, какой вопрос следует задать, может быть выполнено различными способами - например, путем максимизации прогнозируемого (или среднего) entropy из следующего вопроса.
4 ziggystar [2012-12-11 00:46:00]
Эта игра иногда известна как 20 вопросов. На SO есть некоторые вопросы о SO, например:
3 Andrew [2017-04-05 03:18:00]
Основные характеристики алгоритма:
- Self-просвещение
- Ошибки-снисходительность
- Интеллектуальная система следующего вопроса выбирает
Модель игрового алгоритма Akinator называется "Экспертная система, основанная на нечеткой логике".
И это НЕ деревья принятия решений, потому что у него нет ошибок - снисходительность.
Я писал один раз на С#, вы можете найти его по ссылке: https://github.com/ukushu/AkinatorEngine
1 Serge Rogatch [2018-12-24 21:49:00]
Я не знаю, какой именно алгоритм использует Akinator, но здесь я поместил в open-source алгоритм, который обеспечивает тот же эффект: https://github.com/srogatch/ProbQA.
Обычно мы используем куб из N(Questions) умноженные на N(Answer Options) умноженные на N(Targets), см. Https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CpuEngine.decl.h.
Мы обучаем куб, применяя байесовскую формулу с предположением независимости, см. Https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CEEvalQsSubtaskConsider.cpp
Поскольку код сильно оптимизирован для AVX2 и многопоточности, его может быть сложно прочитать. Может быть проще прочитать код CUDA для того же: https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CudaEngineGpu.cu
Применение этого алгоритма также доступно в качестве веб-сайта, чтобы рекомендовать игру.
1 Zaher Joukhadar [2012-12-10 12:53:00]
Я думаю, что это похоже на экспертную систему с структурой B-Tree.