近日，我校郭建華教授團隊在因果推斷算法研究上取得重要突破。郭建華教授團隊在國際機器學習與人工智能頂級會議——第四十二屆國際機器學習會議（International Conference on Machine Learning, ICML）上提交的論文“An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer”（基于超團轉(zhuǎn)移的團選取算法快速計算馬爾可夫等價類規(guī)模），入選全部投稿論文前1%，被評選為口頭報告論文。
該會議共收到專家學者投稿論文共計12107篇，其中僅有120篇被評選為口頭報告。會議審稿人對郭建華教授團隊提交的論文給予高度認可，一致認為：“這篇論文解決了高效計算馬爾可夫等價類規(guī)模這一重要的算法問題，極大提升了現(xiàn)有方法的效率。這種計算能力對貝葉斯實驗設(shè)計方法尤其重要。論文在算法方面作出了重要的貢獻，并提供了扎實的理論支撐”。
圖1:會議論文截圖
本項論文成果由郭建華教授（通訊作者）帶領(lǐng)研究，東北師范大學數(shù)學與統(tǒng)計學院博士研究生劉力夫、北京工商大學數(shù)學與統(tǒng)計學院副教授賀詩源為共同第一作者。該研究聚焦因果推理領(lǐng)域，具體針對高效計算有向無環(huán)圖（Directed Acyclic Graph, DAG）的馬爾可夫等價類（Markov Equivalence Class, MEC）規(guī)模這一關(guān)鍵科學問題，從算法設(shè)計與理論分析兩個維度，對提升計算效率、減少算法冗余及理論支撐方面作出了重要且創(chuàng)新性的貢獻。
在因果推理中，有向無環(huán)圖（DAG）是描述變量之間因果關(guān)系的基礎(chǔ)工具。但在實際研究中，研究人員從有限觀測數(shù)據(jù)無法唯一確定變量間的因果關(guān)系結(jié)構(gòu)，只能識別出一組代表相同條件獨立關(guān)系的DAG，即馬爾可夫等價類（MEC）。MEC的規(guī)模代表了因果結(jié)構(gòu)的不確定程度，對進一步的科研實證環(huán)節(jié)至關(guān)重要。在流行病學、經(jīng)濟因果分析、醫(yī)療干預設(shè)計、政策評估以及智能系統(tǒng)自動推理等諸多領(lǐng)域中，精確量化因果結(jié)構(gòu)的不確定性，能夠助力科研人員和決策者更高效地獲取因果結(jié)構(gòu)、設(shè)計干預實驗、評估潛在風險并制定優(yōu)化策略，為決策過程提供更為精準的科學依據(jù)。
在既有的MEC規(guī)模計算研究中，已知的Clique-Picking算法，通過選取不同的團為根節(jié)點，不斷將MEC拆分為不同的子類，并遞歸計算每個子類中的DAG數(shù)量。但由于子類之間存在大量結(jié)構(gòu)上的重復與相似性，計算過程中產(chǎn)生大量冗余，嚴重影響計算效率。
圖2：傳統(tǒng)Clique-Picking算法
通過選取不同團為根，對馬爾可夫等價類分類
針對這一難題，研究團隊發(fā)現(xiàn)，不同子類在圖結(jié)構(gòu)上存在高度的相似性，特別是在圖結(jié)構(gòu)的無向部分——即連通分量集合上，結(jié)構(gòu)相似性可以被精確識別與利用。借助圖論中“團樹”（Clique tree）工具，研究團隊提出了高階圖結(jié)構(gòu)—— “超團”（Super Clique）和“超殘差”（Super Residual），以此清晰刻畫和高效處理不同MEC子類間復雜的相互關(guān)系。
在引入高階圖結(jié)構(gòu)的基礎(chǔ)之上，研究團隊提出了超團轉(zhuǎn)移（Super Cliques Transfer，SC-Trans）算法。這一創(chuàng)新算法能夠在迭代計算新子類圖結(jié)構(gòu)時，巧妙利用前序計算的“超團”和“超殘差”結(jié)構(gòu)，直接獲取重疊的結(jié)構(gòu)信息，并通過局部的轉(zhuǎn)移操作迅速補充不重疊的部分，從而極大減少冗余計算，提升計算效率。
圖3:研究團隊在團樹中構(gòu)造“超團”結(jié)構(gòu)，
并設(shè)計算法實現(xiàn)不同團樹間的結(jié)構(gòu)快速轉(zhuǎn)換
研究團隊不僅從理論上給出了SC-Trans算法的完整證明，更通過大量模擬驗證了算法的高效性，展現(xiàn)算法在實際應(yīng)用中的巨大潛力。這一研究成果為復雜因果結(jié)構(gòu)評估和貝葉斯實驗設(shè)計提供了重要的理論支撐與算法工具，進一步打通了從大數(shù)據(jù)到精準決策的關(guān)鍵通道。
