基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)算法

郝志峰，喻建華，喬 杰，蔡瑞初

（1.廣東工業(yè)大學(xué) 計算機(jī)學(xué)院，廣州 510006；2.汕頭大學(xué) 理學(xué)院，廣東 汕頭 515063）

0 概述

因果發(fā)現(xiàn)被認(rèn)為是數(shù)據(jù)分析中的強(qiáng)大工具［1-3］。在實際場景中，數(shù)據(jù)缺失問題對因果發(fā)現(xiàn)算法的實際應(yīng)用帶來了巨大挑戰(zhàn)［4］，因為現(xiàn)有的因果發(fā)現(xiàn)算法大多數(shù)是為完整的數(shù)據(jù)集而設(shè)計的［5-7］。如果直接［7］在缺失數(shù)據(jù)上進(jìn)行因果結(jié)構(gòu)網(wǎng)絡(luò)學(xué)習(xí)，可能會存在冗余骨架［8］和錯誤因果方向問題。

為解決在非隨機(jī)缺失數(shù)據(jù)上學(xué)習(xí)因果結(jié)構(gòu)網(wǎng)絡(luò)問題，現(xiàn)有缺失值因果結(jié)構(gòu)學(xué)習(xí)算法分為基于約束的方法［1］和基于結(jié)構(gòu)方程模型的方法［9］?；诩s束的方法包括基于獨立性的方法和基于評分的方法［10］2 類，基于獨立性的方法分析不同缺失機(jī)制對條件獨立性（Conditional Independence，CI）測試［11］結(jié)果的影響，從而通過校正條件獨立性測試結(jié)果來實現(xiàn)因果結(jié)構(gòu)學(xué)習(xí)，如MVPC 算法［8］。基于評分的方法將目標(biāo)評分函數(shù)與逆概率加權(quán)［12］（Inverse Probability Weight，IPW）相結(jié)合，從而解決在非隨機(jī)缺失數(shù)據(jù)上因果結(jié)構(gòu)校正問題，如HC-IPW 算法［13］。然而，這2 類方法都無法識別因果結(jié)構(gòu)網(wǎng)絡(luò)中的因果對［14］以及馬爾可夫等價類結(jié)構(gòu)［15］，因此無法校正在這些結(jié)構(gòu)中出現(xiàn)的錯誤因果方向?；诮Y(jié)構(gòu)方程模型的方法，如MissDAG 算法［16］，通過假設(shè)缺失數(shù)據(jù)類型為隨機(jī)缺失，并結(jié)合非線性加性噪聲模型［14］（Additive Noise Model，ANM）的可識別性假設(shè)來最大化插入值的目標(biāo)似然，而這種假設(shè)缺失數(shù)據(jù)類型是隨機(jī)缺失方法，并不符合實際場景要求。

因此，對于在非隨機(jī)缺失數(shù)據(jù)上，如何識別因果結(jié)構(gòu)網(wǎng)絡(luò)中的因果對以及馬爾可夫等價類結(jié)構(gòu)并校正因缺失導(dǎo)致的錯誤因果方向，仍是1 個具有重要意義和挑戰(zhàn)性的問題。本文提出一種基于結(jié)構(gòu)方程似然框架［17］的缺失值因果學(xué)習(xí)算法MV-SELF。該算法結(jié)合結(jié)構(gòu)方程模型可識別馬爾可夫等價類結(jié)構(gòu)、逆概率加權(quán)可恢復(fù)非隨機(jī)缺失數(shù)據(jù)的聯(lián)合分布和基于評分的方法可搜索高維因果結(jié)構(gòu)網(wǎng)絡(luò)的優(yōu)點，使得在非隨機(jī)缺失數(shù)據(jù)上，因果結(jié)構(gòu)網(wǎng)絡(luò)學(xué)習(xí)和校正成為可能。

1 相關(guān)工作

近年來，得益于描述缺失過程的缺失圖［18］以及可恢復(fù)性［19］概念確立，缺失值因果學(xué)習(xí)研究得到較快發(fā)展。在缺失值因果學(xué)習(xí)研究中，缺失圖也被稱為因果圖，給定1 個缺失圖，如果1 個查詢（如條件或聯(lián)合分布和因果效應(yīng)）可以得到一致估計，則被認(rèn)為是可恢復(fù)的。

在非隨機(jī)缺失設(shè)定中，STROBL 等［20］將缺失機(jī)制視為一種特殊類型的選擇偏差，以處理非隨機(jī)缺失因果結(jié)構(gòu)網(wǎng)絡(luò)學(xué)習(xí)問題，并提出基于測試刪除（Test-wise Deletion，TD）的FCI 算法［1］。然而，缺失機(jī)制一般比選擇偏差提供了更多的缺失狀態(tài)信息，而選擇偏差僅提供選擇后的樣本分布，因此，選擇后的樣本分布是有偏的。為了對非隨機(jī)缺失數(shù)據(jù)的聯(lián)合分布進(jìn)行校正，文獻(xiàn)［21］使用逆概率加權(quán)對條件獨立性測試結(jié)果進(jìn)行糾正，但假設(shè)缺失因果模型是已知的，這并不適用于實際應(yīng)用場景。為此，TU 等［8］提出MVPC 算法，指出測試刪除可能會導(dǎo)致因果骨架冗余，并使用基于排列的校正方法和逆概率加權(quán)的校正方法對缺失數(shù)據(jù)的聯(lián)合分布進(jìn)行校正。但是，基于排列的校正方法僅適合缺失指示變量與缺失變量之間可被d-分離的場景，而不適合缺失指示變量與缺失變量不可被d-分離的場景。而Structure EM 算法［22］通過在候選模型中選擇1 個模型作為當(dāng)前模型，并和訓(xùn)練數(shù)據(jù)一起執(zhí)行標(biāo)準(zhǔn)的EM 算法［23］得到最大似然對應(yīng)的參數(shù)值，然后固定得到的參數(shù)值來迭代候選模型，直至找到最大似然對應(yīng)的候選模型作為當(dāng)前模型，依次交替迭代上面過程直至收斂。因此，Structure EM 算法僅適用缺失機(jī)制可忽略的場景，不適合非隨機(jī)缺失數(shù)據(jù)上的因果結(jié)構(gòu)網(wǎng)絡(luò)學(xué)習(xí)。

2 缺失值因果學(xué)習(xí)框架

為了描述所解決的問題并介紹因果結(jié)構(gòu)的學(xué)習(xí)框架，本節(jié)需要形式化定義一些前置概念，如缺失圖、缺失圖類型以及處理缺失所需的假設(shè)知識。

本文定義缺失圖G={V,E}來表達(dá)因果結(jié)構(gòu)網(wǎng)絡(luò)。其中V=Vo∪Vm∪U∪V*∪R，Vo是完全觀測變量集，在缺失圖中使用白色實線結(jié)點表示。Vm表示至少含有1 條缺失記錄的部分觀測變量集，在缺失圖中使用灰色實線結(jié)點表示。U表示未觀測到的變量集，本文假設(shè)滿足因果充分性假設(shè)，因此U是空集。V*是代理變量集，R表示缺失因果機(jī)制集，也就是缺失指示變量集，在缺失圖中使用白色實線結(jié)點表示。RVi具體值表示Vi*是否缺失狀態(tài)信息，如式（1）所示：

用大寫字母Xi表示第i個變量結(jié)點，以及結(jié)點間的因果邊集合E={(i,j)|Xi→Xj}。本文用小寫字母x表示樣本，令數(shù)據(jù)集，其樣本量大小為m。若滿足直接因果關(guān)系Xi→Xj，則稱Xi是Xj的父母，如果存在間接因果邊使得Xi→Xk→Xj，并稱Xi是Xj的祖先。本文記Xi⊥GXj|S為給定條件集S，Xi與Xj在圖G上條件獨立。

缺失圖的類型示意圖如圖1 所示。根據(jù)缺失數(shù)據(jù)問題分類方法，可將缺失圖分為3 類［24］，如果在缺失圖中滿足Vm∪Vo∪U⊥R，那么缺失數(shù)據(jù)是完全隨機(jī)缺失（Missing Completely At Random，MCAR），如圖1（a）所示。如果在缺失圖中滿足Vm∪U⊥R|Vo，那么缺失數(shù)據(jù)是隨機(jī)缺失（Missing At Random，MAR），如圖1（b）所示。如果缺失圖類型既不是MAR 也不是MCAR，那么屬于非隨機(jī)缺失（Missing Not At Random，MNAR），如圖1（c）所示。

為了在缺失數(shù)據(jù)上進(jìn)行因果結(jié)構(gòu)網(wǎng)絡(luò)學(xué)習(xí)，除了因果結(jié)構(gòu)學(xué)習(xí)算法所需的基本假設(shè)［25］（包括因果馬爾可夫假設(shè)、因果忠誠性假設(shè)、因果充分性假設(shè)和無選擇偏差）以外，本文還需以下額外假設(shè)來解決缺失數(shù)據(jù)問題。

假設(shè)1（缺失指示變量不能是任何觀測變量的原因）該假設(shè)在大多數(shù)缺失圖相關(guān)工作［18-19］中被采用，在該假設(shè)下，如果給定條件集和指示變量集，感興趣的變量之間獨立，那么僅給定條件集，感興趣的變量仍獨立。

假設(shè)2（忠誠觀察性）任何在觀測到的數(shù)據(jù)集中成立的條件獨立性關(guān)系同樣也在未觀測到的數(shù)據(jù)集中成立，形式化為X⊥Y|{Z,Rk=0}?X⊥Y|{Z,Rk=1}。該假設(shè)意味著缺失數(shù)據(jù)中的條件獨立性關(guān)系在完整數(shù)據(jù)中也成立，即不存在由缺失引起的意外條件獨立性關(guān)系。

假設(shè)3（在缺失指示變量之間無確定性關(guān)系）沒有1 個缺失指示變量是其他缺失指示變量的確定性函數(shù)。

假設(shè)4（無自掩缺失）自掩缺失是指導(dǎo)致部分觀測變量缺失的原因是該缺失變量本身，本文假設(shè)不會出現(xiàn)自掩缺失情況。

假設(shè)3 和假設(shè)4 共同保證了觀測變量聯(lián)合分布的可恢復(fù)性［18］。

圖1 將缺失圖和非線性加性噪聲模型相結(jié)合，其中虛線圈結(jié)點表示注入結(jié)果變量的獨立噪聲。由于非線性加性噪聲模型不適合高維因果結(jié)構(gòu)網(wǎng)絡(luò)搜索，因此需要將非線性加性噪聲模型擴(kuò)展至高維場景［17］，如式（2）所示：

本文通過式（2）將非線性加性噪聲模型中原因變量和噪聲變量之間的獨立性檢測轉(zhuǎn)變?yōu)榍蠼馊肿畲竽繕?biāo)評分問題，從而實現(xiàn)對高維因果結(jié)構(gòu)的搜索。

綜上，本文的目標(biāo)是滿足假設(shè)1～假設(shè)4，在非隨機(jī)缺失數(shù)據(jù)上識別因果結(jié)構(gòu)網(wǎng)絡(luò)中的因果對以及馬爾可夫等價類結(jié)構(gòu)，并校正由缺失導(dǎo)致的錯誤因果方向。

圖2 所示為基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)框架，其中虛線和虛線箭頭分別表示當(dāng)前缺失圖中因缺失數(shù)據(jù)可能產(chǎn)生的冗余邊以及反向邊。因此直接在缺失數(shù)據(jù)上進(jìn)行因果結(jié)構(gòu)學(xué)習(xí)可能導(dǎo)致因果結(jié)構(gòu)學(xué)習(xí)結(jié)果不準(zhǔn)確，需要校正因果結(jié)構(gòu)。

圖2 基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)框架Fig.2 Framework for causal learning of missing values based on structural equation likelihood framework

3 基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)算法

3.1 缺失數(shù)據(jù)的因果結(jié)構(gòu)可識別性

本文簡述缺失數(shù)據(jù)的因果結(jié)構(gòu)可識別性以及逆概率加權(quán)校正方法。給定1 個缺失圖，如果變量的聯(lián)合分布可通過缺失數(shù)據(jù)變量表示出來，則變量的聯(lián)合分布被認(rèn)為是可恢復(fù)的，在進(jìn)一步滿足因果模型所需的假設(shè)時，本文認(rèn)為觀測數(shù)據(jù)的因果結(jié)構(gòu)是可識別的，除此之外，還存在一些無法通過缺失數(shù)據(jù)變量來表示變量聯(lián)合分布但仍滿足因果模型假設(shè)的特殊可識別場景，如圖1（d）所示。本文主要討論變量的聯(lián)合分布可恢復(fù)情況。

由于本文觀測到的缺失數(shù)據(jù)分布為P(Xi|Pa(Xi),R=0)，因此根據(jù)缺失圖類型分析，當(dāng)缺失圖類型 為MCAR 時，P(Xi|Pa(Xi),R=0)=P(Xi|Pa(Xi))，顯然可通過缺失變量表示真實變量聯(lián)合分布，不影響因果結(jié)構(gòu)學(xué)習(xí)。但是當(dāng)缺失圖類型為MAR 或MNAR時，P(Xi|Pa(Xi),R=0)≠P(Xi|Pa(Xi))，此時無法通過缺失數(shù)據(jù)變量表示真實變量的聯(lián)合分布。

因此，本文利用逆概率加權(quán)工具對有偏的聯(lián)合分布進(jìn)行校正，如式（3）所示：

3.2 評分函數(shù)

本節(jié)先給出標(biāo)準(zhǔn)的貝葉斯網(wǎng)絡(luò)目標(biāo)評分函數(shù)，再將逆概率加權(quán)加入到評分函數(shù)中。為了防止過擬合，大部分的評分函數(shù)都需要包含貝葉斯準(zhǔn)則即懲罰項，如式（4）所示：

其中：n為變量數(shù)；m為樣本量為懲罰項；di為估計Xi所需的系數(shù)個數(shù)是為了消除因缺失導(dǎo)致的樣本量不同，從而降低對學(xué)習(xí)目標(biāo)評分的影響。

結(jié)合式（2）和式（3），最后得到的目標(biāo)評分函數(shù)如下：

3.3 算法框架

本文將設(shè)計算法流程來求解評分函數(shù)的最大似然。觀察目標(biāo)評分函數(shù)式（5）可得，c是常數(shù)，校正的關(guān)鍵是求，而要求 解βRi須先求Pari，如算法1 所示。

算法 1基于約束的方法學(xué)習(xí)缺失指示變量的父親結(jié)點集

有關(guān)蘇聯(lián)劇變與戈爾巴喬夫的關(guān)系問題，至今還存在不同的看法。有人認(rèn)為，蘇聯(lián)發(fā)生劇變完全是戈爾巴喬夫的責(zé)任，說是戈爾巴喬夫?qū)μK聯(lián)社會主義叛變行為的結(jié)果，甚至說他是叛徒。在這里筆者只是從戈爾巴喬夫改革與蘇聯(lián)劇變關(guān)系進(jìn)行簡要分析。筆者認(rèn)為，在梳理戈爾巴喬夫時期改革與蘇聯(lián)劇變關(guān)系問題時，應(yīng)該作出以下兩個不同層次的結(jié)論：

為進(jìn)一步求解βRi，本文需要確定成對刪除處理缺失數(shù)據(jù)集所涉及到的結(jié)點集W以及逆概率加權(quán)求解所需的充分變量集U。首先有當(dāng)前的最佳DAGG與下一步將要搜索的DAGGnei2 個圖，將這2 個圖進(jìn)行比較，2 個圖中父親結(jié)點集不相同的結(jié)點為Vi，則成對刪除所涉及的變量集W=由于在求解Pa(Vi)和Pa(Vi)nei時可能會引入新的缺失變量和中含有，因此需要迭代并入當(dāng)前集合中缺失變量Xi的操作。最終得到充分變量集是1 個遞歸的過程，直至所涉及到的變量集不再更新為止，其作用如算法2 所示。

算法 2基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)算法

算法2 的主要過程是在當(dāng)前圖G中添加、反向、刪除1 條邊，然后構(gòu)造鄰居DAGGnei并且計算其目標(biāo)評分，最后找出最大目標(biāo)評分的圖。在缺失數(shù)據(jù)上的目標(biāo)評分經(jīng)過逆概率加權(quán)調(diào)整，因此可得到正確的因果結(jié)構(gòu)。

4 實驗

本文將分別使用虛擬因果結(jié)構(gòu)數(shù)據(jù)和真實因果結(jié)構(gòu)數(shù)據(jù)對模型進(jìn)行評估，并將MV-SELF 算法與主流的缺失值因果學(xué)習(xí)算法MVPC、TD-PC 算法［8］和Structure EM 算法相比較。為驗證在非隨機(jī)缺失數(shù)據(jù)上的有效性，本文將所有實驗的缺失機(jī)制設(shè)為非隨機(jī)缺失，將隨機(jī)選擇因果結(jié)構(gòu)上1/2 的結(jié)點作為缺失變量。導(dǎo)致缺失的原因是變量優(yōu)先考慮缺失變量的缺失孩子結(jié)點，若缺失變量沒有缺失孩子結(jié)點，則隨機(jī)選取除自身以外的其他缺失變量作為原因變量。對于某個變量導(dǎo)致的缺失，設(shè)定為：例如X導(dǎo)致Y缺失，當(dāng)X值增大時，對應(yīng)Y的值以概率P=0.1 缺失，反之對應(yīng)Y的值以概率P=0.8 缺失。所有的參數(shù)敏感性實驗都至少運行100 次以上，采用F1 值（F1）、準(zhǔn)確率（P）、召回率（R）和結(jié)構(gòu)性漢明距離［26］（Structural Hamming Distance，SHD）作為評價指標(biāo)，計算表達(dá)式如下：

而結(jié)構(gòu)性漢明距離表示2 個有向無環(huán)圖PDAGs中1 個PDAG 通過添加、刪除反向無向邊和有向邊匹配到另1 個PDAG 所需操作的總次數(shù)。

4.1 虛擬因果結(jié)構(gòu)數(shù)據(jù)集

本文在虛擬結(jié)構(gòu)數(shù)據(jù)上進(jìn)行4 個控制變量實驗，缺失變量數(shù)={4,7,10,13,16}，結(jié)構(gòu)維度={5,10,15,20,25}，平均入度={0.5,1.0,1.5,2.0}，以及樣本數(shù)量={1 000,3 000,5 000,7 000,9 000}實驗，加粗表示實驗中設(shè)置的默認(rèn)參數(shù)，其中結(jié)構(gòu)維度敏感度實驗中缺失變量個數(shù)設(shè)定為總結(jié)點數(shù)的1/2。

圖3 缺失變量控制實驗的F1 值Fig.3 F1 values of missing variables control experiment

圖4 缺失變量控制實驗的結(jié)構(gòu)性漢明距離Fig.4 Structural Hamming distance of missing variables control experiment

圖5 和圖6 所示為控制結(jié)構(gòu)維度的實驗結(jié)果。從圖5 和圖6 可以看出，MV-SELF 算法在結(jié)構(gòu)維度比較大時同樣有效，說明結(jié)構(gòu)維度對MV-SELF 算法的影響很小。因此，MV-SELF 算法在不同維度下具有較優(yōu)的魯棒性。

圖5 結(jié)構(gòu)維度控制實驗的F1 值Fig.5 F1 values of structure dimension control experiment

圖6 結(jié)構(gòu)維度控制實驗的結(jié)構(gòu)性漢明距離Fig.6 Structural Hamming distance of structure dimension control experiment

圖7 和圖8 所示為控制平均入度的實驗結(jié)果。從圖7 和圖8 可以看出，MV-SELF 算法在稀疏結(jié)構(gòu)下表現(xiàn)較優(yōu)，而在稠密結(jié)構(gòu)下表現(xiàn)不佳，但其實驗結(jié)果仍優(yōu)于其他對比算法。其原因為在稠密結(jié)構(gòu)下準(zhǔn)確計算逆概率加權(quán)依賴于缺失指示變量的父親結(jié)點βRi，從而導(dǎo)致難度增大，造成實驗效果下降。但MV-SELF算法的實驗結(jié)果仍然比其他對比算法要好，因此實驗結(jié)果驗證MV-SELF 算法的有效性。

圖7 平均入度控制實驗的F1 值Fig.7 F1 values of average penetration control experiment

圖8 平均入度控制實驗的結(jié)構(gòu)性漢明距離Fig.8 Structural Hamming distance of average penetration control experiment

圖9 和圖10 所示為控制樣本量的實驗結(jié)果。從圖9 和圖10 可以看出，MV-SELF 算法隨著樣本數(shù)量增加效果越好，說明樣本數(shù)量有助于實驗效果的提升，并且MV-SELF 算法明顯優(yōu)于其他比較方法，說明MV-SELF 算法具有一定的有效性。

圖10 樣本數(shù)量控制實驗的結(jié)構(gòu)性漢明距離Fig.10 Structural Hamming distance of numble of samples control experiment

4.2 真實因果結(jié)構(gòu)數(shù)據(jù)集

本文選擇4 個真實結(jié)構(gòu)進(jìn)行測試（https：//www.bnlearn.com/bnrepository/）。真實結(jié)構(gòu)數(shù)據(jù)信息如表1 所示。

表1 真實結(jié)構(gòu)數(shù)據(jù)信息Table 1 Real structure data information

在真實結(jié)構(gòu)數(shù)據(jù)實驗中，本文分別使用F1 值、準(zhǔn)確率、召回率作為評價指標(biāo)。

本文在真實結(jié)構(gòu)數(shù)據(jù)中設(shè)定與虛擬結(jié)構(gòu)數(shù)據(jù)實驗中相同的實驗環(huán)境。圖11～圖13 所示為不同真實結(jié)構(gòu)數(shù)據(jù)的實驗結(jié)果。從圖11～圖13 可以看到，MV-SELF 算法在不同的真實結(jié)構(gòu)中均獲得了最好的效果，特別是在ASIA 結(jié)構(gòu)下實現(xiàn)了最佳效果，其原因為ASIA 的平均入度最低，這與虛擬結(jié)構(gòu)數(shù)據(jù)的實驗結(jié)果相吻合。與對比算法相比，本文所提算法MV-SELF 的準(zhǔn)確率和召回率均較高，說明比較算法更容易學(xué)習(xí)到冗余邊。由于比較算法沒有考慮到因果結(jié)構(gòu)網(wǎng)絡(luò)的馬爾可夫等價類結(jié)構(gòu)，因此出現(xiàn)更多錯誤邊是合理的，這也證明了MV-SELF算法的有效性。

圖11 真實結(jié)構(gòu)對比實驗的F1 值Fig.11 F1 values of real structure comparison experiment

圖12 真實結(jié)構(gòu)對比實驗的準(zhǔn)確率Fig.12 Precision of real structure comparison experiment

圖13 真實結(jié)構(gòu)對比實驗的召回率Fig.13 Recall of real structure comparison experiment

5 結(jié)束語

本文提出一種基于結(jié)構(gòu)方程似然框架的缺失值因果學(xué)習(xí)算法。通過結(jié)合基于非線性加性噪聲模型、逆概率加權(quán)校正工具，以及基于評分的方法優(yōu)點，使得在非隨機(jī)缺失數(shù)據(jù)上也能進(jìn)行因果結(jié)構(gòu)學(xué)習(xí)和校正。實驗結(jié)果表明，該算法在虛擬因果結(jié)構(gòu)數(shù)據(jù)集以及真實因果結(jié)構(gòu)數(shù)據(jù)集上都具有較優(yōu)的表現(xiàn)。下一步將對存在自掩缺失的因果結(jié)構(gòu)學(xué)習(xí)問題進(jìn)行研究。