千呼万唤始出来，犹抱琵琶半遮面,揭开HMM的神秘面纱

什么是时序模型

比如说图像,一个人的特征等都是非时序类型的

股票价格,说话的语音,文本,温度等都是时序类型

传统模型使用HMM/CRF即可解决问题

但是由于硬件的心呢个提升,现在主流RNN/LSTM等深度学习模型

什么是HMM

千呼万唤始出来，犹抱琵琶半遮面,揭开HMM的神秘面纱

他是Directed+Generate model并存的

HMM 的参数( $Z_I$ 是离散性)

以单词词性预测为例来说明问题
$\theta=(A,B,\pi)$

对于 $A_{i,j}$ ,代表某一行 $i$ 前一个单词为 $j$ 的状态转移概率,大小 $M*M$ 的大小, $M$ 为所有单词个数

对于 $B_{i,j}$ ,代表某一行 $i$ 的状态会生成 $j$ 的单词的概率,大小 $M*M$ 的大小, $M$ 为所有单词个数

对于 $\pi=[\pi_1,\pi_2,...\pi_m]$ ,代表某一个状态 $Z_1,Z_2$ 在第一个位置的概率,其中 $\pi_1+\pi_2+...+\pi_m=1$

那么给定 $x-->\theta$ 就是预估集问题

$\theta,x--->Z$ 变成了推理问题

HMM 中的 Inference 问题

给定 $\theta =(A,B.\pi)$ 求 $x$

我们可以罗列出所有的情况????,不要嫌多

if $Z_i\in \{a,b,c\}$ 那么存在下列的情况

$aaa.....a \\ aab.....b \\ baa.....a$

那么 $P(Z_1)P(Z_2|Z_1)P(Z_3|Z_2)...P(Z_m|P_{m-1})·P(x_1|Z_1)P(x_2|Z_2)...P(x_n|Z_n)$ ,每一项都可以计算出来,只需要查询B即可,但是时间复杂度太高了 $3^{n}$ ,哈哈哈,确实还是有那么一点点小问题纳,奇迹估计是跑不出来了

但是并不是说没有解决方案了,可以试探性的使用Viterbi试试

千呼万唤始出来，犹抱琵琶半遮面,揭开HMM的神秘面纱

比如上面我画的某条路径,可以使用 $P(Z_1=2)P(x_1|Z_1=2)P(Z_2=1|Z_1=2)P(x_2|Z_2=1)...P(Z_K=2)P(X_K|Z_K=2)$ 代表所有路径

$\delta_k(i)$ :the score of the best path ending at state i at time k

那么 $\delta_{k+1}(j)=max \left\{\begin{array}{l}\delta_k(1)+\log P(Z_{k+1}=j|Z_k=1)+\log P(x_{t+1}|Z_{t+1}=j)\\\delta_k(2)+\log P(Z_{k+1}=j|Z_k=2)+\log P(x_{t+1}|Z_{t+1}=j) \\ ...... \\ \delta_k(m)+\log P(Z_{k+1}=j|Z_k=m)+\log P(x_{t+1}|Z_{t+1}=j)\end{array}\right.$

简化之后

$\delta_{k+1}(j)=max_i[\delta_k(i)+\log P(Z_{k+1}=j|Z_k=i)+\log P(x_{k+1}|Z_{k+1}=j)]$

HMM 中的 FB 算法

F/B Algorithm :compute $P(Z_k|x)$

Forward:computer $P(Z_k,x_{1:k})$

Backward:computer $P(x_{k+1:n|Z_k})$

贝叶斯定理可以得出
$P(Z_k|x)=\frac{P(Z_k,x)}{P(x)}\propto P(Z_k,x)$

$P(Z_k,x)=P(x_{k+1:n}|Z_k,x_{1:k})·P(Z_k,x_{1:k})$

反思 $P(x_{k+1:n}|Z_k,x_{1:k})$ 中, $x_{1:k}$ 独立于 $Z_k$
$P(Z_k,x)=\underbrace {P(x_{k+1:n}|Z_k)}_{backward}·\underbrace {P(Z_k,x_{1:k})}_{forward}$
例如 $P(Z_{k=1|x})=\frac{P(Z_k=1,x)}{\sum_jP(Z_k=j,x)}$

$x_{1:k}=(x_1,x_2,...x_k)$

通过F/B算法可以计算模型参数
Change Detection

场景:组团欺诈,在那些时间段,网络突变

A:计算 $graph_t,graph_{t+1}$ 之间的相似度

B:HMM中每个状态下生成的图,判断 $P(Z_k\neq Z_{k \neq1}|x) . threhold$

对于目标函数 $P(Z_k,x_{1:k})$

千呼万唤始出来，犹抱琵琶半遮面,揭开HMM的神秘面纱

构造 $P(Z_k,x_{1:k})=[\ ]·P(Z_{k-1},x_{1:k-1})$ m,并且把 $Z_{k-1}$ 边缘化
$\begin{aligned} P(Z_k,x_{1:k})&=\sum_{Z_{k-1}}P(Z_{k-1},Z_k,x_{1:k-1}) \\ &=\sum_{Z_{k-1}}P(Z_{k-1},x_{1:k-1})·P(Z_k|Z_{k-1},x_{1:k-1}) ·P(x_k|Z_k,Z_{k-1},x_{1=k-1}) \\ &=\sum_{Z_{k-1}}\underbrace {P(Z_{k-1},x_{1:k-1})·P(Z_k|Z_{k-1})}_A ·\underbrace {P(x_k|Z_k) }_B \end{aligned}$
重新整理 $\alpha_k(Z_k)=\sum_{Z_{k-1}}\alpha_{k-1}(Z_{k-1})·P(Z_k|Z_{k-1})·P(x_k|Z_k)$

那么D-seperration可以这样表示

$\alpha_1(Z_1)=P(Z_1,x)=\underbrace {P(Z_1)}_\pi· \underbrace {P(x_1|Z_1)}_B$

对于目标函数 $P(x_{k+1:n|Z_k})$

千呼万唤始出来，犹抱琵琶半遮面,揭开HMM的神秘面纱

构造 $P(x_{k+1:n}|Z_k)=[\ ]·P(x_{k+2:n}|Z_{k+1})$ ,并且边缘化 $Z_{k+1}$ ,注意乘 $P(Z_k)$
$\begin{aligned} P(x_{k+1:n}|Z_k) & = \sum_{Z_{k+1}}P(x_{k+1:n}.Z_{k+1}|Z_k) \\ &= \sum_{Z_{k+1}}·P(x_{k+2:n}|Z_{k+1},Z_k,x_{k+1})·P(x_{k+1}|Z_{k+1},Z_k)·P(Z_{k+1}|Z_k) \\ &=\sum_{Z_{k+1}}·\underbrace {P(x_{k+2:n}|Z_{k+1})}_B·\underbrace {P(x_{k+1}|Z_{k+1})·P(Z_{k+1}|Z_k)}_A \end{aligned}$
重新整理 $\beta_k(Z_k)=\sum_{Z_{k+1}}\beta_{k+1}(Z_{k+1})·P(Z_k|Z_{k-1})·P(x_{k+1}|Z_{k+1})$ ,时间复杂度 $O(n·m^2)$