HMM

设隐藏状态序列，及其状态值的集合， $Z$ 为离散型随机变量，有 $m$ 种取值
$Z=z_1,z_2...z_T, Q=\{q_1, q_2,...q_m\}$
设观测序列，及其观测值的集合
$X = x_1, x_2,...x_T,V=\{v_1, v_2,...v_T\}$

模型表示：
$\theta = (A,B, \pi)$

其中 $A$ 为状态转移矩阵，其维度为 $(m\times m)$

$A = [a_{ij}],a_{ij} = P(z_{t+1}=q_j|z_t=q_i)$
$a_{ij}$ 表示 $t$ 时刻，当前隐藏状态 $z_t$ 转换为下一个隐藏状态 $z_{t+1}$ 的概率

$B$ 为生成矩阵

$B = [b_j(k)],b_j(k) = P(x_t=v_k|z_t=q_j)$
$b_j(k)$ 表示 $t$ 时刻，当前观测值 $x_t$ 由当前隐藏值 $z_t$ 转换而来的概率

$\pi$ 表示 $Z$ 的初始概率分布，即 $z_t$ 取到 $\pi _{m}$ 的概率，其维度为 $(1 \times m)$

$\pi = [\pi _1, \pi _2, \pi _3, ..., \pi _m]$

其中 $\pi _1+ \pi _2+ \pi _3+ ...+ \pi _m = 1$

两个假设

齐次马尔科夫假设

$P(z_{t+1}|z_1, z_2,..z_t,x_1,x_2,...x_t) = P(z_{t+1}|z_t)$

$t+1$ 时刻的隐藏状态的生成只和 $t$ 时刻的隐藏状态有关

观测独立性假设

$P(x_t|z_1, z_2,..z_t,x_1,x_2,...x_t) = P(x_t|z_t)$

$t$ 时刻的观测状态的生成，只和 $t$ 时刻的隐藏状态有关

三个问题

Evaluation：Given $\lambda$ ，求 $P(O|\lambda)$ ，使用 $Forward-Backward$ 算法

Learning：$ \lambda_{MLE} = argmax P(O|\lambda)$，EM 算法

Decoding： $\hat{I} = argmax P(I|O,\lambda)$

问题 ①：已知 ( $\pi$ , A, B)，求 $Z$ ，viterbi 算法

已知观测状态和 $\theta$ ，求使得目标概率 $ P(Z|X,\theta )$ 最大的隐藏状态序列 $Z$

目标概率表示为
$P(Z|X,\theta ) = P(z_1=q_1) \cdot P(z_2=q_2|z_1=q_1) \cdot P(x_1=v_1|z_1=q_1)\times ...\\ \times P(z_t=q_t) \cdot P(z_{t+1}=q_{t+1}|z_t=q_t) \cdot P(x_t=v_t|z_t=q_t)$
需要求隐藏状态序列 $ Z$ ，使用枚举的方法，有 $t$ 个隐藏状态，每个隐藏状态有 $m$ 中取值，算法的时间复杂度为 $O(m^t)$ 是无法求解的

动态规划

我们可以把 Z 及其所有取值列出来，Z 取值的最优组合可以看成是从 $z_1$ 到 $z_k$ 走过的分数最高的路径，并且 $z_k$ 取到 $q_i$

HMM

那么 $\delta _{k+1} (j)$ 可以表示成，

$\delta _{k+1} (j) = max\Big\{\delta_k(1) + logP(z_{k+1}=q_j|z_k=q_1)+logP(x_{k+1}|z_{k+1}=q_j) ...\Big\}$

$\delta _{k+1} (j) =max \begin{cases} \delta_k(1) + logP(z_{k+1}=q_j|z_k=q_1)+logP(x_{k+1}|z_{k+1}=q_j) \\ \delta_k(2) + logP(z_{k+1}=q_j|z_k=q_2)+logP(x_{k+1}|z_{k+1}=q_j) \\ ... \\ \delta_k(m) + logP(z_{k+1}=q_j|z_k=q_m)+logP(x_{k+1}|z_{k+1}=q_j) \end{cases}$

最后可得
$\delta _{k+1} (j) = \underset{i}max \Big[ \delta _{k+1} (i)+logP(z_{k+1}=q_j|z_k=q_i)+logP(x_{k+1}|z_{k+1}=q_j)\Big ]$

待續。。。

HMM

HMM

相关推荐