基于馬爾科夫邊界發(fā)現(xiàn)的因果特征選擇算法綜述

吳興宇 江兵兵 呂勝飛 王翔宇 陳秋菊 陳歡歡

高維數(shù)據(jù)為真實(shí)世界的機(jī)器學(xué)習(xí)任務(wù)帶來(lái)諸多挑戰(zhàn)，如計(jì)算資源和存儲(chǔ)資源的消耗、數(shù)據(jù)的過(guò)擬合,學(xué)習(xí)算法的性能退化[1]，而最具判別性的信息僅被一部分相關(guān)特征攜帶[2]．為了降低數(shù)據(jù)維度,避免維度災(zāi)難，特征選擇研究受到廣泛關(guān)注．大量的實(shí)證研究[3-5]表明，對(duì)于多數(shù)涉及數(shù)據(jù)擬合或統(tǒng)計(jì)分類(lèi)的機(jī)器學(xué)習(xí)算法，在去除不相關(guān)特征和冗余特征的特征子集上，通常能獲得比在原始特征集合上更好的擬合度或分類(lèi)精度．此外，選擇更小的特征子集有助于更好地理解底層的數(shù)據(jù)生成流程[6]．

傳統(tǒng)的特征選擇算法主要分為封裝法、過(guò)濾法和嵌入法三類(lèi)[7]．封裝法[8]為不同的特征子集訓(xùn)練一個(gè)學(xué)習(xí)器，評(píng)估其在該特征子集上的表現(xiàn)，決定所選特征子集．過(guò)濾法[9]使用一個(gè)評(píng)估函數(shù),為特征評(píng)分并選擇分?jǐn)?shù)較高的特征，因此不依賴(lài)額外的分類(lèi)器,更高效．嵌入法[10]將特征選擇過(guò)程嵌入學(xué)習(xí)過(guò)程中，同時(shí)搜索特征選擇空間和學(xué)習(xí)器參數(shù)空間,獲得特征子集．

傳統(tǒng)的特征選擇算法根據(jù)特征和目標(biāo)變量之間的相關(guān)性尋找相關(guān)特征子集[11]．然而，相關(guān)關(guān)系只能反映目標(biāo)變量和特征之間的共存關(guān)系，而無(wú)法解釋決定目標(biāo)變量取值的潛在機(jī)制[12-13]．一些研究表明[12-13]，因果關(guān)系具有更好的可解釋性和魯棒性．例如，將吸煙與肺癌患者數(shù)據(jù)集上“肺癌”(例子中變量取值均為“是”、“否”)作為目標(biāo)變量，“黃手指”和“吸煙”作為特征變量．由于“吸煙”可用來(lái)解釋“肺癌”，而長(zhǎng)期吸煙手指會(huì)受到焦油的污染，因此“黃手指”和“吸煙”與“肺癌”之間存在相關(guān)關(guān)系，而只有“吸煙”與“肺癌”之間存在因果關(guān)系．當(dāng)一些吸煙者為了隱藏吸煙習(xí)慣而去除手指上的黃漬時(shí)，基于“黃手指”的預(yù)測(cè)模型將失效，而基于“吸煙”的預(yù)測(cè)模型更魯棒．

為了尋找更魯棒的因果特征，近年來(lái)，因果特征選擇算法被廣泛研究.該類(lèi)算法通過(guò)學(xué)習(xí)目標(biāo)變量的馬爾科夫邊界(Markov Boundary， MB)[14]以尋找關(guān)鍵特征，因此又被稱(chēng)為MB發(fā)現(xiàn)算法．具體地，MB的概念來(lái)源于因果貝葉斯網(wǎng)絡(luò)，在滿足忠實(shí)性假設(shè)的貝葉斯網(wǎng)絡(luò)中，一個(gè)變量的MB集合是唯一的，包含該目標(biāo)變量的父節(jié)點(diǎn)、子節(jié)點(diǎn)及配偶節(jié)點(diǎn)(子節(jié)點(diǎn)的其它父節(jié)點(diǎn))[14]．因此，MB反映目標(biāo)變量周?chē)木植恳蚬P(guān)系，給定目標(biāo)變量的MB作為條件集合，其它特征條件獨(dú)立于目標(biāo)變量[14]．基于此屬性：Tsamardinos等[15]證明在分類(lèi)問(wèn)題中，類(lèi)別變量的MB是具有最大預(yù)測(cè)性的最小特征子集；Pellet等[16]證明類(lèi)別變量的MB集合是特征選擇的最優(yōu)解．因此，因果特征選擇算法通常具有可靠的理論保證．

作為一種算法思路，基于因果關(guān)系的特征選擇算法促進(jìn)特征選擇的可解釋性和魯棒性．近年來(lái)，因果特征選擇算法不斷發(fā)展，不僅提升單/多重馬爾科夫邊界發(fā)現(xiàn)算法的搜索精度和計(jì)算效率，在半監(jiān)督數(shù)據(jù)、流數(shù)據(jù)、多源數(shù)據(jù)、多標(biāo)簽數(shù)據(jù)等特殊場(chǎng)景下也不斷發(fā)展．這些算法無(wú)需學(xué)習(xí)包含所有特征的完整貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，即可挖掘目標(biāo)變量周?chē)囊蚬卣鳎疚膶?duì)現(xiàn)有因果特征選擇方法進(jìn)行較全面的研究和綜述．

1 基本原理與現(xiàn)有方法分類(lèi)

1.1 問(wèn)題定義與基礎(chǔ)理論

本節(jié)介紹MB相關(guān)的基本定義和基礎(chǔ)理論．本文使用U表示特征集合，T表示目標(biāo)變量(標(biāo)簽)．MB的概念來(lái)源于人工智能基礎(chǔ)模型之一的貝葉斯網(wǎng)絡(luò).

定義 1貝葉斯網(wǎng)絡(luò)[14]對(duì)于三元組〈U,G,P〉，U表示變量集合，G表示U上的有向無(wú)環(huán)圖(Directed Acyclic Graph， DAG)，P表示U上的概率分布．對(duì)于?X∈U，將X在G中的父變量作為條件集合，如果任意X的非后代變量在P中都條件獨(dú)立于X，那么〈U,G,P〉為貝葉斯網(wǎng)絡(luò)．

貝葉斯網(wǎng)絡(luò)表征一個(gè)變量集合中的因果關(guān)系．在有向無(wú)環(huán)圖中，對(duì)于一對(duì)直接相連的父子變量，父變量是子變量的直接原因，子變量是父變量的直接結(jié)果[14]．忠實(shí)性是貝葉斯網(wǎng)絡(luò)的基礎(chǔ)假設(shè)之一，定義如下.

定義 2忠實(shí)性[14]給定貝葉斯網(wǎng)絡(luò)〈U,G,P〉，G忠實(shí)于P當(dāng)且僅當(dāng)P中的每個(gè)條件獨(dú)立性關(guān)系都是由G和馬爾科夫條件決定的．P忠實(shí)于G當(dāng)且僅當(dāng)存在一個(gè)G的子圖忠實(shí)于P．

MB的概念是基于忠實(shí)的貝葉斯網(wǎng)絡(luò)而提出的，定義如下.

定義 3馬爾科夫邊界[14]在滿足忠實(shí)性的貝葉斯網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)的馬爾科夫邊界包含該節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)和配偶節(jié)點(diǎn)(子節(jié)點(diǎn)的其它父節(jié)點(diǎn))[14]．

根據(jù)定義3，一個(gè)節(jié)點(diǎn)的MB可直接從忠實(shí)的貝葉斯網(wǎng)絡(luò)中“讀”出來(lái)．如圖1所示，節(jié)點(diǎn)T的MB為{A,B,G,H,F}，包含父節(jié)點(diǎn)A、B，子節(jié)點(diǎn)G、H，配偶節(jié)點(diǎn)F．從因果圖的角度分析，MB提供變量周?chē)木植恳蚬Y(jié)構(gòu)，父節(jié)點(diǎn)、子節(jié)點(diǎn)、配偶節(jié)點(diǎn)分別對(duì)應(yīng)目標(biāo)變量的直接原因、直接結(jié)果、直接結(jié)果的其它原因．MB發(fā)現(xiàn)算法通過(guò)挖掘變量的局部因果結(jié)構(gòu)，無(wú)需學(xué)習(xí)完整的貝葉斯網(wǎng)絡(luò)即可找到變量的MB．而變量的MB集合有一個(gè)特殊的統(tǒng)計(jì)特性，見(jiàn)定理1.

圖1 馬爾科夫邊界的例子

定理 1對(duì)于變量X∈U，X的馬爾科夫邊界MB?U,滿足：?Y∈U-MB-{X}，X⊥Y|MB，且MB為滿足該統(tǒng)計(jì)特性的最小變量集．

定理1中闡述MB的最小性，MB的超集通常稱(chēng)為馬爾科夫毯(Markov Blanket)．根據(jù)定理1，以MB集合為條件，目標(biāo)變量會(huì)條件獨(dú)立于其它特征．因此，MB中的特征攜帶所有關(guān)于目標(biāo)變量的預(yù)測(cè)信息，并且其“最小性”保證MB可作為特征選擇問(wèn)題的最優(yōu)解，見(jiàn)定理2.

定理 2在滿足忠實(shí)性假設(shè)的數(shù)據(jù)中，目標(biāo)變量的MB是唯一的，并且為特征選擇的最優(yōu)解[15-16]．

定理2為MB發(fā)現(xiàn)算法解決特征選擇問(wèn)題提供理論保證，由于MB發(fā)現(xiàn)算法根據(jù)數(shù)據(jù)中的因果關(guān)系選擇特征，并且特征包含目標(biāo)變量的因果信息，因此使用MB發(fā)現(xiàn)算法選擇特征的過(guò)程稱(chēng)為因果特征選擇．

1.2 現(xiàn)有馬爾科夫邊界學(xué)習(xí)方法分類(lèi)及其基本

原理

圖2給出本文對(duì)現(xiàn)有MB發(fā)現(xiàn)算法的分類(lèi)．常規(guī)數(shù)據(jù)中的MB發(fā)現(xiàn)算法主要分為單重MB發(fā)現(xiàn)算法和多重MB發(fā)現(xiàn)算法，這兩類(lèi)算法的應(yīng)用場(chǎng)景取決于訓(xùn)練數(shù)據(jù)是否滿足忠實(shí)性假設(shè)．根據(jù)定理2，在滿足忠實(shí)性的條件下，目標(biāo)變量的MB是唯一的，當(dāng)真實(shí)數(shù)據(jù)并不完全滿足忠實(shí)性條件時(shí)，目標(biāo)變量可能存在多個(gè)等價(jià)的MB．因此，一部分現(xiàn)有算法假設(shè)數(shù)據(jù)滿足忠實(shí)性，并且試圖尋找目標(biāo)變量的唯一MB，該類(lèi)算法稱(chēng)為單重MB發(fā)現(xiàn)算法.另一部分算法考慮忠實(shí)性假設(shè)被違反的情況，這些算法可挖掘目標(biāo)變量的多個(gè)等價(jià)MB，該類(lèi)算法稱(chēng)為多重MB發(fā)現(xiàn)算法．特殊數(shù)據(jù)中的MB發(fā)現(xiàn)算法作為一類(lèi)單獨(dú)介紹，其中包括半監(jiān)督數(shù)據(jù)MB發(fā)現(xiàn)算法、流數(shù)據(jù)MB發(fā)現(xiàn)算法、多源數(shù)據(jù)MB發(fā)現(xiàn)算法、多標(biāo)簽數(shù)據(jù)MB發(fā)現(xiàn)算法．本文按照上述分類(lèi)介紹現(xiàn)有算法的特點(diǎn)．

圖2 現(xiàn)有MB發(fā)現(xiàn)算法的分類(lèi)

單重MB發(fā)現(xiàn)算法假設(shè)目標(biāo)變量有唯一的MB，輸出的MB集合可直接作為特征選擇的結(jié)果．該類(lèi)算法主要分為兩類(lèi)：直接的MB發(fā)現(xiàn)算法(直接法)和分治的MB發(fā)現(xiàn)算法(分治法)．主要區(qū)別是：直接法根據(jù)MB的性質(zhì)(定理1)直接學(xué)習(xí)MB變量，而分治法分別學(xué)習(xí)父子變量和配偶變量.主要理論依據(jù)為定理3和定理4.

定理 3在U上的貝葉斯網(wǎng)絡(luò)中，如果節(jié)點(diǎn)X和Y滿足：任意變量子集Z?U-{X,Y}，X⊥Y|Z不成立，那么X和Y是一對(duì)父子變量[17]．

定理 4在U上的貝葉斯網(wǎng)絡(luò)中，如果不相連的節(jié)點(diǎn)X和Y均與T相連，如果存在變量子集Z?U-{X,Y,T}，使得X⊥Y|Z成立但X⊥Y|Z∪{T}不成立，那么X和Y是一對(duì)配偶變量[17]．

定理3和定理4分別給出父子變量和配偶變量的判別條件，基于上述定理，分治的MB發(fā)現(xiàn)算法可通過(guò)條件獨(dú)立性測(cè)試分別搜索父子和配偶變量．

如圖3所示，單重MB發(fā)現(xiàn)算法通常使用增長(zhǎng)階段和收縮階段搜索MB變量或父子變量．增長(zhǎng)階段用于識(shí)別并添加可能的真變量，而收縮階段檢測(cè)并刪除增長(zhǎng)步驟中找到的假變量．基于這一框架，分治法需要進(jìn)一步搜索配偶變量．直接法通常在時(shí)間效率上更優(yōu)．但由于分治法在條件獨(dú)立性測(cè)試中使用規(guī)模更小的條件集合，因此通常分治法可達(dá)到比直接法更高的準(zhǔn)確性．

圖3 直接法和分治法的區(qū)別

可用于MB發(fā)現(xiàn)算法的通用條件獨(dú)立性測(cè)試方法有5種:1)λ2測(cè)試、G2測(cè)試、互信息計(jì)算，可用于離散數(shù)據(jù)[18]；2)菲爾遜Z檢驗(yàn)[19]，可用于帶有高斯誤差的線性關(guān)系的連續(xù)數(shù)據(jù)；3)基于核的條件獨(dú)立性測(cè)試方法[20],可用于非線性、非高斯噪聲的連續(xù)數(shù)據(jù).

多重MB發(fā)現(xiàn)算法研究忠實(shí)性假設(shè)被違反的情況下一個(gè)變量的多個(gè)等價(jià)MB．理論上來(lái)說(shuō)，目標(biāo)變量的多重MB攜帶等價(jià)的信息且具有相似的預(yù)測(cè)能力[21]，該類(lèi)算法存在的意義是：1)由于實(shí)際應(yīng)用中多個(gè)等價(jià)的MB適應(yīng)的特定學(xué)習(xí)模型是不同的，多重MB可用于解釋學(xué)習(xí)模型的多樣性現(xiàn)象；2)實(shí)際應(yīng)用中可能存在多個(gè)等價(jià)的MB，但并非所有MB都適合作為特征子集建立學(xué)習(xí)模型．例如，當(dāng)不同變量的獲取成本可能不同時(shí)，多重MB算法可用于探索較低獲取成本但具有相似預(yù)測(cè)性的替代解決方案(特征子集)．

根據(jù)Statnikov等[21]的研究，多重MB的本質(zhì)原因是等價(jià)信息現(xiàn)象，定義4和定理5如下.

定義 4等價(jià)信息[21]對(duì)變量集合X?U,Y?U及目標(biāo)變量T∈U，X和Y包含T的等價(jià)信息當(dāng)且僅當(dāng)X和Y與T相關(guān)且滿足X⊥T|Y，Y⊥T|X．

定理 5當(dāng)且僅當(dāng)沒(méi)有發(fā)生信息等價(jià)時(shí)，目標(biāo)變量有一個(gè)唯一的MB集合[21]．

根據(jù)定理5，多重MB與等價(jià)信息現(xiàn)象是共存的，因此尋找多個(gè)MB的過(guò)程也就是識(shí)別等價(jià)信息的過(guò)程[21]．現(xiàn)有的多重MB發(fā)現(xiàn)算法通常遵循如下步驟：1)使用單重MB發(fā)現(xiàn)算法找到一個(gè)初始的MB；2)在當(dāng)前MB中選擇特征子集，將其從源數(shù)據(jù)分布中移除，再在新的數(shù)據(jù)分布中找到新的MB；3)測(cè)試新MB是否正確．

特殊數(shù)據(jù)的MB發(fā)現(xiàn)算法主要是面向近年來(lái)逐漸流行的一些特殊學(xué)習(xí)場(chǎng)景，根據(jù)本文的調(diào)研，目前主要包括但不限于：半監(jiān)督數(shù)據(jù)MB發(fā)現(xiàn)算法、多標(biāo)簽數(shù)據(jù)MB發(fā)現(xiàn)算法、多源數(shù)據(jù)MB發(fā)現(xiàn)算法和流數(shù)據(jù)MB發(fā)現(xiàn)算法．這些算法大多對(duì)應(yīng)某個(gè)單重MB發(fā)現(xiàn)算法，考慮對(duì)應(yīng)場(chǎng)景的特點(diǎn)，將單重MB算法擴(kuò)展應(yīng)用到特殊數(shù)據(jù)中．

2 馬爾科夫邊界發(fā)現(xiàn)算法

本章介紹單重MB發(fā)現(xiàn)算法(分為直接法和分治法)和多重MB發(fā)現(xiàn)算法的研究現(xiàn)狀，以及現(xiàn)有算法在各方面性能上的優(yōu)劣．

2.1 直接法的研究現(xiàn)狀

早期的MB發(fā)現(xiàn)算法均為直接法．直接法直接利用MB的性質(zhì)(定理1)搜索MB變量．該類(lèi)算法的發(fā)展脈絡(luò)如圖4所示．從Koller等[22]關(guān)注到MB在特征選擇中的應(yīng)用并提出第一個(gè)MB搜索的近似算法之后，一些早期的直接法被相繼提出，這些算法大多采用增長(zhǎng)-收縮的兩階段框架(如圖3所示)，使用條件獨(dú)立性測(cè)試搜索MB變量．該框架在GSMB(Growing-Shrinking Markov Blanket)[23]改進(jìn)KS[22]之后正式確立，并在IAMB(Incremental Asso-ciation Markov Blanket)[24]中得到完善．

圖4 直接法的發(fā)展過(guò)程

Koller等[22]提出KS，他們意識(shí)到MB在特征選擇中的應(yīng)用，提出一個(gè)理論上合理的近似算法KS．KS使用基于后向選擇的搜索策略，即從特征的全集開(kāi)始搜索，不斷最小化交叉信息熵的損失函數(shù)，以此最小化在特征選擇過(guò)程中丟失的預(yù)測(cè)信息．不同于KS，GSMB[23]的正確性可以被論證．GSMB基于兩個(gè)假設(shè)：1)被研究的數(shù)據(jù)分布可使用忠實(shí)的貝葉斯網(wǎng)絡(luò)建模；2)條件獨(dú)立性測(cè)試是可靠的．在這兩個(gè)假設(shè)的條件下，GSMB開(kāi)創(chuàng)性地提出增長(zhǎng)-收縮框架，增長(zhǎng)階段通過(guò)條件獨(dú)立性測(cè)試找到可能的MB變量．由于變量遍歷順序的不同可能會(huì)引入一些錯(cuò)誤的MB變量，因此收縮階段排查這一部分錯(cuò)誤變量.使用的方法是：通過(guò)移除某個(gè)變量觀察剩下的變量是否符合MB的定義．增長(zhǎng)階段和收縮階段交替進(jìn)行，直到所選MB集合不發(fā)生改變．IAMB[24]在GSMB的基礎(chǔ)上降低算法的數(shù)據(jù)依賴(lài)性，繼續(xù)使用GSMB中的增長(zhǎng)-收縮框架，主要改進(jìn)GSMB的增長(zhǎng)階段，采用“動(dòng)態(tài)”啟發(fā)式過(guò)程，在搜索可能的MB變量之前，對(duì)候選變量進(jìn)行重新排序．因此IAMB遍歷變量的次序和GSMB不同，變量的動(dòng)態(tài)重排使IAMB在精度上更優(yōu)．

在IAMB被提出后，很多變形算法[24-30]通過(guò)改進(jìn)IAMB而獲得某一方面性能的提升．一些IAMB變形算法提升MB發(fā)現(xiàn)的數(shù)據(jù)依賴(lài)性和準(zhǔn)確性．例如：Inter-IAMB[24]將IAMB中的增長(zhǎng)階段和收縮階段整合到一次MB集合的更新迭代中，并交錯(cuò)執(zhí)行，可及時(shí)消除當(dāng)前MB中的錯(cuò)誤變量，盡量控制MB集合的規(guī)模．IAMBnPC[24]和Inter-IAMBnPC[24]使用PC[17]分別替代IAMB和Inter-IAMB的收縮階段，PC可在收縮階段只檢查當(dāng)前MB的子集而非整個(gè)MB集合，通過(guò)縮小條件集合的規(guī)模，提升準(zhǔn)確性，降低數(shù)據(jù)依賴(lài)．

一些IAMB變形算法提升MB發(fā)現(xiàn)的時(shí)間效率．例如：Fast-IAMB[25-26]改進(jìn)IAMB的增長(zhǎng)階段，在每輪迭代中一次性添加多個(gè)變量到候選MB集合中，減少迭代次數(shù)并提高效率．FBEDK(Forward-Backward Selection with Early Dropping)[27]發(fā)現(xiàn)IAMB的增長(zhǎng)階段(在尋找下一個(gè)最佳候選特征時(shí))需要重新考慮所有剩余特征，造成時(shí)間效率的損失．為了解決這一問(wèn)題，F(xiàn)BEDK改進(jìn)IAMB的增長(zhǎng)階段，采用“早期下降”策略．在每次迭代中，如果一個(gè)特征在當(dāng)前MB為條件下獨(dú)立于目標(biāo)變量，則直接移除，從而避免多次冗余的條件獨(dú)立性測(cè)試．算法允許增長(zhǎng)階段被運(yùn)行K次，用于重新檢測(cè)被刪除的特征．通過(guò)這一改進(jìn)，F(xiàn)BEDK可在保持準(zhǔn)確性的同時(shí)提升MB搜索的時(shí)間效率．

此外，一些IAMB變形算法提升MB發(fā)現(xiàn)算法在高維數(shù)據(jù)上的實(shí)用性．例如：Fit-IAMB(Three-Fast-Inter IAMB)[29]結(jié)合Inter-IAMB和Fast-IAMB的優(yōu)勢(shì)，用于解決高維數(shù)據(jù)中樣本不足的問(wèn)題．PFBP(Parallel Forward-Backward with Pruning)[30]啟發(fā)于IAMB和FBEDK，進(jìn)一步改進(jìn)“早期下降”策略．為了實(shí)現(xiàn)并行計(jì)算，PFBP分別按樣本和特征劃分?jǐn)?shù)據(jù)，并使用元分析技術(shù)結(jié)合本地計(jì)算的結(jié)果，使算法可在數(shù)百萬(wàn)個(gè)特征和樣本的數(shù)據(jù)集上學(xué)習(xí)變量的MB，實(shí)現(xiàn)超線性的加速．

上述MB發(fā)現(xiàn)算法均基于條件獨(dú)立性測(cè)試而設(shè)計(jì)．除此以外，還有2種MB發(fā)現(xiàn)的思路：1)使用貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的方法；2)使用優(yōu)化的方法．DMB和RPDMB[31]采用基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法學(xué)習(xí)目標(biāo)變量的MB，避免條件獨(dú)立性測(cè)試的級(jí)聯(lián)錯(cuò)誤帶來(lái)的影響．DMB和RPDMB分別定義一個(gè)有約束的搜索子空間，稱(chēng)為類(lèi)聚焦有向無(wú)環(huán)圖(CDAG)和類(lèi)聚焦部分約束的有向無(wú)環(huán)圖(CRPDAG)．基于這兩種圖，算法使用基于爬山的搜索算法從空?qǐng)D開(kāi)始搜索，DMB在CDAG空間進(jìn)行局部搜索，RPDMB在CRPDAG空間進(jìn)行搜索，直到評(píng)分函數(shù)達(dá)到最優(yōu)．最后，兩種算法分別從得到的圖中讀取MB．MBMML(Markov Blanket Discovery Using Minimum Message Length)[32]利用最小信息長(zhǎng)度作為評(píng)分函數(shù)，實(shí)現(xiàn)性能提升．TLMB(Tolerant MB Discovery)[33]是優(yōu)化法的代表，該研究注意到條件獨(dú)立性測(cè)試無(wú)法考慮多元相關(guān)關(guān)系，通過(guò)條件協(xié)方差算子[34-35]將特征空間和目標(biāo)變量空間映射到一個(gè)可再生核希爾伯特空間，度量特征攜帶的因果信息．該研究證明，如果概率分布是嚴(yán)格為正的，那么能最小化條件協(xié)方差算子的跡的特征子集就是目標(biāo)變量的MB．基于這一理論，TLMB通過(guò)在希爾伯特空間中優(yōu)化條件協(xié)方差算子的跡，求出最優(yōu)的MB集合．

2.2 直接法的特點(diǎn)對(duì)比與問(wèn)題分析

從直接法的研究現(xiàn)狀來(lái)看，基于條件獨(dú)立性測(cè)試的方法仍占據(jù)主導(dǎo)地位，這是因?yàn)镸B的概念來(lái)自于貝葉斯網(wǎng)絡(luò)，而貝葉斯網(wǎng)絡(luò)是一個(gè)表征條件相關(guān)與獨(dú)立的模型．但是，隨著該領(lǐng)域的不斷發(fā)展，基于條件獨(dú)立性測(cè)試的方法在各方面性能都出現(xiàn)發(fā)展瓶頸，表現(xiàn)不如分治法，因此研究者尋求其它思路解決MB發(fā)現(xiàn)問(wèn)題，即貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)法和優(yōu)化法．

基于條件獨(dú)立性測(cè)試的方法奠定該領(lǐng)域的研究基礎(chǔ)．作為首個(gè)提出的MB發(fā)現(xiàn)算法，KS由于缺乏理論保證，準(zhǔn)確性不夠穩(wěn)定，在大多數(shù)情況下的表現(xiàn)也不如后來(lái)提出的算法．KS需要預(yù)定義兩個(gè)額外的參數(shù)：所選特征數(shù)量和條件獨(dú)立性測(cè)試中條件集合的最大規(guī)模．這兩個(gè)參數(shù)有利于降低算法的運(yùn)行時(shí)間但犧牲正確性．GSMB是第一個(gè)可以在理論上被證明正確性的算法．相比KS，GSMB具有2個(gè)優(yōu)勢(shì)：可靠的理論保證和較高的時(shí)間效率(僅需O(n)次條件獨(dú)立性測(cè)試)．GSMB的缺點(diǎn)是：數(shù)據(jù)依賴(lài)性較強(qiáng)，當(dāng)樣本太少或條件集合較大以致條件獨(dú)立性測(cè)試不可靠時(shí)，算法的準(zhǔn)確性會(huì)受到很大影響．IAMB改善這一問(wèn)題，數(shù)據(jù)依賴(lài)性弱于GSMB．與此同時(shí)，重新排序的改進(jìn)策略確保配偶變量在增長(zhǎng)階段也被較早的找到，從而減少更多的假M(fèi)B變量進(jìn)入候選集合，提升條件獨(dú)立性測(cè)試的可靠性，避免更多級(jí)聯(lián)錯(cuò)誤的發(fā)生．值得一提的是，IAMB與GSMB的基本假設(shè)相同，且理論上的正確性同樣可被證明．正因?yàn)镮AMB改善MB發(fā)現(xiàn)的各方面性能，后來(lái)的大多數(shù)工作均在該算法上進(jìn)行改進(jìn)．

在IAMB的改進(jìn)工作中，準(zhǔn)確性、時(shí)間效率和實(shí)用性均有所提升，而這三方面具有代表性的算法是Inter-IAMB、FBEDK和PFBP，它們?cè)谥靥嵘骋环矫嫘阅艿耐瑫r(shí)在其它方面的損失也是不同的．然而，盡管Inter-IAMB提升準(zhǔn)確性，但由于交錯(cuò)執(zhí)行增長(zhǎng)-收縮過(guò)程而在同一變量上耗時(shí)較多，導(dǎo)致一定的時(shí)間效率損失．此外，交叉兩個(gè)階段可能導(dǎo)致一個(gè)變量被多次添加到MB中或從MB中移除，這也顯著降低時(shí)間效率．在效率提升方面，F(xiàn)BEDK和PFBP均可在保持準(zhǔn)確性的同時(shí)提升時(shí)間效率，是適合于真實(shí)世界大規(guī)模高維數(shù)據(jù)的實(shí)用算法，且PFBP在處理大規(guī)模數(shù)據(jù)時(shí)具有更顯著的時(shí)間效率優(yōu)勢(shì)．

基于條件獨(dú)立性測(cè)試的主要問(wèn)題是有限的準(zhǔn)確性和難以避免的級(jí)聯(lián)錯(cuò)誤．貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)策略和優(yōu)化的策略可在不同程度上解決這一問(wèn)題，但目前這兩類(lèi)方法的發(fā)展仍不夠成熟．其中，結(jié)構(gòu)學(xué)習(xí)法DMB和RPDMB雖然避免條件獨(dú)立性測(cè)試的弊端，但是如果算法使用的有約束的搜索子空間規(guī)模較大時(shí)，學(xué)習(xí)DAG的時(shí)間成本會(huì)很高．這導(dǎo)致該方法不具有其它直接法在時(shí)間效率上的優(yōu)勢(shì)，在大規(guī)模數(shù)據(jù)中的實(shí)用性非常有限．相反，優(yōu)化法TLMB在提升準(zhǔn)確性的同時(shí)并未過(guò)多地?fù)p失時(shí)間效率，因?yàn)樵谇蠼鈨?yōu)化問(wèn)題之前，首先使用基于條件協(xié)方差算子設(shè)計(jì)的評(píng)分函數(shù)過(guò)濾一部分冗余特征，盡量縮小優(yōu)化問(wèn)題的解空間，這在一定程度上節(jié)省運(yùn)行時(shí)間．該方法面臨的的新問(wèn)題是：希爾伯特空間中優(yōu)化條件協(xié)方差算子的跡沒(méi)有理論上的解，而對(duì)應(yīng)的優(yōu)化算法也不夠有效．未來(lái)優(yōu)化法的討論和改進(jìn)是直接法研究的趨勢(shì)之一．

2.3 分治法的研究現(xiàn)狀

盡管直接法已具有較高的效率和準(zhǔn)確性，但數(shù)據(jù)依賴(lài)性較強(qiáng)，在小樣本數(shù)據(jù)集中效果不理想．分治的MB發(fā)現(xiàn)算法的提出主要是為了解決這一問(wèn)題，其數(shù)據(jù)依賴(lài)性取決于目標(biāo)變量周?chē)母缸幼兞恳?guī)模，而非整個(gè)MB規(guī)模．該類(lèi)算法以合理的時(shí)間效率犧牲換取準(zhǔn)確性和數(shù)據(jù)依賴(lài)性的顯著提高．分治法的發(fā)展脈絡(luò)如圖5所示．

分治策略是將MB發(fā)現(xiàn)問(wèn)題分解為兩個(gè)子問(wèn)題:首先識(shí)別父子變量，之后識(shí)別配偶變量．大多數(shù)算法的父子變量搜索過(guò)程遵循圖3中增長(zhǎng)-收縮框架，而配偶變量的搜索可轉(zhuǎn)化為子變量的父子變量的搜索，因此在搜索配偶變量時(shí)也會(huì)調(diào)用父子變量搜索過(guò)程．

MMMB(Max-Min Markov Blanket)[36]是最早的分治算法．在搜索父子變量時(shí)，MMMB的增長(zhǎng)階段為每個(gè)候選特征找到一個(gè)特征子集，使得在該子集為條件下，對(duì)應(yīng)特征與目標(biāo)變量之間的相關(guān)性最小．在此情況下，如果特征與標(biāo)簽之間相互獨(dú)立，根據(jù)定理3，該特征不是MB變量而應(yīng)被移除，與此同時(shí)，相關(guān)性最大的特征是可能性最大的MB變量而應(yīng)被選入候選MB集合．父子變量搜索的收縮階段會(huì)遍歷當(dāng)前MB的所有子集以檢查選中的父子變量是否與目標(biāo)變量相互獨(dú)立，根據(jù)定理3，相互獨(dú)立說(shuō)明該變量不是MB變量而應(yīng)被移除．MMMB的配偶搜索直接使用定理4中的準(zhǔn)則，搜索空間是每個(gè)父子變量集合的并集，在搜索空間中找到配偶變量S和對(duì)應(yīng)子變量C構(gòu)成的V結(jié)構(gòu)[36]，即S→C←T．后來(lái)學(xué)者們提出的基于條件獨(dú)立性測(cè)試的分治法均在MMMB的框架下進(jìn)行改進(jìn).例如，HITON-Markov Blanket(HITON為Blanket的希臘語(yǔ)音譯)[37]交錯(cuò)執(zhí)行增長(zhǎng)-收縮階段，使學(xué)習(xí)父子變量和刪除錯(cuò)誤變量在一次迭代中先后進(jìn)行，可較早識(shí)別錯(cuò)誤的父子變量，從而避免級(jí)聯(lián)錯(cuò)誤．Semi-HITON-MB[12]在HITON-MB的基礎(chǔ)上進(jìn)行改進(jìn)，在候選特征集為空之前只刪除新添加的變量，而在其為空之后執(zhí)行考慮所有錯(cuò)誤變量的刪除．

圖5 分治法的發(fā)展過(guò)程

由于分治法可找到變量之間的父子關(guān)系，一些算法利用父子關(guān)系的對(duì)稱(chēng)性，提升MB發(fā)現(xiàn)算法的準(zhǔn)確性或?qū)嵱眯裕紤]對(duì)稱(chēng)性的方法包括AND規(guī)則和OR規(guī)則．AND規(guī)則是指：對(duì)于一對(duì)變量，只有當(dāng)它們的父子變量集合均包含對(duì)方時(shí)，才是一對(duì)父子變量．OR規(guī)則是指：對(duì)于一對(duì)變量，只要其中一個(gè)的父子變量集合包含另一個(gè)變量，那么它們就是一對(duì)父子變量．

第一個(gè)提出并使用AND規(guī)則的算法是PCMB(Parents-and-Children-Based MB)[38-39].該算法沿用HITON-MB交錯(cuò)執(zhí)行增長(zhǎng)-收縮階段，并利用AND規(guī)則在父子變量之間進(jìn)行對(duì)稱(chēng)檢驗(yàn)，避免一些非子變量的后代變量被誤檢測(cè)為子變量．由于避免這一錯(cuò)誤，PCMB成為第一個(gè)被證明正確性的分治法．IPCMB(Iterative-PCMB)[40]則認(rèn)為過(guò)濾錯(cuò)誤變量比直接識(shí)別正確變量更容易，基于這一考量，IPCMB采用PCMB的逆向過(guò)程，即從完整的變量集合中刪除錯(cuò)誤變量，直到恢復(fù)真正的MB集合.這一改進(jìn)可盡早識(shí)別和去除錯(cuò)誤的MB變量，避免條件獨(dú)立性測(cè)試中條件集合規(guī)模過(guò)大的問(wèn)題及噪聲的影響．DOS(Dynamic Ordering-Based Search)[41]基于IPCMB的思路，提出2個(gè)改進(jìn)策略：1)開(kāi)展條件獨(dú)立性測(cè)試的同時(shí)考慮候選集上的變量排序和條件集上的變量排序，這一改進(jìn)能在少量的條件獨(dú)立性測(cè)試中有效檢測(cè)假M(fèi)B變量；2)利用已知的條件獨(dú)立性測(cè)試，盡可能早地從候選集合中刪除假M(fèi)B變量，提高時(shí)間效率．STMB(Simultaneous Markov Blanket)[42]主要關(guān)注算法效率．為了緩解AND規(guī)則中對(duì)稱(chēng)檢驗(yàn)步驟效率低下的問(wèn)題，STMB采用與PCMB相同的父子變量搜索方法，再使用配偶變量輔助刪除錯(cuò)誤的父子變量，融合兩個(gè)過(guò)程，提升時(shí)間效率．不同于上述算法著力于提升數(shù)據(jù)效率或時(shí)間效率，BAMB(Balanced Markov Blanket)[43]和EEMB(Efficient and Effective Markov Blanket Discovery)[44]通過(guò)父子變量和配偶變量的交替識(shí)別，試圖在數(shù)據(jù)效率和時(shí)間效率之間取得平衡．兩者均采用類(lèi)似于STMB的策略，使用配偶變量輔助刪除錯(cuò)誤的父子變量，同時(shí)在每個(gè)新的父子變量被找到時(shí)都會(huì)直接搜索其對(duì)應(yīng)的配偶變量并刪除錯(cuò)誤的父子變量，從而盡可能地限制候選集的規(guī)模．EEMB進(jìn)一步改進(jìn)BAMB中錯(cuò)誤的父子變量可能導(dǎo)致錯(cuò)誤的配偶變量級(jí)聯(lián)增加的問(wèn)題．

第一個(gè)使用OR規(guī)則的算法是MBOR(MB Sear-ch Using the OR Condition)[45-46]．該研究的主要目的是解決樣本不足時(shí)MB發(fā)現(xiàn)算法失準(zhǔn)的問(wèn)題．由于數(shù)據(jù)不足時(shí)無(wú)法真實(shí)表達(dá)原始分布，數(shù)據(jù)中的分布與真實(shí)分布可能存在偏差，一些可能相關(guān)的特征被誤以為是無(wú)關(guān)特征或冗余特征，導(dǎo)致信息的損失．MBOR放棄AND規(guī)則而使用OR規(guī)則,具體來(lái)說(shuō)，MBOR使用一個(gè)弱MB學(xué)習(xí)器(原理正確但不夠準(zhǔn)確的算法)去產(chǎn)生一個(gè)強(qiáng)的MB學(xué)習(xí)器(更準(zhǔn)確的算法)．算法首先通過(guò)一些簡(jiǎn)單的條件獨(dú)立性測(cè)試(條件集合包含1～2個(gè)變量)，找出目標(biāo)變量的父子集合和配偶集合的超集；再使用OR規(guī)則過(guò)濾這兩個(gè)超集中的錯(cuò)誤MB變量，同時(shí)檢測(cè)尚未被找到的真MB變量．CCMB(Cross-Check and Complement MB Discovery)[47]的研究直接關(guān)注上述MB算法查準(zhǔn)率較高、查全率較低的缺陷，從理論上分析父子變量違反OR規(guī)則的錯(cuò)誤機(jī)理，在此基礎(chǔ)上,CCMB直接通過(guò)OR規(guī)則修復(fù)這類(lèi)錯(cuò)誤．相比MBOR，CCMB對(duì)OR規(guī)則的置信度更高，這導(dǎo)致CCMB具有更高的查全率，但同時(shí)查準(zhǔn)率弱于其它算法．SRMB(Separation and Recovery MB Discovery)[48]與MBOR和CCMB動(dòng)機(jī)相同，引入兩階段發(fā)現(xiàn)策略：在分離階段通過(guò)一個(gè)快速但不夠準(zhǔn)確的直接法得到MB的初始集合，從中區(qū)分父子變量和配偶變量；在恢復(fù)階段,基于OR規(guī)則和分治法的基本框架,搜索父子變量和配偶變量．EAMB(Error-Aware Markov Blanket Learning)[49]提出一種寬松的R-AND規(guī)則，其本質(zhì)與OR規(guī)則接近．基于該規(guī)則,EAMB提出選擇性策略，在被丟棄的特征中找到由于條件獨(dú)立性測(cè)試不準(zhǔn)確而丟失的MB變量．此外該算法提出雙重收縮策略，同時(shí)減少條件集(當(dāng)前選擇的候選MB特征)和候選特征集(當(dāng)前選擇的候選MB特征之外的集合)的大小，從而盡可能地減少不可靠的條件獨(dú)立性測(cè)試．

上述算法均基于MMMB主導(dǎo)的框架，利用條件獨(dú)立性測(cè)試搜索MB．一些算法還嘗試使用貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的方法分治學(xué)習(xí)父子變量和配偶變量,如SLL(Score-Based Local Learning)[50]、S2TMB(Score-Based STMB)[51]和S2TMB+[51]．這些算法通過(guò)學(xué)習(xí)目標(biāo)變量周?chē)腄AG，從中讀取目標(biāo)變量的MB．SLL本質(zhì)上是上述分治MB發(fā)現(xiàn)算法的一種變體，采用貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法而非條件獨(dú)立性測(cè)試學(xué)習(xí)父子變量和配偶變量．為了識(shí)別其中的錯(cuò)誤變量，SLL使用AND規(guī)則篩選錯(cuò)誤的父子變量，使用OR規(guī)則篩選錯(cuò)誤的配偶變量．這一過(guò)程帶來(lái)大量的對(duì)稱(chēng)檢驗(yàn)，因此當(dāng)目標(biāo)變量的MB集合規(guī)模較大時(shí)，SLL的計(jì)算開(kāi)銷(xiāo)會(huì)很大．為了解決效率問(wèn)題，Gao等[51]提出S2TMB，是STMB基于分?jǐn)?shù)的變體．S2TMB不使用對(duì)稱(chēng)檢查，而是采用類(lèi)似于STMB的方法，即利用找到的配偶和父子變量去除錯(cuò)誤的父子變量．S2TMB+是S2TMB的改進(jìn)版本，進(jìn)一步提高計(jì)算效率．

2.4 分治法的特點(diǎn)對(duì)比與問(wèn)題分析

由于直接法不區(qū)分父子變量和配偶變量并同時(shí)學(xué)習(xí)它們，因此此類(lèi)算法具有較低的時(shí)間復(fù)雜度，但需要樣本的數(shù)量與MB的規(guī)模呈指數(shù)關(guān)系，這意味著樣本不足可能影響算法性能．不同于直接法在時(shí)間效率上的優(yōu)勢(shì)，分治法在準(zhǔn)確性和數(shù)據(jù)依賴(lài)性方面表現(xiàn)更優(yōu)．第一個(gè)分治法MMMB在這兩方面均已有較好的表現(xiàn)(優(yōu)于多數(shù)直接法)，之后提出的分治法幾乎都在MMMB的框架下進(jìn)行改進(jìn)．早期的改進(jìn)均為MMMB的修補(bǔ)，如HITON-MB．

盡管MMMB具有很高的準(zhǔn)確性，但算法的輸出無(wú)法保證正確性，其中的一類(lèi)錯(cuò)誤在PCMB的研究中[38-39]被關(guān)注到．在父子變量的搜索中，如果特征X不是父子變量，MMMB和HITON-MB都認(rèn)為必然存在一個(gè)父子變量子集作為條件集合，那么X與T相互獨(dú)立．然而，如果X是T的后代(非子變量)，那么上述論斷是錯(cuò)誤的，因此，這兩種算法(及其它不使用AND規(guī)則的算法)在后代鏈路較長(zhǎng)的貝葉斯網(wǎng)絡(luò)數(shù)據(jù)中精度較低．但是，相對(duì)于MMMB，HITON-MB使用更簡(jiǎn)潔的啟發(fā)式搜索策略，因此也更高效．

MMMB和HITON-MB中的錯(cuò)誤在PCMB中被基于AND規(guī)則的對(duì)稱(chēng)檢驗(yàn)糾正．盡管規(guī)避一部分條件獨(dú)立性測(cè)試無(wú)法解決的風(fēng)險(xiǎn)，能在一定程度上提升MB發(fā)現(xiàn)算法的精度，但對(duì)稱(chēng)檢驗(yàn)有較大的時(shí)間開(kāi)銷(xiāo)，必須對(duì)所有的父子變量再使用一次父子變量的搜索．STMB將對(duì)稱(chēng)檢驗(yàn)融入配偶變量的搜索階段，相對(duì)其它基于AND規(guī)則設(shè)計(jì)的算法，顯著提高時(shí)間效率．但是，由于在一些步驟中使用整個(gè)MB集合作為條件集而非窮舉子集，因此數(shù)據(jù)依賴(lài)性和直接法是相同的，高于大多數(shù)分治法，而彌補(bǔ)這一缺陷的方法是擴(kuò)大數(shù)據(jù)集樣本數(shù)．BAMB和EEMB在精度和效率上進(jìn)行折衷處理．

盡管AND規(guī)則在理論上更合理，但并不具有實(shí)用性．因?yàn)锳ND規(guī)則更關(guān)注精度(對(duì)應(yīng)查準(zhǔn)率(Precision))，傾向于選擇更少更精確的特征，而OR規(guī)則更關(guān)注完整度(對(duì)應(yīng)查全率(Recall))，傾向于選擇更多的特征且盡可能無(wú)遺漏．在真實(shí)世界的學(xué)習(xí)任務(wù)中，保留盡量完整的特征信息顯然更有利于學(xué)習(xí)器的訓(xùn)練，因?yàn)榇蠖鄶?shù)學(xué)習(xí)器可容忍少數(shù)冗余特征，但丟失關(guān)鍵的相關(guān)特征會(huì)導(dǎo)致性能下降．因此，過(guò)于苛求查準(zhǔn)率的AND規(guī)則可能會(huì)導(dǎo)致重要特征的丟失，尤其是在數(shù)據(jù)不足的情況下．OR規(guī)則在這種場(chǎng)景下更實(shí)用．因此MBOR等使用OR規(guī)則的算法更關(guān)注真實(shí)數(shù)據(jù)集上的數(shù)據(jù)有效性及準(zhǔn)確性．然而，OR規(guī)則在效率上的損失大于AND規(guī)則，因?yàn)樾枰獧z查更多變量的父子對(duì)稱(chēng)性，到目前為止，這一問(wèn)題仍未有很好的解決方案．

2.5 多重馬爾科夫邊界發(fā)現(xiàn)算法研究現(xiàn)狀

只有滿足忠實(shí)性分布時(shí)，目標(biāo)變量具有唯一的MB，而在其它分布下的數(shù)據(jù)集上，目標(biāo)變量可能有多個(gè)MB．真實(shí)世界應(yīng)用領(lǐng)域中的數(shù)據(jù)分布常為后者，因此，從這些數(shù)據(jù)中誘導(dǎo)多個(gè)MB是重要的研究問(wèn)題．多重MB發(fā)現(xiàn)算法的發(fā)展脈絡(luò)如圖6所示.多重MB發(fā)現(xiàn)算法通常會(huì)關(guān)聯(lián)一個(gè)單重MB發(fā)現(xiàn)算法或其它基于互信息的特征選擇算法，多次調(diào)用關(guān)聯(lián)算法，提取多個(gè)MB集合．

圖6 多重MB發(fā)現(xiàn)算法的發(fā)展過(guò)程

IR-HITON-PC(Iterative Removal HITON Parents and Children)[52]是最早考慮多重MB問(wèn)題的研究，關(guān)聯(lián)的單重MB算法是Semi-HITON-PC．IR-HITON-PC在每次迭代后會(huì)將該次迭代找到的MB集合中的所有變量從變量總集合中移除，下次迭代中從剩下的變量里尋找MB．因此，IR-HITON-PC具有較高的效率，但輸出的多重MB集合之間沒(méi)有交集．

為了尋找更多的MB集合，一些研究者嘗試使用隨機(jī)策略實(shí)現(xiàn)MB發(fā)現(xiàn)．KIAMB[39]重復(fù)運(yùn)行IAMB，獲得不同的MB．其中，參數(shù)K∈[0,1]，用于指定搜索中貪婪和隨機(jī)性之間的權(quán)衡，當(dāng)K= 1時(shí)，KIAMB與IAMB等價(jià)且進(jìn)行貪婪搜索，當(dāng)K=0時(shí)，KIAMB是完全隨機(jī)的算法．當(dāng)K∈(0,1)時(shí)，KIAMB使用IAMB貪婪地向MB候選集合中添加與目標(biāo)變量最相關(guān)的節(jié)點(diǎn)，然后根據(jù)K值選取MB的一個(gè)子集．因此，不同于IAMB的貪婪選擇，KIAMB輸出的MB可能并不是最優(yōu)的．但通過(guò)反復(fù)運(yùn)行KIAMB，可得到若干不同的MB，KIAMB將這些結(jié)果視為目標(biāo)變量的多重MB．相似地，EGS-CMIM(Ensemble Gene Selection Method with CMIM)[53]和EGSNCM-IGS(Ensemble Gene Selection Method with NCM-IGS)[53]分別反復(fù)調(diào)用CMIM(Conditional Mutual Information Maximization)[54]和NCMIGS(Gene Selection Using Normalized Conditional Mutual Information)[53]，提取多個(gè)MB．但是，CMIM和NCMIGS并不是理論上可靠的MB發(fā)現(xiàn)算法，它們只采用類(lèi)似于IAMB增長(zhǎng)階段的貪婪前向選擇策略，并通過(guò)度量互信息測(cè)量變量和目標(biāo)之間的條件相關(guān)關(guān)系．因此，CMIM和NCMIGS搜索的MB會(huì)存在錯(cuò)誤變量，這也導(dǎo)致EGS-CMIM和EGS-NCMIGS無(wú)法保證其輸出MB的正確性．此外，和其它隨機(jī)算法一樣，EGS-CMIM和EGS-NCMIGS無(wú)法保證找到所有的MB．

除了隨機(jī)策略，另一種脫離因果圖的策略也被用于多重MB發(fā)現(xiàn)．EGSG(Ensemble Gene Selection by Grouping)[55]使用規(guī)范化的互信息度量變量之間的成對(duì)關(guān)聯(lián)，并劃分為不相交的組．每個(gè)組將組中的第一個(gè)變量作為“質(zhì)心”，變量與質(zhì)心的關(guān)聯(lián)度高于目標(biāo)變量時(shí)則入組，否則作為質(zhì)心并創(chuàng)建一個(gè)新的組．EGSG假設(shè)組內(nèi)的變量包含關(guān)于目標(biāo)變量的類(lèi)似信息，因此每組中選取一個(gè)變量即可構(gòu)成一個(gè)MB集合．EGSG從每組中隨機(jī)抽取與目標(biāo)變量關(guān)聯(lián)的最大變量，形成一個(gè)MB集合，通過(guò)多次重復(fù)這一過(guò)程,獲得多個(gè)MB集合．

第一個(gè)可在理論上證明正確性的算法是TIE*(Target Information Equivalence)[21]．該研究給出多重MB現(xiàn)象發(fā)生的根本原因——信息等價(jià)[21]．基于這一理論，TIE*包括3個(gè)步驟：1)使用一個(gè)單重MB發(fā)現(xiàn)算法,從數(shù)據(jù)集中學(xué)習(xí)目標(biāo)變量的一個(gè)MB；2)將MB的某些子集從源數(shù)據(jù)分布中移除，消除可能的等價(jià)信息；3)利用單重MB發(fā)現(xiàn)算法在新的數(shù)據(jù)中尋找MB，而先前在1)中無(wú)法被發(fā)現(xiàn)的MB變量可重新被找到；4)由于新的MB可能只是新數(shù)據(jù)集的MB而在原數(shù)據(jù)集中并不成立，因此該步驟檢驗(yàn)新的MB是否是源分布的MB．重復(fù)上述步驟，直到遍歷所有可能的MB子集為止．

一些研究者在TIE*框架下提出改進(jìn)實(shí)例．MB-DEA(Markov Boundaries from Distributed Feature Data)[56]擴(kuò)展TIE*，可在多變量集的數(shù)據(jù)中使用．TIE*的一個(gè)典型實(shí)例是WLCMB(MB Discovery under the Weak Markov Local Composition Assumption)[28]．WLCMB首先提出一個(gè)單重MB發(fā)現(xiàn)算法LRH(Lessen Swamping, Resist Masking, and Highlight the True Positives)[28],改正條件獨(dú)立性測(cè)試的不準(zhǔn)確帶來(lái)的錯(cuò)誤，WLCMB利用LRH與搜索恢復(fù)過(guò)程相交織，從而在LRH停止工作時(shí)，搜索過(guò)程可重新開(kāi)始．其中，搜索恢復(fù)過(guò)程與TIE*中的恢復(fù)過(guò)程相似，都是通過(guò)去除現(xiàn)有MB的一個(gè)子集以重新發(fā)現(xiàn)MB．WLCMB本質(zhì)上是TIE*的一個(gè)實(shí)例．

2.6 多重馬爾科夫邊界發(fā)現(xiàn)算法的特點(diǎn)對(duì)比與問(wèn)題分析

由于多重MB發(fā)現(xiàn)算法并不能直接作為特征選擇技術(shù)而被應(yīng)用，因此算法數(shù)量遠(yuǎn)少于單重MB發(fā)現(xiàn)算法，且該領(lǐng)域研究不夠成熟，每種算法都有一定的缺陷．IR-HITON-PC由于在每次迭代中都不會(huì)考慮之前的MB變量，因此輸出的MB之間沒(méi)有交集，這是與事實(shí)情況相悖的，因此算法在準(zhǔn)確性上較低，但時(shí)間效率和數(shù)據(jù)效率均較高．KIAMB等隨機(jī)算法并不具有理論保證，無(wú)法確保輸出的MB集合都是真正的MB，但從理論上來(lái)說(shuō)，如果在算法的第一階段中探索足夠多次，將不同的相關(guān)變量序列加入到當(dāng)前的MB候選集合中，KIAMB可識(shí)別所有可能的MB．然而這種策略的計(jì)算效率很低，因?yàn)槠浯蟛糠值倪\(yùn)行可能會(huì)產(chǎn)生先前已經(jīng)確定的MB．因此，為了產(chǎn)生完整的MB集合，參數(shù)K和KIAMB的運(yùn)行次數(shù)必須基于貝葉斯網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和目標(biāo)變量的MB具體數(shù)量確定，然而，兩者都不是已知的．KIAMB的另一個(gè)缺點(diǎn)與IAMB相同，具有很強(qiáng)的數(shù)據(jù)依賴(lài)性，需要大量樣本完成測(cè)試．

KIAMB等的大部分缺陷在TIE*中得到解決，但TIE*主要存在3個(gè)問(wèn)題：1)數(shù)據(jù)集的生成方法本質(zhì)是一個(gè)變量篩選算法，過(guò)程幾乎遍歷一個(gè)MB的所有子集，與此同時(shí)新的MB也在產(chǎn)生，又將會(huì)遍歷更多的子集，因此時(shí)間復(fù)雜度很高.2)新的MB是否在源數(shù)據(jù)分布中成立依賴(lài)于可靠的判別準(zhǔn)則，但文獻(xiàn)[21]中給出的兩個(gè)判別準(zhǔn)則都各有缺陷．其中一種使用MB的定義進(jìn)行條件獨(dú)立性測(cè)試，該準(zhǔn)則需要以先前找到的MB作為條件集合，并測(cè)試目標(biāo)變量和新MB之間的相關(guān)關(guān)系，運(yùn)算涉及到兩個(gè)規(guī)模龐大的集合，導(dǎo)致算法數(shù)據(jù)依賴(lài)性較強(qiáng)，依賴(lài)于大量數(shù)據(jù)樣本才能完成測(cè)試；另一種方法使用一些學(xué)習(xí)算法和性能指標(biāo)評(píng)估新MB的預(yù)測(cè)(分類(lèi)或回歸)性能，若高于之前的MB，認(rèn)為它也是MB，這顯然是不夠可靠的，并且由于不同的MB被找到的先后順序是不確定的，因此對(duì)比MB之間的預(yù)測(cè)性是不合理的．3)TIE*不夠魯棒，當(dāng)某一步驟產(chǎn)生錯(cuò)誤，會(huì)產(chǎn)生大量的級(jí)聯(lián)錯(cuò)誤，而由于問(wèn)題1)、2)導(dǎo)致這種級(jí)聯(lián)錯(cuò)誤容易發(fā)生．作為T(mén)IE*的一個(gè)實(shí)例也具有相似的問(wèn)題，都依賴(lài)大量的樣本確保準(zhǔn)確性．

3 馬爾科夫邊界發(fā)現(xiàn)算法在特殊數(shù)據(jù)中的應(yīng)用

單重MB發(fā)現(xiàn)算法可直接作為特征選擇算法,對(duì)一般應(yīng)用場(chǎng)景中的單標(biāo)簽高維數(shù)據(jù)進(jìn)行降維，但無(wú)法直接應(yīng)用到復(fù)雜學(xué)習(xí)場(chǎng)景中．為了解決這一問(wèn)題，學(xué)者們擴(kuò)展出一些針對(duì)特殊學(xué)習(xí)場(chǎng)景的MB發(fā)現(xiàn)算法．

1)半監(jiān)督數(shù)據(jù)特征選擇.許多真實(shí)世界應(yīng)用通常難以獲取有標(biāo)簽的樣本，但容易收集無(wú)標(biāo)簽數(shù)據(jù)．為了同時(shí)利用無(wú)標(biāo)簽和有標(biāo)簽數(shù)據(jù)學(xué)習(xí)MB，學(xué)者們提出一些半監(jiān)督MB發(fā)現(xiàn)算法，包括分治法BASSUM(Bayesian Semi-Supervised)[57]和直接法Semi-IAMB[58-59]．BASSUM使用一個(gè)基于半監(jiān)督數(shù)據(jù)改進(jìn)的G2檢驗(yàn)，使有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)中的信息可同時(shí)用于判斷變量之間的條件獨(dú)立關(guān)系．此外，文獻(xiàn)[57]中提出有效特征集的概念，利用該子集，BASSUM可不訪問(wèn)有標(biāo)簽數(shù)據(jù)中的類(lèi)別信息而刪除錯(cuò)誤的父子變量．因此，相比普通的MB學(xué)習(xí)算法，BASSUM在半監(jiān)督數(shù)據(jù)中更有效．但是，BASSUM在理論上不可靠，因?yàn)闊o(wú)法保證修改后的G2統(tǒng)計(jì)量服從卡方分布，同時(shí)，當(dāng)有標(biāo)簽數(shù)據(jù)較少時(shí)，表現(xiàn)會(huì)受到很大影響．為了改進(jìn)這一缺陷，Sechidis等[58-59]提出部分標(biāo)簽樣本的條件獨(dú)立性測(cè)試，假設(shè)所有無(wú)標(biāo)簽均屬于正類(lèi)或負(fù)類(lèi)，文獻(xiàn)[58]提出一個(gè)用于半監(jiān)督數(shù)據(jù)假設(shè)檢驗(yàn)的代理類(lèi)變量和代理測(cè)試，并應(yīng)用于包含少量有標(biāo)簽樣本和大量無(wú)標(biāo)簽樣本的半監(jiān)督數(shù)據(jù)中．由于Semi-IAMB是基于上述理論貢獻(xiàn)而提出的算法，因此主要缺陷與代理測(cè)試的缺陷相似：1)只能用于二分類(lèi)問(wèn)題；2)為了減少假負(fù)例，算法依賴(lài)于更多的數(shù)據(jù)或額外的先驗(yàn)知識(shí)．

2)流特征與流數(shù)據(jù)特征選擇.在真實(shí)世界中，很多學(xué)習(xí)場(chǎng)景是實(shí)時(shí)系統(tǒng)，在這些系統(tǒng)中，高維流數(shù)據(jù)的生成速度非?？?，數(shù)據(jù)樣本不斷產(chǎn)生，特征也不斷增加．針對(duì)這一問(wèn)題，一些算法研究流數(shù)據(jù)(假設(shè)訓(xùn)練數(shù)據(jù)以單個(gè)實(shí)例或數(shù)據(jù)塊的形式順序到達(dá)而特征數(shù)量不變)[60]和流特征(假設(shè)特征按順序到達(dá)但訓(xùn)練樣本的數(shù)量是固定的)[61]中的MB發(fā)現(xiàn)問(wèn)題．OMBSF(Online Markov Blanket Discovery with Strea-ming Features)[62]是一個(gè)面向流特征的MB發(fā)現(xiàn)算法，屬于分治法．算法首先檢查新特征與目標(biāo)變量之間的相關(guān)性(條件集合為空集)，如果是相關(guān)的，判斷其是否為父子變量，如果獨(dú)立，判斷其是否為配偶變量．其識(shí)別原理與其它分治法相同，該過(guò)程可快速識(shí)別冗余變量，盡量保證條件獨(dú)立性測(cè)試的準(zhǔn)確性．值得注意的是，存在一些使用MB進(jìn)行流特征選擇的算法[62-67]，如OSFS(Online Streaming Feature Selection)[63]、Fast-OSFS(Fast Online Streaming Feature Selection)[65]和OFSVMB(Online Streaming Features Selection via Markov Blanket)[67]，由于這些算法只搜索MB中的子集(只搜索父子變量作為特征子集)，因此本文沒(méi)有詳細(xì)介紹這些算法．SDMB(Streaming Data-Based MB)[68]是一個(gè)面向流數(shù)據(jù)的MB發(fā)現(xiàn)算法，屬于直接法．算法利用AD-Tree[69]的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)流數(shù)據(jù)中的條件相關(guān)和條件獨(dú)立信息，利用存儲(chǔ)空間的損失提升時(shí)間效率．SDMB使用動(dòng)態(tài)AD-Tree記錄歷史數(shù)據(jù)，使用IAMB的思路針對(duì)AD-Tree中的數(shù)據(jù)計(jì)算變量之間的條件相關(guān)關(guān)系，從而學(xué)習(xí)目標(biāo)的MB．然而，SDMB并未從理論上討論MB在流數(shù)據(jù)中的性質(zhì)，算法本質(zhì)是將流數(shù)據(jù)進(jìn)行存儲(chǔ)并在所有流數(shù)據(jù)形成的數(shù)據(jù)塊上進(jìn)行MB變量搜索，未從根本上解決流數(shù)據(jù)MB發(fā)現(xiàn)問(wèn)題．

3)多源數(shù)據(jù)特征選擇.在真實(shí)世界的應(yīng)用中，數(shù)據(jù)的來(lái)源更豐富，可能一個(gè)標(biāo)簽的信息來(lái)自于多個(gè)不同的數(shù)據(jù)源．為了實(shí)現(xiàn)對(duì)不同分布的多個(gè)數(shù)據(jù)集的穩(wěn)定預(yù)測(cè)，MIMB(Multiple Interventional Markov Blanket)[70]和MCFS(Multi-source Causal Feature Selection)[71]被提出,用于解決多源MB學(xué)習(xí)問(wèn)題．Yu等[70]系統(tǒng)研究多個(gè)數(shù)據(jù)集上MB變量和父子變量的性質(zhì)，提出分治的MB學(xué)習(xí)算法MIMB，算法由兩個(gè)子過(guò)程組成：1)使用MIPC從多個(gè)干預(yù)數(shù)據(jù)集上發(fā)現(xiàn)目標(biāo)變量的父子變量；2)根據(jù)父子變量的結(jié)果，從多個(gè)干預(yù)數(shù)據(jù)集中識(shí)別目標(biāo)變量的配偶變量．基于文獻(xiàn)[70]的理論貢獻(xiàn)，并受到因果不變性概念[72]的啟發(fā)，Yu等[71]提出MCFS，算法將多個(gè)數(shù)據(jù)集上的穩(wěn)定預(yù)測(cè)問(wèn)題定義為跨不同數(shù)據(jù)集搜索不變集．該工作證實(shí)在具有不同分布的多源數(shù)據(jù)集上進(jìn)行特征選擇時(shí)，最優(yōu)且最穩(wěn)定的不變集是目標(biāo)變量的父變量集合而不是目標(biāo)變量的MB集合．同時(shí)為了加快搜索速度，Yu等分析不變集的上界和下界，使MCFS能在一定范圍內(nèi)學(xué)習(xí)最佳的不變集．

4)多標(biāo)簽數(shù)據(jù)特征選擇.常見(jiàn)的MB發(fā)現(xiàn)算法通常只關(guān)注單個(gè)目標(biāo)變量的MB集合，近年的一些工作關(guān)注多目標(biāo)變量的MB發(fā)現(xiàn)問(wèn)題，包括：MIAMB(Multivariate IAMB)[73]、MKIAMB(Multivariate KI-AMB)[73]、MB-MCF(MB-Based Multi-label Causal Fea-ture selection)[74]、CLCD(Common and Label-Specific Causal Variables Discovery)[75]和CLCD-FS(CLCD-Based Feature Selection)[75]．Liu等[73]證明在局部Intersection假設(shè)下，只需取每個(gè)目標(biāo)變量的MB的并集，并將所有目標(biāo)變量排除在并集之外，就可構(gòu)造多類(lèi)變量的MB．根據(jù)這一理論，Liu等[73]提出MIAMB和MKIAMB，將多目標(biāo)變量的MB學(xué)習(xí)問(wèn)題轉(zhuǎn)化為單目標(biāo)變量的多個(gè)MB學(xué)習(xí)問(wèn)題．相比直接將單標(biāo)簽算法分別作用于多個(gè)標(biāo)簽，MIAMB和MKIAMB具有更高的準(zhǔn)確性和更低的時(shí)間復(fù)雜度，但是MIAMB和MKIAMB在真實(shí)世界數(shù)據(jù)的特征選擇任務(wù)上表現(xiàn)一般．Wu等[74]認(rèn)為，多標(biāo)簽數(shù)據(jù)中特征選擇不僅應(yīng)找到所有的因果特征，還應(yīng)指出一個(gè)因果特征影響哪幾個(gè)標(biāo)簽變量．Wu等[74]提出一個(gè)可解釋的MB-MCF以解決此問(wèn)題，但缺乏可靠的理論保證．Wu等[75]指出，在不滿足忠實(shí)性假設(shè)的數(shù)據(jù)中，多重MB可能會(huì)導(dǎo)致更多的共有因果變量．因此，考慮忠實(shí)性被違反的情況下單個(gè)目標(biāo)變量可能擁有多個(gè)MB的情況，并研究等價(jià)信息是如何影響多目標(biāo)變量下的MB學(xué)習(xí)．Wu等[75]證明只有標(biāo)簽上的等價(jià)信息會(huì)導(dǎo)致更多的共有因果變量，并討論每種等價(jià)信息情況下共有因果變量和特有因果變量的性質(zhì)．根據(jù)理論研究，Wu等[75]提出，CLCD不僅可找出多個(gè)目標(biāo)變量的MB集合，還可解釋多個(gè)目標(biāo)變量的共有特征和單個(gè)目標(biāo)變量的特有特征． CLCD-FS[75]是CTCD在真實(shí)世界多標(biāo)簽特征選擇問(wèn)題上的應(yīng)用．Wu等[75]從理論上證明CLCD-FS選擇的特征子集具有最小的冗余性和最多的相關(guān)性，為多標(biāo)簽特征選擇提供理論依據(jù)．

4 因果特征選擇與傳統(tǒng)方法的異同

MB發(fā)現(xiàn)算法與因果特征選擇算法在概念和功能上都是等價(jià)的[76]，MB集合就是所選特征集合，其中的特征就是算法選擇的因果特征，因此本文提到的所有單重MB發(fā)現(xiàn)算法都可直接用于因果特征的選擇．但多重MB發(fā)現(xiàn)算法會(huì)選擇多個(gè)特征子集，需要進(jìn)一步選擇最合適的特征子集．一般會(huì)根據(jù)特征集合的規(guī)模、特征獲取的難易程度和成本等因素考慮最終使用哪個(gè)MB集合．基于上述MB發(fā)現(xiàn)算法的綜述，本節(jié)介紹因果特征選擇與傳統(tǒng)特征選擇之間的聯(lián)系和差異．

按照傳統(tǒng)算法的分類(lèi)，因果特征選擇屬于過(guò)濾法[9]，該類(lèi)方法時(shí)間效率較高，對(duì)過(guò)擬合問(wèn)題更魯棒[76]．傳統(tǒng)過(guò)濾法通常利用評(píng)分函數(shù)評(píng)估特征與目標(biāo)變量之間的關(guān)聯(lián)性，并根據(jù)分?jǐn)?shù)排序特征并選擇相關(guān)特征，而評(píng)分函數(shù)通?；跅l件互信息的概念而設(shè)計(jì)，這與MB發(fā)現(xiàn)算法中條件獨(dú)立性測(cè)試的本質(zhì)是一致的．但是，傳統(tǒng)過(guò)濾法與MB發(fā)現(xiàn)算法對(duì)條件互信息的度量精確程度不同，這可從互信息度量中條件集合的規(guī)模進(jìn)行評(píng)價(jià)．

以三個(gè)經(jīng)典的過(guò)濾法為例．MIM(Mutual Infor-mation Maximization)[77]只關(guān)注備選特征和目標(biāo)變量之間的互信息，而mRMR(Max-Relevance and Min-Redundancy)[78]不僅關(guān)注備選特征和目標(biāo)變量之間的相關(guān)性，同時(shí)關(guān)注備選特征與已選特征之間的相關(guān)性以評(píng)價(jià)其冗余度，這兩種算法在度量互信息時(shí)涉及的條件集合均為空集．JMI(Joint Mutual Infor-mation for Feature Selection)[79]除了關(guān)注上述互信息以外，還額外考慮以目標(biāo)變量為條件的備選特征與已選特征之間的相關(guān)性，所以JMI使用的條件互信息為單變量條件集．大多數(shù)傳統(tǒng)過(guò)濾法與上述算法類(lèi)似，在度量條件互信息時(shí)，條件集合的規(guī)模只精確到1或2個(gè)變量，這意味著傳統(tǒng)過(guò)濾法假設(shè)數(shù)據(jù)中的條件獨(dú)立于條件相關(guān)關(guān)系只涉及到有限規(guī)模的條件集合，不涉及更復(fù)雜的條件相關(guān)或獨(dú)立關(guān)系．

不同于這些算法，MB發(fā)現(xiàn)算法具有可靠的理論保證，無(wú)論是直接法挖掘的MB變量還是分治法挖掘的父子變量和配偶變量，MB發(fā)現(xiàn)算法對(duì)這些變量的度量標(biāo)準(zhǔn)(定理3和定理4)均考慮變量全集的所有可能子集．因此，MB發(fā)現(xiàn)算法的基本假設(shè)要比傳統(tǒng)過(guò)濾法更寬泛，也正是這個(gè)原因，MB發(fā)現(xiàn)算法具有可靠的理論保證，能證明MB集合是最優(yōu)的特征子集，而傳統(tǒng)過(guò)濾法并未在理論上給出最優(yōu)特征子集的標(biāo)準(zhǔn)解.不同過(guò)濾法對(duì)互信息的利用精度有所區(qū)別，均無(wú)法在算法進(jìn)程中智能決定條件獨(dú)立性的層次級(jí)別，未形成一套具有理論保證的方法框架．理論上來(lái)說(shuō)，如果訓(xùn)練數(shù)據(jù)足夠充分，MB發(fā)現(xiàn)算法可實(shí)現(xiàn)更優(yōu)性能．

從上述分析可看出，MB發(fā)現(xiàn)算法考慮的互信息層級(jí)比傳統(tǒng)算法更深入，可度量更精確的條件相關(guān)和獨(dú)立關(guān)系．因此，在樣本足夠多時(shí)，MB發(fā)現(xiàn)算法可在任意規(guī)模的條件集合下度量一對(duì)變量之間的互信息，從而實(shí)現(xiàn)更優(yōu)的性能．精確的條件互信息也提升MB發(fā)現(xiàn)算法的魯棒性和穩(wěn)定性，但這些優(yōu)勢(shì)是以犧牲時(shí)間效率和數(shù)據(jù)效率為代價(jià).MB發(fā)現(xiàn)算法涉及大量的條件互信息計(jì)算，對(duì)訓(xùn)練數(shù)據(jù)的規(guī)模要求較高，同時(shí)MB學(xué)習(xí)比普通特征子集選擇耗時(shí)更多，尤其是分治MB算法對(duì)條件子集的考慮導(dǎo)致指數(shù)級(jí)的時(shí)間復(fù)雜度，這極大影響該類(lèi)算法的實(shí)用性．從數(shù)據(jù)集的特性上考慮，當(dāng)數(shù)據(jù)中的變量關(guān)系較簡(jiǎn)單時(shí)，傳統(tǒng)的過(guò)濾法更有效，可實(shí)現(xiàn)和MB發(fā)現(xiàn)算法相當(dāng)?shù)木?，時(shí)間效率更高．而在變量關(guān)系更復(fù)雜的數(shù)據(jù)集上，MB發(fā)現(xiàn)算法可實(shí)現(xiàn)比傳統(tǒng)過(guò)濾法更優(yōu)的性能．此外，MB發(fā)現(xiàn)算法是基于結(jié)構(gòu)因果模型理論而設(shè)計(jì)的，相對(duì)于傳統(tǒng)特征選擇算法(不限于過(guò)濾法)只考慮相關(guān)關(guān)系，MB發(fā)現(xiàn)算法選擇的特征與目標(biāo)變量同時(shí)具有相關(guān)關(guān)系和因果關(guān)系．其中，分治的MB發(fā)現(xiàn)算法不僅可選擇特征用于完成學(xué)習(xí)任務(wù)，同時(shí)可得到這些特征與目標(biāo)變量之間的因果關(guān)系骨架，是因果發(fā)現(xiàn)的第一步．因此，MB發(fā)現(xiàn)算法更接近于系統(tǒng)的機(jī)理，相比傳統(tǒng)特征選擇，具有更好的因果可解釋性．

5 數(shù)據(jù)集與工具包

由于MB發(fā)現(xiàn)算法是基于貝葉斯網(wǎng)絡(luò)模型的概念而提出的，因此，該類(lèi)算法首先需要在標(biāo)準(zhǔn)的貝葉斯網(wǎng)絡(luò)數(shù)據(jù)集上被檢驗(yàn)．通常這類(lèi)數(shù)據(jù)集上每個(gè)變量的MB集合是已知的，通過(guò)讓MB發(fā)現(xiàn)算法搜索每個(gè)變量的MB并測(cè)試精度(包括查全率和查準(zhǔn)率)和效率，評(píng)估算法性能．此外，作為特征選擇方法，MB發(fā)現(xiàn)算法同時(shí)需要在真實(shí)數(shù)據(jù)集上被檢驗(yàn)，考察算法在特征選擇任務(wù)上的有效性(通常以某個(gè)分類(lèi)器在特征子集上的分類(lèi)精度為依據(jù))．

常用的標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)數(shù)據(jù)集主要來(lái)自真實(shí)的決策支持系統(tǒng)，這些系統(tǒng)涵蓋醫(yī)學(xué)、農(nóng)業(yè)、天氣預(yù)報(bào)、金融建模和動(dòng)物養(yǎng)殖等不同的應(yīng)用領(lǐng)域．例如：小規(guī)模網(wǎng)絡(luò)ASIA[80]、CANCER[81]、SURVEY[82]；中等規(guī)模網(wǎng)絡(luò)ALARM[83]、INSURANCE[84]、CHILD[85]；大規(guī)模網(wǎng)絡(luò)ANDES[86]、LINK[87]、HEPAR2[88]等．此外，Tsamardinos等[89]使用平鋪算法創(chuàng)建幾個(gè)較小網(wǎng)絡(luò)的大規(guī)模版本，創(chuàng)建的貝葉斯網(wǎng)絡(luò)包含3個(gè)、5個(gè)或10個(gè)原始網(wǎng)絡(luò)的副本[89]．標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)數(shù)據(jù)集從這些網(wǎng)絡(luò)中采樣若干訓(xùn)練樣本而得到．針對(duì)特征選擇任務(wù)通常使用真實(shí)數(shù)據(jù)，例如UCI社區(qū)中的數(shù)據(jù)集(https://archive.ics.uci.edu/ml/datasets.ph/)．

一些早期的MB發(fā)現(xiàn)算法被包含在貝葉斯網(wǎng)絡(luò)學(xué)習(xí)工具包中.例如：“bnlearn”R語(yǔ)言工具包[90]中包含 GSMB、IAMB、Inter-IAMB、Fast-IAMB、MMPC(Max-Min Parents and Children)、HITON-PC(HITON Parents and Children)，該算法包利用這些算法實(shí)現(xiàn)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)，并基于貝葉斯網(wǎng)絡(luò)完成推理和分類(lèi)的任務(wù)．“Causal Explorer”MATLAB工具包[91]中包含KS、GSMB、IAMB、IAMBnPC、Inter-IAMB、Inter-IAMBnPC、HITON-MB、MMMB，該算法包[92]利用這些算法實(shí)現(xiàn)局部因果結(jié)構(gòu)的發(fā)現(xiàn)．“CausalFS”C++語(yǔ)言工具包中包含大多數(shù)MB發(fā)現(xiàn)算法，該算法包利用這些算法進(jìn)行因果特征選擇．一些其它工具包還包括：R語(yǔ)言工具包“PGM”[93]和“PC-ALG”[94]、Matlab工具包“BNT”[95]、JAVA語(yǔ)言工具包“tetrad”[96]．本文建立在線的因果特征選擇的資料庫(kù)(http://home.ustc.edu.cn/～xingyuwu/MB.html),匯總因果特征選擇領(lǐng)域經(jīng)典算法的不同語(yǔ)言工具包(如C/C++、Python、Matlab、R語(yǔ)言等)以及用于測(cè)試該類(lèi)算法的標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)數(shù)據(jù)集．

6 研究熱點(diǎn)與發(fā)展趨勢(shì)

MB這一概念的提出為傳統(tǒng)的特征選擇問(wèn)題找到理論依據(jù)，MB發(fā)現(xiàn)算法基于數(shù)據(jù)中的因果關(guān)系，提升特征選擇的魯棒性和可解釋性．經(jīng)過(guò)十幾年的發(fā)展，學(xué)者們對(duì)MB發(fā)現(xiàn)問(wèn)題展開(kāi)研究，并在效率、準(zhǔn)確性、數(shù)據(jù)依賴(lài)性、實(shí)用性等多個(gè)方面改進(jìn)MB學(xué)習(xí)方法．本文回顧當(dāng)前該領(lǐng)域的經(jīng)典算法和最新算法，并進(jìn)行歸納和分類(lèi)討論，包括常規(guī)數(shù)據(jù)中的MB發(fā)現(xiàn)算法和特殊數(shù)據(jù)中的MB發(fā)現(xiàn)算法．結(jié)合每類(lèi)算法的發(fā)展脈絡(luò)，分析異同并對(duì)比算法在效率、準(zhǔn)確性及數(shù)據(jù)依賴(lài)性等方面的優(yōu)劣．

6.1 當(dāng)前研究熱點(diǎn)

經(jīng)過(guò)幾十年的發(fā)展，單重MB發(fā)現(xiàn)算法在理論和方法上都趨于完備，由于直接法和分治法的優(yōu)勢(shì)不同，這兩類(lèi)方法在近幾年的研究趨勢(shì)也有所差異．基于條件獨(dú)立性測(cè)試的方法是單重MB發(fā)現(xiàn)研究的主力，近年的研究也保持著活力．基于條件獨(dú)立性測(cè)試的分治法研究仍著眼于提升該類(lèi)方法的準(zhǔn)確性．隨著大數(shù)據(jù)的發(fā)展，研究者們關(guān)注真實(shí)數(shù)據(jù)中的效率和實(shí)用性問(wèn)題．因此，一些研究者提出BAMB[43]和EEMB[44]，用于確保準(zhǔn)確性的同時(shí)提升效率.而另一些研究者注意到算法在標(biāo)準(zhǔn)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的性能差異，提出CCMB[47]和SRMB[48]，更好地發(fā)揮OR規(guī)則在真實(shí)數(shù)據(jù)中的實(shí)用性．與分治法不同，直接法本身就具有效率上的優(yōu)勢(shì)，因此在大數(shù)據(jù)時(shí)代更受歡迎．但是，基于條件獨(dú)立性測(cè)試的直接法在高維數(shù)據(jù)中的性能短板更明顯，因此，新提出的算法都著眼于高維數(shù)據(jù)中的效率和實(shí)用性研究，包括：FBEDK[27]、Fit-IAMB[29]和PFBP[30]．此外，基于優(yōu)化的直接法[33]在MB研究中是一種新的思路，該項(xiàng)研究證明條件協(xié)方差算子與MB之間的關(guān)聯(lián)，但并未給出理論上的解，這導(dǎo)致搜索最優(yōu)解的效率不夠高.未來(lái)應(yīng)為該優(yōu)化方法構(gòu)建堅(jiān)實(shí)的理論基礎(chǔ)，支撐其進(jìn)一步發(fā)展和應(yīng)用．

相比單重MB發(fā)現(xiàn)算法，多重MB發(fā)現(xiàn)算法更關(guān)注理論的完備性，而在應(yīng)用層面上更窄.因?yàn)閷?shí)際應(yīng)用場(chǎng)景下常常只需要找到一個(gè)最優(yōu)的特征子集，而不是多個(gè)性能相似的特征子集，因此，該領(lǐng)域近年發(fā)展緩慢，但是多重MB理論應(yīng)用在多標(biāo)簽問(wèn)題上是必要的．文獻(xiàn)[73]～文獻(xiàn)[75]中關(guān)于多標(biāo)簽因果特征選擇的探討都未忽略多重MB的影響，并且其中的實(shí)證研究表明，考慮多重MB對(duì)多標(biāo)簽因果特征選擇具有實(shí)際意義，尤其在定義多個(gè)標(biāo)簽的共有特征和單個(gè)標(biāo)簽的特有特征上[75]．

由于因果特征選擇在真實(shí)世界數(shù)據(jù)中的廣泛應(yīng)用，特殊數(shù)據(jù)中的MB發(fā)現(xiàn)算法是近年的另一個(gè)研究熱點(diǎn)，如流特征[62]、流數(shù)據(jù)[68]、多源數(shù)據(jù)[70-71]、多標(biāo)簽數(shù)據(jù)[73-75]等．這些算法基于單重MB算法的框架和理論，完善和擴(kuò)展特殊數(shù)據(jù)中的因果特征選擇理論和方法．未來(lái)仍存在更多復(fù)雜的低質(zhì)量數(shù)據(jù)場(chǎng)景，有待被進(jìn)一步被解決．

6.2 未來(lái)發(fā)展趨勢(shì)

盡管目前基于因果關(guān)系的特征選擇算法已被大量開(kāi)發(fā)并廣泛應(yīng)用于大數(shù)據(jù)分析，但在這一領(lǐng)域仍需要更多的努力以應(yīng)對(duì)如下挑戰(zhàn).

1)由于直接法步驟中的條件獨(dú)立性測(cè)試遠(yuǎn)少于分治法，使得直接法在效率上具有天然優(yōu)勢(shì)，因此是海量數(shù)據(jù)場(chǎng)景下MB算法的最佳選擇．未來(lái)應(yīng)盡可能地提升直接法在超高維數(shù)據(jù)中的準(zhǔn)確性，使該類(lèi)算法能在大數(shù)據(jù)時(shí)代更實(shí)用．此外，一些不適用條件獨(dú)立性測(cè)試的直接法也應(yīng)在理論上逐步完善，在基于條件獨(dú)立性測(cè)試的性能提升進(jìn)入瓶頸時(shí)，基于結(jié)構(gòu)學(xué)習(xí)或基于優(yōu)化的方法可能為問(wèn)題的解決帶來(lái)新的思路．其中基于優(yōu)化的方法目前仍沒(méi)有有效的方式獲得理論最優(yōu)解，只能在較小的解空間下搜索最優(yōu)解，未來(lái)應(yīng)在該優(yōu)化框架的啟發(fā)下進(jìn)行更廣泛的理論研究，以促進(jìn)單重MB發(fā)現(xiàn)算法獲得更優(yōu)性能．對(duì)于分治法，盡管它們提升特征選擇的魯棒性和可解釋性，但探索因果關(guān)系的過(guò)程卻需要耗費(fèi)大量的時(shí)間．這一缺陷限制分治法在海量高維數(shù)據(jù)中的實(shí)用性．因此，提升MB發(fā)現(xiàn)算法效率的同時(shí)保證算法的可解釋性和魯棒性?xún)?yōu)勢(shì)是當(dāng)前分治法研究的重要課題．直接法和分治法的結(jié)合是否能讓兩類(lèi)方法形成優(yōu)勢(shì)互補(bǔ)，是一個(gè)值得討論的問(wèn)題．此外，一些深度學(xué)習(xí)技術(shù)可用于挖掘變量之間的因果關(guān)系，并進(jìn)一步構(gòu)建MB.例如：圖神經(jīng)網(wǎng)絡(luò)的表示能力已在多個(gè)領(lǐng)域被驗(yàn)證[97]，可表示對(duì)象之間的復(fù)雜關(guān)系，未來(lái)可使用圖神經(jīng)網(wǎng)絡(luò)模型構(gòu)建變量之間的因果圖，獲得目標(biāo)變量的MB．

2)現(xiàn)有的多重MB發(fā)現(xiàn)算法存在很多問(wèn)題．在效率上，當(dāng)前算法包含大量冗余的迭代和不必要的測(cè)試，時(shí)間復(fù)雜度非常高；在準(zhǔn)確性上，現(xiàn)有算法存在較多不可靠的步驟，容易受到級(jí)聯(lián)錯(cuò)誤的影響；在數(shù)據(jù)依賴(lài)性上，現(xiàn)有算法的條件獨(dú)立性測(cè)試都存在將整個(gè)馬爾科夫邊界作為條件集合的問(wèn)題，使數(shù)據(jù)依賴(lài)性非常高．因此，多重MB發(fā)現(xiàn)算法的問(wèn)題需要在效率、準(zhǔn)確性及數(shù)據(jù)依賴(lài)性等多方面進(jìn)行改進(jìn)．此外，多重MB發(fā)現(xiàn)算法在特征選擇問(wèn)題上的應(yīng)用是一個(gè)值得研究的問(wèn)題．當(dāng)目標(biāo)變量存在多個(gè)等價(jià)的MB，意味著這些特征子集在理論上擁有等效的預(yù)測(cè)信息，導(dǎo)致多重MB無(wú)法直接解決特征選擇問(wèn)題．然而實(shí)際應(yīng)用中的特征子集之間在其它方面存在差異，如特征集合的規(guī)模、特征獲取的難易程度和成本、特征在特定學(xué)習(xí)模型中的有效性、特征在不同學(xué)習(xí)模型中的穩(wěn)定性及在不同設(shè)置下的魯棒性等．因此，如何從多重MB中選取合適的特征子集是一個(gè)值得被應(yīng)用領(lǐng)域研究的課題.

3)一些特殊數(shù)據(jù)中的MB發(fā)現(xiàn)問(wèn)題仍未被解決，包括不平衡類(lèi)數(shù)據(jù)、在線學(xué)習(xí)數(shù)據(jù)、弱監(jiān)督數(shù)據(jù)、具有缺失值(或噪聲)的數(shù)據(jù)等．大多數(shù)現(xiàn)有的基于因果關(guān)系的方法不能處理這些場(chǎng)景的MB發(fā)現(xiàn)問(wèn)題，然而，它們?cè)谠S多真實(shí)世界的應(yīng)用程序中是廣泛存在．開(kāi)發(fā)特定的因果特征選擇方法解決這一問(wèn)題非常重要．此外，MB發(fā)現(xiàn)算法當(dāng)前主要的應(yīng)用場(chǎng)景是魯棒的特征選擇、特征與標(biāo)簽之間因果關(guān)系的解釋及特征因果關(guān)系圖的構(gòu)建．未來(lái)可繼續(xù)研究特定應(yīng)用領(lǐng)域的MB發(fā)現(xiàn)算法，提升實(shí)用性．