作者：CHEONG
公衆号：AI機器學習與知識圖譜
研究方向：自然語言處理與知識圖譜
閱讀本文之前，首先注意以下兩點：
1、機器學習系列文章常含有大量公式推導證明，為了更好了解，文章在最開始會給出本文的重要結論，友善最快速度了解本文核心。需要進一步了解推導細節可繼續往後看。
2、文中含有大量公式，若讀者需要擷取含公式原稿Word文檔，可關注公衆号後回複：HMM第二講，本文主要講解使用前向算法和後向算法求解隐馬爾科夫模型的Evaluation問題。
一、核心結論
1.HMM Evaluation問題定義：已知參數 λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B)，求輸出觀測序列 O O O的機率 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∣λ)
三、往期精彩
【知識圖譜系列】Over-Smoothing 2020綜述
【知識圖譜系列】基于生成式的知識圖譜預訓練模型
【知識圖譜系列】基于2D卷積的知識圖譜嵌入
【知識圖譜系列】基于實數或複數空間的知識圖譜嵌入
【知識圖譜系列】自适應深度和廣度圖神經網絡模型
【知識圖譜系列】知識圖譜多跳推理之強化學習
【知識圖譜系列】知識圖譜的神經符号邏輯推理
【知識圖譜系列】動态時序知識圖譜EvolveGCN
【知識圖譜系列】多關系神經網絡CompGCN
【知識圖譜系列】探索DeepGNN中Over-Smoothing問題
【知識圖譜系列】知識圖譜表示學習綜述 | 近30篇優秀論文串講
【知識圖譜系列】動态知識圖譜表示學習綜述 | 十篇優秀論文導讀
【面經系列】八位碩博大佬的位元組之旅
【機器學習系列】機器學習中的兩大學派
各大AI研究院共35場NLP算法崗面經奉上
幹貨 | Attention注意力機制超全綜述
幹貨 | NLP中的十個預訓練模型
幹貨|一文弄懂機器學習中偏差和方差
FastText原理和文本分類實戰，看這一篇就夠了
Transformer模型細節了解及Tensorflow實作
GPT,GPT2,Bert,Transformer-XL,XLNet論文閱讀速遞
機器學習算法篇：最大似然估計證明最小二乘法合理性
Word2vec, Fasttext, Glove, Elmo, Bert, Flair訓練詞向量教程+資料+源碼
原稿擷取請關注公衆号後回複：HMM第二講 ，原創不易，有用就點個贊呀！