置信传播是一类用于概率图模型推断的消息传递算法。它在图中相邻部分之间传递称为“消息”的函数,从而计算联合概率分布的相关信息。其标准的和积形式用于计算边缘概率,即将其他变量求和消去后,得到单个变量或一小组变量的分布。与之相关的最大积形式和最小和形式,则用于寻找概率最高或代价最低的联合配置。
其核心思想是利用因子分解。一个涉及众多变量的分布,可以用若干小函数来表示,每个函数只涉及少数几个变量。置信传播不必枚举所有可能的联合赋值,而是将这些局部函数组合起来,并复用中间结果。在树结构图上,经过有限次消息交换,它就能给出精确结果。在含环的图上,同样的局部规则构成了有环置信传播。这是一种迭代近似方法,实际效果有时非常出色,但不能保证收敛,也不能保证得到精确的概率。
置信传播将人工智能、统计学、通信理论和统计物理联系起来,为纠错码、序列模型、图像分析和分布式估计中使用的算法提供了统一的描述语言。它的数学基础也有助于厘清精确推断、近似局部一致性与全局优化之间的区别。
历史发展与统一框架
置信传播源于多个研究传统,它们起初使用的术语各不相同。在通信理论领域,罗伯特·加拉格于1962年发表的低密度奇偶校验码论文,描述了基于稀疏奇偶校验约束的迭代概率译码方法。他在1963年的专著中进一步发展了这一课题。这些译码过程在比特节点与校验节点之间交换局部信息,已初具后来成为标准的因子图解释框架的雏形。
在人工智能领域,朱迪亚·珀尔于20世纪80年代为单连通置信网络发展了局部概率传播方法。他在1982年关于分布式概率推理的研究,以及1988年出版的《智能系统中的概率推理》,推动置信传播确立为一种通用推断方法。其中一个核心问题是:表示不确定性依赖关系的网络,如何在获得观测信息时更新其置信度,而不必反复重新计算整张联合概率表。
在其他领域,相关算法早已得到确立。用于隐马尔可夫模型的前向—后向算法根据序列观测计算状态概率。维特比算法用于寻找概率最大的状态序列。L. R. 巴尔、J. 科克、F. 耶利内克和J. 拉维夫于1974年提出的BCJR算法,则通过计算后验概率来译码卷积码。这些方法的目标和所用的代数运算虽有不同,却都利用了同一种思路:将计算分解为沿图进行的局部计算。
R. 迈克尔·坦纳于1981年提出了码的图表示方法,以二部图连接符号与约束,产生了深远影响。1993年,克洛德·贝鲁、阿兰·格拉维厄和普尼亚·蒂蒂马吉希马提出Turbo码;随后,低密度奇偶校验码重新受到关注。这些进展展示了在有环图上迭代交换信息的强大实用价值。成功译码并不要求底层图必须是一棵树。
弗兰克·克希尚、布伦丹·弗雷和汉斯-安德烈亚·勒利格于2001年发表的论文《因子图与和积算法》,提出了一个涵盖面尤为广泛的统一框架。该论文表明,许多熟知的推断算法和信号处理算法,都可以视为同一条局部计算规则的具体实例。大致在同一时期,乔纳森·耶迪迪亚、威廉·弗里曼和亚伊尔·韦斯的研究,将有环置信传播与近似自由能优化联系起来。这一联系解释了为什么即使收敛后的消息无法给出精确的边缘概率,它们仍能满足有意义的变分方程。
因此,从历史上看,置信传播不仅仅是为某一任务发明的单一算法。它也体现了一种认识:译码、概率推理以及某些形式的动态规划,具有共同的计算结构。
因子化分布与图表示
设 表示一组离散随机变量。因子化分布可写为
其中, 是因子的索引集, 是因子 涉及的变量集合,每个 都非负。配分函数 用于对乘积进行归一化,并假定其值有限且为正。因子可以表示概率依赖关系、观测似然,也可以表示硬约束,即对不允许的赋值取零。
因子图用二分图表示上述表达式。一类节点表示变量,另一类节点表示因子。当且仅当 出现在 中时,变量 与因子 之间有边相连。该图记录的是局部函数所涉及的变量范围,而非因果影响的方向。同一个分布可能有多种因子化方式,具体选择会显著影响消息传递的计算成本和准确性。
例如,一条包含一元证据项和成对相互作用的链具有如下形式:
一元因子 可以编码位置 处的观测,而成对因子则描述相邻状态之间的相容性。这类链式结构常见于序列标注和状态估计。二维图像模型具有类似的局部结构,但通常包含许多环。
贝叶斯网络提供了另一种表示方式:它是一个有向无环图,每个变量都对应一个给定其父节点时的条件概率因子。将这些条件分布视为因子,即可把它转换为因子图。相比之下,马尔可夫随机场通常通过团势函数来表达无向模型。置信传播作用于最终得到的因子化表示,因此,其基本要求并不局限于有向或无向的表示形式。
通常通过固定变量或添加似然因子来纳入观测。例如,观测到离散值 时,可以用一个指示因子来表示:它在 处取一,在其他值处取零。对于不确定性较大的测量,则使用更一般的似然函数。
必须区分几种主要的推断目标。边缘推断求的是 这类分布。最可能解释推断求的是使 最大化的联合赋值。计算 则是另一项任务。这些量彼此相关,但一种方法即使能很好地估计其中一个量,也未必能很好地估计其他量。
和积消息与局部置信度
对于每条变量—因子边,和积置信传播都维护两条消息。从变量发往因子的消息汇总了该变量从其他相邻因子接收到的信息:
从因子发往变量的消息则将该因子与来自其他变量的信息相结合,再对这些变量求和消元:
记号 表示与变量 相邻的因子。单变量证据可以表示为普通因子,因此上述方程已足够,无须另设证据项。
排除接收方至关重要。在同一次更新中,从 发往 的消息不会使用从 发往 的消息。在树上,这保证了每条消息只汇总一条边某一侧的信息,而不会立即将接收方提供的信息传回给它。用物理学术语来说,这种排除与空腔构造有关:暂时移除与接收方的相互作用。
将所有传入的因子消息相结合,即可得到变量置信度:
类似地,因子置信度为
常数 和 用于对这些函数进行归一化。在树上,所得置信度就是精确的边缘分布。在有环图上,使用“置信度”一词,正是为了容许它们只是近似结果。
单条消息通常并不是后验概率。其尺度可以任意选取:将一条消息乘以一个不依赖于其自变量的正常数,不会改变通过相应更新得到的归一化置信度。因此,为了便于数值计算,消息通常会被归一化,使各项之和为一。如果还需要计算配分函数,就必须将这种归一化的影响纳入考虑。
下面用一个二元变量的例子说明因子更新。假设 ,某个因子在 时取值为 ,否则取值为 。如果关于 的传入消息为 ,则发往 的消息为
归一化后为 。因此,因子对两变量取值相等的偏好,将支持 的证据转化为对 较弱的偏好。其他相邻因子通过乘法贡献信息,从而使多个来源的证据得以在局部合并。
树上的精确推断及其计算成本
信念传播在树上具有精确性,源于树的分离性质。移除任意一条边,都会将图分成两个互不连通的分量。沿这条边传递的消息,可以理解为:将发送方一侧的所有因子相乘,再对该侧除边界变量以外的所有变量求和。树结构保证,在给定这一边界变量的条件下,从不同分支传来的信息对应于互不重叠的子问题。
这一解释给出了正确性的归纳证明。在叶节点处,消息直接由局部因子或空乘积得到。内部节点收到的所有向内消息计算完成后,其向外发送的消息就能正确概括这些消息所对应子树的并集。沿树继续向选定的根节点推进,便能得到根节点的精确边缘分布。随后再向外传递一遍,即可得到其余消息,进而得到所有变量和因子的边缘分布。
完整的由内向外双向调度,会沿每条边的两个方向各发送一条消息。因此,通信次数与图的边数呈线性关系。但这并不意味着每个树结构模型的计算成本都很低:对于一个涉及 个变量、每个变量有 个状态的因子,直接采用基于表的计算方法,可能需要与 成正比的计算量。因子涉及的变量个数及其内部代数结构,与图的规模同样重要。
对于含有 个变量、每个变量至多有 个状态的成对交互树模型,稠密消息更新通常总共需要 次算术运算。除因子本身的存储之外,存储所有有向消息还需要 的空间。链是其中的特例,对应于前向—后向推断;若将求和替换为取最大值,则得到维特比式的动态规划算法。
信念传播与变量消去密切相关。两者都反复运用分配律,避免枚举完整的联合分布。变量消去侧重于对变量求和消去的顺序,以及由此产生的中间因子。树上的消息传递则侧重于附着在图的边上、可重复使用的汇总信息。在合适的树表示下,两者实际上是对同一计算过程的互补描述。
对于有环图,可以将变量聚合成更大的节点,再使用联结树算法,从而实现精确推断。代价是,此时消息涉及的是一组变量的赋值。这些变量组的大小由树宽决定,生成的表可能随树宽呈指数增长。
这一区别解释了主要的计算复杂性权衡。稀疏图仍可能具有很大的树宽,因此,仅仅边数少并不能保证精确推断的高效性。反过来,大型链或树也可能易于处理,因为其分隔集始终很小。当所选表示能让子问题之间的边界保持小巧、易于处理时,信念传播就能高效运行。
有环传播、收敛性与近似误差
有环置信传播将相同的更新方程应用于含环的图。消息经过初始化后(通常设为正的均匀值),反复更新,直到满足停止条件。与树的情形不同,此时一条消息不再对应原图中某个固定且互不重叠的部分。信息可以沿环循环传播,最终影响它最初出发的位置。
一种有用的解释方式,是将迭代过程展开为一棵计算树。在这棵展开的树中,每次再次遇到原图中的某个变量或因子,都会将其表示为一个独立的副本。经过有限次迭代后,一条边上的消息可以理解为在相应的有限计算树上进行精确推断的结果,其边界条件由初始化方式决定。近似误差的来源在于:这些副本代表的是原图中的同一个变量,却在展开后的树中被当作不同变量处理。
这既解释了该方法为何有效,也解释了它为何会失效。在环较长的稀疏图中,局部邻域在若干轮迭代内可能呈现树状结构,使算法能够在信息大量回流之前完成有意义的局部计算。当相关性随距离迅速衰减时,人为边界的影响可能较为有限。相反,强相互作用、短反馈环或相互竞争的模态,都可能使展开后的模型难以准确近似原分布。
收敛性与准确性是两个不同的问题。消息可能出现振荡,在归一化之前变得不稳定,因初始化不同而收敛到不同的不动点,或者最终得到与精确边缘概率相差甚远的置信度。稳定的不动点并不能保证结果正确。即便置信度满足局部一致性,也未必是任何全局联合分布的边缘分布。
更新调度方式会影响这些行为。同步更新根据上一轮迭代的值计算所有新消息。异步调度则立即使用刚刚得到的新值。残差调度优先更新那些预计变化最大的消息。阻尼将完整更新替换为新旧值的混合,例如
其中, 是常规更新得到的值。在采用一致的归一化约定时,阻尼不会改变不动点,但并不能普遍保证收敛。
严格的收敛性结论依赖于特定假设。足够弱的相互作用可以使更新映射成为压缩映射,而某些高斯模型的收敛条件可以通过矩阵性质来表述。这些都是针对特定情形的充分条件,而不是对所有图模型都适用的普遍保证。
实际使用的停止判据通常衡量归一化消息或置信度的变化,有时也会同时检查局部一致性的违反程度。数值残差很小,只能说明实现所得到的结果接近其更新方程的某个不动点,并不能衡量它与真实后验分布之间的距离。因此,在评估近似效果时,将结果与较小规模实例上的精确计算进行比较仍然十分重要。
Bethe 自由能与局部一致性
置信传播的一种重要理论解释来自变分推断。变分方法并不直接对所有赋值求和,而是将推断表述为对分布或分布的概括表示进行优化。对于置信传播,所采用的近似是 Bethe 近似,它用局部熵的组合来替代精确的熵。
设 和 分别为归一化的候选变量置信分布和因子置信分布。它们必须非负,并满足局部一致性条件:
这一条件对每条边 都成立。这些条件保证相邻置信分布在共有的单变量边缘分布上保持一致。在树上,这种局部一致性足以构造出一个全局联合分布;但在有环图上,通常并非如此。
若 表示与变量 相邻的因子数量,则 Bethe 熵为
其中, 表示香农熵。减去的部分用于修正重叠因子对变量不确定性的重复计数。这一修正在树上是精确的,但对于一般的有环图则只是近似。
相应的无量纲 Bethe 自由能为
对于硬约束,置信分布必须遵守零概率所限定的支撑集限制,上式也需作相应解释。在树上,在所有满足局部一致性的置信分布中最小化这一自由能,可以得到精确的边缘分布,其最小值等于 。
对于取值严格为正的模型及适当的内部置信分布,置信传播的不动点对应于带约束的 Bethe 自由能的驻点。用于强制满足局部一致性的拉格朗日乘子可以重新表示为消息,从而得到熟悉的更新方程。这就在局部计算与数学优化之间建立了联系。
这种联系并不意味着普通置信传播是一种通用的下降算法。在有环图上,Bethe 目标函数通常是非凸的,标准消息更新不一定在每次迭代中都使其下降。系统可能存在多个驻点,其中一些可能反映相互竞争的模态或相态,另一些则可能对精确分布给出较差的近似。
Bethe 视角还解释了置信传播为何不同于完全因子化的平均场近似。平均场将近似联合分布表示为各个独立变量分布的乘积。Bethe 方法则显式保留因子层面的相关性,并要求这些因子在重叠部分保持一致。因此,它能够捕捉乘积近似所遗漏的依赖关系,不过这两种方法都并非在所有情况下更优。
各种扩展方法会改变熵的近似方式,或调整维护置信分布的区域。其目的是更好地表示相关性,或改善优化问题的目标函数形态,但通常需要付出消息规模更大、一致性约束处理成本更高的代价。
最大积、高斯及广义形式
局部消息传递的模式并不限于求和与乘法。在最大积传播中,从因子到变量的消息更新将对相邻变量赋值的求和替换为取最大值。在树上,由此得到的动态规划算法可以找出全局概率最大的赋值。该算法通常会记录使目标取最大值的选择,再通过回溯重建一个相互一致的解。
回溯之所以重要,是因为存在并列最大值时,分别从每个变量的最大边缘函数中选取一个使其取最大值的状态,可能无法得到最优解。这些独立选择可能将不同最优配置的局部片段拼在一起,形成一个本身并不最优的配置。在有环图上,即使最大积消息已经收敛,通常也不能保证得到全局最优解,不过对于某些特殊模型,在附加条件下可以得出更强的结论。
取负对数可以将乘法转化为加法。若模型写为
则可得到最小和更新:
这就将推断与离散能量最小化联系起来。更广义的和积框架可以用适当的代数结构来表述,这类结构通常称为半环,其中两种组合运算满足分配律。因此,普通的边缘化、最大权重计算以及某些约束处理算法,都具有共同的基于图的结构。
对于连续变量,求和变为积分,消息也由有限数组变为函数。精确的函数形式消息通常很难表示。一个重要的例外是正态分布(高斯)模型的推断:高斯函数的乘积及其边缘化结果仍为高斯函数,因此可以用精度矩阵和信息向量来表示消息。
高斯置信传播在树上是精确的。对于满足适当正定性条件和收敛条件的有环高斯模型,即使方差估计不精确,收敛后的均值估计仍可能是精确的。收敛是一项独立要求;仅仅具有一个正规的高斯分布,并不能保证每一种常规消息调度方式都会收敛。该方法也与线性方程组的分布式求解有关。
非高斯连续模型需要采用离散网格、混合分布、数值积分或粒子等近似方法。除了环路可能造成的误差外,这些方法还会引入表示误差。精细的离散化可能使每条消息的计算代价都很高,尤其是在因子连接多个连续变量时。
广义置信传播在更大的变量簇或区域之间交换置信信息,通常使用区域图来处理区域之间的重叠。将一个短环包含在同一区域内可以改善近似效果,但区域的状态数会随其所含离散变量的数量呈指数增长。树重加权方法则采用另一条路径,将基于树的构造与经过调整的熵权重相结合。这些都是相关的消息传递方法,而不是普通置信传播可以互换使用的名称。
纠错码及其他应用
置信传播最具影响力的应用之一是对纠错码进行译码,尤其是低密度奇偶校验码。这类码由稀疏二元奇偶校验矩阵 定义。有效码字 满足
其因子图中,每个传输比特对应一个变量节点,每个奇偶校验方程对应一个校验节点。信道观测提供各比特的似然。对于满足奇偶校验约束的赋值,校验因子的值为一,否则为零。
对于二元变量,消息可以用对数似然比紧凑地表示。按照一种常用的符号约定,
变量节点将传入的校验消息与信道对数似然比相加。对于偶校验,和积算法的校验节点更新为
凭借这种特殊结构,更新的计算成本远低于枚举高度数奇偶校验因子的所有赋值。最小和译码用传入消息中最小的幅值近似校验消息的幅值,并结合各消息的符号确定其符号;归一化最小和与偏移最小和等变体则进一步修正这一近似。这些方法减少了算术运算量,适合硬件实现,但近似也会改变译码行为。
码的设计与推断相互影响。稀疏图可减少每次迭代的计算量,而短环可能导致消息之间产生相关性。包括陷阱集在内的某些特定子图会导致译码失败。密度演化在使有限邻域实际上呈树状的假设下,分析大规模码集合中的消息分布。实际性能仍取决于码长、度分布、信道模型、数值精度和迭代次数上限。
在计算机视觉中,置信传播已用于立体匹配、图像复原和标注。变量可以表示某个像素处的视差或类别,一元因子描述局部证据,成对因子则鼓励相邻位置采用相容的标签。这类网格包含大量短环,状态空间也可能很大,因此加快更新速度和保证近似质量是核心问题。
在自然语言处理中,链式结构的条件随机场可以使用前向—后向算法进行精确推断,而更复杂的依赖结构则可能需要采用有环置信传播或聚类方法。在机器人学和同时定位与地图构建中,因子图用于表示位姿、地标与传感器测量之间的关系。许多实际系统通过非线性最小二乘法求解由此产生的估计问题,而非采用和积传播,因此仅仅使用因子图,并不能说明系统使用了置信传播。
统计物理是另一个重要的应用领域。变量可以表示自旋,因子则编码相互作用。空腔计算与贝特近似有助于描述稀疏无序系统。在这些应用中,置信传播的共同吸引力在于:它能够将大规模的全局计算转化为反复执行的局部运算,而这些运算的成本取决于较小的邻域。
数值实现及其与现代学习方法的关系
稳健的实现必须将数学更新规则与其数值表示分开。直接将大量很小的概率相乘,会在浮点运算中导致下溢。对数域消息将乘积转化为求和,并利用 log-sum-exp 恒等式计算边缘化:
也可以在每次更新后对消息重新缩放。这种缩放不会改变归一化后的置信度,但如果实现需要估计配分函数,就必须保留相关的归一化信息。
硬约束需要格外谨慎地处理。在对数表示中,零概率变为负无穷,而完全不可能的局部配置可能使归一化无定义。有些实现通过将所有传入消息的乘积除以相应消息来求得传出消息,这类基于除法的实现可能遇到零除以零的问题。采用前缀—后缀累积,或在计算时显式排除接收方,可以避免其中一些困难。检测证据是否存在矛盾,与仅仅避免数值异常是两回事。
性能在很大程度上取决于因子的结构。稠密表的更新开销随因子所涉及的变量数呈指数增长,而奇偶校验、高斯因子、稀疏约束以及某些卷积关系则允许采用专门的计算方法。对于成对因子,矩阵—向量运算是自然的基本操作。如果一个变量有许多邻居,就可以复用部分乘积或部分和,避免为每条出边分别重复计算相同的汇总结果。
这种局部结构适合并行计算和分布式计算。彼此独立的更新可以分配给不同的处理器,大型规则图也可以映射到图形处理器上。不过,不规则的连接结构、较小的消息体量、内存带宽以及同步开销都可能限制加速效果。同步调度易于并行化,但所需的迭代次数可能多于精心选择的顺序调度或残差调度。
置信传播也会作为机器学习系统中的一个组件。当模型参数决定因子取值时,可以将固定次数的消息传递迭代展开为一个计算图,随后通过反向传播求得梯度。这样训练出的参数针对的是有限步推断过程的表现,不一定与采用精确概率推断进行训练所得的结果相同。
另一种方法是,在满足可微性和非奇异性条件的前提下,通过已收敛的不动点进行隐式求导。改变归一化方式、阻尼、停止准则或因子的参数化方式,都可能影响这些导数。因此,对不稳定或收敛不充分的推断过程求导,并不等同于对精确后验概率求导。
图神经网络同样采用从邻居汇集消息的总体模式,但两者的相似性有其限度。图神经网络的消息通常是学习得到的向量表示,而不是具有既定概率解释的函数。学习式消息传递系统可以模仿、初始化、加速或修改置信传播;但一旦替换了更新方程,树上的精确性以及有关 Bethe 不动点的结果就不会自动沿用。即使消息的数学含义已经改变,计算架构仍然可以保持相似。