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

摘要

因果特征選擇算法(也稱為馬爾科夫邊界發(fā)現(xiàn))學(xué)習(xí)目標(biāo)變量的馬爾科夫邊界,選擇與目標(biāo)存在因果關(guān)系的特征,具有比傳統(tǒng)方法更好的可解釋性和魯棒性.文中對(duì)現(xiàn)有因果特征選擇算法進(jìn)行全面綜述,分為單重馬爾科夫邊界發(fā)現(xiàn)算法和多重馬爾科夫邊界發(fā)現(xiàn)算法.基于每類算法的發(fā)展歷程,詳細(xì)介紹每類的經(jīng)典算法和研究進(jìn)展,對(duì)比它們?cè)跍?zhǔn)確性、效率、數(shù)據(jù)依賴性等方面的優(yōu)劣.此外,進(jìn)一步總結(jié)因果特征選擇在特殊數(shù)據(jù)(半監(jiān)督數(shù)據(jù)、多標(biāo)簽數(shù)據(jù)、多源數(shù)據(jù)、流數(shù)據(jù)等)中的改進(jìn)和應(yīng)用.最后,分析該領(lǐng)域的當(dāng)前研究熱點(diǎn)和未來(lái)發(fā)展趨勢(shì),并建立因果特征選擇資料庫(kù),匯總該領(lǐng)域常用的算法包和數(shù)據(jù)集.

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

傳統(tǒng)的特征選擇算法主要分為封裝法、過濾法和嵌入法三類[7].封裝法[8]為不同的特征子集訓(xùn)練一個(gè)學(xué)習(xí)器, 評(píng)估其在該特征子集上的表現(xiàn), 決定所選特征子集.過濾法[9]使用一個(gè)評(píng)估函數(shù), 為特征評(píng)分并選擇分?jǐn)?shù)較高的特征, 因此不依賴額外的分類器, 更高效.嵌入法[10]將特征選擇過程嵌入學(xué)習(xí)過程中, 同時(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), 因果特征選擇算法被廣泛研究.該類算法通過學(xué)習(xí)目標(biāo)變量的馬爾科夫邊界(Markov Boundary, MB)[14]以尋找關(guān)鍵特征, 因此又被稱為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)變量周圍的局部因果關(guān)系, 給定目標(biāo)變量的MB作為條件集合, 其它特征條件獨(dú)立于目標(biāo)變量[14].基于此屬性:Tsamardinos等[15]證明在分類問題中, 類別變量的MB是具有最大預(yù)測(cè)性的最小特征子集; Pellet等[16]證明類別變量的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)變量周圍的因果特征.本文對(duì)現(xiàn)有因果特征選擇方法進(jìn)行較全面的研究和綜述.

基于原理與現(xiàn)有方法分類

1.問題定義與基礎(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提供變量周圍的局部因果結(jié)構(gòu), 父節(jié)點(diǎn)、子節(jié)點(diǎn)、配偶節(jié)點(diǎn)分別對(duì)應(yīng)目標(biāo)變量的直接原因、直接結(jié)果、直接結(jié)果的其它原因.MB發(fā)現(xiàn)算法通過挖掘變量的局部因果結(jié)構(gòu), 無(wú)需學(xué)習(xí)完整的貝葉斯網(wǎng)絡(luò)即可找到變量的MB.而變量的MB集合有一個(gè)特殊的統(tǒng)計(jì)特性, 見定理1.

圖1 馬爾科夫邊界的例子

Fig.1 An example of Markov boundary

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

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

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

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

2.現(xiàn)有馬爾科夫邊界學(xué)習(xí)方法分類及其基本原理

圖2給出本文對(duì)現(xiàn)有MB發(fā)現(xiàn)算法的分類.常規(guī)數(shù)據(jù)中的MB發(fā)現(xiàn)算法主要分為單重MB發(fā)現(xiàn)算法和多重MB發(fā)現(xiàn)算法, 這兩類算法的應(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, 該類算法稱為單重MB發(fā)現(xiàn)算法.另一部分算法考慮忠實(shí)性假設(shè)被違反的情況, 這些算法可挖掘目標(biāo)變量的多個(gè)等價(jià)MB, 該類算法稱為多重MB發(fā)現(xiàn)算法.特殊數(shù)據(jù)中的MB發(fā)現(xiàn)算法作為一類單獨(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)算法.本文按照上述分類介紹現(xiàn)有算法的特點(diǎn).

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

Fig.2 Categories of existing MB discovery algorithms

單重MB發(fā)現(xiàn)算法假設(shè)目標(biāo)變量有唯一的MB, 輸出的MB集合可直接作為特征選擇的結(jié)果.該類算法主要分為兩類:直接的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)算法可通過條件獨(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ū)別

Fig.3 Difference between direct methods and divide-and-conquer methods

可用于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], 該類算法存在的意義是: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)沒有發(fā)生信息等價(jià)時(shí), 目標(biāo)變量有一個(gè)唯一的MB集合[21].

根據(jù)定理5, 多重MB與等價(jià)信息現(xiàn)象是共存的, 因此尋找多個(gè)MB的過程也就是識(shí)別等價(jià)信息的過程[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ù)中.

審核編輯：湯梓紅