дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
проблемы. Одна из проблем состояла в том, что значения коэффициентов достоверности могли быть противоположными условным вероятностям. Например, если даны такие значения: Р(Н2) = 0.2 Р(Н2 Е) = 0.8 Р(Н1) = 0.8 P(H E) = 09 то получаем следующее СР(Н1,E) = 0.5 и СР(Н2, Е) = 0.75 К тому же одним из назначений коэффициентов достоверности является ранжирование гипотез в терминах вероятных диагнозов, поэтому возникает противоречие, если некоторое заболевание отличается более высокой условной вероятностью Р(Н [ E), но все равно характеризуется более низким коэффициентом достоверности, СР(Н, E). Еще одна важная проблема, связанная с использованием коэффициентов достоверности, состоит в том, что, вообще говоря, справедлива следующая формула Р(Н е) ф Р(Н i)P(i е) где i некоторая промежуточная гипотеза, основанная на свидетельстве е. Но, несмотря на это, коэффициент достоверности двух правил вцепи логического вывода вычисляется с использованием независимых вероятностей по такой формуле, е) = CF(H, г)СР(г, е) Приведенная выше формула справедлива только в том частном случае, когда статистическая совокупность со свойством Н содержится в совокупности i, которая содержится в совокупности со свойством е. То, что система MYCIN оказалась успешной, несмотря на наличие этих проблем, возможно, обусловлено применением коротких цепей логического вывода и простых гипотез. Но при попытке использовать коэффициенты достоверности в других прикладных областях, не позволяющих применять короткие цепи логического вывода и простые гипотезы, могут возникнуть реальные проблемы. И действительно, Адамс (Adams) показал, что теория коэффициентов достоверности фактически является аппроксимацией по отношению к классической теории вероятностей Глава 5. Нестрогие рассуждения 5.4 Теория Демпстера — Шефера Рамки различения Теория Демпстера — Шефера основана на предположении о том, что задано фиксированное множество взаимоисключающих и исчерпывающих элементов, называемое средой и символически обозначаемое греческой буквой 0: 0 = (О1,02,...ОЯ,' Термин "среда" аналогичен термину "универсум, применяемому в теории множеств для обозначения объектов, о которых идет речь. Иными словами, среда — это множество объектов, представляющих для нас интерес. Ниже приведены некоторые примеры определения вариантов среды. 0 = (airliner, bomber, fighter) 0 = fred, green, blue, orange, yellow) 0 = (barn, grass, person, cow, car) Обратите внимание на то, что элементы в каждой среде являются взаимоисключающими. Например, авиалайнер (airliner) — не бомбардировщики не истребитель (fighter), красный цвет (red) — не зеленый, трава (grass) — не корова (cow) и т.д. Предположим, что всевозможные элементы универсума находятся в заданном множестве, таким образом, множество является В настоящем разделе рассматривается один из методов формирования нестрогих рассуждений, называемый теорией Демпстера — Шефера, или теорией Шефера — Демпстера. Этот метод основан на работе, первоначально выполненной Демпстером, который предпринял попытку смоделировать неопределенность, задавая ряд вероятностей, а не отдельное вероятностное значение. В дальнейшем Шефер дополнили уточнил результаты, полученные Демпстером, в книге А Mathematical Theory of Åòdåïñå, опубликованной в 1976 году. Еще одно расширение, получившее название рассуждений на основе свидетельств, касалось той информации, которая, согласно ожиданиям, является неопределенной, неточной и иногда неправильной. Теория Демпстера — Шефера имеет хороший теоретический фундамент. К тому же можно показать, что теория коэффициентов достоверности является частным случаем теории Демпстера — Шефера, что позволяет перевести методы, основанные на использовании коэффициентов достоверности, на теоретическую, а непроизвольную основу. Кроме того, теория Демпстера — Шефера нашла свое применение в интеллектуальных базах данных, в которых используется анализ скрытых закономерностей в данных для извлечения образов [7]. 5.4. Теория Демпстера — Шефера 415 исчерпывающим. Кроме того, чтобы упростить приведенное здесь описание, предположим, что множество 0 является конечным. Тем не менее были проведены исследования, основанные на использовании вариантов среды Демпстера — Шефера, элементами которых являются непрерывные переменные, такие как время, расстояние, скорость и т.д. Один из способов размышления о структуре множества 0 состоит в том, что рассматриваются вопросы и ответы, относящиеся к этому множеству. Предположим, что дано приведенное ниже множество, а вопрос, касающийся элементов этого множества, сформулирован так "Какие из этих самолетов имеют военное назначение. 0 = (airliner, bomber, fighter) Ответом становится следующее подмножество множества 0: (02, 03) = (bomber, fighter) Аналогичным образом, ответом на вопрос "Какие из этих самолетов имеют гражданское назначение" является множество (01] = (airliner) Правильным ответом является (01, 02, Оз) Правильным ответом является (01, 0) Всевозможные подмножества в среде представления типов самолетов приведены на рис. 5.6. Линии, проведенные на этом рисунке, показывают отношения между подмножествами. Для обозначения элементов airliner (авиалайнер, бомбардировщики (истребитель) используются буквы А, В и F. Эта Такое множество называется одноэлементным множеством, поскольку содержит только один элемент. Каждое подмножество множества 0 может интерпретироваться как возможный ответ на некоторый вопрос. Атак как все элементы являются взаимоисключающими и среда — исчерпывающей, то правильным ответом на любой вопрос может служить только одно подмножество. Безусловно, не всевозможные вопросы могут иметь смысл, к тому жене представляет интереса сам по себе поиск ответов на всевозможные вопросы. Но важно понять, что именно все подмножества среды представляют собой всевозможные действительные ответы в этом универсуме элементов, о которых идет речь. Каждое подмножество может рассматриваться как подразумеваемое высказывание, например, как в приведенных ниже случаях ив других подобных случаях, касающихся всех подмножеств, где начало высказывания "правильным ответом является" подразумевается для данного подмножества 416 Глава 5. Нестрогие рассуждения диаграмма изображена в виде иерархической решетки, в которой множество 0 находится вверху, а пустое множество И = () — внизу. Пустое множество обычно явно не показывают, поскольку оно всегда соответствует ложному ответу. Так как множество И не имеет элементов, его выбор в качестве приведенного ниже ответа противоречит предположению о том, что данная среда является исчерпывающей. Правильным ответом является отсутствие элемента Рис. 5.6. Все подмножества среды, в которой рассматриваются типы самолетов Обратите внимание на то, что диаграмма, приведенная на рис. 5.6, представляет собой решетку, а не дерево, поскольку узлы подмножеств могут иметь больше одного родительского узла. Кроме того, эта решетка является иерархической, так как она вычерчивается, начиная с более крупных множеств и заканчивая более мелкими. Например, один из путей от узла 0 к узлу И выражает иерархическое отношение подмножеств, соединяющее родительские подмножества с дочерними, как показано ниже. И С АСА, В) С (А, В, F) Напомним, что в разделе 2.10 было указано — наличие такого отношения между двумя множествами, Хи означает, что все элементы Х являются элементами У и записываются более формально следующим образом 417 5.4. Теория Демпстера- Шефера Приведенная выше формула представляет собой утверждение, что если хэлемент множества Х, из этого следует, что х также является элементом множества У. Если Х C У, но Х ф У, то имеется по меньшей мере один элемент У, не являющийся элементом Х. В таком случае Х называется строгим подмножеством У и приведенное выше выражение записывается так ХсУ Если все элементы среды могут интерпретироваться как возможные ответы и только один ответ является правильным, то среду называют рамками различения (frame of discernment). В данном случае термин "различение" показывает, что существует возможность отличить один правильный ответ от всех других возможных ответов на вопрос. Если ответ не находится в рамках, то рамки необходимо расширить, чтобы в них можно было задать дополнительные знания об элементах 0@+q, Оу+2 и т.д. А для того чтобы только один ответ был правильным, требуется, чтобы множество являлось исчерпывающим, а все подмножества несвязанными. Множество с количеством элементов N имеет точно 2 подмножеств, включая самого себя. Все эти подмножества определяют степенное множество (GM. задачу, а это записывается как Р. Таким образом, для среды, представляющей типы самолетов, имеет место следующее Р (Я,(А),В),(F),А,В),(А,F),Â,F),(А, В) Степенное множество среды включает в качестве своих элементов все ответы на всевозможные вопросы из рамок различения. Это означает, что существует взаимно однозначное соответствие между элементами P(0) и подмножествами множества О. Массовые функции и незнание Согласно байесовской теории, апостериорная вероятность по мере приобретения все новых и новых свидетельств изменяется. Аналогичным образом, в теории Демпстера — Шефера может изменяться степень доверия к свидетельству. Кроме того, в теории Демпстера — Шефера принято рассматривать степень доверия к свидетельству как аналогичную массе физического объекта. Иными словами, масса свидетельства поддерживает степень доверия. Мера доверия к свидетельству, символически обозначаемая буквой т, аналогична мере, с помощью которой можно судить о массе. Вместо термина "масса" применяется также термин основное присваивание вероятности (basic probability assignment — Ьра), а иногда просто основное присваивание, поскольку по своей форме уравнения, описывающие плотности вероятностей и массы, являются аналогичными. Но при использовании Глава 5. Нестрогие рассуждения Р 1 N Кроме того, как было сказано в главе 4, такое присваивание значения Р применяется "в безвыходной ситуации" или, если используются термины, которые звучат менее впечатляюще, на основании принципа безразличия. Крайний случай применения принципа безразличия возникает, если имеются только два возможных случая, таких как наличие нефти или отсутствие нефти, что можно обозначить символически как Ни Н. В случаях, подобных этому, Р = Ъ, даже если вообще нет никаких знаний о том, имеется ли нефть или нет, поскольку теория вероятностей гласит, что справедлива следующая формула Р(Н) + Р(Н') = Таким образом, все, что не обосновывает гипотезу, должно ее опровергать, поскольку возможность незнания не допускается. Если подобный подход применяется без размышлений, то могут обнаруживаться некоторые нелепые последствия. Например, допустим, что человек размышляет, есть месторождение нефти под его домом или нет. Согласно принципу безразличия, если полностью отсутствуют какие-либо другие знания, то вероятность наличия месторождения нефти под домом равна 50 lo. Стоит только об этом подумать, можно прийти к выводу, что 50'Ъ-ные шансы наличия нефти являются весьма впечатляющими и предоставляют гораздо лучшую возможность быстро разбогатеть, чем с помощью любых других законных капиталовложений. А поскольку есть 50'Ъ-ные шансы найти нефть, тоне следует ли немедленно снять все свои сбережения, нанять буровую установку и приступить к бурению скважины в кухне таких терминов может возникнуть путаница с терминами теории вероятностей, поэтому в настоящей книге такие термины не используются и речь идет просто о массе. Причина, по которой применяется аналогия с объектом, обладающим массой, состоит в том, что степень доверия может рассматриваться как величина, которую можно перемещать, дробить и комбинировать. Иногда удобно также рассматривать объект, обладающий массой, как состоящий из мягкой глины, что дает возможность удалять и снова прилеплять части этого объекта. Фундаментальное различие между теорией Демпстера — Шефера и теорией вероятностей состоит в том, что в этих теориях понятие незнания трактуется поразному. Как было описано в главе 4, согласно теории вероятностей рассматриваемая вероятность должна подразделяться на равные части даже в случае незнания. Например, если отсутствуют априорные знания, то мы обязаны исходить из предположения, что вероятность Р каждого возможного случая определяется следующей формулой, где N — количество возможных случаев 5.4. Теория Демпстера — Шефера Если следовать той же линии рассуждений, то применение принципа безразличия и теории вероятностей позволяет прийти к выводу о наличии Ъ- ных шансов найти под своим домом не только то, что перечислено ниже, но и все, что можно себе представить: алмазы сокровища пиратов меховые шубы зеленый сыр ваше очередное домашнее задание (Нов действительности вам, возможно, удастся разбогатеть, просто отправившись на телевидение и сообщив всеми каждому, что они могут стать богатыми, отправив вам 9,95 доллара за вашу книгу по теории вероятностей. В таком подходе к трактовке незнания также состоит одно из лучших оправданий для тех, кто не любит чистить зубы. А если вы не знаете, что находится там, где вас нетто у вас всегда имеются 50'Ъ-ные шансы стать богатым, обнаружив в том месте коечто ценное) Но даже если принцип безразличия не используется, следующее ограничение принудительно диктует необходимость присваивания вероятности отрицанию гипотезы и при отсутствии свидетельства, относящегося к отрицанию Р(Н) + Р(Н') = 1 Как было описано в разделе 5.3, такое предположение не совсем приемлемо по отношению к степеням доверия многих типов, например, касающихся медицинских знаний. Но теория вероятностей требует, чтобы свидетельство, которое не обосновывает гипотезу, опровергало ее. С другой стороны, теория Демпстера — Шефера не вынуждает назначать степень доверия незнанию или опровержению гипотезы. Вместо этого масса присваивается только тем подмножествам среды, которым желательно назначить некоторую степень доверия. Вся степень доверия, не присвоенная конкретному подмножеству, рассматривается как степень отсутствия доверия (поили степень нехватки доверия (nonbelief), и связывается со средой О. А степень доверия, которая опровергает гипотезу, представляет собой степень недоверия (disbelief), которую не следует путать со степенью отсутствия доверия. Например, предположим, что некоторый датчик, такой как датчик системы опознавания "свой — чужой" (Identification Friend or Foe — не получает ответа от радиомаяка-ответчика самолета. Работа системы опознавания "свой — чужой" основана на использовании радиопередатчика/приемника, который передает радиограмму на самолет и принимает ответ. Если самолет относится к собственному воздушному флоту (является "своим"), его радиомаяк-ответчик должен отреагировать на радиограмму, отправив в ответ идентификационный код. Самолеты Глава 5. Нестрогие рассуждения которые не отвечают, по умолчанию рассматриваются как "чужие. Но самолет может не ответить на сигналы системы опознавания "свой — чужой" по многим причинам, в частности, описанным ниже. Неисправность в системе опознавания "свой — чужой. Неисправность в радиомаяке-ответчике самолета. ° Отсутствие на самолете системы опознавания "свой — чужой. Исчезновение сигнала опознавания "свой — чужой" в помехах. ° Получение приказа соблюдать режим радиомолчания. Предположим, что неудачная попытка системы опознавания "свой — чужой" получить ответ указывает на наличие степени доверия 0.7 к свидетельству, что рассматриваемый самолет является "чужим, причем как "чужие" самолеты рассматриваются только бомбардировщики и истребители. Таким образом, присваивание массы подмножеству В, осуществляется последующей формуле, в которой т1 обозначает первое свидетельство датчика опознавания "свой чужой т1((В,F)) = 0.7 Остальная часть степени доверия присваивается среде, О, как степень отсутствия доверия т) = 1 — 0.7 = 0.3 P(hostile) = 0.7 Р(поп-hostile) = 1 — 0.7 = Согласно теории вероятностей, если степень доверия к гипотезе, что самолет является "чужим, равна 0.7, то степень недоверия тому, что он "чужой, должна быть равна 0.3. А в теории Демпстера — Шефера значение 0.3 рассматривается не как степень недоверия, а как степень отсутствия доверия к среде, выраженная в виде т. Это означает, что ни доверие, ни недоверие к свидетельству не имеют степень 0.3. Мы доверяем гипотезе, что рассматриваемый самолет является "чужим, в степени 0.7 и резервируем суждение, соответствующее степени, за недоверием и дополнительным доверием к гипотезе, что самолет "чужой. Очень важно понимать, что присваивание значения 0.3 среде 0 не представляет собой Каждое подмножество в степенном множестве среды, имеющее массу больше О, рассматривается как фокальный элемент. Термин "фокальный элемент" применяется в связи стем, что подмножество Х, такое что т(Х) ) О, представляет собой элемент степенного множества, в котором фокусируется (или концентрируется) доступное свидетельство. В этом теория Демпстера — Шефера существенно отличается от теории вероятностей, в которой было бы принято следующее предположение 421 5.4. Теория Демпстера — Шефера присваивание какого- либо значения другим подмножествам множества О, даже несмотря на то, что в число этих подмножеств входят подмножества, охватывающие разные варианты появления "чужих" самолетов, (В, F), (В) и (F). Возвратившись к примеру с учащимся, который рассматривался в последнем разделе, отметим, что присваивание m(getting an 'Ане означает автоматически применение такого присваивания an 'А' and not graduating) = 0.3 если обеим этим массам небыли специально присвоены значения. Как показано в табл, применение понятия массы обеспечивает намного большую свободу выбора по сравнению с понятием вероятности. Таблица. Сравнение возможностей теории Демпстера — Шефера (в которой применяется понятие массы) и теории вероятностей (в которой применяется понятие вероятностей) Теория вероятностей Теория Демпстера — Шефера Значение т) необязательно должно быть равно 1 ) Р i P(X) < P(Y) Если Х C то требование о соблюдении равенства т(Х) = m(Y) не является обязательным Не требуется наличия связи между т(Х) и т(Х') |