马尔可夫随机场(MRF)是一组随机变量,其条件依赖结构由无向图描述。图中的每个顶点代表一个变量,而图的结构则指明:在已知某些变量的条件下,哪些变量组相互独立。其核心原理具有局部性:给定适当邻域内的变量后,一个变量便不再依赖更远处的变量。与马尔可夫链不同,随机场不必以时间为索引,也不必沿一条线排列;其变量可以分布在格点、地理地图、分子结构或任意网络上。
马尔可夫随机场将概率、图论和统计力学联系起来,可用于为存在相互作用的物理系统、空间观测数据、图像像素以及机器学习中的结构化输出建模。其数学意义在于揭示局部条件独立性与由局部相互作用项构成的全局分布之间的关系。实际应用中的难点则在于,简单的局部设定也可能产生复杂的全局行为,使归一化、推断和参数估计需要大量计算。
图与条件独立
设 为无向图, 为以其顶点为索引的一组变量。对于 ,记 ,并用 表示 的邻居集合。当 的联合概率分布满足由图所表达的相应条件独立关系时,就称该分布关于 具有马尔可夫性。三种标准表述分别对应成对、局部和全局性质。
成对马尔可夫性指的是:给定其余所有变量后,彼此不相邻的变量条件独立:
局部马尔可夫性指的是:一个顶点的邻居将它与图中其余部分隔开:
因此,给定其余所有变量时, 的全条件分布仅取决于其邻居。例如,在采用四邻接关系的图像网格中,一旦已知某个像素在水平方向和垂直方向上紧邻的像素,该像素变量就与其他所有像素条件独立。
全局马尔可夫性用图分离来表述。对于互不相交的顶点集 ,如果从 到 的每条路径都经过 ,就称集合 将 与 分离。全局马尔可夫性要求,只要满足这种分离关系,就有
全局马尔可夫性蕴含局部马尔可夫性,局部马尔可夫性又蕴含成对马尔可夫性。反向推导需要对分布作额外假设;特别地,对于有限乘积状态空间上的严格正分布,这些反向推导成立。正性之所以重要,是因为当某些配置的概率为零时,条件独立关系可能表现出不同的性质。
存在一条边并不一定意味着存在非零的边际相关关系,缺少一条边也不意味着具有边际统计独立性。在链 上,变量 和 被 分离,因此 ,但在未给定条件时,它们仍可能高度依赖。反过来,图中也可能包含一条多余的边,其对应的交互作用实际上并不存在。如果一个图所表达的分离关系对某个分布均成立,就称该图是该分布的独立性映射;只有当它刻画了所有相关的条件独立关系时,才称其为完美映射。
因此,“马尔可夫”一词描述的是条件依赖结构,而不是随时间演化的过程。有限随机场可以定义在任意无向图上,无须假设存在空间坐标、满足平稳性,或各顶点上的变量服从相同分布。此外,图本身也不是因果图:一条边表示可能存在的条件关联,而不是影响的方向或干预的结果。
团分解与吉布斯分布
团是一个顶点集合,其中任意两个顶点之间都有边相连。如果一个分布可以写成以下形式,就称它可以在无向图上因子分解:
其中, 是一组团, 是非负势函数, 用于使分布归一化。较小团上的因子可以并入极大团上的因子,因此采用任一种约定都可以。势函数通常不是概率分布:它的取值之和不必为一,也不必描述条件概率。
对于离散变量,配分函数为
对于连续变量,则将求和替换为相对于指定乘积参考测度的积分。只有在 时,模型才定义了一个概率分布。对于有限离散状态空间,配分函数的有限性很容易保证;但对于连续模型,即使每个因子的形式看起来都很合理,模型仍可能无法归一化。
哈默斯利–克利福德定理是连接图所表达的独立性与因子分解的核心桥梁。在标准的有限离散情形下,该定理指出:一个严格为正的分布相对于某个无向图具有马尔可夫性,当且仅当它可以在该图的团上因子分解。严格为正是指,对于乘积状态空间中的每一种配置,都有 。如果没有这一条件,图上的马尔可夫性质未必能推出团分解。反过来,只要团分解确实定义了一个概率分布,即使某些因子的取值为零,该分布也满足全局马尔可夫性质。
对于严格为正的势函数,定义团能量 。同一个模型便可写成
这就是玻尔兹曼分布,也称吉布斯分布。在物理学记号中,通常会将逆温度 显式写出,即 。统计模型则通常将 吸收到参数中。在总能量上加一个常数不会改变归一化后的分布,而且相互作用项有时也可以在因子之间重新分配。因此,联合分布并不能唯一确定势函数。
因子分解解释了局部条件分布为何相对简单。固定所有其他变量后,可得
所有不涉及 的因子都会被约去。剩余因子只涉及 及其邻居,由此得到局部马尔可夫性质。这种消去机制也是局部模拟与估计方法的基础。不过,根据局部条件分布构建模型时需要谨慎:任意给定的一组条件分布公式,未必能与同一个联合分布相容。
离散相互作用模型
最著名的离散例子是伊辛模型。每个变量都是一个自旋 ,其分布为
参数 控制相邻自旋之间的相互作用,而 是局部场。按照这里的符号约定,正的 倾向于使自旋取值相同,负的 则倾向于使其取值相反。这些变量不一定代表物理自旋,也可以表示统计模型中的二元标签、格点占据状态或两状态决策。
单个格点的条件分布可直接由能量得到:
因此,它具有逻辑斯蒂函数的形式。由成对相互作用构成的网络会产生类似逻辑回归的局部条件模型,但这些模型须满足相容性约束:在联合伊辛模型中,一条无向边对应的相互作用系数由该边的两个端点共用。分别独立拟合任意的逻辑回归模型,并不能自动得到一个相容的联合模型。
波茨模型将这种偏好取值相同的相互作用推广到 个标签。一种常见的统计形式为
这里, 是示性函数,而 表示特定格点对标签 的偏好。正的 会提高相邻格点标签相同时的权重。因此,该模型适用于空间分类问题:相邻位置通常预期属于同一类别,但局部观测可能提供与之相冲突的证据。对于两个标签的情形,通过适当的重新编码,可以将波茨模型与伊辛模型的参数化形式联系起来。
并非所有离散马尔可夫随机场都只有成对相互作用。如果图中包含一个三顶点团,该团的势函数就可能包含无法表示为一元项与成对项之和的相互作用。反过来,在不含三角形的图中,每个团至多包含两个顶点,因此,相对于该图满足马尔可夫性质的严格正分布具有成对因子分解。有时,加入辅助变量可以在扩展后的图上用成对相互作用替代高阶相互作用,但将这些辅助变量边缘化后,原始变量之间又可能出现高阶依赖。
取值为零的势函数表示硬约束,例如禁止相邻顶点同时被占据。在只允许单个格点发生变化的情况下,这些约束可能使模型的支持集不连通。这一区别在计算上十分重要:即使存在归一化的联合分布,每次只改变一个变量的采样器也可能无法在有效配置之间转移。相比之下,强但有限的惩罚仍会为每种配置保留正概率,不过,在彼此竞争的高概率区域之间转移仍可能极其缓慢。
高斯场与稀疏精度矩阵
高斯马尔可夫随机场是服从多元正态分布的随机向量,其条件独立关系由图表示。对于非奇异协方差矩阵 ,定义精度矩阵 。其概率密度为
图结构由 中的零元素刻画,而不是由协方差矩阵中的零元素刻画。具体而言,
这种严格的等价关系是高斯模型的一项独特优势。
全条件分布是一元正态分布,其中
只有与相邻顶点对应的元素才对条件均值有贡献。条件关联也可以用偏相关系数表示:
稀疏精度矩阵可以与稠密协方差矩阵并存:局部的直接依赖关系可以在整个连通图中产生长程的边缘依赖关系。
条件分布的设定必须满足对称性和正定性要求。假设某个空间模型设定的条件均值为 ,条件方差为 ,且总体均值为零。相容性要求
因此 。要得到可归一化的非奇异联合高斯分布,还要求 是正定矩阵。看似合理的邻域回归设定,也可能违反这两个条件中的任意一个。
一种常见的构造使用邻接矩阵 和对角度矩阵 。当参数取值使矩阵正定时,与 成正比的精度矩阵会产生局部空间依赖。在边界 处,图拉普拉斯矩阵 是奇异的:在每个连通分量上取常数值的向量,其二次型惩罚均为零。相应的内蕴高斯场在整个欧几里得空间上并不具有归一化的概率密度。可以通过施加约束(如零和条件)来处理它,也可以将其作为模型中的一个非正常分量,只要模型的后验分布是正常的。
其主要计算优势在于稀疏性。对 进行 Cholesky分解,可以在不显式构造稠密逆矩阵的情况下,实现高斯模拟、似然计算和线性方程组求解。不过,消元过程仍可能产生额外的非零元素,这称为填充,因此计算成本取决于图结构和顶点排序。因此,高斯场既是概率模型,也是稀疏数值线性代数的一个重要应用领域。
无限格点、边界条件与相变
在无限图上,全局表达式 通常不能按字面理解为通过对所有无限构型求和而得到的概率密度。总能量可能发散,而且构型空间上不存在均匀的计数概率测度。因此,无限体积模型改为通过有限区域上的条件分布来定义,其条件是各区域外部的构型。
对于有限顶点集 ,用 表示外部构型。局部吉布斯规范具有如下形式:
其中, 包含涉及该区域及其边界的相互作用。无限体积吉布斯测度是一种概率测度,其在各有限区域上的条件分布均与这些核一致。这些一致性要求称为多布鲁申–兰福德–吕埃勒方程。它们以条件概率来表述,而不是依赖单一的有限全局归一化因子。
即使将边界移至任意远处,边界条件仍可能影响内部。以无外场的铁磁伊辛模型为例,可以取越来越大的方盒区域,并将所有外部自旋固定为 ,也可以将其全部固定为 。在标准格点情形下,温度足够高时,这两种做法得到的极限分布相同。而在至少二维且温度足够低时,这两种构造可能产生不同的无限体积测度。此时,同一套局部相互作用规则便可支持不同的宏观相。
对于无限正方格点上具有均匀耦合能 的最近邻伊辛模型,临界逆温度满足
当 高于这一临界值,即温度较低时,零外场下存在正相和负相。这一结果凸显了局部规范与唯一确定的全局概率律之间的区别。相比之下,在一维最近邻链上,耦合有限时,任何正温度下都不会发生相变。
有限图上的有限状态模型,其配分函数是有限个正值项之和,每一项都是有限实值参数的解析函数。因此,它不会表现出无限体积相变所具有的那种热力学非解析性。不过,它仍可能表现出急剧的交叉过渡、多峰性以及极为缓慢的模拟过程。在临界点附近,相关性延伸至很远的距离,因此局部算法可能需要经过大量更新,才能使信息传遍整个系统。
这些问题也澄清了局部性的含义。局部马尔可夫性质并不保证长程依赖较弱、相关性迅速衰减,或无限体积分布具有唯一性。强相互作用可以通过任意长的中间顶点链传递依赖关系。保证唯一性或相关性衰减的条件,取决于相互作用强度、图的连通性、状态空间以及所用势函数族的具体形式。
精确推断与近似推断
推断是在马尔可夫随机场的结构和参数确定后,求解有关该模型的问题。常见任务包括计算边缘概率、求配分函数、抽取样本,以及寻找概率最大的配置。这些是不同的问题。最大后验估计求解的是
而边缘推断则需要对配置求和或积分。概率最大的联合配置,不一定等于分别选取每个变量边缘概率最大的状态所组成的向量。
在树上,置信传播通过局部消息计算精确的边缘分布。对于成对离散模型,从 传向 的消息为
消息沿两个方向传递完毕后,将局部势函数与传入的消息相乘,再进行归一化,即可得到每个顶点的边缘分布。若每个顶点有 个状态,算术运算量通常为 。类似的递推也可用于求出配分函数或概率最大的配置。
对于有环图,变量消元仍能给出精确结果,但会产生涉及多个变量的中间因子。计算成本取决于这些因子的规模,而这与树宽密切相关。联结树方法将变量组合成较大的簇,并在簇之间进行精确的消息传递。当状态数有界时,最坏情况下的复杂度随树宽呈指数增长,而不一定随顶点总数呈指数增长。稀疏图的树宽仍然可能很大,因此边数少本身并不能保证推断容易进行。
马尔可夫链蒙特卡洛提供了另一种方法。吉布斯采样反复从变量或变量块的完全条件分布中抽样。在满足适当的不可约性和常返性条件时,其平稳分布就是目标马尔可夫随机场的分布。局部条件分布的计算无需使用全局配分函数,但强依赖、硬约束以及彼此分离的模态都可能导致混合缓慢。对于某些自旋系统,簇更新可以大幅改善采样效果;而调温等方法则通过考虑不同温度下的分布来应对模态之间的势垒。
确定性近似方法在计算成本与精度之间进行权衡。变分推断在易于计算的分布族中搜索,通常以最小化某个KL散度为目标。平均场近似采用乘积分布,可能无法捕捉强依赖关系。有环置信传播将树上的更新方式应用于有环图;它可能表现良好,但一般情况下无法保证收敛性和结果的正确性。对于最大后验推断,满足次模性条件的一类特殊二元成对能量函数,可以通过图割进行精确最小化。一般离散马尔可夫随机场的推断在最坏情况下仍然是计算上难以处理的问题。
参数估计与图学习
学习马尔可夫随机场(MRF)可以指估计已知图上的相互作用强度,确定图中应包含哪些边,或同时学习结构与参数。在指数族参数化形式下,
其中, 汇集了描述相互作用的统计量。对于 个独立观测,对数似然为
求导可得矩匹配方程
因此,最大似然估计需要反复计算模型下的期望。 的二阶导数是充分统计量的协方差矩阵,因此 是凸函数。在可识别的指数族中,似然函数具有有利于优化的几何性质,但每次计算梯度仍可能需要进行困难的推断。蒙特卡洛似然方法通过模拟来近似模型期望;变分方法则用易于计算的近似来替代这些期望,这可能会改变最终得到的估计结果。
伪似然用各个全条件概率的乘积替代联合似然:
由于全局归一化因子在每个条件概率中都会约去,计算这一目标函数的代价通常要低得多。对于伊辛模型,其中各项都是逻辑斯蒂似然项。伪似然并非真正的联合似然,但在适当的抽样条件和正则条件下,它可以给出相合估计量。评估统计不确定性时,必须考虑其复合结构,而不能把所有条件概率项都当作相互独立的观测。
图学习还会带来额外的困难。在高维情形下,潜在边的数量可能超过观测数据所能可靠识别的范围。带稀疏惩罚的逐节点回归用于估计每个变量的邻域;随后还必须协调这些分别估计得到的邻域,例如取其并集或交集。要保证恢复出真实图结构,需要对信号强度、依赖关系、样本量和底层图结构作出假设。因此,拟合图中缺失的一条边,是基于模型作出的条件独立性判断,而不是无条件成立的经验事实。
对于高斯数据,一种重要的方法是图形套索。给定样本协方差矩阵 ,该方法通过求解以下问题来估计稀疏精度矩阵:
惩罚项促使非对角元素取零,从而得到稀疏图。这是一个凸优化问题,但最终选出的图取决于惩罚项、抽样假设和预处理。潜变量可能引入额外的观测变量间依赖关系:对未观测顶点进行边缘化,往往会在其邻居之间产生边。因此,从测量变量中学到的图,不一定能复现更大底层系统的图结构。
应用、相关模型与历史发展
统计力学为许多随机场模型提供了最初的研究背景。恩斯特·伊辛在1925年的分析中证明,一维最近邻模型在正温度下不存在相变;拉尔斯·昂萨格在1944年求解了零场二维模型,揭示了格点相互作用的丰富性质。后来,“马尔可夫随机场”这一名称强调的是条件依赖的局部性,而非某种特定的物理解释。与约翰·哈默斯利和彼得·克利福德相关的马尔可夫—吉布斯联系可追溯至他们1971年的工作,而朱利安·贝萨格1974年关于空间相互作用的论文,则推动了这些模型在空间统计学中的确立。
图像分析在20世纪80年代成为马尔可夫随机场的重要应用领域。像素或图像区域可以作为顶点,势函数则表示局部外观以及相邻标签之间的相容性。斯图尔特·格曼和唐纳德·格曼在1984年的工作将图像复原、吉布斯分布与随机松弛联系起来。在一个简单的去噪模型中,潜在的无噪声像素服从马尔可夫随机场先验分布,而观测到的含噪像素则提供似然因子。由此得到的后验分布兼顾数据拟合与空间上的规则性。成对平滑可以抑制孤立的错误,但过强的一致性项也可能抹去细小结构,并使边界变得模糊。
空间统计学使用类似的构造来处理行政区域、生态观测点以及不规则地图上的观测数据。高斯条件自回归模型通过地理邻接关系描述残差依赖;离散模型则通过适当的局部设定,表示随空间变化的类别或计数。在层次模型中,观测数据在给定潜在随机场后可以条件独立,尽管它们在边缘分布下仍然相互依赖。物理场方面的应用还利用了稀疏精度算子与离散化微分算子之间的关系。某些高斯过程可以用通过随机偏微分方程和有限元法离散化推导出的高斯马尔可夫随机场来近似。
在概率图模型中,马尔可夫随机场常与贝叶斯网络相对照,后者利用有向无环图将一个分布分解为条件概率的乘积。无向模型适合表示对称的相容性约束,有向模型则适合表达按一定顺序进行的条件生成过程。二者用图表达独立性的方式并不相同。例如,无屏蔽的有向碰撞结构可以表示某些独立性关系,而任何无向图都无法精确表示这些关系。对有向图进行道德化可以得到便于推断的无向图表示,但可能会丢失部分独立性信息。
条件随机场直接对给定观测 时的结构化输出 建模:
其归一化因子取决于观测输入,而其图上的马尔可夫假设涉及给定该输入时输出变量之间的关系。约翰·拉弗蒂、安德鲁·麦卡勒姆和费尔南多·佩雷拉于2001年以“条件随机场”之名引入这一模型,此后它在序列标注和其他结构化预测任务中发挥了重要作用。线性链条件随机场与隐马尔可夫模型类似,可以采用动态规划,同时允许势函数依赖广泛的观测上下文,而无须为观测指定生成分布。