4. 基于分数的算法(GES算法)：GES算法原理、BIC评分函数、前向搜索与后向剪枝

大家好，今天我们来聊聊GES算法。

说实话，在因果发现这个领域里，GES算是我个人比较偏爱的一个算法。为什么？因为它既不像PC算法那样对条件独立性测试那么敏感，也不像LiNGAM那样对数据分布有严格限制。说白了，它走了一条中间路线——用评分函数来指导搜索，既灵活又相对高效。

4.1 GES算法的核心思想

GES，全称是Greedy Equivalence Search，贪婪等价搜索。名字挺长，但核心思想其实很朴素：

我们不是在找单个DAG，而是在找一组等价的DAG。

你想想看，如果两个DAG结构不同，但它们编码的条件独立性关系完全一样，那它们就是等价的。GES算法聪明的地方在于，它直接在等价类空间里搜索，而不是在单个DAG空间里瞎转悠。

4.2 BIC评分函数

BIC，贝叶斯信息准则。我在项目中用过不少评分函数，BIC算是比较靠谱的一个。

它的公式长这样：

BIC(G|D) = -2 * log P(D|G, θ̂) + d * log n

其中：

• P(D|G, θ̂) 是给定图结构G和最大似然参数θ̂下的数据似然
• d 是自由参数的数量
• n 是样本量

嗯，这里要注意。BIC的第一项是拟合优度，第二项是惩罚项。说白了，就是既要让图能很好地解释数据，又不能太复杂。

对于离散数据，BIC的具体计算会用到条件概率表。假设每个变量有r个取值，每个父节点组合有q种情况，那么：

BIC = Σ_i Σ_j Σ_k N_{ijk} * log(N_{ijk} / N_{ij}) - (d/2) * log(n)

其中N_{ijk}是第i个变量取第k个值且父节点组合为j的样本数。

4.3 前向搜索阶段

前向搜索，说白了就是给图加边。

算法从一个空图开始（没有边），然后每次尝试加一条边，看看BIC评分能不能降低。如果能，就保留这条边，继续加下一条。

但这里有个坑——加边的时候不能形成环。我刚开始做的时候，忘了检查环，结果跑出来的图乱七八糟的。

前向搜索的伪代码大致是这样：

初始化：空图 G
循环：
  对于所有可能的加边操作（添加一条有向边）：
    如果加边后不形成环：
      计算新图的BIC评分
  选择BIC评分降低最多的操作
  如果评分不再降低，停止
返回当前图 G

你可能会问：为什么不一次加多条边？

嗯，这就是贪婪算法的特点——每次只做局部最优的选择。虽然不一定能找到全局最优，但计算效率高很多。

4.4 后向剪枝阶段

后向剪枝，就是删边。

为什么前向搜索加完边还要删？因为前向搜索可能加了一些冗余的边。比如，A→B和B→C已经能解释大部分依赖关系了，但前向搜索可能还会加上A→C，这条边其实是多余的。

后向剪枝的逻辑和前向搜索正好相反：

从当前图 G 开始
循环：
  对于所有可能的删边操作（删除一条有向边）：
    计算新图的BIC评分
  选择BIC评分降低最多的操作
  如果评分不再降低，停止
返回最终图 G

有意思的是，后向剪枝阶段删掉的边，往往就是前向搜索阶段最后加进去的那几条。这说明什么？说明前向搜索越往后，加的边越可能是噪声。

4.5 GES算法的整体流程

把两个阶段串起来，就是完整的GES算法：

1. 初始化：从空图开始
2. 前向搜索：不断加边，直到BIC评分不再降低
3. 后向剪枝：不断删边，直到BIC评分不再降低
4. 输出：最终得到的图结构

下面这张图展示了GES算法的完整流程：

4.6 实际应用中的注意事项

我在实际项目中用GES踩过不少坑，这里分享几个：

还有一个容易被忽略的问题——等价类。GES输出的是一个DAG，但可能存在多个等价的DAG。比如X→Y和Y→X，如果它们对应的条件独立性相同，GES可能随机选一个。所以，别把GES输出的方向当成绝对的因果关系。

4.7 小结

GES算法的核心就三点：

• 用BIC评分衡量图的好坏
• 前向搜索加边，后向剪枝删边
• 在等价类空间里搜索，避免局部最优

说实话，GES不是万能的。但它胜在直观、易用，而且对数据分布的要求不高。如果你刚开始接触因果发现，我建议从GES入手，先跑通流程，再慢慢调参优化。