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

Демпстера-Шафера теория — математическая теория очевидностей (свидетельств) ([SH76]), основанная на функции доверия (belief functions) и функции правдоподобия (plausible reasoning), которые используются, чтобы скомбинировать отдельные части информации (свидетельства) для вычисления вероятности события. Теория была развита Артуром П. Демпстером (Arthur P. Dempster) и Гленном Шафером (Glenn Shafer).

Рассмотрим двух возможных игроков

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

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

Формализация

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

<math>X = \left \{ a, b \right \}</math>

то

<math>P(X) = \left \{ \emptyset, \left \{ a \right \}, \left \{ b \right \}, X \right \}</math>

По определению, масса пустого множества — ноль:

<math>m(\emptyset) = 0</math>

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

<math>1 = \sum_{A \in P(X)} m(A)</math>

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

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

<math>bel(A) \le P(A) \le pl(A)</math>

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

<math>bel(A) = \sum_{B \mid B \subseteq A} m(B)</math>

Правдоподобие <math>pl(A)</math> — это сумма масс всех множеств <math>B</math> пересекающихся с рассматриваемым множеством <math>A</math>:

<math>pl(A) = \sum_{B \mid B \cap A \ne \emptyset} m(B)</math>

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

<math>pl(A) = 1 - bel(\overline{A})</math>

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

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

Собственно, объединение (называемое присоединённая масса) вычисляется из двух множеств масс <math>m_1</math> и <math>m_2</math> следующим образом:

<math>m_{1,2}(\emptyset) = 0</math>

<math>m_{1,2}(A) = \frac {1}{1 - K} \sum_{B \cap C = A \ne \emptyset} m_1(B) m_2(C)</math>

где:

<math>K = \sum_{B \cap C = \emptyset} m_1(B) m_2(C)</math>

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

Дискуссия

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

Шаферовский подход позволяет интерпретировать доверие и правдоподобие как границы интервала возможного значения истинности гипотезы:

доверие ≤ какая-то мера истинности ≤ правдоподобие.

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

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

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

Например, пусть у нас есть гипотеза «кот в коробке мертв.» Если для неё доверие 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	0
Жив	0.2	0.2	0.5
Мёртв	0.5	0.5	0.8
Универсальная (то ли жив, то ли мертв)	0.3	1.0	1.0

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

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

Гипотеза	Масса	Доверие	Правдоподобие
Нулевая	0	0	0
Красный	0.35	0.35	0.56
Жёлтый	0.25	0.25	0.45
Зелёный	0.15	0.15	0.34
Красный или Жёлтый	0.06	0.66	0.85
Красный или Зелёный	0.05	0.55	0.75
Жёлтый или Зелёный	0.04	0.44	0.65
Универсальная	0.10	1.00	1.00

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

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

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

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

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

Литература

• [DE68] Dempster, Arthur P.; A generalization of Bayesian inference, Journal of the Royal Statistical Society, Series B, Vol. 30, pp. 205–247, 1968
• [SH76] Shafer, Glenn; A Mathematical Theory of Evidence, Princeton University Press, 1976
• [SH02] Shafer, Glenn; [www.glennshafer.com/assets/downloads/articles/article48.pdf Dempster-Shafer theory], 2002
• Dempster, A. P. Upper and lower probabilities induced by a multivalued mapping (англ.) // The Annals of Mathematical Statistics. — 1967. — Vol. 38, no. 2. — P. 325–339. — DOI:10.1214/aoms/1177698950.
• Fine, Terrence L. [projecteuclid.org/euclid.bams/1183538896 Review: Glenn Shafer, A mathematical theory of evidence] (англ.) // Bull. Amer. Math. Soc.. — 1977. — Vol. 83, no. 4. — P. 667–672. — DOI:10.1090/s0002-9904-1977-14338-3.
• Jøsang, A., and Simon, P. [onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00421.x/pdf Dempster's Rule as Seen by Little Colored Balls] (англ.) // Computational Intelligence. — 2012. — Vol. 28, no. 4. — P. 453–474. — DOI:10.1111/j.1467-8640.2012.00421.x.
• Jøsang, A., Diaz, J., and Rifqi, M. [www.sciencedirect.com/science/article/pii/S156625350900044X Cumulative and averaging fusion of beliefs] (англ.) // Information Fusion. — 2010. — Vol. 11, no. 2. — P. 192–200. — DOI:10.1016/j.inffus.2009.05.005.
• Pearl, J. On Probability Intervals (англ.) // International Journal of Approximate Reasoning. — 1988. — Vol. 2, no. 3. — P. 211–216. — DOI:10.1016/0888-613X(88)90117-X.
• Pearl, J. Reasoning with Belief Functions: An Analysis of Compatibility (англ.) // The International Journal of Approximate Reasoning. — 1990. — Vol. 4, no. 5/6. — P. 363–389. — DOI:10.1016/0888-613X(90)90013-R.

См. также

• Теория возможностей
• Теория вероятностей
• Теорема Байеса
• Байесовская сеть доверия
• Нечёткая логика

Отрывок, характеризующий Теория Демпстера — Шафера

– Нет, он не дурак, – обиженно и серьезно сказала Наташа.
– Ну так что ж ты хочешь? Вы нынче ведь все влюблены. Ну, влюблена, так выходи за него замуж! – сердито смеясь, проговорила графиня. – С Богом!
– Нет, мама, я не влюблена в него, должно быть не влюблена в него.
– Ну, так так и скажи ему.
– Мама, вы сердитесь? Вы не сердитесь, голубушка, ну в чем же я виновата?
– Нет, да что же, мой друг? Хочешь, я пойду скажу ему, – сказала графиня, улыбаясь.
– Нет, я сама, только научите. Вам всё легко, – прибавила она, отвечая на ее улыбку. – А коли бы видели вы, как он мне это сказал! Ведь я знаю, что он не хотел этого сказать, да уж нечаянно сказал.
– Ну всё таки надо отказать.
– Нет, не надо. Мне так его жалко! Он такой милый.
– Ну, так прими предложение. И то пора замуж итти, – сердито и насмешливо сказала мать.
– Нет, мама, мне так жалко его. Я не знаю, как я скажу.
– Да тебе и нечего говорить, я сама скажу, – сказала графиня, возмущенная тем, что осмелились смотреть, как на большую, на эту маленькую Наташу.
– Нет, ни за что, я сама, а вы слушайте у двери, – и Наташа побежала через гостиную в залу, где на том же стуле, у клавикорд, закрыв лицо руками, сидел Денисов. Он вскочил на звук ее легких шагов.
– Натали, – сказал он, быстрыми шагами подходя к ней, – решайте мою судьбу. Она в ваших руках!
– Василий Дмитрич, мне вас так жалко!… Нет, но вы такой славный… но не надо… это… а так я вас всегда буду любить.
Денисов нагнулся над ее рукою, и она услыхала странные, непонятные для нее звуки. Она поцеловала его в черную, спутанную, курчавую голову. В это время послышался поспешный шум платья графини. Она подошла к ним.
– Василий Дмитрич, я благодарю вас за честь, – сказала графиня смущенным голосом, но который казался строгим Денисову, – но моя дочь так молода, и я думала, что вы, как друг моего сына, обратитесь прежде ко мне. В таком случае вы не поставили бы меня в необходимость отказа.
– Г'афиня, – сказал Денисов с опущенными глазами и виноватым видом, хотел сказать что то еще и запнулся.
Наташа не могла спокойно видеть его таким жалким. Она начала громко всхлипывать.
– Г'афиня, я виноват перед вами, – продолжал Денисов прерывающимся голосом, – но знайте, что я так боготво'ю вашу дочь и всё ваше семейство, что две жизни отдам… – Он посмотрел на графиню и, заметив ее строгое лицо… – Ну п'ощайте, г'афиня, – сказал он, поцеловал ее руку и, не взглянув на Наташу, быстрыми, решительными шагами вышел из комнаты.

На другой день Ростов проводил Денисова, который не хотел более ни одного дня оставаться в Москве. Денисова провожали у цыган все его московские приятели, и он не помнил, как его уложили в сани и как везли первые три станции.
После отъезда Денисова, Ростов, дожидаясь денег, которые не вдруг мог собрать старый граф, провел еще две недели в Москве, не выезжая из дому, и преимущественно в комнате барышень.
Соня была к нему нежнее и преданнее чем прежде. Она, казалось, хотела показать ему, что его проигрыш был подвиг, за который она теперь еще больше любит его; но Николай теперь считал себя недостойным ее.
Он исписал альбомы девочек стихами и нотами, и не простившись ни с кем из своих знакомых, отослав наконец все 43 тысячи и получив росписку Долохова, уехал в конце ноября догонять полк, который уже был в Польше.



После своего объяснения с женой, Пьер поехал в Петербург. В Торжке на cтанции не было лошадей, или не хотел их смотритель. Пьер должен был ждать. Он не раздеваясь лег на кожаный диван перед круглым столом, положил на этот стол свои большие ноги в теплых сапогах и задумался.
– Прикажете чемоданы внести? Постель постелить, чаю прикажете? – спрашивал камердинер.
Пьер не отвечал, потому что ничего не слыхал и не видел. Он задумался еще на прошлой станции и всё продолжал думать о том же – о столь важном, что он не обращал никакого .внимания на то, что происходило вокруг него. Его не только не интересовало то, что он позже или раньше приедет в Петербург, или то, что будет или не будет ему места отдохнуть на этой станции, но всё равно было в сравнении с теми мыслями, которые его занимали теперь, пробудет ли он несколько часов или всю жизнь на этой станции.
Смотритель, смотрительша, камердинер, баба с торжковским шитьем заходили в комнату, предлагая свои услуги. Пьер, не переменяя своего положения задранных ног, смотрел на них через очки, и не понимал, что им может быть нужно и каким образом все они могли жить, не разрешив тех вопросов, которые занимали его. А его занимали всё одни и те же вопросы с самого того дня, как он после дуэли вернулся из Сокольников и провел первую, мучительную, бессонную ночь; только теперь в уединении путешествия, они с особенной силой овладели им. О чем бы он ни начинал думать, он возвращался к одним и тем же вопросам, которых он не мог разрешить, и не мог перестать задавать себе. Как будто в голове его свернулся тот главный винт, на котором держалась вся его жизнь. Винт не входил дальше, не выходил вон, а вертелся, ничего не захватывая, всё на том же нарезе, и нельзя было перестать вертеть его.
Вошел смотритель и униженно стал просить его сиятельство подождать только два часика, после которых он для его сиятельства (что будет, то будет) даст курьерских. Смотритель очевидно врал и хотел только получить с проезжего лишние деньги. «Дурно ли это было или хорошо?», спрашивал себя Пьер. «Для меня хорошо, для другого проезжающего дурно, а для него самого неизбежно, потому что ему есть нечего: он говорил, что его прибил за это офицер. А офицер прибил за то, что ему ехать надо было скорее. А я стрелял в Долохова за то, что я счел себя оскорбленным, а Людовика XVI казнили за то, что его считали преступником, а через год убили тех, кто его казнил, тоже за что то. Что дурно? Что хорошо? Что надо любить, что ненавидеть? Для чего жить, и что такое я? Что такое жизнь, что смерть? Какая сила управляет всем?», спрашивал он себя. И не было ответа ни на один из этих вопросов, кроме одного, не логического ответа, вовсе не на эти вопросы. Ответ этот был: «умрешь – всё кончится. Умрешь и всё узнаешь, или перестанешь спрашивать». Но и умереть было страшно.
Торжковская торговка визгливым голосом предлагала свой товар и в особенности козловые туфли. «У меня сотни рублей, которых мне некуда деть, а она в прорванной шубе стоит и робко смотрит на меня, – думал Пьер. И зачем нужны эти деньги? Точно на один волос могут прибавить ей счастья, спокойствия души, эти деньги? Разве может что нибудь в мире сделать ее и меня менее подверженными злу и смерти? Смерть, которая всё кончит и которая должна притти нынче или завтра – всё равно через мгновение, в сравнении с вечностью». И он опять нажимал на ничего не захватывающий винт, и винт всё так же вертелся на одном и том же месте.
Слуга его подал ему разрезанную до половины книгу романа в письмах m mе Suza. [мадам Сюза.] Он стал читать о страданиях и добродетельной борьбе какой то Аmelie de Mansfeld. [Амалии Мансфельд.] «И зачем она боролась против своего соблазнителя, думал он, – когда она любила его? Не мог Бог вложить в ее душу стремления, противного Его воле. Моя бывшая жена не боролась и, может быть, она была права. Ничего не найдено, опять говорил себе Пьер, ничего не придумано. Знать мы можем только то, что ничего не знаем. И это высшая степень человеческой премудрости».
Всё в нем самом и вокруг него представлялось ему запутанным, бессмысленным и отвратительным. Но в этом самом отвращении ко всему окружающему Пьер находил своего рода раздражающее наслаждение.
– Осмелюсь просить ваше сиятельство потесниться крошечку, вот для них, – сказал смотритель, входя в комнату и вводя за собой другого, остановленного за недостатком лошадей проезжающего. Проезжающий был приземистый, ширококостый, желтый, морщинистый старик с седыми нависшими бровями над блестящими, неопределенного сероватого цвета, глазами.
Пьер снял ноги со стола, встал и перелег на приготовленную для него кровать, изредка поглядывая на вошедшего, который с угрюмо усталым видом, не глядя на Пьера, тяжело раздевался с помощью слуги. Оставшись в заношенном крытом нанкой тулупчике и в валеных сапогах на худых костлявых ногах, проезжий сел на диван, прислонив к спинке свою очень большую и широкую в висках, коротко обстриженную голову и взглянул на Безухого. Строгое, умное и проницательное выражение этого взгляда поразило Пьера. Ему захотелось заговорить с проезжающим, но когда он собрался обратиться к нему с вопросом о дороге, проезжающий уже закрыл глаза и сложив сморщенные старые руки, на пальце одной из которых был большой чугунный перстень с изображением Адамовой головы, неподвижно сидел, или отдыхая, или о чем то глубокомысленно и спокойно размышляя, как показалось Пьеру. Слуга проезжающего был весь покрытый морщинами, тоже желтый старичек, без усов и бороды, которые видимо не были сбриты, а никогда и не росли у него. Поворотливый старичек слуга разбирал погребец, приготовлял чайный стол, и принес кипящий самовар. Когда всё было готово, проезжающий открыл глаза, придвинулся к столу и налив себе один стакан чаю, налил другой безбородому старичку и подал ему. Пьер начинал чувствовать беспокойство и необходимость, и даже неизбежность вступления в разговор с этим проезжающим.
Слуга принес назад свой пустой, перевернутый стакан с недокусанным кусочком сахара и спросил, не нужно ли чего.