近日，我校郭建華教授團(tuán)隊(duì)在因果推斷算法研究上取得重要突破。郭建華教授團(tuán)隊(duì)在國(guó)際機(jī)器學(xué)習(xí)與人工智能頂級(jí)會(huì)議——第四十二屆國(guó)際機(jī)器學(xué)習(xí)會(huì)議（International Conference on Machine Learning, ICML）上提交的論文“An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer”（基于超團(tuán)轉(zhuǎn)移的團(tuán)選取算法快速計(jì)算馬爾可夫等價(jià)類規(guī)模），入選全部投稿論文前1%，被評(píng)選為口頭報(bào)告論文。

該會(huì)議共收到專家學(xué)者投稿論文共計(jì)12107篇，其中僅有120篇被評(píng)選為口頭報(bào)告。會(huì)議審稿人對(duì)郭建華教授團(tuán)隊(duì)提交的論文給予高度認(rèn)可，一致認(rèn)為：“這篇論文解決了高效計(jì)算馬爾可夫等價(jià)類規(guī)模這一重要的算法問(wèn)題，極大提升了現(xiàn)有方法的效率。這種計(jì)算能力對(duì)貝葉斯實(shí)驗(yàn)設(shè)計(jì)方法尤其重要。論文在算法方面作出了重要的貢獻(xiàn)，并提供了扎實(shí)的理論支撐”。

圖1:會(huì)議論文截圖

本項(xiàng)論文成果由郭建華教授（通訊作者）帶領(lǐng)研究，東北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院博士研究生劉力夫、北京工商大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院副教授賀詩(shī)源為共同第一作者。該研究聚焦因果推理領(lǐng)域，具體針對(duì)高效計(jì)算有向無(wú)環(huán)圖（Directed Acyclic Graph, DAG）的馬爾可夫等價(jià)類（Markov Equivalence Class, MEC）規(guī)模這一關(guān)鍵科學(xué)問(wèn)題，從算法設(shè)計(jì)與理論分析兩個(gè)維度，對(duì)提升計(jì)算效率、減少算法冗余及理論支撐方面作出了重要且創(chuàng)新性的貢獻(xiàn)。

在因果推理中，有向無(wú)環(huán)圖（DAG）是描述變量之間因果關(guān)系的基礎(chǔ)工具。但在實(shí)際研究中，研究人員從有限觀測(cè)數(shù)據(jù)無(wú)法唯一確定變量間的因果關(guān)系結(jié)構(gòu)，只能識(shí)別出一組代表相同條件獨(dú)立關(guān)系的DAG，即馬爾可夫等價(jià)類（MEC）。MEC的規(guī)模代表了因果結(jié)構(gòu)的不確定程度，對(duì)進(jìn)一步的科研實(shí)證環(huán)節(jié)至關(guān)重要。在流行病學(xué)、經(jīng)濟(jì)因果分析、醫(yī)療干預(yù)設(shè)計(jì)、政策評(píng)估以及智能系統(tǒng)自動(dòng)推理等諸多領(lǐng)域中，精確量化因果結(jié)構(gòu)的不確定性，能夠助力科研人員和決策者更高效地獲取因果結(jié)構(gòu)、設(shè)計(jì)干預(yù)實(shí)驗(yàn)、評(píng)估潛在風(fēng)險(xiǎn)并制定優(yōu)化策略，為決策過(guò)程提供更為精準(zhǔn)的科學(xué)依據(jù)。

在既有的MEC規(guī)模計(jì)算研究中，已知的Clique-Picking算法，通過(guò)選取不同的團(tuán)為根節(jié)點(diǎn)，不斷將MEC拆分為不同的子類，并遞歸計(jì)算每個(gè)子類中的DAG數(shù)量。但由于子類之間存在大量結(jié)構(gòu)上的重復(fù)與相似性，計(jì)算過(guò)程中產(chǎn)生大量冗余，嚴(yán)重影響計(jì)算效率。

圖2：傳統(tǒng)Clique-Picking算法

通過(guò)選取不同團(tuán)為根，對(duì)馬爾可夫等價(jià)類分類

針對(duì)這一難題，研究團(tuán)隊(duì)發(fā)現(xiàn)，不同子類在圖結(jié)構(gòu)上存在高度的相似性，特別是在圖結(jié)構(gòu)的無(wú)向部分——即連通分量集合上，結(jié)構(gòu)相似性可以被精確識(shí)別與利用。借助圖論中“團(tuán)樹”（Clique tree）工具，研究團(tuán)隊(duì)提出了高階圖結(jié)構(gòu)—— “超團(tuán)”（Super Clique）和“超殘差”（Super Residual），以此清晰刻畫和高效處理不同MEC子類間復(fù)雜的相互關(guān)系。

在引入高階圖結(jié)構(gòu)的基礎(chǔ)之上，研究團(tuán)隊(duì)提出了超團(tuán)轉(zhuǎn)移（Super Cliques Transfer，SC-Trans）算法。這一創(chuàng)新算法能夠在迭代計(jì)算新子類圖結(jié)構(gòu)時(shí)，巧妙利用前序計(jì)算的“超團(tuán)”和“超殘差”結(jié)構(gòu)，直接獲取重疊的結(jié)構(gòu)信息，并通過(guò)局部的轉(zhuǎn)移操作迅速補(bǔ)充不重疊的部分，從而極大減少冗余計(jì)算，提升計(jì)算效率。

圖3:研究團(tuán)隊(duì)在團(tuán)樹中構(gòu)造“超團(tuán)”結(jié)構(gòu)，

并設(shè)計(jì)算法實(shí)現(xiàn)不同團(tuán)樹間的結(jié)構(gòu)快速轉(zhuǎn)換

研究團(tuán)隊(duì)不僅從理論上給出了SC-Trans算法的完整證明，更通過(guò)大量模擬驗(yàn)證了算法的高效性，展現(xiàn)算法在實(shí)際應(yīng)用中的巨大潛力。這一研究成果為復(fù)雜因果結(jié)構(gòu)評(píng)估和貝葉斯實(shí)驗(yàn)設(shè)計(jì)提供了重要的理論支撐與算法工具，進(jìn)一步打通了從大數(shù)據(jù)到精準(zhǔn)決策的關(guān)鍵通道。

作者：吳慧中
編輯：曹薇
審核：王遠(yuǎn)芳
審定：倪國(guó)華