專家系統/Dempster-Shafer 理論

關於 Dempster-Shafer 理論

Dempster-Shafer 理論是一個基於置信函式和似然推理的數學證據理論，用於結合不同的資訊片段（證據）來計算事件的機率。該理論由 Arthur P. Dempster 和 Glenn Shafer 創立。

考慮兩個可能的賭注

第一個賭注是，我們賭一個公平的硬幣丟擲後正面朝上。現在考慮第二個賭注，我們賭世界上最偉大的拳擊手和世界上最偉大的摔跤手之間的比賽結果。假設我們對格鬥術非常無知，很難做出選擇。

許多人會覺得第二個賭注比第一個賭注更難以確定，因為第二個賭注的機率是未知的，而第一個賭注的機率很容易看出是二分之一。 Dempster-Shafer 理論允許人們考慮對分配給各種結果的機率的置信度。

形式主義

令X為全集：所有正在考慮的狀態的集合。冪集，$\mathbb {P} (X)\,\!$，是所有可能的X子集的集合，包括空集。例如，如果

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

那麼

$\mathbb {P} (X)=\left\{\varnothing ,\left\{a\right\},\left\{b\right\},X\right\}.\,\!$

冪集的元素可以用來代表人們可能感興趣的命題，因為它們包含並且僅包含該命題為真的所有狀態。

證據理論將置信度分配給冪集的每個子集。正式地，一個函式 $m:\mathbb {P} (X)\rightarrow [0,1]$，稱為基本置信度分配（BBA），當它驗證兩個公理時。首先，空集的質量為零

$m(\varnothing )=0.\,\!$

其次，冪集其餘成員的質量總和為 1

$1=\sum _{A\in \mathbb {P} (X)}m(A).\,\!$

冪集的給定成員A的質量m(A) 表示所有相關和可用證據中支援實際狀態屬於A但屬於A的任何特定子集的比例。m(A) 的值僅與集合A相關，並且不做出關於A的任何子集的額外宣告，根據定義，每個子集都有它自己的質量。

從質量分配中，可以定義機率區間的上限和下限。該區間包含感興趣的集合的精確機率（以經典意義），並受稱為置信度（或支援）和似然度的兩個非加性連續測度限制

$\operatorname {bel} (A)\leq P(A)\leq \operatorname {pl} (A).\,\!$

集合 *A* 的置信度 bel(*A*) 被定義為所有（不一定是真）子集的質量之和，這些子集屬於我們感興趣的集合。

$\operatorname {bel} (A)=\sum _{B\mid B\subseteq A}m(B).$

似然度 pl(*A*) 是所有與我們感興趣的集合 *A* 相交的集合 *B* 的質量之和。

$\operatorname {pl} (A)=\sum _{B\mid B\cap A\neq \varnothing }m(B).$

這兩個度量之間的關係如下

$\operatorname {pl} (A)=1-\operatorname {bel} ({\overline {A}}).\,\!$

從上面可以看出，你只需要知道三個中的一個（質量、置信度或似然度）就可以推斷出另外兩個，儘管你可能需要知道許多集合的值才能計算出特定集合的另一個值。

Dempster 組合規則

我們現在面臨的問題是如何組合兩組獨立的質量分配。最初的組合規則被稱為 Dempster 組合規則，它是貝葉斯規則的推廣。該規則強烈強調多個來源之間的一致性，並透過歸一化因子忽略了所有衝突證據。當遇到資訊中的顯著衝突時，使用該規則受到了嚴重批評。

具體來說，組合（稱為聯合質量）是從兩組質量 $m_{1}\,\!$ 和 $m_{2}\,\!$ 中計算出來的，如下所示

$m_{1,2}(\varnothing )=0\,\!$

$m_{1,2}(A)=(m_{1}\bigoplus m_{2})(A)={\frac {1}{1-K}}\sum _{B\cap C=A\neq \varnothing }m_{1}(B)m_{2}(C)\,\!$

其中

$K=\sum _{B\cap C=\varnothing }m_{1}(B)m_{2}(C).\,\!$

$K\,\!$ 是衡量兩組質量之間衝突程度的指標。歸一化因子 $1-K\,\!$ 的作用是完全忽略衝突，並將與衝突相關的任何質量歸於空集。因此，在某些情況下，當遇到重大的衝突時，此操作會產生違反直覺的結果。

討論

Dempster-Shafer 理論是貝葉斯主觀機率理論的推廣；貝葉斯理論要求對每個感興趣的問題提供機率，而置信函式則將對一個問題的置信度（或信心、信任）建立在對相關問題的機率基礎上。這些置信度可能具有也可能不具有機率的數學性質；它們之間的差異程度取決於兩個問題之間相關性的緊密程度。^[2] 換句話說，它是一種表達認知可能性（epistemic plausibilities）的方式，但它可以得出與使用機率論得出的答案相矛盾的結果。

Dempster-Shafer 理論通常用作感測器融合的方法，它基於兩個思想：從相關問題的主觀機率中獲取對一個問題的置信度，以及 Dempster 規則^[3] 用於結合這些基於獨立證據的置信度。本質上，對一個命題的置信度主要取決於包含該命題的答案數量（針對相關問題），以及每個答案的主觀機率。另外，組合規則也做出了貢獻，它們反映了關於資料的普遍假設。

在這個形式體系中，置信度（也稱為質量）用置信函式來表示，而不是貝葉斯機率分佈。機率值分配給可能性集合，而不是單個事件：它們的吸引力在於，它們自然地編碼了支援命題的證據。

Dempster-Shafer 理論將其質量分配給構成系統的所有實體的子集。例如，假設一個系統有五個成員，也就是說五個獨立狀態，其中只有一個是實際的。如果原始集合稱為 S，$|S|=5$，那麼所有子集的集合——冪集——稱為 2^S。由於你可以用二進位制向量表示每個可能的子集（透過寫“1”或“0”來描述某個成員是否存在，從而描述該成員槽位的出現或不存在），因此可以看出，有 2⁵ 個可能的子集 ($2^{|S|}$ 一般來說)，從空集 (0, 0, 0, 0, 0) 到“所有”集合 (1, 1, 1, 1, 1)。空集代表矛盾，它在任何狀態下都不成立，因此被分配為零質量；其餘的質量被歸一化，使它們的總和為 1。“所有”集合通常被標記為“未知”，因為它代表所有元素都存在的狀態，從某種意義上說，你無法確定哪個是實際的。

置信度和可能性

Shafer 的框架允許將關於命題的置信度表示為區間，由兩個值置信度（或支援）和可能性限定

置信度 ≤ 可能性。

對一個假設的置信度由包含在該假設內的所有集合的質量之和構成（即，所有假設子集的質量之和）。它是直接支援給定假設的置信度，至少部分支援，形成一個下限。可能性是 1 減去與假設的交集為空的所有集合的質量之和（等效地，它是所有與假設的交集不為空的集合的質量之和）。它是假設可能發生的可能性上限，即它“可能發生的”上限為該值，因為只有那麼多的證據與該假設相矛盾。

例如，假設我們對一個命題的置信度為 0.5，可能性為 0.8，比如“箱子裡的貓死了”。這意味著我們有證據可以讓我們強烈地說，該命題為真的置信度為 0.5。但是，與該假設相反的證據（即“貓還活著”）只有 0.2 的置信度。剩餘的 0.3 質量（0.5 的支援證據與 0.2 的相反證據之間的差距）是“不確定的”，這意味著貓可能死了也可能活著。這個區間代表了系統中證據所體現的不確定性水平。

假設	質量	置信度	可能性
空（既不活著也不死了）	0	0	0
活著	0.2	0.2	0.5
死了	0.5	0.5	0.8
任一（活著或死了）	0.3	1.0	1.0

空假設根據定義設定為零（它對應於“無解”）。正交假設“活著”和“死了”的機率分別為 0.2 和 0.5。這可能對應於“活貓/死貓探測器”訊號，它們各自的可靠性分別為 0.2 和 0.5。最後，包含所有假設的“任一”假設（它只是承認箱子裡有貓）彌補了差距，使得質量之和為 1。“活著”和“死了”假設的支援與其相應的質量匹配，因為它們沒有子集；對“任一”的支援由所有三個質量之和（任一、活著和死了）組成，因為“活著”和“死了”都是“任一”的子集。“活著”的可能性是 m(活著) + m(任一)，因為只有“任一”與“活著”相交。同樣地，“死了”的可能性是 m(死了) + m(任一)。最後，“任一”的可能性是 m(活著) + m(死了) + m(任一)。通用假設（“任一”）將始終具有 100% 的支援和可能性——它充當一種校驗和。

這裡是一個稍微複雜的例子，其中支援和可能性之間的行為開始顯現出來。我們正在觀察一個遙遠的目標，它只能透過各種探測模式以三種顏色（紅色、白色和藍色）中的任何一種呈現出來

假設	質量	置信度	可能性
空	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.1	1.0	1.0

儘管這些例子相當糟糕，因為這種型別的事件不會在機率空間中建模為不相交的集合，而是會將“紅色或藍色”事件視為“紅色”和“藍色”事件的並集，從而（參見機率論的公理）p(紅色或白色) >= p(白色) = 0.25 且 p(任一) = 1。實際上，人們可以對線性與“可能性”成比例的空間建模機率測度（歸一化使得 p(紅色) + p(白色) + p(藍色) = 1，並且除了所有機率仍 <= 1 之外）。

組合機率集

使用Dempster 組合規則來組合對應於獨立資訊的置信度，它是事件獨立時貝葉斯定理特例的推廣（目前還沒有方法來組合非獨立的資訊）。請注意，來自相互矛盾命題的機率質量也可以用來獲得系統中衝突程度的度量。該度量已被用作將多個看似相互衝突的證據圍繞競爭假設進行聚類的標準。

此外，Dempster-Shafer 框架的一個計算優勢是，不需要指定先驗和條件機率，這與貝葉斯方法不同，貝葉斯方法通常使用對稱（極小極大誤差）論證來為隨機變數分配先驗機率（例如，為二進位制值分配 0.5，對於這些值，沒有關於哪個更可能的資訊）。但是，Dempster-Shafer 框架中沒有使用任何包含在缺少的先驗和條件機率中的資訊，除非它可以透過間接方式獲得——並且可以說，它然後可以使用貝葉斯方程進行計算。

在這種情況下，Dempster-Shafer 理論允許指定一定程度的無知，而不是被迫提供加起來為一的先驗機率。這種型別的狀況，以及是否存在風險和無知之間的真正區別，已被統計學家和經濟學家廣泛討論。例如，參見 Daniel Ellsberg、Howard Raiffa、Kenneth Arrow 和 Frank Knight 的對比觀點。

批評

Judea Pearl (1988a, 第 9 章;^[4] 1988b^[5] 和 1990);^[6] 認為，將置信函式解釋為代表“事件的機率”、“對分配給各種結果的機率的信心”、“對命題的置信度（或信心、信任）”或“情況下的無知程度”是誤導的。相反，置信函式代表了從分配了機率的一組其他命題中證明給定命題的機率。混淆真實性的機率與可證性的機率會導致推理任務中的反直覺結果，例如（1）表示完整知識，（2）置信度更新和（3）證據合併。他進一步證明，如果部分知識透過置信函式方法進行編碼和更新，則結果置信度不能作為理性決策的基礎。

參考文獻

• Joseph C. Giarratano 和 Gary D. Riley (2005)；*專家系統：原理和程式設計*，ed. Thomson Course Tech.，ISBN 0-534-38447-1
• Kari Sentz 和 Scott Ferson (2002)；*德姆斯特-謝弗理論中的證據組合*，桑迪亞國家實驗室 SAND 2002-0835