GES评分函数：BIC如何引导搜索

可视化演示

因果发现任务

主厨要反推菜谱，但他面对的不是一张白纸，而是堆成山的顾客评价单。每张单子上记录着“这道菜用了哪些食材、客人反馈如何”——却唯独没有写烹饪步骤。主厨的目标很朴素：找出一个“配方蓝图”，让每个味道特征都能被更基础的食材选择所解释。在统计学里，这个“配方蓝图”叫作有向无环图（DAG）：每个节点是一个变量，每条有向边表示一个变量直接影响另一个变量。

因果发现（Causal Discovery）要解决的，正是从纯粹的观测数据中学习这样一张DAG。它不要求你去做随机实验，而是从成千上万条“顾客评价单”中反复比对：当食材A出现时，味道B是否系统性地跟着变化？当同时控制住食材C的影响后，A与B的关联是否消失？这些规律被编码成一张图，而图背后隐含着一个重要假设——联合分布可以被分解成每个变量在给定其父节点条件下的乘积。

这道分解式是整个因果发现大厦的地基。它告诉我们：只要找到每个变量“真正的父节点”，整张图的联合分布就能被完整刻画。剩下的问题只有一个——如何从浩瀚的候选图中找到这组父节点？这就需要一个聪明的“试菜过程”。

GES搜索框架

既然要找的菜谱可能有无穷多种配方组合，主厨不可能把所有配方都试一遍。聪明的做法是：从一份最简单的“白水煮菜”开始，每次只调整一种食材——加一味、换一味、撤一味，然后立刻请品鉴团打分，保留让分数上升的改动。这就是贪婪搜索的基本精神：每次只做局部最优的调整，一步步爬向更高的评分。

GES，全称贪婪等价搜索（Greedy Equivalence Search），正是把这种“试菜直觉”搬到了因果图上。它的独特之处在于，搜索的并不是所有DAG组成的空间，而是“等价类空间”。什么是等价类？想象两份配方——先加糖后加醋、先加醋后加糖——最后端出来的菜味道完全一样。对顾客来说，这两份配方是“不可区分的”；对统计模型来说，它们的联合分布也完全相同、评分一模一样。这样的DAG归为一类，称为马尔可夫等价类。

与其在成千上万个“味道相同”的DAG之间反复横跳，GES干脆只在一个等价类的“代表”上做文章。每次加边或删边，都自动在等价类层面更新代表图，搜索效率大幅提升。这一步设计的关键在于：在等价类空间里，每一类只需要评估一次评分，而不是对每个同类的DAG分别打分。

BIC评分原理

现在评分表登场。主厨的品鉴表上写着这样一行字：“得分 = 美味程度 − 复杂度罚分”。一道菜做得再好吃，如果配方要用五十种食材、每一步都很玄学、没人能复刻，也很难拿到高分；反之，一道菜简单到只有盐和胡椒，却平淡无奇，同样不合格。BIC评分函数（贝叶斯信息准则）就是这张品鉴表的数学化身。

BIC由两部分组成。第一部分是极大对数似然 $\hat{\ell}(\hat{\theta})$，它衡量当前DAG对应的概率模型在数据上的拟合程度——“这份配方解释顾客反馈的能力”；第二部分是复杂度惩罚项 $-\frac{d}{2}\ln N$，其中 $d$ 是模型自由参数个数、$N$ 是样本量。每多一条边，通常意味着条件概率表里多出若干参数，惩罚随之增大。BIC就像一位挑剔的美食评论家：既要求味道精准，又要求配方简洁。

有了这张评分表，GES的每一步试菜都变得有据可依。但BIC只给出了“打分规则”，真正的搜索还需要一个决策机制来决定每一步该动哪条边——这就是下一节的“评分引导”。

评分引导机制

品鉴团评分之后，主厨要做的事很朴素：比较改动前后的分数差。如果加一味蒜让菜从82分涨到85分，这步改动就值得保留；如果加了之后反而掉到79分，就立刻撤回。这个分数差，记作 $\Delta\text{BIC}$，正是GES导航仪的“油门踏板”。

在数学上，GES每次考虑一个候选操作（比如添加 $X\to Y$ 这条边），都计算新图的BIC减去旧图的BIC。注意一个巧妙之处：因为BIC可以按节点分解，一条边只影响目标节点的局部得分，所以增量计算只需重算受影响的局部项，代价很小。当增量为正时，说明这次改动的“拟合收益”超过了“复杂度代价”；当增量为负时，说明这条边纯属画蛇添足。

GES在每一步都会枚举所有合法的单边操作，计算各自的 $\Delta\text{BIC}$，然后贪婪地选择增量最大（且为正）的那个执行。这就像主厨把十种候选调味方案摆上桌，逐一让品鉴团试吃打分，只选得分涨幅最大的那一款。局部决策虽然只看眼前一步，却在宏观上形成了一条持续上升的搜索轨迹。

搜索流程细节

主厨的试菜节奏分为两个截然不同的阶段。第一阶段叫“大胆加料”：他几乎不加节制地尝试往菜里加各种食材——只要能提升品鉴分就保留，直到再怎么加分数都不动了。第二阶段叫“冷静收尾”：他开始审视已经加进去的食材，果断删掉那些贡献微薄、纯属增加配方复杂度的配料，直到再删任何一样都会掉分。GES的完整搜索过程，正是这两个阶段的精确复刻。

前向阶段（Forward Phase）从空图出发，反复执行“添加一条边、计算 $\Delta\text{BIC}$”的循环：如果存在让评分上升的加边操作，就选增益最大者执行；当所有合法加边都无法再提升评分时，前向阶段停止。后向阶段（Backward Phase）则反过来，尝试删除已有边，同样每一步选择增益最大的删边操作，直到任何删边都无法提升评分。两个阶段都收敛时，GES输出当前等价类作为最终结果。

为什么先加后删而不是一步到位？因为前向阶段容易被“边太多”误导——某些边单独看有增益，组合在一起却互相冗余。后向阶段正是用来清洗这些冗余的：它允许GES在评分丘陵上更从容地移动，最终停在BIC的局部（理想情况下是全局）最优点。这套“先加法后减法”的节奏，与主厨先大胆试味、再精简配方的职业习惯如出一辙。

G ← 空图（等价类表示）# 前向阶段：贪婪添加边while 存在合法加边使 ΔBIC > 0:    选 ΔBIC 最大的加边操作执行# 后向阶段：贪婪删除边while 存在合法删边使 ΔBIC > 0:    选 ΔBIC 最大的删边操作执行return G

等价类处理

主厨发现了一个耐人寻味的现象：他试出了两份配方，一份先炒糖再下鸡翅，一份先煎鸡翅再淋糖汁，端上桌客人完全吃不出差别。他意识到，自己没必要在“哪份配方更正统”上浪费时间——反正它们的味道（分布）一模一样。这就是马尔可夫等价类的精髓：两个DAG如果拥有相同的骨架和相同的V结构，它们表达的联合分布完全一致，互为等价类成员。

骨架是忽略方向后的无向图；V结构是指 $X\to Z\leftarrow Y$ 这种“两个变量同时指向一个共同后代、且它们之间没有边”的局部模式。对因果发现来说，等价类内的方向差异属于“数据无法告诉你”的信息。GES因此聪明地选择在等价类空间中搜索：搜索的每一步都以CPDAG（部分有向无环图）为代表——方向在所有等价类成员中一致的边画实线箭头，方向不一致的边保留为无向线段。

这个设计带来两个红利。第一，搜索空间大幅缩小：原本要在指数级的DAG群中挑挑拣拣，现在只在一类一类的“配方组”中穿行；第二，评分更加稳健：既然同类配方评分相同，GES就不会因为随机选择某个成员而在评分上产生无意义波动。最终输出的CPDAG如实告诉使用者：“这些边的方向数据已经确定，那些边的方向还需要领域知识或干预实验来裁定。”

方法优劣评价

回看主厨的整套方法论，它既让人惊喜，也暗藏风险。惊喜在于效率：主厨没有把世界上的所有配方都试一遍，而是靠“每次局部最优”的贪心策略快速逼近一个高分方案，这在菜谱空间极其庞大时几乎是唯一可行的路；样本充足、数据满足忠实性假设时，GES还有漂亮的渐进一致性——样本越多，越能收敛到真实的因果等价类。

风险同样不容忽视。贪心搜索的本质决定了它可能止步于局部最优：某一步的边删除虽然单独看会掉分，却可能为后续更强的结构调整铺路——但贪心策略永远不会迈出那“暂时的倒退”。此外，GES的统计保证依赖几个关键假设：数据忠实于真实图（没有额外的条件独立巧合）、不存在隐藏的混杂变量、样本量足够大。现实数据中这些假设常常被违背，输出图也就只能视为“候选菜谱”而非金科玉律。

不过瑕不掩瑜。在众多因果发现算法中，GES凭借“评分+贪心”这一组合，在可扩展性与准确性之间取得了极佳的平衡，成为评分式因果发现的标杆。PC等约束式方法依赖独立性检验的误差累积，而GES把一切统一到BIC这把评分尺上，决策更连贯、结果更可解释。理解了这套框架，你就掌握了因果发现的主流思维范式。

AI 应用场景

Python 演示

import numpy as np  def _group_counts(sub):    """统计子矩阵各取值组合的出现次数，返回字典映射"""    uniq, counts = np.unique(sub, axis=0, return_counts=True)    return {tuple(row): c for row, c in zip(uniq, counts)}  class BICScorer:    """BIC评分器：对任意父集组合计算局部BIC得分"""     def __init__(self, data):        self.data = data        self.n, self.m = data.shape        self.states = [len(np.unique(data[:, j])) for j in range(self.m)]        self.cache = {}     def local_ll(self, var, parents):        """对数似然：sum n(x,pa) * log(n(x,pa) / n(pa))"""        joint = _group_counts(self.data[:, list(parents) + [var]])        if parents:            pa_map = _group_counts(self.data[:, list(parents)])        else:            pa_map = {(): self.n}        ll = 0.0        for key, c in joint.items():            pa_key = key[:-1]            ll += c * np.log(c / pa_map[pa_key])        return ll     def num_params(self, var, parents):        """自由参数个数 = 父组合数 * (状态数 - 1)"""        if parents:            pa_count = len(_group_counts(self.data[:, list(parents)]))        else:            pa_count = 1        return pa_count * (self.states[var] - 1)     def local_bic(self, var, parents):        """BIC局部得分 = 对数似然 - (参数个数/2) * ln(N)"""        key = (var, tuple(parents))        if key not in self.cache:            ll = self.local_ll(var, parents)            d = self.num_params(var, parents)            self.cache[key] = ll - (d / 2) * np.log(self.n)        return self.cache[key]     def total_bic(self, parents):        """整图BIC = 各节点局部得分之和"""        return sum(self.local_bic(v, parents[v]) for v in range(self.m))  def has_path(parents, start, target):    """判断有向图中start能否沿有向边到达target"""    children = [[] for _ in range(len(parents))]    for v, ps in enumerate(parents):        for p in ps:            children[p].append(v)    stack = [start]    seen = set()    while stack:        cur = stack.pop()        if cur == target:            return True        if cur in seen:            continue        seen.add(cur)        stack.extend(children[cur])    return False  def greedy_search(data):    """贪心加边搜索：每次选择令BIC提升最大的合法操作"""    scorer = BICScorer(data)    m = data.shape[1]    parents = [[] for _ in range(m)]    score = scorer.total_bic(parents)     for _ in range(30):        best_delta = 1e-12        best_cand = None        for x in range(m):            for y in range(m):                if x == y or x in parents[y] or y in parents[x]:                    continue                if has_path(parents, y, x):                    continue                cand = [p[:] for p in parents]                cand[y].append(x)                delta = scorer.total_bic(cand) - score                if delta > best_delta:                    best_delta = delta                    best_cand = cand        if best_cand is None:            break        parents = best_cand        score += best_delta    return parents, score  if __name__ == '__main__':    np.random.seed(42)    n = 5000    x0 = np.random.binomial(1, 0.5, n)    p1 = np.clip(0.5 + 0.3 * x0, 0.05, 0.95)    x1 = np.random.binomial(1, p1)    p2 = np.clip(0.1 + 0.3 * x0 + 0.4 * x1, 0.05, 0.95)    x2 = np.random.binomial(1, p2)    x3 = np.random.binomial(1, 0.3, n)    data = np.column_stack([x0, x1, x2, x3])     parents, score = greedy_search(data)    names = ['X0', 'X1', 'X2', 'X3']    for v in range(4):        pa = [names[p] for p in parents[v]]        print(names[v] + ' 的父节点: ' + (', '.join(pa) if pa else '无'))

1. class BICScorer:评分器封装了BIC的全部数学逻辑：局部对数似然、参数计数、局部得分缓存。
2. joint = _group_counts(self.data[:, list(parents) + [var]])统计“父组合＋变量取值”的联合计数，这是计算对数似然的第一手素材。
3. ll += c * np.log(c / pa_map[pa_key])累加每个父组合下的条件对数似然，实现BIC的拟合优度项。
4. return sum(self.local_bic(v, parents[v]) for v in range(self.m))整图BIC等于各节点局部得分之和，这是GES能快速评估边操作增量的结构基础。
5. def has_path(parents, start, target):环检测工具：若加边 x→y 前，y已经能到达x，则新边必然成环，该操作非法。
6. delta = scorer.total_bic(cand) - score计算候选操作的 ΔBIC 增量，这是GES每一步决策的导航仪表。
7. if delta > best_delta: best_delta = delta; best_cand = cand贪婪选择：在所有合法加边操作中挑出评分增益最大者。

常见误区

面试题