Huajishe Notes

2-GES算法

9 min read

GES算法 (Greedy Equivalence Search)

定位: GES是一种评分式因果发现算法,通过在DAG等价类空间中进行贪婪搜索,优化贝叶斯信息准则(BIC)或等效评分函数来发现因果结构。

前置知识: PC算法、贝叶斯网络、马尔可夫等价类、信息论基础(互信息、似然)

核心直觉

核心直觉: 若能定义一个评分函数来衡量任意DAG与数据的拟合程度,就可以在所有可能的DAG空间中搜索最优结构。GES通过在等价类空间中搜索避免了组合爆炸,同时保证找到局部最优解。

评分式方法将因果发现形式化为优化问题:在所有DAG中搜索最大化评分函数的结构。GES的巧妙之处在于它搜索CPDAG空间(等价类)而非单个DAG空间,大幅降低了搜索复杂度。

数学推导

1. 评分函数的基本要求

一个有效的DAG评分函数 应满足:

  • 等价类一致性: 同一等价类中的所有DAG得分相同
  • 分数可分解:
  • 似然优先: 倾向于更好拟合数据的结构

2. BIC评分 (高斯线性模型)

对于高斯线性数据,观测似然为:

其中为样本协方差矩阵,为样本量。

BIC评分的分解形式:

其中:

  • : 在DAG 下的最大似然估计参数
  • : 自由参数总数
  • : 复杂度惩罚项

可分解性: 令,其中:

其中为父节点配置的样本数,为该配置下的估计方差。

对于线性高斯模型,单个节点的BIC贡献为:

3. BDeu评分 (离散数据)

对于离散数据,使用贝叶斯 Dirichlet 等效评分 (BDeu):

其中:

  • 为先验伪计数
  • 为父节点配置数
  • 为的可能取值数
  • 为等效样本大小(ESS)

4. GES搜索操作

GES在等价类空间中搜索,定义三种基本操作:

操作前向添加反向删除
单边添加 添加边 (若尚未连接)删除现存边
父节点添加为添加新父节点从的父节点中删除
边翻转 反转为 反转为

等价类转换: 操作在CPDAG上执行,确保不违反有向无环性。

5. GES算法流程

输入: 数据D, 评分函数Score, 最大父节点数k_max
输出: 最优CPDAG G*

初始化: G_0 = 无边图 (empty DAG)

# 前向阶段
for t = 0, 1, 2, ...:
    找到所有合法的单步操作 O = {op1, op2, ...}
    对每个操作计算 score(G_t + op) - score(G_t)
    选择使评分增加最大的操作 op*
    if score(G_t + op*) > score(G_t):
        G_{t+1} = apply(op*, G_t)
    else:
        break

# 后向阶段
repeat:
    找到所有合法的单步删除操作
    选择使评分增加的操作
    (注: 后向阶段从当前图开始,删除边以改善评分)

注意: 实际实现中后向阶段从空图或前向终点开始,逐步删除边寻找更优解。

训练与估计

计算细节

  • 评分差计算: 由于评分可分解,只需计算受影响节点的评分变化
  • 合法操作判断: 需要维护当前CPDAG的相邻结构
  • 局部最大值: GES可能陷入局部最优,但在等价类空间中更平滑

时间复杂度

  • 搜索空间: 相比的DAG空间,等价类空间约为此值的
  • 每次迭代: 个候选操作
  • 总复杂度: 取决于达到局部最优的迭代次数,通常

推理/干预/反事实

从GES结果进行干预

GES输出的CPDAG允许进行干预分析:

  • 对于确定方向的边: do演算直接适用
  • 对于双向边(非v-structure): 需要在每个等价DAG中分别计算,然后汇总

do演算应用

给定CPDAG中的一条边:

这正是do演算的基本规则。

优点与局限

优点

  1. 理论基础: 有严格理论保证(在无限样本下收敛到马尔可夫等价类)
  2. 评分一致性: BIC/BDeu满足等价类一致性要求
  3. 可分解性: 使得搜索高效,避免重复计算
  4. 全局最优: 在贪婪框架下能到达局部最优

局限

  1. 局部最大值: 贪婪搜索不能保证全局最优
  2. 搜索空间限制: 通常限制最大父节点数,可能遗漏复杂结构
  3. 计算成本: 评分计算随节点数增加而增加
  4. 参数敏感: ESS等参数影响BDeu评分结果

与其他笔记的连接

  • 前置: PC算法基础 → 本笔记GES(评分式vs约束式)
  • 延伸: NOTEARS(连续优化) → DAG约束优化
  • 对比: 约束式(PC) vs 评分式(GES) 对比见”约束式与评分式方法”
  • 评测: 因果发现评测指标用于验证GES输出的CPDAG质量

可复现性说明

关键参数

参数建议值说明
3-5最大父节点数,控制搜索复杂度
(BDeu)1-10等效样本大小
评分函数BIC(连续) / BDeu(离散)取决于数据分布

常用实现

  • Python: causal-learn库中GES类
  • R: bnlearn包的hc(hill climbing)算法类似GES
  • Matlab: BNT工具箱

评分差计算示例

def score_diff_add_edge(G, X, Y, data, score_type='bic'):
    """计算添加边 X -> Y 的评分变化"""
    old_score = compute_node_score(G, Y, data, score_type)
    G_new = add_edge(G, X, Y)
    new_score = compute_node_score(G_new, Y, data, score_type)
    return new_score - old_score
 
def compute_node_score(G, node, data, score_type='bic'):
    """计算节点的条件评分"""
    parents = get_parents(G, node)
    if len(parents) == 0:
        return -n/2 * log(var(data[:, node]))
    else:
        # 回归残差方差
        residuals = regression_residuals(data, node, parents)
        return -n/2 * log(var(residuals))

章节总结

  • GES通过在DAG等价类空间中进行贪婪搜索来优化BIC/BDeu评分
  • 评分函数必须满足等价类一致性,可分解性两大要求
  • BIC评分中,复杂度惩罚项为,防止过拟合
  • BDeu评分使用Dirichlet先验,ESS参数控制先验强度
  • 前向阶段从空图开始逐步添加边,后向阶段删除边改善评分
  • GES的搜索空间约为DAG空间的,大幅降低复杂度
  • 可分解性使评分差计算高效,只需重新计算受影响节点
  • 贪婪搜索保证局部最优,但可能陷入局部最大值
  • 最大父节点数限制搜索范围,是关键超参数
  • 收敛性理论: 在无限样本下GES收敛到正确的马尔可夫等价类

关键词: GES算法, BIC评分, BDeu评分, 贪婪搜索, 等价类空间, 可分解性, 局部最优, 评分函数

Graph View