隐马尔科夫模型

机器学习最重要的任务，是根据一些已观察到的证据（例如训练样本）来对感兴趣的未知变量（例如类别标记）进行估计和推测。概率图模型提供了一种描述框架，将学习任务归结于计算变量的概率分布，在概率模型中，利用已知变量推测未知变量的分布称为推测。具体来说，假定所有关心的变量集合为Y，可观测变量的集合为O，其他变量的集合为R，“生成式”模型考虑联合概率分布P(Y,R,O),“判别式模型”考虑条件分布P(Y,R|O),给定以组观测变量值，推断就是由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O)。

直接利用概率求和规则去消去变量R显然是不可行，因为即使每个变量仅有两种取值的简单问题，其复杂度也是 $O(2^{|Y|+|R|})$ ，另一方面，属性变量之间往往存在复杂的联系。因此概率模型的学习，即基于训练来估计变量分布的参数往往相当困难。为了便于研究高效的推断和学习算法，需有一套能简洁紧凑地表达变量之间的关系。

概率图模型是一类用图表达变量相关关系的概率模型，它以图为表示工具，最常见的是用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即“变量关系图”，根据边的性质不同，概率图模型大致可分为良率：第一类是使用有向无环图表示变量间的依赖关系，称为有向图模型或贝叶斯网；第二类是使用无向图表示变量间的相关关系，称为无向图模型或马尔科夫网。

隐马尔科夫模型(HMM)是结构最简单的动态贝叶斯网，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。

一、隐马尔科夫模型的基本概念

1.隐马尔科夫模型的定义

隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态的随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态序列，称为状态序列。每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列。序列的每一个位置又可以看作是一个时刻。

隐马尔科夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。

设 $Q$ 是所有可能的状态的集合，V是所有可能的观测集合：
$Q= \{ q_1,q_2,\dots,q_N \},V=\{v_1,v_2,\dots,v_M \}$
其中，N是可能的状态数，M是可能的观测数

$I$ 是观测长度为T的状态序列， $O$ 是对应的观测序列：
$I = (i_1,i_2,\dots,i_T)，O =(o_1,o_2,\dots,o_T)$
A是状态转移概率矩阵：
$A=[a_{ij}]_{N*N}$
其中
$a_{ij} = P(i_{t+1} = q_j|i_t = q_i),i=1,2\dots,N;j=1,2,\dots,N$
是时刻 $t$ 处于状态 $q_i$ 的条件下载时刻 $t+1$ 转移到状态 $q_j$ 的概率
$B$ 是观测概率矩阵:
$B=[b_j(k)]_{N*N}$
其中
$b_j(k) = P(o_t = v_k | i_t = q_j),k=1,2,\dots,M,j=1,2,\dots,M$

$\pi$ 是初始状态概率向量：
$\pi = (\pi_i)$
其中
$\pi_i = P(i_1 = q_i),i=1,2,\dots,N$
是时刻 $t+1$ 处状态 $q_i$ 的概率

隐马尔科夫模型由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定状态序列。其中 $\pi,A$ 决定状态序列， $B$ 决定观测序列。因此，隐马尔科夫模型 $\lambda$ 可以用三元符号表示。
$\lambda(A,B,\pi)$

$A,B,\pi$ 称为隐马尔科夫三要素：
状态转态概率矩阵 $A$ 与初始状态概率向量 $\pi$ 确定了隐藏的马尔科夫链，生成不可观测的状态序列。观测概率矩阵 $B$ 确定了如何从状态生成观测，与状态序列综合确定了如何查产生观测序列。

隐马尔科夫模型作了两个基本假设：

齐次马尔科夫假设，假设隐藏的马尔科夫链在任意时刻t的状态值依赖于前一时刻的状态，与其他时刻的状态无关，也与时刻 $t$ 无关
$p(i|i_{t-1},o_{t-1},\dots,i_1,o_1)=P(i_t|i_{t-1}),t=1,2\dots,T$
观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。
$p(o_t|i_T,o_T,i_{t-1},o_{T-1},\dots,i_1,o_1)=P(o_t|i_t)$

下面看一个隐马尔科夫的例子
盒子与球模型假设有4个盒子，每个盒子里都装有红、白两种颜色的球，盒子里的红、白球数由表给出

盒子	1	2	3	4
红球数	5	3	6	8
白球数	5	7	4	2

按照下面的方法抽球，产生一个球的颜色的观测序列

开始，从4个盒子里以等概率随机选取1个盒子，从这个盒子里随机抽出1个球，记录其颜色，放回：
然后，从当前盒子随机转移到下一个盒子，规则是：如果当前盒子1，那么下一个盒子一定是2；如果当前盒子是2或3，那么分别概率0.4或0.6,转移到左边或右边的盒子；如果当前盒子是4，那么各自以0.5的概率停留在盒子4或者转移到盒子3
确定转移的盒子后，再从这个盒子里随机抽取一个球，记录其颜色，放回
如此下去，得到球的颜色观测序列

在这个过程中，观测者只能观测到球的颜色序列，观测不到球是从哪个盒子里取出的，即观测不到盒子的序列。

盒子对应状态，状态集合是
$Q = \{盒子1，盒子2，盒子3，盒子4\}，N=4$
球的颜色对应观测序列，观测的集合是
$V= \{红、白\},M=2$
初始概率分布为
$\pi = (0.25,0.25,0.25,0.25)$
状态概率分布为
$A = \begin{bmatrix} 0 & 1 & 0 &0 \\[0.3em] 0.4 & 0 &0.6 & 0 \\[0.3em] 0 & 0.4 & 0 & 0.6 \\[0.3em] 0 & 0 &0.5 & 0.5 \end{bmatrix}$
观测概率分布为
$B= \begin{bmatrix} 0.5 & 0.5 \\[0.3em] 0.3 & 0.7 \\[0.3em] 0.7 & 0.3 \\[0.3em] 0.8 & 0.2 \end{bmatrix}$

2.观测序列生成过程

输入：隐马尔科夫模型 $\lambda =(A,B,\pi)$ ，观测序列长度T
输出：观测序列 $O=(o_1,o_2,\dots,o_T)$

按照初始状态分布 $\pi$ 产生状态 $i_1$
令 $t=1$
按照状态 $i_t$ 的观测概率分布 $b_{i_t}(k)$ 生成 $o_t$
按照状态 $i_t$ 的状态转移概率分布 $\{a_{i_t},i_{t+1}\}$ 产生状态 $i_{t+1}$ ， $i_{t+1} = 1,2,\dots,N$
令 $t=t+1$ ,如果 $t < T$ ，转步3,否则终止。

3.隐马尔科夫3个基本问题

概率计算问题。给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\dots,o_T)$ ，计算在模型 $\lambda$ 下观测 $O$ 出现的概率 $P(O|\lambda)$
学习问题。已知预测序列 $O=（o_1,o_2,\dots,o_T)$ ，估计模型 $\lambda = （A,B,\pi）$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大，即用最大似然估计的方法估计参数
预测问题，也称解码(decoding)参数。已知模型 $\lambda = (A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\dots,o_T)$ ，求给定观测序列条件概率 $P(I|O)$ 最大状态序列 $I=(i_1,i_2,\dots,i_T)$ 。即给定观测序列，求最有可能的对应的状态序列

二、概率计算算法

1.前向算法

前向概率给定隐马尔科夫模型 $\lambda$ ，定义到时刻t部分观测序列为 $o_1,o_2,\dots,o_t$ 且状态为 $q_i$ 的概率为向前概率，记作
$a_t(i) = P(o_1,o_2,\dots,o_t,i_t = q_i|\lambda)$
可以递推地求得前向概率 $a_t(i)$ 及观测序列概率 $P(O\lambda)$

算法
输入：隐马尔科夫模型 $\lambda$ ，观测序列 $O$
输出：观测序列概率 $P(O|\lambda)$

初值 $a_1(i) = \pi_ib_i(o_1),i=1,2,\dots,N$
递推,对 $t=1,2,\dots,T-1$ ， $a_{t+1}(i) = \bigg[\sum_{j=1}^N a_t(j)a_{ji}\bigg]b_i(o_{t+1}),i=1,2,\dots,N$
终止 $P(O|\lambda)=\sum_{i=1}^N a_T(i)$

案例考虑盒子和球模型 $\lambda = (A,B,\pi)$ ，状态集合 $Q=\{1,2,3\}$ ，观测集合 $V=\{红，白\}$
$A = \begin{bmatrix} 0.5 & 0.5 & 0.3 \\[0.3em] 0.3 & 0.5 &0.2 \\[0.3em] 0.2 & 0.3 & 0.5 \end{bmatrix}$
$B = \begin{bmatrix} 0.5 & 0.5 \\[0.3em] 0.4 & 0.6 \\[0.3em] 0.7 & 0.3 \end{bmatrix}$
$\pi = \begin{bmatrix} 0.2 \\[0.3em] 0.4 \\[0.3em] 0.4 \end{bmatrix}$

设 $T = 3,O=(红，白，红)$ ，试用前向算法计算 $P(O|\lambda)$

计算初值
$a_1(1) = \pi_1b_1(o_1) = 0.2*0.5 = 0.10 \\ a_1(2) = \pi_1b_2(o_1) = 0.4*0.4 = 0.16 \\ a_1(3) = \pi_1b_3(o_1) = 0.4*0.7$
递推计算
$a_2(1) =\bigg[ \sum_{i=1}^3a_1(i)a_i1\bigg]b_1(o_2) = (0.10*0.5+0.16*0.3+0.28*0.2)*0.5 = 0.077 \\ a_2(2) = \bigg[\sum_{i=1}^3 a_1(i)a_{i2}\bigg]b_2(o_2) = (0.10*0.2+0.16*0.5+0,28*0.3)*0.6 = 0.1104 \\ a_2(3) = \bigg[\sum_{i=1}^3a_1(i)a_{i3}b_3(o_2)\bigg]=(0.10*0.3+0.16*0.2+0.28*0.5)*0.3 = 0.0606 \\ a_3(1) = \bigg[\sum_{i=1}^3a_2(i)a_{i2}\bigg]b_1(o_3) = (0.077*0.5+0.1104*0.3+0.0606*0.2)*0.5 = 0.4187 \\ a_3(2) = \bigg[\sum_{i=1}^3 a_2(i)a_{i2}\bigg]b_2(o_3) = (0.077*0.2+0.1104*0.5+0.0606*0.3)*0.4 = 0.3551 \\ a_3(3) = \bigg[\sum_{i=1}^3 a_2(i)a_{i3}\bigg]b_3(o_3) = (0.077*0.3+0.1104*0.2+0.0606*0.5)*0.7 = 0.05284$
终止 $P(O\lambda) = \sum_{i=1}^3 a_3(i) = 0.04187+0.03551+0.05284 = 0.13022$

2.后向算法

后向算法给定隐马尔科夫模型 $\lambda$ ，定义在t时刻状态为 $q_i$ 的条件下，从 $t+1到T$ 的部分观测序列为 $o_{t+1},o_{t+2},\dots,T$ 的概率为后向概率，记作
$\beta_t(i) = P(o_{t+1},o_{t+2},\dots,o_T|i_t=q_i,\lambda)$
可以引用递归的方法得到后向概率 $\beta_t(i)$ 以及观测序列概率 $P(O|\lambda)$
算法
输入：隐马尔科夫模型 $\lambda$ ，观测序列 $O$
输出：观测序列概率 $P(O|\lambda)$

\beta_T(i) = 1,i =1,2,\dots,N
对 $t = T-1,T-2,\dots,1$ , $\beta_t(i) = \sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\dots,N$
$P(O|\lambda) = \sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$

前后向概率的关系.png

利用前向概率和后向概率的定义可以将观测序列概率 $P(O|\lambda)$ 统一写成
$P(O|\lambda) = \sum_{i=1}^N\sum_{j=1}^Na_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),t=1,2,\dots,T-1$

3.一些概率与期望的计算

利用前向概率 $\lambda$ 和后向概率，可以得到关于单个状态和两个状态概率的计算公式

(1) 给定模型 $\lambda$ 和观测 $O$ ，在时刻t处于状态 $q_i$ 的概率

记为 $\Upsilon_t(i) = P(i_t = q_i|O,\lambda)$
可以通过前向后向概率计算
$\Upsilon_t(i) = P(i_t=q_i|O,\lambda) = \frac{P(i_t = q_i,O|\lambda)}{P(O|\lambda)}$

由向前概率 $a_t(i)$ 和向后概率 $\beta_t(i)$ 定义可知
$a_t(i)\beta_t(i) = P(i_t = q_i,O|\lambda)$
于是得到
$\Upsilon_t(i) = \frac{a_t(i)\beta_t(i)}{P(O|\lambda) } = \frac{a_t(i)\beta_t(i)}{\sum_j=1^N a_t(j)\beta_t(j)}$

(2).给定模型 $\lambda$ 和观测O，在时刻t处于状态 $q_i$ 且时刻 $t+1$ 处于状态 $q_j$ 的概率

记作
$\xi_t(i,j) = P(i_t=q_i,i_{t+1}=q_j) |O,\lambda)$
可以通过前向后向概率基色
$\xi_t(i,j) = frac{P(i_t = q_i,i_{t+1} = q_j,O|\lambda)}{P(O|\lambda)} = \frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda}{\sum_{i=1}^N\sum_{j=1}^N P(i_t = q_i,i_{t+1}=q_j,O|\lambda}$
而
$P(i_t = q_i,i_{t+1}=q_j,O|\lambda) = a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$
所以
$\Upsilon_t(i,j) = \frac{ a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$

(3).将 $\Upsilon_t(i)$ 和 $\xi_t(i,j)$ 对对各时刻t求和可以得到一些有用的概率

在观测O下状态i出现的期望
$\sum_{t=1}^T \Upsilon_t(i)$
在观测O下状态i转移的期望
$\sum_{t=1}^{T-1}\Upsilon_t(i)$
在观测O下状态i转移到状态j的期望
$\sum_{t=1}^{T-1}\xi_t(i,j)$

三、学习算法

隐马尔科夫模型的学习，根据训练数据包括预测序列和对应的状态序列还是只有预测序列，可分别由监督学习和无监督学习实现。

1.监督学习方法

假设已给训练数据包含S个长度相同的观测序列和对应的状态序列 $\{(O_1,I_1),(O_2,I_2),\dots,(O_s,I_s)\}$ ，那么可以利用极大似然估计法来看估计隐马尔科夫模型的参数

（1）转移概率 $a_{ij}$ 的估计

设样本中时刻 $t$ 处于状态 $i$ 时刻 $t+1$ 转移到状态j的频数为 $A_{ij}$ ，那么状态状态转移的概率 $a_{ij}$ 的估计是
$\hat a_{ij}=\frac{A_{ij}}{\sum_{i=1}^N A_{ij}},i=1,2,\dots,N;j=1,2,\dots,N$

(2)观测概率 $b_j(k)$ 的估计

设样本中状态为 $j$ 并观测为 $k$ 的频数是 $B_{jk}$ ，那么状态为j观测为k的概率 $b_j(k)$ 的估计是
$\hat b_j(k) = \frac{B_{jk}}{\sum_{k=1}^M B_{jk}},j=1,2,\dots,N;k=1,2,\dots,N$

(3)初始状态概率 $\pi_i$ 的估计 $\hat \pi_i$ 为S个样本初始状态为 $q_i$ 的频率

由于监督学习需要使用标注的训练数据，而人工标注训练数据往往代价很高，有时就会利用无监督学习方法

2.Baum-Welch算法

假设给定训练数据只包含S个长度为T的观测序列 $\{O_1,O_2,\dots,O_s\}$
而没有对应的状态序列，目标是学习隐马尔科夫模型 $\lambda = (A,B,\pi)$ 的参数。我们将观测序列数据看作观测数据O，状态序列数据看作不可观测的隐数据I，那么隐马尔科夫模型事实上是一个含有一个隐变量的概率模型
$P(O|\lambda) = \sum_I P(O|I,\lambda)P(I|\lambda)$
它的参数学习可由EM算法实现

(1)确定完全数据的对数似然函数

所有观测数据写成 $O=(o_1,o_2,\dots,o_0)$ ，所有隐数据写成 $I=(i_1,i_2,\dots,i_T)$ 。完全数据是 $(O,T) = (o_1,o_2,\dots,o_T,i_1,i_2,\dots,i_T)$ 。完全数据的对数似然函数是
$log P(O,I|\lambda)$

(2)EM算法的E步，求Q函数 $Q(\lambda,\bar \lambda)$

$Q(\lambda,\bar \lambda) = \sum_I log P(O,I|\lambda)P(O,I|\bar \lambda)$
其中, $\bar \lambda$ 是隐马尔科夫模型参数的当前估计值, $\lambda$ 是要极大化隐马尔科夫模型参数

$P(O,I|\lambda)=\pi_{1}b_{i_1}(o_1)a_{i_1,i_2}b_{i_2}(o_2)\dots a_{i_{T-1},i_T}b_{i_T} (O_T)$
于是函数 $Q(\lambda,\bar \lambda)$ 可以写成
$Q(\lambda,\bar \lambda) = \sum_I log\, \pi_{i_1}P(O,I|\bar \lambda) + \sum_I\bigg(\sum_{t=1}^{T-1}log \,a_{i_t,i_{t+1}}\bigg)P(O,I|\bar \lambda+\sum_I \bigg( \sum_{t=1}^T log \,b_{i_t}(o_t)\bigg) P(O,I|\bar \lambda)\space(1)$

式中求和项都是对所有数据的序列总长度T进行的。

(3)EM算法的M步：极大化 $Q$ 函数 $Q(\lambda,\bar \lambda)$ 求模型参数A,B, $\pi$

由于要极大化式(1)中但丢地出现在3个项中所以只需对各项分别极大化

式(1)的第一项可以写成
$\sum_I log \,\pi_{i_1}P(O,I|\bar \lambda) = \sum_{i=1}^N log \,\pi_iP(O,i_1 = i|\bar \lambda)$
注意到 $\pi$ 满足约束条件 $\sum_{i=1}^N \pi_i = 1$ ，利用拉格朗日橙子法，写出拉格朗日函数
$\sum_{i=1}^N log \, \pi_iP(O,i_1 = i|\bar \lambda) + \gamma\bigg(\sum_{i=1}^N \pi_i -1\bigg)$
对其求偏导数并令结果为0
$\frac{\partial}{\partial \pi_i} \bigg[\sum_{i=1}^N log\,\pi_iP(O,i_1=i|\bar \lambda)+\gamma\bigg(\sum_{i=1}^N \pi_i -1\bigg)\bigg]=0$
有
$P(O,i_1 = i|\bar \lambda) + \gamma \pi=0$
对i求和得到 $\gamma$
$\gamma = - P(O|\bar \lambda)$
则
$\pi_i = \frac{P(O,i_1 = i|\bar \lambda)}{P(O|\bar \lambda)}$
式(1)的第二项可以写成
$\sum_I\bigg(\sum_{t=1}^{T-1} log\,a_{i_t,i_{t+1}}\bigg)P(O,I|\bar\lambda)=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}log\,a_{ij}P(O,i_t=i,i_{t+1}=j|\bar\lambda)$
应用约束条件 $\sum_{j=1}^Na_{ij} = 1$ 的拉格朗日乘子法可以求出
$a_{ij}=\frac{\sum_{t=1}^TP(O,i_t=i,i_{t+1}=j|\bar \lambda)}{\sum_{t=1}^{T-1}P(O,i_t=i|\bar \lambda)}$

3.式(1)的第3项为
$\sum_I \bigg(\sum_{t=1}^Tlog\,b_{i_t}(o_t)\bigg)P(O,I|\bar \lambda) = \sum_{j=1}^N\sum_{t=1}^Tlog \,b_j(o_t)P(O,i_t =j|\bar \lambda)$
同样用拉格朗日乘子法，约束条件 $\sum_{k=1}^M b_j(k) = 1$ ，注意，只有在 $o_t = v_k$ 时 $b_j(o_t)对b_j(k)$ 的偏导才不为0，以 $I(o_t=v_k)$ 表示
$b_j(k) = \frac{\sum_{t=1}^TP(O,i_t=j|\bar \lambda)I(o_t = v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar \lambda)}$

四、预测算法

1.近似算法

近似算法的想法是，在每个时刻t选择在该时刻最有可能出现的状态 $i_t^*$ ，从而得到一个状态序列 $I^*=(i_1^*,i_2^*,\dots,i_T^*)$ ，并将它作为预测的结果
给定隐马尔科夫模型 $\lambda$ 和观测序列O，在时刻t处于状态 $q_i$ 的概率 $\gamma_t(i)$ 是
$\gamma_t(i) = \frac{a_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{a_t(i)\beta_t(i)}{\sum_{j=1}^Na_t(j)\beta_t(j)}$
在每一时刻t最有可能的状态 $i_t^*$ 是
$i_t^* = \mathop{arg \,max}_{1 \le i \le N}[\gamma_t(i)],i=1,2\dots,N$

从而得到状态序列 $i_t^* = (i_1^*,i_2^*,\dots,i_T^*)$
近似算法的一个优点是计算简单，其缺点是不能保证预测状态整体上是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。事实上，上述办法得到的状态序列中可能存在转移概率为0的相邻状态，即对某些 $i,j,a_{ij}=0$ 时。尽管如此，近似算法仍然是有用的

2.维特比算法

维特比算法实际上是用动态规划(dynamic programming)解隐马尔科夫模型预测问题，即用动态规划求解概率最大路径(最优路径）。这时一条路径对应着一个状态序列。

根据动态规划原理，最优路径有这样的特性：如果最优路径在时刻t通过结点 $i_t^*$ ，那么这一条路径从结点 $i_t^*$ 到终点 $i_T^*$ 的部分路径，对于从 $i_t^*$ 到 $i_T^*$ 的所有可能的部分路径来说，必须是最优的。因为假如不是这样，那么从 $i_t^*$ 到 $i_T^*$ 就有另一条更好的部分路径存在，如果把它和从 $i_1^*$ 到达 $i_t^*$ 的部分路径连起来，就会形成一条比原来的路径更优的路径，这是矛盾的。依据这一原理，我们只需从时刻t=1开始，递推地计算时刻t状态为 $i$ 各部分路径的最大概率，直至得到时刻t=T状态为i各条路径的最大概括。时刻t=T的最大概率即为最优路径的概率 $P^*$ ，最优路径的终结点 $i_T^*$ 也同时得到，之后，为了找出最优路径的各个结点，从终结点 $i_T^*$ 开始，由后向前逐步得到结点 $i_{T-1}^*$ ，得到最优路径 $I^* = (i_1^*,i_2^*,\dots,i_T^*)$ 。这就是维特比算法

维特比算法
输入：模型 $\lambda=（A,B,\pi)$ 和观测序列 $O(o_1,o_2,\dots,o_T)$
输出：最优路径 $I^*=（i_1^*,i_2^*,\dots,i_T^*)$
1.初始化
$\delta_1(i) = \pi_ib_i(o_1),i=1,2,\dots,N$
$\psi_1(i) = 0,i=1,2,\dots,N$
2.递推，对 $t=2,3,\dots,T$
$\delta_t(i) = \mathop{max}_{1 \le j \le N}[\delta_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\dots,N \\ \psi_t(i) =\mathop{arg \,max}_{1 \le j \le N}[\delta{t-1}(j)a_{ji}],i=1,2,\dots,N$
3.终止
$p^* = \mathop{max}_{1 \le i \le N}\delta_T(i) \\ i_T^* = \mathop{arg max}_{1 \le i \le N}[\delta_T(i)]$
4.最优路径回溯，对 $t=T-1,T-2,\dots,1$
$i_t^* =\psi_{t+1}(i_{t+1}^*)$
求得最优路径 $I^*=（i_1^*,i_2^*,\dots,i_T^*)$

最后编辑于：2019.08.19 08:47:01

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,245评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,749评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,960评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,575评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,668评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,670评论 1赞 294
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,664评论 3赞 415
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,422评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,864评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,178评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,340评论 1赞 344
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,015评论 5赞 340
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,646评论 3赞 323
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,265评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,494评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,261评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,206评论 2赞 352

隐马尔科夫模型

隐马尔科夫模型

一、隐马尔科夫模型的基本概念

1.隐马尔科夫模型的定义

2.观测序列生成过程

3.隐马尔科夫3个基本问题

二、概率计算算法

1.前向算法

2.后向算法

3.一些概率与期望的计算

(1) 给定模型和观测，在时刻t处于状态的概率

(2).给定模型和观测O，在时刻t处于状态且时刻处于状态的概率

(3).将和对对各时刻t求和可以得到一些有用的概率

三、学习算法

1.监督学习方法

（1）转移概率的估计

(2)观测概率的估计

(3)初始状态概率的估计为S个样本初始状态为的频率

2.Baum-Welch算法

(1)确定完全数据的对数似然函数

(2)EM算法的E步，求Q函数

(3)EM算法的M步：极大化函数求模型参数A,B,

四、预测算法

1.近似算法

2.维特比算法

推荐阅读更多精彩内容

(1) 给定模型 $\lambda$ 和观测 $O$ ，在时刻t处于状态 $q_i$ 的概率

(2).给定模型 $\lambda$ 和观测O，在时刻t处于状态 $q_i$ 且时刻 $t+1$ 处于状态 $q_j$ 的概率

(3).将 $\Upsilon_t(i)$ 和 $\xi_t(i,j)$ 对对各时刻t求和可以得到一些有用的概率

（1）转移概率 $a_{ij}$ 的估计

(2)观测概率 $b_j(k)$ 的估计

(3)初始状态概率 $\pi_i$ 的估计 $\hat \pi_i$ 为S个样本初始状态为 $q_i$ 的频率

(2)EM算法的E步，求Q函数 $Q(\lambda,\bar \lambda)$

(3)EM算法的M步：极大化 $Q$ 函数 $Q(\lambda,\bar \lambda)$ 求模型参数A,B, $\pi$