基于线性非高斯无环模型的鲁棒因果发现算法

2022-12-24郝志峰蔡瑞初

计算机仿真 2022年11期

曾艳，郝志峰，2，蔡瑞初，谢峰

(1.广东工业大学计算机学院，广东广州 510006；2.佛山科学技术学院数学与大数据学院，广东佛山 528000；3.北京大学数学科学学院，北京 100080)

1 引言

探索数据背后的因果机制已经成为当前的热点问题，同时也是计算机仿真的重要研究内容，被广泛应用于机器学习等领域中[1]-[4]。传统的因果发现算法大致分为两类：基于约束的算法，如PC[5]和基于评分的算法，如GES[6]。虽然上述方法[5]，[6]已经被用于许多重要领域，但是其不能够找到一个完整的有向无环图(Directed Acyclic Graph，DAG)。Shimizu等人[7]，[8]提出的线性非高斯无环模型(Linear Non-Gaussian Acyclic Model，LiNGAM)很好地解决了上述问题，该模型能够唯一地识别出完整的DAG并成为最重要的因果模型之一。现有估计LiNGAM的算法包括了基于独立成分分析的ICA-LiNGAM[7]、基于独立性分析的DirectLiNGAM[9]算法以及Pairwise-LiNGAM算法[10]、GPL算法[11]等。最近Xie等人[12]利用信息熵提出了ETPIA算法。

然而，上述因果发现方法[7]-[12]由于搜索方式不恰当存在算法性能下降的问题。也即是说，它们采取全局的搜索方式，从整个变量集合出发，在整个变量集合中逐层地选择外生变量(请见定义1)，确定因果次序，进而获得整个因果网络。而且，在逐层选择外生变量的过程中，这些方法均需要将每一个变量与其余所有变量成对地进行对比。因此，当数据的维度增高时，对比的变量个数将增大，累积误差也会相应增加，使得在逐层选择外生变量的步骤上易出错。同理，当样本量不足时，额外的估计误差也会引入。错误地选择外生变量会产生级联效应，使得整个网络的估计误差会随着层数的增大而变得越来越大，导致算法性能大幅度降低。

因此，本文基于LiNGAM，提出了一种鲁棒的因果发现算法。不同于上述方法[7]-[12]，文中的算法采用d分离准则确定因果网络骨架，根据网络骨架提供的相邻节点信息(请见定义2)，采取局部搜索的方式依次寻找外生变量。算法的主要特点主要体现在搜索空间的减少，即，当数据的变量个数增加时，算法在选择外生变量时的搜索空间不是集中在整个变量集合，而是在每个节点的相邻节点集合，因此减小了搜索空间，从而使得算法能在数据的维度增大或样本量不足时展示较好的鲁棒性。此外，本文提供了算法的理论证明。且不同于以往方法的理论[9]-[12]，证明了在引入相邻节点的信息后外生变量的最强独立性以及算法的一致性。同时，该有效性也通过仿真得到验证。

2 线性非高斯无环模型

线性非高斯无环模型(Linear Non-Gaussian Acyclic Model， LiNGAM)是因果关系发现中的重要模型[]，其基本形式为

(1)

其中i={1，…，n}，xi表示观测变量；bij表示有向无环图DAG中变量xj到xi的连接强度；ei表示噪声变量，服从非零方差的非高斯分布，且彼此间独立；K(i)表示变量xi的因果次序。

LiNGAM需满足以下三个基本假设：1)数据产生过程满足式(1)，即线性假设；2)因果充分性假设，即不存在隐藏变量；3)噪声变量ei服从非零方差的非高斯分布。

将(1)式写成矩阵的形式如下：

X=BX+e

(2)

其中X=[x1，…，xn]T，e=[e1，…，en]T，连接矩阵B存储了变量xi与变量xj之间的连接强度bij。值得注意的是，由于DAG的性质，连接矩阵可以通过对应的行列变换，转换成一个严格的下三角矩阵[7](严格的下三角矩阵指的是一个对角线上的元素均为0的下三角矩阵)。

本文的目标是如何有效地估计LiNGAM模型。即在已知观察数据X的情况下，求解因果次序K和连接矩阵B，进而得到完整的因果网络结构。

3 S2-LiNGAM因果发现算法

3.1 基本定义

在阐述本算法的基本思想与理论分析之前，为了便于描述，首先给出外生变量、相邻节点和d分离准则的基本定义。

定义1[9](外生变量)：外生变量是指在因果关系网络中只起解释作用的变量，即在因果模型内部没有直接的原因节点。

外生变量有时也叫外生变量。由定义1可知，在具体的因果关系网络图中，外生变量只指向其它节点，而不存在其它节点指向外生变量。

定义2[5](相邻节点)：在因果关系网络中，如果节点xi与节点xj由一条有向边直接相连，则称节点xi是节点xj的相邻节点，或节点xj是节点xi的相邻节点。

由定义2可知，相邻节点包括了一个节点所有子节点与父节点。

定义3[5](d分离准则)：在因果关系网络中，一条路径p被节点集Zd分离当且仅当

(a)p包含一条链i→m→j或者碰撞点i→m←j使得m∈Z，或者

(b)p包含碰撞点i→m←j使得m∉Z并且不存在节点m的后代节点属于Z。

换句话说，节点集Zd分离X和Y当且仅当Z阻隔了从X到Y的所有路径。由定义3可知，d分离准则能被用于发现因果网络骨架，从而获得每个节点的相邻节点信息。

3.2 算法的理论分析

在这一小节中，将给出外生变量的判定定理(请见定理2)，再给出算法的一致性证明(请见定理3)，保证算法的有效性。在描述定理2和3前，先提供定理1，D-S定理，因为它会被用在后续的定理证明中。

定理1[9](D-S定理)：定义两个随机变量x1和x2是由独立的随机变量εi，i=1，2，…，q线性组合而成，即

(3)

那么，如果x1和x2统计独立，则对于αiβi≠0，所有的εi是高斯分布。换句话说，定理1说明如果存在服从非高斯分布的εi满足αiβi≠0，那么x1和x2统计依赖。

(4)

证明：从1)充分性与2)必要性证明。

xj=ej

xi=bijej+ei

其中，每一个节点xk都(包括xi)可以表示为噪音变量e的线性组合(噪音变量不包括ej)

(5)

(6)

定理1描述了给定相邻节点信息下的外生变量性质，它帮助本文对因果网络结构中的外生变量进行判定，同时它为本文逐层选择外生变量的正确性提供了初步的理论基础。此外，在选择第一个外生变量后，本文需要更新原始观察数据，再继续选择下一个外生变量，进而最终确定因果次序。定理3为下一个外生变量的正确识别，即因果次序的正确识别，提供了完整的理论支撑。

3.3 算法流程

基于上述的理论分析，本文提出了基于LiNGAM的鲁棒因果关系发现算法(A RobuSt CauSal Discovery Algorithm Based on LiNGAM)简称为：S2-LiNGAM。算法的基本步骤如下：

输入：观察数据X={x1，x2，…，xn}。

输出：因果次序K和因果网络B。

1) 初始化因果次序集合K=∅与集合U={1，…，n}；

2) 利用d分离准则，寻找每个节点的相邻节点，并存储在相邻矩阵D={d1，…，dn}中；

3) Repeat

6) 根据式(4)，更新数据X，为每个节点除去外生变量对其产生的影响，同时，U=U/{j}；

7) Until U的节点个数为1；

8) 将最后一个节点的下标加入至K中；

9) 根据得到的因果次序K和相邻矩阵D，使用剪枝算法估计连接矩阵B。为了更清晰地说明流程，提供例子如下。

图1 一个简单LiNGAM模型的因果网络图

x3⊥r(3)1,x3⊥r(3)4,x2⊥r(2)1,x2⊥

r(2)4,x1⊥

r(1)2,x1⊥

4 仿真研究

为了说明算法的有效性，本文从贝叶斯网络存储库中选择了6种不同领域下的真实网络结构来进行仿真，如表1所示(1)真实网络的详细信息请见：http：∥www.cs.huji.ac.il/～galel/Repository/。首先，本文根据真实网络结构产生服从LiNGAM的数据，其中噪声变量服从非高斯的拉普拉斯分布，连接矩阵B从[-1，-0.5]∪[0.5，1]的均匀分布随机产生。选取常用的ICA-LiNGAM算法[7]， Pairwise-LiNGAM算法[10]以及ETPIA算法[12]作为本实验的对比方法。此外，针对衡量标准，本文选择了贝叶斯因果网络的常用指标召回率(Recall)、准确率(Precision)和F1得分(F1 score)。F1得分反映了因果网络结构的总体估计优劣，具体为

Recall=TP/(TP+FN)，

Precision=TP/(TP+FP)，

其中，TP表示正确估计的边的个数；FP表示未估计到的边的个数；FN表示错误估计的边的个数。结果取20次的平均值。

表1 真实网络的介绍

本文分别为6种不同大小的真实网络设计了样本量在50、100、200、500下的对比实验，结果如图2至图7所示。从总体来看，随着样本量的逐渐增加，本算法S2-LiNGAM在不同网络下的召回率、准确率与F1得分都逐渐上升，说明了算法理论的正确性。特别地，当样本量小(=50)或者节点数量高(WIN95PTS的维度为76)时，算法的F1得分都明显优于其余三个算法，验证了算法良好的鲁棒性，同时也说明了本文采取的局部搜索选择外生变量的方式的有效性。虽然S2-LiNGAM的召回率在Barley等部分网络结构上不及对比的算法，但其准确率和F1得分都大大地超过于对比算法，这说明了算法的剪枝操作学习到的边尽管少，但大多数是准确的。因此，在现实应用中，可以根据实际情况选择合适的剪枝操作，从而得到更有效的因果网络结构。Pairwise-LiNGAM和ETPIA算法是基于Direct-LiNGAM框架的，它们采取全局搜索的方式选择外生变量和学习因果网络结构，因此在样本量不足或维度增高时算法性能降低，F1得分较低。

综上分析，相较于其余三个算法，本方法都能够取得较好的效果，验证了S2-LiNGAM在因果关系发现中具有良好的鲁棒性。