图模型与和积算法

图模型综述

概率在信号处理领域中扮演着重要的角色,很多问题的建模都需要引入概率(如贝叶斯模型),因而很多问题的求解也表现为对一些概率分布的计算(如计算参数的后验概率)。再复杂的概率计算都是对以下两个规则的重复应用:贝叶斯公式($ P(A, B) = P(A)P(B | A) $)和边缘概率求取公式($ P(A) = \sum_{B} P(A, B) $ )。但当问题变得复杂之后,涉及到的变量会变多、概率模型会变得复杂,因而寻找一种简便直观的分析概率分布的方法就变得重要起来。

图模型(Graphical Models)就是一种用来刻画变量之间的概率依赖关系的方法,它由节点和边组成,节点代表的是各个随机变量,边则代表不同随机变量之间的关系。多变量的概率分布的一些局部特征可以很直观地在图模型中显示出来,同时复杂的概率运算也可以通过一些与图有关的操作来完成,因而我们可以借助图模型来设计新的模型以及推导出更高效的算法。

图模型一般分为两种,一种是贝叶斯网络(Bayesian Networks),其边是有向的,它可以用来表示各随机变量之间的因果关系;另一种是马尔可夫随机场(Markov Random Fields),其边是无向的,它一般用来表示多个随机变量之间所满足的约束关系。下面我们将具体讲述这两种图模型。


贝叶斯网络

考虑一个简单的关于三个变量的联合概率分布 $ p(a, b, c) $,根据贝叶斯公式,我们可以写出

我们可以将该概率分解以一个有向图来表示,如下图所示。其中每个节点代表一个随机变量,有向箭头则表示该概率分解中的条件依赖关系,即如果随机变量 $ A $ 依赖于某个随机变量集合 $ {\cal S} $,则 $ {\cal S} $ 中的每一个随机变量对应的节点均会发射出一条有向箭头指向随机变量 $ A $ 所对应的节点(如下图中,$ a $ 指向 $ b $,$ a $、$ b $ 指向 $ c $)。

三个变量的联合概率分布的贝叶斯网络示意图

上面的这种对概率分布的表示方法即为贝叶斯网络。对于更一般的概率分布,例如 $ K $ 个随机变量的联合分布 $ p(x_1, \cdots, x_K) $, 我们总可以根据链式法则将其分解为一系列条件概率的乘积:

将上述分解用贝叶斯网络来表示,可以得到一个具有全连接(fully connected)的有向图,即每个节点都有来自编号比其小的节点的进入边,使得任意两个节点之间都有边相连。

式(2)中的分解代表了一种最一般的形式,对节点之间的关系没有任何假设,因而其对应的贝叶斯网络也是最复杂的。而在实际的建模中,我们或多或少会有一些关于不同随机变量之间的先验信息,因而概率分解会较式(2)简单,反映在贝叶斯网络中即是有向边的减少,有向边的减少又可以进一步促进我们对模型的认识以及简化问题的求解过程。

多个变量的联合概率分布的贝叶斯网络示意图

例如上图表示了随机变量 $ (x_1, \cdots, x_7) $ 的联合分布对应的贝叶斯网络,可以看到,该有向图不是全连接的,我们可以根据该图写出这些变量的联合概率分布

更一般地,我们可以根据任意一个贝叶斯网络写出所有节点对应的随机变量的联合概率分布为

其中 $ \text {pa}_k $ 为节点 $ x_k $ 的所有父节点构成的集合(某个节点的父节点指其入边所连接的节点)。

注意到,贝叶斯网络都是有向无环图(Directed Acyclic Graphs,DAG),因为我们总可以按照某种方式将各随机变量排序,使得序位高的随机变量仅仅只“直接”依赖于序位低的随机变量。


条件独立

条件独立是多变量概率分布中的一个非常重要的概念,其在分析概率模型、简化模型结构、降低图模型中的推断问题的计算复杂度等方面均扮演着重要的角色。考虑三个随机变量 $ a $,$ b $ 和 $ c $,假设给定 $ b $ 和 $ c $ 的值之后的 $ a $ 的条件概率分布为

即给定 $ b $ 和 $ c $ 之后,$ a $ 并不依赖于 $ b $ 的值,我们称在给定 $ c $ 的值的情况下,$ a $ 和 $ b $ 条件独立,并且我们将这条性质简记为

给定式(6),我们还可以写出

在知道了某个联合概率分布所对应的贝叶斯网络之后,我们希望能找到任意随机变量集合之间的条件独立关系,d-separation 定理可以帮助我们从贝叶斯网络中很快地找到上述条件独立关系。在介绍 d-separation 定理之前,我们先来看一下最简单的可以表征随机变量间的条件独立关系的三个基本贝叶斯网络单元。

三个基本的贝叶斯网络单元

tail-to-tail 贝叶斯网络单元

第一个贝叶斯网络单元如上图所示,我们关心的是在给定 $ c $ 的值的情况下 $ a $ 和 $ b $ 的条件独立性,因而我们根据 $ c $ 所处的地位将该网络称为 tail-to-tail 网络单元(因为连接它的两条边皆为发射边,对应有向箭头的尾部)。可以根据上图写出 $ p(a, b, c) $ 的形式为

我们首先看一下随机变量 $ a $ 和 $ b $ 是否是独立的,为此,可以写出 $ a $ 和 $ b $ 的联合分布为

可见,$ a $ 和 $ b $ 并不独立,我们可以记为 $ a \not\perp b | \emptyset $ ($ \emptyset $ 代表空集)。再来看给定 $ c $ 的值的情况下 $ a $ 和 $ b $ 的条件独立性,写出 $ p(a, b | c) $ 的形式为

上式的形式符合条件独立的定义,因而有 $ a \perp b | c $。

我们再来用一种直观的方式来从上图中来阐释各随机变量之间的关系,$ a $ 由 $ c $ 生成,$ b $ 也由 $ c $ 生成,即 $ a $ 和 $ b $ 是“同源”的,因而它们必然是相关的;另一方面,在给定 $ c $ 的值之后,生成的 $ b $ 仅与 $ c $ 相关,生成的 $ a $ 也仅与 $ c $ 相关,这就说明了 $ a $ 和 $ b $ 在给定 $ c $ 的情况下条件独立。我们还可以将上图这样理解,在没有观察到 $ c $ 的值时,节点 $ a $ 和节点 $ b $ 之间是有路径“相通”的(如上图左所示),从而 $ a $ 和 $ b $ 相关;但一旦观察到 $ c $ 的值,$ a $ 和 $ b $ 之间的通路被“阻塞”(如上图右所示,带阴影的节点表示该节点被观察到,下同),从而有 $ a $ 和 $ b $ 对于 $ c $ 条件独立。

第二个贝叶斯网络如下图所示,是一个链式的形式,我们根据 $ c $ 所处的地位将该网络称为 head-to-tail 网络单元。

head-to-tail 贝叶斯网络单元

根据上图可分别写出 $ p(a, b, c) $,$ p(a, b) $ 和 $ p(a, b | c) $ 的形式为

可以得出 $ a \not\perp b | \emptyset $,$ a \perp b | c $。这种形式的贝叶斯网络所代表的概率模型在涉及到时间序列的建模的时候应用广泛,例如一阶马尔可夫模型,它比无记忆系统传达的信息更多,又保留了简单易处理的特性。和第一个网络单元类似,我们称在没有观察到 $ c $ 的值时,节点 $ a $ 和节点 $ b $ 之间是“相通”的(如上图左所示),从而 $ a $ 和 $ b $ 相关;但一旦观察到 $ c $ 的值,$ a $ 和 $ b $ 之间的通路即被“阻塞”(如上图右所示),从而有 $ a $ 和 $ b $ 对于 $ c $ 条件独立。

最后来看第三个贝叶斯网络单元,如下图所示,我们称其为 head-to-head 网络单元。

head-to-head 贝叶斯网络单元

我们还是根据上图分别写出 $ p(a, b, c) $,$ p(a, b) $ 和 $ p(a, b | c) $ 的形式

可以得出 $ a \perp b | \emptyset $,$ a \not\perp b | c $。这个性质正好和上面两个贝叶斯网络单元的性质相反。为方便理解,举一个不恰当的例子,假设 $ a $ 是某次测验的难度,$ b $ 是某学生的能力,$ c $ 是该学生在该次测验的成绩,随机变量 $ a $ 和 $ b $ 一般来讲是独立的,它们共同决定了 $ c $ 的分布,因而我们可以用上图来表示 $ a $,$ b $,$ c $ 之间的关系;当我们观测到 $ c $ 的值之后,例如该学生在本次测验中的成绩很高,我们又以某种方式得知了 $ a $ 的值,例如该次测验的难度非常高,那么 $ b $ 的取值显然是与 $ a $ 有关的,在这里该学生的能力必须非常强才可以。同前面一样,我们可以定义一套从图中就可以得出的条件独立性质:当没有观察到 $ c $ 的值时,节点 $ a $ 和节点 $ b $ 之间是“阻塞” 的(如上图左所示),从而 $ a $ 和 $ b $ 独立;而当观察到 $ c $ 的值后,节点 $ a $ 和节点 $ b $ 之间的路径被“打通”(如上图右所示),因而 $ a $ 和 $ b $ 对于 $ c $ 条件相关。

d-separation 定理

假设 $ A $,$ B $ 和 $ C $ 是某一个贝叶斯网络中的三个非相交的节点集合,那么 d-separation 定理可以用来判定下列条件独立性质是否成立:$ A \perp B | C $。在一个贝叶斯网络中,任何一个局部单元都符合我们前面所讲述的三个基本的贝叶斯网络单元的形式,而通过这些基本的贝叶斯网络单元,我们可以看到哪些路径是“阻塞”的或“连通”的。d-separation 定理则基于以上特点来判定任意两个节点之间的所有可能的路径是否是“阻塞”的,若集合 $ A $ 中的任意节点到集合 $ B $ 中的任意节点之间的路径均是“阻塞”的,则称 $ A $ 与 $ B $ 相对于 $ C $ 是 d-separated 的,同时有 $ A \perp B | C $。

我们称集合 $ A $ 中的某节点到集合 $ B $ 中的某节点之间的某条路径是“阻塞”的,如果该路径满足以下两个条件之一:

  1. 路径中的有向箭头在某个节点处符合 head-to-tail 或者 tail-to-tail 的形式,且该节点在集合 $ C $ 中;
  2. 路径中的有向箭头在某个节点处符合 head-to-head 的形式,且该节点以及该节点的所有子孙节点均不在集合 $ C $ 中。

为方便理解,考虑下图中的例子。

d-seperation 举例

先看上图左,我们要判定 $ a \perp b | c $ 是否成立,即需要判定 $ a $ 到 $ b $ 之间的路径是否是“阻塞”的,$ a $ 到 $ b $ 需要经过 $ e $ 和 $ f $。可以看到有向箭头在节点 $ e $ 处符合 head-to-head 的形式,而该节点的后代 $ c $ 被观测到,因而 $ a $ 到 $ b $ 之间的路径在节点 $ e $ 处是“相通”的,再看有向箭头在节点 $ f $ 处符合 tail-to-tail 的形式,而该节点 $ f $ 并不在观测集合中,因此 $ a $ 到 $ b $ 之间的路径在节点 $ f $ 处也是“相通”的,综合可知,$ a $ 到 $ b $ 之间的路径是“相通”的,故可以得出 $ a \not\perp b | c $ 。

再来看上图右,此时要判定 $ a \perp b | f $ 是否成立,判定方式同上。有向箭头在节点 $ e $ 处符合 head-to-head 的形式,且该节点及其后代 $ c $ 均不在观测集合中,因此 $ a $ 到 $ b $ 的路径在节点 $ e $ 处被“阻断”,事实上 $ a $ 到 $ b $ 的路径在节点 $ f $ 处也是“阻断”的,但判断某条路径是否被“阻断”仅需判断一处“阻断”即可。故可以得出 $ a \perp b | f $ 。


马尔可夫随机场

另一种可以用来表示多个变量的概率分布的模型为马尔可夫随机场,同贝叶斯网络不同,它是一个无向图,且它对于表示不同随机变量集合之间的条件独立性质更加直观。在马尔可夫随机场中,若随机变量集合 $ A $ 中的任意节点到随机变量集合 $ B $ 中的任意节点之间的通路都需要经过随机变量集合 $ C $ 中的某一节点,则有 $ A \perp B | C $,如下图所示,可直观理解为 $ C $ 中观测到的变量会坍缩到一个确定的状态,从而会阻塞图中 $ A $ 到 $ B $ 的通路,导致 $ A $ 和 $ B $ 变得不相干。

条件独立在 MRF 中的表示

如何根据马尔可夫场写出对应的随机变量集合的联合分布呢?我们首先定义一下 clique 的概念:若一个节点集合中的所有节点之间均有边连接,则称该节点集合为一个 clique。根据此性质,我们可以得出一个 clique 中不含任何条件独立的性质,即在一个 clique 中找不出三个不相交的子集 $ A $,$ B $,$ C $,使得 $ A \perp B | C $ 成立。因而,我们可以认为每个 clique 都对应一个关于该 clique 中所有随机变量的函数,而最终的所有变量的概率分布可以写成这些函数的乘积。不失一般性,我们一般选取一个无向图中所有的最大 clique (所谓最大 clique,是指对于某个 clique,不可能再向其中加入新的节点,而使得到的新的节点集合保持 clique 全连接的性质),因为其他较小的 clique 所对应的函数总是可以被某个最大 clique 所对应的函数所吸收。我们将某个最大 clique $ C $ 所对应的函数称为势能函数(potential function),并以 $ \psi_C({\bf x}_C) $ 来表示。则所有变量的联合概率分布可以写为

其中,$ Z $ 为归一化常量。由于两个不相连的节点必然在两个不同的 clique 中,因此式(17)总是可以将该两个节点对应的随机变量分布在两个不同的因子中,从而在某种程度上完美地反映了马尔可夫随机场所表征的变量之间的条件独立性。

我们可以将贝叶斯网络转换成马尔可夫随机场,对于只包含 tail-to-tail 或 head-to-tail 节点(即每个节点仅有一个父节点)的贝叶斯网络,直接将有向边替换成无向边即可,这一点可以从 tail-to-tail 单元和 head-to-tail 单元的概率表达式推断出来;而对于含有 head-to-head 节点的贝叶斯网络,我们除了需要把该网络中的有向边替换成无向边之外,还需要将该节点的所有父节点两两相连,因为该单元的概率表达式为 $ p(x_k | \text {pa}_k) $,该函数包含了该节点和其所有的父节点,且一般不可再分解,因而该节点和其所有的父节点构成一个 clique。

贝叶斯网络和马尔可夫随机场各具优势,但无论是贝叶斯网络还是马尔可夫随机场,都不能完美的表征所有可能的概率分布,贝叶斯网络擅长处理结构层次比较明显的条件概率性质;而马尔可夫随机场可以处理稍微复杂点的条件概率性质,但其对于一些简单的条件概率性质却不能表征出来(例如贝叶斯网络中的 head-to-head 节点单元,在对应的马尔可夫随机场中,这些节点表现为全连接,丧失了所有条件独立性质)。我们应当根据具体的问题场景来选用合适的图模型。


和积算法与最大和算法

和积算法(sum-product algorithm)是基于图模型的一类非常强大且普适的算法,它可以高效地根据一个由多个因式构成的关于多个变量的函数来计算出一些局部函数(譬如求取某些随机变量的边缘分布)。信号处理领域的很多经典算法都可以归结为和积算法(或最大和算法)的特例,例如前向-后向算法(forward/backward algorithm),Kalman 滤波,Viterbi 算法,FFT 算法等等。

在介绍和积算法之前,我们要先介绍因子图(factor graphs),其是推演和积算法的关键。

因子图

不管是在贝叶斯网络中还是在马尔可夫随机场中,一个概率分布函数都可表示为如下式所示的一系列因式的乘积

其中 $ {\bf x}_{\cal S} $ 为所有随机变量集合的一个子集,每个因子 $ f_{\cal S} $ 为随机变量子集 $ {\bf x}_{\cal S} $ 的函数。我们可以将变量(variables)和因子(factors)均作为节点表示在一张图中,并以无向边连接以上两类节点,用来表征因子和变量的对应关系(若某个因子是关于某个变量的函数,则该变量对应的节点与该因子对应的节点之间应有一条无向边连接),这种图被称为因子图,有时候也被称为二分图(bipartite graphs),因为它包含两类节点且无向边仅存在于两类节点之间。

例如,某个概率分布可以写成如下因子的分解形式

其因子图如下图所示

因子图示例

该因子图中实际上包含了一个“环路”($ f_a \to x_2 \to f_b \to x_3 \to f_a $),而要在一个因子图中精确地推断某些边缘分布或其他有意义的量是需要因子图中是不包括“环路”的(cycle-free),我们可以通过重组某些因子的方式来“去环”,例如在上图中,我们可以将 $ f_a $ 和 $ f_b $ 合并成一个新的因子,但这样会损失一些有用的信息。

大多数情况下,我们都可以根据贝叶斯网络或者马尔可夫随机场得到一个无环的因子图,这样我们就可以在该因子上运行和积算法或者最大和算法以得到我们想要求得的量。

和积算法

给定一个关于多变量的概率分布以及该概率分布的一个因式分解,和积算法可以用来高效地求解某个变量子集的边缘概率分布。和积算法的本质就是充分地利用原始概率分布的因式分解(因子图),以及合理地交换求和与求积的顺序(消息传递),来尽可能地减少计算开销。

不失一般性,假设要求解随机变量 $ x $ 的边缘分布 $ p(x) $,可以写为

其中 $ {\bf x} \backslash x $ 表示除了 $ x $ 之外的其他所有变量,下图显示了无环因子图中包含 $ x $ 的部分。

和积算法推导1

我们根据上图可以将概率分布 $ p({\bf x}) $ 写为

其中 $\text {ne}(x) $ 是因子图中所有与变量节点 $ x $ 相邻的因子节点,而 $ X_s $ 是与 $ x $ 相邻的某个因子节点 $ f_s $ 除了 $ x $ 以外的其他变量节点及它们的后代所构成的集合,$ F_s(x, X_s) $ 则表示排除 $ f_s \to x $ 的通路外与因子 $ f_s $ 有关的所有因子所构成的函数。将式(21)代入式(20)中,并交换求和与求积的顺序,可得

这里我们引入了函数 $ \mu_{f_s \to x}(x) $,定义为

我们可以将 $ \mu_{f_s \to x}(x) $ 视作因子节点 $ f_s $ 向变量节点 $ x $ 传递的消息(message),而 $ p(x) $ 等于变量节点 $ x $ 的所有相邻因子节点向其传递的消息的乘积。因为这个原因,和积算法也被称为消息传递算法(message-passing algorithms)。

下面,我们再来将 $ F_s(x, X_s) $ 做进一步地分解。

和积算法推导2

如上图所示,它可以被分解为

$ x_1, \cdots, x_M $ 是因子节点 $ f_s $ 除去 $ x $ 之外的其他所有相邻变量节点,$ G_m(x_m, X_{sm}) $ 表示上图中阴影部分所代表的函数,即排除 $ x_m \to f_s $ 通路外与 $ x_m $ 有关(有简单路径可以由 $ x_m $ 出发到达的变量)的所有变量所组成的函数。将式(24)代入式(23)可得

其中 $ \text {ne} (f_s) \backslash x $ 表示除开 $ x $ 外与因子节点 $ f_s $ 相邻的变量节点;$ \mu_{x_m \to f_s } $ 为另一类消息,是由变量节点传递至因子节点的消息,定义为

可以注意到,我们定义的在因子图的某一条边上传递的这两类消息(因子节点传递至变量节点的消息 $ \mu_{f \to x}(x) $ 以及变量节点传递至因子节点的消息 $ \mu_{x \to f}(x) $)都只是关于这条边所连接的变量节点 $ x $ 的函数。另一方面,由式(25)可知,某一因子节点想要向某一变量节点传递消息前,须接受到来自该因子节点的其他相邻变量节点向该因子节点传递的消息。

为给出消息 $ \mu_{x_m \to f_s } $ 的确切表达式,我们需推导 $ G_m(x_m, X_{sm}) $ 的表达式。根据下图可以写出

和积算法推导3

上式中的 $ F_l(x_m, X_{ml}) $ 表达式和式(24)是一致的。我们将式(27)代入式(26)中,并交换求和与求积的顺序,可得

上式中用到了消息 $ \mu_{f \to x}(x) $ 的定义式(23)。所以,要计算某个变量节点传递给某个因子节点的消息,只需要计算该变量节点的其他因子节点传递给该变量节点的消息的乘积即可。

在变量节点或因子节点是叶子节点的情况下,变量叶子节点传递给相邻因子节点的消息为 $ \mu_{x \to f}(x) = 1 $,因子叶子节点传递给相邻变量节点的消息为 $ \mu_{f \to x}(x) = f(x) $。

有了这两类消息的计算公式(25)和(28)后,我们可以根据式(22)计算出某个因子图中任意变量的边缘概率分布,这就是和积算法。

一般,当需要计算某个变量的边缘分布时,我们会将该变量作为根节点,然后从叶子节点开始计算消息,直至计算出所有该变量节点的相邻因子节点传递给该变量节点的消息为止,若因子图中的边的个数为 $ K $,则计算开销为 $ O(K) $。如果要分别计算 $ N $ 个变量的边缘分布,我们可以遵从以上方法分别计算每个变量的边缘分布,计算开销为 $ O(NK) $,但这样会有很多重复计算量,某些边上的消息会计算多次。在这种情况下,我们倾向于将每一条边上两个方向上的消息提前计算好,这样任意变量的边缘分布都可以很方便的计算出,且计算开销仅为 $ O(K + N) $,这一点也充分地利用了动态规划算法的核心思想。

下面举一个详细的例子,来说明和积算法的运行过程。

和积算法举例

对于上图中的因子图,我们可以分 5 步计算出所有边上的消息函数(步骤编号也在上图中标明),计算过程如下:

第一步

第二步

第三步

第四步

第五步

最终求出各变量的边缘分布为

最大和算法

在多变量概率模型中,另一个经常被求解的问题是使得 $ p(\bf {x}) $ 最大的变量序列 $ \bf {x} $ 的取值以及对应的最大概率。一种常见的误区是首先通过和积算法求解出使得每个变量的边缘概率最大所对应的变量取值,这些变量的组合就对应于上述问题的解,但使得各变量的边缘概率的乘积最大并不意味着使得所有变量的联合分布概率最大。因而我们寻求其他的算法来解决上述问题,与和积算法思路相似的最大和算法(max-sum algorithm)是一种对该问题高效的解决方法。

和积算法利用的是乘法对加法的分配律,最大和算法则利用的是乘法对“最大”操作符的分配律:

其中 $ a \geq 0 $,这一条件在我们求解的问题中是满足的。这一性质使得我们可以在适当的时候交换“最大”操作符和求积运算。

为避免求取多个概率函数的乘积而导致的“下溢”(underflow)问题,我们通常先对概率函数求取对数,这样式(29)对应的对数版本为

此时,上式中的 $ a $,$ b $,$ c $ 都对应于对数概率,“最大和算法”的名字也是由式(30)的结构而来。

同和积算法一样,我们也可以根据因子图写出对应的两类消息的表达式,且利用这些消息来计算最大概率。不同的地方是将求和变成了求“最大”,同时之前的概率相乘变成了对数概率相加:

当变量节点或因子节点为叶子节点时,变量叶子节点传递给其相邻因子节点的消息为 $ \mu_{x \to f} = 0 $,因子叶子节点传递给其相邻变量节点的消息为 $ \mu_{f \to x} = \ln f(x) $。

指定根节点为 $ x $ 时,最大概率可以由下式求出

我们还需要求解使得 $ p({\bf x}) $ 最大的 $ \bf x $,由式(33)可知,根节点对应的随机变量的取值应为

怎样求取其他的随机变量的取值呢?一种很容易想到的方法是再从根节点出发,求取因子图各边反向传播的消息函数,然后再利用式(34)分别得到各随机变量的取值。这种方法实际上是有问题的,因为可能有多个使得 $ p({\bf x}) $ 最大的 $ \bf x $ 序列,而利用上述方法求取的各个随机变量的取值是分散且不成体系的,它们组合起来可能并不对应于一个可行解(例如有两个可行解 $ {\bf x}_A $ 和 $ {\bf x}_B $,利用上述方法求解出来的解中的部分随机变量的取值来自于 $ {\bf x}_A $,部分随机变量的取值来自于 $ {\bf x}_B $ ),这也是最大和算法区别于和积算法的特点之一。

为解决上述问题,我们在利用式(31)计算因子节点 $ f $ 传递至变量节点 $ x $ 的消息时,保留一份使得式(31)中的项取得最大值的 $ x_1^{\text {max} }, \cdots, x_M^{\text {max} }$。这样在求取出 $ x^{\text {max} } $ 的值后,我们从存储的数据中取出 $ x^{\text {max} } $ 对应的序列 $ x_1^{\text {max} }, \cdots, x_M^{\text {max} }$,依此规律进行操作,最终可以得出一个可行的使得 $ p({\bf x}) $ 最大的序列 $ {\bf x}^{\text {max} } $。这种预先存储可能用到的数据并在需要时快速查找它们的方法被称为“回溯”法(back-tracking)。

最大和算法的一个主要应用是在隐马尔可夫模型(Hidden Markov Models)中,给定特定的观测序列,求解隐含变量序列最有可能取得的状态,对应的算法为 Viterbi 算法。