隐马尔科夫模型HMM

HMM的贝叶斯网络

HMM (Hidden Markov Model)是关于时序的概率模型,描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列,再由各个状态生成观测随机序列的过程.

HMM的定义

HMM的参数

$Q$ 是所有可能的状态的集合, 其中 $N$ 是可能的状态数;

$V$ 是所有可能的观测的集合, 其中 $M$ 是可能的观测数;

$Q=\{q_1,q_2,\cdots,q_N\},\quad V=\{v_1,v_2,\cdots,v_M\}$

$I$ 是长度为 $T$ 的状态序列; $O$ 是对应的观测序列:

$I=\{i_1,i_2,\cdots,i_T\},\quad O=\{o_1,o_2,\cdots,o_T\}$

HMM的三要素

HMM由初始概率分布 $\pi$ (向量)、状态转移概率分布 $A$ (矩阵) 以及观测概率分布 $B$ (矩阵) 确定. $\pi$ 和 $A$ 决定状态序列, $B$ 决定观测序列。因此, HMM可以用三元符号表示, 称为HMM的三要素:

$\lambda=(A, B,\pi)$

• $A$ 是状态转移概率矩阵:

  $A=[a_{ij}]_{N\times N}$

  其中, $a_{ij}$ 是在时刻 $t$ 处于状态 $q_i$ 的条件下时刻 $t+1$ 转移到状态 $q_j$ 的概率:

  {% math %}a{ij}=P(i{t+1}=q_j\mid i_t=q_i), \quad i=1,2,\cdots,N;j=1,2,\cdots,N{% endmath %}

• $B$ 是观测转移概率矩阵:

  {% math %}B=[b{j}(k)]{N\times M}{% endmath %}

  其中, $b_{j}(k)$ 是在时刻 $t$ 处于状态 $q_i$ 的条件下生成观测 $v_k$ 的概率:

  {% math %}b_j(k)=P(o_t=v_k\mid i_t=q_j),\quad k=1,2,\cdots,M;j=1,2,\cdots,N{% endmath %}

• $\pi$ 是初始状态概率向量:

  $\pi=(\pi_i)_{N\times 1}$

  其中, {% math %}\pi_i{% endmath %} 是时刻 {% math %}t=1{% endmath %} 处于状态 {% math %}q_i{% endmath %} 的概率

  {% math %}\pi_i=P(i_1=q_i),\quad i=1,2,\cdots,N{% endmath %}

HMM的两个假设

• 齐次马尔可夫性假设 任意时刻 t 的状态, 只依赖于其前一刻的状态, 与其他时刻的状态及观测无关, 也与时刻 t 无关.

  {% math %}P(it\mid i{t-1},o{t-1},\cdots,i_1,o_1)=P(i_t\mid i{t-1}), \quad t=1,2,\cdots,T{% endmath %}

• 观测独立性假设 任何时刻的观测只依赖于该时刻的马尔科夫链状态. 与其他观测及状态无关.

  {% math %}P(ot\mid i{T},o{T},\cdots,i{t},o{t},\cdots,i_1,o_1)=P(o_t\mid i{t}), \quad t=1,2,\cdots,T{% endmath %}

HMM的三个基本问题

• 概率计算问题: 前向-后向算法——动态规划
  • 给定模型 $\lambda=(A, B,\pi)$ 和观测序列 $O=\{o_1,o_2,\cdots,o_T\}$
  • 计算模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O\mid \lambda)$
• 学习问题: Baum-Welch算法(状态未知)——EM
  • 已知观测序列$O=\{o_1,o_2,\cdots,o_T\}$
  • 估计模型 $\lambda=(A, B,\pi)$ 的参数,使得在该模型下观测序列 $P(O\mid \lambda)$ 最大
• 预测问题: Viterbi算法——动态规划
  • 已知模型 $\lambda=(A, B,\pi)$, 和观测序列 $O=\{o_1,o_2,\cdots,o_T\}$
  • 求给定观测序列条件概率 $P(I\mid O, \lambda)$ 最大的状态序列 $I=\{i_1,i_2,\cdots,i_T\}$

概率计算问题

直接计算法

• 状态序列 $I=\{i_1,i_2,\cdots,i_T\}$ 的概率:

  $P(I\mid\lambda)=P(i_1)P(i_2\mid i_1)\cdots P(i_T\mid i_{T-1})=\pi_{i_1}a_{i_1i_2}\cdots a_{i_{T-1}i_T},\quad O(T-1)$

• 对固定的状态序列 $I=\{i_1,i_2,\cdots,i_T\}$ ,观测序列 $O=\{o_1,o_2,\cdots,o_T\}$ 的概率是:

  $P(O\mid I, \lambda)=P(o_1\mid i_1)\cdots P(o_T\mid i_T)=b_{i_1}(o_1)b_{i_2}(o_2)\cdots b_{i_T}(o_T), \quad O(T)$

• O 和 I 同时出现的联合概率:

$$\begin{align} P(O,I\mid\lambda)&=P(O\mid I, \lambda)P(I\mid\lambda)\notag\\ &=\pi_{i_1}a_{i_1i_2}b_{i_1}(o_1)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T),\quad\quad O(2T-1)=O(T)\notag \end{align}$$

• 对所有可能的状态序列I求和,得到观测序列O的概率

$$\begin{align} P(O\mid\lambda)&=\sum_I P(O\mid I, \lambda)P(I\mid\lambda)\notag\\ &=\sum_{\underbrace{i_1,i_2, \cdots ,i_T}_{N\times N\times \cdots \times N}}\pi_{i_1}a_{i_1i_2}b_{i_1}(o_1) \cdots a_{i_{T-1}i_T}b_{i_T}(o_T),\quad\quad O(TN^T)\notag \end{align}$$

前向 - 后向概率

• 前向概率: 给定隐马尔科夫模型 λ, 定义到时刻 t , 部分观测序列为 $o_1,o_2,...,o_t$ 且状态为 $q_i$ 的概率

$$\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i\mid\lambda)$$

• 后向概率: 给定隐马尔科夫模型 λ, 定义到时刻 t , 状态为 $q_i$ 的条件下, 从 t+1 到 T 的部分 观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的概率

$$\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T\mid i_t=q_i, \lambda)$$

前向算法

(1) 初值:

$\alpha_1(i)=\pi_i b_i(o_1),\quad i=1,2,\cdots,N$

(2) 递推: 对于 $t=1,2,\cdots,T-1$

$\alpha_{t+1}(i)=\big[\sum_{j=1}^N\alpha_t(j)a_{ji}\big]b_i(o_{t+1})\quad i=1,2,\cdots,N$

(3) 最终:

$P(O\mid \lambda)=\sum_{i=1}^N\alpha_T(i)$

后向算法

(1) 初值:

$$\beta_T(i)=1,\quad i=1,2,\cdots,N$$

(2) 递推: 对于 $t=T-1,T-2,\cdots,1$

$$\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),\quad i=1,2,\cdots,N$$

(3) 最终:

$$P(O\mid \lambda)=\sum_{i=1}^N\pi_i b_i(o_1)\beta_1(i)$$

学习问题

Baum-Welch算法

预测算法

Viterbi算法

反馈与建议

• 微博：@Girl_AI

参考文献

• 统计学习方法
• 七月算法机器学习在线班