1 基本概念
1.1 定义与核心思想
置信传播是一类在图模型上进行概率推理的算法。它将整体推断任务拆分为局部计算，再通过节点之间反复交换“消息”，逐步逼近变量的边缘分布或最优赋值。其核心思想是：复杂系统的全局信息可以由局部约束与邻域关系迭代汇聚而成。
在树状结构中，这种局部到全局的传递能够直接得到精确结果；在一般含环图中，则通常作为近似方法使用。由于形式统一、实现灵活，置信传播常被视为图模型推理中的基础工具之一。
1.2 发展背景
置信传播的发展与概率图模型、信息论和统计物理中的消息传递思想密切相关。早期研究主要来自通信编码与误差纠正领域，随后逐渐扩展到人工智能、机器学习和物理系统分析等方向。
随着因子图等表示方式的普及，置信传播的表达更为清晰，也更便于在不同类型的问题中复用。此后，它不仅成为经典推理算法，也影响了许多近似优化与分布式计算方法。
1.3 适用问题类型
置信传播适用于具有局部依赖结构的问题。只要目标可以写成若干局部函数或约束的组合，并且变量之间存在图结构联系，就可能借助该算法进行推理。
1.3.1 边缘概率推理
边缘概率推理关注的是单个变量或少数变量在给定其他信息后的概率分布。置信传播可通过累积邻域消息，估计每个变量的边缘边际，从而为不确定性分析提供依据。
1.3.2 最优状态估计
在某些任务中，目标不是完整分布，而是最可能的系统状态。此时可使用最大积形式的置信传播来搜索近似的最大后验解，常用于状态识别、路径选择和组合优化。
1.3.3 约束满足问题
当问题主要由一组局部约束构成时，置信传播也可用于判断可行性或寻找满足约束的赋值。此类应用常见于调度、匹配、编码译码以及离散优化场景。
2 图模型基础
2.1 概率图模型
概率图模型用图结构表达随机变量之间的依赖关系。节点通常表示变量，边或因子则描述变量之间的条件关系或联合约束。它的优势在于把复杂联合分布拆解为可管理的局部形式。
2.1.1 贝叶斯网络
贝叶斯网络是一类有向图模型，强调条件依赖与因果式结构。变量之间通过有向边连接，联合分布可分解为各节点在父节点条件下的概率乘积。置信传播可在某些变换后用于这类模型的推理。
2.1.2 马尔可夫随机场
马尔可夫随机场采用无向图表示变量间的相互作用，更适合描述对称关系和局部约束。其联合分布通常写成若干团势函数的乘积，是置信传播的重要应用对象之一。
2.2 因子图表示
因子图是一种将变量与局部函数分开表示的二部图结构。它把复杂模型拆成变量节点和因子节点两类，从而使消息传递规则更直观，也更便于统一描述不同模型。
2.2.1 变量节点
变量节点表示待推理的随机变量或决策变量。它接收来自相邻因子的消息，并将汇总后的信息再反馈出去，以便在图中逐步传播局部约束。
2.2.2 因子节点
因子节点对应局部概率项、约束项或代价项。它根据与之相连的变量状态计算输出消息，反映该局部结构对各变量取值的支持程度。
2.3 图结构与推理难度
图的结构决定了推理的复杂程度。对于无环或弱耦合结构，消息传递较容易收敛；而在复杂环路密集的图中，推理往往更困难，近似误差也更明显。
2.3.1 树结构
树结构没有回路，消息不会沿环反复循环，因此每条边上的信息流向较清晰。对于这类图，置信传播通常可在有限步内完成并给出精确结果。
2.3.2 含环图结构
含环图结构会使消息在图中来回反馈，导致信息重复计入。虽然这会增加推理难度，但在实践中，置信传播仍常能给出质量较高的近似解，因此应用十分广泛。
3 算法原理
3.1 消息传递机制
置信传播的基本过程是节点之间交换消息。每条消息都可看作对某个变量状态的局部判断或支持强度，经过多轮更新后，节点便能形成对全局状态的近似认识。
3.1.1 从变量到因子的信息流
变量到因子的消息通常表示该变量在排除目标因子影响后，对各取值的当前信念。它汇总来自其他相邻因子的输入，再传递给新的因子，以避免重复使用同一信息。
3.1.2 从因子到变量的信息流
因子到变量的消息反映局部函数对该变量不同取值的兼容程度。因子会综合其余相邻变量的消息，再把局部约束或偏好反馈给目标变量。
3.2 和积算法
和积算法是置信传播的经典形式，主要用于估计边缘概率。它通过“求和”整合所有可能状态的贡献，使每个变量的边缘分布得到近似表示。
3.2.1 边缘分布计算
在和积算法中，变量节点收到的消息会被组合成该变量的信念函数，再通过归一化得到边缘分布估计。若图为树结构，这一结果与精确边缘一致。
3.2.2 归一化处理
归一化用于将未标准化的信念转换为合法概率分布。它既便于解释，也能降低数值运算中的尺度差异，常在每轮消息更新后执行。
3.3 最大积算法
最大积算法是和积算法的对应形式，关注的是最可能的整体赋值而不是概率总和。它通过“取最大”保留最优路径上的信息，适合进行最大后验估计。
3.3.1 最大后验估计
最大后验估计旨在寻找给定观测条件下概率最大的变量配置。最大积算法通过局部消息传递近似求解这一问题，在离散优化中具有较强实用性。
3.3.2 赋值选择规则
在完成消息传递后，通常根据节点信念选择最优取值。常见做法是对每个变量取局部信念最大的状态；在某些场景中，也会结合回溯或一致性修正来确定最终赋值。
3.4 迭代更新过程
置信传播一般采用迭代方式运行。每一轮更新都基于上一轮消息进行修正，直到变化足够小或达到预设条件为止。
3.4.1 初始化
初始化决定消息传递的起点。常见做法是将消息设为均匀分布、局部偏好或由先验信息给定的值，不同初始化可能影响收敛速度和最终结果。
3.4.2 收敛判定
收敛判定通常依据相邻两轮消息差异是否足够小，或信念是否稳定不变。若系统达到稳定状态，便可停止迭代并输出当前近似解。
3.4.3 停止准则
停止准则包括达到最大迭代次数、消息变化低于阈值，或信念满足某种一致性要求。实际应用中，常根据精度需求与计算成本综合设定。
4 理论性质
4.1 树图上的精确性
在树图上，置信传播具有严格的精确性。由于不存在环路，消息只需沿树的方向传播一次或有限次，即可完整汇聚所有相关信息，因此边缘结果与最优赋值都能准确得到。
4.2 含环图上的近似性
在含环图中，消息会重复经过相同区域，局部信息可能被多次计算。这使得结果一般不再严格精确，但在许多实际问题里，近似误差仍可接受，甚至表现出较强的经验效果。
4.3 收敛性分析
置信传播的收敛性与图结构、因子强度、初始化方式及更新策略密切相关。理论上，某些情形可保证收敛；但在更复杂的图中，也可能出现震荡或多种稳定点并存的现象。
4.3.1 有限收敛条件
当图结构较简单、相互作用较弱或满足特定单调性条件时，算法更可能在有限步内稳定下来。树结构是最典型的有限收敛情形。
4.3.2 不收敛情形
若图中环路较多、约束较强，或者更新过程缺乏适当阻尼，消息可能在若干状态之间循环摆动，无法稳定到单一解。这也是含环图应用中最常见的难点之一。
4.4 与变分推断的关系
置信传播与变分推断之间存在紧密联系。它不仅可被理解为一种消息传递算法，也可视为在某种近似自由能下进行优化的过程。
4.4.1 自由能解释
从自由能角度看，置信传播对应于对系统近似自由能的局部极值求解。通过迭代更新消息，算法相当于在寻找一个更一致的近似分布。
4.4.2 近似最优化视角
在优化视角下，消息传递可视为协调各局部约束，使整体目标逐渐改善。这个解释为其在组合优化和图模型学习中的应用提供了统一框架。
5 常见变体
5.1 和置信传播
和置信传播强调对概率质量的累积，主要用于边缘分布估计。它是最经典、最基础的置信传播形式，常作为其他变体的参考标准。
5.2 最大置信传播
最大置信传播对应于最大积思想，重心放在寻找最可能的状态配置。与和置信传播相比，它更关注最优解而非完整分布，因此在路径选择和译码中较常见。
5.3 加权置信传播
加权置信传播会对不同消息或因子赋予不同权重，以增强稳定性或改进近似质量。适当的权重设置有时能缓解环图带来的误差，但也会引入参数调节问题。
5.4 残差置信传播
残差置信传播根据消息变化幅度安排更新顺序，优先处理变化较大的边或节点。这样可以提高计算效率，并在某些问题上更快接近稳定状态。
5.5 非同步消息传递
非同步消息传递不要求所有节点同时更新，而是按顺序、按块或按事件触发方式进行。它更适合分布式环境，也常用于大规模图上的实际实现。
6 数学表达
6.1 消息更新公式
置信传播的数学形式通常写为变量节点与因子节点之间的递推关系。不同模型下，公式结构相似，但求和、求积或取最大等操作会根据目标任务发生变化。
6.1.1 离散变量情形
离散变量场景下，消息通常是对每个可能状态的向量表示。更新时会在相邻状态空间上进行求和或取最大，再经过归一化得到新的消息值。
6.1.2 连续变量情形
连续变量场景中，消息可表示为概率密度或其参数化形式。若分布属于高斯族等可闭合类别，消息更新往往能化为参数递推，计算更为高效。
6.2 边缘近似公式
边缘近似通常由某个变量接收到的所有入边消息组合而成。其基本形式是把局部先验与邻域消息相乘，再进行标准化，从而得到该变量的近似边缘分布。
6.3 规范化与数值稳定性
实际计算中，消息值可能非常小或非常大，因此需要专门处理数值稳定性问题。规范化、重标定和对数域计算都是常见手段。
6.3.1 下溢问题
当概率连乘项很多时，浮点数可能迅速接近零，导致下溢。为避免这一问题，通常会在每步更新后重新缩放消息，或改用对数表示。
6.3.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 配分函数近似
配分函数难以直接精确计算，尤其在高维系统中更是如此。置信传播可通过局部消息累积，给出配分函数的近似值或相关热力学量估计。
8 优缺点与局限
8.1 优势
置信传播的优点在于形式统一、适用面广，并且能够在很多大规模问题上提供可接受的近似解。它兼具理论可解释性和工程实用性。
8.1.1 计算效率
相比穷举搜索，消息传递通常能大幅降低计算量。对于稀疏图，单轮更新的代价较低，整体效率尤为突出。
8.1.2 分布式实现
由于各节点主要依赖邻域消息，置信传播很适合并行与分布式执行。这使其在大规模系统和硬件实现中都具有吸引力。
8.2 局限
尽管应用广泛，置信传播并非对所有问题都稳定有效。其结果可能受图结构、参数设置和更新方式影响较大。
8.2.1 环图误差
在含环图中，信息重复传播会造成估计偏差。环越多、耦合越强，这种误差往往越明显。
8.2.2 多解与震荡
某些问题存在多个稳定点，算法可能收敛到不同解，甚至在多个状态之间来回震荡。这会降低结果的可重复性和解释一致性。
8.2.3 参数敏感性
消息更新中的初始化、阻尼系数和权重设置，都会影响运行效果。对于一些复杂模型，参数选择不当会导致收敛变慢或结果失真。
9 历史与影响
9.1 早期思想来源
置信传播的思想可追溯到早期的递推概率计算、动态规划和通信译码方法。其核心并不新颖，但在图模型框架下得到统一后，形成了更通用的算法体系。
9.2 经典研究进展
随着图模型理论成熟，消息传递方法逐步被系统化，并在因子图、贝叶斯推断和统计物理中建立了标准表述。相关研究推动了和积、最大积及其改进形式的发展。
9.3 对后续算法的影响
置信传播不仅是一种独立算法，也为许多后续方法提供了思路模板。它对近似推断和图优化的影响尤为深远。
9.3.1 近似推理方法
许多近似推理算法都借鉴了消息传递、局部更新和变分解释等思想。它们在结构上与置信传播相近，但会针对稳定性、精度或复杂约束进行调整。
9.3.2 图优化方法
在图优化领域，置信传播启发了多种分布式求解策略。无论是能量最小化还是组合搜索，局部协同更新的思路都成为重要基础。