基于結構方程似然框架的缺失值因果學習算法

2023-12-16 10:29:10郝志峰喻建華蔡瑞初

計算機工程 2023年12期

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

（1.廣東工業大學計算機學院，廣州 510006；2.汕頭大學理學院，廣東汕頭 515063）

0 概述

因果發現被認為是數據分析中的強大工具［1-3］。在實際場景中，數據缺失問題對因果發現算法的實際應用帶來了巨大挑戰［4］，因為現有的因果發現算法大多數是為完整的數據集而設計的［5-7］。如果直接［7］在缺失數據上進行因果結構網絡學習，可能會存在冗余骨架［8］和錯誤因果方向問題。

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

因此，對于在非隨機缺失數據上，如何識別因果結構網絡中的因果對以及馬爾可夫等價類結構并校正因缺失導致的錯誤因果方向，仍是1 個具有重要意義和挑戰性的問題。本文提出一種基于結構方程似然框架［17］的缺失值因果學習算法MV-SELF。該算法結合結構方程模型可識別馬爾可夫等價類結構、逆概率加權可恢復非隨機缺失數據的聯合分布和基于評分的方法可搜索高維因果結構網絡的優點，使得在非隨機缺失數據上，因果結構網絡學習和校正成為可能。

1 相關工作

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

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

2 缺失值因果學習框架

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

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

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

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

為了在缺失數據上進行因果結構網絡學習，除了因果結構學習算法所需的基本假設［25］（包括因果馬爾可夫假設、因果忠誠性假設、因果充分性假設和無選擇偏差）以外，本文還需以下額外假設來解決缺失數據問題。

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

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

假設3（在缺失指示變量之間無確定性關系）沒有1 個缺失指示變量是其他缺失指示變量的確定性函數。

假設4（無自掩缺失）自掩缺失是指導致部分觀測變量缺失的原因是該缺失變量本身，本文假設不會出現自掩缺失情況。

假設3 和假設4 共同保證了觀測變量聯合分布的可恢復性［18］。

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

本文通過式（2）將非線性加性噪聲模型中原因變量和噪聲變量之間的獨立性檢測轉變為求解全局最大目標評分問題，從而實現對高維因果結構的搜索。

綜上，本文的目標是滿足假設1～假設4，在非隨機缺失數據上識別因果結構網絡中的因果對以及馬爾可夫等價類結構，并校正由缺失導致的錯誤因果方向。

圖2 所示為基于結構方程似然框架的缺失值因果學習框架，其中虛線和虛線箭頭分別表示當前缺失圖中因缺失數據可能產生的冗余邊以及反向邊。因此直接在缺失數據上進行因果結構學習可能導致因果結構學習結果不準確，需要校正因果結構。

圖2 基于結構方程似然框架的缺失值因果學習框架Fig.2 Framework for causal learning of missing values based on structural equation likelihood framework

3 基于結構方程似然框架的缺失值因果學習算法

3.1 缺失數據的因果結構可識別性

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

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

3.2 評分函數

本節先給出標準的貝葉斯網絡目標評分函數，再將逆概率加權加入到評分函數中。為了防止過擬合，大部分的評分函數都需要包含貝葉斯準則即懲罰項，如式（4）所示：

其中：n為變量數；m為樣本量為懲罰項；di為估計Xi所需的系數個數是為了消除因缺失導致的樣本量不同，從而降低對學習目標評分的影響。

結合式（2）和式（3），最后得到的目標評分函數如下：

3.3 算法框架

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

算法 1基于約束的方法學習缺失指示變量的父親結點集

有關蘇聯劇變與戈爾巴喬夫的關系問題，至今還存在不同的看法。有人認為，蘇聯發生劇變完全是戈爾巴喬夫的責任，說是戈爾巴喬夫對蘇聯社會主義叛變行為的結果，甚至說他是叛徒。在這里筆者只是從戈爾巴喬夫改革與蘇聯劇變關系進行簡要分析。筆者認為，在梳理戈爾巴喬夫時期改革與蘇聯劇變關系問題時，應該作出以下兩個不同層次的結論：

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

算法 2基于結構方程似然框架的缺失值因果學習算法

算法2 的主要過程是在當前圖G中添加、反向、刪除1 條邊，然后構造鄰居DAGGnei并且計算其目標評分，最后找出最大目標評分的圖。在缺失數據上的目標評分經過逆概率加權調整，因此可得到正確的因果結構。

4 實驗

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

而結構性漢明距離表示2 個有向無環圖PDAGs中1 個PDAG 通過添加、刪除反向無向邊和有向邊匹配到另1 個PDAG 所需操作的總次數。

4.1 虛擬因果結構數據集

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

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

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

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

圖5 結構維度控制實驗的F1 值Fig.5 F1 values of structure dimension control experiment

圖6 結構維度控制實驗的結構性漢明距離Fig.6 Structural Hamming distance of structure dimension control experiment

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

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

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

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

圖10 樣本數量控制實驗的結構性漢明距離Fig.10 Structural Hamming distance of numble of samples control experiment

4.2 真實因果結構數據集

本文選擇4 個真實結構進行測試（https：//www.bnlearn.com/bnrepository/）。真實結構數據信息如表1 所示。

表1 真實結構數據信息Table 1 Real structure data information

在真實結構數據實驗中，本文分別使用F1 值、準確率、召回率作為評價指標。

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

圖11 真實結構對比實驗的F1 值Fig.11 F1 values of real structure comparison experiment

圖12 真實結構對比實驗的準確率Fig.12 Precision of real structure comparison experiment

圖13 真實結構對比實驗的召回率Fig.13 Recall of real structure comparison experiment

5 結束語

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