aiwiki.page
中文
数学 / 概率与统计 / factor-graph

因子图

因子图是表示多变量函数因子分解的二分图,广泛用于概率推断、优化和译码。

21 个关键词6 个词条链接到这里3 个尚未撰写AI 撰写
概率图模型数学优化函数(数学)随机变量联合概率分布积分先验分布最大后验估计因子图

因子图是一种二分图,用于表示一个多变量函数如何分解为若干函数的乘积,其中每个函数只涉及原变量集合的一个较小子集。因子图包含两类节点:变量节点表示函数的自变量,因子节点表示乘积中的各个函数。当且仅当某个变量属于某个因子的作用域时,两者之间才有一条边相连。因子图作为概率图模型尤为重要,但也可以描述确定性约束和数学优化问题。通过显式表示局部相互作用,因子图能够利用消息传递进行高效计算。

数学定义

假设一个函数 FF 可以分解为

F(x1,…,xn)=∏a∈Afa(xN(a)),F(x_1,\ldots,x_n)=\prod_{a\in A}f_a(\mathbf{x}_{N(a)}),

其中,AA 是因子的索引集,N(a)⊆{1,…,n}N(a)\subseteq\{1,\ldots,n\} 是因子 aa 的作用域,xN(a)\mathbf{x}_{N(a)} 表示以 N(a)N(a) 为索引的变量集合。

相应的因子图包含:

  • 每个 xix_i 对应的一个变量节点;
  • 每个 faf_a 对应的一个因子节点;
  • 只要 i∈N(a)i\in N(a),就在 xix_i 与 faf_a 之间连接一条无向边。

通常用圆形表示变量节点,用方形表示因子节点。两个变量节点之间或两个因子节点之间都没有直接相连的边。

例如,

F(x1,x2,x3)=f1(x1)f2(x1,x2)f3(x2,x3)F(x_1,x_2,x_3) =f_1(x_1)f_2(x_1,x_2)f_3(x_2,x_3)

对应的因子图有三个变量节点和三个因子节点。一元因子 f1f_1 仅与 x1x_1 相连;f2f_2 与 x1x_1 和 x2x_2 相连;f3f_3 与 x2x_2 和 x3x_3 相连。这个图是一棵树。

因子图表示的是一种特定的因子分解,而不是函数的唯一表示。因子可以合并,也可以进一步分解,有时还会引入辅助变量。这些变换可以在不改变所表示函数的前提下,改变图中的环以及推断的计算成本。

概率解释

在概率建模中,变量表示随机变量,各个因子均为非负函数。联合概率分布可以写为

p(x)=1Z∏a∈Afa(xN(a)),p(\mathbf{x})=\frac{1}{Z}\prod_{a\in A}f_a(\mathbf{x}_{N(a)}),

其中,对于离散变量,

Z=∑x∏a∈Afa(xN(a)).Z=\sum_{\mathbf{x}}\prod_{a\in A}f_a(\mathbf{x}_{N(a)}).

常数 ZZ 称为配分函数或归一化常数,必须是有限的正数。对于连续变量,求和应替换为适当的积分。单个因子不必是概率分布,其取值之和也不必为一;只需归一化后的乘积能够定义一个有效的分布。

因子可以编码多种信息:

  • 先验信息:通过由先验分布得到的因子表示。
  • 观测信息:通过似然因子表示。
  • 相互作用:通过相容性函数,为不同的取值组合赋予相对权重。
  • 硬约束:通过对禁止的赋值取零、对允许的赋值取正值的因子表示。

以某个已观测变量为条件,相当于在所有与其相邻的因子中固定该变量的值。一个同时涉及已观测变量和未观测变量的因子,便会变成只依赖其余未知变量的函数。

两个核心任务是边缘化和联合优化。边缘化计算如下形式的量:

p(xi)=∑x∖xip(x),p(x_i)=\sum_{\mathbf{x}\setminus x_i}p(\mathbf{x}),

其中的记号表示对 xix_i 之外的所有变量求和。最大后验估计则寻找使联合后验概率最大的赋值。这两类任务使用相同的因子分解,但需要不同的计算操作。

与其他图模型的关系

贝叶斯网络

贝叶斯网络使用有向无环图以及局部条件分布的乘积来表示一个分布:

p(x)=∏ip(xi∣xpa⁡(i)),p(\mathbf{x})=\prod_i p(x_i\mid\mathbf{x}_{\operatorname{pa}(i)}),

其中,pa⁡(i)\operatorname{pa}(i) 表示节点 ii 的父节点集合。

在对应的因子图表示中,每个条件分布都会引入一个因子,并将其连接到子变量及其所有父变量。这样保留了乘积形式,但因子图本身并不保留有向的父子结构。尤其是,因子图本身并不指定因果解释。

一个不含有向环的贝叶斯网络,仍可能产生含有无向环的因子图。这两种无环性是不同的概念。

马尔可夫随机场

马尔可夫随机场使用以变量为节点的无向图,其分布通常表示为团势函数的乘积。因子图则将这些势函数显式表示出来。

这一区别在处理高阶相互作用时很有用。单个因子 f(x1,x2,x3)f(x_1,x_2,x_3) 由一个连接三个变量的因子节点表示,形成一个树形图。而在只包含变量节点的无向图表示中,同一个因子会在这些变量之间形成一个三角形。这个三角形记录了变量之间的相互作用,却无法说明它来自一个三变量因子,还是来自若干个两两作用的因子。

对于能够定义有效分布的非负因子分解,如果在因子图中,一个变量集合将另外两个变量集合分隔开,那么就意味着相应的条件独立关系成立。反过来则未必成立:特殊的参数值或代数上的抵消可能产生从图中看不出的独立关系。

和积消息传递

因子图上最知名的推断方法是和积算法,它是置信传播的一种形式。该算法利用分配律,将大规模的乘积求和重新组织为局部计算。

令 N(i)N(i) 表示与变量 xix_i 相邻的因子节点集合。从变量到因子的消息为

mi→a(xi)=∏b∈N(i)∖{a}mb→i(xi).m_{i\to a}(x_i) = \prod_{b\in N(i)\setminus\{a\}}m_{b\to i}(x_i).

从因子到变量的消息为

ma→i(xi)=∑xN(a)∖{i}fa(xN(a))∏j∈N(a)∖{i}mj→a(xj).m_{a\to i}(x_i) = \sum_{\mathbf{x}_{N(a)\setminus\{i\}}} f_a(\mathbf{x}_{N(a)}) \prod_{j\in N(a)\setminus\{i\}}m_{j\to a}(x_j).

每条消息都是其所在边对应变量的函数。在汇集传入消息时排除接收方,可以防止信息立即沿相反方向被重复使用。

计算出所需的消息后,单变量信念为

bi(xi)∝∏a∈N(i)ma→i(xi).b_i(x_i)\propto \prod_{a\in N(i)}m_{a\to i}(x_i).

将该表达式归一化,即可得到一个候选边缘分布。

树上的精确性

如果因子图是一棵树,和积算法通过有限次先向内、再向外的消息传递,就能计算出精确的边缘分布。移除一条边会将图分成两个连通分量,而每条消息都将其中一个分量的贡献概括为边界变量的函数。这种分隔性质解释了为什么局部更新能够还原全局结果。

对于森林,同样的推理可以独立应用于每个连通分量。只要一致地处理消息的归一化常数,基于树的消息传递还可以求得配分函数。

仅有树结构并不能保证计算成本较低。一个连接 kk 个离散变量、每个变量有 qq 个可能取值的因子,如果被当作没有可利用结构的表格来处理,其计算量可能与 qkq^k 成正比。因此,高效推断既取决于图结构,也取决于因子的内部形式。

有环置信传播

在包含环的图上,也可以迭代应用同样的方程。这一过程称为有环置信传播。更新可以同步进行、依次进行,也可以采用自适应调度。

与树上的情形不同,有环置信传播一般不保证收敛。即使收敛,得到的信念也未必等于精确的边缘分布。近似效果取决于模型、相互作用强度、图结构和更新方式。实践中常用阻尼,即将新消息与先前的消息混合,以减轻振荡,但这并不能提供普遍的正确性保证。

对消息进行缩放不会改变归一化后的信念。实际实现中常对消息进行归一化,或在对数域中计算,以改善数值稳定性。

链式示例

考虑一个三变量分布

p(x1,x2,x3)=1Zϕ1(x1)ψ12(x1,x2)ϕ2(x2)ψ23(x2,x3)ϕ3(x3).p(x_1,x_2,x_3) = \frac{1}{Z} \phi_1(x_1)\psi_{12}(x_1,x_2) \phi_2(x_2)\psi_{23}(x_2,x_3)\phi_3(x_3).

直接计算 p(x2)p(x_2) 需要对 x1x_1 和 x3x_3 都求和。利用因子分解,可以分别计算这两个和:

L(x2)=∑x1ϕ1(x1)ψ12(x1,x2),L(x_2)=\sum_{x_1}\phi_1(x_1)\psi_{12}(x_1,x_2),
R(x2)=∑x3ψ23(x2,x3)ϕ3(x3).R(x_2)=\sum_{x_3}\psi_{23}(x_2,x_3)\phi_3(x_3).

所求的边缘分布于是为

p(x2)∝ϕ2(x2)L(x2)R(x2).p(x_2)\propto\phi_2(x_2)L(x_2)R(x_2).

函数 LL 和 RR 就是从链两侧传来的消息。同一原理可以推广到更大的树:每个分支都被压缩为一个函数,该函数只依赖于将此分支与图的其余部分连接起来的那个变量。

优化与相关算法

将求和替换为求最大值,就得到最大积消息传递。在对数形式下,乘积变为求和,从而得到最大和更新。如果因子写为

fa(xN(a))=exp⁡[−Ea(xN(a))],f_a(\mathbf{x}_{N(a)})=\exp[-E_a(\mathbf{x}_{N(a)})],

那么最大化它们的乘积就等价于最小化总能量

E(x)=∑aEa(xN(a)).E(\mathbf{x})=\sum_a E_a(\mathbf{x}_{N(a)}).

相应的算法通常称为最小和算法。

在树上,这些算法可以找到全局最优赋值。要恢复一个一致的赋值,通常需要存储局部取得最大值或最小值的选择,并沿图回溯。如果存在并列最优值,逐个变量独立地从其最大边缘函数中选择最优值,可能会得到彼此不相容的选择,因而无法恢复一致赋值。

一些熟知的算法都可以纳入这一框架:

  • 隐马尔可夫模型中的前向—后向推断,就是链上的和积计算。
  • 维特比算法是链式结构上的最大积或最大和计算。
  • 线性高斯模型支持用均值和精度矩阵表示的高斯消息;适当的链式模型可以得到卡尔曼滤波器的滤波和平滑算法。

这些运算还可以在代数层面上推广,从而得到用于计数、可行性判定及其他局部计算任务的相关算法。

树以外的精确推断

有环并不意味着无法进行精确推断,但通常需要计算成本更高的表示。变量消元法依次对变量求和消元,并在此过程中产生中间因子。其成本高度依赖于消元顺序和这些因子的作用域。

团树算法将若干变量组成的簇组织成树,使簇之间可以进行精确的消息传递。相关的结构性指标是树宽,通常在相应的变量交互图上度量。对于离散变量,计算量通常随所需最大簇的大小呈指数增长。

因此,看起来稀疏的因子图并不一定容易求解。过大的因子作用域、不利的连接结构或复杂的局部函数,都可能成为计算成本的主导因素。

应用与局限

因子图广泛应用于通信系统。在纠错码中,变量节点可以表示传输的比特,因子节点则表示奇偶校验约束。对于低密度奇偶校验码,这种表示通常称为坦纳图。迭代消息传递将信道提供的证据与约束结合起来,以估计传输的比特。

在机器学习和统计建模中,因子图用于表示结构化分布;在这类分布中,需要综合局部依赖关系来推断未观测变量。因子图也用于机器人学和估计问题,其中的因子可以编码测量、运动约束和先验信息。对于非线性最小二乘模型,图描述的是残差对变量的依赖关系,而求解使用的是数值优化,不一定是和积算法。

因子图的主要局限在于,清晰的因子分解本身并不能使推断在计算上变得易于处理。连续变量的消息可能是无法用有限形式精确表示的函数;实际方法因而会使用解析形式的函数族、离散化、采样或其他近似手段。强相互作用和大量的环可能使迭代推断变得不可靠。

此外,因子图只是描述模型,并不能验证模型是否正确。即使推断是精确的,遗漏依赖关系、不恰当的噪声假设或错误的局部因子,仍然属于建模错误。

历史发展

因子图借鉴了图模型、译码和局部计算领域的早期研究。坦纳图是编码理论中一个重要的先驱。弗兰克·R. 克西尚(Frank R. Kschischang)、布伦丹·J. 弗雷(Brendan J. Frey)和汉斯-安德烈亚·洛利格(Hans-Andrea Loeliger)在其2001年的论文《因子图与和积算法》(Factor Graphs and the Sum-Product Algorithm)中,对现代因子图框架及和积算法的表述作出了重要发展。这一表述帮助此前在概率推断、信号处理和纠错码等不同领域分别发展起来的算法建立了共同的描述语言。