隐马尔科夫模型（Hidden Markov Model，HMM）

$$\begin{align} \end{align}$$

1 隐马尔科夫模型定义

状态集合$Q=\left\{q_{1},q_{2},\ldots ,q_{N}\right\}$

观测集合\begin{align} & V=\left\{v_{1},v_{2},\ldots ,v_{M}\right\} \quad \left| V\right| =M \end{align}

状态序列\begin{align} & I=\left\{i_{1},i_{2},\ldots ,i_{t},\ldots,i_{T}\right\} \quad i_{t}\in Q \quad \left(t=1,2,\ldots,T \right)\end{align}

观测序列\begin{align} & O=\left\{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right\} \quad o_{t}\in V \quad \left(t=1,2,\ldots,T \right)\end{align}

状态转移矩阵 \begin{align} & A=\left[a_{ij}\right]_{N\times N} \end{align}

在$t$时刻处于状态$q_{i}$的条件下，在$t+1$时刻转移到状态$q_{j}$的概率\begin{align} & a_{ij}= P\left( i_{t+1}=q_{j}|i_{t}=q_{i}\right) \quad \left(i=1,2,\ldots,N \right) \quad \left(j=1,2,\ldots,M \right)\end{align}

观测概率矩阵\begin{align} & B=\left[b_{j}\left(k\right)\right]_{N\times M} \end{align}

在$t$时刻处于状态$q_{i}$的条件下，生成观测$v_{k}$的概率\begin{align} & b_{j}\left(k\right)= P\left( o_{t}=v_{k}|i_{t}=q_{j}\right) \quad \left(k=1,2,\ldots,M \right) \quad \left(j=1,2,\ldots,N \right)\end{align}

初始概率向量\begin{align} & \pi =\left( \pi _{i}\right) \end{align}

在时刻$t=1$处于状态$q_{i}$的概率\begin{align} & \pi_{i} =P\left( i_{1}=q_{i}\right) \quad \left(i=1,2,\ldots,N \right) \end{align}

隐马尔科夫模型\begin{align} & \lambda =\left( A,B.\pi \right) \end{align}

隐马尔科夫模型基本假设：

1. 齐次马尔科夫性假设：在任意时刻$t$的状态只依赖于时刻$t-1$的状态。\begin{align} & P\left( i_{t}|i_{t-1},o_{t-1},\ldots,i_{1},o_{1}\right)=P\left(i_{t}|i_{t-1}\right) \quad \left(t=1,2,\ldots,T\right) \end{align}
2. 观测独立性假设：任意时刻$t$的观测只依赖于时刻$t$的状态。\begin{align} & P\left( o_{t}|i_{T},o_{T},i_{T-1},o_{T-1},\ldots,i_{t+1},o_{t+1},i_{t},i_{t-1},o_{t-1},\ldots,i_{1},o_{1}\right)=P\left(o_{t}|i_{t}\right) \quad \left(t=1,2,\ldots,T\right) \end{align}

观测序列生成算法:
输入：隐马尔科夫模型$\lambda =\left( A,B.\pi \right)$,观测序列长度$T$;
输出：观测序列$O=\left\{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right\}$；

1. 由初始概率向量$\pi$产生状态$i_{1}$；
2. $t=1$；
3. 由状态$i_{t}$的观测概率分布$b_{j}\left(k\right)$生成$o_{t}$；
4. 由状态$i_{t}$的状态转移概率分布$a_{i_{t}i_{t+1}}$生成状态$i_{t+1} \quad \left(i_{t+1}=1,2,\ldots,N\right)$；
5. $t=t+1$；如果$t<T$，转至3.；否则，结束。

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

1. 概率计算：已知$\lambda =\left( A,B.\pi \right)$和$O=\left\{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right\} $，计算$P\left(O| \lambda \right)$
2. 学习：已知$O=\left\{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right\}$，计算 $\lambda^* =\arg \max P\left( O|\lambda \right) $
3. 预测（编码）：已知$\lambda =\left( A,B.\pi \right)$和$O=\left\{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right\} $，计算 $I^* =\arg \max P\left( I|O \lambda \right) $

2 概率计算算法

前向概率 \begin{align} & \alpha _{t}\left( i\right) =P\left(o_{1},o_{2},\ldots ,o_{t}, i_{t}=q_{i}| \lambda \right) \end{align}
给定模型$\lambda$，时刻$t$部分观测序列为$o_{1},o_{2},\ldots ,o_{t}$且状态为$q_{i}$的概率。

前向概率递推计算\begin{align} & \alpha _{t}\left( i\right) =P\left(o_{1},o_{2},\ldots ,o_{t}, i_{t}=q_{i}| \lambda \right)＝P\left(i_{t}=q_{i},o_{1}^t \right) \\ & =\sum _{j=1}^{N}P\left(i_{t-1}=q_{j},i_{t}=q_{i},o_{1}^{t-1},o_{t}\right) \\ & =\sum _{j=1}^{N}P\left(i_{t}=q_{i},o_{t}|i_{t-1}=q_{j},o_{1}^{t-1}\right)\cdot P\left(i_{t-1}=q_{j},o_{1}^{t-1} \right) \\ & =\sum _{j=1}^{N}P\left(i_{t}=q_{i},o_{t}|i_{t-1}=q_{j}\right)\cdot \alpha _{t-1}\left( j\right)\\ & =\sum _{j=1}^{N}P\left(o_{t}|i_{t}=q_{i},i_{t-1}=q_{j}\right)\cdot P\left(i_{t}=q_{i}|i_{t-1}=q_{j}\right)\cdot \alpha _{t-1}\left( j\right) \\ & =\sum _{j=1}^{N}b_{i}\left(o_{t}\right)\cdot a_{ji}\cdot \alpha _{t-1}\left( j\right)\end{align}

概率计算\begin{align} & P\left(O| \lambda \right) =P\left(o_{1}^{T}| \lambda\right) \\ & = \sum_{i=1}^{N}P\left(o_{1}^{T},i_{T}=q_{i}\right)\\ & = \sum _{i=1}^{N}\alpha _{T}\left( i\right)\end{align}

观测序列概率计算的前向算法：
输入：隐马尔科夫模型$\lambda$,观测序列$O$;
输出：观测序列概率$P\left(O| \lambda \right)$；

1. 初值\begin{align} & \alpha _{1}\left( i\right)= \pi_{i}b_{i}\left(o_{1}\right) \quad \left(t=1,2,\ldots,N\right) \end{align}
2. 递推 对$t=1,2,\ldots,T-1$ \begin{align} & \alpha _{t+1}\left( i\right) =\sum _{j=1}^{N}b_{i}\left(o_{t+1}\right)\cdot a_{ji}\cdot \alpha _{t}\left( j\right) \quad \left(t=1,2,\ldots,N\right) \end{align}
3. 终止 \begin{align} & P\left(O| \lambda \right)= \sum _{j=1}^{N}\alpha _{T}\left( i\right)\end{align}

后向概率 \begin{align} & \beta_{t}\left( i\right) =P\left(o_{t+1},o_{t+2},\ldots ,o_{T}| i_{t}=q_{i} \lambda \right) \end{align}
给定模型$\lambda$，时刻$t$状态为$q_{i}$的条件下，从时刻$t+1$到时刻$T$的部分观测序列为$o_{t+1},o_{t+2},\ldots ,o_{T}$的概率。

后向概率递推计算\begin{align} & \beta _{t}\left( i\right) =P\left(o_{t+1},o_{t+2},\ldots ,o_{T}| i_{t}=q_{i}, \lambda \right)＝P\left(o_{t+1}^T |i_{t}=q_{i}\right) \\ & =\dfrac {P\left(o_{t+1}^{T}, i_{t}=q_{i}\right)} {P\left(i_{t}=q_{i}\right)}\\ & =\dfrac {\sum_{j=1}^{N} P\left(o_{t+1}^{T},i_{t}=q_{i},i_{t+1}=q_{j}\right)}{P\left(i_{t}=q_{i}\right)}\\ & =\sum_{j=1}^{N} \dfrac {P\left(o_{t+1}^{T}|i_{t}=q_{i},i_{t+1}=q_{j}\right) \cdot P\left(i_{t}=q_{i},i_{t+1}=q_{j} \right)}{P\left(i_{t}=q_{i}\right)} \\ & = \sum_{j=1}^{N} P\left(o_{t+1}^{T}|i_{t+1}=q_{j}\right) \cdot \dfrac {P\left(i_{t+1}=q_{j}|i_{t}=q_{i}\right) \cdot P\left(i_{t}=q_{i} \right)}{P\left(i_{t}=q_{i} \right)} \\ & = \sum_{j=1}^{N} P\left(o_{t+2}^{N},o_{t+1}|i_{t+1}=q_{j}\right) \cdot a_{ij} \\ & = \sum_{j=1}^{N} P\left(o_{t+2}^{T}|i_{t+1}=q_{j}\right) \cdot P\left(o_{t+1}|i_{t+1}=q_{j}\right) \cdot a_{ij} \\ & = \sum_{j=1}^{N} \beta_{t+1}\left(j\right) \cdot b_{j}\left(o_{t+1}\right) \cdot a_{ij}\end{align}

概率计算\begin{align} & P\left(O| \lambda \right) =P\left(o_{1}^{T}| \lambda\right) \\ & = \sum_{i=1}^{N}P\left(o_{1}^{T},i_{1}=q_{i}\right)\\ & = \sum_{i=1}^{N}P\left(i_{1}=q_{i}\right) \cdot P\left(o_{1}|i_{1}=q_{i}\right)\cdot P\left(o_{2}^{T}|i_{1}=q_{i}\right) \\ & = \sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}\left(i\right)\end{align}

观测序列概率计算的后向算法：
输入：隐马尔科夫模型$\lambda$,观测序列$O$;
输出：观测序列概率$P\left(O| \lambda \right)$；

1. 初值\begin{align} & \beta_{T}\left( i\right)= 1 \quad \left(t=1,2,\ldots,N\right) \end{align}
2. 递推 对$t=T-1,T-2,\ldots,1$ \begin{align} & \beta_{t}\left( i\right) =\sum_{j=1}^{N} \beta_{t+1}\left(j\right) \cdot b_{j}\left(o_{t+1}\right) \cdot a_{ij} \quad \left(t=1,2,\ldots,N\right) \end{align}
3. 终止 \begin{align} & P\left(O| \lambda \right)= \sum _{j=1}^{N}\pi_{i} b_{i}\left(o_{1}\right)\beta _{1}\left( i\right) \end{align}

$P \left( O | \lambda \right)$的前向概率、后向概率的表示
\begin{align} \\ & P \left( O | \lambda \right) ＝ P \left( o_{1}^{T} \right)
\\ & ＝ \sum_{i=1}^{N} \sum_{j=1}^{N} P \left( o_{1}^{t}, o_{t+1}^{T}, i_{t}=q_{i}, i_{t+1}=q_{j} \right)
\\ & ＝ \sum_{i=1}^{N} \sum_{j=1}^{N} P \left( o_{1}^{t}, i_{t}=q_{i}, i_{t+1}=q_{j} \right) P \left( o_{t+1}^{T} | i_{t+1}=q_{j} \right)
\\ & = \sum_{i=1}^{N} \sum_{j=1}^{N} P \left( o_{1}^{t}, i_{t}=q_{i} \right) P \left( i_{t+1}=q_{j} | i_{t}=q_{i} \right) P \left( o_{t+1}^{T} | i_{t+1}=q_{j} \right)
\\ & = \sum_{i=1}^{N} \sum_{j=1}^{N} P \left( o_{1}^{t}, i_{t}=q_{i} \right) P \left( i_{t+1}=q_{j} | i_{t}=q_{i} \right) P \left( o_{t+1} | i_{t+1}=q_{j} \right) P \left( o_{t+2}^{T} | i_{t+1}=q_{j} \right)
\\ & = \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{t} \left( i \right) a_{ij} b_{j} \left( o_{t+1} \right) \beta_{t+1} \left( j \right) \quad \quad \quad t=1, 2, \cdots, T-1\end{align}

给定模型$\lambda$和观测$O$，在时刻$t$处于状态$q_{i}$的概率
\begin{align} \\ & \gamma_{t} \left( i \right) = P \left( i_{t}=q_{i} | O, \lambda \right)
\\ & = \dfrac{ P \left( i_{t}=q_{i}, O | \lambda \right) } { P \left( O | \lambda \right) }
\\ & = \dfrac{ P \left( i_{t}=q_{i}, O | \lambda \right) } { \sum_{j=1}^{N} \left( i_{t}=q_{i}, O | \lambda \right) }
\\ & = \dfrac{ P \left( o_{1}^{t}, i_{t}=q_{i} \right) P \left( o_{t+1}^{T}| i_{t}=q_{i} \right) } { \sum_{j=1}^{N} P \left( o_{1}^{t}, i_{t}=q_{i} \right) P \left( o_{t+1}^{T}| i_{t}=q_{i} \right) }
\\ & = \dfrac{ \alpha_{t} \left( i \right) \beta_{t} \left( i \right)} { \sum_{j=1}^{N} \alpha_{t} \left( i \right) \beta_{t} \left( i \right) }\end{align}

给定模型$\lambda$和观测$O$，在时刻$t$处于状态$q_{i}$且在时刻$t+1$处于状态$q_{j}$的概率
\begin{align} \\ & \xi_{t} \left( i,j \right) = P \left( i_{t}=q_{i}, i_{t+1}=q_{j} | O ,\lambda \right)
\\ & = \dfrac{ P \left( i_{t}=q_{i}, i_{t+1}=q_{j},O | \lambda \right) } { P \left( O | \lambda \right) }
\\ & = \dfrac{ P \left( i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda \right) } { \sum_{i=1}^{N} \sum_{j=1}^{N} P \left( i_{t}=q_{i}, i_{t+1}=q_{j}, O|\lambda \right) }
\\ & = \dfrac{ \alpha_{t} \left( i \right) a_{ij} b_{j} \left( o_{t+1} \right) \beta_{t+1} \left( j \right) } { \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{t} \left( i \right) a_{ij} b_{j} \left( o_{t+1} \right) \beta_{t+1} \left( j \right)}\end{align}

在观测$O$下状态$i$出现的期望\begin{align} & \sum_{t=1}^{T} \gamma_{t} \left( i \right) = \sum_{t=1}^{T} P \left( i_{t}=q_{i} | O, \lambda \right) \end{align}

在观测$O$下由状态$i$转移的期望\begin{align} & \sum_{t=1}^{T－1} \gamma_{t} \left( i \right) = \sum_{t=1}^{T－1} P \left( i_{t}=q_{i} | O, \lambda \right) \end{align}

在观测$O$下由状态$i$转移到状态$j$的期望\begin{align} & \sum_{t=1}^{T－1} \xi_{t} \left( i,j \right) = \sum_{t=1}^{T－1} P \left( i_{t}=q_{i}, i_{t+1}=q_{j} | O, \lambda \right) \end{align}

3 学习算法

将观测序列作为观测数据$O$,将状态序列作为隐数据$I$，则隐马尔科夫模型是含有隐变量的概率模型
\begin{align} & P \left( O | \lambda \right) = \sum_{I} P \left( O | I, \lambda \right) P \left( I | \lambda \right)\end{align}

完全数据
\begin{align} & \left( O, I \right) = \left(o_{1}, o_{2}, \cdots, o_{T}, i_{1}, i_{2}, \cdots, o_{T} \right)\end{align}

完全数据的对数似然函数
\begin{align} & \log P \left( O, I | \lambda \right) \end{align}

$Q \left( \lambda, \overline{\lambda} \right)$函数
\begin{align} \\& Q \left( \lambda, \overline{\lambda} \right) = E_{I} \left[ \log P \left( O, I | \lambda \right) | O, \overline{\lambda} \right]
\\ & = \sum_{I} \log P \left( O, I | \lambda \right) P \left( I | O, \overline{\lambda} \right)
\\ & = \sum_{I} \log \dfrac{P \left( O, I | \lambda \right) P \left( O, I | \overline{\lambda} \right) }{P \left( O | \overline{\lambda} \right)}\end{align}
其中，$\overline{\lambda}$是隐马尔科夫模型参数的当前估计值，$\lambda$是隐马尔科夫模型参数。

由于对最大化$Q \left( \lambda, \overline{\lambda} \right)$函数，$P \left( O | \overline{\lambda} \right)$为常数因子，
以及\begin{align} & P \left( O, I | \lambda \right) = \pi_{i_{1}} b_{i_{1}} \left( o_{1} \right) a_{i_{1}i_{2}} b_{i_{2}} \left( o_{2} \right) \cdots a_{i_{T-1}i_{T}}b_{T}\left( o_{T} \right)\end{align}
所以求$Q \left( \lambda, \overline{\lambda} \right)$函数对$\lambda$的最大\begin{align} & \lambda = \arg \max{Q \left( \lambda, \overline{\lambda} \right) }\Leftrightarrow \arg\max \sum_{I} \log P \left( O, I | \lambda \right) P \left( O, I | \overline{\lambda} \right)
\\ & = \sum_{I} \log \pi_{i_{1}} P \left( O, I | \overline{\lambda} \right) + \sum_{I} \left( \sum_{t=1}^{T-1} \log a_{i_{t}i_{t+1}} \right) P \left( O, I | \overline{\lambda} \right) + \sum_{I} \left( \sum_{t=1}^{T} \log b_{i_{t}} \left( o_{t} \right) \right) P \left( O, I | \overline{\lambda} \right)\end{align}

对三项分别进行极大化：

1. \begin{align} & \max \sum_{I} \log \pi_{i_{1}} P \left( O, I | \overline{\lambda} \right) = \sum_{i=1}^{N} \log \pi_{i_{1}} P \left( O, i_{1}=i | \overline{\lambda} \right)
   \\ & s.t. \sum_{i=1}^{N} \pi_{i} = 1 \end{align}
   构造拉格朗日函数，对其求偏导，令结果为0 \begin{align} & \dfrac{\partial}{\partial \pi_{i}} \left[ \sum_{i=1}^{N} \log \pi_{i_{1}} P \left( O, i_{1}=i | \overline{\lambda} \right) + \gamma \left( \sum_{i=1}^{N} \pi_{i} - 1 \right) \right] = 0\end{align}
   得\begin{align} & P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} = 0
   \\ & \sum_{i=1}^{N} \left[ P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} \right] = 0
   \\ & \sum_{i=1}^{N} P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \sum_{i=1}^{N} \pi_{i} = 0
   \\ & P \left( O | \overline{\lambda} \right) + \gamma = 0
   \\ & \gamma = - P \left( O | \overline{\lambda} \right)\end{align}
   代入$P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} = 0$，得
   \begin{align} & \pi_{i} = \dfrac{P \left( O, i_{1} = i | \overline{\lambda} \right)}{P \left( O | \overline{\lambda} \right)}
   \\ & = \gamma_{1} \left( i \right) \end{align}
2. \begin{align} \\ & \max \sum_{I} \left( \sum_{t=1}^{T-1} \log a_{i_{t}i_{t+1}} \right) P \left( O, I | \overline{\lambda} \right) = \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{t=1}^{T-1} \log a_{ij} P \left( O, i_{t}=i, i_{t+1}=j | \overline{\lambda} \right)
   \\ & s.t. \sum_{j=1}^{N} a_{ij} = 1 \end{align}
   得\begin{align} \\ & a_{ij} = \dfrac{\sum_{t=1}^{T-1} P \left( O, i_{t}=i, i_{t+1}=j | \overline{\lambda} \right)}{\sum_{t=1}^{T-1} P \left( O, i_{t}=i | \overline{\lambda} \right)}
   \\ & = \dfrac{\sum_{t=1}^{T-1} \xi_{t} \left( i,j \right) }{\sum_{t=1}^{T-1} \gamma_{t} \left( i \right)}\end{align}
3. \begin{align} \\ & \max \sum_{I} \left( \sum_{t=1}^{N} \log b_{i_{t}} \left( o_{t} \right) \right) P \left( O, I | \overline{\lambda} \right) = \sum_{j=1}^{N} \sum_{t=1}^{T} \log b_{j} \left( o_{t} \right) P \left( O, i_{t}=j | \overline{\lambda} \right)
   \\ & s.t. \sum_{k=1}^{M} b_{j} \left( k \right) = 1 \end{align}
   得\begin{align} \\ & b_{j} \left( k \right) = \dfrac{\sum_{t=1}^{T} P \left( O, i_{t}=j | \overline{\lambda} \right) I \left( o_{t} = v_{k} \right)}{\sum_{t=1}^{T} P \left( O, i_{t}=j | \overline{\lambda} \right)}
   \\ & = \dfrac{ \sum_{t=1,o_{t}=v_{k}}^{T} \gamma_{t} \left( j \right)}{\sum_{t=1}^{T} \gamma_{t} \left( j \right)}\end{align}

Baum-Welch算法：
输入：观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$
输出：隐马尔科夫模型参数

1. 初始化
   对$n=0$，选取$a_{ij}^{ \left( 0 \right) },b_{j} \left( k \right)^{\left( 0 \right)},\pi_{i}^{\left( 0 \right)}$，得到模型$\lambda^{\left( 0 \right)} = \left( a_{ij}^{ \left( 0 \right) },b_{j} \left( k \right)^{\left( 0 \right)},\pi_{i}^{\left( 0 \right)} \right)$
2. 递推
   对$n=1,2, \cdots,$
   \begin{align} \\ & a_{ij}^{\left( n+1 \right)} = \dfrac{\sum_{t=1}^{T-1} \xi_{t} \left( i,j \right) }{\sum_{t=1}^{T-1} \gamma_{t} \left( i \right)}
   \\ & b_{j} \left( k \right)^{\left( n+1 \right)} = \dfrac{ \sum_{t=1,o_{t}=v_{k}}^{T} \gamma_{t} \left( j \right)}{\sum_{t=1}^{T} \gamma_{t} \left( j \right)}
   \\ & \pi_{i}^{\left( n+1 \right)} = \dfrac{P \left( O, i_{1} = i | \overline{\lambda} \right)}{P \left( O | \overline{\lambda} \right)} \end{align}
   其中，右端各值按观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$和模型$\lambda^{\left( n \right)} = \left( A^{\left( n \right)},B^{\left( n \right)},\pi^{\left( n \right)} \right)$计算。
3. 终止
   得到模型$\lambda^{\left( n＋1 \right)} = \left( A^{\left( n+1 \right)},B^{\left( n+1 \right)},\pi^{\left( n+1 \right)} \right)$

4 预测算法

在时刻$t$状态为$i$的所有单个路径$\left( i_{1}, i_{2}, \cdots, i_{t} \right)$中概率最大值
\begin{align} \\ & \delta_{t} \left( i \right) = \max_{i_{1}, i_{2}, \cdots, i_{t-1}} P \left(i_{t}=i, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1} | \lambda \right) \quad \quad \quad i = 1, 2, \cdots, N \end{align}

得递推公式\begin{align} \\ & \delta_{t+1} \left( i \right) = \max_{i_{1}, i_{2}, \cdots, i_{t}} P \left(i_{t+1}=i, i_{t}, \cdots, i_{1}, o_{t+1}, \cdots, o_{1} | \lambda \right)
\\ & = \max_{1 \leq j \leq N} \left[ \max_{i_{1}, i_{2}, \cdots, i_{t-1}} P \left( i_{t+1}=i, i_{t}=j, i_{t-1}, \cdots, i_{1}, o_{t+1}, o_{t}, \cdots, o_{1} | \lambda \right) \right]
\\ & = \max_{1 \leq j \leq N} \left[ \max_{i_{1}, i_{2}, \cdots, i_{t-1}} P \left( i_{t+1}=i, i_{t}=j, i_{t-1}, \cdots, i_{1}, o_{t}, o_{t-1}, \cdots, o_{1} | \lambda \right) P \left( o_{t+1} | i_{t+1}=i, \lambda \right)\right]
\\ & = \max_{1 \leq j \leq N} \left[ \max_{i_{1}, i_{2}, \cdots, i_{t-1}} P \left( i_{t}=j, i_{t-1}, \cdots, i_{1}, o_{t}, o_{t-1}, \cdots, o_{1} | \lambda \right) P \left( i_{t+1}=i | i_{t}=j, \lambda \right)P \left( o_{t+1} | i_{t+1}=i, \lambda \right)\right]
\\ & = \max_{1 \leq j \leq N} \left[ \delta_{t} \left( j \right) a_{ji}\right] b_{i} \left( o_{t+1} \right)\quad \quad \quad i = 1, 2, \cdots, N \end{align}

在时刻$t$状态为$i$的所有单个路径$\left( i_{1}, i_{2}, \cdots, i_{t} \right)$中概率最大值的路径的第$t-1$个结点
\begin{align} \\ & \psi_{t} \left( i \right) = \arg \max_{1 \leq j \leq N} \left[ \delta_{t-1} \left( j \right) a_{ji} \right] \quad \quad \quad i = 1, 2, \cdots, N \end{align}

维特比算法：
输入：模型$\lambda = \left( A, B, \pi \right)$和观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$
输出：最优路径$I^{} = \left( i_{1}^{}, i_{2}^{}, \cdots, i_{T}^{} \right)$

1. 初始化
   \begin{align} \\ & \delta_{1} \left( i \right) = \pi_{i} b_{i} \left( o_{1} \right) \quad \quad \quad i = 1, 2, \cdots, N
   \\ & \psi_{1} \left( i \right) = 0 \end{align}
2. 递推
   对$t=2,3, \cdots, T$
   \begin{align} \\ & \delta_{t} \left( i \right) = \max_{1 \leq j \leq N} \left[ \delta_{t-1} \left( j \right) a_{ji}\right] b_{i} \left( o_{t} \right)\quad \quad \quad i = 1, 2, \cdots, N
   \\ & \psi_{t} \left( i \right) = \arg \max_{1 \leq j \leq N} \left[ \delta_{t-1} \left( j \right) a_{ji} \right] \quad \quad \quad i = 1, 2, \cdots, N \end{align}
3. 终止 $$\begin{align} & P^* = \max_{1 \leq j \leq N} \delta_{T} \left( i \right) \\ & i_{T}^{*} = \arg \max_{1 \leq j \leq N} \left[ \delta_{T} \left( i \right) \right] \end{align}$$
4. 最优路径回溯
   对$t=T-1,T-2, \cdots, 1$ $$\begin{align} & i_{t}^{*} = \psi_{t+1} \left( i_{t+1}^{*} \right) \end{align}$$ 求得最优路径 $$I^* = \left( i_{1}^*, i_{2}^{*}, \cdots, i_{T}^* \right)$$