作者：CHEONG
公众号：AI机器学习与知识图谱
研究方向：自然语言处理与知识图谱
阅读本文之前，首先注意以下两点：
1、机器学习系列文章常含有大量公式推导证明，为了更好理解，文章在最开始会给出本文的重要结论，方便最快速度理解本文核心。需要进一步了解推导细节可继续往后看。
2、文中含有大量公式，若读者需要获取含公式原稿Word文档，可关注公众号后回复：HMM第二讲，本文主要讲解使用前向算法和后向算法求解隐马尔科夫模型的Evaluation问题。
一、核心结论
1.HMM Evaluation问题定义：已知参数λ = ( π , A , B ) \lambda=(\pi,A,B)λ=(π,A,B)，求输出观测序列O OO的概率p ( O ∣ λ ) p(O|\lambda)p(O∣λ)
2.常规复杂计算p ( O ∣ λ ) p(O|\lambda)p(O∣λ)：
复杂计算的时间复杂度为O ( N T ) O(N^T)O(NT)
3.前向算法，假设：
求α t ( i ) \alpha_t(i)αt(i)递推式得α T ( i ) \alpha_T(i)αT(i)，最终得出：
4.后向算法，假设：
求β t ( i ) \beta_t(i)βt(i)递归式得β 1 ( i ) \beta_1(i)β1(i)，最终得出：
前向、后向算法的时间复杂度为O ( T N 2 ) O(TN^2)O(TN2)
二、复杂计算
一般情况下，求解p ( O ∣ λ ) p(O|\lambda)p(O∣λ)的时间复杂度为O ( N T ) O(N^T)O(NT)，指数级的复杂度，运算如下：
其中：
其中：
因此：
同理可得：
所以：
由此可见，常规计算的时间复杂度是O ( N T ) O(N^T)O(NT)
三、前向算法
下面介绍通过前向算法来求解p ( O ∣ λ ) p(O|\lambda)p(O∣λ)，如下图所说：
根据上图，先给出一个假设变量
因此：
所以：
接下来目的便是找出α t ( i ) \alpha_t(i)αt(i)的递推式，从而可以方便的求出α T ( i ) \alpha_T(i)αT(i)，最终求得p ( O ∣ λ ) p(O|\lambda)p(O∣λ)
根据观测独立假设，存在：
因此：
根据齐次马尔科夫假设，存在：
并且
所以可以得到递推式：
从而便得到了前向算法的递归公式，通过递归公式便可以计算出p ( O ∣ λ ) p(O|\lambda)p(O∣λ)
四、后向算法
下面介绍通过后向算法来求解p ( O ∣ λ ) p(O|\lambda)p(O∣λ)，如下图所说：
根据上图，先做出一个假设：
因此：
所以可以通过上述假设变量求出p ( O ∣ λ ) p(O|\lambda)p(O∣λ)，推导过程如下：
其中：
因此：
其中：
因此：
因此只需要通过后向算法求出β 1 ( i ) \beta_1(i)β1(i)，便可以求解p ( O ∣ λ ) p(O|\lambda)p(O∣λ)，接下来推导β t ( i ) \beta_t(i)βt(i)的递推公式
结合上图，其中：
因此：
根据观测独立假设，其中：
因此：
从而得到了β t ( i ) \beta_t(i)βt(i)的递归式，可以求出p ( O ∣ λ ) p(O|\lambda)p(O∣λ)
三、往期精彩
【知识图谱系列】探索DeepGNN中Over-Smoothing问题
【知识图谱系列】知识图谱表示学习综述 | 近30篇优秀论文串讲
【知识图谱系列】动态知识图谱表示学习综述 | 十篇优秀论文导读
Transformer模型细节理解及Tensorflow实现
GPT,GPT2,Bert,Transformer-XL,XLNet论文阅读速递
Word2vec, Fasttext, Glove, Elmo, Bert, Flair训练词向量教程+数据+源码
原稿获取请关注公众号后回复：HMM第二讲 ，原创不易，有用就点个赞呀！