Bayesian Inference with Structured Signal: Static Replica Symmetry Breaking on the Nishimori Line in the Planted Spin Glass

问题定义

本文研究了信号具有内部相关性的贝叶斯推断问题，这挑战了信号分量是独立同分布（i.i.d.）的标准假设。作者专注于一个极简且在解析上可处理的模型：**植入自旋玻璃（planted spin glass）**在随机正则图上的模型。

在该模型中：

1. 信号（先验）： 配置 $s \in \{+1, -1\}^N$ 是从定义在随机 $d$ 正则图上的均匀伊辛模型（Ising model）的玻尔兹曼分布中采样的，其耦合常数 $\kappa$ 定义了信号的结构。此耦合 $\kappa$ 即为信号结构的参数。
2. 观测（似然）： 噪声观测 $J = \{J_{ij}\}$ 在图的边上生成。每条边以概率 $\rho$ 报告自旋 $s_i s_j$ 的对齐情况，以概率 $1-\rho$ 报告相反情况。这由信号强度 $\beta = \frac{1}{2} \ln(\frac{\rho}{1-\rho})$ 进行参数化。
3. 目标： 利用噪声耦合 $J$ 通过后验分布 $P(s|J)$ 重构植入信号 $s$，该后验分布对应于一个具有有效耦合 $\kappa + \beta J_{ij}$ 的无序伊辛模型。

本研究在**贝叶斯最优设置（Nishimori 线）**下进行，即推断参数与生成参数（$\kappa$ 和 $\beta$）相匹配。性能通过估计量与真实信号之间的重叠度（overlap）来衡量，分析区分了信息论极限与算法可行性（特别是信念传播算法 BP）。

方法论

作者利用统计物理工具，特别是空腔方法（cavity method）和复制理论（replica theory），来分析该问题的热力学极限。

• 空腔方程： 他们推导并求解了用于后验分布的空腔方程。
  • 对于**复制对称（RS）**相，他们使用标准的群体动力学（population dynamics）来求解 RS 空腔方程。
  • 对于**复制对称破缺（RSB）**相，他们利用了 1 步 RSB (1RSB) 形式。由于求解带有“分布之上的分布”的完整 1RSB 方程非常复杂，他们专注于 Parisi 参数 $x=1$。这一选择简化了方程，使其可以通过群体动力学进行数值求解。
• 相检测：
  • 信息论极限： 通过“不可能”（顺磁）解的稳定性以及竞争解之间的自由熵比较来确定。
  • 算法性能： 通过在有限规模实例（$N=10^4$）上运行信念传播（BP）进行探测，并采用两种初始化策略：“知情”（使用真实信号初始化）和“不知情”（使用随机初始化或先验不动点初始化）。
  • 静态 RSB 识别： 通过复杂度（complexity）（亚稳态数量的对数）进行检测。在 $x=1$ 时复杂度为负，表明进入了凝聚（静态 RSB）相，此时吉布斯测度分解为数量为亚指数级的占主导地位的簇。

核心贡献与结果

论文展示了一个取决于信号结构 $\kappa$ 和信号强度 $\beta$ 的综合相图，揭示了基于先验相的三个不同机制：

1. 顺磁先验 ($\kappa_{rsb} \le \kappa \le \kappa_c$)

• 结构的影响： 在此机制下，先验具有消失的磁化强度。引入结构（$\kappa \neq 0$）促进了推断。
• 阈值： 实现信息论恢复所需的临界信号强度 $\beta_c(\kappa)$ 比无结构情况（$\kappa=0$）更低。
• 算法行为： 从“不可能”相到“容易”相的转变是连续的。信念传播在容易相中达到了信息论最优性能。不存在计算-统计间隙；只要在信息论上是可能的，问题就是“容易”的。

2. 铁磁先验 ($\kappa > \kappa_c$)

• 结构的影响： 先验集中在两个具有非零磁化强度的状态上。因此，仅基于先验的平凡估计器即使在没有观测的情况下也能实现与信号的非零重叠。
• 阈值： 相关阈值为 $\beta_p(\kappa) = \kappa$。
  • 当 $\beta \le \kappa$ 时，后验保持在铁磁相，观测值除了先验之外不提供额外信息；最优估计器与基于先验的估计器相同。
  • 当 $\beta > \kappa$ 时，观测允许基于后验的估计器严格优于基于先验的估计器。
• 算法行为： 问题在算法上仍然是容易的；BP 收敛于最优解。

3. 静态 RSB 先验 ($\kappa < \kappa_{rsb}$)

• 结构的影响： 先验本身处于玻璃态、静态 RSB 相。这一机制产生了最重要的发现。
• Nishimori 线上的静态 RSB： 作者识别出一个临界阈值 $\beta_{rsb}(\kappa)$，在此处后验发生转变：
  • 高 $\beta$ ($\beta > \beta_{rsb}$)： 后验为复制对称（容易相）。观测足够强，能够选定植入态及其全局翻转。
  • 低 $\beta$ ($\beta < \beta_{rsb}$)： 后验进入静态 RSB 相。
• RSB 相的意义：
  • 这是在贝叶斯最优推断问题中出现静态 RSB 相于 Nishimori 线上的罕见案例。通常认为 Nishimori 线不存在静态 RSB 的论据（依赖于可分离先验）在此失效，因为这里的先验是不可分离且相关的。
  • 算法难度： 数值模拟表明该区域表现为一个困难相（hard phase）。随着 $\beta$ 降低，BP 收敛性恶化，且基于后验的估计器表现得比基于先验的估计器更差。
  • 热力学观测量： 虽然 $x=1$ 解通过（负复杂度）检测到了该相的开启，但它无法提供凝聚相内的正确热力学观测量（重叠度），因为正确的描述需要 $x < 1$。然而，$x=1$ 解暗示了一种情形：热力学占主导的状态与信号的重叠为零，而亚占主导（亚稳态）的含信息状态依然存在。

意义与主张

本文声称证明了信号先验中的相关性可以从根本上改变贝叶斯推断的景观，导致在标准 i.i.d. 设置中未观察到的现象：

1. 有益 vs. 有害的结构： 取决于先验的相位，结构既可以降低重构阈值（顺磁机制），也可以通过诱导玻璃行为（静态 RSB 机制）阻碍算法性能。
2. Nishimori 线上的静态 RSB： 该工作为“贝叶斯最优性意味着不存在玻璃态、静态 RSB 相”的猜想提供了一个具体的反例。作者将此归因于植入信号中已存在的“强且非平凡的相关性”，这些相关性在观测较弱时会持续存在于后验中。
3. 算法极限： 研究强调，即使在贝叶斯最优设置下，存在结构化先验也会创造出计算-统计间隙，使得高效算法（如 BP）无法达到信息论极限，特别是在先验处于静态 RSB 相时。

作者对静态 RSB 相本身的表征保持谦逊，指出目前的 $x=1$ 分析虽然允许检测到转变，但无法提供完整的热力学描述。他们建议，若要获得完整的描述，需要求解完整的 $x < 1$ 时的 1RSB 方程。