math, propability
Home

隐式马尔科夫链

Graph Model #

X_1 --> X_2 --> X_3 --> ... --> X_n
 |       |       |               |
Y_1     Y_2     Y_3             Y_n

根据马尔科夫链模型：

\[\begin{align} &P(X_{t+1}\mid X_1,...,X_t,Y_1,...,Y_t)=P(X_{t+1}\mid X_t)\\ &P(Y_t\mid X_1,...,X_t,Y_1,...,Y_t)=P(Y_t\mid X_t)\\ \end{align}\]

第一条对应状态转移概率矩阵：

\[\boldsymbol{A}=\{a_{ij}\}_{N_S\times N_S},a_{ij}=P(X_{t+1}=s_j\mid X_t=s_i)\]

第二条对应发射概率矩阵：

\[\boldsymbol{B}=\{b_{ij}\}_{N_S\times N_V},b_{ij}=P(Y_t=v_j\mid X_t=s_i)\]

我们用一个三元组 $\lambda=(\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi})$ 就可以刻画一个hidden markov model。其中 $\pi$ 为初始概率矩阵：

\[\boldsymbol{\pi_i}=P(X_1=s_i)\]

Problem #

概率问题 #

已知参数 $\lambda=(\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi})$ 的情况下，求一组观测 $Y_1,…,Y_n$ 的概率 $P(Y_1,…,Y_T)$。

Forward Algorithm #

求 $P(Y_{1:T})$ 即求 $\sum_{X_{T}} P(Y_{1:T},X_{T})$

我们令 $\alpha_t(s_i)=P(Y_{1:t},X_t=s_i)$，则 $P(Y_{1:t})=\sum_{i} \alpha_n(s_i)$，分析得

\[\begin{align}P(Y_{1:t},X_{t})&=\sum_{X_{t-1}}P(Y_{1:t},X_t,X_{t-1})\\ &=\sum_{X_{t-1}}P(Y_{1:t-1},X_{t-1})P(Y_{t},X_t\mid Y_{1:t-1},X_{t-1})\\ &=\sum_{X_{t-1}}P(Y_{1:t-1},X_{t-1})P(Y_t\mid X_t)P(X_t\mid Y_{1:t-1},X_{t-1})\\ &=\sum_{X_{t-1}}P(Y_{1:t-1},X_{t-1})P(Y_t\mid X_t)P(X_t\mid Y_{1:t-1}X_{t-1})\\ &=\sum_{X_{t-1}}P(Y_{1:t-1},X_{t-1})P(Y_t\mid X_t)P(X_t\mid X_{t-1})\\ &=P(Y_t\mid X_t)\sum_{X_{t-1}}P(Y_{1:t-1},X_{t-1})P(X_t\mid X_{t-1})\\ \end{align}\]

可以看到有一个递推关系为

\[\begin{align} &\alpha_1(s_i)=\pi(s_i)B(s_i,Y_1)\\ &\alpha_{t+1}(s_i)=B(s_i,Y_{t+1})\sum_{j}\alpha_t(s_j)A(s_j,s_i)\\ &P(Y_{1:T})=\sum_{s_i}\alpha_T(s_i) \end{align}\]

Backword Algorithm #

求 $P(Y_{1:T})$ 即求 $\sum_{X_{1}} P(Y_{1:T},X_{1})$

我们令 $\beta_t(s_i)=P(Y_{t+1:T}\mid X_t=s_i)$，则 $\beta_T(s_i)=1$，则

\[\begin{align} P(Y_{1:T})&=\sum_{X_1}P(Y_{1:T},X_1)\\ &=\sum_{X_1}P(X_1)P(Y_{1:T}\mid X_1)\\ &=\sum_{X_1}P(X_1)P(Y_{2:T}\mid X_1)P(Y_1\mid X_1) \end{align}\]

可得 $P(Y_{1:T})=\sum_{i}\pi(s_i)B(s_i,Y_1)\beta_1(s_i)$

继续分析寻找递推关系

\[\begin{align} P(Y_{t+1:T}\mid X_{t})&=\sum_{X_{t+1}}P(Y_{t+1:T},X_{t+1}\mid X_{t})\\ &=\sum_{X_{t+1}}P(X_{t+1}\mid X_{t})P(Y_{t+1:T}\mid X_{t+1},X_t)\\ &=\sum_{X_{t+1}}P(X_{t+1}\mid X_{t})P(Y_{t+1}\mid X_{t},X_{t+1})P(Y_{t+2:T}\mid X_{t},X_{t+1})\\ &=\sum_{X_{t+1}}P(X_{t+1}\mid X_{t})P(Y_{t+1}\mid X_{t+1})P(Y_{t+2:T}\mid X_{t+1})\\ \end{align}\]

可以看到有一个递推关系为

\[\begin{align} &\beta_T(s_i)=1\\ &\beta_{t}(s_i)=\sum_{s_j}B(s_i,Y_{t+1})\beta_{t+1}(s_j)A(s_i,s_j)\\ &P(Y_{1:T})=\sum_{s_i}\pi(s_i)B(s_i,Y_1)\beta_1(s_i) \end{align}\]

推测问题 #

已知参数 $\lambda=(\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi})$ 的情况下，求使得 $P(X_{1:T}\mid Y_{1:T})$ 最大的状态序列 $X^*_{1:T}$。

使用的是vertbi算法（动态规划最短路）。

注意到 $P(\boldsymbol{X}\mid\boldsymbol{Y})=P(\boldsymbol{X},\boldsymbol{Y})/P(\boldsymbol{Y})$，而且我们已经在上一步中学会求解 $P(\boldsymbol{Y})$，所以只需要最大化 $P(\boldsymbol{X,Y})$。

令 $\delta_t(s_i)=max_{Y_{1:t-1}}P(X_{1:t-1},X_t=s_i,Y_{1:t})$，则

\[\begin{align} \delta_{t+1}(s_i)&=\mathop{max}\limits_{Y_{1:t}}P(X_{1:t},X_{t+1}=s_i,Y_{1:t+1})\\ &=\mathop{max}\limits_{s_j}\mathop{max}\limits_{Y_{1:t-1}}P(X_{1:t-1},X_t=s_j,X_{t+1}=s_i,Y_{1:t+1})\\ &=\mathop{max}\limits_{s_j}\mathop{max}\limits_{Y_{1:t-1}}P(X_{1:t-1},X_t=s_j,Y_{1:t})P(X_{t+1}=s_i\mid X_t=s_j)P(Y_{t+1}\mid X_{t+1}=s_i)\\ &=\mathop{max}\limits_{s_j}(\delta_t(s_j)A(s_j,s_i))B(s_i,Y_{t+1}) \end{align}\]

且

\[\begin{align} &\delta_1(s_i)=P(X_1=s_i,Y_1)=\pi(s_i)B(s_i,Y_1)\\ &\mathop{max}\limits_{\boldsymbol{Y}}P(\boldsymbol{X},\boldsymbol{Y})=\mathop{max}\limits_{s_i}\delta_T(s_i) \end{align}\]

我们只需要把递推过程中的最优路径都记录下来就可以了。

训练问题 #

这里不做讨论。

Reference #

  1. 隐马尔科夫模型教程(Hidden Markov Model Tutorial)
  2. 一站式解决：隐马尔可夫模型（HMM）全过程推导及实现
  3. Viterbi最短路算法-动态规划