HMM简介

---

HMM的前提假设

        +------+     +------+     +------+     +------+

Start-> | S₁   | --> | S₂   | --> | S₃   | --> | Sₙ   |

        +------+     +------+     +------+     +------+

           |             |             |             |

           v             v             v             v

        +------+     +------+     +------+     +------+

        | O₁   |     | O₂   |     | O₃   |     | Oₙ   |

        +------+     +------+     +------+     +------+

• 马尔科夫性：t时刻状态，只和t-1时刻状态有关，和更前的无关

• 观测独立性：t时刻观测值只依赖该时刻的状态，和其他任何时刻的观测值以及状态无关

HMM中拿到数据集之后，我们建模他们的联合概率函数：

$$\begin{aligned} P(O_1, O_2, ...,O_n, X_1, X_2, ..., X_n) &= P(X_1, O_1, X_2, O_2, ..., X_n, O_n) \\ &= P(X_1) * P(O_1 | X_1) * P(X_2 | X_1 O_1) * P(O_2|X_2X_1O_1) * ...\\ &=P(X_1) * P(O_1 | X_1) * P(X_2 | X_1) * P(O_2 | X_2) * ....P(X_n | X_{n - 1}) * P(O_n | X_n) \\ &=P(X_1) P(O_1 | X_1) \prod_{t = 2}^n P(X_t | X_{t - 1}) P(O_t | X_t) \end{aligned}$$

因此，联合概率只依赖：

• $P(X_1)$: 初始状态概率分布，不妨记作$\pi$

• $P(X_t | X_{t - 1})$：状态转移概率矩阵，不妨记作$A$

• $P(O_t | X_t)$ ：给定状态时候，观测值的概率分布，也叫做发射概率，不妨记作$B$

HMM的所有计算和预测，都围绕如何从数据集中计算得到$\lambda = (\pi, A, B)$

• 评估问题：已知$\lambda = (\pi, A, B)$ 和观测序列$O_1, O_2, ... , O_n$, 需要计算这个观测序列的出现概率, 一般解法为前向算法或者后向算法

• 预测问题：已知$\lambda = (\pi, A, B)$ 和观测序列$O_1, O_2, ... , O_n$， 预测最有可能的状态序列，一般用贪心算法或者维特比算法

• 学习问题：模型参数$\lambda = (\pi, A, B)$ 未知，需要学习推断，分为两种场景：

  • 已知诸多观测序列和状态序列的监督学习，直接根据数据集统计出$A$矩阵和$B$矩阵

  • 只知道观测序列，不知道背后状态情况的无监督学习，这个常常采用EM算法

关于评估问题：

$$\begin{aligned} P(O_1, O_2, ..., O_n) &= \sum_{所有可能的状态序列X} P(O, X) \\ &= \sum_{x_1, x_2, ..., x_n} P(o_1, o_2, ..., o_n, x_1, x_2, ..., x_n) \end{aligned}$$

由于状态序列的可能性是指数级增长的, 如果状态有$T$种可能，那么状态序列有$T^N$种可能，不可能穷尽, 于是改成采用动态规划的前向算法，具体算法过程没看。

关于预测问题

$$\begin{aligned} MAX_{x_1, x_2, ..., x_n}P(x_1, x_2, ..., x_n) & = MAX(P(x_1)) * MAX(P(x_2)) * ... * MAX(P(x_n)) (贪心解法) \end{aligned}$$

希望找到一个状态序列$x_1, x_2, ..., x_n$, 使得概率最大，那么贪心的解法就是令每个状态的出现概率最大，即每次选择概率最大的状态。

维特比算法没看。

关于学习问题

有监督场景

既然已经知道每个观测背后的状态是什么，那状态转移矩阵和发射矩阵很好直接统计出来：

• 将状态序列划分为二元组，就能直接得到一个状态到另外一个状态的频率，最后归一化为概率

• 直接统计一个状态到某种观测的次数，就能得到发射频率，最后归一化为发射概率

无监督场景

只能看到观测序列，不知道背后的状态是什么，反正就是学习出模型参数$\lambda = (\pi, A, B)$ ， 使得$P(O | \lambda)$最大 。

那就采用EM算法，但是这个HMM中用的的EM算法的E步骤有点奇怪，暂时解决不了