12.HMM

隐马尔可夫模型（HMM）是离散状态空间模型，参数为 $(\pi ,A,B)$。解决评估、学习和译码三个问题。

动态模型分类

模型	状态变量特点
HMM	离散
Kalman 滤波	连续、线性
粒子滤波	连续、非线性

HMM 假设

齐次 Markov 假设： $p(i_{t+1}|i_t,\cdots ,i_1)=p(i_{t+1}|i_t)$

观测独立假设： $p(o_t|i_t,\cdots ,i_1)=p(o_t|i_t)$

三个问题

问题	目标	算法
评估	$p(O\Vert \lambda )$	前向后向
学习	${\mathrm{argmax}}_{\lambda }p(O\Vert \lambda )$	EM (Baum-Welch)
译码	${\mathrm{argmax}}_{I}p(I\Vert O,\lambda )$	Viterbi

前向算法

${\alpha }_t(i)=p(o_1,\cdots ,o_t,i_t=q_i|\lambda )$

递推：

${\alpha }_{t+1}(j)={\sum }_{i=1}^N{b}_j(o_{t+1})a_{ij}{\alpha }_t(i)$

$p(O|\lambda )={\sum }_{i=1}^N{\alpha }_T(i)$

后向算法

${\beta }_t(i)=p(o_{t+1},\cdots ,o_T|i_t=q_i)$

递推：

${\beta }_t(i)={\sum }_{j=1}^N{b}_j(o_{t+1})a_{ij}{\beta }_{t+1}(j)$

Viterbi 算法

${\delta }_{t+1}(j)={\max }_{1\le i\le N}{\delta }_t(i)a_{ij}{b}_j(o_{t+1})$

${\psi }_{t+1}(j)={\mathrm{argmax}}_{1\le i\le N}{\delta }_t(i)a_{ij}$

推断任务

任务	公式
滤波	$p(z_t\Vert x_{1:t})=C{\alpha }_t(z_t)$
平滑	$p(z_t\Vert x_{1:T})=C{\alpha }_t(z_t){\beta }_t(z_t)$
预测	$p(z_{t+1}\Vert x_{1:t})={\sum }_{z_t}p(z_{t+1}\Vert z_t)p(z_t\Vert x_{1:t})$