兩種基于條件獨立性測試的高維數(shù)據(jù)因果關(guān)系推斷算法的比較

洪英漢　夏文棟　郭才

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

【關(guān)鍵詞】高維數(shù)據(jù);因果關(guān)系推斷;維度約簡;網(wǎng)絡(luò)分區(qū)

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

1 研究背景及意義

1.1 研究背景

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

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

1.2 研究的意義

（1）降低高維數(shù)據(jù)因果關(guān)系推斷算法的時間復(fù)雜度，適用于更多場景;

（2）提高因果關(guān)系推斷算法的準確率，提升該領(lǐng)域的算法的可用性;

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

2 兩種高維因果關(guān)系推斷算法的比較

2.1 基于條件集維度約簡的因果關(guān)系推斷算法

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

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

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

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

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

（5）步驟5：重復(fù)執(zhí)行步驟1～4，直到屬于X的節(jié)點都找到對應(yīng)的因果節(jié)點集PC（y）。

（6）步驟6：通過因果節(jié)點集PC（y），把所有的節(jié)點之間的因果關(guān)系連接起來，構(gòu)成完整的因果網(wǎng)絡(luò)圖。

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

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

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

（2）步驟2：通過網(wǎng)絡(luò)分區(qū)的方法把網(wǎng)絡(luò)V分成（V1，V2，C）。

（3） 步驟3：如果|V1∪C|≥δ（δ是規(guī)定變量的個數(shù)）是真的，則對|V1∪C|繼續(xù)執(zhí)行LCSCD算法;否則用PC算法對|V1∪C|進行因果網(wǎng)絡(luò)學(xué)習(xí)。

（4）步驟4：繼續(xù)重復(fù)執(zhí)行步驟4～8，保證所有的子網(wǎng)絡(luò)都進行學(xué)習(xí)。

（5）步驟5：整合所有子網(wǎng)絡(luò)，網(wǎng)絡(luò)邊沖突進行重新識別，最終構(gòu)成完整的因果網(wǎng)絡(luò)圖。

3 總結(jié)

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

【參考文獻】

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

[2]金洲.基于約束學(xué)習(xí)的觀測數(shù)據(jù)因果關(guān)系發(fā)現(xiàn)研究[D]. 合肥：中國科學(xué)技術(shù)大學(xué)， 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]洪英漢.一種快速因果網(wǎng)絡(luò)骨架學(xué)習(xí)算法. 南京理工大學(xué)學(xué)報（自然科學(xué)版）.2016，40（3）：315-321.