1. 隐马尔可夫模型的基本概念
1.1 定义
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。
- 马尔可夫链：隐藏的马尔可夫链随机生成的状态的序列
- 每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列
1.2 三要素
隐马尔可夫模型由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和 观测概率矩阵 $B$ 决定。 $ \pi $ 和 $A$ 决定状态序列，$B$ 决定观测序列。
1.3 两个基本假设
- 齐次马尔可夫性假设：假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻的状态集观测无关，也与时刻 $t$ 无关
- 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关
1.4 隐马尔可夫模型的3个基本问题
- 概率计算问题。 给定模型 $\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=(i_1, i_2, …, i_T)$ 。即给定观测序列，求最有可能的对应的状态序列。
2. 概率计算算法
2.1 直接计算法
给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1, o_2, … , o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$
通过列举所以可能的长度为 $T$ 的状态序列 $I=(i_1, i_2, …, i_T)$， 求各个状态序列 $I$ 与观测序列 $O=(o_1, o_2, … , o_T)$ 的联合概率 $ P(O, I | \lambda)$，然后对所有可能的状态序列求和，得到 $P(O|\lambda)$
- 时间复杂度 $O(TN^T)$
2.2 前向算法
前向概率：给定隐马尔可夫模型 $\lambda $，定义到时刻 $t$ 部分观测序列为 $o_1, o_2, … , o_t $ 且状态为 $q_i$ 的概率为前向概率，记作
结合动态规划递推求解 $ \alpha_t(i) $ 即观测序列概率 $P(O|\lambda)$
- 时间复杂度 $O(TN^2)$
2.3 后向算法
后向概率：给定隐马尔可夫模型 $\lambda $，定义在时刻 $t$ 状态为 $qi$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o{t+1}, o_{t+2}, … , o_T $ 的概率为后向概率，记作
结合动态规划递推求解 $ \beta_t(i) $ 即观测序列概率 $P(O|\lambda)$
- 时间复杂度 $O(TN^2)$
3. 学习算法
3.1 监督学习方法
状态数据和观测序列都存在的训练数据，利用极大似然估计发来估计隐马尔可夫模型的参数
- 转移概率
- 观测概率
- 初始状态概率
3.2 Baum-Welch算法
Todo
4. 预测算法
4.1 近似算法
贪心思想，在每个时刻 $t$ 选择该时刻最有可能出现的状态，优点是计算简单，缺点是不能保证预测的状态序列整体是最优可能的状态序列。
4.2 维特比算法
用动态规划求概率最大路径（最优路径），这时一条路径对应着一个状态序列。
下一步规划：补充EM算法，CRF
