Dempster–Shafer theory

本文參考書Wikipedia中的 Dempster-Shafer thoery 原文鏈接：點擊打開鏈接 同時還參考了浙江大學(xué)計算機學(xué)院人工智能系?徐從富 教授的《人工智能》課件。
在這里特別感謝！

一、 DS證據(jù)理論概述

核心： Dempster合成規(guī)則——將多個主體（可以是不同的人的預(yù)測、不同的傳感器的數(shù)據(jù)、不同的分類器的輸出結(jié)果等等）相融合
優(yōu)點： 1、所需要的先驗數(shù)據(jù)比概率推理理論中更直觀、更容易獲得 （不知道為什么）；滿足比Bayes概率理論更弱的條件，即 “不必滿足概率可加性” 2、可以融合多種數(shù)據(jù)和知識（正如核心中所述） 3、具有直接表達 “不確定” 和 “不知道” 的能力，這些信息表示在mass函數(shù)中，并在證據(jù)合成過程中保留了這些信息（還沒有理解感受到）。
缺點： 1、證據(jù)必須是獨立的 2、證據(jù)合成規(guī)則沒有非常堅固的理論支持，其合理性和有效性還存在較大的爭議 3、計算上存在“指數(shù)爆炸問題” 4、在某些情況下得到的結(jié)果違背常理，如“Zadeh悖論”，具體見下面的例子

二、 DS證據(jù)理論基本概念

我們先來假設(shè)這樣一個情景，有一個傳感器探測一個很遠(yuǎn)處的一道光，這道光只能發(fā)出 {red, yellow, green}這三種中的一種光。傳感器對所探測的光做出分析，形成了一些假設(shè)這道光可能是{Null, Red, Yellow, Green, Red or Yellow, Red or Green, Yellow or Green, Any}，以及這些假設(shè)相應(yīng)的可能性（也就是說Mass）。那么，DS證據(jù)理論是干啥呢，我感覺就是根據(jù)這個傳感器提供的各個假設(shè)的信息，得到針對每一個假設(shè)的可信度區(qū)間。需要注意的是，這里的Red or Yellow并不是P(Red) + P(Yellow), 而是Red or Yellow 這一假設(shè)的概率（其實我也還沒太搞懂這之間的區(qū)別，只是感覺上應(yīng)該不一樣）。 這里先給出這一場景的所有信息表： Hypothesis Mass Belief Plausibility

Null	0	0	0
Red	0.35	0.35	0.56
Yellow	0.25	0.25	0.45
Green	0.15	0.15	0.34
Red or Yellow	0.06	0.66	0.85
Red or Green	0.05	0.55	0.75
Yellow or Green	0.04	0.44	0.65
Any	0.1	1.0	1.0

OK，根據(jù)上面的例子，我們就來定義一下DS證據(jù)理論中的基本概念。
1. 首先我們設(shè)X 全域（Universe）：也就是指的上面那道光可能發(fā)出的顏色，即X = {Red, Yellow, Green} ? 對于X 全域，我們一共可以有多少種假設(shè)呢？很顯然，就是?個啦 （包括空集），這個叫做識別框架，或者是假設(shè)空間。 ?? ? 比如說：?則? ? 對于我們的例子X?= {Red, Yellow, Green}，={Null, Red, Yellow, Green, Red or Yellow, Red or Green, Yellow or Green, Any}
2. DS證據(jù)理論針對識別框架中的每一個假設(shè)都分配了概率，我們稱為基本概率分配（BPA, Basic Probability Assignment）或者是基本置信分配 ? ? (BBA, Basic Belief Assignment )。這個分配函數(shù)我們稱為mass函數(shù)。 ?? ? 1）公式為：，每個假設(shè)的mass函數(shù)值（概率（probability）或者是置信度（belief）值）都在0和1之間； ?? ? 2）同時，空集的mass函數(shù)值為 0，即另外其他的假設(shè)mass值得和為1，即,A 為所包含的假設(shè)。 ? 3）其中，使得mass值大于0的假設(shè) A稱為焦元(Focal element) ?? ? 在我們上面的例子中，Column 2 即為mass函數(shù)針對各個假設(shè)的值，m(Null) = 0, m(Red) + m(Yellow) + m(Green) + ... + m(Any) = 1 根據(jù)該列我們可以得到滿足上面的定義。
3. 下面我們要根據(jù)mass函數(shù)來計算每一個假設(shè)的?信度函數(shù) (Belief function) 以及 似然函數(shù) （Plausibility function） ?? ? 得到的信度函數(shù)和似然函數(shù)就是這個假設(shè)A 的概率范圍了：
? 1）信度函數(shù)的定義如下： ? 該公式表示，對于假設(shè)A ，它的信度函數(shù)為所有真屬于 A 的假設(shè)，即 B ，的mass值的和。 ? 以上面的例子來講，A假設(shè)為 Red，那么它的 Bel?函數(shù)值就是0.35， 因為只有它本身是屬于假設(shè) A 。 ? 但是，如果假設(shè)A 為 Red or Yellow, 那么它的 Bel 函數(shù)值就不是0.06了， 而是 m(Null) + m(Red) + m(Yellow) + m(Red or Yellow) = 0 + ? 0.35 + 0.25 + 0.06 = 0.66
? 2) 似然函數(shù)的定義如下： ? ? ? ? ? ? ? ? ? ? ? ? ? 該公式表示，對于假設(shè)A ， 它的似然函數(shù)為所有與 A 相交不為空的假設(shè) B 的mass值的和。 ? 以上面的例子來講， 還是 A假設(shè)為 Red，那么它的 pl 函數(shù)值為 m(Red) + m(Red or Yellow) + m(Red or Green) + m(Any) = 0.35 + 0.06 + 0.05 + 0.1 =0.56
? 3） 信任區(qū)間 ? 根據(jù)上面的信度函數(shù)和似然函數(shù)，對于一個識別框架中的某個假設(shè)A ， 我們可以根據(jù)其基本概率分配的mass函數(shù)來計算 A 的 Bel(A) 及Pl(A)。那么，由信任函數(shù)與似然函數(shù)組成的閉區(qū)間[Bel(A),Pl(A)]則為假設(shè) A 的信任區(qū)間，表示對假設(shè) A 的確認(rèn)程度。 ? ? ? ? ? ? ? ? ? ? ??

三、 Dempster合成規(guī)則

前面所述的都是只有一個主體（subject）對一個識別框架預(yù)測。而Dempster合成規(guī)則正是用來將多個主體的輸出結(jié)果相結(jié)合的關(guān)鍵步驟。 兩個主體的mass函數(shù) m1 和 m2 有：

其中 ?? 等價于 ? ? ? ? ? ? ? ? ?

合成規(guī)則為兩個mass函數(shù) m1 和 m2, 對于假設(shè)A的合成結(jié)果等于兩個主體的假設(shè)中，所有相交為 A 的假設(shè)的mass函數(shù)值的乘積的和，再除以一個歸一化系數(shù) 1-K。歸一化系數(shù) 1-K 中的 K 的含義是證據(jù)之間的沖突（the conflict between the evidences, called conflict probability）(并不太明白為何能夠表現(xiàn)證據(jù)之間的沖突，從公式上來看就是兩個主體提供的證據(jù)不同的時候（B與C相交為了空集）的mass函數(shù)值乘積)。
舉個“栗子”： 一宗謀殺案有三個犯罪嫌疑人 U = {Peter, Paul, Mary}, 兩個目擊證人分別指證犯罪嫌疑人，得到兩個mass函數(shù) m1 和 m2.
1）根據(jù)上述公式，為了求得合成規(guī)則 m12?，我們先求歸一化系數(shù) 1-K 值
然后再求合成之后的每個假設(shè)的mass函數(shù)值 2）Peter的組合mass函數(shù)值
3）Paul的組合mass函數(shù)值
4）Mary的組合mass函數(shù)值

由此，我們得到了如上表所示的組合函數(shù) m12 。 根據(jù)得到的合成的mass函數(shù)，我們同樣能計算對于組合mass函數(shù)對于各個假設(shè)的信度函數(shù)以及似然函數(shù)。 ??

但是這一結(jié)果卻有悖于我們的常識，因為在兩個目擊證人指證的證據(jù)中，Paul是兇手的概率都不大，但是最終的結(jié)果卻直接指向了Paul。該例子就是“Zadeh悖論”。
若修改“Zadeh悖論”中的部分?jǐn)?shù)據(jù)，如下表：
重新計算新的組合mass函數(shù) 1）還是先計算歸一化系數(shù) 1-K 這次計算采用簡便方法，用相交為空的公式來做（及上面的等價公式）
2）計算Peter的組合mass函數(shù)
3）計算Paul的組合mass函數(shù)
4）計算Mary的組合mass函數(shù)
5)計算{Peter, Paul, Mary}的組合mass函數(shù)
根據(jù)這次的結(jié)果，我們同樣可以計算組合函數(shù)對每個假設(shè)的信度函數(shù)值以及似然函數(shù)值

以上就是Dempster-shafer 的基本概念和理論知識了。

總結(jié)

以上是生活随笔為你收集整理的Dempster-Shafer Evidence Theory的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。