图、矩阵和概率的一些交集

最直观的概率是事件的概率，比如抛一次硬币为正的概率，这种情况下，如果 P 是表示概率的函数， P(x) 就是将一个事件 映射到一个 0 到 1 之间的实数值。

而事件是什么？放在现实世界中，它是某一连串状态的变化或结果，但放在语言中， 它就是一个句子，并且是可以谈论真和假的句子，比如“硬币结果为正”，如果是假的，概率就是 0 ，如果是真的， 那么可以附着一个正的概率值，也就是说，概率函数所处理的目标和真值函数（或者命题逻辑）所处理的目标是同类型的句子，我们不能把一个祈使句看作命题，给它赋予真或假，比如 "请给我手机" 是真还是假呢？ 同样，也不能把一个祈使句看作事件，从而去讨论它的概率，比如 P("请给我手机") 基本是无意义的。

因此概率可以看作是对命题真假值的一个扩充，如果命题为假，那么概率为 0, 如果为真，那么不单可以用 True 或 1 这样的离散分类值去非黑即白地描述该命题的含意，还可以用 0 到 1 之间的浮点数去捕捉其真和假的程度。

然而，很多时候讨论的实际不是单个事件的概率，而是某个场景下所有不同事件的概率分布，这时候会用一个随机变量来把事件映射到某个数，比如把本次抛硬币场景下 "硬币为正" 映射到 1, 把 "硬币为反面" 映射到 0 ，如果用 X 表示这个随机变量，那么 P(X=1) 中 X=1 实际描述的是 X=1 方程的解，而解的结果是一个事件命题，在硬币的例子里， X=1 的解是 "硬币为正" 这个命题，X=0 的解是命题 "硬币为反面" 。只不过这种解并不是代数或者数值方程，而是 类似概念方程。

对于简单的离散情况，由于我们实现就用映射表（类似 python 字典）的方式定义了随机变量 X:

X={"硬币为正": 1, "硬币为反": 0}

那么当解 X=0 的时候就是反转这个字典，并且去求值

{value:key for key, value in X.items()}[0]

硬币为反

尽管这次逆向求解看上去很简单，但随机变量之间可以进行任意形式的正向组合，比如定义新的随机变量 Z=X+Y, 其中 Y 也是

Y={"硬币为正": 1, "硬币为反": 0}

X 和 Y 的加法并不是普通变量的加法，而是函数之间的组合，其组合方式和结果如下：

Z = {}
for x in X:
    for y in Y:
        Z[(x,y)] = X[x]+X[y]

from pprint import pprint
pprint(Z)

{('硬币为反', '硬币为反'): 0,
 ('硬币为反', '硬币为正'): 1,
 ('硬币为正', '硬币为反'): 1,
 ('硬币为正', '硬币为正'): 2}

这个时候给定 Z=1 去解方程，解出来的结果不是单个事件，而是事件的集合，并且每个事件是 X,Y 中事件的组合：

{('硬币为反', '硬币为正'),
 ('硬币为正', '硬币为反')}

如果随机变量更为复杂，比如是 X^2+XY-1 呢？逆向根据随机变量值求解出概念事件的过程就会变得非常复杂。

而如果给变量值添加概率分布，那么 P(X) + P(Y) 则称为卷积。

假设 A 和 B 都是把事件映射到 0/1 的随机变量（也称伯努利随机变量，是一个二值函数），它们的值到概率的映射函数（又称概率表，或概率分布）如下：

注意，根据概率公理，要保证第二列求和为 1 。

那么问题是，P(A)P(B) 是什么？不考虑任何独立性条件，可以用笛卡尔积的方式强行得到以下函数：

以上表格第三列求和后也是 1, 那么这有两个问题：

• 为什么等于 1?

  因为最后一列求和表达式为 P(A=0)P(B=0) + P(A=0)P(B=1) + P(A=1)P(B=0) + P(A=1)P(B=1)

  提取公因式：

  P(A=0)(P(B=0)+P(B=1)) + P(A=1)(P(B=0)+P(B=1)) = P(A=0)+P(A=1) = 1

  或者更高层来看，是 P(A) 的每一行都乘以了 P(B) 的每一行，而 P(B) 行加起来是 1, 因此 P(A) 的每一行为求和表达式共享了当前这一行的概率，最终结果就是 P(A) 的每一行相加，结果为 1 。

• 既然最后一列求和为 1, 那么这个表可以看作是一个概率分布, 但它是哪个变量的分布，有什么意义？

  一种情况是，如果 A 和 B 独立，那么有 P(A)=P(A|B) 或 P(B)=P(B|A), 再根据条件概率的定义 P(A|B) = P(A,B)/P(B) 可以知道 P(A,B)=P(A|B)P(B) = P(A)P(B) 。

  也就是说，在 A, B 独立的情况下，最后一列可以被赋予 P(A,B) 意义，它表示这是 A,B 中事件同时发生的概率。 但如果没有这个条件，则无法找到一个具体的解释，只能说它是“假设 A,B 独立的情况下的联合概率”。

  另外，A,B 独立的情况下， P(A|B) 为：

  B	A	P(A/B)
  0	0	0.1
  0	1	0.9
  1	0	0.1
  1	1	0.9

  这种情况下，并非最后一列的值求和为 1, 而是根据 B 的值分成了多个组，每个组里的第三列的值求和为 1.

  此外无论 B 是 0 还是 1, P(A=0|B) 的值都等于 P(A=0|B), P(A=1|B) 的值都等于 P(A=1|B) 。

  P(B|A) 为：

  A	B	P(B/A)
  0	0	0.2
  0	1	0.8
  1	0	0.2
  1	1	0.8

假设 A 的分布仍然是：

但我们不知道 B 的分布，而是知道给定 A 的值之后 B 的条件分布：

从以上表格第一和第三行（或第二和第四行）可以看出，P(B=0|A=0)!= P(B=0|A=1), 因此这就足以说明 A 和 B 变量并不独立。这体现了独立性是一个非常强的条件，找到单个数值不一致就可以推翻独立性，而要验证独立性则要完整计算出 P(A)P(B)=P(A,B), 从前文给出的 P(A)P(B) 的表格可以知道，这是两个分布之间的比较，需要比较每一行和每一列。

根据条件概率公式，我们可以计算出 P(A,B):

现在问题是：

• 为什么以上表格最后一列求和为 1 ？ 因为 P(A=0) 只对 P(B|A) 前两行进行相乘，而这两行相加是 1, 因此 P(A,B) 前两行相加是 P(A=0), 同理，后两行相加 是 P(A=1), 而二者再相加为 1.

• P(B) 是什么样子的？ 根据概率公理中的可加性，可以计算出边缘概率：

  • P(B=0) = P(A=0,B=0) + P(A=1,B=0) = 0.39
  • P(B=1) = P(A=0,B=1) + P(A=1,B=1) = 0.61

  B	P(B)
  0	0.39
  1	0.61

• P(A)P(B) 呢？

  A	B	P(A)P(B)
  0	0	0.156
  0	1	0.244
  1	0	0.234
  1	1	0.366

  它和 P(A,B) 的值是不同的。

• P(B)P(B|A) 是什么？

  几乎是没有直接的概率解释

以上用表格来表示 P(A) ，P(B|A) 等分布可以看作是一种非参数化模型，它和把数据直接呈现出来几乎是一样的， 比如以下表格可以解释成是直接统计硬币抛了 10 次之后的正反面出现的频率：

参数模型则是用一个函数方程来“压缩”这些数据，比如最常见的描述二元随机变量的伯努利分布函数： \( f_{A}(x)=p^x(1-p)^{(1-x) \)

p 取 0.9 就完全可以复原以上表格。

函数 \( f_{A}(x) = 0.8x+0.1 \) 也是可行的。

现在假设 P(B) 的参数方程是 \( f_{B}(x)=0.6x+0.2 \), 那么 P(A)P(B) 是什么？

我们用 a 和 b 表示 A,B 的具体取值（范围是 {0,1}）, 那么两个概率分布为：

\( f_{A}(a) = 0.8a+0.1 \)

\( f_{B}(b)=0.6b+0.2 \)

假设 A,B 独立，P(A,B) = P(A)P(B) 的参数方程可以写成：

\[ f_{A,B}(a,b) = (0.8a+0.1)(0.6b+0.2) \]

注意这是关于 a 的函数 h(a)=0.8a+0.1 和关于 b 的函数 h(b)=0.6b+0.2 的乘积 h(a)h(b)

假设 A 的分布还是 \( f_{A}(a) = 0.8a+0.1 \) ， 但我们不知道 B 的分布，而是知道给定 A 的值之后 B 的条件概率函数：

\[ f_{B|A}(a, b) = (0.4b+0.3)^{1-a}(0.2b+0.4)^{a} \]

把所有可能的 {0,1} 取值代入后，它和以下无参数的表格数据是一致的：

那么根据 P(A,B)=P(A)P(B|A) 可以得到联合分布函数：

\[ f_{A,B}(a, b)=f_{B|A}(a, b)f_{A}(a) = (0.4b+0.3)^{1-a}(0.2b+0.4)^{a}(0.8a+0.1) \]

不同于 A,B 独立的情况，这个式子无法写成单独的只关于 a 的函数和只关于 b 的函数的乘积。

另外，如果要从该函数直接求出边缘分布 P(B), 可以写成 \[ f_{B}(b) = f_{A,B}(0, b) + f_{A,B}(1, b) = (0.4b+0.3)(0.1) + (0.2b+0.4)(0.9) = 0.22b+0.39 \]

它和上一节的以下分布是一致的：

上一节已经提到概率分布分解的例子，如果 A,B 独立，那么 P(A,B)=P(A)P(B), 也就是联合分布函数可以写成两个只关于变量 a,b 的函数的乘积。本节继续将其扩展到更多变量以及条件独立下概率的分解性质。

为什么要讨论概率的分解形式呢？

小学时学过正整数的因式分解，比如九九乘法表就是 100 以内整数的乘法分解模式。

中学时又学习到任何整数都可以拆成素数因子的乘法，还会学会了多项式的分解，某个多项式，如 \( x^{2}-2x+1 \) 能写成更简单两个多项式 \( (x-1) \) 的乘法 ，那么问题可能就会变得更简单。

分解是一种还原论的思想，使得能用更小更简单的部分去理解更大更复杂的对象。

根据独立和条件独立性，概率的分解天然地也是一种乘法分解性质：

如果 A,B 独立： P(A,B) = P(A)P(B)

如果 A,B 在给定 S 下独立： P(A,B|S) = P(A|S)P(B|S)

如果 A,B 是事件，那么这是普通的数值的乘法分解，然而更多时候 A,B 是随机变量（更多时候用 X,Y 表示随机变量），而随机变量之间概率的乘法 P(X)P(Y) 是一种接近笛卡尔积的操作。

如果 0/1 随机变量 X 和 Y 的概率密度函数如下：

\( f_{X}(x) = 0.8x+0.1 \)

\( f_{Y}(y)=0.6y+0.2 \)

那么 X,Y 独立时联合分布就是 P(X,Y)=P(X)P(Y), 可以写成

\[ f_{X,Y}(x,y) = (0.8x+0.1)(0.6y+0.2) \]

这意味着，如果变量独立，那么联合分布就可以写成各个变量分布之间的乘积形式 h(x)h(y) 。

如果 X,Y 不独立呢？那么一种直觉是，它无法拆分成 h(x)h(y), 而是两个变量耦合在一起的函数 h(x,y), 比如 h(x,y) = 0.25(x+y) 时 P(X,Y) 的概率表如下：

边缘概率：

可以看到， P(X=0)P(Y=0) 不等于 P(X=0,Y=0), 因此 X 和 Y 变量不独立。

这里想表明的是，虽然 0.25(x+y) 是简单的线性函数，但概率中，独立性意味着的是乘法的解耦。 实践场景下，很多非独立变量之间的概率分布是形如 exp(xy)/Z 的指数形式耦合在一起的。

现在检查条件独立下概率分布的拆分形式：

如果 X,Y 在给定变量 S 的情况下独立，那么 P(X,Y|S)=P(X|S)P(Y|S), 这里直接可以看作是只包括 X 和 S 变量的函数 h1(X,S) 和只包括 Y 和 S 变量的函数 h2(Y,S) 的乘积，因此如果条件独立，那么条件变量会被分配到两个解耦的因子函数中去，但 X,Y 本身的变量是可以分开的。

这个结论的反方向也是成立的，它被以下定理：

对于无向图，可以得到以下性质

• 对称性：如果 ind(A,B)|S, 那么 ind(B,A)|S 如果 S 阻断了 A 到 B 之间的所有通路，那么 S 也阻断了 B 到 A 所有通路，A,B 在给定 S 的情况下是独立的。
• 分解性：如果 ind(A,B+C)|S, 那么 ind(A,B)|S 以及 ind(A,C)|S 如果 S 阻断了 A 到 B 和 C 之间的路径，那么 S 阻断了 A 到 B 之间路径，二元阻断了 A 到 C 之间路径。
• 弱联合性： ind(A,B+C)|S, 那么 ind(A,B)|S+C 如果 S 阻断了 A 到 B 和 C 之间的路径，阻断 S 以及 C 也能断开 A 到 B 之间的联系 对于无向图来说，这可以从分解性推导出来，ind(A,B+C)|S 已经蕴含了 ind(A,B)|S ，而阻断更多的节点是不会 使得原本就阻断的两个节点从新获得联系的（这个性质其实需要一个名字），因此 ind(A,B)|S+C

• 收缩性： 如果 ind(A,B)|S 以及 ind(A,C)|S+B 那么 ind(A,B+C)|S

  如果 A,B 本身被 S 阻断，那么 A 到 B 之间的所有联系都来自 S, 此时 A 到 C

• 交叉（Intersection）: ind(A,C)|S+B 和 ind(A,B)|S+C, 那么 ind(A,B+C)|S

满足性质称为 graphoid

这种性质的描述是抽象的，这意味着它可以和不同具体场景结合，获得不同的解释，比如可以把 ind 关系解释成无传染风险，也可以解释成信息的流动关系：

• 对称性公理指出，在任何知识状态 S 中，如果 B 对 A 没有提供新信息，那么 A 对 B 也没有提供新信息。
• 分解公理断言，如果两条结合在一起的信息被判定对 A 无关，那么每一条单独的信息也和 A 无关的。
• 弱联合公理表明，学习到无关的信息 C 不会使无关的信息 B 对 A 变得相关。
• 收缩公理指出，如果在得知无关信息 B 之后， C 对 A 是无关的，那么在我们得知 B 之前，C 和 A 也一定是无关的。 弱联合和收缩属性共同意味着，无关信息不应改变系统中其他命题的相关性状态； 曾经相关的仍然相关，曾经无关的仍然无关。
• 交叉公理指出，如果 B 在我们知道 C 时对 A 无关，并且 C 在我们知道 B 时对 A 无关，那么 C 和 B（以及它们的组合）都对 A 无关。

对于概率分布，则解释成条件独立，把条件独立替换以上无关，即获得了概率下的解释。

但对于概率的独立性，如果其中有 0 概率，那么不会满足最后的交叉性质，这类似奇异值塌缩了。

既然图中节点的独立性（非联通性）和概率的条件独立性都有 graphoid 性质，那么如何把他们对应起来呢？

既然无向图已经可以“编码”概率中的相关关系，为什么要有向图？相比于无向图，有向图增加了更多“先验信息” – 方向。

有向图对于概率分布的分解更有“概率意义”

假设有一个有向图如下

如果某人说，联合概率分布 P(A,B,C,D) 可以按照以上图的形式进因式分解，这意味着 P(A,B,C,D) 可以写成 P(A)P(B)P(C|A,B)P(D|C)

那么：

这使得整个分布的参数就少了很多，这是还原主义的思路，原本 P(D|A,B,C) 这种需要各个节点信息一同支撑的公式 简化成了 P(D|C), 只需要局部 C,D 两个变量的信息，建模成本就低了很多。

一般来说，给定更多的变量，A 和 B 独立的可能性越大

可以写一个算法遍历出所有分解方式：

from itertools import permutations
def generate_conditional_prob(args):
    if len(args) == 1:
        return f"P({args[0]})"
    return f"P({args[0]}|" + ",".join(args[1:]) + ")"

def chain_rule(variables):
    res = []
    for per in permutations(variables):
        factors = []
        for i in range(len(per)):
            factors.append(generate_conditional_prob(list(per)[i:]))
        res.append("".join(factors))
    return res

v = ["A", "B", "C"]
for factor in chain_rule(v):
    print(f"P({','.join(v)}) = {factor}")

P(A,B,C) = P(A|B,C)P(B|C)P(C)
P(A,B,C) = P(A|C,B)P(C|B)P(B)
P(A,B,C) = P(B|A,C)P(A|C)P(C)
P(A,B,C) = P(B|C,A)P(C|A)P(A)
P(A,B,C) = P(C|A,B)P(A|B)P(B)
P(A,B,C) = P(C|B,A)P(B|A)P(A)

如果有 n 个变量，就有 n! 种不同的分解方法。 假设所有变量都只有 0/1 两个取值，那么 P(C|B,A) 实际有 2^3 = 8 个参数，并且在 A 和 B 相等的时候，C 的不同取值之和要等于 1, 一个例子如下：

因果推断一般称为 Causal Effects estimate, 这是 可是识别性问题：一种最简单的无法识别的情况就是，A->B, 但我们不知道 A 和 B 还有一个 confounding C, 这种情况不可能计算出 A 到 B 的因果影响。 正式定义是？

如果没有隐藏的因果变量，那么可以用前后门准则来判断可识别性，并且这两个准则直接

为什么说后门准则和 conditiaonal ignorability 是一样的，能否用例子说明：

这种图在因果发现中称为 CPDAG （Completed Partially Directed Acyclic Graph）

前文说明，无向图的路径阻挡满足 graphoid 性质，本节则说明有向图中的 d 分离也满足以上所有性质，这里证明其满足弱联合和收缩性：

• 弱联合性： ind(A,B+C)|S, 那么 ind(A,B)|S+C

  我们证明其逆否命题，即如果 A B 中分别有节点 a,b, 在给定 S+C 的情况下，还存在一个路径 p 是 d-connected 的，那么在只给定 S 的情况下存在一条从 A 集合到 B+C 结合的联通路径 p', 注意 p' 不一定等于 p.

  我们还是分情况去构造出 p'：

  • p 中不包括对撞结构，那么 p 和 S+C 的交集应该是空集，否则 p 应该是 block 的，这种情况下，p' = p
  • p 中包括对撞结构，假设这些对撞节点集合是 X, 那么 des(X)+X 和 S+C 的交集不为空。如果 des(X)+X 和 C 的交集为空，那么对撞或者后代只和 S 有交集，此时 p' 可以等于 p 。如果 des(X)+X 和 C 的交集不为空，假设其节点集合为 Z，那么 Z 经过对撞点再经过复用路径 p 中对撞到到 B 的路径是联通的。

• 收缩性：如果 ind(A,B)|S 以及 ind(A,C)|S+B 那么 ind(A,B+C)|S

  仍然证明其逆否命题，如果给定 S, A 到 B+C 存在一条联通路径 p，那么：

  1. 要么给定 S ， A 到 B 之间存在联通路径 p'
  2. 要么给定 S+B ， A 到 C 之间存在联通路径 p'

  还是分情况：

  • p 中不包括对撞结构，那么 p 不会经过 S, 这时候继续分两种情况：
    • p 经过 B, 那么 p' 取 p, 满足以上第一个要求
    • p 不经过 B, p' 取 p, 满足以上第二条要求
  • p 中包括对撞结构，那么 p 中所有对撞点及其后代和 S 有交集：
    • p 经过 B, 那么 p' 取 p, 满足以上第一个要求
    • p 不经过 B, p' 取 p, 满足以上第二条要求

如果 A 是某个有向图 G 的邻接矩阵，即 A[i,j]=1 等价于 G 中存在边 i->j 。 那么对 A 求平方后， \( A^{2}_{i,j} =\sum_{k}A_{ik}A_{kj}\), 这相当于从节点 i 到节点 j 的长度为 2 的有向路径的数量。 根据归纳法可以知道 \( A^{n}_{ij} \) 表示的就是从节点 i 到节点 j 中的数值表示为 n 的有向路径的数量。

对于有向无环图，无环意味着不存在从 i 到 i 的有向路径，而 \( tr(A^{n}) \) 是 \( A^{n} \) 对角线上元素的和，也就是长度为 n 的环的数量，对于有向无环图，对于 n>=2 的情况下 \( tr(A^{n}) \) 均为 0 。而对于 A=1 的情况，本身约定 A 对角线上元素都为 0, 因此 tr(A) = 0, 对于 n = 0, 根据定义 \( A^{0} =I\) ，因此 \( tr(A^{0}) = d \) ，其中 d 是 A 的维度，也就是图中节点的数量。

接着考虑更一般的情况，对于 DAG, 对于两个不同的节点 i,j, i 到 j 的有向路径会有什么性质呢？注意 i 到 j 的所有路径中，最长的路径长度不可能等于或大于节点数 d ，如果等于 d，那么（根据鸽巢原理）路径中一定存在环， 比如说只有三个节点 1,2,3 的图，那么 1 到 3 的路径最多就是 1->2->3, 长度为 d-1, 如果等于 d, 比如 1->2->1->3, 那么就存在环 1->2->1 了

这个性质使得 DAG 的邻接矩阵 A 满足 \( A^d = 0 \) 。这称为幂零性质：即存在正整数 k ，使得 \( A^k = 0 \)。

幂零性质又可以推导出 A 的特征值的性质：

假设 A 有非 0 特征根 x 和 \( \lambda \), 那么满足 \( Ax=\lambda x \) 左右两边乘以 \( A^{k-1} \) 得到 \( A^{k}x=\lambda A^{k-1}x = \lambda^{k}x \)

那么可以知道 A 的所有特征值 \( \lambda=0 \)

回到矩阵迹的性质 对一般的方阵 A, \( \sum_{n=0}^{\infty}A^{n} \) 是一个等比数列，如果 A 的最大特征值小于 1, \( A^{n} \) 会随着 n 增大趋于 0 矩阵， 级数是收敛的, 可以写成 \( (I-A)^{-1} \) ，那么

\[ tr(\sum_{n=0}^{\infty}A^{n})=tr((I-A)^{-1})=tr(I)+ tr(\sum_{n=1}^{\infty}A^{n})\]

如果 A 对应的是 DAG, 以上式子最后部分结果就只能等于 d

因此如果 A 对应的是 DAG 那么 \( (I-A)^{-1}=d \) 。反过来也成立

PC 可以通过 partial_correlation 来计算变量之间的独立性

def compute_partial_correlation(samples, i, j, S):
    """
    Compute the partial correlation between variables i and j given the set S of conditioning variables.
    """

    # regression of i on S

    i, j = i - 1, j - 1
    if S == []:
        return np.corrcoef(samples[:, i], samples[:, j])[0, 1]
    S = [x - 1 for x in S]
    reg_i = LinearRegression().fit(samples[:, S], samples[:, i])
    residuals_i = samples[:, i] - reg_i.predict(samples[:, S])
    reg_j = LinearRegression().fit(samples[:, S], samples[:, j])
    residuals_j = samples[:, j] - reg_j.predict(samples[:, S])
    return np.corrcoef(residuals_i, residuals_j)[0, 1]

PC 需要有 causal sufficiency 的假设，且符合 fathfulness 和 markov 假设

FCI(Fast Causal Inference) 则解除了 causal sufficiency 假设，可以作为隐变量发现算法 FCI 输出的不是 CPDAG 而是一种更泛化的图模版，PAG, 能够表示 not 关系，比如 A 不是 B 的祖先

通过枚举所有可能的变量排列，找到与数据生成分布最稀疏的因果图。

• 算法过程：
  1. 遍历所有可能的排列（复杂度为 p!）。
  2. 基于每个排列构造 DAG，通过条件独立性测试决定是否添加边。
  3. 选择边数最少的 DAG。
• 复杂度：
  • 遍历所有排列的复杂度： \( p! \)。
  • 每个排列中检查条件独立性复杂度为 \( O(p^2) \)。
  • 总复杂度为 \( p! \times O(p^2) \)，计算量庞大，难以应用于大规模数据集。

基于 Chickering 序列

定义 5.6：Covered Edge

• 在一个 DAG 中，如果有一条边 \( X_i \to X_j \)，且它是**covered edge**，那么它满足以下条件：
  • \( X_i \) 和 \( X_j \) 的父节点集合相同，或者可以认为 \( X_j \) 的父节点集合等于 \( X_i \) 的父节点集合加上 \( X_i \)。
  • 用符号表示：\( pa_G(X_i) = pa_G(X_j) \) 或者 \( pa_G(X_j) = pa_G(X_i) \cup \{ X_i \} \)。
• Covered edge 的概念非常重要，因为它描述了当边被反转时 DAG 的等价性是否能保持。

引理 5.3：Covered Edge 反转保持 Markov 等价性

• 引理 5.3 提到，如果在 DAG \( G \) 中有一条 covered edge \( X_i \to X_j \)，并将这条边反转得到新的图 \( G' \)，即 \( X_j \to X_i \)，那么 \( G \) 和 \( G' \) 是 Markov 等价的。
• 证明：
  1. 由于图 \( G \) 是有向无环图，因此除了 \( X_i \to X_j \) 这条边外，\( X_i \) 到 \( X_j \) 之间没有其他路径。这意味着将边反转不会产生新的环，\( G' \) 仍然是一个 DAG。
  2. \( G \) 和 \( G' \) 的**骨架**相同，所谓骨架指的是忽略边的方向后图的结构。两个 DAG 的骨架相同是 Markov 等价的一个必要条件。
  3. \( G \) 和 \( G' \) 的**无屏蔽碰撞点（unshielded colliders）**也相同。在 \( G \) 中的碰撞点形式为 \( X_k \to X_i \leftarrow X_j \)，在 \( G' \) 中则可能反过来。但是由于 covered edge 的存在，所有新增的碰撞点实际上都是被“屏蔽”的，因而 \( G \) 和 \( G' \) 仍是等价的。
• 定理 5.3 进一步说明，如果 \( H \) 是 \( G \) 的一个 I-MAP（即 \( H \) 可以表示所有在 \( G \) 中存在的条件独立性关系），那么存在一条从 \( G \) 到 \( H \) 的 Chickering 序列，即通过边的增加或 covered edge 的反转，可以逐步从 \( G \) 转换到 \( H \)。

添加边的条件（不是都满足，而是至少满足以下之一）：

• 添加边必须能够显著提高得分函数（如 BIC、AIC）的值。
• 得分函数衡量模型对数据的适应性及其复杂度。
  • 添加边后必须保持原图的 Markov 等价性。
  • 添加边不能引入新的无屏蔽碰撞点（unshielded colliders），且骨架（skeleton）结构要一致。
• 增加边时必须确保图结构依然是无环的，避免形成回路。
• 添加边应该有合理的因果解释基础，保证新增加的因果关系是符合因果逻辑的。

GES 算法是一个典型

另一种与之相似的级数是指数： \[ e^{A}=\sum_{n=0}^{\infty}\frac{A^{n}}{n!} \]

首先它在任何情况下都是成立的，不对 r(A) 有特别要求，此外即便是直接计算无穷级数的估计值，由于 1/n! 的加权， 数值不太可能溢出。

矩阵指数 e^W 并不是对矩阵 W 的每个元素分别计算指数。在 numpy 中的定义是按位求指数：

import numpy as np
A = np.array([[1,2],[3,4]])
np.e**A

array([[ 2.71828183,  7.3890561 ],
       [20.08553692, 54.59815003]])

它是通过矩阵的泰勒级数展开定义的，即：

\[ e^{W} = I + W + \frac{1}{2!} W^2 + \frac{1}{3!} W^3 + \cdots \]

其导数： \[ \frac{d}{dW}e^{W} = I + \frac{1}{1}W + \frac{1}{2!}W^{2}+\dots = e^{W} \]

其中 \( I \) 是与 \( W \) 维数相同的单位矩阵。计算矩阵指数需要进行矩阵的乘法和求和，而不是逐元素地应用指数函数。

如果矩阵 \( W \) 可对角化，即 \( W = P D P^{-1} \)，其中 \( D \) 是由 \( W \) 的特征值组成的对角矩阵，\( P \) 是由对应特征向量组成的矩阵，那么矩阵指数可以简化为：

\[ e^{W} = P e^{D} P^{-1} \]

其中 \( e^{D} \) 是对角矩阵，其对角元素是 \( D \) 的对角元素的指数。