hmmem演算法
A. 大數據經典演算法解析（5）一EM演算法
姓名：崔升 學號：14020120005
【嵌牛導讀】：
EM作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法
【嵌牛鼻子】：經典大數據演算法之EM簡單介紹
【嵌牛提問】：EM是一種怎麼的演算法，其如何去觀測其中隱變數的？
【嵌牛正文】：
1. 極大似然
極大似然（Maximum Likelihood）估計為用於已知模型的參數估計的統計學方法。比如，我們想了解拋硬幣是正面（head）的概率分布θθ；那麼可以通過最大似然估計方法求得。假如我們拋硬幣1010次，其中88次正面、22次反面；極大似然估計參數θθ值：
θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2
其中，l(θ)l(θ)為觀測變數序列的似然函數（likelihood function of the observation sequence）。對l(θ)l(θ)求偏導
∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8
因為似然函數l(θ)l(θ)不是凹函數（concave），求解極大值困難。一般地，使用與之具有相同單調性的log-likelihood，如圖所示
凹函數（concave）與凸函數（convex）的定義如圖所示：
從圖中可以看出，凹函數「容易」求解極大值，凸函數「容易」求解極小值。
2. EM演算法
EM演算法（Expectation Maximization）是在含有隱變數（latent variable）的模型下計算最大似然的一種演算法。所謂隱變數，是指我們沒有辦法觀測到的變數。比如，有兩枚硬幣A、B，每一次隨機取一枚進行拋擲，我們只能觀測到硬幣的正面與反面，而不能觀測到每一次取的硬幣是否為A；則稱每一次的選擇拋擲硬幣為隱變數。
用Y表示觀測數據，Z表示隱變數；Y和Z連在一起稱為完全數據( complete-data )，觀測數據Y又稱為不完全數據(incomplete-data)。觀測數據的似然函數：
P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)
求模型參數的極大似然估計：
θ^=argmaxθlogP(Y|θ)θ^=argmaxθlogP(Y|θ)
因為含有隱變數，此問題無法求解。因此，Dempster等人提出EM演算法用於迭代求解近似解。EM演算法比較簡單，分為兩個步驟：
E步（E-step），以當前參數θ(i)θ(i)計算ZZ的期望值
Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]
M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))極大化的θθ，確定第i+1i+1次迭代的參數的估計值θ(i+1)θ(i+1)
θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=argmaxθQ(θ,θ(i))
如此迭代直至演算法收斂。關於演算法的推導及收斂性證明，可參看李航的《統計學習方法》及Andrew Ng的《CS229 Lecture notes》。 這里 有一些極大似然以及EM演算法的生動例子。
3. 實例
[2]中給出極大似然與EM演算法的實例。如圖所示，有兩枚硬幣A、B，每一個實驗隨機取一枚拋擲10次，共5個實驗，我們 可以 觀測到每一次所取的硬幣，估計參數A、B為正面的概率θ=(θA,θB)θ=(θA,θB)，根據極大似然估計求解
如果我們 不能 觀測到每一次所取的硬幣，只能用EM演算法估計模型參數，演算法流程如圖所示：
隱變數ZZ為每次實驗中選擇A或B的概率，則第一個實驗選擇A的概率為
P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45
按照上面的計算方法可依次求出隱變數ZZ，然後計算極大化的θ(i)θ(i)。經過10次迭代，最終收斂。
4. 參考資料
[1] 李航，《統計學習方法》.
[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?
[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .
[4] Rudan Chen, 【機器學習演算法系列之一】EM演算法實例分析 .
B. 數據挖掘十大經典演算法之EM
EM（Expectation-Maximum）演算法也稱期望最大化演算法，它是最常見的隱變數估計方法，在機器學習中有極為廣泛的用途，例如常被用來學習高斯混合模型（Gaussian mixture model，簡稱GMM）的參數；隱式馬爾科夫演算法（HMM）、LDA主題模型的變分推斷等等。
EM演算法是一種迭代優化策略，由於它的計算方法中每一次迭代都分兩步，其中一個為期望步（E步），另一個為極大步（M步），一輪輪迭代更新隱含數據和模型分布參數，直到收斂，即得到我們需要的模型參數。
1. EM演算法推導過程
補充知識：Jensen不等式：
如果f是凸函數，函數的期望 大於等於 期望的函數。當且僅當下式中X是常量時，該式取等號。（應用於凹函數時，不等號方向相反）
2. EM演算法流程
3. EM演算法的其他問題
上面介紹的傳統EM演算法對初始值敏感，聚類結果隨不同的初始值而波動較大。總的來說，EM演算法收斂的優劣很大程度上取決於其初始參數。
EM演算法可以保證收斂到一個穩定點，即EM演算法是一定收斂的。
EM演算法可以保證收斂到一個穩定點，但是卻不能保證收斂到全局的極大值點，因此它是局部最優的演算法，當然，如果我們的優化目標是凸的，則EM演算法可以保證收斂到全局最大值，這點和梯度下降法這樣的迭代演算法相同。
EM演算法的簡單實例： https://zhuanlan.hu.com/p/40991784
參考：
https://zhuanlan.hu.com/p/40991784
https://blog.csdn.net/u011067360/article/details/24368085
C. 02 隱馬爾可夫模型 - HMM的三個問題 - 概率計算問題
01 隱馬爾可夫模型 - 馬爾可夫鏈、HMM參數和性質
假設有三個盒子，編號為1,2,3；每個盒子都裝有黑白兩種顏色的小球，球的比例。如下：
按照下列規則的方式進行有放回的抽取小球，得到球顏色的觀測序列：
1、按照π的概率選擇一個盒子，從盒子中隨機抽取出一個球，記錄顏色後放回盒子中；
2、按照某種條件概率選擇新的盒子，重復該操作；
3、最終得到觀測序列：「白黑白白黑」
例如： 每次抽盒子按一定的概率來抽，也可以理解成隨機抽。
第1次抽了1號盒子①，第2次抽了3號盒子③，第3次抽了2號盒子②.... ； 最終如下：
①→③→②→②→③ 狀態值
白→黑→白→白→黑 觀測值
1、 狀態集合： S={盒子1，盒子2，盒子3}
2、 觀測集合： O={白，黑}
3、 狀態序列和觀測序列的長度 T=5 (我抽了5次)
4、 初始概率分布： π 表示初次抽時，抽到1盒子的概率是0.2，抽到2盒子的概率是0.5，抽到3盒子的概率是0.3。
5、 狀態轉移概率矩陣 A：a11=0.5 表示當前我抽到1盒子，下次還抽到1盒子的概率是0.5；
6、 觀測概率矩陣 - 混淆矩陣 - 為了不和之前的混淆矩陣概念沖突，可以稱之為發射矩陣，即從一個狀態發射到另一個狀態： B：如最初的圖，b11=第一個盒子抽到白球概率0.4，b12=第一個盒子抽到黑球概率0.6;
在給定參數π、A、B的時候，得到觀測序列為「白黑白白黑」的概率是多少?
這個時候，我們不知道隱含條件，即不知道狀態值：①→③→②→②→③ ；
我們如何根據π、A、B求出測序列為「白黑白白黑」的概率？
下面給出解決方案。
前向-後向演算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，計算模型λ下觀測到序列Q出現的概率P(Q|λ)；
回顧上面的案例 ，λ=(A,B,π)已知。觀測到序列 Q=白→黑→白→白→黑，但我們不知道 狀態序列 I=①→③→②→②→③；我們要求解 P(Q|λ) ，即Q=白→黑→白→白→黑 這個觀測序列發生的概率。 可以用前向-後向演算法來實現 。
Baum-Welch演算法(狀態未知) 已知觀測序列Q={q1,q2,...,qT}，估計模型λ=(A,B,π)的參數，使得在該模型下觀測序列P(Q|λ)最大。
Baum-Welch演算法是EM演算法的一個特例，專門用來 求解 隱馬爾科夫中隱狀態參數 λ=(A,B,π) 。即：根據已知的 觀測到序列 Q=白→黑→白→白→黑，去尋找整個模型的一組隱狀態參數λ=(A,B,π)，使得在模型中 觀測序列 發生的可能性P(Q|λ)最大。
Viterbi演算法 給定模型λ=(A,B,π)和觀測序列Q={q1,q2,...,qT}，求給定觀測序列條件概率P(I|Q，λ)最大的狀態序列I。
已知 觀測到序列 Q=白→黑→白→白→黑，當我們得到λ=(A,B,π)後，我們用 Viterbi演算法 求出在哪一種 狀態序列 發生的可能性最大，即，求出 狀態序列 I=①→③→②→②→③；即，抽取什麼樣的盒子順序，更可能得到白→黑→白→白→黑這種結果。
1、直接計演算法(暴力演算法)
2、前向演算法
3、後向演算法
類似KNN計算最近鄰時候的演算法。《 01 KNN演算法 - 概述 》
也就是說， 暴力演算法 需要一個個遍歷所有的狀態去計算當前狀態發生的概率。
按照概率公式，列舉所有可能的長度為T的狀態序列I={i1,i2,...,iT}，求各個狀態序列I與觀測序列Q={q1,q2,...,qT}的聯合概率P(Q,I;λ)，然後對所有可能的狀態序列求和，從而得到最終的概率P(Q;λ)；
分析： 先思考這樣一個問題：生成「白-黑-白-白-黑」這樣的結果，是不是會有很多種盒子組合的序列來抽取，都會生成這樣一個結果？我把這些可能出現「白-黑-白-白-黑」結果的盒子序列的聯合概率求出來-P(Q,I;λ)，即∑P(Q,I) = P(Q) ，P(Q) 是我們觀測到「白-黑-白-白-黑」結果時，符合這個結果的所有狀態序列I出現的概率。
公式運用：
設狀態序列 I=③→②→①→①→②； T=5；
P(I;λ) = π 3 a 32 a 21 a 11 a 12
因為： 在給定狀態序列I後，Q中的每個觀測值都獨立。（貝葉斯網路原理） 貝葉斯網路
所以： P(Q|I;λ)可以用聯乘的方式表示 (獨立可以使用聯合概率)
I = ③→②→①→①→②
Q=白→黑→白→白→黑
P(Q|I;λ) = b 3白 b 2黑 b 1白 b 1白 b 2黑
P(Q,I;λ) = P(Q|I;λ) × P(I;λ)
= b 3白 b 2黑 b 1白 b 1白 b 2黑 × π 3 a 32 a 21 a 11 a 12
若：
I 1 = ③→②→①→①→②
I 2 = ①→②→③→①→②
...
I T = ②→②→①→③→②
都能得出：
Q = 白→黑→白→白→黑
因為我所有的盒子都能取出黑球和白球，所以T的值=3 5 ;
∑P(Q,I;λ) 計算的是 I 1 ~ I T 這些狀態序列情況下，求出的P(Q,I;λ)的和。
前向 和 後向 演算法是運用某種遞歸(遞推)的方式，幫助我們盡快得求解最終結果。
解析: 如果 t 這一時刻觀察到的狀態是 q t = 雨天；其中y={干，濕，濕... 濕}共t個狀態。
先不考慮λ。
α t 是 1時刻~t時刻 所有觀測值y1，y2，...yt ，qt 出現的聯合概率。
β t 是 t+1時刻~T時刻 所有觀測值y t+1 ，y t+2 ，...y T 出現的聯合概率。
前向概率-後向概率 指的其實是在一個觀測序列中，時刻t對應的狀態為si的概率值轉換過來的信息。
分析2~3步的推導： 因為q 1 ~ q t 這些條件對 q t+1 ~ q T 的產生沒有影響 (理由：貝葉斯網路)，所以這些條件可以去掉。
定義：給定λ，定義到時刻t部分觀測序列為q1,q2,...,qt且狀態為si的概率為 前向概率 。
記做：
在給定參數π、A、B的時候，得到觀測序列為「白黑白白黑」的概率是多少?
定義：給定λ，定義到時刻t狀態為si的前提下，從t+1到T部分觀測序列為qt+1,qt+2,...,qT的概率為 後向概率 。
記做：
分析上面的公式：
如果一共只有t個時間點，t+1的時刻不存在。那麼t+1以後發生的是必然事件。
所以 β t (i) = P(q t+1 ，q t+2 ，...，q T ) = 1;
如果實在不理解也沒關系，我們姑且認為認為定義了一個初始值，即 β T (i) = 1 ；
從T-1時刻，倒推到1時刻。
首先，β t+1 (j)是什麼？是t+1時刻，在狀態sj的前提下，下圖中圈起來這部分的聯合概率。
β t (j)是什麼？是t時刻，在狀態sj的前提下，下圖中圈起來這部分的聯合概率。
求給定模型λ和觀測序列Q的情況下，在時刻t處於狀態si的概率，記做：
單個狀態概率的意義主要是用於判斷在每個時刻最可能存在的狀態，從而可以得到一個狀態序列作為最終的預測結果。
求給定模型λ和觀測序列Q的情況下，在時刻t處於狀態si並時刻t+1處於狀態sj概率，記做：
03 隱馬爾可夫模型 - HMM的三個問題 - 學習問題
D. em演算法就是baum-welch 演算法嗎
baum-welch演算法是一種對hmm模型做參數估計的方法，是EM演算法的一個特例。
前向後向演算法是已知模型和序列求概率的演算法，也是用於訓練的Baum-Welch演算法的循環中的一個步驟。
E. （十）EM演算法
EM演算法的英文全稱是 Expectation Maximization Algorithm——期望極大化演算法 ，它採用迭代的方式逼近帶隱變數的似然函數。通過對似然函數的一個下界求偏導，得到每一步參數估計的過程。
這個名稱由於缺乏作用對象，讓人一頭霧水。這里的期望是什麼？為什麼我們要極大化這個期望，我們試圖優化什麼？
這里的期望的含義其實是針對 極大似然估計 中的 似然函數 來說的，這里的期望就是似然函數的一個 下界 ，我們的目的是求這樣一個期望: 這個下界是根據 詹森不等式(Jensen's inequality） 放縮得到的，為什麼要放縮呢？因為我們試圖找出一個下界，極大化這個帶參數的下界之後，可以無限近似於似然函數。你想，如果這個做法ok的話，意味著什麼？意味著我們可以通過這個過程找出極大似然估計或最大後驗估計的參數近似解。這也意味著我們可以搞一個迭代法來得到一個近似解。但是即便我說的天花亂墜，這個下界要是不收斂那也白搭。而下界要收斂必須滿足兩個條件：
1.這個下界的取值要單調遞增（因為每回迭代的結果要比上一次的取值更大）
2.這個下界必須有上界(這個上界就是對數似然函數，且這一點可以由詹森不等式保證，這個也是EM的核心)
大白話就是 單調有界必有極限 。
我們來證明一下它確實是收斂的。
首先，在極大似然估計中，我們的目的是根據手頭上的 個樣本，最大化 後，將參數 估計出來；引入對數： ;此時引入輔助變數 ;我們的對數似然函數就變成了：
設置變分函數： ;那麼：
根據琴生不等式,對數函數為凸函數(因為 ：等號在 為常數時取到)：
上面的這個下界，就是用來逼近原對數似然函數的，這里我們已經證明了演算法收斂的一個條件， 有界性 ；但是在繼續進行下一步的時候，我們還有一個問題沒搞清楚，那就是變分函數 的具體形式,實際上，我們可以通過琴生不等式等號成立的條件導出我們要的這個變分函數q。
令 為常數：
接著我們代入變分函數 的形式，定義這個下界的第一項：
定義下界的第二項：
對於第二項，我們看看隨著迭代步數的增大，它是否是遞增的，
我們將不同參數的 與 看作是兩個分布，那麼這個結果實際上是一個KL散度，它表徵兩個分布的相似度,其結果總是大於等於0的。
大於等於0的原因：
所以：
H為一個遞增的序列，那麼剩下的就是Q是否遞增了，基於前面提到的這個下界是有上界的，上界就是我們的對數似然函數。在這個前提下，現在我們只要證明，Q遞增是整個下界遞增的充分必要條件即可。
必要性：
當整個下界遞增，即：
那麼：
所以 單調遞增，必要性得證。
充分性：
因為：
前面已經證明：
又因為：
所以：
即，在 遞增的情況下，整個下界遞增。
充分性得證。
證畢。
這個演算法名稱里提及的期望究竟是什麼？
我們說了這么多，實際都是要做一件事，那就是：
由於前面證明過整個下界有界。且只要找到讓第i次迭代的Q函數最大的 作為下一次迭代的參數，我們就可以讓Q遞增，讓演算法收斂。
我們來看看Q的形式。
這就是為什麼叫期望最大演算法的原因。
我們以概率PCA，來展開EM的應用：
當然這里的應用只涉及變分函數已知情況下的應用，並不涉及廣義EM的內容，日後看完文獻在來嘮嘮廣義EM，AVE，GAN等內容。
我們先來算一下PPCA的EM期望的形式：
在 概率PCA 中，我們有提到：
所以：
所以期望裡面是這個式子：
我們的目的是要估計出 和 ;那麼我們分別對它們求偏導:
所以：
因為：
代入偏導中
所以：
我們偏導得到的結果就是：
我們會發現我們還有兩個估計量沒解決，一個是一階估計量 ,另一個是二階估計量
在概率PCA中，我們提到過：
那麼我們就有了一階估計量：
二階估計量可以通過簡單的計算得到：
剩下的代入即可.
結果展示：