Введение в экспертные системы
Применение теории Демпстера—Шефера к системе MYCIN
21.1.2. Применение теории Демпстера—Шефера к системе MYCIN
Гордон (Gordon) и Шортлифф (Shortliffe) предложили использовать теорию Демпстера—Шефера в качестве альтернативы операциям с коэффициентами уверенности, применяемым в системе MYCIN. Они обратили внимание на то, что при определении организмов система MYCIN часто сужает множество рассматриваемых гипотез до определенного подмножества, включая в него, например, только грамотрицательные микроорганизмы. (Это пример того, что Кленси (Clancey) назвал применением структурных знаний.) Правила, которые порождают такое сужение пространства гипотез, ничего не говорят об относительном правдоподобии отобранных гипотез.
При использовании Байесовского подхода можно было бы предположить, что отобранные гипотезы об искомых микроорганизмах имеют равные априорные вероятности, и, следовательно, равномерно распределить между этими гипотезами веса свидетельств. Но это может привести к тому, что система не будет способна отличить случаи, когда имеются равные свидетельства в пользу каждой гипотезы, от случаев, когда такие свидетельства отсутствуют вовсе. Функция присвоения базовых вероятностей в теории Демпстера—Шефера не делает различия между априорными и апостериорными вероятностями, а потому и не приводит к такому распределению вероятностей.
Функции доверия в теории Демпстера—Шефера позволяют также избежать и другого следствия применения Байесовского подхода, противоречащего нашей интуиции. При использовании Байесовского подхода субъективная интерпретация вероятностей означает, что, доверяя в определенной степени гипотезе Я, мы тем самым изменяем степень доверия к остальным гипотезам, т.е.
Р(H) = 1 - Р(-H).
Гордон и Шортлифф показали также, как можно применить теорию Демпстера— Шефера в MYCIN для вывода суждений о гипотезах на основании поступивших свидетельств. Триада (объект-атрибут-значение), включенная в правую часть правил, представляет в каждом из них единственную гипотезу (т.е. множество гипотез, состоящее из единственного элемента), "ответственную" за данное значение определенного атрибута в определенном объекте. Следовательно, любое множество таких триад, имеющих те же самые объекты и те же самые атрибуты, например (ORGANISM-1 IDENTITY <значенае>), образует пространство гипотез в том смысле, как это трактуется в теории Демпстера— Шефера. Если параметр имеет единственное значение, условие взаимной исключительности гипотез не нарушается. Набор значений в правилах также должен быть исчерпывающим.
Таким образом, правила в системе должны быть построены как своего рода описания функций доверия в теории Демпстера—Шефера. Если посылка в правиле подтверждает заключение о гипотезе H со степенью d и d имеет значение, превышающее определенный порог активизации правила, то значение коэффициента уверенности, связанного с этой гипотезой H, можно рассматривать как функцию присвоения базовых вероятностей, которая присваивает значение d множеству {H}, состоящему из одной гипотезы, а значение 1 - d— пространству 6. Если же посылка опровергает гипотезу со степенью уверенности d, то мы присваиваем значение d множеству {H}c, значение 1 -d— пространству O, а значение коэффициента уверенности, связанного с этой гипотезой Я, будет равно -d.
Авторы выделили три варианта комбинирования свидетельств в результате выполнения правил при использовании модели Демпстера—Шефера.
(1)Оба правила либо подтверждают, либо опровергают одно и то же заключение {H}, причем правила характеризуются базовыми вероятностями т1 и т2. В этом случае некоторый вес свидетельства будет распределен между {H} и O. Обновленные значения доверия для этих двух множеств будут иметь вид т1+т2({Н}) и т1+т2(O). При этом нет необходимости применять k-нормализацию, поскольку {H} ^ O не равно 0. Оказывается, что в этом случае теория Демпстера—Шефера дает тот же результат, что и метод обработки коэффициентов уверенности.
(2) Одно правило подтверждает гипотезу {H} со степенью т1, а другое правило ее опровергает со степенью т2, т.е. подтверждает {H}с. В этом случае необходима нормализация, поскольку {H}^{H}с = 0. Иначе значения вероятностей будут комбинироваться, как и ранее:m1+m2({H}), т1+т2({Н}с) и т1+т2(O).
В этом случае результаты отличаются от полученных при использовании коэффициентов уверенности. Если применить правило Демпстера, то оказывается, что такое противоречивое свидетельство приводит к снижению поддержки и гипотезы {H}, и ее оппонентов {H}с, а растет доверие к 0. (В результате появления противоречивого свидетельства для каждого из множеств гипотез увеличивается оценка привлекательности Pls, поскольку поддержка оппонента снижается. Этот результат не согласуется с нашим интуитивным представлением о привлекательности, но следует отметить, что в теории Демстера—Шефера этот термин имеет несколько отличный от обыденного смысл.) Применение тех функций комбинирования коэффициентов уверенности, которые используются с MYCIN, скажется только на той гипотезе, которая характеризуется большим значением коэффициента уверенности.
(3) Правила выносят заключения, касающиеся двух конкурирующих гипотез {H1} и {H2}, т.е. двух множеств, каждое из которых содержит только по одному элементу. Если {H1} ^ {H2} =0, то потребуется нормализация и нужно будет вычислить значения оценок m1+m2({H1}), ml+m2({H2}) и т1+т2(O).
Правило Демпстера и в этом случае оказывается более общим, чем функции комбинирования коэффициентов уверенности в MYCIN. Это проявляется в том, что если между {H1} и {H2} существует отношение подмножества, то доверие к подмножеству будет расцениваться как доверие к супермножеству, но не наоборот. Таким образом, при использовании модели Демпстера—Шефера появление нового свидетельства оказывает большее влияние, чем при использовании прежней модели, основанной на коэффициентах уверенности.
Гордон и Шортлифф предложили приближенные методы вычислений, позволяющие снизить объем вычислительных операций по сравнению с оригинальной теорией Демпстера—Шефера. Они также обратили внимание на то, что разделение пространства поиска, подобное выполненному в системе INTERNIST, поможет выделить достаточно малое множество конкурирующих гипотез, образующих текущую область анализа. Однако в таких системах, как INTERNIST, при формировании множества конкурирующих гипотез невозможно выполнить прямое отображение вида Г:U —> 2O между отдельными свидетельствами и множествами гипотез, полагая, что симптомы могут быть причастны к разделению множеств гипотез на уровни иерархии.
За последние десять лет популярность теории Демпстера—Шефера неуклонно растет. Она находит применение в различных областях, например при решении задач диагностирования [Biswas and Anand, 1987] и машинного зрения [Provan, 1990]. Хотя эта теория и не позволяет решить проблему условной зависимости, о которой шла речь в главе 9, она предоставляет инженеру по знаниям определенную гибкость в том, что можно назначать степень доверия к подмножествам в пространстве гипотез, состоящим более чем из одного элемента. Такое назначение может служить средством кодирования зависимостей между группами свидетельств. Иерархическая организация областей распознавания способствует упрощению этой технологии обработки.
