从计算角度进行归类，因果推断可表示为关于变量的概率图模型，变量间的因果关系则可用模型中的有向边表示. 高维数据不同于传统的低维数据，它的复杂度更高，常用的基于条件独立测试或约束的方法只能得到变量间局部的因果关系. 考虑如下情形， $X \bot Y|Z$ (给定条件变量集 $Z$ ， $X$ 和 $Y$ 条件独立)，可推知 $X$ ( $Y$ )没有附加信息到 $Y$ ( $X$ )，进一步可知直接的因果关系在 $X$ 和 $Y$ 两者之间并不存在. 马尔科夫等价类问题尽管可以被现有的因果推断方法所解决，如IC算法，然而，算法所执行的时间不仅会随着维度的增加而增长，而且会随着样本量的增多，呈指数增长. 因此，高维数据中隐含的因果关系难以被现有的方法推断得到. 例如，现有的方法难以利用条件独立(Conditional Independent，CI)测试方法从变量数目超过50个的数据集中推断出其因果关系. 目前研究表明，高维数据因果推断面临的问题可总结为以下两个.

1) 难以在有效时间内从数据中搜索出可用于测试 $X \bot Y|Z$ 的CT测试中条件集 $Z$ 的所有可能结果.

2) 当 $Z$ 为高阶条件集时(个数变多)，测试每一对变量的CI测试方法通常并不可靠；若CI测试得到的错误结果也被接受，陷入第二类错误的情况则极有可能发生. 若 $X$ 、 $Y$ 直接连接则不会被任何其他变量集D分离，也就是说， $X\not{\bot }Y|Z$ ，而CI测试的结果相悖地认为 $X$ 和 $Y$ 是可D分离的.

有研究者为了克服上述问题提出SADA-LINGAM算法^[1]——一种基于分裂−合并策略的递归方法. 为简便起见，下文将采用SADA的英文缩写表示SADA-LINGAM算法. 该算法用至少2个子集划分原来的变量，分别对应利用现有的因果推断方法求解的各个子问题；通过对所有子问题的结果进行合并，最后推断出原始问题的因果关系. 考虑以下例子，给定某个集合 $V$ ，把其划分为 ${V_1}$ ， ${V_2}$ 和 $C = ({C_1},{C_2},{C_3})$ ；其中， ${V_1}$ ， ${V_2}$ 并不相连， ${V_1}$ ， ${V_2}$ ， ${C_1}$ ， ${C_2}$ ， ${C_3}$ 都是 $V$ 的子集. 接着，分别推断 $({V_1},C)$ 和 $({V_2},C)$ ，逐次递归直至子问题的变量数目足够小. 然而，设计出一个合适的分区过程并非易事，因为每次迭代都需要搜索集合 $C$ . 与此同时，条件集 $Z$ 所形成的“维度灾难”问题也不容忽视.

文献[2]开创性地提出一种新的REC因果分区方法. 其主要思想如下：移除满足 $x \bot y|V{\backslash _{x,y}}$ 条件的 $x,y \in V$ 的每对变量间的边，进而重建无向独立图. 类似地将无向独立图分解为 $V = \{ {V_1},{V_2},C\} $ (其中， ${V_1}$ ， ${V_2}$ 在 $C$ 条件下独立)；递归分解初始变量集 $V$ 直到得到无法再分解的每个子集，再将特定的约束方法应用于求解上述得到的子问题，并将所得子结果合并，最终获得原始问题的结果. 对比文献[3-4]所提出的方法，该分区方法更为有效. 文献[4]的方法采用直接删除条件集，这点不同于文献[2]需要每个分离图都包含完整无向图的处理方法；在依据变量集 $V$ 的情况下，它可以分解整个无向独立图，但不能分解对应的子图. 为此，一种基于无向独立图的新分区方法被Liu等^[5]提出，该方法不同点在于它基于评分搜索^[6]解决子问题.

该方法在处理过程中选择应用于实际中构造准确无向独立图的高阶CI测试方法，效率很低. 为解决这个问题，提高构造效率，基于SADA的递归方法被应用于文献[1]，其每次迭代过程中只需采用一次高阶CI测试，接下来用多次低阶测试分解 $V = \{ {V_1},{V_2},C\} $ 即可. 该方法由2个主要部分组成：(1)选择符合 $x,y \in V$ ， $x \bot y|V{\backslash _{x,y}}$ 的2个变量. 参考文献[7]中寻找最小D分离集的方法，寻找出变量 $x$ , $y$ 的最小D分离集 $C$ ；(2)令 ${V_1} = x$ ， ${V_2} = y$ ， $V = V{\backslash _{x,y,C}}$ ；对任意 $w \in V$ ，若 $\forall u \in {V_1}$ ， $\exists \tilde C \subseteq C$ 使得 $u \bot w|\tilde C$ ，则把 $w$ 移到 ${V_2}$ ；同理， $\forall v \in {V_2}$ ， $\exists \tilde C \subseteq C$ 使得 $v \bot w|\tilde C$ ，则把 $w$ 移到 ${V_1}$ ；否则，将 $w$ 移到 $C$ . 最后，得到两个子集 ${V_1} \cup C$ 和 ${V_2} \cup C$ . 然而，SADA算法同样存在上述问题：因为分离器 $C$ 是随机的，仅用枚举法一种方法来缩小 $C$ ^[1]，且CI测试的次数需要更多. 综上所述，该方法虽然在一些较小或稀疏的因果网络中应用效果较为可观，但应用于高维数据时，依然存在容易导致“维度灾难”的问题.

不失一般性地假设最小分离器的分布是关于两个不连接变量且服从不同自由度的 ${\chi ^2}$ 分布；随机选取通用因果网络中的两个变量，若两者是非连接的，相对于大的分离器，在D分离时选取最小或者中等的分离器的概率会更高. 阈值 $d$ 与最大条件集 $\left| Z \right|$ 的合理选择与限制，而且基于 $\left| Z \right| \leqslant d$ 的条件下，利用约束的方法测试 $X \bot Y|Z$ ，是这方面的一致性问题. 若阈值 $d$ 过小，大量非连接的变量未被及时D分离，进而导致精度低、召回率高的问题. 反之，则易于诱发第二类错误即使便于D分离地进行，而且会导致高精度、低召回率的发生，除此之外，返回最终结果也比较耗时，因为此时的时间复杂度接近于 $O({\left| V \right|^{d + 1}} \cdot CT)$ ，其中CT表示CI测试方法的时间复杂度. 通过分析可知，选择一个合适的阈值 $d$ 是十分重要的.

上述内容引发这样的思考：当重构一个粗糙因果骨架时，用来D分离两个变量的最小分离器的大小能否确定？如果能，即可以基于不同的阈值 $d$ 更准确地区分两个非相邻变量是否D分离.

基于此，本文提出了基于低阶条件独立测试的因果分割方法(Learning Causal Structure based on Causality Division，LCSCD)——一种具有可扩展性和有效性的因果推断方法. LCSCD算法只使用了低阶(变量个数小于等于2)CI测试方法，即可把原始的问题分割为多个子问题；在此基础上，再使用现有的因果推断算法如PC算法，逐一处理这些子问题；最后，合并所有子问题的结果，推断出完整的因果关系图.

为验证LCSCD算法具备更高的效率和可扩展性，实验针对较小、中等、较大3种规模的真实网络进行. 其中，按照目前因果推断的相关工作，较小、中等、较大是按照最小分离器的变量数量区分的，依次是指变量数目小于等于2、变量数目是3或4、变量数目大于或等于5时.

对比目前较为流行的算法SADA方法，LCSCD算法有两个优势：1) LCSCD算法在因果划分时更具可靠性；2) LCSCD在执行时间上耗时更短.

1 准备知识

用 $G = (V,E)$ 表示有向无环图(DAG)，其中 $V$ 是变量集，E是有向边集，图 $G$ 中没有循环. 有向边 $ < u,v > $ 表示变量 $u$ 指向 $v$ ，同时称为 $u$ 是 $v$ 的父亲节点， $v$ 是 $u$ 的孩子节点，同时用 ${\rm{Pa}}_{v}$ 来表示 $v$ 的所有父亲节点，用 ${\rm{Ch}}_{v}$ 来表示 $v$ 的所有孩子节点. 在 $G$ 中如果两个变量 $u$ , $v$ 邻接就说 $u$ , $v$ 两个节点有一条相连的边. 路径P是表示两个节点 $u$ 和 $v$ 之间的连接，以 $u$ 为第一个节点开始出发，以 $v$ 为最后一个节点结束，P就是途径的所有节点集. 同时如果在 $G$ 中有一条路径P从 $u$ 到 $v$ ，且所有的边都是最终指向 $v$ ，就定义 $u$ 为 $v$ 的祖先， $v$ 为 $u$ 的子孙. 路径P被一组节点集 $Z$ 给D分离的情况如下：1) 路径P是链条结构 $u \to v \to w$ 或者分支结构 $u \leftarrow v \to w$ ，其中 $v$ 在分离集 $Z$ 中. 2) 路径P是碰撞结构 $u \to v \leftarrow w$ ，其中 $v$ 不在分离集Z中且 $v$ 的后代也不在Z中. 如果节点集X到节点集Y的每一条路径都被集合Z给D分离，则称为Z集合是X和Y的分离器. 根据D分离的定义，如果两个节点 $u$ 和 $v$ 不邻接，若存在 $Z \subseteq P{a_u} \cup P{a_v}$ ，则u和v在Z条件下D分离.

如果在 ${V'}$ 集内没有两个或以上的变量共享 $V$ 外面的因果变量，则变量 ${V'} \subseteq V$ 集是充分因果关系. $u \bot v$ 表示 $u$ 和 $v$ 独立， $u \bot v|Z$ 表示在Z条件下 $u$ 和 $v$ 独立^[8-10]. 一般地，假设通过在 $G$ 中进行D分离检测在 $V$ 中变量的概率分布的所有依赖性，称为忠诚假设，即所有独立和条件独立可以在图 $G$ 中表示^[11-13]. 因此，在DAG中用 $ \bot $ 来表示D分离. 遵循现有研究的共同假设，关于 $G$ 可以通过测试两个变量是否D分离，基于约束方法如PC算法来发现因果骨架或一组马尔科夫等价类. 然而，随着所需的样本大小随着 $V$ 的大小呈指数级增长，直接用PC算法一般无法恢复高维数据所有变量之间的因果关系.

2 LCSCD算法 2.1 算法框架

首先定义有效因果分区^[1]，然后提出LCSCD方法的框架.

定义1　给定 $G = (V,E)$ 在变量集 $V$ 中表示一个DAG，从图 $G$ 中进行因果分区得到3个不重叠的变量子集 ${V_1}$ ， ${V_2}$ ， $C$ . 当且仅当1) ${V_1} \cup {V_2} \cup C{\rm{ = }}V$ ；2) $\forall u \in {V_1}$ ， $\forall v \in {V_2}$ ，且u和v不相邻.

直观来说， ${V_1}$ 中的任意节点到 ${V_2}$ 中的任意节点间的通路被 $C$ 阻塞. 因此，可以用2个较小子集 ${V_1} \cup C$ 和 ${V_2} \cup C$ 的因果推断代替变量集 $V$ 上的因果推断.

LCSCD方法的描述如算法1的伪代码所示，其中输入的参数包括集合 $V$ 、阈值 $\delta $ 和自定义采用的现有因果推断算法A(如PC算法). 当递归分区过程的子集的变量数小于所设置的 $\delta $ 时，终止递归. 算法1主要包括两个过程：1) 寻找一个因果分区(对应于伪代码第6行)；2) 更新子网络至大网络(对应于伪代码第8行). 详细的算法流程如下：

算法1：LCSCD

1: Input: dataset $\scriptstyle{V}$ , threshold $\scriptstyle\delta $ , algorithm $\scriptstyle{A}$

2: Output: Causal skeleton $\scriptstyle{S}$

3: Construct a fully connected graph G on V.

4: To search a causality division $\scriptstyle({V_1},{V_2},C)$ over V.

5: if $\scriptstyle\left| {{V_1} \cup C} \right| \geqslant \delta $ then

6: LCSCD( $\scriptstyle{V_1} \cup C$ , $\scriptstyle\delta $ , $\scriptstyle{A}$ )

7: else

8: Update the skeleton S to G by $\scriptstyle{A}$ ( $\scriptstyle{V_1} \cup C$ ).

9: end if

10: Do the same process (Lines 4-8) to $\scriptstyle{V_2} \cup C$ .

2.2 寻找因果分区

LCSCD算法的重点之一在于因果分区的搜索过程. 算法采用CI测试处理输入变量以识别潜在的因果分区. 该过程如算法2的伪代码所示.

算法2：Searching Causal Division (寻找因果划分)

1: Input: The variables set $\scriptstyle{V}$ ; $\scriptstyle\sigma $ : The maximum order of CI tests;

2: Output: The causal division $\scriptstyle({V_1},{V_2},C)$ ;

3: Construct fully connected graph $\scriptstyle{G}$ on $\scriptstyle{V}$ .

4: For $\scriptstyle\forall {v_i},{v_j} \in V$ , delete the edge between $\scriptstyle{v_i}$ and $\scriptstyle{v_j}$ if $\scriptstyle{v_i}$ and $\scriptstyle{v_j}$ is independent given an arbitrary S with $\scriptstyle\left| S \right| \leqslant \sigma $ and $\scriptstyle{S \subseteq V\backslash {v_i},{v_j}}$ .

5: end if

7: for $\scriptstyle\forall {v_i} \in V$ do

8: Add $\scriptstyle{v_i}$ into $\scriptstyle{V_1}$ if $\scriptstyle{v_i}$ and $\scriptstyle\forall {v_j} \in {V_2}$ are non-adjacent;

9: Add $\scriptstyle{v_i}$ into $\scriptstyle{V_2}$ if $\scriptstyle{v_i}$ and $\scriptstyle\forall {v_j} \in {V_1}$ are non-adjacent;

10: Add $\scriptstyle{v_i}$ into C, if $\scriptstyle\exists {v_j} \in {V_1}$ and $\scriptstyle\exists {v_k} \in {V_2}$ such that $\scriptstyle{v_i}$ is adjacent to $\scriptstyle{v_j}$ and $\scriptstyle{v_k}$ .

11: end for

12: Return the causal division $\scriptstyle({V_1},{V_2},C)$ .

划分初始变量集 $V = \{ {v_1},{v_2}, \cdot \cdot \cdot {v_n}\} $ 的过程如下：首先，构造一个关于 $V$ 的全连接图 $G$ (伪代码第3行). 然后根据 $(0 \sim m)$ ( $m \leqslant \sigma $ )阶条件独立性测试，将 $G$ 中被验证可以被D分离的边剔除，得到一个关于 $V$ 的粗糙无向图 $G$ . (伪代码第4行). 接着描述集合 $V$ 的分区过程，把 $V$ 划分为3个部分 $V = \{ {V_1},{V_2},C\} $ ：(1)如果 ${v_i}$ 和 $\forall {v_j} \in {V_2}$ 是非邻接，则把 ${v_i}$ 加到 ${V_1}$ 集里；(2)如果 ${v_i}$ 和 $\forall {v_j} \in {V_1}$ 是非邻接，则把 ${v_i}$ 加到 ${V_2}$ 集里；(3)如果存在 $\forall {v_j} \in {V_1}$ 和 $\forall {v_k} \in {V_2}$ ， ${v_i}$ 是 ${v_j}$ 和 ${v_k}$ 的邻接点，则把 ${v_i}$ 加到集合 $C$ (伪代码第7~11行). 最终获得因果分区 $V = \{ {V_1},{V_2},C\} $ .

同样，获得关于子问题的一个子集 ${V^t} = \{ {v_1},{v_2},$ $\cdot \cdot \cdot , {v_n}\}$ ，由于相应的粗糙图G是在前一次迭代获得，用遵循类似(伪代码第7~11行)的过程来获得因果分区 ${V^t} = \{ {V_1},{V_2},C\} $ .

假设给定的原始数据集为 $V = \{ {v_1},{v_2}, \cdot \cdot \cdot , {v_n}\} $ ，通过算法1与算法2将 $V$ 分成了 $m$ 个子数据集 $\{ {V_1}, \cdot \cdot \cdot ,{V_m}\} $ . 接着用PC算法作为子数据集学习因果关系的算法，则该部分的时间复杂度为 $O({k_{{\rm{max}}}}{2^{({k_{{\rm{max}}}} - 2)}})$ ，其中 ${k_{{\rm{max}}}}$ 为 ${\rm{max}}(\left| {{V_1}} \right|, \cdot \cdot \cdot ,\left| {{V_m}} \right|)$ . 另外，计算因果划分V所耗的时间；算法执行 $\sigma $ 阶的独立性测试，因此算法的总时间复杂度为 $O({k_{{\rm{max}}}}{2^{({k_{{\rm{max}}}} - 2)}}{\rm{ + }}{n^{(\sigma + 2)}})$ . 假设这个因果推断问题完全由PC算法解决，则时间复杂度为 $O({2^{(n - 2)}}{n^2})$ . 由于m往往比n小得多，且 ${k_{{\rm{max}}}}$ 也比n小得多，因此LCSCD在处理因果推断问题上的效率要优于传统PC算法.

3 实验分析

为综合评价本文所提出的LCSCD算法的效率与准确率等指标，实验采用文献[1]中涉及的来自不同实际应用领域的6个因果网络数据集(这些数据集均基于某一个因果推断领域中通用的线性模型^[1]， ${v_i} = \sum\nolimits_{{v_1} \in {\rm{Pa}}_{{{v_i}}}} {{w_{ij}}{v_j} + {e_i}} $ ， ${\rm{sum}}({w_{ij}}) = 1$ ). 上述网络结构的数据集覆盖了多个应用领域，包括规模较小( $20 \leqslant \left| V \right| < 50$ ， $\left| V \right|$ 是整个网络的维数)的ALARM和BARLEY、规模中等( $50 \leqslant \left| V \right| < 100$ )的HAILFINDER和WIN95PTS、规模较大( $\left| V \right| \geqslant 100$ )的ANDES和PIGS. 表1列出了这些网络的结构节点数量、平均度和最大入度3个参数的统计情况.

为探索LCSCD算法在因果分区的性能表现，采用与当前流行的SADA算法^[1]进行对比实验. 在6个不同网络下分别以样本数{25,50,100,200,400}来评估两种算法之间的性能和准确率. 此实验寻找的因果骨架是无方向的，因为目前可用于判断现成网络骨架中的因果方向的算法有很多，如V结构方法^[14-16]、ANM方法^[17-21]，以及IGCI(信息几何因果推断)方法^[22-26]等. 实验采用文献[27]中用到的CI测试方法，设置阈值为5%；为了防止子网络数目呈指数级增长，把各数据集的子网络维度大小都设置为 $\delta = \left| V \right|/10$ ，当算法达到阈值时停止分区. 一般而言，这样划分得到的子网络的维度已足够小，接着应用现有的因果推断算法(如PC算法)判断其中的网络方向.

LCSCD算法和SADA算法在6个不同数据集、不同样本下进行Recall(召回率)、Precision(精度)和F₁评价指标的比较，结果如图1所示，这些指标的定义如下：

${\text{召回率}} = \frac{{{\text{因果推断节点}} \cap {\text{真实因果节点}}}}{{{\text{真实因果节点}}}}.$

(1)

${\text{精度}} = \frac{{{\text{因果推断节点}} \cap {\text{真实因果节点}}}}{{{\text{因果推断节点}}}}.$

(2)

$F_1 = \frac{{2 \times {\text{召回率}} \times {\text{精度}}}}{{{\text{召回率}} + {\text{精度}}}}.$

(3)

式(1)~式(3)中，实际因果网络中各节点间的因果关系称之为真实因果节点，利用算法推断得到的各节点间的因果关系则是因果推断节点. 推断所得因果网络正确边的方向与实际因果网络的比值定义为召回率，而精度则是推断所得因果网络正确边的方向与推断网络之比. F₁是评价算法中的一种标准.

观察并分析图1可知：1) 从总体上观察综合评价指标F₁的值可知LCSCD算法在6个不同网络、不同样本的情况下得到的数值比SADA算法所得的结果更优；2) SADA算法的Recall值和Precision的准确率均随样本量的增加而增加，但后者增幅较小；3) LCSCD算法和SADA算法的F₁值均与样本量呈正相关关系，但前者在小样本量时增长率较快.

通过对比表2统计的执行时间情况，易知：1) LCSCD算法的执行时间远小于SADA算法，特别当样本量大、数据维度高时，后者的执行时间是前者的近10倍；2) LCSCD算法在相同数据集、不管样本大小下的执行时间基本保持稳定，而随着数据集维度的增加，SADA算法的执行时间将不断增长；3)特别在维度达到441维的PIGS数据集，当样本量超过25时，LCSCD算法仍能够得出结果，而SADA算法则无法在有效时间内得出结果.

4 结束语

本文提出一种兼具有效性与扩展性的因果推断算法——LCSCD算法. 即使当数据集属于高维度范畴时，该算法仍可采用低阶CI测试对数据集进行分区推断(应注意条件集的变量数目一般不大于2). LCSCD算法的主要流程可分为3步：首先，把目标的大问题分割成数目小于某设定阈值的子问题，该过程可采用分区的方法处理；其次用现有的算法如PC算法，对分割的每个子问题进行因果推断；最后，对所得的子网络结果进行合并以获得所需的完整的因果网络骨架图. 为了验证本文所提算法的性能，将算法应用于6个规模相异的网络，并不失一般性地以样本量作为变量. 通过对比实验，可知本文提出LCSCD算法无论在效率还是准确率都要优于目前较为先进的SADA-LINGAM算法. 本研究后续工作将进一步探讨优化算法的分区模式以提高算法的准确率和性能.