馬爾科夫毯學(xué)習(xí)算法綜述

1、頁(yè)碼 計(jì)算機(jī)應(yīng)用研究 第28卷馬爾科夫毯學(xué)習(xí)算法研究和進(jìn)展*傅順開(kāi)，Sein Minn (華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建省廈門(mén)市 361021） 摘 要:馬爾科夫毯（MB）在貝葉斯網(wǎng)絡(luò)（BN）研究中較早被認(rèn)識(shí)和定義，它是BN拓?fù)浣Y(jié)構(gòu)的重要組成部分。在1996年被證明是預(yù)測(cè)目標(biāo)變量的最優(yōu)特征子集。給定全局BN可以很容易推導(dǎo)出特定變量的MB，但BN結(jié)構(gòu)的學(xué)習(xí)已知是NP問(wèn)題?；仡櫫藦?996年至今關(guān)于MB學(xué)習(xí)算法的17個(gè)典型工作，包括 (1) 基于MB的全局條件獨(dú)立特征的KS、IAMB等8個(gè)算法，(2) 利用MB的局部條件獨(dú)立特征的PCMB、IPC-MB等6個(gè)算法, （3）基于邏輯回歸分析+局

2、部條件獨(dú)體特征的RA-MMMB算法，和 (4) 基于評(píng)分-搜索方法的DMB和RPDMB兩個(gè)算法。討論時(shí)兼顧理論和實(shí)用性?xún)?nèi)容，并統(tǒng)一/擴(kuò)展了相關(guān)算法的偽代碼（描述），對(duì)學(xué)術(shù)界和工業(yè)界研究人員都具參考價(jià)值。關(guān)鍵詞:馬爾科夫毯; 貝葉斯網(wǎng)絡(luò)；約束學(xué)習(xí)； 特征選擇中圖分類(lèi)號(hào):TP391 文獻(xiàn)標(biāo)志碼: A 文章編號(hào)：（作者可不填）doi:10.3969/j.issn.1001-3695 (作者可不填)A Review of Markov Blanket Induction Algorithms FU Shun-kai, SEIN Minn (College of Computer Science and

3、 Technology, Huaqiao University, Xiamen Fujian 361021, China)Abstract: Markov blanket (MB) has been realized and defined during the research of Bayesian network, and it is an important component of the BN. In 1996, it was proved the optimal feature subset for prediction. Given the global BN, it is t

4、rivial to read off the MB of specific variable, but the structure learning of BN is known as NP-hard problem. From 1996 on, there are many published works on the induction of MB, and our review covers 17 typical works, including (1) those based on the global conditional independence (CI) probability

5、 feature of MB, like KS, IAMB etc., (2) those based on the local CI probability feature, such as PCMB, IPC-MB etc., (3) one work with the combination of logistic regression and constraint learning, called RA-MMMB, and (4) non-constraint learning works based on score-and-search, DMB and RPDMB. Our di

6、scussion covers theoretical as well as practical aspect, and we revise the pseudo codes of related algorithms to easier the understanding. It is believed a useful reference for both academic and industrial colleagues.Key words: Markov blanket;Bayesian network; constraint learning;dimension reduction

7、; feature selection 1 引言貝葉斯網(wǎng)絡(luò)（Bayesian Network, BN）是一種有向無(wú)環(huán)圖（DAG）模型，其中節(jié)點(diǎn)代表了隨機(jī)變量，而邊代表了隨機(jī)變量之間的概率關(guān)系?；跅l件獨(dú)立性，BN的圖模型能夠有效緊湊表達(dá)目標(biāo)問(wèn)題的聯(lián)合概率關(guān)系，并可以通過(guò)貝葉斯鏈?zhǔn)椒▌t來(lái)快速實(shí)現(xiàn)從圖表征語(yǔ)言到公式的相互轉(zhuǎn)換。BN是人工智能領(lǐng)域的一種重要工具，被成功運(yùn)用到機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域。早在1988年，Peal就在他的關(guān)于貝葉斯網(wǎng)絡(luò)研究的專(zhuān)著1里定義和討論了馬爾科夫毯（Markov Blanket，MB）。給定一個(gè)節(jié)點(diǎn)，它的MB是唯一的，包括的所有父、子和配偶（和有共同孩子的）節(jié)點(diǎn)（見(jiàn)圖1

8、）。當(dāng)MB內(nèi)的（所有）節(jié)點(diǎn)的值確定后，的值可以被確定。雖然該性質(zhì)被較早認(rèn)識(shí)到，但直到1996年才由Koller和Sahami（簡(jiǎn)稱(chēng)K&S）兩位斯坦福大學(xué)的學(xué)者將MB和特征選擇（feature selection）關(guān)聯(lián)起來(lái)2，而特征選擇是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域重要的預(yù)處理步驟之一。K&S從信息論角度首次證明了MB是預(yù)測(cè)目標(biāo)變量的最優(yōu)子集 - 不包含無(wú)關(guān)（irrelevant）和冗余（redundant）變量。特征選擇通過(guò)降低輸入維度而讓隨后的學(xué)習(xí)器所面臨的求解搜索空間的復(fù)雜度大大降低，這既提高了求解效率，也減小出現(xiàn)過(guò)擬合現(xiàn)象的可能性。同時(shí)，降維還能為數(shù)據(jù)采集、存儲(chǔ)、傳輸和預(yù)處理帶來(lái)可觀的（時(shí)間和

9、經(jīng)濟(jì)）成本節(jié)約。當(dāng)然，理想的特征選擇是在保證以上收益的同時(shí)不犧牲模型的預(yù)測(cè)能力。當(dāng)已知BN（的結(jié)構(gòu)），我們可以很容易“讀出”目標(biāo)節(jié)點(diǎn)（變量）的MB。然而，推導(dǎo)BN的結(jié)構(gòu)被公認(rèn)是NP問(wèn)題3，已知的需要自動(dòng)推導(dǎo)BN的應(yīng)用一般只包含數(shù)十個(gè)變量4。王雙成等的工作顯示了基于馬爾科夫毯的預(yù)測(cè)由于TAN、樸素貝葉斯和BN，但仍然需要先學(xué)習(xí)完整的BN5。K&S在1996年發(fā)表的著作里除了證明MB的重要性質(zhì)，也討論了MB的推導(dǎo)策略。為了保證搜索效率，他們提出了一個(gè)近似的學(xué)習(xí)算法。作者并沒(méi)有為其命名，為了引用方便本文簡(jiǎn)稱(chēng)其為K&S算法。K&S算法無(wú)法保證一定輸出正確的馬爾科夫毯2。圖 1 貝葉斯網(wǎng)絡(luò)和T的馬爾科夫

10、毯（灰色節(jié)點(diǎn)）示例。X1，X2為T(mén)的父節(jié)點(diǎn)，X3，X4 為T(mén)的子節(jié)點(diǎn)，X5，X6為T(mén)的配偶節(jié)點(diǎn)。X3，X4，Y3 為T(mén)的后代節(jié)點(diǎn)，剩下的為T(mén)的非后代節(jié)點(diǎn)基于Google Scholar的統(tǒng)計(jì)數(shù)據(jù)和我們對(duì)搜索結(jié)果的人工整理，在19962013期間至少有超過(guò)100篇的比較重要的關(guān)于馬爾科夫毯推導(dǎo)和應(yīng)用的學(xué)術(shù)論文，其中不乏發(fā)表在包括JMLR（Journal of Machine Learning Research）、DMKD（Data Mining and Knowledge Discovery）、ICML、KDD、ECMLPKDD、AAAI、PAKDD等頂級(jí)期刊和學(xué)術(shù)會(huì)議上。K&S的1996年的開(kāi)

11、創(chuàng)性論文2更是獲得了超過(guò)1260次的引用（截止準(zhǔn)備本文時(shí)）。以上事實(shí)和數(shù)字直接反映了該研究方向的重要性，但國(guó)內(nèi)相關(guān)的研究成果甚少（查新過(guò)程中只發(fā)現(xiàn)兩篇相關(guān)的工作），這推動(dòng)我們撰寫(xiě)本文將相關(guān)研究進(jìn)展向國(guó)內(nèi)同行介紹。在文中，我們將揀選出已發(fā)表的工作有代表性的算法進(jìn)行分類(lèi)，并從理論和實(shí)用維度分別給予介紹和討論，相信這將有助于同行研究人員和工業(yè)界應(yīng)用者的參考。2 符號(hào)、概念、算法分類(lèi)和討論維度2.1 符號(hào)表示采用粗體羅馬字母表示變量集合（比如），非粗體的斜體羅馬字母表示單個(gè)變量（比如），對(duì)應(yīng)的小寫(xiě)羅馬字母表示變量值（比如，）。對(duì)于一個(gè)分布，采用表示給定條件集時(shí)，與是相互獨(dú)立的。若條件集（為空），使用表

12、示。為了簡(jiǎn)化表示，在考慮單個(gè)變量時(shí)，都忽略標(biāo)準(zhǔn)的集合表示。比如，采用表示。類(lèi)似地，使用來(lái)表示在圖模型中節(jié)點(diǎn)之間的條件獨(dú)立關(guān)系。2.2 貝葉斯網(wǎng)絡(luò)和理論基礎(chǔ)給定變量集合，對(duì)應(yīng)的貝葉斯網(wǎng)絡(luò)是個(gè)二元組，。其中，是一個(gè)有向無(wú)環(huán)圖：節(jié)點(diǎn)集合對(duì)應(yīng)，邊集合蘊(yùn)含了拓?fù)潢P(guān)系。任意節(jié)點(diǎn)的父、子和配偶節(jié)點(diǎn)集合分別記為、和，而父子節(jié)點(diǎn)又常合并表示為。參數(shù)包含諸如這樣的條件概率分布（當(dāng)變量取連續(xù)值時(shí)對(duì)應(yīng)條件概率分布函數(shù)，而變量取離散值時(shí)對(duì)應(yīng)條件概率表），它“定量地”給出當(dāng)父節(jié)點(diǎn)集合取值為時(shí)，他們共同的子節(jié)點(diǎn)取值的條件概率。沒(méi)有父節(jié)點(diǎn)的用先驗(yàn)概率進(jìn)行信息表達(dá)。本文中，“變量”和“節(jié)點(diǎn)”將混合使用。給定貝葉斯網(wǎng)絡(luò)，其所表示

13、的聯(lián)合概率分布可以根據(jù)所包含的信息因式分解為: (1)貝葉斯網(wǎng)絡(luò)中任意相連的三個(gè)節(jié)點(diǎn)，和存在三種可能的連接場(chǎng)景，（1）（簡(jiǎn)稱(chēng)“順序接接”），（2）（簡(jiǎn)稱(chēng)“尾部連接”），（3）（簡(jiǎn)稱(chēng)“頭部連接”或“結(jié)構(gòu)”）。圖中任意存在路徑（即連接兩個(gè)節(jié)點(diǎn)的邊集合）的兩個(gè)節(jié)點(diǎn)之間的邊都可以分解為這三種結(jié)構(gòu)。例如圖1中的是連接和的路徑，但不是唯一的路徑，因?yàn)檫€存在路徑。能夠割斷兩個(gè)節(jié)點(diǎn)之間所有路徑的最小節(jié)點(diǎn)集合稱(chēng)作最小“割集”（seperator），例如圖1中和的最小割集是空集。割集對(duì)應(yīng)到中的。為了討論方便，在此簡(jiǎn)要介紹一些基礎(chǔ)概念和定理。定義1 忠實(shí)性（Faithfulness）。一個(gè)貝葉斯網(wǎng)絡(luò)和一個(gè)聯(lián)合分布是

14、相互忠實(shí)的，當(dāng)且僅當(dāng)蘊(yùn)含在的結(jié)構(gòu)里的每一個(gè)條件獨(dú)立性關(guān)系也同樣存在于中，即。1定義2 馬爾科夫毯。一個(gè)變量的馬爾科夫毯記為，它是滿(mǎn)足以下條件的變量集合：， （2）而其中最小的馬爾科夫毯稱(chēng)為馬爾科夫邊界（Markov boundary）。定理1 假定忠實(shí)性滿(mǎn)足，對(duì)應(yīng)于聯(lián)合分布的貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)，（1）任意節(jié)點(diǎn)的馬爾科夫毯是唯一的，包含其父、子和配偶節(jié)點(diǎn)（參考圖1），（2），。引理1 假定忠實(shí)性滿(mǎn)足，（1）一個(gè)變量的馬爾科夫毯和其馬爾科夫邊界是一致的，（2）的父、子和配偶節(jié)點(diǎn)組成了最優(yōu)特征子集。（根據(jù)定義2和定理1容易證明）定理2 兩個(gè)有向無(wú)環(huán)圖是等價(jià)的，當(dāng)且僅當(dāng)他們有相同的無(wú)向圖和相同的結(jié)構(gòu)。定

15、義3 后代（Descendant）。貝葉斯網(wǎng)絡(luò)中，如果存在一條從到的有向邊，但不存在從到的有限邊，那么就說(shuō)是的后代。的后代節(jié)點(diǎn)集記為。定義4 非后代（Non-Descendant）。貝葉斯網(wǎng)絡(luò)中，的除了后代節(jié)點(diǎn)的其他節(jié)點(diǎn)集稱(chēng)作非后代節(jié)點(diǎn)集，記為。定理3 如果一個(gè)貝葉斯網(wǎng)絡(luò)忠實(shí)于聯(lián)合概率分布，那么和在中是直接相連接的，當(dāng)且僅當(dāng)對(duì)于任何不包含和的集合，恒不成立。定義4 馬爾科夫條件（Markov condition）。在一個(gè)貝葉斯網(wǎng)絡(luò)中，當(dāng)已知，任意的除外的非后代節(jié)點(diǎn)條件獨(dú)立于 ， (3)當(dāng)忠實(shí)性滿(mǎn)足，我們?nèi)菀椎茫海?(4) 2.3 算法特征和分類(lèi)參考貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法分類(lèi)方法，我們將已發(fā)表的

16、推導(dǎo)算法分為約束和非約束學(xué)習(xí)。所謂約束學(xué)習(xí)（Constraint Learning，CL），屬于求解經(jīng)典的約束滿(mǎn)足問(wèn)題（Constraint Satisfaction Problems, CSP）。CL類(lèi)算法普遍基于條件獨(dú)立（簡(jiǎn)稱(chēng)CI）測(cè)試，而在實(shí)際應(yīng)用中用于訓(xùn)練的數(shù)據(jù)樣本數(shù)目相對(duì)于問(wèn)題特征所構(gòu)成的高維度空間十分稀疏有限。例如一個(gè)應(yīng)用包含16個(gè)二值特征變量，可能的值組合是。如果把每個(gè)組合看成一個(gè)單元格，當(dāng)我們擁有1024（）個(gè)樣本，意味著至多1.56%的單元格能分配到一個(gè)觀測(cè)值；即便觀測(cè)樣本數(shù)提高一個(gè)量級(jí)，也只是覆蓋了不超過(guò)15.6%的區(qū)域。當(dāng)面對(duì)更多的特征變量，并且每個(gè)變量可能的取值不止兩個(gè)

17、，問(wèn)題空間的復(fù)雜度將呈指數(shù)級(jí)增長(zhǎng)。目前通用的統(tǒng)計(jì)測(cè)試可靠性判斷標(biāo)準(zhǔn)是要求每個(gè)單元格至少具備5個(gè)觀測(cè)值6，這意味著面對(duì)16個(gè)二值特征變量時(shí)，即使我們有51200個(gè)樣本也只是覆蓋不超過(guò)16%的組合。當(dāng)樣本數(shù)不夠時(shí)，統(tǒng)計(jì)測(cè)試的結(jié)果變得不可靠。如果“強(qiáng)行”信任測(cè)試結(jié)果，將引入錯(cuò)誤的決策；而任何早期引入的錯(cuò)誤將導(dǎo)致更多的“級(jí)聯(lián)”錯(cuò)誤，最終輸出不佳甚至極差的結(jié)果。實(shí)際應(yīng)用里，一般會(huì)預(yù)先進(jìn)行類(lèi)似每單元格至少5個(gè)樣本的檢查（簡(jiǎn)稱(chēng)“可靠性測(cè)試”），如果該條件不滿(mǎn)足，該統(tǒng)計(jì)測(cè)試將被放棄。這個(gè)措施的后果是當(dāng)沒(méi)有更多可靠的測(cè)試可以被進(jìn)行時(shí)，CL算法不得不提前結(jié)束搜索。非約束學(xué)習(xí)的典型策略是基于打分+搜索（Scorin

18、g +Search-based，S&S） - 基于一個(gè)預(yù)定義的打分規(guī)則（很多選擇，比如MDL、BDeu等4），以及一個(gè)啟發(fā)式技術(shù)（比如爬山、退火等），迭代修改當(dāng)前狀態(tài)直至某個(gè)搜索停止條件（比如新的狀態(tài)得分比上一個(gè)裝填得分差）滿(mǎn)足并輸出結(jié)果。到目前為止，關(guān)于推導(dǎo)馬爾科夫毯的工作普遍屬于約束學(xué)習(xí)，這可以歸結(jié)為兩個(gè)緣由：n 我們能夠清晰定義出目標(biāo) - 馬爾科夫毯的概率和拓?fù)涮卣餍畔?，這兩部分信息的聯(lián)合有助于定義有效學(xué)習(xí)的約束條件。具體來(lái)說(shuō)，這兩個(gè)信息讓我們能夠識(shí)別出馬爾科夫真元素或/和假正（false positive）元素；n 然而，這兩個(gè)信息并不會(huì)幫助到我們建立局部和全局得分之間的關(guān)聯(lián)。具體來(lái)說(shuō)

19、，我們?cè)诓涣私饩植拷Y(jié)構(gòu)（這恰是我們希望推導(dǎo)的）的前提下，無(wú)法準(zhǔn)確推導(dǎo)局部得分，只有從全局得分入手。而全局得分的提高無(wú)法保證所關(guān)注的特定變量的局部得分也提高。即使我們能找到這個(gè)關(guān)聯(lián)，學(xué)習(xí)全局結(jié)構(gòu)的代價(jià)也將讓我們望而卻步。 因此，雖然基于S&S的學(xué)習(xí)策略在BN的推導(dǎo)上獲得了更大成功，在MB推導(dǎo)上目前尚沒(méi)有有效的實(shí)施手段，鮮有相關(guān)研究的發(fā)表。在回顧已知的工作時(shí)，我們將按約束和非約束區(qū)分，而前者相關(guān)的工作更多，故篇幅占用也更多。已知基于約束學(xué)習(xí)的算法可進(jìn)一步分成兩大類(lèi)：n 基于馬爾科夫毯的條件獨(dú)立（CI）特性設(shè)計(jì)的算法。該類(lèi)算法直接尋找目標(biāo)和非集合的“割集”，即依據(jù)公式（2）。此類(lèi)算法的搜索策略簡(jiǎn)單、

20、時(shí)間效率高，但實(shí)際應(yīng)用時(shí)學(xué)習(xí)效果不佳。K&S算法可以算是此類(lèi)算法最早的一個(gè)工作，而引用頻次相當(dāng)高的IAMB也是屬于該類(lèi)。n 基于拓?fù)湫畔⒃O(shè)計(jì)的算法。此類(lèi)算法檢查單獨(dú)的和之間的條件獨(dú)立關(guān)系，所需要的條件集合（或割集）通常比要小許多，因此條件獨(dú)立測(cè)試的可信度提高，學(xué)習(xí)效果相對(duì)更高。該類(lèi)算法的第突破性工作出現(xiàn)在2003年左右7。2.4 挑選標(biāo)準(zhǔn)和討論維度我們將從約束和非約束類(lèi)別里分別挑選出開(kāi)創(chuàng)性和/或里程碑的工作，盡量做到不遺漏典型貢獻(xiàn)。針對(duì)每個(gè)算法，將從幾個(gè)維度進(jìn)行討論：n 提出背景和假設(shè)n 核心學(xué)習(xí)/搜索策略n 理論正確與否n 學(xué)習(xí)效率n 學(xué)習(xí)效果（又稱(chēng)數(shù)據(jù)效率、樣本效率）n 實(shí)用性n 輸出的信

21、息n 可提高方向考慮到討論方便、自包含以及實(shí)用參考價(jià)值，將整理并附上重要的算法偽代碼（片段）。偽代碼描述將忠實(shí)反映原工作，但統(tǒng)一相關(guān)變量符號(hào)，并做必要擴(kuò)展細(xì)化。3 約束學(xué)習(xí)I：基于全局條件獨(dú)立信息的搜索3.1 K&S算法算法K&S2在1996發(fā)表在ICML年會(huì)上。作者K&S認(rèn)為我們不可能擁有能完全預(yù)測(cè)目標(biāo)的所有特征（實(shí)際情況是我們也不知道全集是什么，這導(dǎo)致我們不但不可能擁有所有特征，甚至很有可能包含錯(cuò)誤的特征），因此預(yù)測(cè)問(wèn)題演變?yōu)樘卣髯兞考虾湍繕?biāo)變量的條件概率分布建模，。當(dāng)給定一組觀測(cè)值，預(yù)測(cè)變成了選擇能最大化的。如果我們希望找一個(gè)能“代表”的子集，理想的選擇是基于的條件分布接近于，即。信息

22、熵衡量一個(gè)分布的不確定性，信息互熵（cross-entropy）則衡量?jī)蓚€(gè)分布和的“距離”，。作者K&S從信息熵和互熵角度證明了是最理想的子集，即比任何其他的都更接近。K&S的工作和Singh和Provan發(fā)表在1996年ICML的另一個(gè)工作8類(lèi)似，后者嘗試基于選擇的特征子集來(lái)訓(xùn)練貝葉斯網(wǎng)絡(luò)分類(lèi)器，而在選擇標(biāo)準(zhǔn)上也利用了信息熵。在理論的實(shí)踐上，作者K&S也討論了前向（forward）和后向選擇（backward selection）哪種搜索策略更適合馬爾科夫毯的推導(dǎo)。文獻(xiàn)8提出的算法是基于前向選擇，從空集合開(kāi)始，每次選擇一個(gè)能帶來(lái)最大信息增益的變量直到?jīng)]有更多增益能獲得。K&S認(rèn)為該選擇策略過(guò)

23、于貪婪，很可能將搜尋導(dǎo)向錯(cuò)誤的方向。因此，算法K&S選擇了基于后向選擇的搜索策略 - 從特征全集開(kāi)始，每次挑選并刪除滿(mǎn)足的變量，直到?jīng)]有更多變量可挑選。K&S算法需要兩個(gè)參數(shù)，（1）要保留多少個(gè)變量，即預(yù)測(cè)，（2）條件獨(dú)立測(cè)試?yán)锏脑试S的最大。兩條件中任一個(gè)滿(mǎn)足時(shí)，搜索即停止，而此時(shí)所得的即認(rèn)為是目標(biāo)馬爾科夫毯。顯然，我們事先并無(wú)法預(yù)知目標(biāo)馬爾科夫毯的大小，如果將參數(shù)設(shè)置過(guò)大，時(shí)間效率將因?yàn)樗阉骺杀M早結(jié)束而提高，但輸出的不準(zhǔn)確。關(guān)于第二個(gè)參數(shù)，如果設(shè)置較小，算法將從兩個(gè)方面受益：（1）條件獨(dú)立測(cè)試的可靠性更高，（2）時(shí)間復(fù)雜度降低。但隨之而來(lái)的代價(jià)是無(wú)法“刪除”所有非元素，從而無(wú)法輸出準(zhǔn)確的。所

24、以，K&S算法是近似的，無(wú)法保證一定輸出準(zhǔn)確的馬爾科夫毯。即便該算法只能實(shí)現(xiàn)近似推導(dǎo)，K&S的工作仍被視為該研究方向的開(kāi)山之作。K&S算法的搜索策略也被后繼同類(lèi)算法所參考，而其自身的缺陷也被加以重視和避免。3.2 GSMB算法GS算法9首次發(fā)表于1999年的NIPS會(huì)議上，作者希望借助“經(jīng)濟(jì)”的局部（鄰居）推導(dǎo)，之后 “整合”這些局部結(jié)構(gòu)信息以獲得完整的貝葉斯網(wǎng)絡(luò)。這里的“局部結(jié)構(gòu)信息”即指馬爾科夫毯，而該推導(dǎo)策略在當(dāng)時(shí)相比于傳統(tǒng)的全局推導(dǎo)是一個(gè)創(chuàng)新。我們?cè)谶@里只關(guān)心該工作里的核心部分 算法GSMB（Grow-Shrink based Markov Blanket induction），它負(fù)責(zé)

25、推導(dǎo)具體變量的馬爾科夫毯。其推導(dǎo)過(guò)程由兩個(gè)步驟組成：先增長(zhǎng)（Grow），后裁剪（Shrink），因此得名。增長(zhǎng)階段執(zhí)行的是貪婪的啟發(fā)策略，基于發(fā)現(xiàn)的候選馬爾科夫毯集合做條件獨(dú)立測(cè)試，只要發(fā)現(xiàn)一個(gè)變量和目標(biāo)變量關(guān)于條件獨(dú)立，則認(rèn)為為新的馬爾科夫毯候選元素并添加中。該策略導(dǎo)致增長(zhǎng)階段結(jié)束時(shí)會(huì)包含一些假正（False positive）元素，因此需要隨后的裁剪階段里檢查每個(gè)的元素，找出并刪除假正變量。而這一步驟所基于的條件也直接明了 任何一個(gè)中的元素如果和目標(biāo)變量關(guān)于條件獨(dú)立，則可以將刪除；迭代執(zhí)行這個(gè)過(guò)程，直到中沒(méi)有這樣的存在 輸出的即我們所要找的。GSMB算法屬于約束學(xué)習(xí)，將受到CI測(cè)試（即）準(zhǔn)

26、確性的影響。在假設(shè)CI測(cè)試準(zhǔn)確的前提下，GSMB算法可被證明為正確的。該算法簡(jiǎn)單易實(shí)現(xiàn)，學(xué)習(xí)效率高，時(shí)間復(fù)雜度屬于層級(jí)。但是，該算法在實(shí)際應(yīng)用中的推導(dǎo)準(zhǔn)確率表現(xiàn)可能很差。在增長(zhǎng)階段，由于配偶節(jié)點(diǎn)較晚進(jìn)入導(dǎo)致可能引入錯(cuò)誤的節(jié)點(diǎn)。而一旦有錯(cuò)誤節(jié)點(diǎn)被引入（算法1的第6行），將持續(xù)誤導(dǎo)隨后迭代里的判斷并引入更多的假正進(jìn)。直接的后果是大大降低后面的測(cè)試的可靠性，當(dāng)再無(wú)可靠的CI測(cè)試可參考，搜索將不得不停止，而此時(shí)很可能不但包含假正，還僅只有部分的馬爾科夫毯元素；即使在裁剪步驟里能夠刪除全部的假正，最終輸出的依舊是不完整的馬爾科夫毯。這個(gè)由于CI測(cè)試?yán)锼婕暗淖兞浚ɑ蜃杂啥萬(wàn)reedom）太多而導(dǎo)致每個(gè)取

27、值組合的可用觀測(cè)值數(shù)目可能很少，甚至為0，引發(fā)測(cè)試不可靠甚至（嚴(yán)重）影響統(tǒng)計(jì)學(xué)習(xí)的現(xiàn)象稱(chēng)為數(shù)據(jù)/樣本效率（Data/Sample efficiency）問(wèn)題。給定同樣的訓(xùn)練樣本，如果算法A輸出的準(zhǔn)確率高于算法B，我們稱(chēng)算法A的數(shù)據(jù)效率更高。這是統(tǒng)計(jì)學(xué)習(xí)算法除了時(shí)間、空間效率之外，很重要的一個(gè)衡量指標(biāo)。GS、IAMB以及他們的衍生算法由于固有的搜索策略局限，普遍數(shù)據(jù)效率不高10, 11。算法1：GS。輸入： - 目標(biāo)變量 - 數(shù)據(jù)集/訓(xùn)練集 - 顯著性門(mén)限值輸出：的馬爾科夫毯01. ；/增長(zhǎng)(Grow)階段02. DO03. ;04. FOR() DO05. IF() THEN06. ;07.

28、; / 跳轉(zhuǎn)到第3行08. BREAK;09. WHILE ;/ 裁剪(Shrink)階段10. DO11. ;12. FOR() DO13. IF() THEN14. ;15. ; 16. BREAK; / 跳轉(zhuǎn)到第11行17. WHILE ;18. RETURN ;3.3 IAMB及其派生算法IAMB算法12首次發(fā)表于2003年，全名為Incremental Association Markov Blanket。它繼承了GSMB算法的兩步驟策略：先（貪婪）增長(zhǎng)，后裁剪（假正元素）。裁剪階段兩者完全一致，增長(zhǎng)階段存在一個(gè)區(qū)別：IAMB會(huì)對(duì)通過(guò)CI測(cè)試的候選元素（參考GSMB算法第5行）進(jìn)行排

29、序，挑選出“最可能”的候選馬爾科夫毯元素，即和目標(biāo)變量條件依賴(lài)度最高的。雖然這個(gè)選擇過(guò)程依舊是貪婪決策，相比于GS更充分利用了當(dāng)下的信息，因此降低了往添加假正元素的可能性。由于GSMB算法發(fā)表時(shí)是以學(xué)習(xí)貝葉斯網(wǎng)絡(luò)為目標(biāo)，而IAMB是專(zhuān)門(mén)針對(duì)推導(dǎo)馬爾科夫毯提出的，所以后者在該方向的引用頻次和知名度更高。IAMB繼承了GSMB算法低數(shù)據(jù)效率的問(wèn)題，例如，給定經(jīng)典的Alarm問(wèn)題，當(dāng)給定相同的訓(xùn)練集大?。ɡ?000），IAMB算法輸出的馬爾科夫毯的平均準(zhǔn)確率為49%，而IPC-MB算法為99%13。IAMB的作者也意識(shí)到這個(gè)問(wèn)題，提出了三個(gè)“改良”版本：InterIAMB、IAMBnPC和Inte

30、rIAMBnPC。InterIAMB將增長(zhǎng)-裁剪兩個(gè)階段交替執(zhí)行，而原來(lái)的IAMB里，完全執(zhí)行完增長(zhǎng)階段才開(kāi)始執(zhí)行裁剪階段。IAMBnPC算法是將經(jīng)典的PC算法應(yīng)用于裁剪階段，但它忽視了增長(zhǎng)階段所獲得的有可能并不包含所有的元素，這將導(dǎo)致輸出仍然不完整。當(dāng)將這兩個(gè)算法的思路合并后即為InterIAMBnPC，它的時(shí)間復(fù)雜度在這三個(gè)算法中最高。相比于IAMB，這三個(gè)算法的數(shù)據(jù)效率都有不同程度的提高，因此實(shí)際應(yīng)用的準(zhǔn)確率能得到提升，但是時(shí)間復(fù)雜度也有不同幅度的增加。3.4 Fast-IAMBFast-IAMB算法 14發(fā)表于2005年的ICDM年會(huì)，它實(shí)際上是InterIAMB的升級(jí)版本。相比于In

31、terIAMB，該算法有兩個(gè)不同：n 條件獨(dú)立性檢查選擇了統(tǒng)計(jì)；n 增長(zhǎng)階段里每個(gè)迭代選擇一個(gè)或多個(gè)變量添加到中。作者認(rèn)為第二個(gè)策略的采用將提高時(shí)間效率，但這個(gè)更貪婪的策略將導(dǎo)致更多的假正元素被添加到，從而導(dǎo)致IAMB增長(zhǎng)步驟已知的問(wèn)題惡化 該步驟更早終止，且終止時(shí)包含更多的假正變量（自然包含更少的真元素）。3.5 K-IAMBK-IAMB和PCMB（在下章節(jié)里介紹）在2007被同時(shí)發(fā)表在文獻(xiàn)15。其作者認(rèn)為PCMB等（約束學(xué)習(xí)II類(lèi)）算法所要求的忠實(shí)性假設(shè)過(guò)于嚴(yán)格，而IAMB算法的數(shù)據(jù)效率太低。K-IAMB實(shí)質(zhì)是IAMB的一種隨機(jī)版本，它允許算法使用者指定一個(gè)參數(shù)，該參數(shù)反映了對(duì)搜索貪婪度和

32、隨機(jī)性所能接受的一個(gè)“度”。當(dāng)時(shí)，K-IAMB等價(jià)于IAMB，即在增長(zhǎng)階段的每個(gè)迭代里總是選擇當(dāng)下和條件相關(guān)性最強(qiáng)的元素。當(dāng)數(shù)據(jù)樣本不充足時(shí)，這樣的決策顯然是有風(fēng)險(xiǎn)的。因此時(shí)，算法會(huì)從隨機(jī)選擇一個(gè)子集再執(zhí)行類(lèi)似算法1第5行的CI測(cè)試，并基于測(cè)試結(jié)果決策。3.6 -IAMB等算法-IAMB發(fā)表于2010年16，跟IAMB算法對(duì)比存在兩個(gè)差異點(diǎn)。其一是作者通過(guò)使用信息熵，而非條件互信息，來(lái)降低衡量?jī)蓚€(gè)變量的條件獨(dú)立性計(jì)算量。其二是算法希望一次選取多個(gè)候選變量進(jìn)入，例如和目標(biāo)變量相關(guān)性最高的兩個(gè)變量，這和Fast-IAMB如出一轍。然而，為了降低風(fēng)險(xiǎn)，作者提出了參數(shù)（其實(shí)是門(mén)限值），當(dāng)次相關(guān)變量和目

33、標(biāo)變量的相關(guān)性和最相關(guān)變量的相關(guān)性超過(guò)一定值時(shí)，方可同時(shí)被添加到。這個(gè)二次檢查的策略和K-IAMB類(lèi)似。盡管較IAMB有一定的改善，F(xiàn)ast-IAMB、K-IAMB和-IAMB并沒(méi)有在根本上解決此類(lèi)算法的數(shù)據(jù)效率低的缺陷。4 約束學(xué)習(xí)II：基于局部條件獨(dú)立信息的搜索在IAMB算法的追隨者繼續(xù)沿著那條路徑前進(jìn)的時(shí)候，有些人開(kāi)始另辟蹊徑來(lái)解決IAMB類(lèi)算法的低數(shù)據(jù)效率的問(wèn)題。他們的工作基礎(chǔ)是貝葉斯網(wǎng)絡(luò)DAG的拓?fù)湫畔?，特別是“截?cái)唷眱蓚€(gè)節(jié)點(diǎn)的割集（的信息）。雖然是和之間的最小割集，但對(duì)于單獨(dú)的和之間的割集往往遠(yuǎn)比小，例如圖1的和的最小割集是空集，而包含六個(gè)元素。除了推導(dǎo)策略迥然不同，II類(lèi)算法的輸

34、出相比I類(lèi)算法存在一個(gè)巨大的優(yōu)勢(shì)：能推導(dǎo)出更多的拓?fù)湫畔?。I類(lèi)算法僅僅告訴我們一個(gè)元素是否屬于，而II類(lèi)算法能(1)區(qū)分目標(biāo)變量的父子和配偶集合,(2)從父子集合里分離出部分孩子（節(jié)點(diǎn)）,(3)一部分結(jié)構(gòu)。4.1 MMPC/MB和HITON-PC/MB算法MMPC/MB算法17發(fā)表于2003年的ACM KDD年會(huì)，其第一作者和IAMB的一致，這間接反映了該作者也意思到IAMB算法的局限。MMPC全稱(chēng)是Max-Min Parents and Children，它的任務(wù)是推導(dǎo)特定變量的父子節(jié)點(diǎn)；MMMB的全稱(chēng)是Max-Min Markov Blanket，即推導(dǎo)一個(gè)變量的馬爾科夫毯。MMMB依賴(lài)M

35、MPC來(lái)完成馬爾科夫毯的推導(dǎo)，這也是第一次將馬爾科夫毯的推導(dǎo)分解成分別推導(dǎo)父子節(jié)點(diǎn)和配偶節(jié)點(diǎn)。這個(gè)拆分策略將避免或出現(xiàn)在CI測(cè)試?yán)铮兄谔岣逤I測(cè)試的可靠性，繼而讓基于CI測(cè)試的結(jié)果所做的決策（比IAMB等）更準(zhǔn)確。HITON-PC/MB算法7同樣發(fā)表于2003年，它的總體策略和MMPC/MB如出一轍，為了節(jié)省篇幅不再單獨(dú)熬述。MMPC/MB和HITON-PC/MB都是針對(duì)馬爾科夫毯推導(dǎo)的重要嘗試和突破，但更復(fù)雜的啟發(fā)式策略也帶來(lái)了高的多的計(jì)算代價(jià)。然而，在2007年這兩個(gè)算法都被證明都無(wú)法恒保證輸出正確的馬爾科夫毯，有興趣的讀者可以參考文獻(xiàn)15里提供的一個(gè)反例。鑒于此，我們?cè)诖藶榱斯?jié)約篇幅

36、都沒(méi)有單獨(dú)給出兩個(gè)算法的偽代碼，但他們的主要流程被PCMB和IPC-MB所繼承，讀者可以參考算法3（IPC-MB）。4.2 PCMB算法PCMB算法15最初發(fā)表在2007年的Journal of Approximate Reasoning上，它的全稱(chēng)是Parents and Children based Markov Boundary。其作者同樣意識(shí)到IAMB及其衍生算法在實(shí)際應(yīng)用中的局限，并充分認(rèn)可MMPC/MB和HITON-PC/MB的作者所提出從拓?fù)浣嵌瘸霭l(fā)進(jìn)行搜索策略的設(shè)計(jì)。雖然這個(gè)新的方向有貝葉斯網(wǎng)絡(luò)研究者所積累的大量理論依據(jù)，但MMPC/MB和HITON-PC/MB兩個(gè)具體算法都存

37、在設(shè)計(jì)缺陷，這無(wú)法保證它們恒輸出正確的結(jié)果。PCMB的作者首次在文獻(xiàn)15中給出了反例，因而他們提出的PCMB屬于“約束學(xué)習(xí)II”類(lèi)已知發(fā)表的工作中首個(gè)能進(jìn)行正確推導(dǎo)馬爾科夫毯的算法。PCMB算法類(lèi)似MMPC/MB和HITON-PC/MB，采用了分而治之的策略 分別學(xué)習(xí)父子節(jié)點(diǎn)和配偶節(jié)點(diǎn)。由于PCMB算法和隨后將介紹的IPC-MB算法的主體架構(gòu)相似，因此讀者可以參考算法3來(lái)了解其總體設(shè)計(jì)。PCMB算法和IPC-MB算法的主要差別是RecognizePC（見(jiàn)算法2），該過(guò)程在原文獻(xiàn)中即GetPCD。RecognizePC負(fù)責(zé)推導(dǎo)一個(gè)變量的候選父子集合，有可能輸出后代節(jié)點(diǎn)。PCMB算法的Recogn

38、izePC實(shí)際是在IAMB的增長(zhǎng)-裁剪過(guò)程前增加一個(gè)在候選集合里進(jìn)行“裁剪”的步驟，故總體上是SGS（Shrink-Grow-Shrink）。本質(zhì)上，這是一個(gè)混合了后向和前向選擇的搜索策略。然而，過(guò)度“謹(jǐn)慎”的檢查導(dǎo)致PCMB算法時(shí)間復(fù)雜度甚高10, 11。算法2：RecognizePC（對(duì)應(yīng)原PCMB文獻(xiàn)中的GetPCD）。輸入： - 目標(biāo)變量 - 候選鄰居 - 數(shù)據(jù)集/訓(xùn)練集 - 顯著性門(mén)限值輸出：的候選父子集合01. ; 02. DO/ 刪除中的假正03. FOR() DO04. ;05. FOR() DO06. IF()THEN07. ; /添加最佳候選到08. ; 09. ;10.

39、;/從中刪除假正11. FOR() DO12. ;13. FOR() DO14. IF()THEN15. ;16. WHILE 在本輪循環(huán)有改變;17. RETURN ;4.3 IPC-MB算法IPC-MB算法18最初發(fā)表在2007年的澳大利亞AI年會(huì)上，而提供了更完善證明的版本發(fā)表在2008年的加拿大人工智能年會(huì)上10。IPC-MB全稱(chēng)是Iterative Parent-Child based search of Markov Blanket。它同PCMB一樣，基于拓?fù)湫畔⒃O(shè)計(jì)，選擇了分而治之的策略，通過(guò)迭代的推導(dǎo)父子節(jié)點(diǎn)（這一更局部的信息）來(lái)完成馬爾科夫毯的推導(dǎo)。然而，在如何推導(dǎo)直接相連接

40、的節(jié)點(diǎn)（父子節(jié)點(diǎn)）這個(gè)核心子策略上，IPC-MB選擇了和PCMB完全不同的策略：PCMB采用的是前向選擇，而IPC-MB采用的是后向選擇。PCMB的策略在上一節(jié)已經(jīng)有介紹，此處著重介紹IPC-MB的后向選擇。而關(guān)于前向和后向選擇的孰優(yōu)孰劣可以參考章節(jié)2.1里的簡(jiǎn)單討論，更詳細(xì)的討論可以參考K&S的工作2。IPC-MB（見(jiàn)算法3）是依賴(lài)RecognizePC過(guò)程（見(jiàn)算法4）來(lái)完成對(duì)父子節(jié)點(diǎn)的判斷。它的基本思路是當(dāng)給定一個(gè)節(jié)點(diǎn)時(shí)，先假設(shè)其他的節(jié)點(diǎn)和都相連（即都為真的父子節(jié)點(diǎn)），隨后通過(guò)一系列的CI測(cè)試來(lái)刪除鄰居集合里的假正元素，直到?jīng)]有更多的CI測(cè)試可被執(zhí)行。與PCMB算法判斷一個(gè)元素是否為真的父

41、子節(jié)點(diǎn)不同，判斷假正元素的條件更為簡(jiǎn)單 只要存在一個(gè)關(guān)于節(jié)點(diǎn)和節(jié)點(diǎn)的割集，即可判斷為假正，并從里刪除。在判斷假正元素時(shí)，IPC-MB的作者從空集合開(kāi)始判斷其是否是和之間的割集；在第二個(gè)迭代里，允許割集合包含一個(gè)元素，并尋找可“割斷”的變量；以此類(lèi)推，直到?jīng)]有更多的CI測(cè)試能夠被執(zhí)行。這個(gè)策略使得用于判斷假正的CI測(cè)試總是能夠基于最小的割集，充分保障了CI測(cè)試的可靠性。 算法3：IPC-MB。輸入： - 目標(biāo)變量 - 數(shù)據(jù)集/訓(xùn)練集 - 顯著性門(mén)限值輸出：的馬爾科夫毯01. ； /候選鄰居02. RecognizePC(); /候選父子03. ;04. FOR()DO05. ;06. Recog

42、nizePC()07. IF () THE /刪除假正08. ;09. ELSE /發(fā)現(xiàn)真父子，并進(jìn)一步推導(dǎo)配偶10. FOR(AND )DO11. IF()THEN12. ; /發(fā)現(xiàn)一個(gè)配偶13. RETURN ;算法4：RecognizePC（IPC-MB版本）。輸入： - 目標(biāo)變量 - 候選鄰居 - 數(shù)據(jù)集/訓(xùn)練集 - 顯著性門(mén)限值輸出：的候選父子集合14. ;15. ; /初始化CutSet Size16. DO17. FOR() DO18. FOR( with ) DO19. IF()THEN20. ; /假正父子21. ; /緩存供算法2使用22. BREAK; /跳轉(zhuǎn)到第4行23

43、. IF() THEN /統(tǒng)一刪除假正24. ;25. ;26. ;27. WHILE ;28. RETURN ;IPC-MB算法被證明是正確的，其數(shù)據(jù)效率和PCMB相當(dāng)，但它的時(shí)間效率比PCMB要高許多。例如在一個(gè)實(shí)驗(yàn)里它比PCMB節(jié)省了95%左右的CI測(cè)試次數(shù)10。雖然相比于IAMB的時(shí)間效率還是要低不少，但該算法在“瘦”網(wǎng)絡(luò)（即網(wǎng)絡(luò)連接不太稠密）問(wèn)題里表現(xiàn)出與IAMB匹敵的時(shí)間效率但高得多的準(zhǔn)確率。4.4 MBOR算法MBOR算法19發(fā)表于2008年的ECML/PKDD年會(huì)上，也是其作者在觀察到GS和IAMB分支的算法數(shù)據(jù)效率不高后設(shè)計(jì)的，并聲稱(chēng)結(jié)合了PCMB和IAMB的優(yōu)點(diǎn)，并同時(shí)規(guī)避

44、了他們的缺點(diǎn)。MBOR的全稱(chēng)是Markov Boundary search using the OR condition。MBOR沿用了PCMB和IPC-MB的搜索策略，核心差異在于判斷兩個(gè)變量和是否相連的條件。PCMB和IPC-MB在判斷時(shí)要求且（AND）都滿(mǎn)足（算法4第7行），而MBOR只要求其中一個(gè)條件滿(mǎn)足，即或（OR）。策略O(shè)R是一把雙刃劍：真元素容易進(jìn)入，而假正元素也不例外。MBOR算法的總體思路是依賴(lài)基于OR條件的弱學(xué)習(xí)器來(lái)構(gòu)成能輸出正確的強(qiáng)學(xué)習(xí)器，這個(gè)思想類(lèi)似集成學(xué)習(xí)（ensemble learning）。MBOR算法由三個(gè)階段組成：n 學(xué)習(xí)的超集。這是通過(guò)分別學(xué)習(xí)以及合并和的超

45、集獲得。（1）學(xué)習(xí)超集，算法設(shè)計(jì)了一個(gè)“粗糙”過(guò)濾策略 將CI測(cè)試的條件集合限制為空集或包含一個(gè)變量。這個(gè)過(guò)程的輸出為，而當(dāng)發(fā)現(xiàn)可被刪除的變量時(shí)，同IPC-MB一樣記錄對(duì)應(yīng)的。（2）學(xué)習(xí)的超集，針對(duì)每一個(gè)不屬于的，嵌套執(zhí)行一個(gè)先增長(zhǎng)-后裁剪的檢查。增長(zhǎng)步驟里，算法檢查每個(gè)不屬于的，如果能通過(guò)類(lèi)似算法3第11行的測(cè)試（測(cè)試?yán)锏臈l件集合為），則認(rèn)為是候選配偶，并添加到集合。這個(gè)步驟里，由于可能為空或包含一個(gè)變量，所以將包含至多2個(gè)變量。隨后的裁剪步驟將檢查和刪除當(dāng)前能識(shí)別的里的假正元素（不保證全部刪除）。n 基于推導(dǎo)。原算法里這個(gè)階段同樣包含兩個(gè)子步驟。第一個(gè)子步驟是從第一階段獲得的的超集中刪除假

46、正，而這個(gè)步驟和IAMB的裁剪步驟如出一轍。不同的是IAMB的裁剪步驟里，條件子集是，而此處（作者沒(méi)有明講，但按經(jīng)驗(yàn)以及作者重點(diǎn)關(guān)注數(shù)據(jù)效率上判斷）選擇的是滿(mǎn)足條件的最小子集。我們判斷作者的實(shí)現(xiàn)應(yīng)該同IPC-MB的RecognizePC（算法4）過(guò)程，從空集開(kāi)始迭代搜尋。第二個(gè)子步驟是針對(duì)每一個(gè)執(zhí)行第一個(gè)子步驟并輸出，如果屬于的則將添加到，這是OR條件的貫徹。n 推導(dǎo)配偶。這個(gè)步驟同IPC-MB的配偶推導(dǎo)，但計(jì)算復(fù)雜度要高不少。MBOR算法為了保證數(shù)據(jù)效率而設(shè)計(jì)了弱而快的學(xué)習(xí)器，但為了保證準(zhǔn)確性又不得不增加了繁瑣的檢查機(jī)制。作者并沒(méi)有給出可信服的證明，而時(shí)間復(fù)雜度將高于IPC-MB。4.5 D

47、OS算法DOS算法20發(fā)表在2011年的PAKDD年會(huì)上，全稱(chēng)是Dynamic Ordering-based Search，它充分參考之前的MMPC/MB、PCMB和IPC-MB。DOS算法的兩個(gè)步驟如下：n 推導(dǎo)。這步對(duì)應(yīng)IPC-MB（算法3）的第2行，作者在IPC-MB的RecognizePC（算法4）基礎(chǔ)之上添加了一個(gè)微創(chuàng)新的啟發(fā)策略。一旦發(fā)現(xiàn)可以變量和的割集，除了執(zhí)行算法4的第22和23行的動(dòng)作，作者對(duì)每個(gè)進(jìn)行計(jì)數(shù)更新，并根據(jù)計(jì)數(shù)對(duì)他們按從高到低在排序。計(jì)數(shù)是根據(jù)出現(xiàn)在里的頻次，作者認(rèn)為里的的頻次將較高。這個(gè)啟發(fā)是合理的，因?yàn)闈M(mǎn)足這樣條件的和直接相連，更可能出現(xiàn)在和的通路上，即更可能出

48、現(xiàn)在里。這個(gè)信息將被用在從產(chǎn)生里，算法將優(yōu)先選擇包含高頻次的（如果有多個(gè)則對(duì)頻次求和再比較大?。 推導(dǎo)并刪除里的假正。該步驟和IPC-MB（算法3）的第412行完全一致。n DOS算法較IPC-MB參考了更多的拓?fù)湫畔ⅲ沟脮r(shí)間效率有可能獲得提升。5 約束學(xué)習(xí)III：基于邏輯回歸分析的過(guò)濾HITON-PC/MB和MMPC/MB算法已知無(wú)法保證正確的輸出，但它們比約束學(xué)習(xí)I類(lèi)的算法樣本效率要高許多，也開(kāi)創(chuàng)了新的學(xué)習(xí)策略。郭坤等人在2012年發(fā)表了名為RA-MMMB的算法 21，全名為Regress Analysis Max Min Markov Blanket。該算法期望利用MMMB算法的樣

49、本效率優(yōu)的特征進(jìn)行特征全集的預(yù)過(guò)濾，得到候選的馬爾科夫毯。隨后建立目標(biāo)變量與候選馬爾科夫毯的邏輯回歸方程，基于逐步后向回歸分析結(jié)果刪除錯(cuò)誤的和弱相關(guān)的變量（即所謂的兄弟節(jié)點(diǎn) 和目標(biāo)節(jié)點(diǎn)同父節(jié)點(diǎn)）。作者的實(shí)驗(yàn)顯示該算法優(yōu)于MMMB，說(shuō)明在刪除假正節(jié)點(diǎn)上確實(shí)有效。然而，作者并沒(méi)有給出算法的正確性證明。6 非約束學(xué)習(xí)前面兩節(jié)介紹的算法都屬于約束學(xué)習(xí)范疇。雖然非約束學(xué)習(xí)算法在貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)研究領(lǐng)域有很多工作，但直到最近才由Acid等研究人員在2013年的DMKD雜志發(fā)表了一篇關(guān)于馬爾科夫毯的非約束學(xué)習(xí)的文章22。作者在該文章里提出了兩個(gè)算法，分別叫DMB和RPDMB。DMB和RPDMB算法使用常

50、見(jiàn)的評(píng)分機(jī)制（例如BDeu等，關(guān)于他們的簡(jiǎn)短比較可以參考22），但通過(guò)將搜索局限在一個(gè)特殊的圖空間里來(lái)降低復(fù)雜度。由于作者的重心是應(yīng)用貝葉斯網(wǎng)絡(luò)于分類(lèi)問(wèn)題，這個(gè)圖空間包含了所有和目標(biāo)DAG分類(lèi)等價(jià)（Classification equivalence）的DAGs，作者將其命名為C-DAG（Class-focused DAG）23。雖然這個(gè)空間相對(duì)于全局空間縮小很多，但仍然是一個(gè)指數(shù)增長(zhǎng)的空間，故作者進(jìn)一步應(yīng)用了啟發(fā)式搜索策略來(lái)加速學(xué)習(xí)。文獻(xiàn)22中報(bào)告的實(shí)驗(yàn)結(jié)果顯示RPDMB（配合BDeu和MIT兩種評(píng)分機(jī)制）相比PCMB能夠輸出有競(jìng)爭(zhēng)力的準(zhǔn)確率的結(jié)果，但耗時(shí)要多許多?？紤]到PCMB的時(shí)間效率比

51、IPC-MB低許多，可以預(yù)測(cè)IPC-MB算法在時(shí)間效率上將遠(yuǎn)比RPDMB更有優(yōu)勢(shì)。即便如此，DMB和RPDMB仍不失為一個(gè)重要的嘗試。7 研究前景7.1 約束學(xué)習(xí)從既往已發(fā)表的工作來(lái)看，約束學(xué)習(xí)一般通過(guò)利用馬爾科夫毯的條件獨(dú)立性信息（I類(lèi)）或拓?fù)湫畔ⅲ↖I類(lèi)）來(lái)“約束”或“裁剪”搜索空間。雖然II類(lèi)算法能夠輸出更準(zhǔn)確的結(jié)果和更多的拓?fù)湫畔?，但需要消耗更多的?jì)算資源。未來(lái)的目標(biāo)在保持高數(shù)據(jù)效率的前提下降低時(shí)間效率，但存在以下制約進(jìn)一步提升的客觀事實(shí)：n 如果我們選擇前向選擇策略，努力的方向是用最小的代價(jià)識(shí)別出真正的馬爾科夫毯元素。然而，根據(jù)定理3，判斷是否和目標(biāo)變量相連的條件是要求不存在能讓他們

52、條件獨(dú)立的集合。這要求進(jìn)行“遍歷”測(cè)試，可能的嘗試是復(fù)用已經(jīng)確認(rèn)的元素信息來(lái)推導(dǎo)更多的元素，而不是每個(gè)元素的判斷都是從0開(kāi)始。同時(shí)，還要避免CI測(cè)試?yán)锏臈l件集合過(guò)大；n 如果我們選擇反向選擇策略，努力的方向則是用最小的代價(jià)識(shí)別出假正元素。IPC-MB是基于這個(gè)目標(biāo)設(shè)計(jì)的，并同時(shí)兼顧了CI測(cè)試?yán)飾l件集合盡量小的目標(biāo)。有兩個(gè)問(wèn)題目前影響該類(lèi)算法的時(shí)間效率：（1）推導(dǎo)的父子節(jié)點(diǎn)集合時(shí)，后代節(jié)點(diǎn)可能會(huì)無(wú)法被正確刪除，因而需要用到AND的檢查策略，（2）配偶節(jié)點(diǎn)需要做間接鑒定。K-IAMB所采取的當(dāng)數(shù)據(jù)樣本不充足時(shí)的折中策略其實(shí)是進(jìn)行二次驗(yàn)證，可以考慮在其他算法里嘗試，畢竟相對(duì)樣本不足是常態(tài)。RA-MM

53、MB所采用的基于回歸分析的二次過(guò)濾也是一個(gè)有趣的方向。或許可以嘗試基于回歸分析進(jìn)行“粗糙”地前置過(guò)濾，再基于更精細(xì)的推導(dǎo)算法進(jìn)行二次過(guò)濾。7.2 非約束學(xué)習(xí)目前非約束學(xué)習(xí)的算法還相當(dāng)稀少，從發(fā)表的兩個(gè)算法來(lái)看，側(cè)重分類(lèi)問(wèn)題，理解起來(lái)也相對(duì)比較復(fù)雜。鑒于S&S策略在貝葉斯網(wǎng)絡(luò)學(xué)習(xí)上所獲得的成功，以及馬爾科夫毯和貝葉斯網(wǎng)絡(luò)的關(guān)系，有理由相信其在馬爾科夫毯推導(dǎo)上還有很大的空間可供挖掘。從前面的討論可知：約束學(xué)習(xí)算法目標(biāo)時(shí)間效率優(yōu)于非約束學(xué)習(xí)算法，但面臨統(tǒng)計(jì)測(cè)試不可靠以及級(jí)聯(lián)出錯(cuò)的風(fēng)險(xiǎn)。IPC-MB、MBOR和DOS算法都嘗試去極力讓CI測(cè)試?yán)锏臈l件集合盡可能小。MBOR在其第一階段的做法啟發(fā)我們可否

54、先用條件集合很小的CI測(cè)試做一個(gè)快速的粗過(guò)濾，這有助于我們快速裁剪搜索空間，輸出一個(gè)接近的超集。在這之上，我們?cè)賾?yīng)用S&S策略來(lái)規(guī)避大條件集合CI測(cè)試所可能帶來(lái)的問(wèn)題。7.3 應(yīng)用文中著重圍繞特征選擇問(wèn)題討論了馬爾科夫毯，這歸因于特征選擇在整個(gè)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘研究和應(yīng)用中的重要基礎(chǔ)角色。由于馬爾科夫毯是貝葉斯網(wǎng)絡(luò)的重要局部結(jié)構(gòu)，可以通過(guò)先推導(dǎo)出該信息而獲得全局貝葉斯網(wǎng)絡(luò)，例如9, 24。考慮到局部推導(dǎo)可以并行化，運(yùn)行等待時(shí)間將有可能獲得較大縮短。此外，相關(guān)的工作也可能應(yīng)用于局部因果關(guān)系的推導(dǎo)25。結(jié)束語(yǔ) 馬爾科夫毯從1996年被證明是預(yù)測(cè)目標(biāo)的最優(yōu)子集后，至今有眾多的關(guān)于推導(dǎo)馬爾科夫毯的工作

55、。文中綜合分析了已發(fā)表工作的兩大分支 約束和非約束分析，而在約束學(xué)習(xí)類(lèi)里又進(jìn)一步分成了三個(gè)分支。本文累計(jì)覆蓋了17個(gè)典型工作，據(jù)查新所知，這是截止撰寫(xiě)本文時(shí)關(guān)于馬爾科夫毯推導(dǎo)研究的最綜合性的綜述。在介紹每個(gè)算法時(shí)，討論兼顧了理論和實(shí)用性，故該討論對(duì)研究和工程人員都有一定的參考價(jià)值?；谝延械墓ぷ魈攸c(diǎn)，文中同時(shí)給出了約束和非約束學(xué)習(xí)的可能機(jī)會(huì)，以及關(guān)于馬爾科夫毯的可能應(yīng)用。參考文獻(xiàn): 1 Pearl, J., Probabilistic reasoning in expert systems M 1988,San Matego: Morgan Kaufmann.2Koller, D. and M

56、. Sahami. Toward optimal feature selection. in the 13th International Conference on Machine Learning (ICML) C. 1996. Bari, Italy: Morgan Kaufmann.3Chickering, D.M., D. Geiger, and D. Heckerman, Learning Bayesian Network is NP-Hard R, 1994, Microsoft. p. 22.4Campos, C.P.d., Z. Zeng, and Q. Ji, Efficient structure learning of Bayesian networks using co