華為諾亞ICLR 2020滿分論文：基于強(qiáng)化學(xué)習(xí)的因果發(fā)現(xiàn)算法

taotao_2016 2019-12-30

展開全文

機(jī)器之心發(fā)布

機(jī)器之心編輯部

人工智能頂會(huì) ICLR 2020 將于明年 4 月 26 日于埃塞俄比亞首都亞的斯亞貝巴舉行，不久之前，大會(huì)官方公布論文接收結(jié)果：在最終提交的 2594 篇論文中，有 687 篇被接收，接收率為 26.5%。本文介紹了華為諾亞方舟實(shí)驗(yàn)室被 ICLR 2020 接收的一篇滿分論文。

論文地址：https:///pdf/1906.04477.pdf

因果研究作為下一個(gè)潛在的熱點(diǎn)，已經(jīng)吸引了機(jī)器學(xué)習(xí)/深度學(xué)習(xí)領(lǐng)域的的廣泛關(guān)注，例如 Youshua Bengio 和 Fei-Fei Li 近期都有相關(guān)的工作。因果研究中一個(gè)經(jīng)典的問(wèn)題是「因果發(fā)現(xiàn)」問(wèn)題——從被動(dòng)可觀測(cè)的數(shù)據(jù)中發(fā)現(xiàn)潛在的因果圖結(jié)構(gòu)。

在此論文中，華為諾亞方舟實(shí)驗(yàn)室因果研究團(tuán)隊(duì)將強(qiáng)化學(xué)習(xí)應(yīng)用到打分法的因果發(fā)現(xiàn)算法中，通過(guò)基于自注意力機(jī)制的 encoder-decoder 神經(jīng)網(wǎng)絡(luò)模型探索數(shù)據(jù)之間的關(guān)系，結(jié)合因果結(jié)構(gòu)的條件，并使用策略梯度的強(qiáng)化學(xué)習(xí)算法對(duì)神經(jīng)網(wǎng)絡(luò)參數(shù)進(jìn)行訓(xùn)練，最終得到因果圖結(jié)構(gòu)。在學(xué)術(shù)界常用的一些數(shù)據(jù)模型中，該方法在中等規(guī)模的圖上的表現(xiàn)優(yōu)于其他方法，包括傳統(tǒng)的因果發(fā)現(xiàn)算法和近期的基于梯度的算法。同時(shí)該方法非常靈活，可以和任意的打分函數(shù)結(jié)合使用。

模型定義和問(wèn)題

我們假設(shè)以下常用的數(shù)據(jù)生成模型：給定一個(gè)有向無(wú)環(huán)圖（DAG），每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)隨機(jī)變量，每個(gè)變量的觀測(cè)值是圖中父親變量的函數(shù)加上一個(gè)獨(dú)立的噪聲，即

這里噪聲 n_i 是聯(lián)合獨(dú)立的。如果所有的函數(shù)都是線性的且噪聲是高斯的，則上述模型為標(biāo)準(zhǔn)的線性高斯模型。當(dāng)函數(shù)為線性但噪聲為非高斯函數(shù)時(shí)，上述模型為線性非高斯加性模型（LiNGAM），在一定的條件下是可以識(shí)別出真實(shí)的 DAG。

我們目前考慮所有的變量都是一維的實(shí)變量；給定一個(gè)合適的打分函數(shù)則可以直接擴(kuò)展到多維變量的情形。在固定的函數(shù)和噪聲分布下，我們的觀測(cè)數(shù)據(jù)是根據(jù)上述模型在某個(gè)未知的 DAG 上獨(dú)立采樣得到。因果發(fā)現(xiàn)的目的就是使用這些觀測(cè)的數(shù)據(jù)來(lái)推斷真實(shí)的因果 DAG。

背景介紹

打分法是因果發(fā)現(xiàn)算法中一類常用的方法：給每個(gè)有向圖打分（通常基于觀測(cè)數(shù)據(jù)計(jì)算得到），然后在所有的 DAG 中進(jìn)行搜索取得最好分?jǐn)?shù)的 DAG：

盡管有很多已經(jīng)深入研究的打分函數(shù)，例如基于線性高斯模型的 BIC/MDL 和 BGe 分?jǐn)?shù)，但上述問(wèn)題通常是 NP-hard 的，因?yàn)?DAG 條件是一個(gè)組合問(wèn)題，并且可能的 DAG 數(shù)量的隨著圖節(jié)點(diǎn)的個(gè)數(shù)增加而超指數(shù)增加。為了解決這個(gè)問(wèn)題，大多數(shù)已有方法都依賴于局部啟發(fā)式算法。

例如，貪婪等價(jià)搜索（GES）在添加一條邊時(shí)顯式檢查 DAG 約束是否滿足。GES 在適當(dāng)?shù)募僭O(shè)和極限數(shù)據(jù)量的情況下可以找到具全局最優(yōu)值，但在有限樣本的情況下無(wú)法得到保證。

最近，也有工作在線性數(shù)據(jù)模型上對(duì)上述的無(wú)環(huán)條件提出了一個(gè)等價(jià)的可微分函數(shù)，再選擇適當(dāng)?shù)膿p失函數(shù)（例如最小二乘損失），上述問(wèn)題可以轉(zhuǎn)換為關(guān)于帶權(quán)值的鄰接矩陣的連續(xù)優(yōu)化問(wèn)題。后續(xù)的工作也采用 ELBO 和 negative log-likelihood 作為損失函數(shù)，并使用神經(jīng)網(wǎng)絡(luò)對(duì)因果關(guān)系進(jìn)行建模。但是很多已有的得分函數(shù)沒(méi)有顯式的表示或者是非常復(fù)雜的等價(jià)損失函數(shù)，這樣和上述連續(xù)的方法結(jié)合會(huì)比較困難。

基于強(qiáng)化學(xué)習(xí)的因果發(fā)現(xiàn)算法

我們提出一種基于 RL 的方法來(lái)搜索 DAG，整體框架圖如下所示。基于隨機(jī)策略的 RL 可以在給定策略的不確定性信息的情況下自動(dòng)確定要搜索的位置，同時(shí)可以通過(guò)獎(jiǎng)勵(lì)信號(hào)來(lái)及時(shí)更新。在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，基于強(qiáng)化學(xué)習(xí)的方法大大提高了搜索能力，并且不會(huì)影響打分函數(shù)的選擇。

基于自注意力機(jī)制的 Encoder-Decoder 模型

如上圖所示，我們采用 Transfomer 中基于自注意機(jī)制的 encoder，而 decoder 則是通過(guò)建立成對(duì)的 encoder 輸出之間的關(guān)系來(lái)生成圖的鄰接矩陣。為了得到 0-1 的鄰接矩陣，我們將每個(gè) decoder 的輸出通過(guò) logistic-sigmoid 函數(shù)，然后使用 Bernoulli 分布進(jìn)行采樣。

我們也嘗試了其他的 decoder，例如 bilinear model 以及 Transformer 中的 decoder。我們實(shí)驗(yàn)發(fā)現(xiàn)上圖中 decoder 的效果最好，可能是因?yàn)樗膮?shù)量比較少、更容易訓(xùn)練來(lái)找到更好的 DAG，而基于自注意力機(jī)制的 encoder 已經(jīng)提供了足夠的交互來(lái)探索數(shù)據(jù)之間的因果關(guān)系。

Reward

傳統(tǒng)的 GES 會(huì)在每次添加一條邊時(shí)顯式的檢查圖是否有環(huán)，我們使用打分函數(shù)和基于有環(huán)性質(zhì)的懲罰項(xiàng)來(lái)設(shè)計(jì) reward，并允許生成的圖在每次迭代中變化多條邊。具體的形式如下：

其中第一項(xiàng)是得分函數(shù)，用于衡量給定有向圖和觀測(cè)數(shù)據(jù)的匹配程度，其他兩個(gè)正項(xiàng)則衡量某些「DAGness」（給定的有向圖距無(wú)環(huán)的某種度量，例如所有環(huán)上的長(zhǎng)度之和），lambda_1 和 lamba_2 是懲罰項(xiàng)的權(quán)重。通過(guò)選擇適當(dāng)?shù)膽土P權(quán)重，最大化 reward 等價(jià)于之前打分法的問(wèn)題的形式。但是兩個(gè)問(wèn)題等價(jià)并不意味著使用 RL 來(lái)最大化 reward 就可以直接取得很好的結(jié)果：實(shí)際中，我們發(fā)現(xiàn)較大的懲罰權(quán)重可能會(huì)妨礙 RL 的探索，得到的因果圖的得分通常比較差，而較小的懲罰值將導(dǎo)致有環(huán)的圖。同時(shí)，不同的打分函數(shù)可能具有非常不同的范圍，而兩個(gè)懲罰項(xiàng)的值與打分函數(shù)是沒(méi)有關(guān)系的。因此，我們將所有的打分函數(shù)調(diào)整到一定范圍，并為懲罰權(quán)重設(shè)計(jì)一種在線更新策略。詳細(xì)內(nèi)容可以參見論文的第 5 章。

Actor-Critic 優(yōu)化參數(shù)

我們采用策略梯度和隨機(jī)優(yōu)化的方法來(lái)優(yōu)化以下目標(biāo)：

其中 A 中有向圖對(duì)應(yīng)的 0-1 鄰接矩陣。我們使用 Actor-Critic 來(lái)進(jìn)行訓(xùn)練，同時(shí)還加了熵正則項(xiàng)來(lái)鼓勵(lì)探索。盡管策略梯度方法僅在一定條件下能保證局部收斂，但是通過(guò)懲罰項(xiàng)系數(shù)的設(shè)計(jì)，在我們的實(shí)驗(yàn)中 RL 算法得到的圖都是無(wú)環(huán)的。

最終輸出

由于我們關(guān)注的是尋找得分最好的 DAG，而不是 policy，因此我們記錄了訓(xùn)練過(guò)程中生成的所有的有向圖，并選擇具有最佳 reward 的圖作為輸出結(jié)果。實(shí)際上由于有限的數(shù)據(jù)，圖中會(huì)包含一些真圖里邊不存在的邊，因此需要進(jìn)一步的減枝處理。

我們可以根據(jù)損失函數(shù)或者打分函數(shù)，使用貪婪方法來(lái)進(jìn)行減枝操作。我們刪除一個(gè)父親變量并計(jì)算相應(yīng)的結(jié)果，如果損失函數(shù)或者打分函數(shù)效果沒(méi)有變差或者是在預(yù)先設(shè)定的范圍內(nèi)，就接受減枝的操作并繼續(xù)下去。對(duì)于線性模型，可以通過(guò)和閾值比較的方法來(lái)進(jìn)行減枝。

實(shí)驗(yàn)結(jié)果

在此工作中，我們使用 BIC 打分函數(shù)，并假設(shè)附加性的高斯噪聲（實(shí)際中噪聲可能是非高斯的）?？紤]兩種情況：不同的噪聲方差，等價(jià)于 negative log-likelihood 加上一個(gè)對(duì)邊的個(gè)數(shù)的懲罰項(xiàng)作為打分函數(shù)；以及相等的噪聲方差，將得到最小平方損失加上邊的個(gè)數(shù)的懲罰項(xiàng)。它們分別表示為 RL-BIC 和 RL-BIC2。

我們的方法與傳統(tǒng)方法（PC，GES，ICA-LiNGAM 和 CAM）以及最近基于梯度的方法（NOTEARS，DAG-GNN 和 GraN-DAG）在學(xué)術(shù)界常用的一些數(shù)據(jù)集上進(jìn)行了比較。我們使用三個(gè)指標(biāo)評(píng)估學(xué)到的圖結(jié)構(gòu)：錯(cuò)誤發(fā)現(xiàn)率（FDR），正確率（TPR）和結(jié)構(gòu)漢明距離（SHD）。SHD 是將得到的圖轉(zhuǎn)換為真實(shí) DAG 的邊添加，刪除和反轉(zhuǎn)操作的最少個(gè)數(shù)。

高斯和非高斯噪聲的線性數(shù)據(jù)模型

我們首先考慮 12 個(gè)節(jié)點(diǎn)的有向圖。圖 2 顯示了在一個(gè)線性高斯數(shù)據(jù)集上 RL-BIC2 的訓(xùn)練過(guò)程。我們采用 NOTEARS 和 DAG-GNN 在同樣的數(shù)據(jù)集上使用的閾值來(lái)做減枝。在這個(gè)例子中，RL-BIC2 在訓(xùn)練過(guò)程中生成 683,784 個(gè)不同的圖，遠(yuǎn)低于 12 個(gè)節(jié)點(diǎn) DAG 的總數(shù)（約 5.22 * 10^26）。經(jīng)過(guò)減枝的 DAG 和真實(shí)的圖結(jié)構(gòu)完全相同。

圖 2：在線性高斯數(shù)據(jù)集上 RL-BIC2 的學(xué)習(xí)過(guò)程。

表 1 是我們?cè)?LiNGAM 和線性高斯數(shù)據(jù)模型的實(shí)驗(yàn)結(jié)果。在該實(shí)驗(yàn)中，RL-BIC2 在兩個(gè)數(shù)據(jù)模型上恢復(fù)了所有真實(shí)的因果圖，而 RL-BIC 的表現(xiàn)稍差。盡管如此，在相同的 BIC 分?jǐn)?shù)下，RL-BIC 在兩個(gè)數(shù)據(jù)集上的表現(xiàn)均遠(yuǎn)好于 GES。

具有高斯過(guò)程的非線性模型

我們考慮一種非線性的數(shù)據(jù)模型，每個(gè)因果關(guān)系函數(shù)是從高斯過(guò)程中采樣的一個(gè)函數(shù)。該問(wèn)題被證明是可識(shí)別的，即可以從聯(lián)合概率分布中識(shí)別出真實(shí)的圖。我們使用和 GraN-DAG 一樣的實(shí)驗(yàn)條件：10 個(gè)節(jié)點(diǎn)，40 條邊的 DAG，并考慮 1000 個(gè)觀測(cè)樣本。

實(shí)驗(yàn)結(jié)果如下表 3 所示。對(duì)于我們的方法，我們將高斯過(guò)程回歸（GPR）與 RBF 核一起使用來(lái)建立因果關(guān)系模型。雖然觀察到的數(shù)據(jù)是來(lái)自于高斯過(guò)程采樣得到的函數(shù)，但這并不能保證具有相同核的 GPR 可以達(dá)到很好的結(jié)果。實(shí)際上，使用固定的核參數(shù)將導(dǎo)致嚴(yán)重的過(guò)度擬合，從而導(dǎo)致許多錯(cuò)誤的邊，這樣訓(xùn)練結(jié)束最好 reward 對(duì)應(yīng)的有向圖通常不是 DAG。為此我們將數(shù)據(jù)歸一化處理，并使用 median heuristics 來(lái)選擇核參數(shù)。我們兩種方法的表現(xiàn)都不錯(cuò)，其中 RL-BIC 的結(jié)果優(yōu)于其他所有方法。

真實(shí)數(shù)據(jù)集

我們最后考慮 Sachs 數(shù)據(jù)集，通過(guò)蛋白質(zhì)和磷脂的表達(dá)程度來(lái)發(fā)現(xiàn)蛋白質(zhì)信號(hào)網(wǎng)絡(luò)。我們將帶有 RBF 內(nèi)核的 GPR 應(yīng)用于因果關(guān)系建模，對(duì)數(shù)據(jù)做歸一化并使用基于 median heuristics 的核參數(shù)。我們使用和 CAM 及 Gran-DAG 中同樣的減枝方法。實(shí)驗(yàn)結(jié)果見下表。與其他方法相比，RL-BIC 和 RL-BIC2 均取得了不錯(cuò)的結(jié)果。

結(jié)語(yǔ)

我們使用強(qiáng)化學(xué)習(xí)來(lái)搜索具有最佳分?jǐn)?shù)的 DAG，其中 actor 是基于自注意力機(jī)制的 encoder-decoder 模型，而 reward 結(jié)合了預(yù)先給定的得分函數(shù)和兩個(gè)懲罰項(xiàng)來(lái)得到無(wú)環(huán)圖。在合成和真實(shí)數(shù)據(jù)集上，該方法均取得了很好的結(jié)果。在論文里，我們還展示了該方法在 30 節(jié)點(diǎn)的圖上的效果，但是處理大規(guī)模的圖（超過(guò) 50 個(gè)節(jié)點(diǎn)）仍然具有挑戰(zhàn)性。盡管如此，許多實(shí)際的應(yīng)用（例如 Sachs 數(shù)據(jù)集）的變量數(shù)都相對(duì)較少。此外，有可能將大的因果發(fā)現(xiàn)問(wèn)題分解為較小的問(wèn)題分別處理，基于先驗(yàn)知識(shí)或基于約束的方法也可以用來(lái)減少搜索空間。

當(dāng)前的工作有幾個(gè)未來(lái)改進(jìn)的方向。在目前的實(shí)現(xiàn)中，打分函數(shù)的計(jì)算比訓(xùn)練神經(jīng)網(wǎng)絡(luò)會(huì)花費(fèi)更多的時(shí)間，一個(gè)更有效率的打分函數(shù)將會(huì)大大提升目前算法的表現(xiàn)。其他 RL 算法也可以用來(lái)加速訓(xùn)練，例如 A3C。此外，我們觀察到實(shí)驗(yàn)中使用的總迭代次數(shù)通常超過(guò)了需要的次數(shù)，我們也會(huì)研究如何進(jìn)行 early stopping。

本文為機(jī)器之心發(fā)布，轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)。

?------------------------------------------------

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： taotao_2016 > 《AI》

舉報(bào)/認(rèn)領(lǐng)