基于信息熵的Markov網(wǎng)絡(luò )結構學(xué)習算法研究

1 引言
日常生活中人們常需要處理不確定信息，例如：預測明天是否會(huì )下雨，病人是否得了某種疾病。Bayesian網(wǎng)是進(jìn)行不確定性推理的有力工具，被廣泛應用于人工智能、專(zhuān)家系統、數據挖掘等領(lǐng)域，是當前研究的熱點(diǎn)。利用Bayesian網(wǎng)可以推理不確定性知識，從而達到較好效果。
Markov網(wǎng)是類(lèi)似于Bayesian網(wǎng)的另一種進(jìn)行不確定性推理的有力工具。Markov網(wǎng)是一個(gè)無(wú)向圖，構造時(shí)無(wú)需發(fā)現邊的方向，要比構造Bayesian網(wǎng)容易得多。首先構造Markov網(wǎng)，再求出與之等價(jià)的Bayesian網(wǎng)。本文提出一種基于信息熵的方法構造Markov網(wǎng)，給出一個(gè)有效的基于信息獨立測試的Markov網(wǎng)的構造算法，該算法是一種基于依賴(lài)分析的算法。在測試樣本中的條件獨立時(shí)，利用信息論中驗證信息獨立的一個(gè)重要結論，從而大大提高效率。為衡量構造的Markov網(wǎng)的好壞，引入I-圖、D-圖和P-圖的概念。

2 依賴(lài)模型與MarkOV網(wǎng)
知識可以用一組條件獨立和條件概率表示，Markov網(wǎng)(無(wú)向圖)用于表示條件獨立。下面主要討論如何用Markov網(wǎng)表示一個(gè)依賴(lài)模型M(一組條件獨立的集合)以及如何衡量Markov網(wǎng)的好壞(引入I-圖、D-圖和最小P-圖)。
定義1：依賴(lài)模型M定義為一組條件獨立的集合，設X，Y，Z是全集U的3個(gè)不相交的子集，M={I(X，Z，y)}。其中的I(X，Z，y)表示在給定Z的條件下，X獨立于Y，即：p(X|Y，Z)=p(X|Z)和p(Y|X，Z)=p(Y|Z)。
定理1：依賴(lài)模型M中的I(X，Z，y)滿(mǎn)足以下4個(gè)性質(zhì)，設X，Y，Z是全集U的3個(gè)不相交的子集，
(1)對稱(chēng)性：I(X，Z，Y)XXXXXXI(Y，Z，X)；
(2)分解律：I(X，Z，Y∪W)=》I(X，Z，Y)＆I(X，Z，W)；
(3)弱歸并律：I(X，Z，Y∪W)→I(X，Z，∪W，Y)；
(4)減縮律：I(X，Z，y)I(X，Z，∪Y，W)→I(X，Z，Y∪W)若聯(lián)合概率函數p嚴格為正，Vx，p(x)>0，則相交律成立。
(5)相交律：I(X，Z，∪W，Y)＆I(X，Z，∪Y，W)→I(X，Z，Y∪W)給定一個(gè)依賴(lài)模型M，利用無(wú)向圖中節點(diǎn)分割的概念表示依賴(lài)模型中的條件獨立。
定義2：在有向無(wú)環(huán)圖G中，X，Y，Z是U上3個(gè)不相交的子集，刪去節點(diǎn)集Z及其相應的邊，使節點(diǎn)集X，Y之間再無(wú)邊相連，稱(chēng)Z將X，Y分割開(kāi)，記為X|Z|Y>G。用X|Z|Y>G表示依賴(lài)模型中條件獨立信息I(X，Z，Y)，得到一個(gè)依賴(lài)模型的圖形化表示方式，繼續用I-圖、P-圖、D-圖的概念衡量依賴(lài)模型M中的所有條件獨立信息和最優(yōu)Markov網(wǎng)。
定義3：設M為依賴(lài)模型，I(X，y，Z)M表示依賴(lài)模型M所蘊含的依賴(lài)關(guān)系(條件獨立)I(X，y，Z)。無(wú)向圖G=(V，E)為M的I-圖、D-圖、P-圖，定義如下：
(1)G是M的I-圖(獨立圖)，當X|Z|Y>G=X|Z|Y>M。
(2)G是M的D-圖(依賴(lài)圖)，當X|Z|Y>M=>X|Z|Y>G。
(3)G是M的P-圖(理想圖)，當X|Z|Y>M=X|Z|Y>G。
由上述定義可知，I-圖不一定包含依賴(lài)模型M所蘊含的所有依賴(lài)關(guān)系，但I-圖中蘊含的依賴(lài)關(guān)系M中一定蘊含；D-圖恰好相反，D-圖包含依賴(lài)模型M所蘊含的所有依賴(lài)關(guān)系，但D-圖中蘊含的依賴(lài)關(guān)系M中不一定蘊含；P-圖是最理想的情況，P-圖與M形成一一對應關(guān)系?？請D(不含任何邊的無(wú)向圖)是一個(gè)平凡的D-圖，而完全圖(包含所有邊的無(wú)向圖)是一個(gè)平凡的I-圖。
定義4：設一個(gè)無(wú)向圖G是M的一個(gè)I-圖，若刪除G中任何一條邊后，使得G不再是M的I-圖，則稱(chēng)G為M的最小I-圖。顯然，最小I-圖能夠最多地表示依賴(lài)模型M中的依賴(lài)關(guān)系。
定理2：滿(mǎn)足對稱(chēng)性、分解性、相交律和弱歸并律的依賴(lài)模型M,從完全圖中刪除所有條件獨立性成立的邊，則產(chǎn)生一個(gè)唯一的最小I-圖。

3 信息熵概述
Markov網(wǎng)結構用來(lái)消除不確定性的東西，信息的載體稱(chēng)為消息。含有信息的消息集合稱(chēng)為信源。信源的信息熵，就是信源提供整個(gè)信息的總體度量。所以如果消息消除的不確定性越大，信源的信息熵就越小，信息間的相互依賴(lài)性就越大；反之，信息間的相互獨立性就越大。具體概念作如下定義：
定義5：設屬性X具有r種可能狀態(tài)，Pi為狀態(tài)Xi時(shí)的概率，則信息熵可定義為：

式中，C為大于0的常數。
定義6：設X，Y為兩個(gè)相互關(guān)聯(lián)的隨機變量，稱(chēng)：為X，Y的聯(lián)合熵。H(X|Y)=H(X，i=1j=1Y)-H(Y)為給定Y時(shí)X的條件熵。條件熵H(X|Y)表示在觀(guān)測到Y的結果后，對X保留的不確定性度量。
定義7：設X，Y，Z為3個(gè)不相交的變量集，稱(chēng)：的互信息。
為給定Z的條件下，X和Y的互信息(條件互信息)。
定理3：互信息I(X，Y)和I(X，Y|Z)具有如下性質(zhì)：
(1)對稱(chēng)性，即I(X，Y)=I(Y，X|Z)和I(X，Y|Z)=I(Y，X|Z)；
(2)非負性，即I(X，Y)≥0和I(X，Y｜Z)≥0。而且，當且僅當X和Y條件獨立時(shí)有I(X，Y)=0。同理，當且僅當在給定條件Z，X和Y條件獨立時(shí)I(X，Y｜Z)=0。

4 基于信息熵的Markov網(wǎng)構造算法
給定一樣本集(n個(gè)屬性的一張二維表)，先對系統中N個(gè)變量構建一個(gè)完全無(wú)向圖氏，然后利用信息獨立測試理論有效刪剪PG圖，以得到所求的Markov網(wǎng)。
首先給出這個(gè)算法所需要的一些假設：給定的樣本數據集D是完整的；所有的變量取值均為離散性，若取值連續可先進(jìn)行離散化。
第1步：構造完全有向圖
定義8：設一個(gè)系統含有N個(gè)變量｛X1，X2，……，Xn}，完全有向圖PG={Xi,Xj>|，其中i,j=1，2，…，n且i≠j，Xi，Xj>表示Xi與Xj有因果關(guān)系Xi→Xj}。由此定義可知，PG是一個(gè)I-圖。
第2步：有效刪剪PG圖
從定理3的性質(zhì)2可得到一個(gè)判斷X,Y是否條件獨立的算法：當給出一個(gè)概率分布P(x)時(shí)，可通過(guò)判斷I(X，Y|Z)=0代替I(X，Y|Z)，從而PG圖中的X→Y和Y→X邊可刪除；否則。在給定條件Z的情況下，X和Y互相依賴(lài)。然而在實(shí)際計算中并沒(méi)有一個(gè)真正的概率分布P(x)，只有一個(gè)基于樣本數據集D而計算的一個(gè)經(jīng)驗概率分布PD(x)近似估計P(x)，計算的I(X，Y｜Z)只是基于PD(x)上的I(X，Y｜Z)近似值，所以其值總大于0。為此，判斷條件獨立方法可描述為：
定理4：設X，Y，Z為全集U上3個(gè)不相交的子集，基于樣本數據集D上概率分布PD(x)，如果有：I(X，Y｜Z)ε，則判定給定Z，X與Y條件獨立；否則給定Z，X與Y是條件依賴(lài)的。其中ε為一個(gè)閾值，通常取一個(gè)很小的正數。