ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 6, с. 38-43
СИСТЕМНЫЙ АНАЛИЗ ^^^^^^^^ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 004.89
ОПТИМАЛЬНОЕ ОТГАДЫВАНИЕ ОБЪЕКТА ЭКСПЕРТНОЙ СИСТЕМОЙ*
© 2012 г. А. ^ Соколов
Москва, ВЦ РАН Поступила в редакцию 04.05.12 г.
Последние десятилетия вопросам разработки и применения экспертных систем посвящено значительное количество публикаций (см., например, [1—3]). В данной работе рассматриваются вопросы построения оптимального алгоритма для экспертных систем отгадывания объекта в процедуре последовательного опроса о свойствах загаданного объекта с возможными неверными ответами. В качестве критерия оптимизации представлено несколько вариантов. Наиболее практически удобным признан критерий минимума энтропии. Минимизация энтропии за один шаг является аналогом детерминированного жадного алгоритма. Вопрос, задаваемый экспертной системой и минимизирующий энтропию, может выбираться на каждом шаге процедуры для любой глубины просмотра, в зависимости от вычислительных ресурсов.
Введение. Пусть имеется база знаний, состоящая из объектов и их свойств. Необходимо разработать алгоритм отгадывания объекта, загаданного пользователем. По условиям задачи алгоритм задает вопросы, на которые пользователь может отвечать "да" или "нет", и по этим ответам алгоритм пытается отгадать объект за минимальное число вопросов. На некоторые вопросы пользователь может давать неверные ответы в силу добросовестного заблуждения. Например, если речь идет об угадывании животного, пользователь может иметь неверные представления о том, что кит — это рыба, а не млекопитающее. Тем не менее алгоритм должен правильно угадать описываемое животное.
1. Формализация. Имеется база данных, содержащая N объектов и сведения о них. Сведения представлены в виде правильных ответов на вопросы и вероятностных оценок того, как могут пользователи отвечать на них. Пусть есть набор из Я возможных вопросов Q2,...,QЯ} относительно загаданного объекта и на каждый из этих вопросов можно дать четыре ответа: {А1, А2, А3, А4} = {да, нет, иногда, не знаю}. Известны вероятностные оценки р(у,г\к) получения У -го ответа на г -й вопрос для к -го объекта у = 1,..., 4, г = 1,..., Я, к = 1,..., N.
2. Байесовская оптимизация. Пусть 5 — штраф за каждый заданный вопрос, а Б — штраф за каждое неправильное угадывание. Для красоты задачи можно считать, что в базе есть несколько выделенных вопросов — назовем их прямыми вопросами — с ответами только двух типов "да" или "нет" и со штрафом Б при ответе "нет". Это прямые вопросы типа: "Является ли загаданный объект тем-то". Их столько, сколько есть в базе объектов. Пусть для определенности эти вопросы имеют номера в базе от Я + к, где к — номер объекта. Будем считать, что при ответе "да" на любой из этих прямых вопросов процедура опроса прекращается. Условные вероятности ответов на эти вопросы 1 или 0:
р(1,Я + к\к) = 1,р(2,Я + к\к) = р(3,Я + к\к) = р(4,Я + к\к) = 0 при к = 1,...,N.
Остальные вопросы, в отличие от прямых, будем называть косвенными.
Предположим, что известны априорные вероятности загадывания объектов Р = {Рь Р2,..., PN},
N
где Рк — вероятность загадывания к -го объекта: ^ Рк = 1. Тогда алгоритм выбирает очередной
к=1
вопрос на основании а) ответов на предыдущие вопросы, б) знаний априорного распределения вероятностей загадываемых объектов и в) знания условных вероятностей правильных ответов р (у, г\к). Пусть алгоритм задал г косвенных вопросов и / прямых и на последний прямой вопрос
* Работа выполнена при финансовой поддержке РФФИ (грант 12-01-91162-ГФЕ-а).
получен ответ "да". В этом случае процедура окончена, и штраф будет случайной величиной 2 = $г + Б(/ - 1). Средние потери будут математическим ожиданием этой случайной величины Е(2) и могут быть вычислены по формуле
N
Е(2) = ^ РЕ(Ак),
к=1
где Е (21 к) — средние потери при условии, что загадан к -й объект. Так как Е(2\к) = X ^ /1к)Е(2, г, /\к),
г,/
где д(г, /\к) — вероятность того, что угадывание к -го объекта закончится после г косвенных и / прямых вопросов, т.е. на (г + /) -й вопрос будет получен ответ "да"; Е (2, г, / \ к) — величина потерь при этих условиях, которая равна $г + Б(/ - 1), то окончательно имеем
к=1
Е(2) = X Рк X 9(г, / I к) (г + Б(/ - 1))
V г,/
(2.1)
Вероятность д(г,/\к) зависит от алгоритма выбора очередного вопроса.
Искомый алгоритм — это правило, сопоставляющее каждому подмножеству вопросов и ответов на них номер следующего вопроса. Очевидно, что это правило не зависит от порядка уже заданных вопросов. Задача состоит в том, чтобы найти алгоритм выбора очередного вопроса, максимизирующий (2.1).
3. Эвристика. Рассчитать в общем случае эти вероятности р(г, / \ к) — нетривиальная задача, решение которой лучше отложить на потом. К тому же вероятностные оценки ответов пользователей приблизительные, и, возможно, удовлетворительные результаты удастся получить более простыми методами. Поэтому будем пытаться искать оптимальный алгоритм в классе каких-то более-менее разумных эвристических алгоритмов.
4. Аналогии с Вальдом. Один тип эвристических алгоритмов можно устроить по принципу двухпорогового вальдовского алгоритма [4] принятия последовательных статистических решений. Согласно Вальду вводятся два порога, с которыми сравнивается статистика. Испытания продолжаются до тех пор, пока статистика находится между порогами. В классической вальдов-ской задаче оптимальные пороги, минимизирующие среднее число испытаний, рассчитываются по вальдовским формулам на основании заданных вероятностей правильного обнаружения и ложной тревоги. Отличия от классического вальдовского случая состоят в том, что мы имеем: а) многоальтернативную проблему выбора, б) неравнозначные эксперименты + проблему выбора их последовательности, в) сложность расчета статистики отношения правдоподобия, которая должна сравниваться с порогами, г) возможность пересмотра решения и продолжение опроса.
Мы попытались сконструировать вальдовский алгоритм, взяв в качестве статистики среднее расстояние от объекта до набора полученных ответов. Решающее правило состояло в том, чтобы выбрать очередной вопрос, дающий максимальный разброс по ответам. Результаты экспериментов показали затягивание процедуры, что, в общем, характерно для применения вальдовского алгоритма в многоальтернативном случае.
5. Принцип дихотомии. Другая эвристическая модель может быть основана на принципе дихотомии [5]: по результатам каждого эксперимента половина или что-то около того "плохих" объектов исключается из рассмотрения, а оставшаяся половина участвует в выборе следующего вопроса и по результатам ответа на него подвергается следующей дихотомии.
Нужно модифицировать этот алгоритм так, чтобы он учитывал возможности ошибок и неправильных представлений пользователей о загаданном объекте. Предлагаются следующие варианты.
1. Рассматривается некоторая разумная метрика для определения расстояния от ответа на вопрос до объекта. Чем хуже согласуется ответ на вопрос о некотором свойстве объекта с объективными данными и субъективными представлениями пользователей об этом свойстве объекта, тем больше расстояние от этого ответа до объекта. Наименьшее расстояние — 0, наибольшее — 1.
2. В качестве статистики берем усредненное по полученным ответам расстояние от объекта до набора ответов, чтобы сгладить влияние случайной составляющей.
3. Для отбраковки на очередном шаге объектов потребуется некоторый алгоритм кластеризации полученных статистик по объектам. Устройство этого алгоритма кластеризации может быть
разным, но он должен отобрать один кластер с минимальным значением статистики. Один из простейших вариантов — ранжирование объектов по возрастанию статистики и отбраковывание половины худших объектов. Недостаток его в том, что в одних случаях отбракуется мало объектов, а в других случаях близкие варианты могут оказаться "по разные стороны баррикад". Второй вариант алгоритма — деление ранжированных объектов в том месте, где между ними самое большое расстояние. Недостаток этого алгоритма в том, что он может давать медленную сходимость, либо удалять слишком много потенциально привлекательных объектов. Третий вариант — посчитать число объектов, у которых усредненная величина статистики не более 0.5.
Пока остановились на втором варианте и по умолчанию доля оставляемых объектов Q1 = 0.8. Другими словами, максимальный скачок ищется только среди 80% объектов с минимальной статистикой. Отобранные объекты будем называть "лидеры". Так как кластеров может быть несколько, нужно попробовать еще раз кластеризовать полученных лидеров.
Один из вариантов такой. Пусть лидеров п штук. Ранжируем всех лидеров по величине статистики 5. Возьмем некоторый объект номер т на этой шкале 1 < т < п, 5(т) < 5(п) и предположим, что объекты 1,...,т принадлежат одному кластеру (кластер т), а объекты т + 1,...,п — второму (кластер п). Подсчитаем внутрикластерное расстояние для кластера т и для п и сравним с межкластерным. В качестве внутрикластерного расстояния можно взять дисперсии расстояний относительно средних точек (центроидов) кластеров
т
От = X ( - Ет )2/т,
к=1 т
где Ет = X 5(к)/т — центроид. Суммирование ведется по всем объектам кластера т. Аналогично
к=1
п
Бп = X (5(к) - Еп )2/(п - т),
к=т+1
п
где Ет = X 5(к)/(п - т), суммирование ведется по всем объектам кластера п.
к=т+1
Из этих дисперсий выбираем максимальную и ищем такое т, которое дает минимум: Бт1п = ш1пшах{Бт, Бп]. Сравним Бт1п с межкластерным расстоянием, которое равно
т
п
От+п = X () - Ет+п ) к=1
п
где Ет+п = X 5(к)/п, суммирование ведется по всем объектам обоих кластеров. Если отношение
к=1
Бт+п /Бтп достаточно велико, то считаем, что здесь два кластера и отбираем в лидеры только полученные т объектов. Если нет, то оставляем в лидерах все п объектов.
4. Для выбора локально оптимального вопроса нужно проанализировать все возможные варианты вопросов и ответов и посмотреть, как они разбивают множество лидеров. Тот вопрос, который разобьет множество лидеров на два примерно равномощных кластера, и будет считаться оптимальным.
Вначале д
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.