1 基本概念
信念传播是一类在图结构上进行概率推断的迭代算法。它通过在节点或因子之间传递“消息”，把局部信息逐步汇聚为对全局变量的近似估计。该方法在树形图上可得到精确结果，在含环图上则通常作为高效近似算法使用。由于其计算方式直接、可并行化程度较高，信念传播在概率图模型中占据重要位置。
1.1 定义
信念传播通常指一组基于消息传递的推断规则，用于估计随机变量的边缘分布、最优配置或相关统计量。它的基本单位是消息，即某个节点根据自身局部信息向相邻节点发送的函数或数值向量。随着消息不断迭代更新，网络中的“信念”逐渐形成，因此得名。
1.2 核心思想
其核心思想是局部计算与全局推断之间的递进关系：一个节点只需结合邻域中的信息，就能够更新对自身状态的判断，再把这一判断传递给其他节点。若图结构为树，这种局部汇总不会造成信息回路，因此结果可精确反映整体分布；若图中存在环，消息会重复经过同一结构，从而带来近似性与收敛性问题。
1.3 适用对象
信念传播适用于可分解为局部函数乘积或加和的模型，尤其适合变量之间依赖关系可由图结构清晰表示的情形。
1.3.1 概率图模型
在概率图模型中，变量间的统计依赖关系可通过图来表达，信念传播能够借助这一结构有效完成推断。它常用于处理联合分布难以直接求解但局部条件关系明确的系统。
1.3.2 因子图
因子图将变量与因子分别作为不同类型节点，并用边表示变量参与哪些局部因子。信念传播在此框架中尤其自然，因为消息正是沿着变量与因子之间交替传递的。
1.3.3 马尔可夫随机场
在马尔可夫随机场中，变量的依赖关系通常以无向边与势函数表示。信念传播可利用这些局部势函数近似恢复节点边缘或最可能状态，特别适合稀疏结构。
1.4 主要目标
信念传播的目标并不局限于单一数值，而是涵盖多类推断任务，视具体消息规则而定。
1.4.1 边缘分布估计
其最常见目标是估计每个变量的边缘分布，即在给定已知信息后，求某一变量取各状态的概率。该结果对于不确定性分析非常关键。
1.4.2 最优状态推断
在某些应用中，更关心的是联合配置中概率最高的状态组合。通过相应变体，信念传播可以近似求解最大后验估计问题。
1.4.3 误差控制与近似计算
当精确推断代价过高时，信念传播常作为近似计算工具使用。此时需要关注误差范围、收敛速度以及数值稳定性，以保证结果可用。
2 理论基础
信念传播建立在图论、概率论与优化思想的交叉之上。其形式上是消息更新，实质上与分解、约束传播和变分近似密切相关。
2.1 图论基础
图结构决定了消息传递的路径与复杂度，也影响算法是否能够精确工作。
2.1.1 节点与边
图由节点与边构成，节点可表示随机变量或因子，边则描述变量之间的依赖或参与关系。消息传递本质上是在边上进行的局部信息交换。
2.1.2 树结构与环结构
树结构没有闭合回路，因而信息在传播时不会重复回流，推断过程较为简单。环结构则会使消息多次经过同一子图，带来重复计算与潜在的不稳定性。
2.2 概率论基础
信念传播处理的是带有不确定性的系统，因此离不开概率论中的基本概念。
2.2.1 条件概率
条件概率描述在已知部分信息后某一事件发生的可能性。信念传播中的局部更新，实际上是在不断修正条件概率的估计。
2.2.2 联合分布
联合分布刻画多个变量同时取值的整体概率结构。信念传播通过分解联合分布的因子形式，避免直接处理高维联合空间。
2.2.3 边缘化
边缘化是从联合分布中消去部分变量，得到目标变量分布的过程。信念传播的主要任务之一，就是高效近似这一操作。
2.3 变分推断视角
从变分角度看，信念传播可以理解为在某个可计算的目标函数下寻找近似最优解的过程。
2.3.1 自由能
自由能是衡量近似分布与真实分布差异的重要量。许多信念传播形式可被解释为对某种自由能的迭代优化。
2.3.2 期望一致性
期望一致性强调局部统计量在不同子结构之间应保持协调。广义信念传播常以此为修正原则，使近似结果更符合整体约束。
2.4 动态规划联系
信念传播与动态规划在思想上十分接近，二者都通过递推来整合子问题的解。
2.4.1 消息传递与递推关系
消息可看作递推式中的中间量，先由局部计算生成，再传递给更高层结构。这个过程与动态规划中的“自底向上汇总”非常相似。
2.4.2 树上精确推断
在树上，信念传播等价于动态规划式的精确推断。每条边只需处理一次上行和一次下行信息，便可恢复全局结果。
3 算法机制
信念传播的运行过程通常包括消息定义、更新、迭代和停止判断几个环节。不同变体在形式上有所差异，但基本框架相近。
3.1 消息定义
消息是算法的基本计算单元，通常表示某个节点对邻居所提供的信息摘要。
3.1.1 变量到因子消息
变量到因子消息反映某个变量在排除目标因子后，基于其余邻居信息形成的局部判断。它常由相邻因子传来的信息综合得到。
3.1.2 因子到变量消息
因子到变量消息则表示某个局部约束或势函数对变量状态的影响。该消息通常需要对因子中其他变量进行求和或取最大化处理。
3.2 更新规则
消息更新规则决定了算法到底是在估计概率，还是在寻找最优配置。
3.2.1 标准乘积形式
标准形式下，消息通常由相邻消息的乘积与局部因子共同构成，再进行归一化处理。这一形式适合边缘分布估计。
3.2.2 最大和形式
最大和形式将求和替换为最大化，用于寻找最可能的状态组合。它更关注最优解而非完整分布。
3.2.3 对数域更新
在数值实现中，常把乘法转为加法，改在对数域中更新消息。这样可以减轻下溢问题，也便于处理极小概率。
3.3 迭代过程
信念传播通常不是一步完成，而是通过多轮迭代逼近稳定结果。
3.3.1 初始化
初始化阶段需要为每条消息设定初值。常见做法是使用均匀分布、零向量或依据先验信息给出初始估计。
3.3.2 同步更新
同步更新指在同一轮中先读取旧消息，再统一生成新消息。该方式实现简单，便于分析，但有时收敛速度不如异步更新。
3.3.3 异步更新
异步更新允许某些消息先行刷新，并立即影响后续计算。它在部分场景下更快，但实现上需要更细致地处理更新顺序。
3.4 收敛判定
是否继续迭代，取决于消息变化是否已经足够小，或系统是否已进入稳定状态。
3.4.1 固定点条件
当消息更新前后几乎不再变化时，可视为达到固定点。此时所得信念通常被作为最终近似结果。
3.4.2 停止准则
实际应用中常设定最大迭代次数或误差阈值作为停止准则。这样可避免长时间循环导致计算资源浪费。
3.4.3 数值稳定性
由于消息可能跨越很大数量级，数值稳定性十分重要。常借助归一化、对数变换或截断来降低计算误差。
4 图结构中的表现
信念传播的效果与图结构高度相关，不同拓扑下其精确性、速度和稳定性差异明显。
4.1 树形图
树形图是信念传播最理想的结构。
4.1.1 精确性
在树上，消息不会形成回路，因此每个局部子问题都能被准确整合，最终得到精确边缘分布或最优配置。
4.1.2 线性复杂度
树上推断通常只需沿边进行有限次数的传递，计算量与节点数和边数大致成线性关系，因此非常高效。
4.2 有环图
当图中存在环时，信念传播的结果一般不再严格精确。
4.2.1 近似推断
有环图中常把该算法作为近似工具使用。尽管无法保证完全正确，但在许多实际问题中仍能给出质量较高的估计。
4.2.2 循环消息传播
消息在环中会多次流转，同一信息可能被重复计入，这种现象既可能改善局部一致性，也可能造成偏差累积。
4.2.3 收敛问题
有环结构下，消息可能震荡、停滞或收敛到多个不同固定点之一。实际效果往往依赖图的稀疏程度和参数配置。
4.3 稀疏图
稀疏图是信念传播较为适合的场景之一。
4.3.1 计算优势
由于邻接关系较少，每次消息更新涉及的变量规模有限，因此计算负担较轻，整体效率较高。
4.3.2 局部结构利用
稀疏图中的局部依赖往往更清晰，算法能够更直接地利用局部约束完成推断，减少无关计算。
4.4 密集图
密集图对信念传播并不友好。
4.4.1 计算负担
当节点连接较多时，单次消息计算可能涉及大量变量组合，导致时间和空间开销迅速上升。
4.4.2 近似策略
在密集图上，通常需要采用简化、截断或低秩近似等策略，以降低计算复杂度并保持可用精度。
5 主要变体
围绕基本信念传播，研究者提出了多种变体，以适应不同的目标函数与图结构。
5.1 置信传播
置信传播是信念传播的典型变体之一，常用于循环图中的近似推断。
5.1.1 概率解释
它沿用概率分解的思想，通过局部“置信”来描述变量状态的可能性。尽管在有环图中不一定精确，但仍保留较强的统计解释。
5.1.2 消息形式
其消息通常仍在变量与因子之间传递，只是更新公式可能更适合环结构中的近似一致性条件。
5.2 最大和算法
最大和算法关注的是最优状态而非全部概率质量。
5.2.1 MAP推断
该算法常用于最大后验推断，即寻找使联合概率最大的变量配置。它本质上将求和问题转化为最大化问题。
5.2.2 与最短路径的联系
在某些特殊模型中，最大和更新可与最短路径或动态规划中的代价累积相对应，因此在形式上具有相似性。
5.3 链式与树递推
链式结构和一般树结构上的递推方法，是信念传播最直观的特例。
5.3.1 前向算法
前向算法从起点逐步向后传递信息，常用于序列模型中的累积概率计算。
5.3.2 后向算法
后向算法则从末端反向传播信息，与前向过程配合后，可以得到每个位置的局部后验估计。
5.4 广义信念传播
广义信念传播试图在更复杂的结构上改进标准方法。
5.4.1 区域图
区域图把若干节点或因子合并为较大的计算单元，以增强局部一致性并更好地处理环结构中的相关性。
5.4.2 期望一致性修正
期望一致性修正通过对局部统计量施加额外约束，减少近似误差，使消息更新更接近全局目标。
6 性质与分析
从理论角度看，信念传播的关键问题包括正确性、复杂度、收敛性与稳定性。
6.1 正确性
算法是否正确，取决于图结构以及所采用的更新规则。
6.1.1 树上正确性证明
在树结构下，通常可证明消息传递得到的信念与精确边缘分布一致。这一性质是信念传播最重要的理论基础之一。
6.1.2 近似误差分析
在有环图中，误差一般与环的长度、图的稀疏性和势函数强度有关。误差分析的目标是评估近似结果与真实解之间的偏离程度。
6.2 复杂度
信念传播之所以广受欢迎，与其较好的复杂度表现密切相关。
6.2.1 时间复杂度
时间复杂度主要由每条消息的计算代价和迭代轮数决定。对于结构规整且局部规模不大的图，算法通常较为高效。
6.2.2 空间复杂度
空间开销主要来自消息缓存和中间变量存储。若图较大或状态空间较宽，内存占用会明显上升。
6.3 收敛性
收敛性是信念传播在实际应用中的核心问题之一。
6.3.1 单调性
某些特殊设置下，消息更新可呈现单调变化趋势，这有助于判断算法是否朝稳定方向推进。
6.3.2 多固定点现象
在复杂图中，可能存在多个固定点。不同初始化方式有时会导致算法收敛到不同结果。
6.3.3 不收敛情形
若环路较强或参数设置不当，消息可能持续震荡，难以进入稳定状态。这也是实践中需要重点防范的情形。
6.4 稳定性
稳定性直接影响算法实现的可靠程度。
6.4.1 数值下溢
当概率值极小且连续相乘时，计算结果可能接近机器精度下限，出现下溢现象。
6.4.2 归一化处理
通过对消息进行归一化，可以保持数值范围适中，并减少不同轮次之间的尺度漂移。
7 应用场景
信念传播在多个领域都有成熟用途，尤其适合需要在复杂依赖结构中进行快速推断的任务。
7.1 统计推断
在统计分析中，信念传播可帮助处理含隐变量或复杂依赖的模型。
7.1.1 参数估计辅助
它能够在参数学习过程中提供中间的边缘估计，为最大似然或近似贝叶斯方法提供支持。
7.1.2 隐变量推断
对于不可直接观测的变量，信念传播可估计其后验分布，从而辅助解释数据生成机制。
7.2 机器学习
在机器学习中，该算法常用于结构化模型的推断环节。
7.2.1 图模型学习
在学习图模型参数时，信念传播可作为推断子程序嵌入训练流程，以估计期望值和梯度信息。
7.2.2 结构化预测
对于具有内部关联的输出对象，如序列、网格或树结构，信念传播可用于求解预测结果及其置信度。
7.3 计算机视觉
视觉任务中的局部一致性问题与图模型天然契合，因此信念传播应用广泛。
7.3.1 图像分割
在图像分割中，像素或超像素可视为图节点，算法通过邻域约束帮助判断区域归属。
7.3.2 去噪与标注
它也可用于去噪、边界平滑和语义标注，使局部观测与整体结构更协调。
7.4 自然语言处理
语言序列和句法结构常可表示为图或链式模型，因此适合采用消息传递推断。
7.4.1 词性标注
在词性标注中，信念传播可估计每个词属于各类词性的概率，并利用上下文关系提高准确度。
7.4.2 句法分析
在句法分析中，词与词之间的依存关系可形成图结构，消息传递有助于寻找更合理的句法配置。
7.5 编码理论
信念传播在纠错译码中非常重要，尤其适合稀疏校验结构。
7.5.1 纠错码译码
译码问题可被表示为变量与校验约束之间的图模型，信念传播能在此框架下高效估计比特状态。
7.5.2 LDPC码
低密度奇偶校验码的校验图稀疏，正好契合信念传播的优势，因此该算法是其经典译码方法之一。
8 历史与发展
信念传播并非孤立出现，而是多条研究路径逐渐汇合的结果。
8.1 早期思想来源
其思想基础可追溯到概率推断、递推计算与图结构分析的早期研究。
8.1.1 马尔可夫链与动态规划
马尔可夫链提供了局部依赖建模的直观方式，动态规划则展示了如何通过递推处理复杂问题，这两者都对信念传播形成了重要影响。
8.1.2 概率图模型发展
随着概率图模型体系逐渐完善，研究者开始系统化地研究图上的局部消息如何重建全局分布，信念传播由此成为核心工具之一。
8.2 算法扩展
在基础方法之外，许多扩展版本被提出，以适应更复杂的任务需求。
8.2.1 近似推断方法
围绕大规模与有环图场景，出现了多种近似推断方法，它们与信念传播在思想上相通，但更强调可计算性。
8.2.2 变分方法融合
将变分优化与消息传递结合后，算法可在保持局部更新形式的同时，获得更明确的目标函数解释。
8.3 现代研究方向
近年来，信念传播研究不断向大规模、异构和学习驱动的场景延伸。
8.3.1 大规模分布式推断
面对海量节点与边的系统，分布式实现成为重要方向，重点在于并行更新、通信开销与容错性。
8.3.2 深度学习结合
信念传播也被用于与神经网络结合，作为可解释的推断模块或训练中的结构约束组件。
9 相关概念
信念传播与若干经典概念密切相关，但侧重点并不相同。
9.1 与贝叶斯网络的关系
贝叶斯网络是有向图概率模型，强调条件依赖的方向性；信念传播则是其常见推断手段之一，尤其在树状或近似条件下表现良好。
9.2 与马尔可夫随机场的关系
马尔可夫随机场采用无向图描述变量关系，信念传播可直接在其局部势函数上运行，因此常被视为自然匹配的推断算法。
9.3 与消息传递算法的关系
消息传递是更广义的概念，涵盖多种在图上交换局部信息的算法。信念传播可以看作其中最具代表性的概率推断形式之一。
9.4 与变分推断的关系
变分推断通过优化近似分布来逼近真实后验，信念传播在许多形式下可被解释为变分框架中的特殊迭代过程，两者在理论上存在深层联系。