基于结构方程似然框架的缺失值因果学习算法

郝志峰，喻建华，乔 杰，蔡瑞初

（1.广东工业大学 计算机学院，广州 510006；2.汕头大学 理学院，广东 汕头 515063）

0 概述

因果发现被认为是数据分析中的强大工具［1-3］。在实际场景中，数据缺失问题对因果发现算法的实际应用带来了巨大挑战［4］，因为现有的因果发现算法大多数是为完整的数据集而设计的［5-7］。如果直接［7］在缺失数据上进行因果结构网络学习，可能会存在冗余骨架［8］和错误因果方向问题。

为解决在非随机缺失数据上学习因果结构网络问题，现有缺失值因果结构学习算法分为基于约束的方法［1］和基于结构方程模型的方法［9］。基于约束的方法包括基于独立性的方法和基于评分的方法［10］2 类，基于独立性的方法分析不同缺失机制对条件独立性（Conditional Independence，CI）测试［11］结果的影响，从而通过校正条件独立性测试结果来实现因果结构学习，如MVPC 算法［8］。基于评分的方法将目标评分函数与逆概率加权［12］（Inverse Probability Weight，IPW）相结合，从而解决在非随机缺失数据上因果结构校正问题，如HC-IPW 算法［13］。然而，这2 类方法都无法识别因果结构网络中的因果对［14］以及马尔可夫等价类结构［15］，因此无法校正在这些结构中出现的错误因果方向。基于结构方程模型的方法，如MissDAG 算法［16］，通过假设缺失数据类型为随机缺失，并结合非线性加性噪声模型［14］（Additive Noise Model，ANM）的可识别性假设来最大化插入值的目标似然，而这种假设缺失数据类型是随机缺失方法，并不符合实际场景要求。

因此，对于在非随机缺失数据上，如何识别因果结构网络中的因果对以及马尔可夫等价类结构并校正因缺失导致的错误因果方向，仍是1 个具有重要意义和挑战性的问题。本文提出一种基于结构方程似然框架［17］的缺失值因果学习算法MV-SELF。该算法结合结构方程模型可识别马尔可夫等价类结构、逆概率加权可恢复非随机缺失数据的联合分布和基于评分的方法可搜索高维因果结构网络的优点，使得在非随机缺失数据上，因果结构网络学习和校正成为可能。

1 相关工作

近年来，得益于描述缺失过程的缺失图［18］以及可恢复性［19］概念确立，缺失值因果学习研究得到较快发展。在缺失值因果学习研究中，缺失图也被称为因果图，给定1 个缺失图，如果1 个查询（如条件或联合分布和因果效应）可以得到一致估计，则被认为是可恢复的。

在非随机缺失设定中，STROBL 等［20］将缺失机制视为一种特殊类型的选择偏差，以处理非随机缺失因果结构网络学习问题，并提出基于测试删除（Test-wise Deletion，TD）的FCI 算法［1］。然而，缺失机制一般比选择偏差提供了更多的缺失状态信息，而选择偏差仅提供选择后的样本分布，因此，选择后的样本分布是有偏的。为了对非随机缺失数据的联合分布进行校正，文献［21］使用逆概率加权对条件独立性测试结果进行纠正，但假设缺失因果模型是已知的，这并不适用于实际应用场景。为此，TU 等［8］提出MVPC 算法，指出测试删除可能会导致因果骨架冗余，并使用基于排列的校正方法和逆概率加权的校正方法对缺失数据的联合分布进行校正。但是，基于排列的校正方法仅适合缺失指示变量与缺失变量之间可被d-分离的场景，而不适合缺失指示变量与缺失变量不可被d-分离的场景。而Structure EM 算法［22］通过在候选模型中选择1 个模型作为当前模型，并和训练数据一起执行标准的EM 算法［23］得到最大似然对应的参数值，然后固定得到的参数值来迭代候选模型，直至找到最大似然对应的候选模型作为当前模型，依次交替迭代上面过程直至收敛。因此，Structure EM 算法仅适用缺失机制可忽略的场景，不适合非随机缺失数据上的因果结构网络学习。

2 缺失值因果学习框架

为了描述所解决的问题并介绍因果结构的学习框架，本节需要形式化定义一些前置概念，如缺失图、缺失图类型以及处理缺失所需的假设知识。

本文定义缺失图G={V,E}来表达因果结构网络。其中V=Vo∪Vm∪U∪V*∪R，Vo是完全观测变量集，在缺失图中使用白色实线结点表示。Vm表示至少含有1 条缺失记录的部分观测变量集，在缺失图中使用灰色实线结点表示。U表示未观测到的变量集，本文假设满足因果充分性假设，因此U是空集。V*是代理变量集，R表示缺失因果机制集，也就是缺失指示变量集，在缺失图中使用白色实线结点表示。RVi具体值表示Vi*是否缺失状态信息，如式（1）所示：

用大写字母Xi表示第i个变量结点，以及结点间的因果边集合E={(i,j)|Xi→Xj}。本文用小写字母x表示样本，令数据集，其样本量大小为m。若满足直接因果关系Xi→Xj，则称Xi是Xj的父母，如果存在间接因果边使得Xi→Xk→Xj，并称Xi是Xj的祖先。本文记Xi⊥GXj|S为给定条件集S，Xi与Xj在图G上条件独立。

缺失图的类型示意图如图1 所示。根据缺失数据问题分类方法，可将缺失图分为3 类［24］，如果在缺失图中满足Vm∪Vo∪U⊥R，那么缺失数据是完全随机缺失（Missing Completely At Random，MCAR），如图1（a）所示。如果在缺失图中满足Vm∪U⊥R|Vo，那么缺失数据是随机缺失（Missing At Random，MAR），如图1（b）所示。如果缺失图类型既不是MAR 也不是MCAR，那么属于非随机缺失（Missing Not At Random，MNAR），如图1（c）所示。

为了在缺失数据上进行因果结构网络学习，除了因果结构学习算法所需的基本假设［25］（包括因果马尔可夫假设、因果忠诚性假设、因果充分性假设和无选择偏差）以外，本文还需以下额外假设来解决缺失数据问题。

假设1（缺失指示变量不能是任何观测变量的原因）该假设在大多数缺失图相关工作［18-19］中被采用，在该假设下，如果给定条件集和指示变量集，感兴趣的变量之间独立，那么仅给定条件集，感兴趣的变量仍独立。

假设2（忠诚观察性）任何在观测到的数据集中成立的条件独立性关系同样也在未观测到的数据集中成立，形式化为X⊥Y|{Z,Rk=0}⇔X⊥Y|{Z,Rk=1}。该假设意味着缺失数据中的条件独立性关系在完整数据中也成立，即不存在由缺失引起的意外条件独立性关系。

假设3（在缺失指示变量之间无确定性关系）没有1 个缺失指示变量是其他缺失指示变量的确定性函数。

假设4（无自掩缺失）自掩缺失是指导致部分观测变量缺失的原因是该缺失变量本身，本文假设不会出现自掩缺失情况。

假设3 和假设4 共同保证了观测变量联合分布的可恢复性［18］。

图1 将缺失图和非线性加性噪声模型相结合，其中虚线圈结点表示注入结果变量的独立噪声。由于非线性加性噪声模型不适合高维因果结构网络搜索，因此需要将非线性加性噪声模型扩展至高维场景［17］，如式（2）所示：

本文通过式（2）将非线性加性噪声模型中原因变量和噪声变量之间的独立性检测转变为求解全局最大目标评分问题，从而实现对高维因果结构的搜索。

综上，本文的目标是满足假设1～假设4，在非随机缺失数据上识别因果结构网络中的因果对以及马尔可夫等价类结构，并校正由缺失导致的错误因果方向。

图2 所示为基于结构方程似然框架的缺失值因果学习框架，其中虚线和虚线箭头分别表示当前缺失图中因缺失数据可能产生的冗余边以及反向边。因此直接在缺失数据上进行因果结构学习可能导致因果结构学习结果不准确，需要校正因果结构。

图2 基于结构方程似然框架的缺失值因果学习框架Fig.2 Framework for causal learning of missing values based on structural equation likelihood framework

3 基于结构方程似然框架的缺失值因果学习算法

3.1 缺失数据的因果结构可识别性

本文简述缺失数据的因果结构可识别性以及逆概率加权校正方法。给定1 个缺失图，如果变量的联合分布可通过缺失数据变量表示出来，则变量的联合分布被认为是可恢复的，在进一步满足因果模型所需的假设时，本文认为观测数据的因果结构是可识别的，除此之外，还存在一些无法通过缺失数据变量来表示变量联合分布但仍满足因果模型假设的特殊可识别场景，如图1（d）所示。本文主要讨论变量的联合分布可恢复情况。

由于本文观测到的缺失数据分布为P(Xi|Pa(Xi),R=0)，因此根据缺失图类型分析，当缺失图类型 为MCAR 时，P(Xi|Pa(Xi),R=0)=P(Xi|Pa(Xi))，显然可通过缺失变量表示真实变量联合分布，不影响因果结构学习。但是当缺失图类型为MAR 或MNAR时，P(Xi|Pa(Xi),R=0)≠P(Xi|Pa(Xi))，此时无法通过缺失数据变量表示真实变量的联合分布。

因此，本文利用逆概率加权工具对有偏的联合分布进行校正，如式（3）所示：

3.2 评分函数

本节先给出标准的贝叶斯网络目标评分函数，再将逆概率加权加入到评分函数中。为了防止过拟合，大部分的评分函数都需要包含贝叶斯准则即惩罚项，如式（4）所示：

其中：n为变量数；m为样本量为惩罚项；di为估计Xi所需的系数个数是为了消除因缺失导致的样本量不同，从而降低对学习目标评分的影响。

结合式（2）和式（3），最后得到的目标评分函数如下：

3.3 算法框架

本文将设计算法流程来求解评分函数的最大似然。观察目标评分函数式（5）可得，c是常数，校正的关键是求，而要求 解βRi须先求Pari，如算法1 所示。

算法 1基于约束的方法学习缺失指示变量的父亲结点集

有关苏联剧变与戈尔巴乔夫的关系问题，至今还存在不同的看法。有人认为，苏联发生剧变完全是戈尔巴乔夫的责任，说是戈尔巴乔夫对苏联社会主义叛变行为的结果，甚至说他是叛徒。在这里笔者只是从戈尔巴乔夫改革与苏联剧变关系进行简要分析。笔者认为，在梳理戈尔巴乔夫时期改革与苏联剧变关系问题时，应该作出以下两个不同层次的结论：

为进一步求解βRi，本文需要确定成对删除处理缺失数据集所涉及到的结点集W以及逆概率加权求解所需的充分变量集U。首先有当前的最佳DAGG与下一步将要搜索的DAGGnei2 个图，将这2 个图进行比较，2 个图中父亲结点集不相同的结点为Vi，则成对删除所涉及的变量集W=由于在求解Pa(Vi)和Pa(Vi)nei时可能会引入新的缺失变量和中含有，因此需要迭代并入当前集合中缺失变量Xi的操作。最终得到充分变量集是1 个递归的过程，直至所涉及到的变量集不再更新为止，其作用如算法2 所示。

算法 2基于结构方程似然框架的缺失值因果学习算法

算法2 的主要过程是在当前图G中添加、反向、删除1 条边，然后构造邻居DAGGnei并且计算其目标评分，最后找出最大目标评分的图。在缺失数据上的目标评分经过逆概率加权调整，因此可得到正确的因果结构。

4 实验

本文将分别使用虚拟因果结构数据和真实因果结构数据对模型进行评估，并将MV-SELF 算法与主流的缺失值因果学习算法MVPC、TD-PC 算法［8］和Structure EM 算法相比较。为验证在非随机缺失数据上的有效性，本文将所有实验的缺失机制设为非随机缺失，将随机选择因果结构上1/2 的结点作为缺失变量。导致缺失的原因是变量优先考虑缺失变量的缺失孩子结点，若缺失变量没有缺失孩子结点，则随机选取除自身以外的其他缺失变量作为原因变量。对于某个变量导致的缺失，设定为：例如X导致Y缺失，当X值增大时，对应Y的值以概率P=0.1 缺失，反之对应Y的值以概率P=0.8 缺失。所有的参数敏感性实验都至少运行100 次以上，采用F1 值（F1）、准确率（P）、召回率（R）和结构性汉明距离［26］（Structural Hamming Distance，SHD）作为评价指标，计算表达式如下：

而结构性汉明距离表示2 个有向无环图PDAGs中1 个PDAG 通过添加、删除反向无向边和有向边匹配到另1 个PDAG 所需操作的总次数。

4.1 虚拟因果结构数据集

本文在虚拟结构数据上进行4 个控制变量实验，缺失变量数={4,7,10,13,16}，结构维度={5,10,15,20,25}，平均入度={0.5,1.0,1.5,2.0}，以及样本数量={1 000,3 000,5 000,7 000,9 000}实验，加粗表示实验中设置的默认参数，其中结构维度敏感度实验中缺失变量个数设定为总结点数的1/2。

图3 缺失变量控制实验的F1 值Fig.3 F1 values of missing variables control experiment

图4 缺失变量控制实验的结构性汉明距离Fig.4 Structural Hamming distance of missing variables control experiment

图5 和图6 所示为控制结构维度的实验结果。从图5 和图6 可以看出，MV-SELF 算法在结构维度比较大时同样有效，说明结构维度对MV-SELF 算法的影响很小。因此，MV-SELF 算法在不同维度下具有较优的鲁棒性。

图5 结构维度控制实验的F1 值Fig.5 F1 values of structure dimension control experiment

图6 结构维度控制实验的结构性汉明距离Fig.6 Structural Hamming distance of structure dimension control experiment

图7 和图8 所示为控制平均入度的实验结果。从图7 和图8 可以看出，MV-SELF 算法在稀疏结构下表现较优，而在稠密结构下表现不佳，但其实验结果仍优于其他对比算法。其原因为在稠密结构下准确计算逆概率加权依赖于缺失指示变量的父亲结点βRi，从而导致难度增大，造成实验效果下降。但MV-SELF算法的实验结果仍然比其他对比算法要好，因此实验结果验证MV-SELF 算法的有效性。

图7 平均入度控制实验的F1 值Fig.7 F1 values of average penetration control experiment

图8 平均入度控制实验的结构性汉明距离Fig.8 Structural Hamming distance of average penetration control experiment

图9 和图10 所示为控制样本量的实验结果。从图9 和图10 可以看出，MV-SELF 算法随着样本数量增加效果越好，说明样本数量有助于实验效果的提升，并且MV-SELF 算法明显优于其他比较方法，说明MV-SELF 算法具有一定的有效性。

图10 样本数量控制实验的结构性汉明距离Fig.10 Structural Hamming distance of numble of samples control experiment

4.2 真实因果结构数据集

本文选择4 个真实结构进行测试（https：//www.bnlearn.com/bnrepository/）。真实结构数据信息如表1 所示。

表1 真实结构数据信息Table 1 Real structure data information

在真实结构数据实验中，本文分别使用F1 值、准确率、召回率作为评价指标。

本文在真实结构数据中设定与虚拟结构数据实验中相同的实验环境。图11～图13 所示为不同真实结构数据的实验结果。从图11～图13 可以看到，MV-SELF 算法在不同的真实结构中均获得了最好的效果，特别是在ASIA 结构下实现了最佳效果，其原因为ASIA 的平均入度最低，这与虚拟结构数据的实验结果相吻合。与对比算法相比，本文所提算法MV-SELF 的准确率和召回率均较高，说明比较算法更容易学习到冗余边。由于比较算法没有考虑到因果结构网络的马尔可夫等价类结构，因此出现更多错误边是合理的，这也证明了MV-SELF算法的有效性。

图11 真实结构对比实验的F1 值Fig.11 F1 values of real structure comparison experiment

图12 真实结构对比实验的准确率Fig.12 Precision of real structure comparison experiment

图13 真实结构对比实验的召回率Fig.13 Recall of real structure comparison experiment

5 结束语

本文提出一种基于结构方程似然框架的缺失值因果学习算法。通过结合基于非线性加性噪声模型、逆概率加权校正工具，以及基于评分的方法优点，使得在非随机缺失数据上也能进行因果结构学习和校正。实验结果表明，该算法在虚拟因果结构数据集以及真实因果结构数据集上都具有较优的表现。下一步将对存在自掩缺失的因果结构学习问题进行研究。