Huajishe Notes

3-约束式与评分式方法

10 min read

约束式与评分式方法 (Constraint-based vs Score-based Methods)

定位: 约束式与评分式方法是因果发现的两大主流范式。约束式通过条件独立检验推断结构,评分式通过优化评分函数搜索结构,两者各有优劣且互补。

前置知识: PC算法、分数式方法(BIC/BDeu)、条件独立概念、马尔可夫等价类

核心直觉

核心直觉: 约束式方法将因果结构推断问题转化为一系列条件独立检验问题,而评分式方法将同一问题转化为在离散结构空间中的优化问题。前者利用统计检验的局部性质,后者利用评分函数的全局性质。

约束式方法的核心假设是:真实因果结构编码了变量间的条件独立关系。评分式方法的核心假设是:最优结构应该同时具有良好的拟合度和简洁性(Occam’s razor)。

数学推导

1. 约束式方法的理论基础

马尔可夫条件与忠诚性共同保证条件独立与因果结构的双射:

在中和在给定后无直接边

完备性: 在一定正则条件下,所有条件独立关系都可以通过统计检验发现(PC算法)。

2. 评分式方法的理论基础

评分函数需要在似然性和复杂度间权衡:

其中为复杂度惩罚系数。

等价类一致性要求:若(同一等价类),则。

3. 约束式方法的失败情况

情况1: 样本量不足

当样本量不足时,条件独立检验功效下降:

拒绝

低功效导致假阴性(删除存在的边)。

情况2: 违背忠诚性假设

若但无直接边(如由对撞结构产生),会导致错误删除边。

情况3: 高维稀疏性

当变量数接近样本量时,条件集搜索空间过大,统计不稳定。

4. 评分式方法的失败情况

情况1: 局部最大值

贪婪搜索可能陷入局部最优,错过全局最优结构。

情况2: 评分函数选择不当

错误的数据类型假设(如对离散数据使用BIC for Gaussian)会导致结构错误。

情况3: 参数敏感性

BDeu的ESS参数等对结果影响显著。

5. FCI: 扩展到隐藏变量

FCI(Fast Causal Inference)算法扩展PC算法处理隐藏变量:

核心思想:

  • 使用sepset区分直接因果连接和经由隐藏变量的伪连接
  • 在骨架阶段之后,识别可能含潜伏父母的节点
  • 输出部分骨架(可能边)和确定的方向边

数学框架:

定义为可能分离和的最小节点集。FCI识别:

可能由隐藏变量导致

约束式与评分式对比表

维度约束式(PC)评分式(GES)
基本思路CI检验发现结构评分优化搜索结构
理论基础马尔可夫+忠诚性评分一致性+可分解
输出CPDAGCPDAG
计算复杂度近似
样本需求中等(检验功效)较高(评分精确估计)
参数假设无(非参数CI检验)有(BIC/BDeu假设)
局部最大值无有
隐藏变量FCI处理需要扩展
高维性能较差(k限制)较差(搜索爆炸)
可解释性直接(检验路径)间接(评分增益)

混合方法

MMHC算法

混合极大爬山(Max-Min Hill Climbing):

  1. 骨架阶段: 使用MMPC(Max-Min Parents Children)发现相邻结构
  2. 定向阶段: 使用贝叶斯评分进行贪婪搜索定向边

混合评分函数

定义混合评分:

其中控制约束和评分的权重。

训练与估计

方法选择指南

场景推荐方法原因
小样本()PC(非参数CI)无参数假设
大样本()GES评分更精确
高维()混合/MMHC平衡效率和精度
离散数据BDeu评分自然处理类别变量
含隐藏变量FCI专门处理confounders
时序数据PCMCI时序扩展

推理/干预/反事实

干预推理

无论约束式还是评分式,输出的CPDAG都支持do演算:

在CPDAG中,方向确定的边可直接应用;方向不确定的边需要考虑所有等价情况。

反事实推理

反事实需要完全定向的DAG:

  1. 从CPDAG选择一个代表性DAG
  2. 使用结构方程模型(SEM)定义函数形式
  3. 计算反事实查询

优点与局限

约束式优点

  1. 无需参数假设: 非参数CI检验适用于任意分布
  2. 理论基础清晰: 马尔可夫+忠诚性保证完备性
  3. 计算效率: 无需迭代评分计算

约束式局限

  1. 高维灾难: 条件集指数增长
  2. 检验多重校正: 大量CI检验需校正显著性
  3. 忠诚性敏感: 违背假设导致错误

评分式优点

  1. 全局搜索: 考虑整体结构而非局部检验
  2. 避免多重检验: 单一评分优化问题
  3. 自然处理噪声: 评分函数建模观测不确定性

评分式局限

  1. 参数假设: 依赖特定的评分函数形式
  2. 局部最优: 贪婪搜索不保证全局最优
  3. 计算密集: 大量评分计算

与其他笔记的连接

  • 约束式代表: PC算法 → FCI(隐藏变量扩展)
  • 评分式代表: GES算法 → NOTEARS(连续优化)
  • 延伸: 约束式+评分式 → DAG约束优化(GraN-DAG)
  • 评测: 因果发现评测指标比较两类方法性能

可复现性说明

实验设计

def compare_methods(data, true_dag, methods=['pc', 'ges', 'fci']):
    """比较约束式和评分式方法"""
    results = {}
    for method in methods:
        if method == 'pc':
            est = PC_algorithm(data, alpha=0.05)
        elif method == 'ges':
            est = GES(data, max_k=3, score='bic')
        elif method == 'fci':
            est = FCI(data, alpha=0.05)
        results[method] = {
            'shd': structural_hamming_distance(est, true_dag),
            'sid': structural_interventional_distance(est, true_dag),
            'cpdag_accuracy': cpdag_exact_match(est, true_dag)
        }
    return results

关键参数选择

方法关键参数默认值
PC, max_cond_size0.05, 3
GES, score_type3, ‘bic’
FCI, max_cond_size0.05, 3

章节总结

  • 约束式方法通过条件独立检验推断结构,评分式方法通过评分函数优化搜索结构
  • 约束式依赖马尔可夫+忠诚性假设,评分式依赖评分一致性假设
  • 约束式在样本量不足、违背忠诚性、高维情况下可能失败
  • 评分式在陷入局部最优、评分选择不当、参数敏感时可能失败
  • FCI通过扩展sepset概念处理隐藏变量,是约束式的重要扩展
  • 混合方法结合两类方法优势,如MMHC使用约束式骨架+评分式定向
  • 两类方法输出均为CPDAG,都支持do演算和干预分析
  • 方法选择应根据数据规模、变量维度、数据类型、是否有隐藏变量来决定
  • 计算复杂度上,两类方法都随最大父节点数指数增长
  • 评测指标SHD/SID用于量化两类方法的结构估计误差

关键词: 约束式方法, 评分式方法, PC算法, GES算法, FCI, 混合方法, 马尔可夫等价类, 条件独立检验

Graph View