深入解析隐马尔可夫模型：全面攻略指南

时间：11-18 民间故事提交错误

考虑下面的交通灯示例，序列可能是红-红/橙-绿-橙-红。该序列可以绘制为状态机。不同的状态根据这个状态机相互交替。每个状态仅取决于前一个状态。如果当前灯为绿色，则下一盏灯为橙色。这是一个确定性系统。因此，只要知道这些状态转换，就更容易理解和分析。但实践中仍存在许多不确定的制度。

在日常生活中，我们总是希望根据当前的天气状况来预测未来的天气状况。与上面的交通灯例子不同，我们不能依靠现有的知识来确定天气状况的变化，但我们仍然希望得到天气预报。模型。一种方法是假设模型的每个状态仅取决于先前的状态。这种假设称为马尔可夫假设，可以大大简化问题。显然，这个假设也是一个非常糟糕的假设，导致很多重要信息丢失。

谈到天气，马尔可夫假设被描述为假设如果我们知道前几天的天气信息，那么我们就可以预测今天的天气。当然，这个例子也有些不切实际。然而，这样一个简化的系统可以有利于我们的分析，所以我们通常接受这个假设，因为我们知道这样的系统会让我们获得一些有用的信息，尽管不是很准确。

在谈论HMM时，我们首先简单介绍一下马尔可夫过程。它以俄罗斯数学家安德烈·马尔可夫的名字命名，代表数学中具有马尔可夫性质的离散随机过程。在这个过程中，每次状态转换只依赖于之前的n个状态。这个过程称为n 阶模型，其中n 是影响过渡态的数量。最简单的马尔可夫过程是一阶过程，每个状态的转移仅取决于其之前的状态。请注意，这与确定性系统不同，因为转换是概率性的，而不是确定性的。

马尔可夫链是随机变量X1,…,Xn 的序列。这些变量的范围，即它们所有可能值的集合，称为“状态空间”，Xn的值就是n时刻的状态。如果过去状态Xn+1 的条件概率分布只是Xn 的函数，则

这里x是过程中的某个状态。上述恒等式可以看作是马尔可夫性质。

马尔可夫链在许多应用中发挥着重要作用。例如，Google使用的网页排名算法（PageRank）就是由马尔可夫链定义的。

下图显示了天气示例中所有可能的一阶转换：

请注意，具有N 个状态的一阶过程有N2 个状态转换。每次转移的概率称为状态转移概率，即从一种状态转移到另一种状态的概率。所有这些N2个概率都可以用一个状态转移矩阵来表示，其表达式如下：

该矩阵有以下约束：

以下是海藻示例的状态转移矩阵：

这个矩阵的意思是，如果昨天是晴天，那么今天有50%的机会是晴天，37.5%的机会是多云，12.5%的机会是下雨。显然，矩阵中每一行的和都是1。

为了初始化这样的系统，我们需要一个初始概率向量：

该向量表明第一天是晴天。

至此，我们为上面的一阶马尔可夫过程定义了以下三个部分：

状态：晴、阴、雨

初始向量：定义系统在时间0时的状态概率

状态转换矩阵：每次天气转换的概率

所有可以用这种方式描述的系统都是马尔可夫过程。

然而，当马尔可夫过程不够强大时我们该怎么办呢？在某些情况下，马尔可夫过程不足以描述我们希望发现的模式。

例如，一个隐居的人可能无法直观地观察天气状况，但民间传说告诉我们，海藻的状态与天气状况有一定的概率相关。在这种情况下，我们有两组状态，一组可观察的状态（海藻的状态）和一组隐藏的状态（天气条件）。我们希望找到一种能够根据海藻状况和马尔可夫假设来预测天气状况的算法。

一个更现实的例子是语音识别。我们听到的声音是声带、喉等发声器官共同作用的结果。这些因素相互作用来决定每个单词的声音，而语音识别系统检测到的声音（可观察状态）是由人体内的各种物理变化产生的（隐藏状态，延伸一个人真正想要表达的内容）。

一些语音识别设备将内部发音机制视为隐藏状态序列，并将最终声音视为与隐藏状态序列非常相似的可观察状态序列。在这两个例子中，非常重要的一点是隐藏状态的数量和可观察状态的数量可能不同。在具有3 种状态（晴天、阴天、雨天）的天气系统中，可以观察到4 种湿度水平（干燥、干燥、潮湿、潮湿）。在语音识别中，一段简单的语音可能只需要80个语素来描述，但内部的发音机制可以产生少于80种或多于80种不同的声音。

在上述情况下，可观察状态序列和隐藏状态序列在概率上相关。然后，我们可以将此类过程建模为具有隐马尔可夫过程和一组与隐马尔可夫过程概率相关的可观察状态。这就是本文重点讨论的隐马尔可夫模型。

隐马尔可夫模型是一种统计模型，用于描述具有隐藏未知参数的马尔可夫过程。困难在于从可观察的参数中确定过程的隐含参数，然后使用这些参数进行进一步的分析。下图是三态隐马尔可夫模型状态转移图，其中x表示隐藏状态，y表示可观测输出，a表示状态转移概率，b表示输出概率。

下图展示了天气示例中隐藏状态和可观察状态之间的关系。我们假设隐藏状态是一个简单的一阶马尔可夫过程，并且它们中的任何两个都可以相互转换。

对于HMM来说，有以下三个重要的假设，尽管这些假设是不现实的。

假设1：马尔可夫假设（状态形成一阶马尔可夫链）

假设2：不动性假设（状态与具体时间无关）

假设3：输出独立性假设（输出仅与当前状态相关）

隐藏状态和可观察状态之间存在概率关系。也就是说，假设P(O1|H)，某个隐藏状态H有可能被认为是可观察状态O1。如果存在三个可观察状态，则显然P(O1| H)+P(O2| H)+ P(O3| H)=1。

这样，我们还可以得到另一个矩阵，称为混淆矩阵。这个矩阵的内容是某个隐藏状态被观察到几个不同可观察状态的概率。以天气为例，这个矩阵如下：

上面的图都强调了HMM的状态变化。下图清晰地展示了模型的演变过程。绿色圆圈代表隐藏状态，紫色圆圈代表可观察状态，箭头代表状态之间的依赖概率。 HMM可以使用5元组{N,M,,A,B}表示，其中N表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值，M表示可观察状态的数量，其中通过训练集可以得到，={i} 为初始状态概率，A={aij} 为转移矩阵Pr(xt(i)| ,Pr(ot(i)| xt(j))。状态转移矩阵和混淆矩阵中的概率是与时间无关的，即这些矩阵不会随着系统演化而随时间变化，对于固定N和M的HMM，使用={,A,B}。来表示HMM 参数。

在正常的马尔可夫模型中，观察者可以直接看到状态。这样，状态的转移概率就是所有的参数。在隐马尔可夫模型中，状态不是直接可见的，但受状态影响的一些变量是可见的。每个状态在可能的输出符号上都有一个概率分布。因此，输出符号的序列可以揭示有关状态序列的一些信息。

HMM中存在三个典型问题：

(1) 给定模型参数，计算给定可观测状态序列的概率

假设我们已经有一个特定的隐马尔可夫模型和一组可观察的状态序列。我们可能想知道给定所有可能的隐藏状态序列的给定可观察状态序列的概率。当给出以下隐藏状态序列时：

那么在HMM和这个隐藏状态序列的条件下，可观察状态序列的概率为：

HMM条件下隐藏状态序列的概率为：

因此，隐藏状态序列和可观测状态序列的联合概率为：

那么可观察状态序列在所有可能的隐藏状态序列上的概率为：

例如，我们可能有海藻的“夏季”模型和“冬季”模型，因为海藻的状态在夏季和冬季应该是不同的，而我们现在要根据一系列可观察状态（潮湿或不潮湿）来判断海藻）现在是夏天还是冬天。

我们可以使用前向算法计算特定HMM下可观测状态序列的概率，然后据此找到最可能的模型。

这种类型的应用通常发生在语音识别中，我们通常使用许多HMM，每个HMM 都针对一个特定的单词。从可听单词向前获得可观察状态序列，然后可以通过找到满足该可观察状态序列的最大概率的HMM 来识别该单词。

先介绍一下前向算法（Forward Algorithm）

如何计算可观察序列的概率？

1. 穷举搜索

给定一个HMM，我们想要计算某个可观察序列的概率。考虑天气示例，我们知道一个描述天气和海藻状态的HMM，并且我们还有一系列海藻状态。假设这种状态下的三天是（干燥、潮湿、湿透）。这三天的每一天，天气可能是晴天、阴天或雨天。我们可以用下图来描述观察序列和隐藏序列：

该图中的每一列代表天气的一种可能状态，每个状态都指向相邻列中的每个状态。每个状态转换在状态转换矩阵中都有一个概率。每列下方是当天可观测海藻的状态，每个状态中出现这种可观测状态的概率由混淆矩阵给出。

计算可观察概率的一种可能方法是找到每个可能的隐藏状态的序列。有32=27种。此时可观测序列的概率为Pr(干燥，潮湿，潮湿| HMM)=Pr(干燥，潮湿，潮湿| 晴朗，晴朗，晴朗) + 。 + Pr(干燥、潮湿、潮湿|下雨、下雨、下雨)。

显然，这种计算的效率是很低的，特别是当模型中的状态很多或者序列很长的时候。事实上，我们可以利用概率不随时间变化的假设来减少时间开销。

2.使用递归降低复杂度

我们可以考虑递归计算给定HMM 的可观察序列的概率。我们可以首先定义一个部分概率，表示达到某个中间状态的概率。接下来我们将了解如何在time=1 和time=n (n 1) 时计算这些部分概率。

假设时间段T 的可观测序列为：

1) 部分概率

下图表示观察序列的一阶转变（干燥、潮湿、潮湿）

我们可以通过计算到达中间状态的所有路径的概率之和来计算到达该状态的概率。例如，在时间t=2时，阴天的概率用三个路径的概率之和来表示：

我们用t(j) 表示在时间t 处于状态j 的概率，t(j)=Pr(观测状态| 隐藏状态j) x Pr(在时间t 到状态j 的所有路径)。

最后观察到的状态的部分概率表示整个序列到达某个状态的所有可能路径的概率之和。例如，在本例中，最后一列的部分状态是通过以下路径计算的：

因为最后一列的部分概率是所有可能路径的概率之和，所以它是给定HMM下该观察序列的概率。

2）计算t=1时的偏概率

当t=1 时，没有到达某个状态的路径，因此这里是初始概率Pr(state j | t=0)=(state j)，这样我们就可以计算t=1 时的部分概率为：

因为在初始阶段，状态j的概率不仅与状态本身有关，还与观察状态有关，所以这里使用混淆矩阵的值，k1代表第一个观察状态，bjk1代表第一个观察状态隐藏状态是j，但是观察变成k1的概率。

3）计算t1时的部分概率

我们来看一下部分概率的计算公式：t(j)=Pr（观测状态| 隐藏状态j）x Pr（在时间t 到状态j 的所有路径）。这个公式的左边是从混淆矩阵中知道的，我只需要计算右边，这显然是所有路径的总和：

需要计算的路径数量与观测序列长度的平方有关，但之前所有路径在t时刻的部分概率已经计算出来，所以在t+1时刻只需要计算基于时间t 的概率：

这里简单解释一下，bjk(t+1) 是在时间t+1 时第j 个隐藏状态被认为是当前观察状态的概率。后一部分是从t时刻的所有隐藏状态到t+1时刻的隐藏状态的隐藏状态。 j 的转移概率之和。这样，我们每一步的计算都可以使用上一步的结果，节省大量的时间。

4）公式推导

5）降低计算复杂度

我们可以比较穷举算法和递归算法的复杂性。假设有一个具有n 个隐藏状态的HMM，并且我们有一个长度为T 的观察序列。

穷举算法需要计算所有可能的隐藏序列：

需要计算：

显然，穷举算法的时间成本与T索引即NT有关。如果采用递归算法，由于我们每一步都可以使用上一步的结果，所以它与T线性相关，即复杂度为N2T。

我们这里的目的是计算给定HMM 下可观察序列的概率。我们通过首先计算部分概率来递归地计算整个序列中所有路径的概率，这大大节省了时间。 t=1时，使用初始概率和混淆矩阵的概率，t时刻的概率可以使用t-1时刻的结果。

这样，我们就可以递归地计算所有可能路径的概率之和。最后，所有偏概率的计算公式为

以天气为例，计算t=2时刻多云状态的概率方法如下：

我们使用前向算法来计算给定HMM 的可观察序列的概率。前向算法主要采用递归思想，利用之前的计算结果。通过这个算法，我们可以在一堆HMM中找到一个最能满足当前可观察序列的模型（前向算法计算出的概率是最高的）。

(2) 根据可观察状态序列找到最可能的隐藏状态序列

与上面的问题类似，但更有趣的是从可观察序列中找到隐藏序列。在许多情况下，我们对隐藏状态更感兴趣，因为它们包含无法直接观察的有价值的信息。例如，在海藻和天气的例子中，隐居者只能看到海藻的状态，但他想知道天气的状态。这时，我们可以利用维特比算法，根据可观测序列来获得最优的可能隐藏状态序列。当然，前提是已经有HMM了。

维特比算法广泛使用的另一个领域是自然语言处理中的词性标注。句子中的单词是可观察的，词类是隐藏状态。通过根据句子的上下文找到单词序列在句子中最可能的隐藏状态序列，我们就可以得到单词的词性（最可能的）。所以我们可以利用这些信息来做一些其他的工作。

我们先来介绍一下维特比算法（Viterbi Algorithm）

一。如何找到最可能的隐藏状态序列？

通常我们有一个特定的HMM，然后根据一个可观察状态序列来寻找最有可能生成这个可观察状态序列的隐藏状态序列。

1. 穷举搜索

我们可以在下图中看到每个隐藏状态和可观察状态之间的关系。

通过计算所有可能的隐藏序列的概率，我们可以找到最大化Pr（观察序列|隐藏状态集）的最可能的隐藏序列。例如，对于上图中的可观察序列（干湿湿透），最可能的隐藏序列是以下概率中最大的：

Pr(干燥、潮湿、潮湿| 晴天、晴天、晴天), Pr(干燥、潮湿、潮湿| 下雨、下雨、下雨)

该方法可行，但计算量大。与前向算法一样，我们可以利用转移概率的时间不变性来降低计算复杂度。

2.使用递归降低复杂度

给定一个可观察序列和一个HMM，我们可以考虑递归地寻找最可能的隐藏序列。我们可以首先定义一个部分概率，它是达到某个中间状态的概率。接下来我们将讨论如何计算t=1 和t=n (n1) 的部分概率。

注意，这里的部分概率与前向算法中的部分概率不同。这里的部分概率表示在t时刻最有可能到达某个状态的路径的概率，而不是所有概率的总和。

1）部分概率和部分最优路径

考虑下图和可观察序列的一阶转换（干燥、潮湿、潮湿）

对于每个中间状态和最终状态(t=3)，都有一条最可能的路径。例如，时间t=3 时的三个状态都有以下最可能的路径：

我们可以将这些路径称为部分最优路径。这些部分最优路径都有一个概率，即部分概率。与前向算法中的部分概率不同，这里的概率只是一条最可能路径的概率，而不是所有路径的概率之和。

我们可以用(i, t) 来表示在所有可能的序列（路径）中，在时间t 状态i 的概率最高的序列的概率。部分最优路径是达到该最大概率的路径。对于每个时刻的每个状态都有这样一个概率和部分最优路径。

最后，计算t=T时刻各状态的最大概率和部分最优路径，选择概率最大的状态及其部分最优路径，得到全局最优路径。

2）计算时间t=1时的部分概率

当t=1时，到达某个状态的最可能路径还不存在，但我们可以直接使用t=1时某个状态的概率以及从该状态到可观察序列k1的转移概率：

3）计算t1时刻的部分概率

接下来我们可以根据t-1时刻的偏概率求出t时刻的偏概率

我们可以计算到达状态X的所有路径的概率，并找到其中最可能的路径，即局部最优路径。这里注意，到X的路径在t-1时刻必须经过A、B和C，所以我们可以使用之前的结果。最有可能到达X 的路径是以下三种路径之一：

（状态序列）， A, X（状态序列）, B, X（状态序列）,C、X

我们需要做的就是找到以AX、BX 和CX 结尾的最可能路径。

根据一阶马尔可夫假设，一个状态的出现与前一个状态相关，因此X出现在序列末尾的概率仅取决于前一个状态：

Pr（到A 的最佳路径）。 Pr(X|A) 。 Pr（观察状态|X）

通过这个公式，我们可以利用t-1时刻的结果以及状态转移矩阵和混淆矩阵的数据：

通过推广上面的表达式，我们可以得到计算第i 个状态的最大概率的公式，其中t 时刻的可观测状态为kt：

其中aji表示从状态j转移到状态i的概率，bikt表示状态i被观察为kt的概率。

4）向后指针

考虑下面的图片

每个中间状态和最终状态都有一个部分最优概率(i,t)。但我们的目标是找到最可能的隐藏状态序列，因此我们需要一种方法来记住部分最优路径的每个节点。

考虑到计算t时刻的偏概率，我们只需要知道t-1时刻的偏概率，因此只需要记录t时刻概率最大的状态即可。也就是说，任何时候，系统都必须处于下一时刻产生最大概率的状态。如下图：

我们可以用一个向后指针来记录导致某个状态局部概率最大的前一个状态，即

这里argmax表示可以最大化下面公式的j值。还可以发现，这个公式与t-1时刻的偏概率和转移概率有关，因为后向指针只是为了寻找“我从哪里来？”这个问题与可观察状态无关，所以这里不需要乘混淆矩阵因子。全局行为如下所示：

5）优点

使用维特比算法解码可观察状态有两个重要的优点：

a) 通过使用递归降低复杂度，与之前的前向算法相同

b) 根据可观测序列可以找到最优隐藏序列。其计算公式为：

在

这是一个从左到右翻译的过程。使用先前的翻译结果来获得后续的结果。起点是初始向量。

3、补充

但当序列中某处存在噪声干扰时，某些方法可能与正确答案相差甚远。但维特比算法会查看整个序列以确定最有可能的终止状态，然后使用向后指针来查找先前的状态，这对于忽略孤立噪声非常有用。

维特比算法提供了一种基于可观察序列计算隐藏序列的非常有效的方法。它使用递归来降低计算复杂度，并使用之前的所有序列进行判断，可以很好地容忍噪声。

在计算过程中，该算法计算每个时刻每个状态的部分概率，并使用向后指针记录当前状态的最大可能的先前状态。最后，最可能的终止状态是隐藏序列的最后一个状态，然后使用向后指针找到整个序列的所有状态。

(3)根据观察到的序列集找到最有可能的HMM。

在很多实际情况下，HMM无法直接判断，这就成为一个学习问题，因为对于给定的可观测状态序列O，没有办法准确找到一组最优的HMM参数最大化P(O | )，所以人们寻求解决方案使其局部最优，前向-后向算法（也称为Baum-Welch 算法）成为HMM 学习问题的近似解。方法。

前向-后向算法首先对HMM的参数进行初始估计，但这很可能是错误的猜测，然后通过评估这些参数对于给定数据的有效性并减少它们造成的误差来更新HMM。使给定训练数据的误差更小的参数。这其实就是机器学习中梯度下降的思想。

对于网格中的每个状态，前向-后向算法不仅计算达到该状态的“前向”概率，还计算生成该模型最终状态的“后向”概率。通过前面的介绍，这些概率可以通过递归来使用。执行有效的计算。这些中间概率可以通过使用近似HMM模型参数来调整，这些调整构成了前向和后向算法迭代的基础。

另外，前向-后向算法是EM算法的特例。它避免了EM算法的暴力计算，采用动态规划的思想来解决问题。 Jelinek 在他的书《Statistical Methods for Speech Recognition》中比较了前向-后向算法和EM 算法。书中对其中的关系进行了详细的描述，有兴趣的读者可以参考本书。

与上面提到的前向算法类似，我们也可以定义后向变量t(i) 来计算给定当前隐藏状态i 的部分观测序列ot+1, ot+2, oT 的概率，即：

与前向算法类似，我们也可以通过迭代算法有效地计算t(i)。计算公式如下：

在

进一步我们可以发现

所以

让我们从前向-后向算法开始。

首先我们需要定义两个辅助变量。这两个变量可以使用前面介绍的前向变量和后向变量来定义。

第一个变量定义为时间t时状态i和时间t+1时状态j的概率，即

该变量在网格中所表示的关系如下所示：

这个方程相当于

利用前向变量和后向变量，上式可表示为

第二个变量定义为后验概率，即给定观测状态序列和HMM 的情况下，状态i 在时间t 的概率，即

利用前向变量和后向变量，上式可表示为

因此，下式是任意时刻状态i的期望，即从状态i转变到观察状态o的期望

同样，下式是从状态i转移到状态j的期望

我们可以发现定义的两个变量之间的关系为

下面介绍前向-后向算法的参数学习过程。在学习过程中，HMM的参数不断更新以最大化P(O | )。我们假设初始HMM 参数为={,A,B}，首先计算前向变量和后向变量，然后根据刚刚介绍的公式计算期望xi 和，最后根据以下三次重估计公式更新HMM参数。

如果我们将当前的HMM模型定义为={,A,B}，那么这个模型就可以用来计算上面三个方程的右边；然后我们将重新估计的HMM 模型定义为

，那么上述三个方程的左端就是重估后的HMM模型参数。 Baum 和他的同事在20 世纪70 年代进行了演示

，所以如果我们迭代计算上述三个方程，不断重新估计HMM的参数，那么经过多次迭代我们就可以得到HMM模型的最大似然估计。但需要注意的是，前向-后向算法得到的最大似然估计是局部最优解。

参考：

1.http://blog.csdn.net/eaglex/article/details/6376826

2. http://en.wikipedia.org/wiki/Markov_chain

3.http://en.wikipedia.org/wiki/Hidden_Markov_model

4. Lawrence R. Rabiner，隐马尔可夫模型教程

nd Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989. 5. L. R. Rabiner and B. H. Juang, “An introduction to HMMs,”IEEE ASSP Mag., vol. 3, no. 1, pp. 4-16, 1986. 6. http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html

关于深入解析隐马尔可夫模型：全面攻略指南和的介绍到此就结束了，不知道你从中找到你需要的信息了吗？如果你还想了解更多这方面的信息，记得收藏关注本站。