基于反饋證據沖突度的概率轉換

關 欣, 劉海橋, 衣 曉, 趙 靜

(海軍航空工程學院電子信息工程系, 山東 煙臺 264001)

0 引 言

不確定推理是多源信息融合與人工智能領域處理不確定數據的有效手段,主要方法有貝葉斯推理[1]、D-S證據理論[2-4]、D-S理論(Dezert-Smarandache theory, DSmT)[5-6]、模糊邏輯推理、粗糙集理論等[7]。

而對于證據理論還存在諸多課題等待進一步研究,其中包括基本概率賦值(basic probability assignment, BPA)的獲取、相關證據的融合、沖突證據的融合[8-13]、證據決策等相關問題的研究,隨著研究進一步深入,目標識別框架由概率框架拓展到冪集框架和超冪集框架等廣義冪集框架,廣義冪集框架的勢不斷增大,信度賦值過于分散,決策過程相對復雜,傳統的基于BPA的決策方法不能對目標有效識別。而概率推理方法具有較強理論基礎,所以國內外學者開展了概率轉換方法研究,將廣義冪集框架下的信度賦值映射到單子集識別框架形成概率,利用概率推理手段對目標進行識別。

文獻[14-15]率先提出基于可傳遞信度模型(transferable belief model, TBM)中的Pignistic概率轉換(pignistic probability transform, PPT),將廣義冪集框架下的BPA根據命題的勢均分到單子集命題,該方法過于粗糙,沒有考慮單子集命題權重;文獻[16-18]結合信任函數和似真度函數對單子集命題的權重進行改進,提出多種改進算法,但提出的系列算法中多采用單一指標進行決策分析;文獻[19]將信任函數與似真度函數相結合對轉換公式進行改進,但構造的公式沒有利用命題的勢;文獻[20-21]引入命題的勢,給出新的改進公式,但是缺乏合理的評價指標;文獻[22]在pignistic概率轉換的基礎上,提出多尺度概率轉換(multiscale probability, MulP)函數,該公式引入Tsallis信息熵,對PPT進行了一般化表達,但同樣沒有給出合理的評價指標;文獻[23]在研究沖突證據之間融合問題時,提出改進型概率轉換公式,對于轉化公式的合理性,同樣,文章只給出算例分析;文獻[24]在D-S證據融合中,關于組合規則選取和概率轉換方法選取之間的關聯性進行了深入研究;文獻[25]引入有序加權平均的思想,基于有序可視圖(ordered visibility graph, OVG)給出新的概率轉換公式,該方法基于BPAs給出OVG,從而計算出每個元素的權重,能夠一定程度上得到有效的概率轉換結果。

上述概率轉換公式方法的給出過程較為主觀,概率轉換方法缺乏嚴密性,本文首先從多種概率轉換公式出發,研究概率轉換規律,給出統一的概率轉換公式。

概率轉換的另一個研究焦點在于,如何對概率轉換公式進行合理評判,以論證轉換的合理性。概率轉換效果好壞,應分析轉換后的概率能否有效表征原有的證據,即轉換后的概率向量與原有的證據向量關聯性大小。概率轉換公式的評價多采用文獻[12]提出的概率信息容量(probability information content, PIC),而PIC本質上是對轉換后概率信息熵的歸一化。在BPA不確定度度量問題的研究中,多引入信息熵的概念。學者先后提出諸多信息熵的概念[26-29],其中文獻[29]提出的新的Deng熵,Deng熵引入元素的勢,將元素本身的不確定度也考慮在內,使得對BPA不確定度的度量更加合理。但是這些熵信息并不能很好地衡量證據之間的關聯度,只能反映證據的決策能力,并不能反映概率轉換的合理性。

鑒于此,文獻[30]在關聯系數基礎上,提出證據關聯系數,給出最優化轉換方法,使轉換概率與原證據關聯系數最大,但是,該方法提出的證據關聯系數衡量的是轉換概率與原證據當中單元素命題之間的關聯程度,丟失了多元素命題的信息量,并不能很好的度量轉換概率與原證據之間的關聯程度。對于2個證據之間的沖突度的度量研究,是一類超維函數求解問題,而且維度隨著識別框架的變化而變化,所以現有的沖突度量函數都很難表征證據之間的沖突度。鑒于此,本文引入了現代優化算法。通過構造新的基于反饋證據沖突度的評價方法;在統一的概率轉換公式框架下,基于最小反饋沖突度,利用遺傳算法求解出新的轉換概率;最后結合仿真分析驗證本文方法合理性。

1 理論基礎

主觀貝葉斯方法是不確定推理最初使用的方法,該方法基于概率論中的貝葉斯理論進行不確定推理,具有較強理論基礎,但是在處理不確定數據過程中,用概率來表示不確定信息的貝葉斯方法沒有用信度表示不確定方法的證據理論有效[31]。D-S證據理論是對主觀貝葉斯方法的推廣[2-3],這種與推廣具體表現在對識別框架的推廣,假設研究對象X的所有可能取值都在論域集合中,Ω內所有元素互斥,則稱Ω為一識別框架。在貝葉斯框架下,命題Ai∈Ω互相獨立,而D-S證據理論將識別框架推廣到了冪集,命題Ai,Aj∈2Ω,則Ai∪Aj∈2Ω,即冪集2Ω在并運算下封閉。假設Ω為一識別框架,映射m:2Ω→[0,1]在滿足

(1)

構建上述信度函數的最終目的是決策,從而形成有效評估,但是由于信度表示信息的不確定性,使得決策缺乏有效的理論基礎,同時也不符合人的主觀認知。鑒于此,文獻[14-15]進一步證實了概率轉換的有效性,并將決策分為2個層,credal層和pignistic層。在credal層,建立各種模型,完成對不確定信息的表示;在pignistic層,完成對信度的概率轉換,概率轉換要求命題Ai轉換后得到的概率應該落在原命題Ai的信任區間內,同時轉換后的概率在單元素框架Ω內滿足歸一化要求,即滿足

(2)

與傳統的決策相比,基于pignistic概率轉換的決策方法更符合人的決策思維,同時拉大了不同元素之間的信度賦值,有效提高識別率。

2 概率轉換公式的統一表達式

2.1 Bel或Bel(A)類方法的統一概率轉換公式

Bel(A)、Pl(A)不具備歸一化要求,單純基于Bel或Pl的概率轉換公式相對較少。通過對現有概率轉換公式分析,給出這一類型的統一的概率轉換公式

(3)

其中

BP(Ai)=α1Bel(Ai)+(1-α2)Pl(Ai)

(4)

(5)

式中,αi為[0,1]區間上的常數。

2.2 BPA類方法的統一概率轉換公式

m(Ai)具備歸一化要求,轉換公式更直觀,多數轉換公式基于這一類模型。通過對現有概率轉換公式分析,給出這一類型的統一的概率轉換公式

(6)

文獻[21]在DSmP的基礎上,基于分層概率轉換思想,提出Hierarchical DSmP(HDSmP),雖然HDSmP公式利用遞推的形式給出,但分析不難發現也是第二類概率轉換模型,考慮多元素命題A(k)轉換給Ai?A(k)的概率

(7)

需通過分層遞推求解得到。

文獻[22]在pignistic概率轉換的基礎上,提出多尺度概率轉換MulP,該公式引入Tsallis信息熵q對PPT進行了一般化表達:

其中,m(φ)≠0,可以看出

當q=0時,MulP便退化為pignistic概率轉換[14]。

3 基于反饋證據沖突度的概率轉換公式

3.1 新的基于反饋證據沖突度的概率轉換表達式

3.1.1 基于反饋證據沖突度的概率轉換評價方法

概率轉換問題討論焦點在于如何設計合理的轉換公式,本文將提出新的基于最小反饋證據沖突度的概率轉換評價方法。

概率轉換將原有的廣義冪集框架下的信任分配轉換到單元素框架下的概率,轉換后的概率應該與原證據具有很高的相似度。本文構造反饋證據沖突度的指標來衡量概率轉換的優劣,先將證據進行概率轉換,然后將轉換概率與原基本概率賦值融合,得到反饋證據,最后計算反饋證據與原證據之間的沖突度,沖突度越小,概率轉換公式轉換效果越優,如圖1所示。

圖1 基于反饋證據沖突度的概率轉換評價方法流程圖Fig.1 Flow diagram of the conflict degree of feedback evidence

3.1.2 最小反饋證據沖突度概率轉換表達式

結合流程圖1,給出基于最小反饋沖突度的概率轉換表達式(8),其中,m′為轉換概率,?表示混合DSmT組合規則。

從流程圖中可以看出,基于反饋證據沖突度的概率轉換方法有兩層反饋,第1層是通過證據融合規則,得到反饋證據;第2層是通過沖突度量函數得到沖突度,所以基于反饋證據沖突度的評價標準效果的好壞,取決于融合規則和沖突度量函數選取的優劣,下面對這2個要素分別進行分析與選取。

mindcf(m1,m2)

(8)

3.1.3 概率轉換表達式中證據融合規則的選取

步驟2中的證據融合規則的選取決定了概率轉換評價效果的好壞,分析流程圖,可以知道,選取的證據融合規則需具備以下要素:能夠有效的表達兩條證據的綜合信度;融合后的識別框架與原證據識別框架保持一致。隨著不確定推理的研究不斷地深入,文獻[2]提出經典的Dempster組合規則

(9)

Dempster組合規則在處理沖突量時采用了歸一化手段,但是由于沖突系數K的存在,使得Dempster組合規則在處理沖突信息時,產生反直覺效果,不利于決策。其次,分析Dempster組合規則發現,證據與轉換概率進行組合時,由于轉換概率都是單元素集,所以在Dempster組合規則下,步驟2融合后的識別框架為單元素集,不利于后續的證據沖突度的度量,失去證據融合的意義。D-S證據組合規則有很多的改進規則,其中具有代表性的是DSmT[21]:

(10)

式中,Φ(A)是命題A的特征非空函數,混合DSmT模型的約束條件就是原證據的信任賦值空間。由于DSmT證據理論能有效融合沖突證據,并且,通過混合DSmT模型,融合后的反饋證據與原證據理論有著相同的識別框架,對于步驟2證據融合方法,本文選取混合DSmT證據融合模型。

3.1.4 概率轉換表達式中沖突度量函數的選取

衡量2個信度賦值之間的沖突度,便是求解2個向量之間“距離”的算法研究。在線性空間V中,對于任意的向量x,都存在著非負實數‖x‖與之對應,并滿足以下要求:‖x‖≥0,‖x‖=0當且僅當x=0,‖kx‖=|k|·‖x‖,‖x+y‖≤‖x‖+‖y‖,則稱‖x‖為向量x的范數。

其中應用比較廣泛的有文獻[32]提出的是證據距離:

(11)

3.2 基于反饋證據沖突度的概率轉換方法實現

對式(8)優化問題進行求解。由于規劃方程中的約束條件有概率轉換運算和混合DSmT運算,這2種運算都不是連續的,所以,上述優化問題需要通過現代優化技術解決,本文將采用理論比較成熟、應用比較廣泛的遺傳算法解決上述優化問題。具體算法流程圖如圖2所示,首先構造初始“種群”,使算法能夠快速收斂,初始種群數據通過pignistic概率轉換獲取得到,種群的數量與識別框架的勢有關;然后進過復制、交叉、變異等操作,直到數據收斂,交叉和變換都有相應的執行概率pc、pm,以模擬生物進化過程;適應度函數用反饋證據沖突度衡量。

圖2 基于遺傳算法求解概率轉換流程圖Fig.2 Flow diagram of the probability transformation

具體實現步驟如下:

步驟1生成初始種群

步驟2構建種群

步驟3染色體編碼

步驟4個體適應度評價

個體適應度評價方法利用反饋證據沖突度dcf,計算種群每一個體反饋證據沖突度,判斷是否收斂,如果收斂,輸出概率轉換結果;如果不收斂,進行升序排序,淘汰后N/2的個體,形成新的種群。

步驟5繁衍復制

步驟6染色體交叉運算

圖3 染色體交叉運算Fig.3 Chromosome crossover operation

步驟7染色體變異運算

染色體復制過程中還存在變異的可能,如圖4所示。為模擬這一過程,隨機選取染色體的突變點進行變異運算,變異概率pm=0.05,同樣對運算結果進行歸一化。

圖4 染色體變異運算Fig.4 Chromosome mutation operation

步驟8返回步驟4。

4 算例分析

4.1 對反饋證據沖突度評價方法的算例分析

算例1假設識別框架Ω={a,b,c,ab,ac,bc,abc},基本概率賦值定義如下m(a)=m(b)=m(c)=0.2,m(ab)=m(ac)=m(bc)=m(abc)=0.1,分別用不同的概率轉換公式對其進行轉換,得到相同的轉換概率m′(a)=m′(b)=m′(c)=1/3。再分別用不同的評價方法對轉換結果進行評價,得到表1數據。算例中基本概率賦值對a、b、c的信任程度一樣,概率轉換應該給予a、b、c相同的轉換概率,所以現有概率轉換方法都賦予a、b、c轉換概率1/3是合理的,不同評價方法對此概率轉換因給出最優評價。

表1 算例1概率轉換評價結果

但是,基于信息熵的評價方法(越小越好)給出最差的評價,因為信息熵反應的是證據的決策能力,當a,b,c具有相同的轉換概率時,無法作出決策,與正確評價剛好相反;本文基于反饋證據沖突度的評價方法(越小越好)給出較優的評價結果,能夠正確衡量概率轉換的效果;而基于關聯系數評價方法(越大越好)和本文評價方法一樣給出較優的評價結果,因為關聯系數衡量的是轉換概率與原證據中單元素命題之間的關聯程度,該算例中原證據單元素命題a,b,c的信度都為0.2,所以基于關聯系數評價方法給出較優評價,但這并不能反應關聯系數評價方法的優越性,下面看算例2。

算例2假設識別框架Ω={a,b,c,ab,ac,bc},基本概率賦值定義如下:

m(a)=0.015,m(b)=0.015,m(c)=0.07

m(ab)=0.3,m(ac)=0.3,m(bc)=0.3

分別用不同的概率轉換公式對其進行轉換,并算出不同評價方法下的轉換效果,如表2所示。

表2 算例2實驗結果

該算例中基本概率賦值,單元素命題的信度很低,多元素命題給予a,b,c的信度相等,所以轉換結果應該顯示a,b的概率相等,c的概率略高。從融合結果看,這幾種融合算法都賦予c命題過高的概率,效果不是很理想。基于信息熵的評價方法顯示,BetP,PraPl,PrPl法轉換效果較差,但是,通過分析可以發現,相比于其他算法,這3種算法更接近基本概率賦值的設定,原因和算例1一樣,信息熵不能反映轉換概率的好壞;基于關聯系數的評價方法認為幾種概率轉換效果很好,原因在于轉換后a,b,c概率之間比例與原證據中單元素信度之間比例相似,所以給出錯誤評判;而本文提出的反饋證據沖突度顯示,幾種轉換方法都不是很好,相比較而言,BetP,PraPl,PrPl法更優于其他幾種算法。通過算例分析可以看到反饋證據沖突度相比于其他的評價方法能夠更好地衡量概率轉換的效果。

4.2 基于反饋證據沖突度的概率轉換仿真分析

假設識別框架Ω={a,b,c,ab,bc,abc},基本概率賦值定義如下:

m(a)=0.1,m(b)=0.1,m(c)=0.2

m(ab)=0.2,m(bc)=0.1,m(abc)=0.3

基于遺傳算法求解最小反饋證據沖突度的概率分配,算法迭代過程如圖5所示。橫坐標表示遺傳算法中“種群”繁衍代數,種群指規劃方程中比例系數kiI;縱坐標表示適應度函數,本文用反饋證據沖突度dcf表示種群的適應度。可以看出,當繁衍代數為1 000次時,系統處于收斂狀態;圖中的多個階躍點是由于種群變異產生,向上階躍表明變異后的個體是劣質的,向下階躍表明變異后個體是優異的。

圖5 遺傳算法迭代過程Fig.5 Iteration process of genetic algorithm

分別用不同的概率轉換公式對算例進行轉換,并算出轉換效果,如表3所示。

表3 各種概率轉換結果對比

對表3中數據進行對比,發現本文算法能求解出更合理的概率分配,因為不同改進型概率轉換算法求解過程較為主觀,先定義概率轉換公式,然后根據轉換結果驗證算法合理性,這很難得到最優轉換概率;同時經典的pignistic概率轉換方式下的轉換概率不一定比其他改進型的概率轉換方式差,只是單純的從數學公式角度分析,改進型的概率轉換公式比經典的pignistic概率轉換公式更加合理。

最后,利用基于反饋證據沖突度的概率轉換方法對算例2的數據進行算例分析,結果如表2所示,3個單元素得到的轉換后概率都接近1/3,符合直覺判斷結果。而從評價指標可以看出,信息熵的評價指標為1,最差,因為當元素的置信度相同時,無法進行決策;關聯系數也給出相對其他轉換方法較差的評價結果,因為該算例中單元素賦值太小,失去意義,而關聯系數衡量的是轉換概率與原證據當中單子集命題之間的關聯程度,沒考慮多子集命題的信息量,因此不能很好的度量轉換效果;本文提出的反饋證據沖突量相對于其他算法給出較好的評價結果,驗證了本文所提方法的有效性。

5 結 論

概率轉換是不確定推理中有效決策方法之一,合理的概率轉換可以有效地避免不準確的估計與決策。本文首先從結構組成上分析現有的多種概率轉換公式,給出兩類統一的概率轉換公式;然后構造反饋證據沖突度評價指標,利用轉換概率與原基本概率賦值經過DSmT融合規則得到反饋證據,計算反饋證據與原證據之間沖突度,有效衡量概率轉換效果;繼而利用統一的概率轉換公式框架,在最小反饋證據沖突度的約束條件下,利用遺傳算法求解出最優的轉換概率;最后分別對基于反饋證據沖突度的評價方法和概率轉換的實現進行算例分析,表明了算法的合理性。

參考文獻：

[1] LUCAS P J, HOMMERSOM A. Modeling the interactions between discrete and continuous causal factors in bayesian networks[J]. International Journal of Intelligent Systems, 2015, 30(3): 209-235.

[2] DEMPSTER A P. Upper and lower probabilities induced by a multivalued mapping[J]. Annals of Mathematical Statistics, 1967, 38(2): 325-339.

[3] DENG Y. Generalized evidence theory[J]. Applied Intelligence, 2015, 43(3):530-543.

[4] YAGER R R, ALAJLAN N. Dempster-Shafer belief structures for decision making under uncertainty[J]. Knowledge Based Systems, 2015,80(C): 58-66.

[5] DEZERT J, SMARANDACHE F. Advances and applications of DSmT for information fusion collected works[M]. 4th ed. Rehoboth: American Research Press, 2015.

[6] HAN D, DEZERT J, DUAN Z. Evaluation of probability transformations of belief functions for decision making[J]. IEEE Trans.on Systems Man & Cybernetics-Part A: Systems,2016,46(1):1-18.

[7] YANG Y, HAN D. A new distance-based total uncertainty measure in the theory of belief functions[J]. Knowledge-Based Systems, 2016, 94: 114-123.

[8] HAN D, DEZERT J, YANG Y. Belief interval-based distance measures in the theory of belief functions[J]. IEEE Trans.on Systems Man & Cybernetics Systems, 2016,PP(99): 1-18.

[9] QIAN J, GUO X F, DENG Y. A novel method for combining conflicting evidences based on information entropy[J]. Applied Intelligence, 2017, 46(4): 876-888.

[10] YU C, YANG J, YANG D, et al. An improved conflicting evidence combination approach based on a new supporting probability distance[J]. Expert Systems with Applications, 2015, 42(12): 5139-5149.

[11] SMARANDACHE F, DEZERT J. Modified PCR rules of combination with degrees of intersections[C]∥Proc.of the International Conference on Information Fusion, 2015: 2100-2107.

[12] JIANG W, LUO Y, QIN X, et al. An improved method to rank generalized fuzzy numbers with different left heights and right heights[J]. Journal of Intelligent and Fuzzy Systems, 2015, 28(5): 2343-2355.

[13] JIANG W, WEI B, QIN X, et al. Sensor data fusion based on a new conflict measure[J]. Mathematical Problems in Engineering, 2016: 1-11.

[14] SMETS P, KENNES R. The transferable belief model[J]. Artifieial Intelligenee, 1994, 66(4): 191 -234.

[15] SMETS P. Decision making in the TBM: the neeessity of the pignistic transformation[J]. International Journal of Approximate Reasoning, 2005, 38(2): 133-147.

[16] SUDANO J J. The system probability information content (PIC) relationship to contributing components, combining independent multi-source beliefs, hybrid and pedigree pignistic probabilities[C]∥Proc.of the International Conference on Information Fusion, 2002: 1277-1283.

[17] SUDANO J J. Yet another paradigm illustrating evidence fusion(YAPIEF)[C]∥Proc.of the International Conference on Information Fusion, 2007:1-7.

[18] SUDANO J J. Pignistic probability transforms for mixes of low-and high-probability events[C]∥Proc.of the 4th International Conference on Information Fusion, 2001: 23-7.

[19] 潘巍, 王陽生, 楊宏戟. Pignistic概率轉換算法設計[J]. 計算機工程與應用, 2005, 31(4): 20-25.

PAN W, WANG Y S, YANG H J. Algorithm design of pignistic probability transforms[J]. Computer Engineering and Applications, 2005, 31(4): 20-25.

[20] DEZERT J, SMARANDACHE F. A new probabilistic transformation of belief mass assignment[C]∥Proc.of the International Conference on Information Fusion, 2008: 1-8.

[21] DEZERT J, HAN D, LIU Z G, et al. Hierarchical DSmP transformation for decision-making under uncertainty[C]∥Proc.of the International Conference on Information Fusion, 2012: 294-301.

[22] LI M, LU X, ZHANG Q, et al. Multiscale probability transformation of basic probability assignment[J]. Mathematical Problems in Engineering, 2014,2014: 1-6.

[23] MA M, AN J. Combination of evidence with different weighting factors: a novel probabilistic-based dissimilarity measure approach[J]. Journal of Sensors, 2015, 2015(2): 1-9.

[24] CINICIOGLU E N. Decision making with consonant belief functions: Discrepancy resulting with the probability transformation method used[J]. Yugoslav Journal of Operations Research, 2014, 24(3): 359-370.

[25] LI M, ZHANG Q, DENG Y, et al. A new probability transformation based on the ordered visibility graph[J]. International Journal of Intelligent Systems, 2016, 31(1): 44-67.

[26] DU W, GAO Y, LIU C, et al. Adequate is better: particle swarm optimization with limited-information[J]. Applied Mathematics and Computation, 2015, 268: 832-838.

[27] DU W, YING W, YAN G, et al. Heterogeneous strategy particle swarm optimization[J]. IEEE Trans.on Circuits and Systems Ii-express Briefs, 2017, 64(4): 467-471.

[28] DU W, ZHOU X, LORDAN O, et al. Analysis of the Chinese airline network as multi-layer networks[J]. Transportation Research Part E-logistics and Transportation Review, 2016, 89(89): 108-116.

[29] DENG Y. Deng entropy: a generalized shannon entropy to measure uncertainty[J]. Chaos, Solitons & Fractals, 2016, 91: 549-553.

[30] 許培達, 韓德強, 鄧勇. 一種基本概率賦值轉換為概率的最優化方法[J]. 電子學報, 2011, 39(3A): 121-125.

XU P D, HAN D Q, DENG Y. An optimal transformation of basic probability assignment to probability[J]. Acta Electronica Sinica, 2011, 39(3A): 121-125.

[31] 蔣雯, 張安, 鄧勇. 基于區間信息的基本概率賦值轉換概率方法及應用[J]. 西北工業大學學報, 2011, 29(1): 44-48.

JIANG W, ZHANG A, DENG Y. Proposing interval probability transform(IPT) method for decision making and its application[J]. Journal of Northwestern Polytechnical University, 2011, 29(1): 44-48.

[32] JOUSSELME A, GRENIER D, BOSSE E, et al. A new distance between two bodies of evidence[J]. Information Fusion, 2001, 2(2): 91-101.