Размещено на http://www.allbest.ru/

1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Кафедра KТ и ВМ

Реферат

Тема: “Меры доверия и правдоподобия в теории Демпстера-Шеффера”

Выполнил:

студент группы 4-IС-27

Куделя С.В.

Проверил:

Ст. преподаватель

Виктор Исаакович

Днепропетровск 2010

Введение

очевидность вероятность доверие правдоподобие

Демпстера-Шеффера теория - это математическая теория очевидностей (свидетельств), основанная на функции доверия (belief functions) и функции правдоподобия (plausible reasoning), которые используются, чтобы скомбинировать отдельные части информации (свидетельства) для вычисления вероятности события.

Теория была развита Артуром П. Демпстером (Arthur P. Dempster) и Гленном Шеффером (Glenn Shafer).

I. Меры доверия и правдоподобия в теории Демпстера-Шеффера

Теория обоснования Демпстера-Шеффера, рассматривает множества предположений и ставит в соответствие каждому из них вероятностный интервал доверия (правдоподобия), которому должна принадлежать степень уверенности в каждом предположении. Мера доверия обозначается bel(p) и изменяется от нуля, что указывает на отсутствие свидетельств в пользу множества предположений, до единицы, означающей определенность. Мера правдоподобности предположения р - pl(p) определяется следующим образом:

pl(p) = 1 - bel(not(p)).

Таким образом, правдоподобие также изменяется от нуля до единицы и вычисляется на основе меры доверия предположению not(p). Если not(p) вполне обоснованно, то bel(not(p))= 1, a pl(p)=0. Единственно возможным значением для bel(p) также является нуль.

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

Определения

Пусть X - универсальное множество, набор всех рассматриваемых утверждений. Показательное множество, P(X), совокупность всех подмножеств множества X, включая пустое множество,. Например, если:

X={a,b}

то P(X)={ ,{a}, {b},X}

По определению, масса пустого множества - ноль: m()=0.

Массы оставшихся элементов показательного множества нормированы на единичную сумму:

Масса m(A) элемента показательного множества, A, выражает соотношение всех уместных и доступных свидетельств, которые поддерживают утверждение, что определенный элемент X принадлежит A, но не принадлежит ни одному подмножеству A. Величина m(A) относится только к множеству A и не создает никаких дополнительных утверждений о других подмножествах A, каждое из которых, по определению, имеет свою собственную массу.

Исходя из приписанных масс, могут быть определены верхняя и нижняя границы интервала возможностей. Этот интервал содержит точную величину вероятности рассматриваемого подмножества (в классическом смысле), и ограничена двумя неаддитивными непрерывными мерами, называемыми доверие (belief) (or поддержка (support)) и правдоподобие (plausibility):

Доверие bel(A) к множеству A определяется как сумма всех масс собственных подмножеств рассматриваемого множества:

Правдоподобие pl(A) - это сумма масс всех множеств , пересекающихся с рассматриваемым множеством A:

Эти две меры соотносятся между собой следующим образом:

Из выше написанного следует, что достаточно знать хотя бы одну из мер (массу, доверие или правдоподобие), чтобы вычислить оставшиеся две.

Объединение двух независимых множеств приписанных масс.

Исходное правило объединения известно, как Dempster's rule of combination. Это правило придает особое значение согласию между многочисленными источниками и игнорирует все конфликтующие свидетельства с помощью нормализации. Правомерность использования этого правила подвергается серьёзным сомнениям в случае значительных несоответствий между источниками информации.

Собственно, объединение (называемое присоединенная масса) вычисляется из двух множеств масс m₁ и m₂ следующим образом:

где:

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

II. Примеры

Теория Демпстера - Шафера позволяет интерпретировать доверие и правдоподобие как границы интервала возможного значения истинности гипотезы: доверие ? какая-то мера истинности ? правдоподобие.

Полагается, что:

Доверие к гипотезе = {сумма масс свидетельств, однозначно поддерживающих гипотезу}.

Правдоподобие = 1 ? {сумма масс всех свидетельств, противоречащих гипотезе}.

1. Рассмотрим субъективные вероятности правдивости свидетельств моей подруги Мелиссы. Вероятность того, что ей можно верить, составляет 0,9, а того, что верить нельзя, - 0,1. Предположим, Мелисса говорит, что мой компьютер сломался. Это утверждение истинно, если Мелиссе можно верить, но оно не обязательно ложно, если ей верить нельзя. Таким образом, утверждение Мелиссы, что мой компьютер сломался, обосновывается с достоверностью 0,9, а то, что он исправен - с достоверностью 0,0. Достоверность 0,0 не означает уверенности в том, что компьютер не сломался, как это означала бы вероятность 0,0. Это просто означает, что утверждение Мелиссы не дает причин верить, что мой компьютер не сломался. Мера правдоподобия p1 в этой ситуации равна:

р1{компьютер_сломался) =1 - [bel(not(компьютер_cломался)] -0,0,

или 1,0, и моя мера доверия Мелиссе есть [0,9; 1,0]. Заметим, что еще нет основания считать, что мой компьютер не сломался.

Рассмотрим правило Демпстера для объединения свидетельств.

Допустим, мой друг Билл также говорит, что мой компьютер сломался. Предположим, вероятность того, что Биллу можно верить, составляет 0,8, а что верить нельзя - 0,2. Я также должен предположить, что утверждения Билла и Мелиссы о моем компьютере независимы друг от друга, т.е. они вызваны разными причинами. Событие "Билл заслуживает доверия" также должно быть независимо от события, определяющего степень доверия Мелиссе. Вероятность правдивости и Билла и Мелиссы равна произведению их вероятностей - 0,72; вероятность неправдивости обоих - 0,02. Вероятность того, что верить можно по крайней мере одному из них - 1-0,02 = 0,98. Поскольку оба они говорят, что мой компьютер сломался, и вероятность того, что по крайней мере один из них заслуживает доверия, равна 0,98, можно установить степень достоверности события поломки компьютера [0,98; 1,0].

Предположим, Билл и Мелисса расходятся в том, что мой компьютер сломался: Мелисса утверждает, что он сломался, а Билл говорит, что нет. В этом случае они оба одновременно не могут говорить правду и не могут оба вызывать доверие. Либо обоим им нельзя верить, либо нельзя верить одному из них. Априорная вероятность того, что можно верить лишь Мелиссе, составляет 0,9*(1 - 0,8) = 0,18, а того, что верить можно только Биллу, - 0,8*(1 - 0,9) = 0,08, а того, что ни одному из них верить нельзя, - 0,2*0,1 = 0,02. Имея вероятность того, что по крайней мере одному из друзей верить нельзя, (0,18 + 0,08 + 0,02) = 0,28, можно вычислить апостериорную вероятность того, что верить можно лишь Мелиссе, и мой компьютер сломан - 0,18/0,28 = 0,643; или апостериорную вероятность того, что прав лишь Билл, и мой компьютер исправен - 0,08/0,28 = 0,286.

При этом было использовано правило Демпстера для объединения свидетельств. После заявления Мелиссы и Билла о том, что компьютер сломан, мы рассмотрели три гипотетические ситуации, связанные с поломкой: Биллу и Мелиссе можно верить; Биллу можно верить, а Мелиссе нет; Мелиссе можно верить, а Биллу нет. Доверие результату анализа возможных гипотетических сценариев составила 0,98. При втором использовании правила Демпстера свидетельства расходились. Снова были проанализированы все возможные сценарии. Исключалась единственная ситуация, связанная с тем, что верить можно обоим. Таким образом, либо Мелиссе можно верить, а Биллу нет; либо можно верить Биллу, а не Мелиссе; либо нельзя верить никому из них. Суммарная достоверность поломки составила 0,64. Достоверность того, что компьютер не сломан (согласно мнению Билла), - 0,286. Поскольку правдоподобие поломки составляет 1 -bel(not(поломка)) - 0,714, мера доверия принадлежит интервалу [0,28; 0,714].

Используя правило Демпстера, можно получить меру доверия для одной задачи (Был ли компьютер сломан?) из вероятности для другой (Является ли свидетельство надежным?). Для применения правила необходимо предположить, что задачи, для которых известны вероятности, независимы, но эта независимость лишь априорная. Она исчезает, когда возникает конфликт между различными источниками обоснования.

Использование подхода Демпстера-Шеффера в каждой ситуации приводит к решению двух связанных проблем. Во-первых, мы разделяем неопределенность ситуации на априорно независимые части. Во-вторых, применяем правило Демпстера. Эти две задачи взаимосвязаны: предположим опять-таки, что Билл и Мелисса независимо друг от друга сказали, что они были уверены в том, что мой компьютер сломан. Предположим также, что я вызвал мастера для проверки компьютера, и что оба (и Билл, и Мелисса) были свидетелями этого. Из-за этого общего события мы не можем больше сравнивать степени доверия. Однако, явно учитывая возможность приглашения мастера, можно получить три независимых атомарных обоснования: правдивость Мелиссы, правдивость Билла и основание для присутствия мастера, которые можно затем объединить с помощью правила Демпстера.

2. Например, пусть у нас есть гипотеза «кот в коробке мертв.» Если для нее доверие 0.5 и правдоподобие 0.8, то это значит, что у нас есть свидетельства (общей массой 0.5) однозначно указывающие, что кот мертв; но имеются и свидетельстве (общей массой 0.2), однозначно указывающие, что кот жив (правдоподобие «кот мертв» = 1 - 0.2 = 0.8). Оставшаяся масса (дополняющая 0.5 и 0.2 до 1.0) - она же зазор между правдоподобием 0.8 и доверием 0.5 - соответствует «неопределенности» ("универсальной" гипотезе), наличию свидетельств, что кот в коробке точно есть, но не говорящих ничего о том, жив он, или мертв.

Итого, интервал [0.5; 0.8] характеризует неопределенность истинности исходной гипотезы исходя из имеющихся свидетельств.

Масса "нулевой" гипотезы устанавливается равной 0 по определению (она соответствует случаям «нет решения» или неразрешимому противоречию между свидетельствами). Эти приводит к тому, что доверие к "нулевой" гипотезе равно 0, а правдоподобие "универсальной" 1. Так как масса "универсальной" гипотезы вычисляется из масс гипотез "Жив" и "Мертв", то её доверие автоматически получается равно 1, а правдоподобие "нулевой" гипотезы 0.

3. Возьмем более сложный пример, демонстрирующий особенности доверия и правдоподобия. Допустим, мы с помощью набора детекторов регистрируем единичный далекий сигнальный огонь, который может быть одного из трех цветов (красный, желтый, либо зеленый):

где, например:

Доверие (Красный или Желтый) = Масса ("Нулевая" гипотеза) + Масса (Красный) + Масса (Желтый) + Масса (Красный или Желтый) = 0 + 0.35 + 0.25 + 0.06 = 0.66

Правдоподобие (Красный или Желтый) = 1 - Доверие (отрицание "Красный или Желтый") = 1 - Доверие (Зеленый) = 1 - Масса ("Нулевая" гипотеза) - Масса (Зеленый) = 1 - 0 - 0.15 = 0.85

События данного набора не должны рассматриваться как пересечение событий в вероятностном пространстве, так как они заданы в пространстве масс. Правильнее рассматривать событие «Красный или Желтый» как объединение событий «Красный» и «Желтый», и (см. аксиомы теории вероятностей) P(Красный или Желтый) ? P(Желтый), и P(Универсальная)=1, где «Универсальная» гипотеза соответствует «Красный», «Желтый» или «Зеленый». В ТДШ, масса «Универсальной» гипотезы соответствует части свидетельств, которые не могут быть отнесены к какой-либо другой гипотезе; то есть свидетельства, которые утверждают, что какой-то сигнал был, но совершенно не говорят о его цвете.

В этом примере, свидетельствам «Красный или Зеленый» приписана масса 0.05. Такие свидетельства могли бы быть получены, например, от людей со слепотой к Красному/Зеленому. ТДШ позволяет нам взвешено учесть такие свидетельства.

III. Отличие теории Демпстера-Шеффера от теории вероятностей

Теория вероятности рассматривает отдельные высказывания и использует единственную числовую оценку степени достоверности - вероятность.

Теория Демпстера-Шеффера решает проблему измерения достоверности, делая коренное различие между отсутствием уверенности и незнанием. В теории вероятностей мы вынуждены выражать степень нашего знания о гипотезе h единственным числом P(h).

В основу теории свидетельств Демпстера-Шеффера положены две функции: функция доверия (belief functions) и функция правдоподобия (plausible reasoning), которые используются для комбинирования частей информации (свидетельств) при вычислении вероятности события;

Для любого множества U, величина необходимости определяется следующим образом:

В данной формуле обозначает дополнение к Uhttp://images.wikia.com/wikitex/images/e/e9/e94/35e91699ecb58b1f8cb9fbb8990961.png, это элементы . которые не принадлежат .

для любого U и

Заметим, что, в отличие от теории вероятностей, возможность не двойственна. То есть, для любого события , мы имеем только неравенство:

Однако следующее двойственное правило остается в силе:

Для любого события U, либо , либо nec(U)=0

Следовательно, доверие к событию может быть представлено числом и битом. Возможность может рассматриваться как верхняя вероятность: любое распределение возможности определяет единственное множество допустимых распределений вероятности по правилу:

.

Размещено на Allbest.ru