#!/usr/bin/env python
# coding: utf-8

# 状态集合\begin{align*} & Q=\left\{q_{1},q_{2},\ldots ,q_{N}\right\}  \quad \left| Q\right| =N \end{align*}  

# 观测集合\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) $

# 前向概率 \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*}

# 将观测序列作为观测数据$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)$

# 在时刻$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)$