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

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

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

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

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

ФормализацияПравить

Пусть $X$$X$  — универсальное множество, набор всех рассматриваемых утверждений. Показательное множество, $P(X)$$P(X)$ , — совокупность всех подмножеств множества $X$$X$ , включая пустое множество $\mathrm{\varnothing <!--\; \varnothing \; -->}$$\emptyset$ . Например, если:

$X=\left\{a,b\right\}$$X=\left\{a,b\right\}$ 

то

$P(X)=\left\{\mathrm{\varnothing <!--\; \varnothing \; -->},\left\{a\right\},\left\{b\right\},X\right\}$$P(X)=\left\{\emptyset ,\left\{a\right\},\left\{b\right\},X\right\}$ 

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

$m(\mathrm{\varnothing <!--\; \varnothing \; -->})=0$$m(\emptyset )=0$ 

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

$1=\underset{A\in <!--\; \in \; -->P(X)}{\sum <!--\; \sum \; -->}m(A)$$1=\sum _{A\in P(X)}m(A)$ 

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

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

$bel(A)\le <!--\; \le \; -->P(A)\le <!--\; \le \; -->pl(A)$$bel(A)\leq P(A)\leq pl(A)$ 

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

$bel(A)=\underset{B\mid <!--\; \mid \; -->B\subseteq <!--\; \subseteq \; -->A}{\sum <!--\; \sum \; -->}m(B)$$bel(A)=\sum _{B\mid B\subseteq A}m(B)$ 

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

$pl(A)=\underset{B\mid <!--\; \mid \; -->B\cap <!--\; \cap \; -->A\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}}{\sum <!--\; \sum \; -->}m(B)$$pl(A)=\sum _{B\mid B\cap A\neq \emptyset }m(B)$ 

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

$pl(A)=1-<!--\; -\; -->bel(\stackrel{¯<!--\; ¯\; -->}{A})$$pl(A)=1-bel({\overline {A}})$ 

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

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

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

$m_{1,2}(\mathrm{\varnothing <!--\; \varnothing \; -->})=0$$m_{1,2}(\emptyset )=0$ 

$m_{1,2}(A)=\frac{1}{1-<!--\; -\; -->K}\underset{B\cap <!--\; \cap \; -->C=A\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}}{\sum <!--\; \sum \; -->}{m}_1(B)m_2(C)$$m_{1,2}(A)={\frac {1}{1-K}}\sum _{B\cap C=A\neq \emptyset }m_{1}(B)m_{2}(C)$ 

где:

$K=\underset{B\cap <!--\; \cap \; -->C=\mathrm{\varnothing <!--\; \varnothing \; -->}}{\sum <!--\; \sum \; -->}{m}_1(B)m_2(C)$$K=\sum _{B\cap C=\emptyset }m_{1}(B)m_{2}(C)$ 

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

ДискуссияПравить

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

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

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

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

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

Правдоподобие = 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; 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. 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. 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. 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.

См. такжеПравить

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