Функции доверия
21.1.1. Функции доверия
В теории Демпстера—Шефера т — это функция присвоения базовых вероятностей (bра — basic probability assignment), которая определена на множестве 2O значений из интервала [0,1], такая, что
m(пустое множество) = 0
и
суммирование выполняется по всем
Ai
Bel(A) = Am(B).
Оценка вероятности фокального элемента А будет ограничена снизу оценкой доверия к А, а сверху — оценкой привлекательности А, которая равна 1 - Веl(Aс)> где Aс — дополнение к A.
Оценка привлекательности A, Рls(A), представляет степень совместимости свидетельства с гипотезами в А и может быть вычислена по формуле
Рls(A)=
Поскольку определенная таким образом оценка привлекательности А есть не что иное, как мера нашего недоверия к -A, то можно записать:
Рls (A) = 1 - Вel (-A).
Правила Демпстера позволяют вычислить новое значение функции доверия по двум ее значениям, базирующимся на разных наблюдениях. Обозначим Bel1 и Веl2 два значения функции доверия, которым соответствуют два значения функции присвоения базовых вероятностей т1 и тг. Правило позволяет вычислить новое значение т1+т2, а затем и новое значение функции доверия Веl1+ Веl2, основываясь на определениях, приведенных выше.
Для гипотезы А значение т1+т2(А) есть сумма всех произведений в форме т1(Х) m2(Y), где X и Y распространяются на все подмножества в в, пересечением которых является А. Если в таблице пересечений будет обнаружен пустой элемент, выполняется нормализация. В процедуре нормализации значение k определяется как сумма всех ненулевых значений, присвоенных в множестве 0, затем т1+т2(0) присваивается значение нуль, а значения m1+m2 для всех других множеств гипотез делится на (1 - k).
Таким образом,
m1+m2= X^Y=пустое множество{m1(X)m2(Y)}]
Применение теории Демпстера—Шефера к системе 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, она предоставляет инженеру по знаниям определенную гибкость в том, что можно назначать степень доверия к подмножествам в пространстве гипотез, состоящим более чем из одного элемента. Такое назначение может служить средством кодирования зависимостей между группами свидетельств. Иерархическая организация областей распознавания способствует упрощению этой технологии обработки.
Байесовские сети
21.1. Байесовские сети
В работе [Pearl, 1988] описан формализм, которому автор присвоил название Байесовские сети. Этот механизм можно рассматривать как обобщение описанных в данном разделе иерархических сетей доверия. В Байесовской сети дуги между узлами также представляют причинные зависимости, но допускается ситуация, когда некоторые узлы имеют множество родителей, причем структура сети может содержать петли. Обновление оценок доверия выполняется с помощью передачи сообщений, как и в случае строгой иерархической организации, хотя действие этого механизма очевидно только для полидеревьев, т.е. сетей, в которых между любыми двумя узлами существует единственный путь.
Представляет интерес сравнение формализма Перла и теории Демпстера — Шефера.
В системе Перла определение функции ВЕL(h1) через P(h1) и BEL'(h1) через P(h, | E) позволяет более корректно обосновать эти функции на основе выводов теории вероятностей, чего нельзя сказать о правилах комбинирования Демпстера, с чем согласился и Шефер в работе [Shafer, 1976].
Йен [Yen, 1986] обратил внимание на то, что в формализме Перла теряется понятие доверительного интервала, внутри которого могут изменяться вероятностные оценки. Доверительные интервалы очень удобно использовать в экспертных системах, поскольку они позволяют судить о "качестве" гипотез, возможности их совершенствования и ассоциированной степени неопределенности.
В своей книге [Pearl, 1988] Перл совершенно справедливо отмечает, что теория Демпстера—Шефера основана на неполной вероятностной модели, а потому может дать только частичные ответы. Вместо того чтобы непосредственно оценить, насколько близка гипотеза к тому, чтобы ее можно было считать истинной, эта теория говорит, как сильно полученное свидетельство должно продвинуть нас к убеждению, что данная гипотеза истинна. В этом отношении теория Демпстера—Шефера значительно больше напоминает объективистские методы проверки значимости с использованием доверительных интервалов, чем субъективистские методы на основе Байесовского подхода [Neapolitan, 1990].
Но, несмотря на отмеченные различия, в обоих подходах есть много общего, почему мы и рассматриваем их совместно в рамках одной главы. Ассоциирование свидетельств с подмножествами гипотез в рамках метода Перла не противоречит отображению одного множества на другое в теории Демпстера—Шефера. Оба варианта можно рассматривать как использование метафоры "массового распределения" в том смысле, что основное внимание уделяется распределению полученных свидетельств в контексте структурированного пространства альтернатив, причем оба метода позволяют вычислять значения функции доверия на основе простых вероятностных оценок.
Теория Демпстера—Шефера
21.1. Теория Демпстера—Шефера
В теории Демпстера—Шефера (Dempster—Shafer) предполагается, что гипотезы — компоненты пространства гипотез 6 — являются взаимно исключающими, а набор гипотез — исчерпывающим. В терминологии авторов пространство гипотез 0 называется областью анализа (frame of discernment). Также предполагается, что мы располагаем средством получения свидетельств не только в пользу отдельных гипотез h1.....hn, принадлежащих 6, но и в пользу подмножеств гипотез A1 ..., Ak, которые могут перекрываться.
Можно рассматривать эти свидетельства как элементы множества U и построить отображение
Г:U -> 2O,
Теория Демпстера—Шефера предлагает средства вычисления функции доверия на таких множествах гипотез и правила объединения функций доверия, сформулированных на основании разных свидетельств.
Методика Перла
21.2. Методика Перла
Альтернативой теории Демпстера—Шефера является методика Перла [Pearl, 1986], в которой свидетельства учитываются на основе Байесовского подхода к группированию и распространению влияния свидетельств на достоверность гипотез. Как и в методике, предложенной Гордоном (Gordon) и Шортлиффом (Shortliffe), предполагается, что в пространстве гипотез выделено некоторое подмножество гипотез, представляющих интерес в определенном семантическом контексте, причем это подмножество имеет иерархическую структуру.
Предполагается также, что еще до получения свидетельств с каждой отдельной гипотезой связано определенное значение степени доверия к ее правдоподобности. Перл не уточняет, каким именно способом формируются эти исходные значения, но скорее всего это должен сделать эксперт в предметной области при формулировке гипотез.
От эксперта также требуется выделить множество гипотез S, на которые непосредственно распространяется определенное множество свидетельств Е. Если свидетельства из Е непосредственно влияют на гипотезы из S, то должен существовать какой-то причинный механизм, связывающий каждый член множества S со свидетельствами, причем он является уникальным для каждого из них. Однако сами по себе свидетельства в множестве Е не несут никакой информации, которая позволила бы нам отдать предпочтение одному из членов S перед другими.
Это отображение множеств друг на друга позволяет ввести понятие условной независимости между свидетельствами и отдельными гипотезами hi:
Р(Е | S, hi) = Р(Е | S, h1), для всех hi
Сравнение методов неточных рассуждений
21.3. Сравнение методов неточных рассуждений
В работе [Horvitz et al, 1986] предлагается обобщенная модель, которая может служить в качестве оболочки для сравнения альтернативных формализмов оценок доверия к гипотезам. Описанная модель появилась в ходе обширной дискуссии, призванной пролить свет на проблемы неточных рассуждений, которые проявились в процессе эксплуатации системы MYCIN. Авторы этой работы, основываясь на работах Кокса [Сох, 1946], выделили набор свойств, которыми должны обладать параметры, предлагаемые в качестве меры доверия. Идея состояла в том, чтобы обеспечить некоторый единый теоретико-вероятностный базис для сравнения альтернативных формализмов.
Предлагаемые Горвицем свойства перечислены ниже.
(Р1) Ясность. Высказывания должны быть сформулированы настолько четко, чтобы всегда можно было выполнить проверку истинности условий в них.
(Р2) Скалярная непрерывность. Степень доверия к высказыванию должна выражаться действительным числом, значение которого может непрерывно изменяться в диапазоне от полного доверия к истинности до полного отрицания истинности.
(РЗ) Полнота. Должна быть обеспечена возможность приписать значение степени доверия любому правильно сформулированному высказыванию.
(Р4) Зависимость от контекста. Степень доверия к одному высказыванию может зависеть от степени доверия к другим высказываниям.
(Р5) Гипотетическая условность. Должна существовать функция, которая позволяла бы вычислить оценку доверия к совокупности высказываний по степени доверия к одному из высказываний и оценкам доверия к другим высказываниям в предположении, что первое истинно.
(Р6) Комплементарность. Оценка доверия к отрицанию высказывания должна быть монотонно убывающей функцией от оценки доверия к самому высказыванию.
(Р7) Совместимость. Высказывания с одинаковыми значениями истинности должны иметь одинаковые оценки доверия.
Можно показать, что аксиомы теории вероятности являются логическим следствием из этих аксиом, т.е. существует непрерывная монотонная функция Ф, такая, что
(А2) Ф(TRUЕ|е)=1;
(А4) Ф(QR |e)=Ф(Q|e)Ф(R | е).
Для классификации подходов к оценке степени доверия, не основанных на теории вероятностей, Горвиц использует четыре категории:
(С1) обобщение — определенные свойства ослабляются или исчезают вовсе;
(СЗ) внутренняя несовместимость — (С2) приводит к тому, что набор свойств становится несовместимым;
(С4) подстановка — изменения свойств нельзя отнести к категориям (С1) или (С2).
Для демонстрации практического использования предлагаемой модели Горвиц сравнивает формализмы нечеткой логики (см., например, [Zadeh, 1981]), теории Демпстера — Шефера [Shafer, 1976] и коэффициентов уверенности в системе MYCIN с теорией вероятностей.
Для нечетких логик характерно ослабление свойства (Р1), поскольку в них предполагается назначение оценки доверия расплывчатым высказываниям. Формализм нечеткой логики может быть отнесен к категории (С 1 ). Расплывчатость представления об истинности в нечетких логиках несовместима со свойством гипотетической условности (Р5). Формализм нечеткой логики оценивает доверие к совокупности высказываний по минимальному значению оценки для компонентов, что противоречит аксиоме (А4). В результате Горвиц относит эти формализмы к категории (С4).
Наиболее существенным отличием теории Демпстера—Шефера от классической теории вероятностей Горвиц считает ослабление свойства полноты (РЗ). Эта теория позволяет утверждать, что определенные априорные и условные вероятности не могут быть оценены, и в ней вводится понятие отношения совместимости между допущениями. Это приводит к нарушению свойств скалярной непрерывности комплементарноети (Р6). В результате Горвиц относит эту теорию к категории обобщения теории вероятностей (С1).
В использованной в MYCIN модели на основе коэффициентов уверенности применяются более строгие предположения, чем в вероятностной модели оценки доверия, а потому ее следовало бы отнести к категории (С1). Но мы уже отмечали, что для этой модели характерна внутренняя несовместимость, и Горвиц относит ее к категории (СЗ). Предложенная в [Heckerman, 1986] новая формулировка коэффициентов уверенности в терминах отношения вероятностей является, однако, весьма удачной специализацией.
Резюме
21.4. Резюме
В работах Горвица (Horvitz) и Гекермана (Heckerman) продемонстрирован типичный теоретический подход к проблеме неопределенности, в котором основное внимание сосредоточено на сравнении семантик различных формальных языков вычисления оценки степени доверия. Однако нужно иметь в виду, что классическая теория вероятностей также допускает неоднозначное семантическое толкование. Например, в работе [Shafer and Tversky, 1985] отмечаются три способа интерпретации формализма Байеса:
семантика частотности — мы задаемся вопросом, как часто при наличии данного свидетельства гипотеза оказывается истинной;
семантика пари — мы определяем, каковы шансы на успех при заключении пари в пользу истинности определенной гипотезы в свете имеющихся свидетельств;
семантика склонности — мы изучаем причинно-следственную модель и пытаемся ответить на вопрос, насколько хорошо данная гипотеза объясняет наблюдаемую ситуацию.
Частотная интерпретация меры доверия используется в экспертных системах чрезвычайно редко. Например, в работе [Buchanan and Shortliffe, 1984, Chapter 11] авторы предпочитают рассматривать оценку доверия как степень подтверждаемости гипотезы, что очень близко к семантике пари. Эта же интерпретация имеет совершенно очевидную связь с оценкой степени риска, используемой в эвристических правилах MYCIN. Модель, используемая в системе INTERNIST, ближе к интерпретации склонности, поскольку в ней значительное внимание уделено возможности формирования пояснений и анализу причинно-следственных связей между свидетельствами и гипотезами.
Таким образом, ясно просматривается тенденция к повышению уровня обоснованности как в теоретических работах, так и в практическом воплощении соответствующих методов в реальных системах.
Сети доверия
ГЛАВА 21. Сети доверия 21.1. Теория Демпстера—Шефера 21.1.1. Функции доверия 21.1.2. Применение теории Демпстера—Шефера к системе MYCIN 21.2. Методика Перла 21.3. Сравнение методов неточных рассуждений 21.4. Резюме Рекомендуемая литература Упражнения
Пространство гипотез о неисправностях в автомобиле
Пространство гипотез о неисправностях в автомобиле
I) Предположим, что степень подтверждения диагноза неисправность карбюратора имеющимися свидетельствами оценивается значением 0.8. Вычислите т(неисправность бензопровода), т(неисправность электрооборудования) и m(0).
II) Предположим, что степень опровержения диагноза неисправность системы подачи топлива имеющимися свидетельствами оценивается значением 0.6. Вычислите т{неисправность электрооборудования).
Ill) Предположим, что степень подтверждения диагноза неисправность карбюратора имеющимися свидетельствами оценивается значением 0.2, а диагноза неисправность бензопровода— значением 0.5. Вычислите т(неисправность системы подачи топлива). .
2. Используя пространство гипотез, представленное на рис. 21.1, предположим, что степень подтверждения диагноза неисправность системы подачи топлива имеющимися свидетельствами оценивается значением 0.3, а диагноза неисправность аккумуляторной батареи — значением 0.6. Вычислите значения т для всех узлов графа, используя правило Демпстера.
3. Пусть на пространстве гипотез, представленном на рис. 21.1, априорные вероятности отдельных гипотез равны:
Равноправность карбюратора) = 0.4;
Р(неисправность бензопровода) = 0.1;
Р(неисправность аккумуляторной батарей) = 0.3.
Р(е| неисправность карбюратора) = 0.3;
Р(е| —неисправность карбюратора) = 0.5;
Р(е| неисправность бензопровода) = 0.2;
Р(е| —(Неисправность бензопровода) = 0.4;
Р(е| неисправность аккумуляторной батареи) = 0.6;
Р(е| —(Неисправность аккумуляторной батареи) - 0.3;
Р(е| неисправность распределителя) = 0.7;
Р(е| —(неисправность распределителя) = 0.1.
Рекомендуемая литература
Рекомендуемая литература
В своей книге [Pearl, 1988] Перл уделяет основное внимание методам, основанным на Байесовском подходе, демонстрируя их возможности на множестве примеров, взятых из различных областей искусственного интеллекта. Эту книгу можно рекомендовать в качестве отправной точки для детального изучения проблемы обработки неопределенности в задачах искусственного интеллекта, поскольку изложенный в ней материал является самодостаточным. Структура книги позволяет читателям с разным уровнем подготовки выбирать нужный для себя материал. Более поздняя работа [Pearl, 1997] содержит описание последних исследований в этой области, включая и теорию сетей доверия. Среди других книг на эту тему я бы выделил [Jensen, 1996] и [Shafer and Pearl, 1990].
Сети доверия
Сети доверия
21.1. Теория Демпстера—Шефера
21.2. Методика Перла
21.3. Сравнение методов неточных рассуждений
21.4. Резюме
Рекомендуемая литература Упражнения
В этой главе мы рассмотрим два количественных метода реализации логических рассуждений при наличии неопределенности в структурированном пространстве гипотез, базирующихся на теории свидетельств Демпстера—Шефера [Gordon and Shortliffe, 1985] и Байесовском формализме [Pearl, 1986]. Каждый из этих подходов предполагает, что на множестве гипотез каким-то способом определена функция доверия (belieffunction), а затем по мере накопления новых свидетельств применяется специфический механизм обновления текущего множества допущений.
Оба подхода будут описаны достаточно подробно, а затем будет проведено их сравнение. Будет показано, что оба метода имеют под собой более убедительное математическое обоснование, чем метод, базирующийся на эмпирических коэффициентах неопределенности, о котором шла речь в главе 9. Их можно рассматривать как альтернативу эвристическим методам обработки неопределенности, использованным в системах INTERNIST и CENTAUR, описанным в главе 13.
приведена схема простого пространства
Упражнения
1. На рис. 21. 1 приведена схема простого пространства гипотез для задачи поиска неисправности в автомобиле. Корневой узел, неисправность автомобиля, представляет множество неисправностей {неисправность системы подачи топлива, неисправность электрооборудования}. Узел неисправность системы подачи топлива представляет множество {неисправность карбюратора, неисправность бензопровода}, а узел неисправность электрооборудования — множество {неисправность аккумуляторной батареи, неисправность распределителя}. Таким образом, узел неисправность автомобиля можно рассматривать как представляющий всю область анализа.
Э = {неисправность системы подачи топлива, неисправность электрооборудования, неисправность карбюратора, неисправность бензопровода}.