Применение теории Демпстера—Шефера к системе MYCIN

Гордон (Gordon) и Шортлифф (Shortliffe) предложили использовать теорию Демпстера—Шефера в качестве альтернативы операциям с коэффициентами уверенности, применяемым в системе MYCIN. Они обратили внимание на то, что при определении организмов система MYCIN часто сужает множество рассматриваемых гипотез до определенного подмножества, включая в него, например, только грамотрицательные микроорганизмы. (Это пример того, что Кленси (Clancey) назвал применением структурных знаний.) Правила, которые порождают такое сужение пространства гипотез, ничего не говорят об относительном правдоподобии отобранных гипотез.

При использовании Байесовского подхода можно было бы предположить, что отобранные гипотезы об искомых микроорганизмах имеют равные априорные вероятности, и, следовательно, равномерно распределить между этими гипотезами веса свидетельств. Но это может привести к тому, что система не будет способна отличить случаи, когда имеются равные свидетельства в пользу каждой гипотезы, от случаев, когда такие свидетельства отсутствуют вовсе. Функция присвоения базовых вероятностей в теории Демпстера—Шефера не делает различия между априорными и апостериорными вероятностями, а потому и не приводит к такому распределению вероятностей.

Функции доверия в теории Демпстера—Шефера позволяют также избежать и другого следствия применения Байесовского подхода, противоречащего нашей интуиции. При использовании Байесовского подхода субъективная интерпретация вероятностей означает, что, доверяя в определенной степени гипотезе Я, мы тем самым изменяем степень доверия к остальным гипотезам, т.е.

Р(H) = 1 - Р(-H).

Однако одна из слабостей модели подтверждения, которая в MYCIN использует коэффициенты уверенности, состоит в том, что свидетельство, частично подтверждающее определенную гипотезу, не может рассматриваться одновременно и как свидетельство, эту гипотезу опровергающее. В теории Демпстера—Шефера изменение степени доверия к подмножеству гипотез А не принуждает к изменению степени доверия к остальным гипотезам, поскольку Веl(A) + Веl(A^с)=< 1. Остаток после суммирования степеней доверия А и к А^с — это степень игнорирования гипотезы А.

Гордон и Шортлифф показали также, как можно применить теорию Демпстера— Шефера в MYCIN для вывода суждений о гипотезах на основании поступивших свидетельств. Триада (объект-атрибут-значение), включенная в правую часть правил, представляет в каждом из них единственную гипотезу (т.е. множество гипотез, состоящее из единственного элемента), "ответственную" за данное значение определенного атрибута в определенном объекте. Следовательно, любое множество таких триад, имеющих те же самые объекты и те же самые атрибуты, например (ORGANISM-1 IDENTITY <значенае>), образует пространство гипотез в том смысле, как это трактуется в теории Демпстера— Шефера. Если параметр имеет единственное значение, условие взаимной исключительности гипотез не нарушается. Набор значений в правилах также должен быть исчерпывающим.

Таким образом, правила в системе должны быть построены как своего рода описания функций доверия в теории Демпстера—Шефера. Если посылка в правиле подтверждает заключение о гипотезе H со степенью d и d имеет значение, превышающее определенный порог активизации правила, то значение коэффициента уверенности, связанного с этой гипотезой H, можно рассматривать как функцию присвоения базовых вероятностей, которая присваивает значение d множеству {H}, состоящему из одной гипотезы, а значение 1 - d — пространству 6. Если же посылка опровергает гипотезу со степенью уверенности d, то мы присваиваем значение d множеству {H}^c, значение 1 -d — пространству O, а значение коэффициента уверенности, связанного с этой гипотезой Я, будет равно -d.

Авторы выделили три варианта комбинирования свидетельств в результате выполнения правил при использовании модели Демпстера—Шефера.

(1)Оба правила либо подтверждают, либо опровергают одно и то же заключение {H}, причем правила характеризуются базовыми вероятностями т₁ и т₂. В этом случае некоторый вес свидетельства будет распределен между {H} и O. Обновленные значения доверия для этих двух множеств будут иметь вид т₁+т₂({Н}) и т₁+т₂(O). При этом нет необходимости применять k-нормализацию, поскольку {H} ^ O не равно 0. Оказывается, что в этом случае теория Демпстера—Шефера дает тот же результат, что и метод обработки коэффициентов уверенности.

(2) Одно правило подтверждает гипотезу {H} со степенью т₁, а другое правило ее опровергает со степенью т₂, т.е. подтверждает {H}^с. В этом случае необходима нормализация, поскольку {H}^{H}^с = 0. Иначе значения вероятностей будут комбинироваться, как и ранее:m₁+m₂({H}), т₁+т₂({Н}^с) и т₁+т₂(O).

В этом случае результаты отличаются от полученных при использовании коэффициентов уверенности. Если применить правило Демпстера, то оказывается, что такое противоречивое свидетельство приводит к снижению поддержки и гипотезы {H}, и ее оппонентов {H}^с, а растет доверие к 0. (В результате появления противоречивого свидетельства для каждого из множеств гипотез увеличивается оценка привлекательности Pls, поскольку поддержка оппонента снижается. Этот результат не согласуется с нашим интуитивным представлением о привлекательности, но следует отметить, что в теории Демстера—Шефера этот термин имеет несколько отличный от обыденного смысл.) Применение тех функций комбинирования коэффициентов уверенности, которые используются с MYCIN, скажется только на той гипотезе, которая характеризуется большим значением коэффициента уверенности.

(3) Правила выносят заключения, касающиеся двух конкурирующих гипотез {H₁} и {H₂}, т.е. двух множеств, каждое из которых содержит только по одному элементу. Если {H₁} ^ {H₂} =0, то потребуется нормализация и нужно будет вычислить значения оценок m₁+m₂({H₁}), m_l+m₂({H₂}) и т₁+т₂(O).

Правило Демпстера и в этом случае оказывается более общим, чем функции комбинирования коэффициентов уверенности в MYCIN. Это проявляется в том, что если между {H₁} и {H₂} существует отношение подмножества, то доверие к подмножеству будет расцениваться как доверие к супермножеству, но не наоборот. Таким образом, при использовании модели Демпстера—Шефера появление нового свидетельства оказывает большее влияние, чем при использовании прежней модели, основанной на коэффициентах уверенности.

Гордон и Шортлифф предложили приближенные методы вычислений, позволяющие снизить объем вычислительных операций по сравнению с оригинальной теорией Демпстера—Шефера. Они также обратили внимание на то, что разделение пространства поиска, подобное выполненному в системе INTERNIST, поможет выделить достаточно малое множество конкурирующих гипотез, образующих текущую область анализа. Однако в таких системах, как INTERNIST, при формировании множества конкурирующих гипотез невозможно выполнить прямое отображение вида Г:U —> 2_O между отдельными свидетельствами и множествами гипотез, полагая, что симптомы могут быть причастны к разделению множеств гипотез на уровни иерархии.

За последние десять лет популярность теории Демпстера—Шефера неуклонно растет. Она находит применение в различных областях, например при решении задач диагностирования [Biswas and Anand, 1987] и машинного зрения [Provan, 1990]. Хотя эта теория и не позволяет решить проблему условной зависимости, о которой шла речь в главе 9, она предоставляет инженеру по знаниям определенную гибкость в том, что можно назначать степень доверия к подмножествам в пространстве гипотез, состоящим более чем из одного элемента. Такое назначение может служить средством кодирования зависимостей между группами свидетельств. Иерархическая организация областей распознавания способствует упрощению этой технологии обработки

Методика Перла

Альтернативой теории Демпстера—Шефера является методика Перла [Pearl, 1986], в которой свидетельства учитываются на основе Байесовского подхода к группированию и распространению влияния свидетельств на достоверность гипотез. Как и в методике, предложенной Гордоном (Gordon) и Шортлиффом (Shortliffe), предполагается, что в пространстве гипотез выделено некоторое подмножество гипотез, представляющих интерес в определенном семантическом контексте, причем это подмножество имеет иерархическую структуру.

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

От эксперта также требуется выделить множество гипотез S, на которые непосредственно распространяется определенное множество свидетельств Е. Если свидетельства из Е непосредственно влияют на гипотезы из S, то должен существовать какой-то причинный механизм, связывающий каждый член множества S со свидетельствами, причем он является уникальным для каждого из них. Однако сами по себе свидетельства в множестве Е не несут никакой информации, которая позволила бы нам отдать предпочтение одному из членов S перед другими.

Это отображение множеств друг на друга позволяет ввести понятие условной независимости между свидетельствами и отдельными гипотезами h_i:

Р(Е | S, h_i) = Р(Е | S, h₁), для всех h_i S.

С помощью отношения вероятностей можно количественно оценить степень, с которой свидетельства подтверждают или опровергают множество гипотез S:

лS=[P(E|S)] / [P(E|-S)].

Влияние свидетельств Е на множество S вычисляется следующим образом. Каждая отдельная гипотеза h_i, принадлежащая множеству S, получает вес W_i = л_S , в то время как каждая гипотеза из дополняющего множества S^C получает вес W_i = 1. Все это выполняется на фазе распределения весов.

Затем, когда наступает фаза обновления, вычисляется новое значение функции доверия ВЕL'(h_i) по ее прежнему значению ВЕL(h_i):

BEL'(h_i) = P(h_i | Е) = a _s W_iВЕL(h_i),

где a _s — коэффициент нормализации, заданный соотношением

a _s =( _i[W_iBEL'(h_i))^-1.]

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

Вся схема вычислений основана на предположении об условной независимости и соблюдении симметричности множеством S^C, дополняющим S. Из соотношения

Р(Е | S^C, h_i) = Р(Е | S^C, h_i)

Для всех

h_i S^C следует,

что Р(Е | h_i) = Р(Е | S), если h_i, h_i S, иначе Р(Е | S^C).

Из этого соотношения и правила Байеса следует, что P(h,| Е) = a_sX_sP(h,), если Л, е S, иначе a_sP(h,).

Но, хотя Перл использует формализм Байеса, частичное свидетельство в пользу какой-либо гипотезы не может быть истолковано и как частичная поддержка отрицания этой гипотезы. Свидетельство в пользу подмножества гипотез S не может быть истолковано как свидетельство в пользу дополнения к этому подмножеству 5^е.

Распределение свидетельств в пользу подмножества между отдельными гипотезами восстанавливает точечное распределение вероятностей на пространстве гипотез, но это происходит за счет точности оценок для отдельных гипотез. Перл утверждает, что нет необходимости распределять общий показатель, взятый для всего подмножества S, на его элементы до тех пор, пока не будут получены дополнительные свидетельства (или все возможные). Нормализацию также можно отложить до тех пор, пока полученные свидетельства не подтолкнут систему к выделению определенных гипотез (возможно, разных). Например, если получены свидетельства Е₁,..., Е_n соответственно в пользу гипотез S₁,..., S_n, то веса будут комбинироваться мультипликативно

W_i(E₁,...,E_n)=W_1,i,W_2,i... W_n,i

Где

W_k,i =л_Sk если hi S_k,

Иначе 1.

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

Байесовские сети

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