隐马尔可夫模型

  隐马尔可夫模型（HMM）是一种标注模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。其在语音识别，自然语言处理，模式识别等领域有着广泛的应用。

1.基本概念

  友好起见，我们以例子来导出马尔可夫的定义

• 盒子与球模型
    设有4个盒子，每个盒子里装有红白两种颜色的球。该模型抽取过程定义如下：先等概率选择一个盒子，从中抽取一次得到一个观测结果，然后换盒子，并且换盒子的过程中服从一些概率，比如1号盒子到2、3、4号的概率分别为0.1、0.4、0.5。2号盒子到1、2、3、4号的概率分别为0.3、0.2、0.1、0.4。假设抽取了5次，结果为“红，白，白，红，红”。
    总共抽取了5次，那么得到一个时间长度为5的观测序列，这里”红，白，白，红，红“便是最终的观测序列，其中每次抽取是在不同的盒子中进行的，这5次选择的盒子构成了一个状态随机序列，表示是在什么状态下抽取的。注意模型开始假设是等概率选择一个盒子，这个概率叫初始状态概率$\pi$。
    设所有可能的状态Q有N种，可能的V观测有M种，为了公式表达方便， 用 $q=i$ 表示状态为第$i$ 个状态， $q_t=i$表示在 $t$ 时刻的状态是第 $i$ 个状态，$y_t$ 表示第 $t$个时刻的观测。
    其中每个状态（当前盒子）都有转移到另一个状态的概率，这些概率可以方便的用矩阵表示，并且这个矩阵一定是方阵， $$A=[a_{ij} ] _ {N*N}$$

其中,

$$a_{ij} = P(q_{(t+1)} =j|q_t = i), i=1,2,...,N;j=1,2,...,$$

表示在时刻 t 处于状态 i 的条件下在下一时刻 t+1 转移到状态 j 的概率。
  除了状态转移矩阵，要知道还有每个状态下各个观测事件发生的概率，因此也用矩阵B将其表示

$$B = [b_j(k)]_{N*M}$$

其中

$$b_j(k) = P(y_t = v_k|q_t = j)$$

表示在状态 $j$ 下生成观测$v_k$的概率。
  $\pi$表示初始状态概率向量

$$\pi = (\pi_i) ,$$

其中,$\pi = P(q_1 =i)$，表示$t = 1$时刻处于状态 $i$ 的概率。
  状态转移概率矩阵A，观测概率矩阵B和初始状态概率$\pi$构成了隐马尔可夫模型的三要素，常用三元符表示隐马尔可夫模型的参数

$$\lambda = (A,B,\pi)$$

1.1 两个重要假设

  隐马尔可夫模型有两个非常重要的假设，后面简化算法的推导都是基于这两个假设

• 齐次马尔可夫性假设
    即假设隐马尔可夫链在任意时刻$t$的状态只依赖与前一时刻的状态，与其他时刻的装态和观测值无关，也与$t$时刻无关，即得概率简化公式如下 $$P(q_t|y_1,y_2,...,y_{t-1},q_1,q_2,...,q_{t-1})= P(q_t|q_{t-1})$$
• 观测独立性假设
    即假设任意时刻的观测只依赖于当前时刻马尔可夫链的状态，而与其他观测和状态无关 $$P(y_t|y_1,y_2,...,y_{t-1},q_1,q_2,...,q_t) = P(y_t|q_t)$$   总结一下隐马尔可夫的过程，那么假设$\lambda$的参数已知，生成一个长度为T的时间序列的过程如下：
    （1） 按照初始状态概率$\pi$产生一个状态$q_1$。
    （2）令 t = 1
    （3）按照状态$q_t$的观测概率矩阵B生成$y_t$。
    （4）安装状态$q_t$的状态转移矩阵A产生下一个时刻的状态。
    （5）$t= t +1$, 如果$t < T$，转至（3），否则结束。

  大致明白隐马尔可夫模型是什么之后我们需要考虑它是干嘛的，能做什么。事实上隐马尔可夫模型有三个基本问题，解决这三个基本问题的过程也就是解决不同问题的过程，同时其问题描述也很明确，相信看完问题描述之后便对它能做什么有大致的了解。

• 隐马尔可夫的三个基本问题
  (1) 概率计算问题。给定隐马尔可夫模型的参数$\lambda=(A,B,\pi)$和观测序列$Y=(y_1,y_2,…,y_t)$，计算在该模型下观测 序列$Y$出现的概率$P(Y|\lambda)$。
  (2) 学习问题。已知观测序列$Y= (y_1,y_2,…,y_t)$，估计模型的参数$\lambda=（A,B,\pi）$,使得该模型下的该观测序列发生的概率$P(Y|\lambda)$最大，即极大似然估计该模型参数。
  (3) 预测问题，也称为解码(decoding)问题。已知模型$\lambda=(A,B,\pi)$和观测序列$Y=(y_1,y_2,…,y_t)$，求使给定序列条件下状态序列的概率$P(Q|Y)$最大的状态序列，即给定观测序列，求最有可能生成该观测序列的状态序列。

  后面继续讨论如何计算这些问题以及如何简化这些问题。

2. $P(Y|\lambda)$概率计算问题

  本问题可以通过前向和后向算法进行计算，不过先来看看该问题的直接解法，以及该方法为什么不可行。前面已经说过隐马尔可夫有两个基本假设，其计算基本都是基于它们来化简的，先考虑其基本用法，即一个观测序列可以如何简化表达，以三个观测序列为例$P(y_1,y_2,y_3)$，其中共有K个状态

$$\begin{aligned} P(y_1,y_2,y_3) = & \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_1,y_2,y_3,q_1,q_2,q_3)\\ = &\sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|y_1,y_2,q_1,q_2,q_3)\cdot P(y_1,y_2,q_1,q_2,q_3)\\ = &\sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3)\cdot P(q_3|y_1,y_2,q_1,q_2)\cdot P(y_1,y_2,q_1,q_2)\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_1,y_2,q_1,q_2)\\ & \cdots \cdots\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_2|q_2)\cdot P(q_2|q_1) \cdot P(y_1|q_1) \cdot P(q_1)\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_2|q_2)\cdot P(q_2|q_1) \cdot P(y_1|q_1) \cdot \pi(\pi_1) \end{aligned}$$

  虽然这一方法在直接计算法中没有用到，但是是后面化简都会用到的，所以先写在这儿。

2.1 直接计算方法

   回忆问题，给定模型参数和一个观测序列，计算这个观测序列出现的概率$P(Y,\lambda)$，若要直接计算，需考虑我们有哪些已知条件。首先初始状态概率$\pi$知道，状态转移概率矩阵A也知道，那么生成和这个观测序列相同长度的状态序列的概率$P(Q|\lambda)$就能表示出来了

$$P(Q|\lambda)=\pi_{q_1} a_{q_1q_2}a_{q_2q_3} \cdots a_{q_{t-1}q_{t}}$$

  $P(Y|\lambda)$不能直接表达的原因是中间还有隐变量——转移状态，在固定状态下的观测概率B是已知的，那么已经得到了一串状态序列的概率，在这串状态序列下的观测是能够表示的，这便得到了

$$P(Y|Q,\lambda) = b_{q_i}(y_1)\cdot b_{q_2}(y_2)\cdots b_{q_t}(y_t)$$

  有了这两个概率，隐变量和观测变量的联合概率分布可表示为

$$\begin{aligned} P(Y,Q|\lambda) =&P(Y|Q,\lambda) P(Q|\lambda)\\ =&\pi_{q_1}b_{q_1}(y_1)a_{q_1q_2}b_{q_2}(y_1)\cdots a_{q_{t-1}q_t}b_{q_t}(y_t) \end{aligned}$$

  对于联合概率分布，可以求解其一个变量的边缘分布的和或积分得到另一个变量的分布，这是机器学习中常见的 手段，应熟练掌握，现对状态序列求和

$$\begin{aligned} P(Y|\lambda) =& \sum_QP(Y|Q,\lambda) P(Q|\lambda)\\ =& \sum_{q_t}^K \cdots \sum_{q_1}^K\pi_{q_1}b_{q_1}(y_1)a_{q_1q_2}b_{q_2}(y_1)\cdots a_{q_{t-1}q_t}b_{q_t}(y_t) \end{aligned}$$

  这个计算量是非常大的，T个观测序列，每个序列有K种可能的状态，且内部还有T个乘积需要计算，相当于T个for循环，每个循环执行K次，每次的复杂度T，那么总复杂度$O(TK^T)$。

2.2 前向算法

  为了简化，首先定义了前向概率表达，对于隐马尔可夫模型$\lambda$，定义在时刻 t 的观测序列为$(y_1,y_2,…,y_t)$且状态为$q_t = i$的概率为前向概率$\alpha_t(i)$，即

$$\alpha_t(i) = P(y_1,y_2,...,y_t,q_t = i |\lambda)$$

  下面通过这个前向概率推导$P(Y|\lambda)$的递推表达式

$$\begin{aligned} \alpha_1(i) = & P(y_1,q_1 = i | \lambda)\\ =&\pi(\pi_i)bi(y_1)\\ ,&\\ \alpha_2(i)=&P(y_1,y_2,q_2 = i)\\ =&\sum_jP(y_1,y_2,q_2 = i,q_1 = j)\\ =&\sum_jP(y_2|q_2 = i)P(q_2 = i|q_1 =j)\cdot \alpha_1(j)\\ =&P(y_2|q_2)\sum_jP(q_2 = i|q_1 = j) \cdot \alpha_1(j)\\ &\cdots\\ \alpha_t(i)=&P(y_t|q_t = i)\sum_jP(q_t = i|q_{t-1} = j) \cdot \alpha_{t-1}(j)\\ =&b_i(y_t)\sum_ja_{ji}\cdot \alpha_{t-1}(j) \end{aligned}$$

这是我之前想的推导方法，但不得不说是比较蠢的，由定义观察式子中少了什么多了什么即可，法2

$$\begin{aligned} \alpha_t(i) = &P(y_1,\cdots,y_t,q_t = i|\lambda)\\ =& \sum_j P(y_1,\cdots,y_t,q_{t-1} = j,q_t = i|\lambda)\\ =& \sum_j P(y_t|q_t=i)P(q_t = i|q_{t-1}=j)P(y_1,\cdots,y_{t-1},q_{t-1}=j|\lambda)\\ =&\sum_jb_i(y_t) a_{ji}\alpha_{t-1}(j) \end{aligned}$$

  注意求第二个前向概率的时候，为了化简式子，引入了$q_1$但将它当作边缘概率求和去掉了。这个递推式就这样神奇的得到了 t 时刻状态为 $q = i$ 的概率，得到t 时刻的前向概率的表达式后，根据它的定义$\alpha_T(i) = P(y_1,y_2,…,y_T,q_t = i|\lambda)$可知，计算$P(Y|\lambda)$只需要将 t 时刻的所有状态的概率求和就可以了（边缘概率）

$$P(Y|\lambda) = \sum_i^K\alpha_T(i)$$

  而且这个递推式极大的简化了计算量，因为在计算下一个时刻的前向概率的时候，上一个时刻的前向概率是已经算出来了的，只需做少量乘法，最后的复杂度为$O(KT)$。

2.3 后向算法

  明白前向算法的推导过程后，后向算法的思想其实是一样的，并且得到的结果都一样，只不过后向是从后面往前面推，前向可与后向算法组合在一起表达$P(Y|\lambda)$
定义：
  给定隐马尔可夫模型$\lambda$，定义在 t 时刻 且状态为$q_t = i$的条件下，从 t + 1 时刻到 T 时刻的观测序列的概率为后向概率，即

$$\beta_t(i) = P(y_{t+1},y_{t+2},...,y_T| q_t = i, \lambda)$$

  注意观测数据是从 t + 1 时刻开始的，并且$\beta_t(i) = 1$，

$$\begin{aligned} \beta_T(i) = & 1\\ ,&\\ \beta_{T-1}(i)=&P(y_T|q_{T-1} = i,\lambda)\\ =&\sum_{j}^KP(y_T,q_T=j|q_{T-1} = i,\lambda)\\ =&\sum_j^KP(y_T|q_T =j)P(q_T = j|q_{T-1} =i)\\ =&\sum_j^Kb_j(y_T)a_{ij} \beta_T(j)\\ &，\\ \beta_{T-2}(i)=&P(y_{T-1},y_T|q_{T-2} = i, \lambda)\\ =&\sum_{j}^K P(y_{T-1},y_T,q_{T-1} = j|q_{T-2} = i, \lambda)\\ (乘法公式）=&\sum_{j}^K P(y_T|q_{T-1} = j)\cdot P(y_{T-1}|q_{T-1}=j)\cdot P(q_{T-1}=j|q_{T-2} = i,\lambda)\\ =&\sum_j^K \beta_{T-1}(j)\cdot b_j(y_{T-1})a_{ij}\\ &\cdots\\ \beta_t(i)=&\sum_j^K\beta_{t+1}(j)\cdot b_j(y_{t+1})\cdot a_{ij} \end{aligned}$$

  和上面一样，法2，由定义，补充一个$q_{t+1}$即可

$$\begin{aligned} \beta_t(i) = &P(y_{t+1},y_{t+2},\cdots,y_T|q_t = i,\lambda)\\ =&\sum_jP(y_{t+1},y_{t+2},\cdots,y_T,q_{t+1}=j|q_t = i,\lambda)\\ =& \sum_jP(y_{t+1}|q_{t+1}=j)P(q_{t+1}=j|q_t=i)P(y_{t+2},\cdots,y_T|q_{t+1} =j,\lambda)\\ =&\sum_j b_j(y_{t+1})a_{ij}\beta_{t+1}(j) \end{aligned}$$

  同样，得到后向概率的表达式后，根据其定义$\beta_t(i) = P(y_{t+1},y_{t+2},…,y_T| q_t = i, \lambda)$，所求序列为1-T，但t 至少为1 ，这使得该表达式缺少了第一个观测值的概率，不过这很简单，乘上$\pi_i b_{i}(y_1)$即可，通过后向概率得到$P(Y|\lambda)$

$$P(Y|\lambda) = \sum_i^K\pi_i b_i(y_1)\beta_1(i)$$

  从刚刚这个求和运算中发现后向概率的定义从 t + 1 时刻开始似乎不方便，但是当它和前向概率结合时，就会发现，应当如此！

2.4 通过前向与后向概率表达两个重要概率和三个期望

  （1）计算$P(q_t = i|Y,\lambda),Y = (y_1,y_2,…y_T)$时，即计算给定一串序列情况下，其 t 时刻的状态为 i 的几率，记为$\gamma_t(i)$。利用前向与后向概率，先计算t 时刻状态与观测的联合分布

$$\begin{aligned} \gamma_t(i)=P(Y,q_t = i | \lambda) = &P(Y|q_t = i)\cdot P(q_t = i)\\ =& P(y_1,\cdots,y_t|q_t = i)\cdot P(y_{t+1},\cdots ,y_T|q_t = i)\cdot P(q_t = i)\\ =& P(y_1,\cdots,y_t,q_t = i)\cdot P(y_{t+1},\cdots ,y_T|q_t = i)\\ =& \alpha_t(i)\cdot \beta_t(i) \end{aligned}$$

  即序列中某个时刻 t 的状态与观测的联合分布可用前向与后向拼接而成，由该联合分布可得观测的分布

$$P(Y|\lambda) = \sum_i^KP(Y,q_t = i|\lambda)=\sum_i^K\alpha_t(i)\beta_t(i)$$

  再根据条件概率或乘法公式

$$\gamma_t(i)=P(q_t = i|Y,\lambda) =\frac {P(Y,q_t = i|\lambda)} {P(Y|\lambda)}= \frac {\alpha_t (i) \beta_t(i)} {\sum_i\alpha_t(i) \beta_t(i)}$$

  （2）给定模型参数和观测序列Y，求在时刻 t 处于状态 i 且在时刻 t + 1 处于状态 j 的概率，记为$\xi_t(i,j)$，大概已经找到窍门了，就是通过其联合概率和观测概率

$$\begin{aligned} \xi_t(i,j)=P(q_t =i,q_{t+1}=j|Y,\lambda) = & \frac {P(q_t =i ,q_{t+1} = j,Y, \lambda)} {P(Y|\lambda)}\\ =& \frac {P(q_t =i ,q_{t+1} = j,Y, \lambda)} {\sum_i^K\sum_j^KP(q_t =i ,q_{t+1} = j,Y, \lambda)}\\ \end{aligned}$$

其中，

$$\begin{aligned} P(&q_t =i ,q_{t+1} = j,Y, \lambda)\\ =&P(Y|q_t=i,q_{t+1} = j)P(q_t=i,q_{t+1} = j)\\ =&P(y_T,y_{T-1},\cdots,y_{t+1}|q_t=i,q_{t+1}=j)P(y_t,\cdots,y_1|q_t=i,q_{t+1}=j)P(q_{t+1}=j,q_t=i)P(q_t=i)\\ =&P(y_T,y_{T-1},\cdots,y_{T+2}|q_{t+1}=j)P(y_{T+1}|q_{t+1} = j)P(y_T,\cdots,y_1,q_t=i)P(q_{t+1}=j,q_t = i)\\ =&\beta_{t+1}(j)b_j(y_{t+1})\alpha_t(i)a_{ij} \end{aligned}$$

  此过程中应仔细考虑马尔可夫的两个基本假设，确定其中哪些变量是相互独立的，还有哪些是我们之前已经求出来的。这里以 t 和 t + 1 为界将观测量分开，这样时刻 t 和 时刻 t + 1 的状态都只能作用 于其中一边了。带入原式

$$\xi_t(i,j)=\frac {\alpha_t(i)a_{ij}b_j(y_{t+1})\beta_{t+1}(j)} { \sum_i^K\sum_j^K\alpha_t(i)a_{ij}b_j(y_{t+1})\beta_{t+1}(j)}$$

（3）上面计算出的两个概率求和可以方便的表示一些有用的期望
   1> 在观测Y下状态 i 出现的期望

$$=\sum_t^T\gamma_t(i) = \sum_t^TP(q_t=i|Y,\lambda)$$

  2> 在观测Y下由状态 i 转移的期望，即前 T- 1个时刻有过状态 i

$$= \sum_t^{T-1} \gamma_t (i) = \sum_t^{T-1}P(q_t = i | Y, \lambda)$$

   3>在观测Y下由状态 i 转移到状态 j 的期望

$$=\sum_t^{T-1} \xi _t(i,j) = \sum_i^{T-1} P(q_t = i,q_{t+1} = j|Y, \lambda)$$

3. 学习算法(EM)

  对于学习算法，可分为知道状态序列和不知道状态序列，知道状态序列的计算可直接用极大似然估计经验概率。这里就不说了，一般都是不知道状态序列的，这就和上一篇讲的EM算法一致了，即包含隐变量的概率模型的学习。隐马尔可夫的学习算法叫Baum-Welch，不过原理和EM是一致的，只是因为那时候EM算法还未成体系。

• EM估计

  在隐马尔可夫中，模型参数是$\lambda= (A,B,\pi)$，观测序列$Y$便是观测数据，而状态转移序列$Q$作为不可观测的隐数据，这样便确立了EM的结构，下面只需按EM算法的步骤计算即可。（按理说初始状态产生的概率也应算作隐变量，但事实上状态序列的第一个已经包含它，并且在后面的计算中状态转移都是依赖于$\pi$的，可同时将其计算出来）
  首先，确立完全数据的对数似然函数

$$L(\lambda,Q) = logP(Y,Q|\lambda)$$

E-Step：
  E步求对数似然函数关于 隐变量 Q （状态序列）的条件后验概率的期望，但在隐马尔可夫模型中，并未用关于隐变量Q的条件后验概率的期望，而是用 关于 观测序列 Y 和 状态序列的联合后验概率的期望，可以这么做的原因是联合概率等于观测概率 * 隐变量的条件概率——$P(Y,Q|\bar \lambda) = P(Q|Y,\bar \lambda)P(Y|\bar \lambda)$，而$P(Y|\bar \lambda)$是常数，并不影响对似然函数的极大化。至于为什么这么做，当然是为了化简后面的结果——用前面推导出的容易表示的概率和期望。于是Q函数表示为

$$Q(\lambda,\bar \lambda) = \sum_Q(Y,Q|\bar \lambda)logP(Y,Q|\lambda)$$

  其中$Q = (q_1,q_2,\cdots ,q_t)$，表示有 t 个求和运算，log前是参数已知的概率，实际要优化的是后面参数未知的$\lambda$，而

$$P(Y,Q|\lambda) = \pi_{q_1} \prod_{t=1}^{T-1}a_{q_tq_{t+1}}\prod_{t = 1}^Tb_{q_t}(y_t)$$

  于是，

$$Q(\lambda,\bar \lambda) = \sum_QP(Y,Q|\bar \lambda)\left \{ log\pi_{q_1} + \sum_{t=1}^{T-1}loga_{q_tq_{t+1}} + \sum_{t=1}^T log b_{q_t}(y_t) \right \}$$

M-Step:
  得到Q函数后就可以进行M步求解模型参数

$$\widehat \lambda = arg \underset \lambda {max} Q(\lambda,\bar \lambda)$$

  对于这个Q函数，由于$\lambda$的三个参数都是互相分离的，因此可以分开极大化求解

  （1）对于第1 项

$$\begin{aligned} \sum_QP(Y,Q|\bar \lambda)log\pi_{q_q} = & \sum_{q_1}\cdots \sum_{q_t}P(Y,Q|\bar \lambda)log\pi_{q_1}\\ =&\sum_{q_1}log\pi_{q_1}\sum_{q_2}\cdots \sum_{q_t}P(Y,q_1,\cdots,q_t|\bar \lambda)\\ =&\sum_{q_1}P(Y,q_1|\bar \lambda) log \pi_{q_1} \end{aligned}$$

  注意log 函数中只与 状态序列中第一个有关，于是可以提到 第二个状态序列的求和前面，而后面的求和就是常见的边缘概率的求和=1，相当于把那部分变量积分消去了，这时添加$\sum_i\pi_i =1$的约束，利用拉格朗日乘数法计算极大点，这里求偏导时其实就是对每个$\pi_i$求偏导，也就是说有 N 个等式都得为0 ，然后分别求$\pi_i$

$$\begin{aligned} \frac {\partial \sum_i^NP(Y,q_1 = i|\bar \lambda)log\pi_{q_1}+\gamma(\sum_i^N\pi_i - 1) } {\partial \pi_i}=&0\\ P(Y,q_1 = i| \bar \lambda) + \gamma \pi_i=& 0\\ \sum_i^N P(Y, q_1 = i| \bar \lambda) + \gamma \sum_i^N \pi_i=&0\\ \gamma=&-P(Y|\bar \lambda) \end{aligned}$$

  $\gamma$带回到上面等式第二步，

$$\pi_i = \frac { P(Y,q_1 = i|\bar \lambda)} {P(Y|\bar \lambda)}\\ = \frac {\alpha_1(i) \beta_1(i)} {\sum_i^N\alpha_t(i)}\\ =\gamma_1(i)$$

  其中分母也可用后向概率表示，或是后向与前向组合，注意分子被前面得到的前向后向概率简单的表示出来，这便是开始选择Q函数的时候为什么选择联合概率的原因。
  （2） 对于第二项

$$\begin{aligned} \sum_QP(Y,Q|\bar \lambda)\sum_{t=1}^{T-1} loga_{q_tq_{t+1}}=& \sum_{q_1} \cdots \sum_{q_t} P(Y,Q|\bar \lambda)\sum_{t=1}^{T-1} log a_{q_tq_{t+1}}\\ =&\sum_i\sum_jP(Y,q_t = i,q_{t +1} =j|\bar \lambda)\sum_{t=1}^{T-1} log a_{ij} \end{aligned}$$

  原理与第一项是一样的，虽是对每个状态变量都要求和，但是当 t 确定时，求和中只有时刻 t 和与它相邻的 t + 1 时刻的状态有关，因此外面的T个求和运算总是只有两个有效，然后添加关于$a_{ij}$的约束$\sum_j a_{ij}= 1$构造拉格朗日即可

$$\begin{aligned} 0=&\frac \partial {\partial a_{ij}} \left \{ \sum_i\sum_jP(Y,q_t = i,q_{t +1} =j|\bar \lambda)\sum_{t=1}^{T-1} log a_{ij} + \eta( \sum_ja_{ij} -1)\right \} \\ 0=&\sum_{t-1}^{T-1}P(Y,q_t =i,q_{t+1} =j|\bar \lambda) + \eta a_{ij}\\ 0=&\sum_j \left \{ \sum_{t-1}^{T-1}P(Y,q_t =i,q_{t+1} =j|\bar \lambda) + \eta a_{ij} \right \}\\ 0=&\sum_{t=1} ^{T-1} P(Y,q_t =i | \bar \lambda) + \eta\\ \eta=&-\sum_{t=1} ^{T-1} P(Y,q_t =i | \bar \lambda) \end{aligned}$$

代回上式第二步，

$$\begin{aligned} a_{ij} = &\frac { \sum_{t-1}^{T-1}P(Y,q_t =i,q_{t+1} =j|\bar \lambda) } { \sum_{t=1} ^{T-1} P(Y,q_t =i | \bar \lambda) }\\ =&\frac {\sum_t^{T-1} \xi_t(i,j) } { \sum_t^{T-1} \gamma_t(i) } \end{aligned}$$

   （3） 对于第三项

$$\sum_QP(Y,Q|\bar \lambda) \sum_t b_{q_t}(y_t) = \sum_jP(Y,q_t = j|\bar \lambda)\sum_tb_j(y_t)$$

  求解方法相同，这里不赘述，只需要注意$b_j(y_t)$偏导时不止要保证 j 相同就不为0，还需保证观测值也相同，可用$I(y_t = k)$表示，结果为

$$b_j(k) = \frac { \sum_t P(Y,q_t = j| \bar \lambda) I(y_t = k) } { \sum_tP(Y,q_t = j | \bar \lambda) } \\ =\frac { \sum_{t=1,y_t = k}^T \gamma_t (j) } { \sum_t^T\gamma_t(j) }$$

  这些结果最后都可以用前向后向的简化而来的期望进行计算和表达。

4.预测算法

  隐马尔可夫的预测是指给定模型参数和已知的观测序列，求解最有可能的状态序列，所以也称为解码运算（decoding）。下面介绍用于预测的近似算法和维特比算法（Viterbi algorithm）。

4.1 近似算法

  近似算法是不考虑状态之间的互相影响而简化的一种算法，它的基本思想是分别选取每个时刻 t 最有可能出现的状态 $q_i$，从而得到一个状态序列。而前面我们已经将 t 时刻最有可能出现的概率表示出了

$$\gamma_t(i) = \frac { \alpha_t(i) \beta_t(i) } {P(Y|\lambda)} = \frac {\alpha_t(i) \beta_t(i) } { \sum_j \alpha_t(j) \beta_t(j)}$$

于是，t 时刻最有可能的状态是

$$q_t^* = arg\underset i {max} [\gamma_t(i) ]$$

  对 T 个时刻依次求解即可得到状态序列，从求解过程中也可以看到，每个状态只是单独的用观测序列进行估计，并未考虑状态序列之间的整体影响和概率最大情况。但近似算法计算简单，并在有些场景仍可使用。

4.2 维特比算法

  维特比算法采用动态规划求解隐马尔可夫模型的状态序列，即从初始时刻开始，依次计算到每个状态的概率，保存到当前时刻的每个状态最大的概率的上一个状态是什么，直到T时刻时，便计算出了所有状态的最大概率，选择概率最大的那个状态，并从该状态回溯，得到其状态序列，那么该序列便是总概率最大的状态序列。其实就是贪心的思想，先求解最优子问题。
  根据刚刚的分析，该问题需要计算的有两个，一是当前时刻是状态 i 的最大概率，二是当前时刻是状态 i 的最大概率是由上个时刻哪个状态得到的。

• 定义

(1) . 在时刻 t 状态为 i 的状态序列的概率最大值为(注意 时刻 t 前的序列都已确定）

$$\delta_t(i) = \underset {q_1,\cdots ,q_{t-1}} {max} P(q_t = i,q_{t-1},\cdots,q_1,Y|\lambda)$$

  那么无论是通过定义，还是考虑这是一个递归过程，都能得到

$$\delta_{t+1} (i) = \underset {q_1,\cdots ,q_{t}} {max} P(t_{t+1} = i,q_t,\cdots,q_1,y_{t+1},\cdots,y_1|\lambda)\\ =\underset {0<j<N+1} {max}[ \delta_t(j)a_{ji}b_i(y_{t+1}) ]$$

(2) . 在时刻 t 状态为 i 的概率最大的状态序列的上一个时刻的状态为

$$\Psi_t(i) = arg \underset {0<j<N+1} {max}[\delta_{t-1}(j)a_{ji}]$$

  注意求上一个时刻的状态时不需要乘发射概率，因为当前时刻 t 的状态已确定，与观测无关。

算法过程：
  需要计算的量和贪心策略确定后，算法过程也就比较简单了。
  （1）初始化

$$\delta_1(i) = \pi_ib_i(y_1)\\ \Psi_1(i) = 0$$

  （2）递推，t = 2, 3, … , T

$$\delta_t(i) = =\underset {0<j<N+1} {max}[ \delta_t(j)a_{ji}b_i(y_{t+1}) ]\\ \Psi_t(i) = arg \underset {0<j<N+1} {max}[\delta_{t-1}(j)a_{ji}]$$

  （3）停止

$$P^* = \underset{0<i<N+1} {max} \delta_T(i)\\ q_T^* = arg \underset {0<i<N+1} {max} \delta_T(i)$$

  （4）回溯 ，t = T-1,…, 1

$$q_t^* = \Psi_{t+1} (q_{t+1})$$

  算法完成便得到一个状态序列，这个序列对于观测序列来说是概率最大的。