兩種基于條件獨立性測試的高維數據因果關系推斷算法的比較

洪英漢　夏文棟　郭才

【摘 要】機器直覺推理與因果模型的研究是AI基礎理論體系的重要組成部分之一。針對目前因果關系推斷在高維數據情況下，傳統的基于條件獨立性測試出現消耗時間多和準確率差等現象。本文對兩種基于條件獨立性測試的高維數據因果關系推斷算法進行比較：一種是通過降低條件集維度的方法、另外一種是構建粗糙網絡及分裂-合并策略方法，每個算法都有其優缺點。通過分析總結，在今后的工作中，可以根據實際情況選擇合適的方法來解決高維數據因果關系推斷問題。

【關鍵詞】高維數據;因果關系推斷;維度約簡;網絡分區

中圖分類號： TP18 文獻標識碼： A 文章編號： 2095-2457（2019）01-0116-002

1 研究背景及意義

1.1 研究背景

隨著人工智能技術的在全球的迅猛發展，它的貢獻將深刻影響了人類社會生活模式，把人類社會帶進了“第四次工業革命”。在新的國家人工智能發展規劃中，也提到了新一代強AI的基礎理論體系包括“機器直覺推理與因果模型”。Judea Pearl在近期的國際會議上發表了前沿的論文“Theoretical Impediments to Machine Learning With Seven Sparks from the Causal Revolution”，該論文提出了機器學習（ML）無法成為強AI基礎，人工智能研究方向由模仿“人腦”轉向“因果推理”[1]。

因果推斷跟傳統的關聯規則不一樣的，關聯關系只是簡單地從事物的現象觀察統計到事物與事物之間存在相關性，而因果關系推斷則是透過事物表明，反映了事物內部的機制，而且還決定方向“誰因誰果”，因此因果關系推斷真是我們要研究的科學問題以及可以為人工智能等領域提供強有力的理論基礎支撐。在現實世界里，因果關系更為復雜，主要表現是：影響事物的因素眾多，而且因素變量常常是高維的。例如社交網絡領域、經濟學領域、基因工程領域等是目前數據科學的研究熱點領域，但是這些領域的特點是數據量大、數據維度高。雖然這些高維數據復雜難以處理，但是復雜的網絡結構下蘊藏了豐富的事物規則，研究這方面的課題可以產生巨大的經濟價值和社會價值。

1.2 研究的意義

（1）降低高維數據因果關系推斷算法的時間復雜度，適用于更多場景;

（2）提高因果關系推斷算法的準確率，提升該領域的算法的可用性;

（3）理論與實際相結合，為算法的順利推廣提供良好的基礎。

2 兩種高維因果關系推斷算法的比較

2.1 基于條件集維度約簡的因果關系推斷算法

在文獻【】中提出了一種基于條件集維度簡約的快速因果網絡學習方法，通過該算法可以快速的推斷出因果網絡結構。其算法與傳統算法快速的關鍵是利用mRMR算法能給找到2個節點y、x的候選馬爾科夫毯節點集的并集P=PcxUPcy。分析該方法與傳統PC算法的區別是：PC算法在除掉y、x的n-2個節點中關于y、x的條件獨立測試集合，而基于維度簡約的條件獨立性測試的條件集規模比PC算法要小很多，PC算法要在n-2的節點集里面求任意組合，而維度約簡方法則是在|PAxUPAy|<2m個節點求任意組合。特別是高維情況下2m<<（n-2），基于維度約簡的條件獨立性測試的所表現出來的速度會比PC算法好。不過，在進行mRMR算法尋找馬爾科夫毯的過程中，難免存在一些冗余變量，從而導致影響了條件獨立性測試的準確率，不過總體來說還是可以接受的。條件集維度約簡算法的流程如下：

（1）步驟1：在n維數據集X={x1，x2，…，xn}，對其節點集任意尋找一個節點xi，設xi=y，然后對y的父子節點集初始化為PC（y）={ }。

（2）步驟2：求出y的一個父親節點xi，在節點集合X＼xi中，選取任意節點xj∈X＼xi。

（3）步驟3：利用mRMR算法，求出y和xj的得到共同候選父子節點集Sx，y。

（4）步驟4：對節點集Sx，y的任意子集做條件獨立測試，如果存在節點集S，S屬于Sx，y，使得xi┴y|S，則xi與y不存在因果節點，選取X＼xj，xi，循環執行步驟2～4，如果沒有S條件集可以使得xi是y能夠D分離，則xi與y是因果節點，將xi加入PC（y）。

（5）步驟5：重復執行步驟1～4，直到屬于X的節點都找到對應的因果節點集PC（y）。

（6）步驟6：通過因果節點集PC（y），把所有的節點之間的因果關系連接起來，構成完整的因果網絡圖。

2.2 基于低階條件獨立測試的因果關系推斷算法

在做基于約束的因果關系推斷方法中，條件獨立測試是一個關鍵的過程，它能夠判斷網絡中的節點x，y之間是否獨立，從而覺得是否給x，y存在邊。然而，隨著維度數量的增長，條件集的所有組合也呈指數級增長。目前基于低階的條件獨立測試方法的總體思想就是首先通過低階的條件獨立測試，意思就是控制條件獨立測試集合的數量，保證算法執行的速度，第一階段迅速地生成粗糙的因果網絡圖。第二階段，網絡通過分裂成多個子網絡，再次降低大網絡的維度，然后對各個子網絡進行條件獨立測試以求得因果網絡子圖。第三階段就是通過子網絡的整合方法，去掉冗余邊，最終整合成完整的因果網絡圖。這樣的算法比傳統的分裂-合并方法速度更快，因為傳統的分裂子網絡的每個子網絡都是完整邊圖，而我們的方法則是相對稀疏的網絡圖，消耗時間相對比較少。其算法LCSCD流程描述如下：

（1）步驟1：在n維數據集V={v1，v2，…，vn}，構建一個完整的全連接圖。

（2）步驟2：通過網絡分區的方法把網絡V分成（V1，V2，C）。

（3） 步驟3：如果|V1∪C|≥δ（δ是規定變量的個數）是真的，則對|V1∪C|繼續執行LCSCD算法;否則用PC算法對|V1∪C|進行因果網絡學習。

（4）步驟4：繼續重復執行步驟4～8，保證所有的子網絡都進行學習。

（5）步驟5：整合所有子網絡，網絡邊沖突進行重新識別，最終構成完整的因果網絡圖。

3 總結

本文討論了兩種高維網絡的因果關系推斷算法，基于條件集維度簡約的快速因果網絡學習方法是通過mRMR算法對條件集進行約簡，從而減少條件獨立測試的次數;而基于低階條件獨立測試的因果關系推斷算法是先使得條件集數量少于m個進行粗糙因果網絡學習，然后在進行分裂-合并策略把大問題分解成小問題。每種算法各有利弊，在今后的工作中，將對這兩種算法進行改進，爭取能夠把算法的時間復雜度降低同時準確率提高。

【參考文獻】

[1]https：//baijiahao.baidu.com/s？id=1589723721812697687&wfr=spider&for=pc.

[2]金洲.基于約束學習的觀測數據因果關系發現研究[D]. 合肥：中國科學技術大學， 2014.

[3]Y Hong， Z Liu， G Mai. An efficient algorithm for large-scale causal discovery[J]. Soft Computing， 2016， 21（24）：1-11.

[4]Yinghan Hong， Zhifeng Hao， Guizhen Mai， Bingfeng Chen ， Rui Xie. An Approach for Inferring Causal Directions from Multi-dimensional Networks. 2017 IEEE International Conference on Computational Science & Engineering. 2017 ： 388-392.

[5]洪英漢.一種快速因果網絡骨架學習算法. 南京理工大學學報（自然科學版）.2016，40（3）：315-321.