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

(4)輸出V
由以上算法可知：整個(gè)算法是計(jì)算復(fù)雜度為O(／N2)的條件獨(dú)立性CI(Conditional Independence)測(cè)試。

5 實(shí)例分析
此例來自對(duì)華盛頓高級(jí)中學(xué)131名高年級(jí)學(xué)生的升學(xué)計(jì)劃調(diào)查，每個(gè)學(xué)生用下列變量及其相應(yīng)的狀態(tài)來描述：性別(X1)：男、女；社會(huì)經(jīng)濟(jì)狀態(tài)(X2)：低、中下、中上、高：智商(X3)：低、中下、中上、高；家長的鼓勵(lì)(X4)：低、高；升學(xué)計(jì)劃(X5)：是、否。樣本數(shù)據(jù)：下面的數(shù)據(jù)表示對(duì)5個(gè)變量取值的某種組合統(tǒng)計(jì)所得到的人數(shù)，例如：第一個(gè)數(shù)據(jù)4表示對(duì)(X1=男，X2=低，X3=低，X4=低，X5=是)這種組合所統(tǒng)計(jì)出的人數(shù)。變量依次按從右到左的順序輪換，狀態(tài)則按照上述所列各變量狀態(tài)的順序進(jìn)行輪換，依此類推，得到完全統(tǒng)計(jì)數(shù)據(jù)如下：4，349，13，64，9，207，33，72，12，126，38，54，10，67，49，43，2，232，27，84，7，201，64，95，12，115，93，92，17，79，119，59，8，166，47，91，6，120，74，110，17，92，148，100，6，42，198，73，4，48，39，57，5，47，123，90，9，41，224，65，8，17，414，54，5，454，9，44，5，312，14，47，8，216，56，35，13，96，28，24，11，285，29，61，19，236，47，88，12，164，62，85，15，113，72，50，7，163，36，72，13，193，75，90，12，174，91，100，20，8l，142，77，6，50，36，58，5，70，110，76，12，48，230，81，13，49，360，98Heckerman等用基于統(tǒng)計(jì)打分搜索算法得到如圖1所示的兩種最有可能的結(jié)構(gòu)。

基于圖1所示的算法計(jì)算結(jié)果如下：取閾值為0．007和0．001，經(jīng)計(jì)算得到圖2a的結(jié)構(gòu)，根據(jù)專家知識(shí)可知：性別、社會(huì)經(jīng)濟(jì)狀態(tài)是不會(huì)有父節(jié)點(diǎn)的，所以對(duì)X1=>X4和X2=>X3兩種依賴關(guān)系可修訂為X1=>X4和X2=>X3，由此得到圖2b所示的結(jié)構(gòu)。因此，可以看出，圖1a和圖2b是一樣的。根據(jù)Markov的理論和特征，得到Markov網(wǎng)結(jié)構(gòu)，如圖3所示。

6 結(jié)束語
通過認(rèn)真研究信息熵理論知識(shí)得到基于信息熵的Markov網(wǎng)算法，在一定程度上簡(jiǎn)化了Bayesian網(wǎng)推理過程，提高了推理效率，對(duì)知識(shí)的不確定推理研究具有參考價(jià)值。