《统计学习方法》——隐马尔可夫模型(上)

引言

这是《统计学习方法》第二版的读书笔记，由于包含书上所有公式的推导和大量的图示，因此文章较长，正文分成三篇，以及课后习题解答，在习题解答中用Numpy实现了维特比算法和前向后向算法。

---

1. 《统计学习方法》——隐马尔可夫模型(上)
2. 《统计学习方法》——隐马尔可夫模型(中)
3. 《统计学习方法》——隐马尔可夫模型(下)
4. 《统计学习方法》——隐马尔可夫模型#习题解答#

隐马尔可夫模型(Hidden Markov Model,HMM)是描述隐藏的马尔可夫链随机生成观测数据过程的模型。

前置知识

马尔可夫链

马尔可夫链(Markov chain)又称离散时间马尔可夫链，使用$t$来表示时刻，用$X_t$来表示在时刻$t$链的状态，假定所有可能状态组成的有限集合$\mathcal{S}$称为状态空间。

马尔可夫链为状态空间中从一个状态到另一个状态的转换的随机过程。

在马尔可夫链的每一步，根据概率分布，可以从一个状态变到另一个状态，也可以保存当前状态。状态的概率叫做转移，状态改变的概率相关的概率就转移概率。

描述当前状态为$i$，下一个状态为$j$的转移概率$p_{ij}$定义为：
$$p_{ij}=P(X_{t+1}=j|X_t=i),i,j\in \mathcal{S}$$
马尔可夫链的核心假设是，只要时刻$t$的状态为$i$，不论过去发生了什么，也不论链是如何到达状态$i$的，下一个时刻转移到状态$j$的概率就一定是状态转移概率$p_{ij}$。即，该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，与时间序列上它前面的事件无关。这种无记忆性称为马尔可夫性质。在数学上表示为：
$$P(X_{t+1}=j|X_t=i,X_{t-1}=i_{n-1},\cdots ,X_0=i_0)=P(X_{t+1}=j|X_t=i)=p_{ij}$$
转移概率$P_{ij}$一定是非负的，且和为1：
$$\sum _j{p}_{ij}=1$$
下一个状态可能和当前状态一样，即状态没有发生变化，我们也认为状态发生了一次特殊的转移(自身转移)。

总结一下，一个马尔可夫链模型由以下特征确定:

1. 状态集合$\mathcal{S}$；
2. 可能发生状态转移$(i,j)$的集合，即由所有$p_{ij}>0$的$(i,j)$组成；
3. $p_{ij}$的取值为正；

马尔可夫链可以由转移概率矩阵所刻画，它是一个简单的二元矩阵，其第$i$行第$j$列的元素为$p_{ij}$，假设共有$m$个状态：
$$\left[\begin{array}{cccc}{p}_{11}& p_{12}& \cdots & p_{1m}\\ p_{21}& p_{22}& \cdots & p_{2m}\\ ⋮& ⋮& ⋮& ⋮\\ p_{m1}& p_{m2}& \cdots & p_{mm}\end{array}\right]$$
也可以用转移概率图表示马尔可夫链，图中用节点表示状态，连接节点的(有向)弧线表示可能发生的转移，将$p_{ij}$的数值标记在相应的弧线旁边。

比如下面来自维基百科的一个例子，它表示一个具有两个状态转换的马尔可夫链：

图p1 马尔可夫链的例子 来自维基百科

概率图模型

概率图模型(probabilistic graphical models)是概率分布的图形表示，它非常方便我们分析模型的性质，尤其是条件独立性质。
和我们数据结构中学的图一样，一个图由节点、节点间的边组成。概率图模型中，每个节点表示一个随机变量，边表示这些变量之间的概率关系，缺失的边表示条件独立假设。

概率图主要分为两大类：有向图模型，也称为贝叶斯网络(实际上和贝叶斯关系不大)；无向图模型，也称为马尔可夫随机场(名字也没那么直观)。

这里主要简单介绍下有向图模型，因为HMM可以通过它进行表示。它的一些概念有助于后面的公式推理。

首先介绍下 条件独立(conditional independence, CI) 的概念。
我们先来回顾下独立的概念，假设有两个随机变量$a,b$相互独立的话，有
$$p(a,b)=p(a)p(b)$$
如果此时求给定$b$的条件下$a$的概率：
$$p(a|b)=\frac{p(a,b)}{p(b)}=\frac{p(a)p(b)}{p(b)}=p(a)\text{\hspace{1em}(p1)}$$
即不管$b$的取值如何，都不影响$a$发生的概率。也可以说$a$条件独立于$b$。

现在假设有三个变量$a,b,c$，假设给定$b,c$的条件下$a$的条件分布不依赖于$b$的值，即
$$p(a|b,c)=p(a|c)\text{\hspace{1em}(p2)}$$
也就是说，在给定$c$的条件下，$a$条件独立于$b$。在给定$c$的条件下，$b$作为条件的取值不会影响$p(a|c)$。

我们考虑将$p(a,b|c)$展开：
$$p(a,b|c)=p(a|b,c)p(b|c)=p(a|c)p(b|c)\text{\hspace{1em}(p3)}$$

$(p2)$和$(p3)$都是在这种情况下条件独立的不同描述。
注意条件独立中的条件二字，比如这里都是在以$c$为条件的前提下，而且是对于$c$的所有取值都成立。
记为
$$a\perp b|c$$
表示给定$c$的条件下$a$和$v$条件独立。

我们以此为基础再来看下马尔可夫链，假设$x_{t+1}\perp x_{1:t-1}|x_t$，即下一时刻仅依赖于当前时刻，和所有的之前时刻无关，这就是(一阶)马尔可夫假设。

基于该假设，结合链式法则，$x_{1:N}$的联合概率分布可以写成：
$$p(x_{1:N})=p(x_1)\prod _{t=2}^{N}p(x_t|x_{1:t-1})=p(x_1)\prod _{t=2}^{N}p(x_t|x_{t-1})\text{\hspace{1em}(p4)}$$
这就是一阶马尔可夫链。这里说的一阶是什么意思？说的$x_t$仅依赖于$x_{t-1}$，如果是二阶，则依赖于$x_{t-1},x_{t-2}$。相当于假设要弱一点，但带来的复杂性也高一点。那最强的假设是什么，朴素贝叶斯假设，所有的$x_t$之间是相互独立的。

前面说概率图模型是概率分布的图形表示，那么它如何表示概率分布呢？

考虑三个变量$a,b,c$的联合分布$p(a,b,c)$，此时我们不对这些变量做出任何的假设，通过概率的乘积规则，可以将联合概率分布写成：
$$p(a,b,c)=p(c|a,b)p(a,b)=p(c|a,b)p(b|a)p(a)\text{\hspace{1em}(p5)}$$
此时，我们引入图模型来表示上面等式的右侧。首先我们为每个随机变量引入一个节点，然后为每个节点关联上式右侧对应的条件概率，然后，对于每个条件概率分布，我们在图中添加一个链接(箭头)，箭头的起点是条件概率中条件的随机变量对应的节点。结果就是图p2中的图。

图p2 有向图模型的例子

可以看到，这个图描述了联合概率分布$p(a,b,c)$在所有随机变量上能分解成一组因子的乘积的方式，每个因子只依赖于随机变量的一个子集。
比如对于因子$p(a)$，没有输入的链接，也就没有箭头指向它。而对于因子$p(c|a,b)$，存在从节点$a,b$到节点$c$的链接。
这里我们说节点$a$是节点$b$的父节点，节点$b$是节点$a$的子节点。这种关系和数据结构中的图一致。

这里要注意的是，我们隐式地选择了一种顺序来分解$p5$，不同的顺序会对应不同的分解方式，也得到不同的图表示。

我们看到，在图的所有节点上定义的联合概率分布由每个节点上的条件概率分布的乘积表示，每个条件概率分布的条件都是图中节点的父节点所对应的变量。因此，对于一个有$K$个节点的图，联合概率为：
$$p(x)=\prod _{k=1}^{K}p(x_k|p{a}_k)\text{\hspace{1em}(p6)}$$
其中$p{a}_k$表示$x_K$的父节点的集合； x = { x 1 , ⋯ , x K } \pmb x=\{x_1,\cdots,x_K\} x={x1​,⋯,xK​}。这个公式非常重要，表示有向图模型的联合概率的分解(factorization)属性。图中每个节点还可以关联一个变量的集合。

有向图的独立性质

有了这些概念，下面我们来看条件独立相关的图表示，我们以三个变量$a,b,c$的图模型为例。
三个变量$a,b,c$之间的有向图连接对应三个经典的例子，我们先来看第一个。如图p3所示：

图p3

根据$(p6)$，我们可以写出这个图的联合概率分布：
$$p(a,b,c)=p(c)p(a|c)p(b|c)\text{\hspace{1em}(p7)}$$

该结构为同父结构，即节点$a,b$存在相同的父节点$a$。当父节点$c$被观测到时，$a,b$条件独立。

考虑没有变量是观测变量的情形，即我们通过对$(p7)$两边进行积分或求和的方式，来考察$a$和$b$是否为相互独立的，即
$$p(a,b)=\sum _{c}p(c)p(a|c)p(b|c)\text{\hspace{1em}(p8)}$$
这通常不能分解为乘积$p(a)p(b)$的形式，因此我们说：

$$a/\perp b|\varnothing$$

这里$\varnothing$表示空集，符号$/\perp$表示条件独立性质不总是成立。

现在假设我们以变量$c$为条件(或者说观测到变量$c$，即$c$取了特定值，不再是一个随机变量)，得到的图如p4所示。

图p4

我们为上图中的节点添加阴影部分，如节点$c$所示，表示它被观测到了。

我们可以写成给定$c$的条件下，$a$和$b$的条件概率分布，并结合$(p7)$：
$$p(a,b|c)=\frac{p(a,b,c)}{p(c)}=\frac{p(c)p(a|c)p(b|c)}{p(c)}=p(a|c)p(b|c)$$
因此，我们可以得到条件独立性质(回顾$(p3)$)：

$$a\perp b|c$$
这里节点$c$被关于关于从节点$a$经过节点$c$到节点$b$路径的尾到尾(tail-to-tail)，因为节点与两个箭头的尾部相连。
这样的一个连接节点$a$和节点$b$的路径的存在(从箭头头部到尾部的路径是通的)使得节点相互依赖。
然而，当我们观测到节点$c$，或者说以$c$为条件时，被当做条件的节点$c$阻隔了从$a$到$b$的路径，使得$a$和$b$变成(条件)独立了。

路径的阻隔表示条件独立！

我们再来看第二个例子，如图p5所示：

图p5

该结构称为顺序结构。当$c$被观测到时，$a,b$条件独立。

这幅图的联合概率分布通过$(p6)$得到，形式为：
$$p(a,b,c)=p(a)p(c|a)p(b|c)\text{\hspace{1em}(p9)}$$
与之前一样，我们对$c$积分或求和来考察$a$和$b$是否互相独立：
$$p(a,b)=p(a)\sum _{c}p(c|a)p(b|c)$$
这一般也不能分解为$p(a)p(b)$，因此
$$a/\perp b|\varnothing$$
现在以节点$c$为条件，再利用公式$(p9)$：
$$\begin{array}{rl}p(a,b|c)& =\frac{p(a,b,c)}{p(c)}\\ & =\frac{p(a)p(c|a)p(b|c)}{p(c)}\\ & =\frac{p(a,c)p(b|c)}{p(c)}\\ & =p(a|c)p(b|c)\end{array}$$
我们再次得到了条件独立性质：
$$a\perp b|c$$
节点$c$被称为关于从节点$a$到节点$b$的路径的头到尾(head-to-tail)。这样的一个连接节点$a$和节点$b$的路径的存在使得节点相互依赖。如果我们观测节点$c$，如图p6所示，这个观测阻隔了从$a$到$b$的路径，因此我们得到了条件独立性质。

图p6

最后，我们考虑第三个例子，也是最难理解的例子。如图p7所示：

图p7

V型结构，也称冲状撞结构。当$c$未被观测，或者说$c$未知的情况下，$a,b$相互独立。当$c$被观测到，$a,b$必不独立。

这里提到了给定和未知。基于条件概率$p(A|B)$，指事件$A$在事件$B$已经发生条件下的发生概率。事件$B$是已经发生的，即给定的、观测到的；事件$A$的发生是以概率形式表现的，$A$是否发生是未知的。

同样，我们可以得到联合概率分布：
$$p(a,b,c)=p(a)p(b)p(c|a,b)\text{\hspace{1em}(p10)}$$
对上式两侧关于$c$积分或求和，得到：
$$p(a,b)=p(a)p(b)$$
因为$p(c|a,b)$是关于$c$的条件分布，也是一种概率分布，对$c$求和或积分结果为$1$。

这样，我们得到了和之前不一样的结果，当没有变量被观测时，$a$和$b$是独立的。我们可以把这个结果写成：
$$a\perp b|\varnothing$$

图p8

那么，假设我们还是以$c$为条件，如图p8所示，有：
$$p(a,b|c)=\frac{p(a,b,c)}{p(c)}=\frac{p(a)p(b)p(c|a,b)}{p(c)}$$
这通常也不能分解为$p(a)p(b)$，因此，
$$a/\perp b|c$$
图形上来看，我们说节点$c$关于从$a$到$b$的路径是头到头(head-to-head)。当$c$没有被观测到时，它阻隔了路径，使得变量$a$和$b$是相互独立的。当以$c$为条件时，路径被解除阻隔，使得$a$和$b$相互依赖了。

特别地，我们考虑下图p9这种情形。是V型结构的延伸，其中新节点$d$是节点$c$的孩子节点，但该结构中仅$d$被观测到，那么$a$和$b$也会被解除阻隔。其实，不仅是$c$的直接孩子节点$d$，当$c$或$c$的任意后继(descendant)节点被观测到，都会使得$a$和$b$解除阻隔。

图p9

怎么证明呢？

我们还是先写出概率分布：
$$p(a,b,c,d)=p(a)p(b)p(c|a,b)p(d|c)$$

假设观测到$d$，我们考虑$a,b$是否是条件独立的。
$$\begin{array}{rl}p(a,b|d)& =\sum _{c}p(a,b,c|d)\\ & =\sum _c\frac{p(a,b,c,d)}{p(d)}\\ & =\sum _c\frac{p(a)p(b)p(c|a,b)p(d|c)}{p(d)}\\ & =\sum _c\frac{p(a)p(b)p(c|a,b)p(d|c,a,b)}{p(d)}\\ & =\sum _c\frac{p(a)p(b)p(d,c|a,b)}{p(d)}\\ & =\frac{p(a)p(b)p(d|a,b)}{p(d)}\\ & \ne p(a)p(b)\end{array}$$

这里用到了$d,c,a$和$d,c,b$满足上面描述的顺序结构，即$p(d|a,b,c)=p(d|c)$。

我们再考虑相反的情况，假设未观测到$d$，有：
$$p(a,b,c,d)=p(a)p(b)p(c|a,b)p(d|c)$$
对上式两侧关于$d$积分或求和，得到：
$$p(a,b,c)=p(a)p(b)p(c|a,b)$$
再关于$c$积分或求和：
$$p(a,b)=p(a)p(b)$$

同样，当没有变量被观测到时有：

$$a\perp b|\varnothing$$

可以看到在未观测到$d$的情况下，$a,b$还是互相独立的。这和节点$c$的性质是一样的。反之，在观测到$d$的情况下，联合概率不能分解成$p(a)p(b)$。

我们可以以一个例子来简单理解，假设你家装了一个偷窃报警器，当家里遭窃或地震都有可能触发这个偷窃报警器响，而当报警器响的情况下，邻居听到后可能给你打电话。

图p10

地震与否不会被你家是否遭窃影响。这里也假设小偷不管有没有地震，都不影响他进行偷窃。此时，这两个事件在报警响未被观测到的情况下，就是独立的。

假设你正在外度假，邻居给你打电话说你家报警器响了。那么从邻居打电话这个事件我们可以得到警报响这个事件发生了。

最后，我们总结成一个图：

图p11

再重申一次，若$a$到$b$的路径被阻隔，说明它们是(条件)独立的。

基于上面的三个例子，下面我们引入一个非常重要的概念D-划分(D-Separation)，也称为有向分离，或D-分离。

D-划分

图模型的一个重要且优雅的特征是，联合概率分布的条件独立性可以直接从图中读出来，不用进行任何计算。完成这件事的一般框架就是d-划分，d表示有向。

考虑一个一般的有向图，其中$A,B,C$是任意无交集的节点集合。我们考虑从$A$中任意节点到$B$中任意节点的所有可能的路径，我们说这样的路径被阻隔，如果它包含一个节点满足下面两个性质中的任意一个：

• 路径上的箭头以头到尾或尾到尾的方式交汇于这个节点，且这个节点在集合$C$中；
• 箭头以头到头的方式交汇于这个节点，且这个节点和它的所有后继都不在集合$C$中；

如果所有的路径都被阻隔，我们说$C$把$A$从$B$中d-划分开，且图中所有变量上的联合概率分布都满足$A\perp B|C$。

图p12

如图p12所示。尾到尾是红线表示，头到尾是黑线表示，都交汇于集合$C$中；而头到头方式交汇的节点，不在集合$C$中。

我们再通过一个例子来理解一下，例子来自PRML。

图p13 来自PRML

在p13左图中，从$a$到$b$的路径是通的，首先对于$a\to e\to f$的路径，这是一个头到头结构，虽然$e$未被观测到，但$e$的后继$c$被观测到，因此这条路径是通的，然后对于$e\to f\to b$的路径，这是尾到尾结构，且$f$没有被观测到，没有被$f$阻隔；

在p13右图中，从$a$到$b$的路径被节点$e$和$f$阻隔，对于$a\to e\to f$的路径，$e$和$e$的后继没有被观测到(没有在条件集合中)，$a$到$f$是被阻隔的；同时对于$e\to f\to b$来说，是一个尾到尾结构，且$f$被观测到。因此使用这幅图进行分解的任何概率分布都满足条件独立性质$a\perp b|f$。

下面我们来看如何用概率图来表示隐马尔科夫模型。

隐马尔可夫模型图示

假设针对顺序观测数据，基于一阶马尔可夫假设，即每个观测只与最近的一次观测有关，我们就得到了一阶马尔科夫链(马尔科夫模型)，$N$次观测的序列的联合分布为：
$$p(x_{1:N})=p(x_1)\prod _{t=2}^{N}p(x_t|x_{1:t-1})=p(x_1)\prod _{t=2}^{N}p(x_t|x_{t-1})$$
该一阶马尔可夫链用概率图表示如图p14所示：

图p14

再进一步，如果引入额外的潜在变量$z_n$，假设潜在变量也构成了马尔可夫链，得到的图结构称为状态空间结构(state space model)，如图p15所示。它满足下面的条件独立性质，即在给定$z_n$的条件下，$z_{n-1}$和$z_{n+1}$是独立的，有：
$$z_{n+1}\perp z_{n-1}|z_n\text{\hspace{1em}(p11)}$$

图p15

这个模型的联合概率分布为
$$p(x_1,\cdots ,x_N,z_1,\cdots ,z_N)=p(z_1)\left[\prod _{t=2}^{N}p(z_t|z_{t-1})\right]\prod _{t=1}^{N}p(x_t|z_t)\text{\hspace{1em}(p12)}$$
根据d-划分准则，我们看到总存在一个路径通过潜在变量连接了任意两个观测变量$x_n$和$x_m$，并且这个路径永远不会被阻隔。对于观测变量$x_{n+1}$来说，给定所有之间的观测，条件概率分布$p(x_{n+1}|x_{1:n})$不会表现出任何的条件独立性，因为对$x_{n+1}$的预测依赖于所有之前的观测。

对于顺序数据来说，如果潜在变量是离散的，那么这个图描述的就是隐马尔可夫模型。

隐马尔可夫模型的基本概念

隐马尔可夫模型的定义

定义 10.1(隐马尔可夫模型) 隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列(状态序列,state sequence)，然后由每个状态生成一个观测从而产生随机观测序列(observation sequence)的过程。序列的每一个位置又可以看作是一个时刻。

隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定，模型概率图示如图1所示，模型的形式定义为：

图1 HMM的概率图

设$Q$是所有可能的状态的集合，$V$是所有可能的观测的集合：
Q = { q 1 , q 2 , ⋯ , q N } , V = { v 1 , v 2 , ⋯ , v M } Q=\{q_1,q_2,\cdots,q_N\},\qquad V=\{v_1,v_2,\cdots,v_M\} Q={q1​,q2​,⋯,qN​},V={v1​,v2​,⋯,vM​}
其中$N$是可能的状态数，$M$是可能的观测数。

$I$是长度为$T$的状态序列，$O$是对应的观测序列，由于一个状态生成一个观测，所以它们的长度是相同的：
$$I=(i_1,i_2,\cdots ,i_T),O=(o_1,o_2,\cdots ,o_T)$$
$A$是状态转移概率矩阵：
$$A=[a_{ij}{]}_{N\times N}\text{\hspace{1em}(10.1)}$$
其中，
$$a_{ij}=P(i_{t+1}=q_j|i_t=q_i),i=1,2,\cdots ,N;j=1,2,\cdots ,N\text{\hspace{1em}(10.2)}$$
表示时刻$t$处于状态$q_i$的条件下，在时刻$t+1$转移到状态$q_j$的概率。

$B$是观测概率矩阵：
$$B=[b_j(k){]}_{N\times M}\text{\hspace{1em}(10.3)}$$
其中，
$$b_j(k)=P(o_t=v_k|i_t=q_j),k=1,2,\cdots ,M;j=1,2,\cdots ,N\text{\hspace{1em}(10.4)}$$
这个表示可能不好理解，类似$a_{ij}$，下标表示状态，那么这里用括号表示观测。

表示时刻$t$处于状态$q_j$的条件下，生成观测$v_k$的概率。$b_j(k)$只涉及到当前时刻$t$。

$\pi$是初始状态概率向量：
$$\pi =({\pi }_i)\text{\hspace{1em}(10.5)}$$
其中，
$${\pi }_i=P(i_1=q_i),i=1,2,\cdots ,N\text{\hspace{1em}(10.6)}$$
还是用下标表示状态，但符号变成了$\pi$，表示时刻$t=1$处于状态$q_i$的概率，所以是初始概率。

上面的符号有点多，记不住没关系，后面碰到的时候多回顾几次就好了。

HMM由初始状态概率向量$\pi$、状态转移概率矩阵$A$和观测概率矩阵$B$决定。$\pi$和$A$决定状态序列，$B$决定观测序列。因此，隐马尔可夫模型$\lambda$可用三元符号表示，
$$\lambda =(A,B,\pi )\text{\hspace{1em}(10.7)}$$
$A,B,\pi$称为隐马尔可夫模型的三要素。

A和$\pi$确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵$B$确定了如何从状态生成观测。

从定义可知，隐马尔可夫模型作了两个基本假设：

(1) 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻$t$的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻$t$无关：
$$P(i_t|i_{t-1},o_{t-1},\cdots ,i_1,o_1)=P(i_t|i_{t-1})，t=1,2,\cdots ,T\text{\hspace{1em}(10.8)}$$
齐次指的是，任何时刻的状态转移概率与时刻$t$无关，都是一样的。

(2) 观测独立假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关：
$$P(o_t|i_T,o_T,i_{T-1},o_{T-1},\cdots ,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},\cdots ,i_1,o_1)=P(o_t|i_t)\text{\hspace{1em}(10.9)}$$

隐马尔可夫模型可用于标注，此时状态就对应要标注的标签(标记)。标注问题的标记是隐藏的、未知的，已知的是观测到的(单词)序列。

例 10.1(盒子和球模型) 假设有4个盒子，每个盒子里都装有红、白两种颜色的球。该例子主要是描述了初始概率分布$\pi$，状态转移概率分布$A$和观测概率分布$B$。具体可以查阅书上的内容。

观测序列的生成过程

可以将一个长度为$T$的观测序列$O=(o_1,o_2,\cdots ,o_T)$的生成过程描述如下。

算法10.1(观测序列的生成)

输入：隐马尔可夫模型$\lambda =(A,B,\pi )$，观测序列长度$T$；

输出：观测序列$O=(o_1,o_2,\cdots ,o_T)$。

(1) 安装初始状态分布$\pi$产生状态$i_1$；

(2) 令$t=1$；

(3) 按照状态$i_t$的观测概率分布$b_{i_t}(k)$生成$o_t=v_k$；

(4) 按照状态$i_t$的状态转移概率分布 { a i t , i t + 1 } \{a_{i_t,i_{t+1}}\} {ait​,it+1​​}产生状态$i_{t+1}$；

(5) 令$t=t+1$；如果$t<T$，转步(3)；否则，终止。

隐马尔可夫模型的3个基本问题

隐马尔可夫模型由3个基本问题：

(1) 概率计算问题。给定模型$\lambda =(A,B,\pi )$和观测序列$O=(o_1,o_2,\cdots ,o_T)$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda )$。

(2) 学习问题。已知观测序列$O=(o_1,o_2,\cdots ,o_T)$，估计模型$\lambda =(A,B,\pi )$参数，使得在该模型下观测序列概率$P(O|\lambda )$最大。即用极大似然估计法估计参数。

(3) 预测问题，也称为解码问题。已知模型$\lambda =(A,B,\pi )$和观测序列$O=(o_1,o_2,\cdots ,o_T)$，求对给定观测序列条件概率$P(I|O)$最大的状态序列$I=(i_1,i_2,\cdots ,i_T)$。即给定观测序列，求对应的最有可能的状态序列。