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

   隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可检测的状态随机序列（状态序列），再由各个状态生成一个观测而产生观测随机序列（观测序列）。

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

   设$Q=\{q_1,q_2,...,q_N\}$为状态集合，$V=\{v_1,v_2,..,v_M\}$为观测集合，N和M分别为状态和观测的数量。

   设序列长度为T，则状态序列和观测序列分别为：
   $$
   I=(i_1,i_2,...,i_T)
   \\O=(o_1,o_2,...,o_T)
   $$
   概率转移矩阵为：
   $$
   A=[a_{ij}]_{N*N}
   $$
   其中$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$是在时刻t处于状态$q_i$的条件下在时刻t+1转移到状态$q_j$的概率。

   观测概率矩阵为：
   $$
   B=[b_j(k)]_{N*M}
   $$
   其中$b_j(k)=P(o_t=v_k|i_t=q_j)$是在时刻t处于状态$q_j$的条件下生成观测$v_k$的概率。

   初始状态概率向量：
   $$
   \pi=(\pi_i)
   $$
   其中，$\pi_i=P(i_1=q_i)$是时刻t=1处于状态$q_i$的概率。

   隐马尔可夫模型$\lambda$由以上三要素决定，可以表示为：
   $$
   \lambda=(A,B,\pi)
   $$
   隐马尔可夫模型的两个基本假设：

   - 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关，即：
     $$
     P(i_{t}|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t|i_{t-1})
     $$

   - 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关，即：
     $$
     P(o_t|i_t,i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t|i_t)
     $$

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

   - 概率计算问题，给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,...,o_T)$，计算在模型$\lambda$下观测序列O出现的概率$P(O|\lambda)$。
   - 学习问题，已知观测序列$O=(o_1,o_2,...,o_T)$，估计模型$\lambda=(A,B,\pi)$的参数，使得在该模型下$P(O|\lambda)$最大。
   - 解码问题，给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,...,o_T)$，求最有可能的状态序列，及求使得$P(I|O)$最大的状态序列$I$。

2. 概率计算问题

   - 前向算法

     定义到时刻t部分观测序列为$o_1,o_2,...,o_t$且状态为$q_i$的概率为前向概率，记作：
     $$
     \alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)
     $$
     则：
     $$
     \alpha_1(i)=\pi(i)b_i(o_1)
     \\\alpha_{t+1}(i)=\sum_{j=1}^N\alpha_t(j)a_{ji}b_i(o_{t+1}),t=1,2,...,T
     \\P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)
     $$

   - 后向算法

     定义在时刻t状态为$q_i$的条件下，从t+1到T的部分观测序列为$o_{t+1},o_{t+1},...,o_T$的概率为后向概率，记作：
     $$
     \beta_t(i)=P(o_{t+1},o_{t+1},...,o_T|\lambda,i_t=q_i)
     $$
     则：
     $$
     \beta_T(i)=1
     \\\beta_t(i)=\sum_{j=1}^N\beta_{t+1}(j)b_j(o_{t+1})a_{ij},t=1,2,...,T
     \\P(O|\lambda)=\sum_{i=1}^N\pi(i)b_i(o_1)\beta_1(i)
     $$

   由前向概率和后向概率可得以下一些常用概率：
   $$
   P(O|\lambda)=\sum_{i=1}^N\alpha_t(i)\beta_t(i)
   \\=\sum_{j=1}^N\sum_{i=1}^N\alpha_t(i)a_{ij}b_j(o_t+1)\beta_{t+1}(j)
   \\
   P(i_t=q_i,O|\lambda)=\alpha_t(i)\beta_t(i)
   \\
   P(i_t=q_i|\lambda,O)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}
   \\=\frac{\alpha_t(i)\beta_t(i)}{\sum_{i=1}^N\alpha_t(i)\beta_t(i)}
   \\
   P(i_t=q_i,i_{t+1}=q_j|\lambda,O)=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{P(O|\lambda)}
   \\=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{j=1}^N\sum_{i=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}
   $$
   
3. 学习问题

   根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可以分别由监督学习和非监督学习实现。

   - 监督学习

     根据训练数据集，使用极大似然估计来估计隐马尔可夫模型的参数，分别为：

     设样本中时刻t处于状态i时刻t+1转移到状态j的频数为$A_{ij}$，那么状态转移概率的估计：
     $$
     \hat a_{ij}=\frac{A_{ij}}{\sum_{j=1}^NA_{ij}}
     $$
     设样本中状态为j且观测为k的频数为$B_{jk}$，则观测概率的估计：
     $$
     \hat b_j(k)=\frac{B_{jk}}{\sum_{k=1}^MB_{jk}}
     $$
     初始状态概率的估计$\hat \pi_i$为所有样本中初始状态为$q_i$的频率。

   - 非监督学习（Baum-Welch算法）

     假设仅能获取到观测数据O，不能获取到状态序列I，此时可以应用EM算法对隐马尔可夫模型进行参数估计。
     
     设观测数据$O=(o_1,o_2,...,o_T)$，隐数据$I=(i_1,i_2,...,i_T)$，其中T为序列长度。设隐马尔可夫模型当前的估计参数为$\overline\lambda$，则EM算法的Q函数为：
     $$
     Q(\lambda,\overline\lambda)=E_I(\log P(O,I|\lambda)|O,\overline\lambda)
     \\=\sum_I\log P(O,I|\lambda)P(I|O,\overline\lambda)
     \\=\sum_I\log P(O,I|\lambda)P(I,O|\overline\lambda)\frac{1}{P(O|\overline\lambda)}
     \\\propto\sum_I\log P(O,I|\lambda)P(I,O|\overline\lambda)
     \\=\sum_I\log(\pi_{i_1}b_{i_1}(o_1)a_{i_1,i_2}...a_{i_{T-1},i_T}b_{i_T}(o_T))P(I,O|\overline\lambda)
     \\=\sum_I\log\pi_{i_1}P(I,O|\overline\lambda)+\sum_I(\sum_{t=1}^{T-1}\log a_{i_ti_{t+1}})P(I,O|\overline\lambda)+\sum_I(\sum_{t=1}^{T}\log b_{i_t}(o_t))P(I,O|\overline\lambda)
     $$
     

   因为要极大化的参数$\pi,A,B$单独出现在三个项中，所以只需对各项分别极大化。

   因为：
   $$
   \sum_I\log\pi_{i_1}P(I,O|\overline\lambda)=\sum_{i=1}^N\log\pi_iP(O,i_1=i|\overline\lambda)
   \\\sum_{i=1}^N\pi_i=1
   $$
   于是利用拉格朗日乘子法并令偏导数等于0可以求得：
   $$
   \pi_i=\frac{P(O,i_1=i|\overline\lambda)}{P(O|\overline\lambda)}
   $$
   利用相同方法可以分别求得A和B，在此不再赘述，结果为：
   $$
   a_{i,j}=\frac{\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1}=j|\overline\lambda)}{\sum_{t=1}^{T-1}P(O,i_t=i|\overline\lambda)}
   \\b_j(k)=\frac{\sum_{t=1}^{T}P(O,i_t=j|\overline\lambda)I(o_t=v_k)}{\sum_{t=1}^{T}P(O,i_t=j|\overline\lambda)}
   $$
   其中I为指示函数。

4. 解码问题

   - 近似算法

     每个时刻选择该时刻最有可能出现的状态，即对应$P(i_t=q_i|\lambda,O)$最大的状态。

     近似算法的优点是计算简单，缺点是不能保证预测的状态概率整体式最有可能的状态序列。

   - 维特比算法

     记$\delta_t\in\mathbb{R}^N$，其第i维$\delta_t(i)$表示t时刻以状态$q_i$结尾的所有路径的得分中的最大得分，则：
     $$
     \delta_{t+1}(i)=\max_{1\le j\le N}[\delta_{t}(j)a_{ji}]b_i(o_{t+1})
     $$
     同时使用$\psi\in\mathbb{R}^{N*T}$来方便进行路径回溯，矩阵第t行第i列对应元素$\psi_{i,j}$表示第t个时刻以状态$q_i$结尾时得分最大路径的第t-1时刻所对应的状态，即：
     $$
     \psi_{t+1,i}=\arg\max_{1\le j\le N}[\delta_{t}(j)a_{ji}]
     $$
     通过$\delta$和$\psi$进行回溯即可求得最优路径。

