硬EM演算法
Ⅰ EM Algorithm
EM演算法和之前學的都不太一樣，EM演算法更多的是一種思想，所以後面用幾個例子講解，同時也會重點講解GMM高斯混合模型。
極大似然估計這裡面用的比較多。假設我們想要知道我們學生身高的分布，首先先假設這些學生都是符合高斯分布 我們要做的就是要估計這兩個參數到底是多少。學生這么多，挨個挨個來肯定是不切實際的，所以自然就是抽樣了。
為了統計學生身高，我們抽樣200個人組成樣本
我們需要估計的參數 首先估計一下抽到這兩百人的概率一共是多少，抽到男生A的概率 抽到學生B的概率 所以同時抽到這兩個學生的概率就是 那麼同時抽到這200個學生的G概率
最後再取一個對數就好了：
似然函數的執行步驟：
1.得到似然函數
2.取對數整理
3.求導數，另導數為零
4.解方程得到解
首先引出凸函數的概念 那麼就是凸函數，所以它的圖像就是一個勾形的，看起來是一個凹函數，實際上是凸函數。
正常來看先是要引入一個最大似然函數： 但這樣其實是和難求的，P(x|θ)完全混在了一起，根本求不出來，所以我們要引入一個輔助變數z。
所以我們引入隱變數的原因是為了轉化成和這幾個高斯模型相關的式子，否則無從下手。化簡一下上式子： 既然z可以指定x，那麼我們只需要求解出z就好了。
注意上面凸函數所提到的一個期望性質，這里就可以使用了。因為雖然優化了上面的式子，還是不能求出來，因為z變數實在是太抽象了，找不到一個合適的公式來表示它。EM的一個方法就是用優化下界函數的方法來達到優化目標函數的目的。
既然z很抽象，那麼我們就需要一個轉變一下。對於每一個樣例x都會對應一個z，那麼假設一個分布Q(z)是滿足了z的分布的，而Q(z)滿足的條件是 Qi意味著每一個x對應的z都會對應著一個Q了，這里有點復雜，再詳細解釋一下。一個x對應一組z，z是一個向量，但是每一個z又會分別對應一個一個分布Q。以為最後得到的z不會是一個數字，而是一個概率，也就是說Q(z)得到的是這個x樣例屬於這個類別的概率是多少。而z的數量，一個是當前有多少個分布混合在一起的數量。
再梳理一下：現在的樣本是xi，那麼每一個xi將會對應著一組的z，每一個xi同時也會對應著一個分布Qi，z其實就是反應了這個樣本是來自於哪個分布的。比如這個x是A1分布做了3，A2分布做了5，那麼z可能就是={3,5}。所以Qi(z)得到的是這個x屬於這些個分布的概率，也就是說這些分布對x做了多少百分比的功，自然就是要等於1了。
還要注意的是，上面的 這個並不能得到Qi(z)就是分布對x做了多少功的結論，得到這個結論是後面下界函數與目標函數相等得到的。這里只是知道了總和等於1，因為是分布的總和嘛。
現在就到了公式的化簡：
仔細看一下這個式子 這個式子其實就是求 的期望，假設 ，那麼可以利用上面 。於是化簡：
這個時候就得到了下界函數，上面也講過了，想要相等，自然就是x要是常數，所以 既然 ，而且z也是一樣的，因為一個樣本嘛。所以上下加和（如果是離散的，那就sum一下，連續的那就積分，這里是離散的，所以就是sum一下）。於是有
於是有：
這就是整一個EM演算法的框架了，可以看到其實沒有比較具體的演算法，大致上就是一個框架。那麼問題來了，怎麼樣證明這東西是一個收斂的？？
可以直接把高斯混合模型代入EM框架裡面。
存在多個高斯分布混合生成了一堆數據X，取各個高斯分布的概率是 ，第i個高斯分布的均值是 ，方差是 ，求法φ，μ，σ。
按照套路，第一個E-step求出Q，於是有：
意思就是求出第i個樣本屬於第j個分布的概率是多少。之後就是M-step了，就是化簡了：
這里可能需要解釋一下，根據 至於條件，因為很明顯，z是隱變數，只是指明了x是屬於哪個類別，和μ，Σ沒有什麼關系，所以直接忽略那兩個參數了，所以P(z)是沒有那兩個參數的，z是代表了分布，所以每一個分布的概率肯定是包括了，所以就只有一個概率的參數。P(x|z)是本身的概率，就是已經知道分布是那個了，求屬於這個分布的概率是多少，既然已經選定了分布那麼自然就不需要再看φ了，因為φ是各個分布的概率。
現在有兩個硬幣AB，進行5次試驗每一次投10次，並不知道是哪個硬幣投的，求兩種硬幣的正面的概率。
首先E-step：
首先先初始化一下，
第一個試驗選中A的概率：
同樣求得
計算機出每一個試驗的概率然後相加求均值。
之後就是M-step了：
方差的求解就不玩了，主要就是迭代求解μ和φ的值了。
首先是生成數據，4個高斯分布，每一個高斯分布的sigma都是一樣的，不一樣的只有μ和α，也就是φ，習慣上把前面的一個參數叫做權值，所以用α來表示。
這四個模型的比例分別是1:2:3:4，使用EM來找到他們屬於的類別。
其實如果用kmeans聚類的話更加快速，但是這里還是用EM。
E-step：
就是按照公式來求解w即可，求解每一個分布對樣本點做了多少的功，之後求單個樣本點求比例。
M-step：
直接按照公式優化即可。
運行函數。看看結果：
結果其實還是相差不大。達到預期。
上面所講的其實只是一種理解方法，在李航老師的統計學習方法裡面是另一種比較厲害的解法：
1.E-step：求出Q函數。
2.M-step：利用Q函數求極大值。
其實這兩種方法是完全一樣的，Q函數就是下界函數，
EM和Kmeans演算法其實很類似，事實上步驟基本可以用EM框架來替換，但是Kmeans演算法是硬分類，說一不二，但是EM演算法不太一樣，是軟分類，百分之幾是那個，百分之幾是這個。
缺點也還是有的：初值敏感，局部最優。因為存在了隱變數，所以導致了直接對x做極大似然是不可行的，log已經在sum的外面了。所以EM演算法就轉向了下界函數，而這種方法本來就不保證找到局部最優解。
如果將樣本看作觀察值，潛在類別看作是隱藏變數，那麼聚類問題也就是參數估計問題。如果一個目標函數存在多個變數，那麼梯度下降牛頓法這些逼近方法就用不了了。但我們可以使用坐標上升方法，固定一個變數，對另外一個求導數，然後替換最後逐步逼近極值點。對應到EM演算法也是一樣，E步求隱含的z變數，Mstep求解其他參數。
Ⅱ NLP自然語言處理
羅素悖論：由所有不包含自身的集合構成的集合
例子：理發師稱只給那些不給自己理發的人理發。
基於集合論，理發師無論給自己理發還是不給自己理發都是矛盾的。
因此集合論不是完備的。 即使後面馮羅伊德等科學家提出了各種假定條件。
由於上述的原因，集合率無法很好的描述自然語言，科學家發現通過概率模型可以更好的描述自然語言。
深度學習來處理自然語言屬於概率模型
證明最小點位於坐標軸上
h = f+c|x|
由於在x = 0處不可導
h-left'(0)*h-right'(0) = (f'+c)*(f'-c)
那麼如果c>|f'(0)|可得，h在0處左右導數異號
0是最值。
那麼在損失函數加入L1正則化後，可以得到某些維度容易為0，從而得到稀疏解
幾乎所有的最優化手段，都將適用凸優化演算法來解決
P(A|B) = P(A and B) / P(B)
if A and B 獨立
=》P(A and B| C) = P(A|C)*P(B|C)
也可以推出
=>A(A|B and C) = P(A|C) (B交C不為空)
拋9次硬幣，硬幣出現正面的概率是0.5，出現k次的概率分布如下如
服從正態分布
x的平均值
E = x*p(x) + ...
x相對於期望的偏離
var = (x-E(x))^2
conv = (x - E(x))*(m - E(m))
描述x,m是否有同分布
按理協方差為0，並不代表x和m沒有關系
例如下圖
如果點的分布對稱的分布，會得到協方差為0，但是其實他們是有關系的。
把每個相關的概率累加，得到聯合概率
P(x1=m1,x2=m2...) = n!*P1 m1/m1!*P2 m2/m2!
T(n) = (n-1)!
T(x)用一條曲線逼近n!，進而可以求得非整數的階乘
由二項式分布推出
P = T(a+b)*x (a-1)*(1-x) (b-1)/(T(a)*T(b))
則正態分布
y為0時，不考慮y『。y為1時，y'越接近1，越小，越靠近0，越大
把D最小化，迫使y'逼近y
對於一個句子，有若干單片語成。例如
C1: The dog laughs.
C2: He laughs.
那麼計算P(C1) = P(The, Dog, laughs)的概率和P(C2) = P(He, laughs)的概率。
根據歷史文本的統計學習。
可以得到P(C1)<<P(C2)
P('I love the game') = P('I')*P('love')*P('the')*P('game')
其中P(<work>) = 頻率/總單詞數
計算一篇文章是積極的還是消極的。
P(y|x) = sigmod(wx)
x是文章內每個單詞的頻率
y表示積極和消極情感
其中P(xk|x1, x2,..xk-1) = frequence(x1, x2 ,, xk)/frequence(x1, x2..xk-1)
2-gram模型例子
把多個gram的模型進行線性整合
P(y|x1, x2, .. xn) = P(y)*P(x1, x2, ... xn|y) / P(x1, x2, ... xn)
y代表是否是垃圾郵件
x代表單詞
廣州市長壽路 -》 廣州市長|壽路
廣州市長壽路 -》 廣州市|長壽路
匹配詞袋：廣州市，廣州市長，長壽路
使用最大匹配發，第二個分詞更優
通過統計P(A|B)，得出各個option的概率，取最大的概率，則為最後的分詞
word => [0, 0 , ... 1, ... 0]
word => [0, 1, 0, 1, 0, ...]
可以解決詞相似性問題
計算附近詞的頻率
word => [0, 3, 0, 1, 0, ...]
w是附近詞的one-hot encoding
score是詞的one-hot encoding
最後一層通過softmax，取擬合文本
最終中間層則為詞向量
輸入為詞one-hot encoding
輸出為附近此的one-hot encoding
最後通過softmax預測附近詞
最後中間層則為結果詞向量
混合模型是一種統計模型，問題中包含若干個子問題，每個子問題是一個概率分布，那麼總問題就是若干個子問題的組合，也就是若干個子分部的組合，這樣就形成了混合模型。
有紅黑兩種硬幣，把它們放在盒子里，從盒子里隨機抽取一個硬幣並投幣，抽到紅色的概率是p，紅色硬幣正面的概率是q，黑色硬幣正面的概率是m，假設我們沒辦法看到抽取出的硬幣的顏色，只能看到最終是正面或者反面的結果，例如HTTHTTTTHHH (H:正面 T: 反面)。需要估計p,q,m三個參數。
此時可以計算出
通過EM演算法迭代如下：
隨機p q m
迭代以下過程：
計算上面table
p = (aC(正)+cC(反))/total
q = aC(正)/(aC正+cC正)
m = bC(正)/(bC正 + dC正)
假設有上述數據，需要用混合模型來逼近，通過分析，紅色和藍色數據分別為高斯正態分布，N(u, v)
此時可以得到如下表
p = pN紅x/(pN紅x+(1-p)N藍x)
u = pN紅x/n
v = pN紅(x-u)^2/n
詞性轉換概率
詞性到單詞的轉換概率
通過EM遞歸演算法，訓練以上參數，得到隱馬爾可夫模型
PLSA主題模型
只統計詞的頻率，不計算詞的相對位置
計算文檔和單詞頻率的矩陣
進行奇異矩陣分解
得到A矩陣的壓縮U，U中的k則為k個主題
通過分析，LSA得到的主題是跟現實無法關聯，它只是一個量，而沒有明顯的意義。
PLSA為了解決此問題，引入概率模型，先確定主題個數
然後通過構建Doc->topic的概率table，和topic->word的概率table。
然後通過EM模型，得到這兩個table的所有概率值。
進而得到文檔的主題表示
PLSA的缺陷是，對於預測未知的doc，無法計算此文檔的相關概率。隨著doc數量的增加，PLSA模型的參數會線性增加，從而會造成過擬合。
LDA通過引入先驗概率來克服PLSA的問題。
類似於編譯原理的上下文無法句法分析，一顆語法樹
通過對CFG引入概率參數
有了概率，可以計算每顆語法樹的極大似然概率，並取最大概率的樹為最終輸出
上一個狀態中間層的輸出作為下一隱層的輸入
類似於HMM的2-gram模型。t狀態受到t-1時刻輸出的影響，受t-k的輸出的k越大，影響越小
由於RNN幾乎只受到上一時刻的影響，而忽略了久遠信息的影響。從而造成了一定的局限性。
LSTM通過引入長短記憶方法，來維持長記憶的信息。
通過訓練核內的sigmod函數，使得LSTM可以根據不同的句子，有條件的保留和過濾歷史信息，從而達到長記憶的功能。
GRU是LSTM的簡化版，它只需要處理兩個sigmod函數的訓練，而LSTM需要三個sigmod函數的訓練，減少了訓練的參數，加快了訓練的速度，但也損失了一部分模型的復雜，在處理較復雜問題時，沒有LSTM那麼好。
auto-encoder-decoder的特點是輸出的單元數是固定的。對於一般自然語言處理，例如機器翻譯，輸入的單元個數跟輸出單元的個數並不是一一對應的，此時就需要動態的生成輸出單元。Seq2Seq通過動態的輸出結束符，代表是否輸出完成，達到可以動態的根據輸入輸出不同的單元個數。
seq2seq的缺點是，所有的輸入序列都轉化為單一的單元c，導致很多信息都將消失，對於不同的輸出yi，它可能依賴的輸入xj有可能不一樣，此時通過加入注意力模型，通過對xi進行softmax處理，並加入到y權重的訓練中，可以讓不同的y，有不同的x對它進行影響
softmax的輸入為輸入單元x，和上一個輸出單元y，聯合產生softmax的權重，進而對不同的序列，對於同一個x，會有不同的注意力到輸出
q = Wq(x)
k = Wk(x)
v = Wv(x)
x為詞向量
通過訓練，得到權重w，從而學習到這一層的softmax注意力參數
R是前一次encoder的輸出
通過增加w的數量，產生多個z，並進行堆疊，通過前饋網路，最後產生z
在使用self attention處理句子時，是沒有考慮單詞在句子中的位置信息的。為了讓模型可以加入考慮單詞的位置信息，加入了位置編碼的向量
計算如下：
pos為單詞在句子中的位置
i為詞向量的位置
d為句子的長度
位置編碼加上詞向量形成tranformer的輸入
加入了歸一化和殘差網路
最終通過softmax，輸出每個單詞的概率，並最終輸出單詞
Ⅲ 期望最大演算法(EM)
1977年，DempSter首次提出EM演算法。
假設四種實驗結果，發生的概率依次為 ，且發生的次數為 ，求 的估計。
解：使用MLE，得到：
上式是關於 的一元三次方程，不易解。
因此，以下另作處理（引入隱變數）：
將第一部分 分為 ，且出現次數為 次
將第三部分 分為 ，且出現次數為 次；
則
(1)
現在，並不知道 （隱變數）的值，只能知道分布的信息， 服從的分布為二項分布，概率數值類似於條件概率，第一個的概率是用 除以 得到的，第二個同理：
其中， ，
第一步（E步）：求期望的目的是為了消去隱變數 。
;
代入(1)式，得到：
第二步（M步）：取最大值。
EM演算法使用迭代法來更新參數。 （精髓）
任意取 ，就可以開始按照上面的公式進行迭代了。
收斂性 ：
DempSter證明：在很一般的條件下，最後會收斂。（可以參考李航老師的《統計學習方法》）
解析解：能列出公式解決的，數值上是更准確的（相比迭代解），比如MLE就是列出公式求解。
迭代解：退而求其次，當解析解難求的時候，通過迭代逼近的方式，可以獲得令人滿意的解，比如EM就是為了解決當MLE遇到高次方程難以求解的時候，提出的方法。
問：給定參數 ，觀測變數 ，隱變數 ，如何估計參數 ？
從觀測序列，可以獲得：
此時，對數似然函數為：
由於包含和（積分）的對數，因此直接求解困難。
解析解困難，轉而使用迭代解：假設第i次迭代後的 為 ，由於我們希望似然函數 是增大的，即 。
此時，考慮兩者的差：
不等式右邊是 的下界，記為 ，那麼，使得下界盡可能大，即：
Algorithm: Estimation Maximum (EM)
舉例：以三硬幣模型為例。有A、B、C三枚硬幣，分別有 的概率為正面。每次試驗為：先投A硬幣，如果A為正面，則投B硬幣；否則，投C硬幣。最終，可以觀測到的結果為硬幣的正/反面，但是不知道是由B還是C投出的（隱變數）。問：如果某次試驗數為10的結果為：{1,1,0,1,0,0,1,0,1,1}，如何估計參數 ？
顯然，題目的 隱變數為A硬幣投出的結果，此時可以採用EM解法。
先從「E」入手，求解Q函數：
然後，逐一擊破：
回代 函數：
極大似然求導數，令其為0，能取得極值點：
令上式為0
------對應書(9.6)式
令上式為0
------對應書(9.7)式
令上式為0
------對應書(9.8)式
至此，只要根據當前迭代下的 ，就能得到不同 下標的 ，進而得到下一次迭代的 。
Ⅳ EM演算法深度解析
最近在做文本挖掘的時候遇到了EM演算法，雖然讀書的時候簡單地接觸過，但當時並沒有深入地去了解，導致現在只記得演算法的名字。既然EM演算法被列為數據挖掘的十大演算法之一，正好借這個機會，重新學習一下這個經典的演算法。學習的過程中，我發現網上的資料大多講解地不夠細致，很多地方解釋得並不明了。因此我決定拋開別人的想法，僅從數學推導本身出發，盡力理解每一個公式的含義，並將其對應到實際的實驗過程當中。這篇博客記錄了我對與EM演算法的思考與理解，也是我人生中的第一篇博客，希望能夠對於想要學習EM演算法的同學有所幫助。
前面談到我在做文本挖掘的時候遇到了EM演算法，EM演算法用於估計模型中的參數。提到參數估計，最常見的方法莫過於極大似然估計——在所有的候選參數中，我們選擇的參數應該讓樣本出現的概率最大。相信看到這篇筆記的同學一定對極大似然估計非常熟悉，而EM演算法可以看作是極大似然估計的一個擴充，這里就讓我們用極大似然估計來解決一個簡單的例子，來開始正式的討論。
有A，B，C三枚硬幣，我們想要估計A，B，C三枚硬幣拋出正面的概率 , , 。我們按如下流程進行實驗100次：
記錄100次實驗的結果如下：
我們將上面的實驗結果表述如下：
表示第i次實驗中，硬幣A的結果，1代表正面，0代表反面； 表示第i次實驗中，硬幣B或硬幣C拋出正面的個數，則參數 的極大似然估計分別為：
即硬幣A，B，C各自拋出正面的次數占總次數的比例，其中 為指示函數。
實驗流程與1相同，但是我們不慎遺失了硬幣A的記錄結果，導致我們只知道隨後十次拋出了多少次正面，多少次反面，卻不知道實驗結果來自於硬幣B還是硬幣C。在這種情況下，我們是否還能估計出 , , 的值呢？
這時候利用極大似然估計似乎行不通了， 因為這種情況下，我們不但缺失了硬幣A產生的觀測值，同時也不知道哪些觀測值屬於硬幣B，哪些觀測值屬於硬幣C。
有些同學可能會提出，雖然我們無法得到三個硬幣各自產生的樣本，但是我們依然可以得到每個觀測值出現的概率。比如在第一次實驗中， 我們拋出了5次正面5次反面，我們可以做如下思考：
假設這5次正面由硬幣B得到，那麼概率應該為 ，而這次觀測值來自於硬幣B，也就是硬幣A拋出正面的概率為
假設這5次正面由硬幣C得到，那麼概率應該為 ，而這次觀測值來自於硬幣C，也就是硬幣A拋出反面的概率為
綜合起來，利用條件概率公式，這個觀測值出現的概率就是
因此我們可以將樣本整體的概率和似然函數利用 , , 表示出來，通過對似然函數求導，令其關於 的偏導數等於0，我們可以求出三個參數的值。
這個思路聽上去十分合理，我們可以順著這個思路進行數學推導，看看可以得到什麼樣的結果。首先我們計算樣本的概率:
對應的似然函數為
其中 關於 的條件分布為
的分布為
因此我們可以得到
至此，我們成功地得到了似然函數。然而觀察可以發現，這個函數是由100項對數函數相加組成，每個對數函數內部包含一個求和，想通過求導並解出導數的零點幾乎是不可能的。當然我們可以通過梯度下降來極小化這個函數，藉助深度學習庫的自動微分系統在實現上也非常容易。但是這種做法過於簡單粗暴，有沒有辦法來優雅地解決這個問題呢？在繼續討論之前，我們先將這類問題進行一般化表述：
我們觀測到隨機變數 產生的m個相互獨立的樣本 , 的分布由聯合分布 決定， 是缺失數據或無法在實驗中被直接觀測到，稱為 隱變數 ，我們想要從樣本中估計出模型參數 的值。在接下來的討論中，我們假定 的取值是離散的，於是可以得到似然函數如下:
接下來，我們就探討一下，如何利用EM演算法解決這個問題。
這一部分的數學推導，主要參考了吳恩達CS229n的筆記，並且根據個人的思考和理解，盡力對公式的每一步進行詳細的解釋。我們先簡單地介紹一下琴生不等式。
琴生不等式有多種形式，下面給出其離散形式的表述和概率論中的表述:
1.若 為嚴格凹函數， 為定義域內的n個點， 是n個正實數，且滿足 , 則下述不等式成立:
當且僅當 時，不等式取等號。
2.若 為嚴格凹函數， 為實值隨機變數，且期望存在，則下述不等式成立:
當且僅當 ，即 為常數時，不等式取等號。
註： 這里將函數上方為凹集的函數稱為凹函數， 例如 函數就是凹函數。
相信大家對琴生不等式都十分熟悉，因此這里就不做過多的說明。接下來，我們將琴生不等式應用到我們的問題中。
回到我們之前的問題上， 我們想要極大化下面這個函數:
但是我們無法對這個函數直接求導，因此我們藉助琴生不等式，對這個函數進行變換。為了讓過程看上去簡潔，下面只對求和中的第 項進行計算。
令 滿足 ，且 ，則根據琴生不等式，可以得到：
當且僅當 為常數時，上述不等式取等號。也就是說，對於任意 ， 是一個與 無關的量。設對於任意 ，我們可以得到：
因此當 時，不等式 取等號，容易驗證此時 , 與 無關。將 綜合一下，我們可以得到以下結論:
到這里為止，我們已經擁有了推導出EM演算法的全部數學基礎，基於 我們可以構建出E步和M步。上面的數學推導雖然看上去略為復雜，但實際上只用到了三個知識點：
1.琴生不等式:
2.條件概率:
3.聯合分布求和等於邊緣分布:
對上面的數學推導有疑問的同學，可以結合上面這三點，再將整個推導過程耐心地看一遍。
大部分關於EM演算法的資料，只是在數學形式上引入了 函數，即 ，以滿足琴生不等式的使用條件，卻沒有過多地解釋 函數本身。這導致了很多人完全看懂了演算法的推導，卻還是不理解這些數學公式究竟在做什麼，甚至不明白EM演算法為什麼叫做EM演算法。所以在給出E步和M步之前，我想先談一談 函數。
我們回顧一下 函數所滿足的條件（暫時不考慮琴生不等式取等號的限制），
在 所有可能的取值處有定義。可以看出， 是 的樣本空間上任意的一個概率分布。因此，我們可以對不等式 進行改寫。首先我們可以將含有 的求和寫成期望的形式:
這里 指的是在概率分布 下，求隨機變數 和 的期望。有同學會問，為什麼我們平時求期望的時候只要寫 ，並沒有指明是在哪個概率分布下的期望。這是因為一般情況下，我們都清楚地知道隨機變數 所服從的分布 ，並且默認在分布 下求期望。
舉個例子，我手上有一個硬幣，拋了10次，問拋出正面次數的期望。這種情況下，大部分人會默認硬幣是均勻的，也就是說拋出正面的次數 服從二項分布 ，期望 。這時有人提出了質疑，他說我認為你這個硬幣有問題，拋出正面的概率只有0.3，那麼在他眼裡， 期望 。
回到正題，我們利用等式 改寫不等式 ，可以得到:
這正是琴生不等式在概率論中的形式。我們可以將不等式倒過來理解：
首先，假定隨機變數 服從概率分布 ， 是 的樣本空間上的任意一個概率分布。這里 可以是一組定值，也可以是關於參數 的函數。
顯然，當我們取不同的 時，隨機變數 的期望也會隨之改變。需要注意的是，由於 與 相關，所以這里的期望不是一個數值，而是關於 的函數。
當我們令 為 的後驗分布 時，上面的期望最大。這里有兩點需要注意，1. 後驗分布 也是一個關於參數 的函數。2. 由於期望是關於 的函數，所以這里的最大指的並非是最大值，而是最大的函數。
若對於每一個 ，我們都令 為 的後驗分布 ，則上述期望之和等於我們要極大化的似然函數，即
通過上述分析，我們為尋找似然函數的極大值點 提供了一個思路。我們不去極大化似然函數本身，而是去極大化 。至於如何將這個思路實際應用，就要利用到EM演算法中的E-step和M-step。
這一節中，我們先給出E-step和M-step的數學形式，隨後在結合拋硬幣的例子來解釋這兩步究竟在做什麼。下面進入演算法的流程，首先我們任意初始化 ，按下述過程進行迭代直至收斂：
在第 次迭代中，
(E-step)對於每個 ，令
(M-step)更新 的估計值，令
EM演算法從任意一點 出發，依次利用E-step優化 ，M-step優化 ，重復上述過程從而逐漸逼近極大值點。而這個過程究竟是怎樣的呢，就讓我們一步步地揭開EM演算法的面紗。
假設我們現在隨機初始化了 ，進入第一輪迭代：
(E-step)
由於我們已經假定模型參數為 ，所以此時 不再是與 有關的函數，而是由一組常數構成的概率分布。結合拋硬幣的例子來看，這一步是在我們已知模型參數 的基礎上(雖然這是我們瞎猜的)，去推測每一次的觀測值是由哪個硬幣產生的，或者說我們對每一次觀測值做一個軟分類。比如我們根據初始化的參數，計算出 ， 。可以解釋為第 個觀測值有20%的概率來自於硬幣B，80%的概率來自於硬幣C；或者說硬幣A拋出了0.2個正面，0.8個反面。
(M-step)
考慮到 是一組常數，我們可以舍棄常數項，進一步簡化上面這個要極大化的函數
由於 不再與 相關，因此上面的函數變成了對數函數求和的形式，這個函數通常來說是容易求導的，令導數等於0，我們可以求出新的參數 。我們仍舊以拋硬幣為例進行解釋，
令 , 可以得到，
這三個參數的解釋是顯而易見的。我們在E-step中對每個觀測值進行了軟分類， 可以看成是硬幣A拋出正面的次數，所以 是 的極大似然估計； 是我們拋硬幣B的次數， 是硬幣B拋出正面的次數，所以 是 的極大似然估計；對於 我們有相同的解釋。
我們將這個結果與拋硬幣1中極大似然估計的結果相比較可以發現，之前結果中的指示函數 變成了這里的 ，在指示函數下，某個觀測值要麼來自於硬幣B，要麼來自於硬幣C，因此也稱為硬分類。而在 函數下，某個觀測值可以一部分來自於硬幣B，一部分來自於硬幣C，因此也稱作軟分類。
將上述兩步綜合起來，EM演算法可以總結如下：我們首先初始化模型的參數，我們基於這個參數對每一個隱變數進行分類，此時相當於我們觀測到了隱變數。有了隱變數的觀測值之後，原來含有隱變數的模型變成了不含隱變數的模型，因此我們可以直接使用極大似然估計來更新模型的參數，再基於新的參數開始新一輪的迭代，直到參數收斂。接來下我們就討論為什麼參數一定會收斂。
前面寫了太多的公式，但是這一部分我不打算給出收斂性的數學推導。其實數學上證明EM演算法的收斂性很容易，只需要證明每一輪迭代之後，參數的似然函數遞增，即
Ⅳ 大數據經典演算法解析（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演算法實例分析 .
Ⅵ EM演算法和混合高斯模型（一）
EM（Expectation Maximization）演算法是一種迭代演算法，用於含有隱變數的概率模型參數的極大似然估計，或極大後驗估計。EM演算法的每次迭代由兩步組成：E步，求期望（expectation）；M步，求極大值，因而被稱為期望極大演算法，簡稱EM演算法。
本文從EM演算法的引入說起，簡單介紹EM演算法的推導過程，以及其在高斯混合模型中的應用。更多的關於EM演算法的推導細節，可參見 人人都懂EM演算法 。
假設我們需要調查我們學校學生的身高分布。我們先假設學校所有學生的身高服從正態分布 。( 注意：極大似然估計的前提一定是要假設數據總體的分布，如果不知道數據分布，是無法使用極大似然估計的 )，這個分布的均值μ和標准差為σ 未知，如果我們估計出這兩個參數，那我們就得到了最終的結果。那麼怎樣估計這兩個參數呢？
學校的學生這么多，我們不可能挨個統計吧？這時候我們需要用到概率統計的思想，也就是抽樣，根據樣本估算總體。假設我們隨機抽到了 200 個人（也就是 200 個身高的樣本數據，為了方便表示，下面「人」的意思就是對應的身高）。然後統計抽樣這 200 個人的身高。根據這 200 個人的身高估計均值 μ和方差σ 。例子來自 人人都懂EM演算法 。
現在我們假設這200個人的身高服從一個正態分布N(μ，σ)，因此可以直接使用極大似然估計方法估計出這個分布的參數μ和σ。
但是，這200個人的身高真的是服從同一個正態分布嗎？實際情況並不是這樣的，男生和女生分別服從兩種不同的正態分布，即男生 女生各服從一個正態分布 ，( 注意：EM演算法和極大似然估計的前提是一樣的，都要假設數據總體的分布，如果不知道數據分布，是無法使用EM演算法的 )，而且假設我們現在只有身高數據，丟失了性別數據，那麼該怎樣評估學生的身高分布呢？
這個時候，對於每一個樣本或者你抽取到的人，就有兩個問題需要估計了，一是這個人是男的還是女的，二是男生和女生對應的身高的正態分布的參數是多少。這兩個問題是相互依賴的：
但是現在我們既不知道每個學生是男生還是女生，也不知道男生和女生的身高分布。這就成了一個先有雞還是先有蛋的問題了。雞說，沒有我，誰把你生出來的啊。蛋不服，說，沒有我，你從哪蹦出來啊。為了解決這個你依賴我，我依賴你的循環依賴問題，總得有一方要先打破僵局，不管了，我先隨便整一個值出來，看你怎麼變，然後我再根據你的變化調整我的變化，然後如此迭代著不斷互相推導，最終就會收斂到一個解（草原上的狼和羊，相生相剋）。這就是EM演算法的基本思想了。
EM的意思是「Expectation Maximization」，具體方法為：
上面的學生屬於男生還是女生我們稱之為隱含參數，女生和男生的身高分布參數稱為模型參數。
EM 演算法解決這個的思路是使用啟發式的迭代方法，既然我們無法直接求出模型分布參數，那麼我們可以先猜想隱含參數（EM 演算法的 E 步），接著基於觀察數據和猜測的隱含參數一起來極大化對數似然，求解我們的模型參數（EM演算法的M步)。由於我們之前的隱含參數是猜測的，所以此時得到的模型參數一般還不是我們想要的結果。我們基於當前得到的模型參數，繼續猜測隱含參數（EM演算法的 E 步），然後繼續極大化對數似然，求解我們的模型參數（EM演算法的M步)。以此類推，不斷的迭代下去，直到模型分布參數基本無變化，演算法收斂，找到合適的模型參數。
在開始介紹EM演算法之前，讓我們先來了解一個重要的定理——Jensen不等式。
如下圖，如果函數f(x)是凸函數，x是隨機變數，有 0.5 的概率是 a，有 0.5 的概率是 b， x的期望值就是 a 和 b 的中值了，那麼：
對於m個相互獨立的樣本:
假如沒有隱含變數z， 我們僅需要找到合適的θ極大化對數似然函數即可:
現在我們給定一個θ值（初始化θ），那麼logL(θ)的值就取決於Q i (z)和P(x (i) ,z (i) )。我們可以通過調整這兩個概率使下屆逼近logL(θ)的真實值，當不等式變為等式時，說明我們調整後的下屆就等於logL(θ)了。由Jeson不等式可知，等式成立的條件是隨機變數是常數，則有：
如果Q i (z (i) ) = P(z (i) |x (i) , θ)，則（2）式使我們包含隱藏數據的對數似然函數的一個下屆。如果我們能極大化這個下屆，則也在嘗試極大化我們的對數似然函數。即我們需要極大化下式：
由於對logaf(x)求導的結果與f(x)的系數無關（(ln(ax))'= (lna + lnx)'=1/x），因此對θ求極大似然時，可以去掉式中的常數部分Q i (z (i) )：
現在，讓我們來總結一下EM演算法的流程。
輸入：觀察數據x = (x (1) , x (2) , ... , x (m) ), 聯合分布P(x, z|θ)，條件分布P(z|x,θ)，極大迭代次數J。
（1）隨機初始化模型參數θ值；
（2）迭代求解各個分布模型的參數以及各個模型的概率：
for j from 1 to J:
輸出：模型參數θ
圖中的直線式迭代優化的路徑，可以看到每一步都會向最優值前進一步，而且前進路線是平行於坐標軸的，因為每一步只優化一個變數。
這猶如在x-y坐標系中找一個曲線的極值，然而曲線函數不能直接求導，因此什麼梯度下降方法就不適用了。但固定一個變數後，另外一個可以通過求導得到，因此可以使用坐標上升法，一次固定一個變數，對另外的求極值，最後逐步逼近極值。對應到EM上，E步：固定 θ，優化Q；M步：固定 Q，優化 θ；交替將極值推向極大。
E步 ：初始化θ A =0.6和θ B =0.5（θ A 和θ B 分別表示兩個硬幣出現正面的概率），計算每次擲硬幣選擇A和B的概率，例如第一個實驗中選擇A的概率為：
M步 ：求出似然函數下屆Q(θ，θ i ), y i 代表第j次試驗正面朝上的個數，μ j 代表第j次試驗選擇硬幣A的概率，1-μ j 代表第j次試驗選擇硬幣B的概率。
參考：
人人都懂EM演算法
《統計學習方法》. 李航
Ⅶ 從馬爾可夫模型到隱馬爾可夫模型
馬爾可夫模型個人認為這個概念應該是從 隨機過程 裡面提出來的，由馬爾可夫過程過來的概念。實際上掌握了隨機過程裡面對馬爾可夫過程的特殊情況：離散參數離散狀態的馬爾可夫鏈的數學運算的話。就能夠很好解決馬爾可夫模型上面的計算問題，包括隱馬爾科夫模型。講馬爾可夫模型以及過程重點在於其滿足的性質-馬爾可夫性。
隨機過程：
現實中時常出現，某個事物滿足一定的隨機分布，但是其隨機分布會隨著時間的變化而變化。我們假設其在時刻 符合隨機分布 並且用隨機變數 來表示。假設 。但是在時間 的時候就符合隨機分布 並且用隨機變數 來表示。假設 。也就是說某個事物的某個特徵會隨著時間的變化其對應的分布也會發生變化。這樣一個總體的過程，稱之為 隨機過程。
具體例子：
燈泡壽命問題，燈泡其實在每個時間點上都有一定的可能性會損壞，在這個時間點上損壞的可能性符合一個具體的正態分布（其 是確定的），而隨著時間的久遠，燈泡損壞的可能性就變大了。所以在之後的某個時間點上燈泡損壞的可能性可能就符合另外一個具體的正態分布（其 就和先前不一樣了，會有變壞的趨勢）。燈泡損壞在傳統的概率論中也是一個經典例子，可能傳統的概率論會認為燈泡的壽命長短符合一個隨機分布，並且用一個隨機變數來表示，我們研究這個分布的特徵。這里和傳統的概率論中不一樣，可以發現的是，引入了隨機過程，可以對隨機現象更加深入徹底地描述和研究。
定義隨機過程中的一些量。
參數：也就是上述的時間，如果是和時間有關，往往叫做時間序列。但是很多的現象研究不是和時間相關的。
狀態：也就是上述的隨著時間變化的隨機變數。
馬爾可夫過程：滿足馬爾科夫性的隨機過程。
以後再解釋
馬爾可夫性：
馬爾可夫鏈：
馬爾可夫模型和上述的關系。
具體講一下 隱馬爾可夫模型。
和普通的馬爾可夫不一樣，馬爾可夫模型是可以確定狀態序列的。也就是說序列上的每個項的分布是怎麼樣的是已知的。而隱馬爾可夫模型是連序列上的每個項的是什麼分布都不能夠知道，都是隨機的。
對於這樣的一個隨機模型。
經常要解決三個基本問題：
1). 給定 和 ，求解 。 又叫作 計算問題。
2). 給定 和 ，求解一個狀態轉換序列 ，使得最優可能產生上面的序列。又叫做估計問題。
3). 在模型參數（A或者B）未知或者參數不準確的情況下，由 來調整參數。又叫做訓練問題。
狀態一定是按著產生了部分觀察序列來的。考慮前綴。 表示處理到了n,觀察序列到n為止都是答案的概率。但是不好轉移，轉移的時候要枚舉前後隱藏狀態，考慮把隱藏狀態也表示出來。 表示處理到了n，並且第n個狀態為j的概率。
范圍：
結果：
初始化：
轉移：
知道 和 ，求Q，狀態序列，使得產生 的可能性最大。
定義：
這個函數的含義是：
模型在時刻t處於狀態i，觀察到 的最佳狀態轉換序列的概率。
從而有了轉移方程：
而 就是
因此 的轉移過程構成了一個圖，而Q就是上面的最優路徑。
利用 觀察數據進行對模型參數 或者 或者 進行預測和修正，訓練問題，又可以叫做預測問題。
並且這個問題其實是帶有隱變數的最大似乎估計，也就是EM演算法。
直接講EM,用數學角度來引入 或者 用遞歸式來求解含有隱變數的參數估計 都是可以的，後者會比較清楚。
但是課上老師給出了另外一種比較好的解釋：
考慮第三個問題，實際上應該分兩種情況。
1：帶指導的參數學習。
給出的數據是這樣的：
狀態/觀察數據。
硬幣中的例子就是
H/1 H/1 T/1 T/2 H/3 T/3 T/2 H/1 T/2 H/3 H/3 H/1
其實當擁有了數據 狀態/觀察數據 是可以直接對參數進行估計的。
假設是齊次的（一般也是齊次的，概率只和狀態有關，和時間關系不大，放在詞句中就是詞語所在的句子的部位關系不是很大，而是上下文內容關系比較大。），
考慮aij 指的是在狀態i和狀態j的轉移概率。
可以直接對上面2個2個統計進行參數估計。
考慮bi(o_j)也就是狀態為i輸出為o_j的。
一個一個枚舉來即可。
考慮pi_i。也就是初始狀態。
一個一個枚舉狀態即可。
帶有指導的是有缺點的：
數據上不可行，狀態這樣的數據其實都是人工標注的。
數據量要求比較大。
但是在NLP中這個方法是很重要的。因為效果比較好。
2：不帶指導的參數學習
數據上只給出了 觀察序列，沒有狀態序列。
實際上1中就出了答案。沒有狀態序列，我們就枚舉狀態序列。
比如上述。如果觀察出來了
1 2 2
那麼我們就考慮以下
1 2 2
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT
所有情況。
所以就產生了
H/1 H/2 H/2
H/1 H/2 T/2
....
然後分組進行統計參數估計即可。
但是這里有兩個問題：
1：狀態太多了。N^T。
2：給每個狀態的權重是一樣的。不是很科學。（實際上還行，如果使用熵最大原理。）
那麼怎麼辦？解決2考慮給不同狀態加權重，那麼要有一個先驗的的知識：
咱們先給出先驗的 模型參數。
那麼就可以計算P(Q|O,人)P（Q,O|人）這樣的東西了。
明顯可以用P(Q|O,人)作為一個路徑序列的權重。
但是這樣計算的時候，路徑序列很長。並且轉移路徑還是N^T條。
不可行。
避開對路徑的考慮。考慮參數abt最多隻有涉及兩個時間點的。
我們如果只關注兩個時間點之間的狀態。那麼就可以變成二維的。
使Q不是一個路徑的。而是只是兩個時間點之間的狀態。
q_t = i q_t+1 = j 。把這個概率計算出來的話。就能直接對aij這樣的進行估計了。
（實際上只是換了一種計數方式，就減少了問題規模，因為咱們關注的也只是路徑上兩個點兩個點之間的。）
由此引出Baum_Welch演算法：
定義以下：
這樣就能對參數們進行評估了。有以下：
這樣只要挑一個滿足條件的初始值，然後迭代求解即可。