首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

华为诺亚ICLR 2020满分论文:基于强化学习的因果发现算法

2020-05-22

论文地址:https://arxiv.org/pdf/1906.04477.pdf

因果研讨作为下一个潜在的热门,现已招引了机器学习/深度学习范畴的的广泛重视,例如 Youshua Bengio 和 Fei-Fei Li 近期都有相关的作业。因果研讨中一个经典的问题是「因果发现」问题——从被迫可观测的数据中发现潜在的因果图结构。

在此论文中,华为诺亚方舟试验室因果研讨团队将强化学习运用到打分法的因果发现算法中,经过依据自留意力机制的 encoder-decoder 神经网络模型探究数据之间的联系,结合因果结构的条件,并运用战略梯度的强化学习算法对神经网络参数进行练习,终究得到因果图结构。在学术界常用的一些数据模型中,该办法在中等规划的图上的体现优于其他办法,包括传统的因果发现算法和近期的依据梯度的算法。一同该办法十分灵敏,能够和恣意的打分函数结合运用。

咱们假定以下常用的数据生成模型:给定一个有向无环图,每个节点对应一个随机变量,每个变量的观测值是图中父亲变量的函数加上一个独立的噪声,即

这儿噪声 n_i 是联合独立的。假如一切的函数都是线性的且噪声是高斯的,则上述模型为规范的线性高斯模型。当函数为线性但噪声为非高斯函数时,上述模型为线性非高斯加性模型,在必定的条件下是能够辨认出实在的 DAG。

咱们现在考虑一切的变量都是一维的实变量;给定一个适宜的打分函数则能够直接扩展到多维变量的景象。在固定的函数和噪声散布下,咱们的观测数据是依据上述模型在某个不知道的 DAG 上独立采样得到。因果发现的意图便是运用这些观测的数据来揣度实在的因果 DAG。

打分法是因果发现算法中一类常用的办法:给每个有向图打分,然后在一切的 DAG 中进行查找获得最好分数的 DAG:

尽管有许多现已深入研讨的打分函数,例如依据线性高斯模型的 BIC/MDL 和 BGe 分数,但上述问题一般是 NP-hard 的,因为 DAG 条件是一个组合问题,而且或许的 DAG 数量的跟着图节点的个数增加而超指数增加。为了处理这个问题,大多数已有办法都依赖于部分启发式算法。

例如,贪婪等价查找在增加一条边时显式查看 DAG 束缚是否满意。GES 在恰当的假定和极限数据量的状况下能够找到具大局最优值,但在有限样本的状况下无法得到确保。

最近,也有作业在线性数据模型上对上述的无环条件提出了一个等价的可微分函数,再挑选恰当的丢失函数,上述问题能够转换为关于带权值的邻接矩阵的接连优化问题。后续的作业也选用 ELBO 和 negative log-likelihood 作为丢失函数,并运用神经网络对因果联系进行建模。可是许多已有的得分函数没有显式的标明或许是十分复杂的等价丢失函数,这样和上述接连的办法结合会比较困难。

咱们提出一种依据 RL 的办法来查找 DAG,全体结构图如下所示。依据随机战略的 RL 能够在给定战略的不确定性信息的状况下主动确定要查找的方位,一同能够经过奖赏信号来及时更新。在组成数据集和实在数据集上的试验标明,依据强化学习的办法大大提高了查找才能,而且不会影响打分函数的挑选。

如上图所示,咱们选用 Transfomer 中依据自留意机制的 encoder,而 decoder 则是经过树立成对的 encoder 输出之间的联系来生成图的邻接矩阵。为了得到 0-1 的邻接矩阵,咱们将每个 decoder 的输出经过 logistic-sigmoid 函数,然后运用 Bernoulli 散布进行采样。

咱们也尝试了其他的 decoder,例如 bilinear model 以及 Transformer 中的 decoder。咱们试验发现上图中 decoder 的作用最好,或许是因为它的参数量比较少、更简单练习来找到更好的 DAG,而依据自留意力机制的 encoder 现已供给了满足的交互来探究数据之间的因果联系。

传统的 GES 会在每次增加一条边时显式的查看图是否有环,咱们运用打分函数和依据有环性质的赏罚项来规划 reward,并答应生成的图在每次迭代中改变多条边。具体的方式如下:

其间第一项是得分函数,用于衡量给定有向图和观测数据的匹配程度,其他两个正项则衡量某些「DAGness」,lambda_1 和 lamba_2 是赏罚项的权重。经过挑选恰当的赏罚权重,最大化 reward 等价于之前打分法的问题的方式。可是两个问题等价并不意味着运用 RL 来最大化 reward 就能够直接获得很好的成果:实践中,咱们发现较大的赏罚权重或许会阻碍 RL 的探究,得到的因果图的得分一般比较差,而较小的赏罚值将导致有环的图。一同,不同的打分函数或许具有十分不同的规模,而两个赏罚项的值与打分函数是没有联系的。因而,咱们将一切的打分函数调整到必定规模,并为赏罚权重规划一种在线更新战略。具体内容能够拜见论文的第 5 章。

咱们选用战略梯度和随机优化的办法来优化以下方针:

其间 A 中有向图对应的 0-1 邻接矩阵。咱们运用 Actor-Critic 来进行练习,一同还加了熵正则项来鼓舞探究。尽管战略梯度办法仅在必定条件下能确保部分收敛,可是经过赏罚项系数的规划,在咱们的试验中 RL 算法得到的图都是无环的。

因为咱们重视的是寻觅得分最好的 DAG,而不是 policy,因而咱们记录了练习进程中生成的一切的有向图,并挑选具有最佳 reward 的图作为输出成果。实践上因为有限的数据,图中会包括一些真图里面不存在的边,因而需求进一步的减枝处理。

咱们能够依据丢失函数或许打分函数,运用贪婪办法来进行减枝操作。咱们删去一个父亲变量并核算相应的成果,假如丢失函数或许打分函数作用没有变差或许是在预先设定的规模内,就承受减枝的操作并继续下去。关于线性模型,能够经过和阈值比较的办法来进行减枝。

在此作业中,咱们运用 BIC 打分函数,并假定附加性的高斯噪声。考虑两种状况:不同的噪声方差,等价于 negative log-likelihood 加上一个对边的个数的赏罚项作为打分函数;以及持平的噪声方差,将得到最小平方丢失加上边的个数的赏罚项。它们别离标明为 RL-BIC 和 RL-BIC2。

咱们的办法与传统办法以及最近依据梯度的办法在学术界常用的一些数据集进步行了比较。咱们运用三个目标评价学到的图结构:过错发现率,正确率和结构汉明间隔。SHD 是将得到的图转换为实在 DAG 的边增加,删去和回转操作的最少个数。

咱们首要考虑 12 个节点的有向图。图 2 显现了在一个线性高斯数据集上 RL-BIC2 的练习进程。咱们选用 NOTEARS 和 DAG-GNN 在相同的数据集上运用的阈值来做减枝。在这个比如中,RL-BIC2 在练习进程中生成 683,784 个不同的图,远低于 12 个节点 DAG 的总数。经过减枝的 DAG 和实在的图结构完全相同。

图 2:在线性高斯数据集上 RL-BIC2 的学习进程。

表 1 是咱们在 LiNGAM 和线性高斯数据模型的试验成果。在该试验中,RL-BIC2 在两个数据模型上康复了一切实在的因果图,而 RL-BIC 的体现稍差。尽管如此,在相同的 BIC 分数下,RL-BIC 在两个数据集上的体现均远好于 GES。

咱们考虑一种非线性的数据模型,每个因果联系函数是从高斯进程中采样的一个函数。该问题被证明是可辨认的,即能够从联合概率散布中辨认出实在的图。咱们运用和 GraN-DAG 相同的试验条件:10 个节点,40 条边的 DAG,并考虑 1000 个观测样本。

试验成果如下表 3 所示。关于咱们的办法,咱们将高斯进程回归与 RBF 核一同运用来树立因果联系模型。尽管观察到的数据是来自于高斯进程采样得到的函数,但这并不能确保具有相同核的 GPR 能够到达很好的成果。实践上,运用固定的核参数将导致严峻的过度拟合,然后导致许多过错的边,这样练习完毕最好 reward 对应的有向图一般不是 DAG。为此咱们将数据归一化处理,并运用 median heuristics 来挑选核参数。咱们两种办法的体现都不错,其间 RL-BIC 的成果优于其他一切办法。

咱们最终考虑 Sachs 数据集,经过蛋白质和磷脂的表达程度来发现蛋白质信号网络。咱们将带有 RBF 内核的 GPR 运用于因果联系建模,对数据做归一化并运用依据 median heuristics 的核参数。咱们运用和 CAM 及 Gran-DAG 中相同的减枝办法。试验成果见下表。与其他办法比较,RL-BIC 和 RL-BIC2 均获得了不错的成果。

咱们运用强化学习来查找具有最佳分数的 DAG,其间 actor 是依据自留意力机制的 encoder-decoder 模型,而 reward 结合了预先给定的得分函数和两个赏罚项来得到无环图。在组成和实在数据集上,该办法均获得了很好的成果。在论文里,咱们还展现了该办法在 30 节点的图上的作用,可是处理大规划的图依然具有挑战性。尽管如此,许多实践的运用的变量数都相对较少。此外,有或许将大的因果发现问题分解为较小的问题别离处理,依据先验常识或依据束缚的办法也能够用来削减查找空间。

当时的作业有几个未来改善的方向。在现在的完成中,打分函数的核算比练习神经网络会花费更多的时刻,一个更有功率的打分函数将会大大提高现在算法的体现。其他 RL 算法也能够用来加快练习,例如 A3C。此外,咱们观察到试验中运用的总迭代次数一般超过了需求的次数,咱们也会研讨怎么进行 early stopping。

热门文章

随机推荐

推荐文章