HMM

马尔科夫链

一个随机过程在某一个时刻的状态只与前n个时刻的状态有关，这个过程称为n阶马尔科夫过程。最简单的马尔科夫过程就是一阶马尔科夫过程，即任一时刻的状态只与前一个时刻的状态有关。时间和状态都是离散值的一阶马尔科夫过程即为马尔科夫链（Markov Chain）。一个马尔科夫链由3部分组成：

  • $S = \lbrace 1, …, N \rbrace$: 状态集合
  • $\pi = \lbrace \pi_1, \pi_2, …, \pi_N \rbrace$: 系统初始时处于各个状态的概率
  • $A = \lbrace a_{i,j} \rbrace$: 转移矩阵，$a_{i,j}$ 表示由状态 $i$ 到 $j$ 的转移概率，$\sum_{j=1}^n a_{i,j} = 1$

有了这些，给定一个状态序列 $x_0 x_1 … x_T$，我们很容易计算该序列发生的概率

\[P(x_0 x_1 ... x_T) = p(x_0)\prod_{i=1}^T p(x_i \vert x_{i-1})\]

隐马尔科夫模型

马尔科夫链常被用来计算一个可观察序列的概率。但是我们感兴趣的事件并不总是可以被直接观察，比如一串文本，文本中的每个单词是可观察的，但是每个单词的词性并不是可以直接观察的，我们需要从文本串中推断每个单词的词性。隐马尔科夫模型（Hidden Markov Model, HMM）可以用来对这类问题建模，一个HMM模型由5个部分组成：

  • $S = \lbrace 1, 2, …, N \rbrace$: 状态集合
  • $\pi = \lbrace \pi_1, \pi_2, …, \pi_N \rbrace$: 系统初始时处于各个状态的概率
  • $A = \lbrace a_{i,j} \rbrace$: 转移矩阵，即系统由一个状态转移到另一个状态的概率
  • $O = \lbrace o_1, o_2, …, o_M \rbrace$: 一个观察到的状态序列，
  • $B = \lbrace b_i(k) \rbrace$: 观测概率分布矩阵，$b_i(k)$ 表示系统处于状态 $i$ 时观察到 $o_k$ 的概率

HMM可以表示为 $\Phi = (A, B, \pi)$, 它主要有3个基本问题：

  1. 概率计算问题（Evaluation）。给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$ , 计算该观察序列发生的概率 $P(O \vert \Phi)$
  2. 解码问题(Decoding)。给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$, 求解最可能的状态序列 $S = \lbrace s_1, s_2, …, s_T \rbrace$
  3. 学习问题(Learning)。给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$, 调整模型参数 $\Phi$ 以使 $P(O \vert \Phi)$ 最大。

下面将介绍如何求解这3类问题。

概率计算问题

给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$, 可以使用前向算法来计算该观察序列发生的概率 $P(O \vert \Phi)$:

  1. Initialization

    \[\alpha_1(i) = \pi_i b_i(o_1),\ \ \ \ \ 1 \leq i \leq N\]

  2. Induction

    \[\alpha_t(i) = (\sum_{j=1}^N \alpha_{t-1}(j) a_{j, i})b_i(o_t),\ \ \ \ \ 2 \leq t \leq T, 1 \leq i \leq N\]

  3. Termination

    \[P(O \vert \Phi) = \sum_{i=1}^N \alpha_T(i)\]

解码问题

给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$, 求解最可能的状态序列 $S = \lbrace s_1, s_2, …, s_T \rbrace$, 可以使用Viterbi算法求解:

  1. Initialization

    \(V_1(i) = \pi_i b_i(o_1), \ \ \ \ \ 1 \leq i \leq N\) \(B_1(i) = 0, \ \ \ \ \ 1 \leq i \leq N\)

  2. Induction

    \[V_t(i) = \max_{1 \leq j \leq N} \lbrace V_{t-1}(j)a_{j,i} \rbrace b_i(o_i), \ \ \ \ \ 2 \leq t \leq T\] \[B_t(i) = \mathop{argmax}_{1 \leq j \leq N} \lbrace V_{t-1}(j) a_{j,i} \rbrace, \ \ \ \ \ 2 \leq t \leq T\]

  3. Termination

    \(best\ score = \max_{1 \leq i \leq N} V_T(i)\) \(s_T^* = \mathop{argmax}_{1 \leq i \leq N} B_T(i)\)

  4. Backtracking

    \(s_t^* = B_{t+1}(s_{t+1}^*), \ \ \ \ \ \ t = T-1, T-2, ..., 1\) \(S^* = (s_1^*, s_2^*, ..., s_T^*)\)

学习问题

给定模型 $\Phi$ 和一个观察序列 $O = \lbrace o_1, o_2, …, o_T \rbrace$, 可以使用Baum-Welch算法来调整模型参数 $\Phi$ 以使 $P(O \vert \Phi)$ 最大。Baum-Welch算法也叫Forward-Backward算法，是EM算法的一种。
为了理解Baum-Welch算法，先定义后向概率 $\beta$ 为时刻t状态为i时，我们观察到t+1到T状态为$o_{t+1}, o_{t+2}, …, o_T$的概率

\[\beta_t(i) = P(o_{t+1}, o_{t+2}, ..., o_T \vert s_t = i, \Phi)\]

我们可以像前向算法那样计算 $\beta$

  1. Initialization

    \[\beta_T(i) = 1, \ \ \ \ \ 1 \leq i \leq N\]

  2. Recursion

    \[\beta_t(i) = \sum_{j=1}^N a_{i,j} b_j(o_{t+1}) \beta_{t+1}(j), \ \ \ \ \ \ 1 \leq i \leq N, 1 \leq t \leq T\]

  3. Termination

    \[P(X \vert \Phi) = \sum_{i=1}^N \pi_i b_i(o_1) \beta_1(i)\]

先看一下如何估算转移概率

\[\hat{a}_{i,j} = \frac{expected \ number \ of \ transitions \ from \ state \ i \ to \ state \ j}{expected \ number \ of \ transitions \ from \ state \ i}\]

为了估算从状态i到状态j的期望转移次数，定义概率 $\xi$ 为时刻t状态为i且时刻t+1状态为j的概率，即

\[\xi_t(i, j) = P(s_t=i, s_{t+1} = j \vert O, \Phi)\]

为了计算 $\xi_t(i, j)$, 先计算

\[\begin{split} non\_quite\_\xi_t(i, j) & = P(s_t=i, s_{t+1}=j, O \vert \Phi) \\ & = \alpha_t(i) a_{i,j} b_j(o_{t+1}) \beta_{t+1}(j) \end{split}\]

根据前向算法，我们可以知道

\[P(O \vert \Phi) = \sum_{i=1}^N \alpha_t(i) \beta_t(i)\]

进一步有

\[\begin{split} \xi_t(i, j) & = P(s_t=i, s_{t+1} = j \vert O, \Phi) \\ & = \frac{P(s_t=i, s_{t+1} = j, O \vert \Phi)}{P(O \vert \Phi)} \\ & = \frac{\alpha_t(i) a_{i,j} b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{i=1}^N \alpha_t(i) \beta_t(i)} \end{split}\]

很容易知道，系统由状态i转移到状态j的概率，可以通过对 $\xi$ 在时间维度上求和得到

\[\hat{a}_{i,j} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \sum_{k=1}^{N} \xi_t(i,k)}\]

接下来估算观察概率

\[\hat{b}_{j}(v_k) = \frac{expected \ number \ of \ times \ in \ state \ j \ and \ observing \ symbol \ v_k}{expected \ number \ of \ times \ in \ state \ j}\]

定义 $\gamma$ 为时刻t时系统处于状态j的概率

\[\gamma_t(j) = P(s_t=j \vert O, \Phi)\]

和计算 $\xi$ 一样，我们很容易就得到

\[\begin{split} \gamma_t(j) & = P(s_t=j \vert O, \Phi) \\ & = \frac{P(s_t=j, O \vert \Phi)}{P(O \vert \Phi)} \\ & = \frac{\alpha_t(j) \beta_t(j)}{P(O \vert \Phi)} \end{split}\]

则

\[\hat{b}_{j}(v_k) = \frac{\sum_{t=1, s.t.\ o_t=v_k}^{T} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)}\]

完整的Forward-Backward算法如下：

  1. Initialization
    initialize A and B
  2. Iterate until convergence
    • E-step:
    \[\gamma_t(j) = \frac{\alpha_t(j) \beta_t(j)}{\sum_{k=1}^N \alpha_T(k)}, \ \ \ \ \ 1 \leq t \leq T, 1 \leq j \leq N\] \[\xi_t(i, j) = \frac{\alpha_t(i) a_{i,j} b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{k=1}^N \alpha_T(k)}, \ \ \ 1 \leq t \leq T, 1 \leq i \leq N, 1 \leq j \leq N\]
    • M-step:
    \[\hat{a}_{i,j} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \sum_{k=1}^{N} \xi_t(i,k)}\] \[\hat{b}_{j}(v_k) = \frac{\sum_{t=1, s.t.\ o_t=v_k}^{T} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)}\]

参考

[1] http://practicalcryptography.com/miscellaneous/machine-learning/hidden-markov-model-hmm-tutorial/
[2] https://web.stanford.edu/~jurafsky/slp3/A.pdf

Written on December 17, 2018
View: