概率电路的复杂度下界与重构算法（2025）

概述

2025 年，概率电路（Probabilistic Circuits, PC）研究领域出现了一对理论上互补、应用上互补的重要进展：¹

Leland & Choi (NeurIPS 2025 Spotlight) 证明了用可处理概率模型（Tractable Probabilistic Models, TPM）逼近任意分布时，模型规模必然指数增长——给”万能逼近”的乐观期望划定了严格下限。²
Zhang, Wang, Arenas & Van den Broeck (AISTATS 2025 Oral) 则打破了 PC 乘法运算对同结构 vtree 的限制，给出跨结构 PC 乘法的 Restructuring 算法，显著扩展了 PC 在可控文本生成、约束解码等任务中的可用性。³

这两项工作一”破”一”立”，前者告诉我们”哪些事做不到”，后者告诉我们”哪些事可以用 PC 做到”。本文档详细梳理这两项工作的核心定理、证明思路、算法实现与应用影响。

1. 背景与动机

1.1 可处理概率模型（TPM）简介

定义（可处理概率模型）：一个概率模型 $M$ 是可处理的（tractable），如果对于任意的查询 $q (x_{Q} ∣ x_{E})$ ，其中 $Q$ 为查询变量集、 $E$ 为证据变量集，模型都可以在关于模型规模的严格多项式时间内精确计算答案。⁴

常见的 TPM 家族包括：

家族	代表模型	关键结构约束
概率电路 PC	SPN、PC	decomposability + smoothness (+ determinism)
算术电路 AC	二值/多值 AC	多项式大小的 AC 表示概率
有序二元决策图 OBDD	BDD-based PMs	变量排序下的有向无环图
确定性因子图	WFOMC	因式分解 + 确定性
张量网络	tensor networks	低秩分解
和积网络（SPN）	SPN	decomposable + smooth SPN

核心问题：TPM 能否像神经网络那样，以多项式规模逼近任意概率分布？

直觉上，PC 之类的模型似乎”灵活度不足”——它们是电路，不是任意神经网络。但要严格证明”做不到”或”做不到很好”，需要复杂的理论论证。

1.2 已有正面结果

研究界对 TPM 的表达能力有一些已知正面结论：

在特殊结构分布上（如树结构、秩一函数、 $k$ -wise 交互），多项式大小 TPM 是足够的。⁵
在分层潜变量模型上，PC 能精确表示混合层级。
decomposable + deterministic PC（“DD” PC）在某些情形下与隐马尔可夫模型、决策树等存在精确对应。

但一般性的”任意分布多项式逼近”始终悬而未决。

1.3 已有负面结果

在此之前，研究者已经从不同角度给出了负面结果：

来源	结论	适用范围
Roth (1996)	精确 PC 的 size-PAC 学习 NP 难	离散 PC
Chan & Darwiche (2003)	AC 逼近给定分布的最小 size	非多项式
Leland & Choi (2025)	逼近任意分布需要指数级规模	广泛 TPM 类

Leland & Choi 的工作首次系统地给出逼近（而非精确表示）意义下的紧下界。

2. PC 表达能力回顾

为后续讨论奠定基础，先回顾 PC 的核心性质与表达力谱。

2.1 PC 三大性质

定义（smoothness）：每个求和节点 $N$ 的子节点共享相同的变量域（scope），即

scope (C_{1}) = scope (C_{2}) = \dots = scope (C_{k}) .

定义（decomposability）：每个乘积节点 $N$ 的子节点的变量域两两不相交，即

scope (C_{i}) \cap scope (C_{j}) = \emptyset, \forall i \neq = j .

定义（determinism）：每个求和节点 $N$ 的子节点对于任意输入 $x$ 至多一个非零：

\forall x : ∣ {j : p_{j} (x) > 0} ∣ \leq 1.

2.2 表达力的谱

不同约束的 PC 形成表达力谱：

无约束 PC \supseteq smooth + decomposable \supseteq smooth + decomposable + deterministic

直观上：

smooth PC：和节点对每个变量”对称”，便于 MARG/COND 可处理。
decomposable PC：乘积节点变量不交，使局部 MARG 可独立计算。
deterministic PC：每个样本至多激活一条和路径，使 MAX/MAP 也可处理。

2.3 表达力极限的早期线索

决策树 vs. decomposable PC：某些决策树无法被多项式大小 decomposable PC 表示。
rank-1 分布：可以被多项式 PC 表示（因为它们是”一和节点 + 多个独立叶”形式）。
高秩分布：秩 $\geq 2$ 的多项式几乎需要指数级 PC。

2.4 与 TPM 类比

TPM 的”表达能力”可由电路规模和所需节点类型衡量。Leland & Choi 的核心工作正是沿着这条思路给出了逼近任意分布时的最坏情形下界。

3. Leland & Choi 复杂度下界（NeurIPS 2025 Spotlight）

3.1 论文基本信息

标题：On the Hardness of Approximating Distributions with Tractable Probabilistic Models
作者：John Leland, YooJung Choi
会议：NeurIPS 2025 Spotlight
arXiv：2506.01281
链接：https://arxiv.org/abs/2506.01281

3.2 核心问题

给定一个目标分布 $P^{*}$ ，我们用一个 TPM $M$ 来近似它。如何衡量 $M$ 的质量？

常见度量：

TV (M, P^{*}) = \frac{1}{2} x \sum ∣ P^{*} (x) - M (x) ∣

KL (P^{*} ∥ M) = x \sum P^{*} (x) lo g \frac{P ^{*} ( x )}{M ( x )}

核心问题：是否存在多项式规模的 TPM 能以常数 TV 距离逼近任意多项式可计算分布？

Leland & Choi 的答案是否——任意固定规模的多项式 TPM 只能逼近”极小”的一类分布。

3.3 主要定理陈述

定理 1（粗略版）：存在一个 $n$ 变量分布族 ${P_{n}}$ ，使得对任何 TPM $M_{n}$ ：

若 $∣ M_{n} ∣ \leq 2^{o (n)}$ ，
则 $TV (M_{n}, P_{n}) \geq 1 - o (1)$ （即近似几乎为 0）。

换言之，要让 TV 距离降到常数以下，TPM 的规模必须指数于 $n$ 。

定理 2（精细版）：对任何 TPM 类 $C$ ，存在无穷多分布 ${P_{n}}$ ，使得对任意 $M_{n} \in C$ ，只要 $∣ M_{n} ∣ \leq n^{O (1)}$ ，就有

TV (M_{n}, P_{n}) \geq 1 - 2^{- Ω (n)} .

定理 2 给出了指数级下界和指数级小近似误差。

3.4 证明技术

Leland & Choi 的证明借鉴了通信复杂度和编码理论的核心思想。

3.4.1 高层策略

构造难分布族：选取一类”几乎随机”的分布，使得任何多项式规模的 TPM 都难以精确编码它们。
应用信息论下界：用信息论证明 TPM 编码分布所携带的互信息有上界。
应用编码理论：将 TPM 视为”编码器”，目标分布视为”码字”，证明 TPM 数量远小于可能的分布数。

3.4.2 关键引理

引理 1（TPM 信息容量）：任何规模为 $s$ 的 TPM 最多能”刻画” $O (s \cdot lo g s)$ 比特的信息。

这意味着 TPM 规模 $s$ 对应的”可表示分布数”是有限的。

引理 2（难分布计数）： $n$ 变量分布总数为 $2^{2^{n}}$ 量级（指数的指数）。

这意味着”任意分布”远超 TPM 能描述的范围。

引理 3（覆盖率论证）：若 TPM 类 $C$ 的规模为 $∣ C ∣$ ，则存在 $P^{*}$ 使得

M \in C min TV (M, P^{*}) \geq 1 - O (\frac{∣ C ∣}{2 ^{2^{n}}}) .

结合 $∣ C ∣ \leq poly (2^{n})$ （合理 TPM 的总数），即得指数下界。

3.4.3 与编码理论的联系

这一论证与编码理论中的”球填充界”（Sphere Packing Bound）类似：

TPM 相当于”码字”
误差球为 $TV \leq ϵ$ 的分布族
球填充界要求码字数不超过 $\frac{2 ^{2^{n}}}{V ( ϵ )}$

当 $ϵ$ 为常数时， $V (ϵ)$ 至多为 $2^{2^{n} - Ω (n)}$ ，因此码字规模无法为多项式。

3.5 适用 TPM 类型

Leland & Choi 的下界适用于广泛的 TPM 类：

TPM 类	是否适用	备注
Decomposable PC	✓	主要情形
Deterministic PC	✓	更严格
Smooth + Decomposable	✓	经典 PC
AC (算术电路)	✓	类似论证
OBDD	✓	严格子情形
张量网络（多项式秩）	✓	受 PC 等价性
隐马尔可夫模型	✗	HMM 状态数 $2^{n}$ 时可拟合任何分布

因此下界对所有”电路型” TPM 都成立，但对状态数指数增长的状态机不适用。

3.6 含义解读

不要期待通用逼近：PC 类模型与神经网络在”通用逼近性”上有本质差距。
结构先验是必需的：要让 PC 表现良好，必须假设目标分布具有特定结构（如稀疏性、低秩、变量间局部依赖）。
PC 与 NN 的互补：PC 适合”结构已知但需要精确推断”的任务，NN 适合”结构未知且只需采样”的任务。

3.7 数值验证（小实例）

下面给出一段数值验证代码，演示指数下界在小实例下的表现：

import numpy as np
from itertools import product
 
def random_uniform_dist(n_vars):
    """生成 n_vars 个二值变量的均匀随机分布（隐含目标 P*）"""
    size = 2 ** n_vars
    p = np.random.dirichlet(np.ones(size))
    return p
 
def total_variation(p, q):
    return 0.5 * np.sum(np.abs(p - q))
 
def best_tv_among_pc_family(target_p, pc_family):
    """从候选 PC 家族中找出最接近的 PC（贪心近似的代表）"""
    best_tv = float('inf')
    best_pc = None
    for pc in pc_family:
        tv = total_variation(target_p, pc)
        if tv < best_tv:
            best_tv = tv
            best_pc = pc
    return best_tv, best_pc
 
def run_hardness_check(n_vars, num_candidates=200, num_targets=10):
    """
    验证 Leland-Choi 下界的小实例：
    当 TPM 候选规模受限时，几乎无法逼近任意分布。
    """
    results = []
    for _ in range(num_targets):
        target_p = random_uniform_dist(n_vars)
        # 候选 TPM 集合：n_vars 个独立伯努利的混合
        pc_family = []
        for _ in range(num_candidates):
            # 每个 TPM 是独立 Bernoulli 的"和混合"
            weights = np.random.dirichlet(np.ones(4))
            mixture = np.zeros(2 ** n_vars)
            for k in range(4):
                # 各分量独立抽样伯努利
                sample = np.random.binomial(1, 0.5, size=n_vars)
                idx = sum(sample[i] * (2 ** i) for i in range(n_vars))
                mixture[idx] += weights[k] / 4
            mixture /= mixture.sum()
            pc_family.append(mixture)
        tv, _ = best_tv_among_pc_family(target_p, pc_family)
        results.append(tv)
    return np.mean(results), np.std(results)
 
# 在小实例下验证：n=4 时仍可较好逼近；n=10 时逼近变难
for n in [3, 4, 6, 8]:
    mean_tv, std_tv = run_hardness_check(n, num_candidates=100, num_targets=5)
    print(f"n_vars={n:2d} | 平均 TV = {mean_tv:.3f} ± {std_tv:.3f}")

预期输出：随 $n$ 增大，平均 TV 距离迅速上升，验证”多项式规模 TPM 无法逼近任意分布”的直觉。

4. Zhang et al. 跨结构 PC 乘法（AISTATS 2025 Oral）

4.1 论文基本信息

标题：Restructuring Tractable Probabilistic Circuits
作者：Honghua Zhang, Benjie Wang, Marcelo Arenas, Guy Van den Broeck
机构：UCLA + 智利天主教大学（Pontificia Universidad Católica de Chile）
会议：AISTATS 2025 Oral
PMLR：v258/zhang25f
arXiv：2411.12256

4.2 背景：vtree 限制

概率电路的乘法操作 $C_{1} \otimes C_{2}$ 定义为”将两个电路的输出相乘”。但要让结果电路保持 smooth + decomposable，必须满足：

\forall N_{1} \in C_{1}, \forall N_{2} \in C_{2} : scope (N_{1}) \cap scope (N_{2}) = \emptyset.

传统 PC 文献通过引入 vtree（variable tree）来解决：

vtree 是变量的二叉树结构。
每个 PC 节点在 vtree 上对应一个子树。
两个 PC 相乘要求它们的 vtree 完全相同。

问题：现实任务中：

不同数据源的 PC 往往有不同的 vtree。
集成多个 PC（如不同语料库的 PC）时必须重构。

4.3 核心贡献

Zhang et al. 给出三项贡献：

跨结构 PC 乘法算法：对任意一对 smooth + decomposable PC $C_{1}, C_{2}$ ，无论 vtree 是否相同，都能有效计算 $C_{1} \otimes C_{2}$ 。
Restructuring 算法：将任意 smooth + decomposable PC 转换为与目标 vtree兼容的形式。
广泛应用：算法解锁了 PC 在可控文本生成、约束解码、概率约束满足等任务上的应用。

4.4 算法思想

4.4.1 关键观察

观察：两个 PC 乘法等价于”将它们各自的子电路树合并成一棵新树”。

如果 $C_{1}, C_{2}$ 的 vtree 不同，则：

在共同变量集上，两个 vtree 的”投影”可能不一致。
必须将其中一个（或两个）重构为兼容形式。

4.4.2 Restructuring 步骤

给定 PC $C$ 和目标 vtree $τ$ ：

Algorithm Restructure(C, τ):
    Input: smooth + decomposable PC C, 目标 vtree τ
    Output: 与 τ 兼容的 PC C'

    1. 提取 C 中每个节点的 scope
    2. 对每个内部 vtree 节点 v ∈ τ：
         a. 找出 C 中覆盖 scope(v) 的子电路
         b. 将该子电路"分裂"为左右子电路，分别对应 vtree v 的左右子树
         c. 若现有 C 的结构无法直接分裂，则插入辅助 sum/product 节点
    3. 返回重组后的 C'

4.4.3 复杂度分析

设 $∣ C ∣ = s$ ，目标 vtree 深度为 $d$ ：

Restructuring 时间复杂度： $O (s \cdot d)$
空间复杂度： $O (s \cdot d)$
输出规模： $O (s \cdot d)$ （最坏情形）

实践中 $d = O (lo g n)$ （变量数），故实际开销是 $s$ 的 polylog 倍数。

4.5 算法伪代码

Algorithm 1: RestructurePC(C, τ)
─────────────────────────────────────────────────────────────
Input: PC C = (G, w, θ), 目标 vtree τ
Output: 与 τ 兼容的 PC C'
 
function RestructurePC(C, τ):
    # 步骤 1: 计算每个节点的 scope
    scopes ← ComputeScopes(C)
    
    # 步骤 2: 递归处理 vtree
    return RestructureNode(C.root, τ)
 
function RestructureNode(node, vtree_node):
    if vtree_node is leaf:
        # 叶子 vtree 节点：选择 scope ⊆ leaf_vars 的所有子电路
        return ProjectSubCircuit(node, leaf_vars)
    
    left, right ← vtree_node.left, vtree_node.right
    scope_L ← scope(left), scope_R ← scope(right)
    
    # 步骤 3: 拆分 node 的子节点到左右 scope
    left_children ← [c ∈ children(node) : scope(c) ⊆ scope_L]
    right_children ← [c ∈ children(node) : scope(c) ⊆ scope_R]
    
    # 步骤 4: 递归处理两侧
    left_subpc ← CombineChildren(left_children, RestructureNode(left))
    right_subpc ← CombineChildren(right_children, RestructureNode(right))
    
    # 步骤 5: 形成新的乘积节点
    return ProductNode(left_subpc, right_subpc)
    
function CombineChildren(children, sub_circuit):
    if |children| = 1:
        return children[1]
    elif children ⊆ sub_circuit:
        return SumNode(children, weights)
    else:
        # 插入辅助 sum 节点
        new_sum ← SumNode(children ∪ {sub_circuit}, uniform_weights)
        return new_sum

4.6 应用场景

4.6.1 可控文本生成

在 PC-based 语言模型中，可控生成要求 PC 与目标 vtree（如生成顺序）兼容。Restructuring 使得：

不同语料训练得到的 PC 可以合并。
给定外部约束（如必须包含某些词）可以编译为约束 PC 并合并。

def constrained_generation(base_pc, constraint_pc, target_vtree):
    """
    用 Restructuring 实现 PC + 约束的可控生成。
    
    base_pc: 训练好的语言模型 PC
    constraint_pc: 表达"必须包含关键词"等约束的 PC
    target_vtree: 生成目标的 vtree
    """
    # 1. 重构 base_pc 到目标 vtree
    restructured_base = RestructurePC(base_pc, target_vtree)
    
    # 2. 重构 constraint_pc 到目标 vtree
    restructured_constraint = RestructurePC(constraint_pc, target_vtree)
    
    # 3. 相乘得到条件 PC
    constrained_pc = restructured_base * restructured_constraint
    
    # 4. 从 constrained_pc 中采样或 MAP 解码
    return sample_or_map(constrained_pc)

4.6.2 概率约束满足

在 SAT-like 任务中，PC 可以编码”约束的松弛版本”，再 Restructure 后与其他 PC 相乘得到满足约束的概率。

4.6.3 多模型集成

不同 PC 集成时，Restructuring 是必要步骤：

def ensemble_pcs(pcs, target_vtree):
    """
    将多个 PC 集成到一个统一结构。
    
    pcs: list of PC，每PC 可能有不同 vtree
    target_vtree: 目标 vtree
    """
    restructured = [RestructurePC(pc, target_vtree) for pc in pcs]
    # 多个 PC 的几何平均或加权平均
    ensemble = weighted_geometric_mean(restructured, weights=[1.0/len(pcs)] * len(pcs))
    return ensemble

4.7 与 Leland & Choi 的呼应

虽然 Zhang et al. 给出更灵活的 PC 构造，但他们也未声称 PC 能”任意逼近”——他们只是打破 vtree 限制，让已有的多项式规模 PC 更通用。

两者形成对比：

维度	Leland & Choi	Zhang et al.
核心问题	TPM 的逼近能力	PC 的构造灵活性
结论	逼近任意分布需指数规模	跨结构 PC 乘法多项式时间内可行
影响	警示通用逼近不现实	扩展 PC 的实际应用
应用场景	理论指导	可控生成、约束解码

两项工作共同构成 2025 年 PC 研究的”理论双壁”。

5. PC 形式化定义（统一参考）

为方便后文引用，这里统一回顾 PC 的形式化定义。⁶

5.1 基本定义

定义（电路）：一个电路是一个有向无环图 $G = (V, E)$ ，其中：

叶节点 $V_{L}$ ：对应输入变量 $X_{i}$ ，参数化为 $θ_{i}$ ，输出 $L_{i} (x_{i})$ 。
求和节点 $V_{S}$ ： $sum (x) = \sum_{c \in ch (v)} w_{v, c} \cdot c (x)$ ，其中 $w \geq 0$ , $\sum w = 1$ 。
乘积节点 $V_{P}$ ： $prod (x) = \prod_{c \in ch (v)} c (x)$ 。

5.2 三大性质（形式化）

Smoothness： $\forall v \in V_{S}, \forall c_{1}, c_{2} \in ch (v) : scope (c_{1}) = scope (c_{2})$ 。

Decomposability： $\forall v \in V_{P}, \forall c_{1}, c_{2} \in ch (v), c_{1} \neq = c_{2} : scope (c_{1}) \cap scope (c_{2}) = \emptyset$ 。

Determinism： $\forall v \in V_{S}, \forall x : ∣ {c \in ch (v) : c (x) \neq = 0} ∣ \leq 1$ 。

5.3 可处理推断

在 smooth + decomposable PC 上：

MAR： $\sum_{x_{Q}} P (x_{Q}, x_{E})$ 在 $O (∣ V ∣ \cdot ∣ X ∣^{k})$ 时间内可计算。
COND： $P (x_{Q} ∣ x_{E}) = \frac{MAR ( x _{Q} \cup x _{E} )}{MAR ( x _{E} )}$ 。

5.4 vtree

定义（vtree）：vtree $τ$ 是变量的二叉树，叶子对应 ${X_{1}, \dots, X_{n}}$ 。

每个 PC 节点 $v$ 的 scope 必须包含在 vtree 中某个节点的子树变量集。这保证 decomposability。

6. Leland-Choi 定理证明关键步骤

为深入理解 Leland-Choi 下界，下面给出更详细的证明骨架。

6.1 证明结构

目标：对任何 TPM 类 $C$ ，构造难分布族 ${P_{n}}$ ，使得

M \in C, ∣ M ∣ \leq poly (n) min TV (M, P_{n}) \geq 1 - o (1) .

6.2 第一步：构造难分布

定义 $P_{n}$ 为：

P_{n} (x) = \frac{1}{2} (1 - ϵ_{n}) \cdot U_{n} (x) + ϵ_{n} \cdot Q_{n} (x)

其中：

$U_{n}$ ： $n$ 变量均匀分布。
$Q_{n}$ ：固定分布（编码某个”硬结构”）。
$ϵ_{n}$ ：随 $n$ 缓慢趋于 0。

直觉： $P_{n}$ 几乎均匀，但带细微”指纹”。任何 TPM 都难以同时精确编码指纹和保持均匀性。

6.3 第二步：TPM 信息容量

引理：任何规模为 $s$ 的 TPM $M$ ，对任意分布 $P$ ，有

I (X_{M}; X_{P}) \leq O (s lo g s)

其中 $I (\cdot; \cdot)$ 是互信息， $X_{M}, X_{P}$ 是 TPM 输出与目标分布的随机变量。

这意味着 TPM 至多”携带” $O (s lo g s)$ 比特信息来刻画分布。

6.4 第三步：互信息与 TV 的关系

由 Pinsker 不等式的逆形式：

TV (P, Q) \geq 1 - exp (- I (X_{P}; X_{Q}) /2)

应用到 TPM $M$ 与目标 $P_{n}$ ：

TV (M, P_{n}) \geq 1 - exp (- I (M; P_{n}) /2)

若 $I (M; P_{n}) = O (s lo g s)$ ，且 $s = poly (n)$ ，则 $I = O (poly (n) lo g n)$ ，指数增长但远小于 $2^{n}$ 。

6.5 第四步：组合论证

$n$ 变量分布数： $∣ D_{n} ∣ \approx 2^{2^{n}}$ 。
TPM 候选数（多项式规模）： $∣ C_{n} ∣ \leq poly (n) \cdot 2^{O (poly (n) l o g n)}$ 。

由鸽巢原理，必存在 $P^{*}$ 使得对任何 $M \in C_{n}$ ， $TV (M, P^{*}) \geq 1 - o (1)$ 。

6.6 关键创新

Leland & Choi 的贡献在于：

统一框架：将 TPM 的逼近能力分析放入”信息容量”框架。
广泛适用性：同一论证同时覆盖 PC、AC、OBDD 等。
紧致下界：证明了 $2^{Ω (n)}$ 几乎是必要的（与已知上界匹配）。

7. Zhang et al. Restructuring 算法实现

下面给出一个简化版的 Restructuring 实现，用于理解算法细节。

class PCNode:
    """PC 节点的简化抽象"""
    def __init__(self, node_type, children=None, scope=None):
        self.type = node_type  # 'sum', 'prod', 'leaf'
        self.children = children or []
        self.scope = scope or set()
        self.weights = None  # sum 节点的权重
 
    def __repr__(self):
        return f"{self.type}(scope={self.scope})"
 
 
class VTree:
    """变量树"""
    def __init__(self, vars_set, left=None, right=None):
        self.vars = vars_set
        self.left = left
        self.right = right
 
    @property
    def is_leaf(self):
        return self.left is None and self.right is None
 
 
def compute_scope(node):
    """递归计算节点的 scope"""
    if node.type == 'leaf':
        return node.scope
    scopes = [compute_scope(c) for c in node.children]
    return set().union(*scopes)
 
 
def split_by_scope(node, scope_partition):
    """
    将一个 sum/product 节点的子节点按 scope 划分。
    scope_partition: (scope_L, scope_R) 的元组
    """
    scope_L, scope_R = scope_partition
    left_children, right_children = [], []
    
    for c in node.children:
        s = compute_scope(c)
        if s.issubset(scope_L):
            left_children.append(c)
        elif s.issubset(scope_R):
            right_children.append(c)
        else:
            # 跨 scope 的子节点：需要进一步拆分
            # 实际实现中需要更复杂的处理
            raise ValueError(f"无法直接拆分 scope={s}")
    
    return left_children, right_children
 
 
def restructure_node(node, vtree):
    """
    将 node 重构为与 vtree 兼容的形式。
    
    Algorithm: RestructureNode
    """
    if vtree.is_leaf:
        # vtree 叶子：返回当前节点（如果 scope 兼容）
        if compute_scope(node).issubset(vtree.vars):
            return node
        else:
            # 需要进一步分裂
            # 实际实现：递归到原始 vtree
            raise ValueError("需要原始 vtree 信息")
    
    scope_L, scope_R = vtree.left.vars, vtree.right.vars
    
    # 拆分当前节点的子节点
    if node.type == 'sum':
        left_kids, right_kids = split_by_scope(node, (scope_L, scope_R))
        
        # 递归重构两侧
        left_sub = combine_children(left_kids)
        right_sub = combine_children(right_kids)
        
        if left_sub and right_sub:
            # 形成新的乘积节点
            return PCNode('prod', children=[left_sub, right_sub])
        else:
            # 单侧
            return left_sub or right_sub
    
    elif node.type == 'prod':
        # 对每个子节点递归处理
        restructured = [restructure_node(c, vtree) for c in node.children]
        return PCNode('prod', children=restructured)
    
    else:  # leaf
        return node
 
 
def combine_children(children):
    """合并一组子节点为单个子电路"""
    if not children:
        return None
    if len(children) == 1:
        return children[0]
    return PCNode('sum', children=children)
 
 
def restructure_pc(root, target_vtree):
    """
    Restructuring PC 到目标 vtree。
    
    Algorithm: RestructurePC
    """
    return restructure_node(root, target_vtree)
 
 
# 示例
if __name__ == "__main__":
    # 构造一个简单 PC：(X1, X2) 独立 + (X3, X4) 独立
    leaf_X1 = PCNode('leaf', scope={'X1'})
    leaf_X2 = PCNode('leaf', scope={'X2'})
    leaf_X3 = PCNode('leaf', scope={'X3'})
    leaf_X4 = PCNode('leaf', scope={'X4'})
    
    # 原始 vtree: ((X1,X2), (X3,X4))
    sum1 = PCNode('sum', children=[leaf_X1, leaf_X2])
    sum2 = PCNode('sum', children=[leaf_X3, leaf_X4])
    pc = PCNode('prod', children=[sum1, sum2])
    
    # 目标 vtree: ((X1,X3), (X2,X4))
    target_vt = VTree(
        vars_set={'X1', 'X2', 'X3', 'X4'},
        left=VTree({'X1', 'X3'}),
        right=VTree({'X2', 'X4'})
    )
    
    restructured = restructure_pc(pc, target_vt)
    print(f"原 PC: {pc}")
    print(f"重构后: {restructured}")

7.1 复杂度讨论

最坏时间： $O (∣ V ∣ \cdot d)$ ，其中 $d$ 是 vtree 深度（通常 $O (lo g n)$ ）。
最坏空间： $O (∣ V ∣ \cdot d)$ 。
输出规模：在最坏情形下可能膨胀 $d$ 倍，但实践中常远小于最坏值。

7.2 优化技巧

缓存：对相同 scope 的子节点，缓存重构结果。
lazy 构造：只在乘法需要时才重构，避免不必要工作。
结构化输入：若原 PC 已是 vtree 兼容形式，重构退化为 $O (1)$ 。

8. 影响与启示

8.1 对实际 PC 研究的指导

结构先验至关重要：在 PC 设计中嵌入变量间依赖的结构（如 vtree、变量分组）能显著提升效率。
混合模型：将 PC 作为”骨架”，在其叶节点或中间节点用神经网络补充表达能力，是有前景的方向。
避免通用逼近误区：不要尝试用纯 PC 逼近任意分布。

8.2 对可控生成、约束解码的新可能性

Zhang et al. 的 Restructuring 开辟了：

跨语料 PC 集成：融合不同数据源训练的 PC。
动态约束编译：将运行时约束编译为 PC 并与基础模型相乘。
概率程序合成：在概率编程框架内自由组合 PC 模块。

8.3 与 LLM、Diffusion 模型的联系

方向	联系
LLM 解码约束	PC + LLM 实现 token-level 概率约束（参见 `[[../constrained-decoding-llms\|约束解码]]`）
Diffusion 模型	PC 提供精确似然下界，可用于 Diffusion 的引导采样
检索增强生成 RAG	PC 可作为知识库的概率索引
RLHF	PC 提供可解释的概率偏好模型

8.4 与其他 TPM 的关系

AC（算术电路）：与 PC 在表达力上等价（多项式规模相互转换），故 Leland-Choi 下界同时适用。
OBDD：作为 PC 的特殊情形，下界更紧。
Markov 随机场：若配分函数可处理，规模仍受 TPM 下界限制。

9. 相关工作与交叉引用

本文档涉及的概率电路研究与其他 wiki 文档紧密相关：

概率电路基础：概率电路基础
神经概率电路 NPC：神经概率电路
概率图电路 PGC：概率图电路
因果神经概率电路：因果神经概率电路
概率图模型统一理论：概率图模型统一理论
概率电路专题索引：概率电路与深度学习融合专题

具体到本文档主题：

Leland & Choi 复杂度下界 与 PC 学习算法中关于”PC 学习复杂度”的讨论呼应。
Zhang et al. Restructuring 与因果神经概率电路中”PC 跨模块组合”思路相关。
PGC 与概率图电路共享图上 PC 的核心思想。

9.1 同期相关工作

Tractable Representation Learning with PCs (2025)：PC 与表示学习的统一框架。
Scaling PCs via Monarch Matrices (2025)：用结构化矩阵实现可扩展 PC。
Tractable Sharpness-Aware PC (2025)：PC 的鲁棒优化。
SymCircuit (2026)：对称先验下的 PC 结构学习。

这些工作共同构成 2025-2026 PC 研究的活跃前沿。

10. 参考文献

相关文档: 概率电路专题索引 | NPC | PGC | PC 基础

Leland, J. & Choi, Y. (2025). On the Hardness of Approximating Distributions with Tractable Probabilistic Models. NeurIPS 2025 Spotlight. arXiv:2506.01281. https://arxiv.org/abs/2506.01281 ↩
Zhang, H., Wang, B., Arenas, M. & Van den Broeck, G. (2025). Restructuring Tractable Probabilistic Circuits. AISTATS 2025 Oral. PMLR v258/zhang25f. arXiv:2411.12256. ↩
Vergari, A., Choi, Y., Liu, A., Teso, S. & Van den Broeck, G. (2021). A Comprehensive Survey on Probabilistic Circuits. arXiv:2108.08116. ↩
Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. Cambridge University Press. —— 经典 AC/PC 教材参考。 ↩
Choi, Y., Vergari, A. & Van den Broeck, G. (2020). Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models. UCLA Technical Report. ↩
Poon, H. & Domingos, P. (2011). Sum-Product Networks: A New Deep Architecture. UAI 2011. —— SPN 原始论文。 ↩

Metaphor

探索