马尔科夫模型和HMM的最大区别在于，马尔科夫模型中的状态是离散，外在的，可以被观察到。而HMM中状态变成了一个隐藏的值，只能通过观察值来猜测。观察值是状态值的条件随机变量。在这里，每个状态都可以看作是一个分布的均值\(\mu_i\)，而观测到的值\(x_i\)相当于\(\mu_i + \epsilon_i\)，其中\(\epsilon_i\)可以理解为是随机误差
HMM的定义 一个HMM由以下三部分组成 - 一个\(S \times S\)的马尔科夫转移矩阵\(A\)，描述\(S\)个状态之前的转移关系 - 概率分布\(\pi\)描述初始状态的分布 - 相关于状态的发射概率分布，即\(s_i=k\)时观察到\(x_i\)的概率，即\(p(x_i|\theta_{S_i})\)。该矩阵记为\(B\) 观察到的序列\((x_1, x_2, x_3, \ldots)\)通过如下方法生成 1. 通过\(s_1 \sim {\rm Discrete}(\pi)\)生成初始状态，然后通过\(x_1 \sim p(x|\theta_{S_1})\)生成第一个观测值 2. 从马尔科夫状态链取样，\(s_i|\{s_{i-1}=k'\} \sim {\rm Discrete}(A_{k',:})\)，然后由\(s_i\)生成观察值\(x_i|s_i \sim p(x|\theta_{s_i})\)
其中根据\(p(x|\theta_s)\)的分布形式又可以将HMM分成两种：连续HMM（概率分布是连续分布），这里该分布通常是高斯分布；离散HMM（概率分布是离散分布，\(\theta_s\)是概率值组成的向量）。注意无论是连续HMM还是离散HMM其背后的状态的分布都是离散的，只不过条件概率形式不同
为方便起见，本课中涉及到的HMM均为离散HMM
关于HMM的预测问题，常见的有三种
- 估计状态：给定HMM\(\{\pi, A, B\}\)和观测序列\((x_1, \ldots, x_T)\)，估计是哪个状态产生了\(x_i\)，即\(p(s_i = k|x_1, \ldots, x_T, \pi, A, B)\)——使用前向后向算法
- 估计状态序列：给定HMM\(\{\pi, A, B\}\)和观测序列\((x_1, \ldots, x_T)\)，估计观测序列背后的状态序列，即\(s_1, \ldots, s_T = {\rm arg}\max_{s} p(s_1, \ldots, s_T|x_1, \ldots, x_T, \pi, A, B)\)——使用Viterbi算法
- 学习HMM：给定观测序列\(x_1, \ldots, x_T\)，使用最大似然估计HMM的参数\(\pi, A, B\)，即 \[ \pi_{\rm ML}, A_{\rm ML}, B_{\rm ML} = {\rm arg}\max_{\pi, A, B} p(x_1, \ldots, x_T|\pi, A, B) \]
为了学习HMM中的参数，我们要最大化\(p(\vec{x}|\pi, A, B)\)。将状态和时序展开，有 \[ \begin{align*} p(\vec{x}|\pi, A, B) &= \sum_{s_1=1}^S\cdots \sum_{s_T=1}^S p(\vec{x},s_1, \ldots, s_T|\pi, A, B) \\ &= \sum_{s_1=1}^S\cdots \sum_{s_T=1}^S \prod_{i=1}^T p(x_i|s_i, B)p(s_i|s_{i-1}, \pi, A) \end{align*} \] 其中有 \[ \begin{align*} p(x_i|s_i, B) &= B_{s_i, x_i} \\ p(s_i|s_{i-1}, \pi, A) &= A_{s_{i-1}, s_i}\ ({\rm or}\ \pi_{s_1}) \end{align*} \]
直接求解非常困难。但是如果把\(s_i\)看作是隐变量，可以使用EM算法求解。回顾EM算法可以表示为 E步：使用\(q(\vec{s}) = p(\vec{s}|\vec{x}, \pi, A, B)\)计算 \[ \mathcal{L}(\vec{x}, \pi, A, B) = \mathbb{E}_q[\ln p(\vec{x}, \vec{s}|\pi, A, B)] \] M步：以\(\pi, A, B\)最大化\(\mathcal{L}\)
其中 \[ \ln p(\vec{x}, \vec{s}|\pi, A, B) = \sum_{i=1}^T\sum_{k=1}^S\underbrace{1(s_i=k)\ln B_{k, x_i}}_{\rm observations} + \sum_{k=1}^S \underbrace{1(s_1=k)\ln \pi_k}_{\rm initial\ state} + \sum_{i=2}^T\sum_{j=1}^S\sum_{k=1}^S\underbrace{1(s_{i=1}=j, s_i=k)\ln A_{j,k}}_{\rm Markov\ chain} \]
E步 考虑指示变量的期望等于其对应事件发生的概率，则可以定义两个条件后验概率变量
- \(\gamma_i(k)\)，\(s_i = k\)的后验概率
- \(\xi_i(j,k)\)，\(s_{i-1}=j\)且\(s_i=k\)的后验概率
这两个变量可以通过前向后向算法算出来。因此E步为 \[ \mathcal{L} = \sum_{k=1}^S \gamma_1(k)\ln \pi_k + \sum_{i=2}^T\sum_{j=1}^S\sum_{k=1}^S \xi_i(j,k)\ln A_{j,k} + \sum_{i=1}^T\sum_{k=1}^S \gamma_i(k)\ln B_{k,x_i} \]
M步
\[ \pi_k = \frac{\gamma_1(k)}{\sum_j \gamma_1(j)}, A_{j,k}=\frac{\sum_{i=2}^T \xi_i(j,k)}{\sum_{i=2}^T\sum_{l=1}^S \xi_i(j,l)}, B_{k,v}=\frac{\sum_{i=1}^T \gamma_i(k)1\{x_i = v\}}{\sum_{i=1}^T \gamma_i(k)} \]
由于一个HMM可能产生多个序列，则若我们有\(N\)个序列，上式可以修改为
\[ \pi_k = \frac{\sum_{n=1}^N \gamma_1^n(k)}{\sum_{n=1}^N\sum_j \gamma_1^n(j)}, A_{j,k}=\frac{\sum_{n=1}^N\sum_{i=2}^{T_n} \xi_i^n(j,k)}{\sum_{n=1}^N\sum_{i=2}^{T_n}\sum_{l=1}^S \xi_i^n(j,l)}, B_{k,v}=\frac{\sum_{n=1}^N\sum_{i=1}^{T_n} \gamma_i^n(k)1\{x_i = v\}}{\sum_{n=1}^N\sum_{i=1}^{T_n} \gamma_i^n(k)} \]
