Экспертная система для отгадывания любого персонажа по полученным ответам



В этой работе будет рассматриваться экспертная система. Она должна угадывать любого персонажа по вашим ответам.

Какими свойствами должны обладать экспертная система? Во-первых, система должна обучаться и добавлять в свою базу данных новых персонажей, так как невозможно изначально создать ее своими силами. Во-вторых, система не должна критически относиться ко всем ответам, так как на многие вопросы люди могут отвечать по-разному или же не знать верного ответа. В-третьих, система не должна задавать все вопросы подряд. Вопросов в базе огромное количество. Система должна отбирать нужные вопросы для более быстрого определения загаданного персонажа.

1. Экспертная система

Экспертная система (ЭС) — компьютерная система, способная частично заменить специалиста-эксперта в разрешении проблемной ситуации [1, c. 21]. Важнейшей частью экспертной системы являются базы знаний, как модели поведения экспертов в определённой области знаний с использованием процедур логического вывода и принятий решений, иными словами, базы знаний — совокупность фактов и правил логического вывода в выбранной предметной области деятельности.

ЭС можно разделить на следующее виды, в зависимости от решаемой задачи:

– Интерпретация данных

– Диагностирование

– Мониторирование

– Проектирование

– Прогнозирование

– Сводное планирование

– Оптимизация

– Обучение

– Управление

– Ремонт

– Отладка

2. Алгоритмы поиска

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

Сложность — O(n). [2]

Бинарный поиск — более эффективный, по сравнению с предыдущим способом, метод. Здесь уже подразумевается, что данные отсортированы. На каждом шаге иметься средний элемент, который сравнивается с исходным. Если исходное значение больше, чем средний элемент массива, то будет рассматриваться правая часть, если меньше — левая. Таким образом на каждой итерации размер рассматриваемого массива уменьшается в два раза, что обеспечивает сложность метода — O((n)) [3].

Если количество элементом массива — 512, то в худшем случае с помощью линейного поиска элемент будет найден за 512 шагов, а с помощью бинарного — за 8 шагов. Разница в скорости ощутима. Но минус второго метода в том, что массив данных должен быть отсортирован заранее.

3. Определение персонажа

Для того, чтобы по ответам на вопросы определить конкретного персонажа в данной работе будет применяться модель Байеса.

Одна из основных теорем теории вероятности гласит, что вероятность события можно определить при условии, что другие, связанные с ним события произошли. То есть данная модель объединяет события для точного определения вероятности данного события [4, c. 53].

Пусть для нашей задачи B представляет собой событие: на вопрос Q1 дан ответ A1, Q2 — A2, …, Qn — An.

Тогда P(Ai | B) — вероятность того, что было загадано i.

Так как некоторых персонажей загадывают город чаще, то P(Ai) определяется отношением числа игр, где был загадан i, к общему числу всех игр.

Предположив, что событие (B при условии Ai) — независимое, тогда можно представить вероятность в виде произведения условные вероятностей:

То есть при условии, что на вопрос Qj был дан ответ Aj при условии Ai. Уравнение выше можно представить в виде отношения числа раз, когда на заданный вопрос Oj был дан ответ Aj к числу раз, когда был задан вопрос Oj при условии загнанного объекта i. Для программной реализации важно учесть, что на любой вопрос уже был задан вопрос по одному разу. Такое допущение нужно, чтобы не было нулевого результата.

4. Обучение модели

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

5. Выбор вопросов

Если будет задаваться все вопросы, то на определение одного персонажа потребуется огромное количество времени, поэтому важно уменьшить это количество. То есть важно сначала задавать вопросы, которые могут уменьшить исходные вопросы. Например, определить пол персонажа. В этой части работы будет использовать понятие энтропия [5, c. 13].

где — вероятность i события

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

6. Вывод

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

Литература:

1. Никулин, А. Н. Экспертные системы / А. Н. Никулин — Э41 Ульяновск: УлГТУ, 2015. — 78 с.
2. URL: http://kvodo.ru/lineynyiy-poisk.html (дата обращения: 13.05.2019).
3. URL: https://prog-cpp.ru/search-binary/ (дата обращения: 13.05.2019).
4. Аллен Дауни Байесовские модели. Байесовская статистика на языке Python, 2018–182с.
5. Духин, А. А. Теория информации / А. А. Духин. — М.: Гелиос АРВ, 2007–248 с.