3. Представление

Вид материала

Обзор

Содержание ГЛАВА 21. Сети доверия 21.1. Теория Демпстера—Шефера Можно рассматривать эти свидетельства как элементы множества U и построить отображение Г:U -> 2 21.1.1. Функции доверия m(пустое множество) = 0 и [(т(Аi) - 1] А может быть найдено суммированием значений т Оценка привлекательности A, Рls(A), представляет степень совместимости свидетельства с гипотезами в А и может быть вычислена по Поскольку определенная таким образом оценка привлекательности А есть не что иное, как мера нашего недоверия к -A, то можно запис Таким образом 21.1.2. Применение теории Демпстера—Шефера к системе MYCIN Авторы выделили три варианта комбинирования свидетельств в результате выполнения правил при использовании модели Демпстера—Шефер

Подобный материал:

• Вопросы к экзамену по курсу " ЭВМ и периферийные устройства" для групп К2-121, -122,, 75.03kb.
• И представление налоговой отчетности, 357.06kb.
• И представление налоговой отчетности, 394.07kb.
• Дать детям представление о речевом этикете, как о правилах поведения в различных ситуациях;, 241.98kb.
• Дать общее представление о витаминах, познакомить учащихся с их классификацией, представителями, 180.08kb.
• Урок Окружающий мир 2 класс умк «Перспективная начальная школа», 44.76kb.
• Задачи:; развивать обобщенное представление о казахстанцах; сформировать представление, 49.53kb.
• Урок 57 Источники права Цель, 56.46kb.
• Вопросы для подготовки к экзамену по архитектуре ЭВМ, 79.1kb.
• Отчет об оказании юридических услуг за 20 г. Представляют, 89.3kb.

^

ГЛАВА 21. Сети доверия

21.1. Теория Демпстера—Шефера

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

21.3. Сравнение методов неточных рассуждений

21.4. Резюме

Рекомендуемая литература

Упражнения

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

Оба подхода будут описаны достаточно подробно, а затем будет проведено их сравнение. Будет показано, что оба метода имеют под собой более убедительное математическое обоснование, чем метод, базирующийся на эмпирических коэффициентах неопределенности, о котором шла речь в главе 9. Их можно рассматривать как альтернативу эвристическим методам обработки неопределенности, использованным в системах INTERNIST и CENTAUR, описанным в главе 13.

^

21.1. Теория Демпстера—Шефера

В теории Демпстера—Шефера (Dempster—Shafer) предполагается, что гипотезы — компоненты пространства гипотез 6 — являются взаимно исключающими, а набор гипотез — исчерпывающим. В терминологии авторов пространство гипотез 0 называется областью анализа (frame of discernment). Также предполагается, что мы располагаем средством получения свидетельств не только в пользу отдельных гипотез h₁.....h_n, принадлежащих 6, но и в пользу подмножеств гипотез A₁ ..., A_k, которые могут перекрываться.

^

Можно рассматривать эти свидетельства как элементы множества U и построить отображение

Г:U -> 2^O,

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

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

^

21.1.1. Функции доверия

В теории Демпстера—Шефера т — это функция присвоения базовых вероятностей (bра — basic probability assignment), которая определена на множестве 2^O значений из интервала [0,1], такая, что

^

m(пустое множество) = 0

и

[(т(Аi) - 1];

суммирование выполняется по всем

A_i 2^O.

Суммарное доверие Bel для любого фокального элемента ^ А может быть найдено суммированием значений т по всем подмножествам в А. Таким образом, Bel является функцией, определенной на множестве 2^е значений из интервала [0,1], такой, что

Bel(A) = _{B A}m(B).

Ве1(0) всегда равно 1, независимо от значения т(O). Это следует из определения функции присвоения базовых вероятностей. Соотношение Ве1(O) = 1 означает следующее: можно с полной уверенностью утверждать, что в пространстве 0 обязательно имеется корректная гипотеза, поскольку по определению набор гипотез является исчерпывающим. Значение m(O) отображает вес свидетельства, еще не учтенного в подмножествах, входящих в пространство 0. Значения Bel и т будут равны для множеств, состоящих из единственного элемента.

Оценка вероятности фокального элемента А будет ограничена снизу оценкой доверия к А, а сверху — оценкой привлекательности А, которая равна 1 - Веl(A^с)> где A^с — дополнение к A.

^

Оценка привлекательности A, Рls(A), представляет степень совместимости свидетельства с гипотезами в А и может быть вычислена по формуле

Рls(A)= _{A^B не равно пустому множеству} m(B).

^

Поскольку определенная таким образом оценка привлекательности А есть не что иное, как мера нашего недоверия к -A, то можно записать:

Рls (A) = 1 - Вel (-A).

Значение оценки привлекательности А можно рассматривать как предел, до которого можно улучшить гипотезы из А при наличии свидетельств в пользу гипотез-конкурентов. Удобно рассматривать информацию, содержащуюся в оценке Bel для данного подмножества, в виде доверительного интервала в форме [Вel(A), Pls(A)]. Ширина интервала может служить оценкой неуверенности в справедливости гипотез из А при имеющемся наборе свидетельств.

Правила Демпстера позволяют вычислить новое значение функции доверия по двум ее значениям, базирующимся на разных наблюдениях. Обозначим Bel₁ и Веl₂ два значения функции доверия, которым соответствуют два значения функции присвоения базовых вероятностей т₁ и т_г. Правило позволяет вычислить новое значение т₁+т₂, а затем и новое значение функции доверия Веl₁+ Веl₂, основываясь на определениях, приведенных выше.

Для гипотезы А значение т₁+т₂(А) есть сумма всех произведений в форме т₁(Х) m₂(Y), где X и Y распространяются на все подмножества в в, пересечением которых является А. Если в таблице пересечений будет обнаружен пустой элемент, выполняется нормализация. В процедуре нормализации значение k определяется как сумма всех ненулевых значений, присвоенных в множестве 0, затем т₁+т₂(0) присваивается значение нуль, а значения m₁+m₂ для всех других множеств гипотез делится на (1 - k).

^

Таким образом,

m₁+m₂= _X^Y=A[m₁(X)m₂(Y)]/[1- X^Y=пустое множество{m₁(X)m₂(Y)}]

Следует учитывать, что значения т₁ и m₂ сформированы по независимым источникам свидетельств в пределах того же пространства гипотез. Обратите внимание и на тот факт, что вследствие коммутативности операции умножения правило Демпстера дает один и тот же результат при любом порядке объединения свидетельств.

^

21.1.2. Применение теории Демпстера—Шефера к системе 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, она предоставляет инженеру по знаниям определенную гибкость в том, что можно назначать степень доверия к подмножествам в пространстве гипотез, состоящим более чем из одного элемента. Такое назначение может служить средством кодирования зависимостей между группами свидетельств. Иерархическая организация областей распознавания способствует упрощению этой технологии обработки