本節(jié)講的主要是EM算法的推導(dǎo)，對于算法的應(yīng)用解釋的不多，所以這里不多贅述，只講講推理的主要思想。

E步就是想根據(jù)上一步的參數(shù)θ，找到最好的Q_i，得到最好的下界，最好的下界。。

M步，就是想根據(jù)上一步得到的最好的下界（固定住Q），找到這個下界上最大的值，找到最好的θ。。

1、Jensen不等式

如果f是凸函數(shù)，X是隨機(jī)變量，那么

當(dāng)且僅當(dāng)X是常量時，上式左右兩邊相等。

從圖中可以看到，這是成立的。

當(dāng)不等式，應(yīng)用于凹函數(shù)時，不等號方向相反 ，也就是：

2、EM算法

--------------------------------------------------------------------------------------
故意寫在前面，是為了下面思路連接起來清晰一些。
--------------------------------------------------------------------------------------

log(x)是凹函數(shù)，并且

是

的期望。其中，X是z⁽ⁱ⁾ , Q_i(z⁽ⁱ⁾)是p_k，上式是g(x)。

相當(dāng)于求g(x)的期望。再根據(jù)不等式，可以得到（3）。

-----------------------------------------------------------------------

2.1 開始推導(dǎo)

已有數(shù)據(jù)x⁽ⁱ⁾，樣例間獨(dú)立，我們想要找到每個樣例隱含的類別z，已知數(shù)據(jù)，又假設(shè)了分布，所以想到用極大似然 估計，如下：

但是，直接求θ并不好求，所以我們用EM方法，不斷地建立極大似然函數(shù)的下界（E步），然后優(yōu)化下界（M步）。其中用到了Jensen不等式以及“自變量的函數(shù)”期望公式。

此時相當(dāng)于求出了下界的表達(dá)式。但是，想要找出最好的下界，那么最好就是2和3兩式 相等。

再由

認(rèn)為下面的[p(x,z)/Q(z)] 是隨機(jī)變量X（這里不同于上式為了推出公式3的那個X了），函數(shù)log是f。于是可以知道f(E(X)) >= E[f(X)].即，

根據(jù)前面所說的，當(dāng)且僅當(dāng)X是常量時，

等式才能相等。把上面等式中的Q移到右邊，再累計加k個不同類別的Q。
sigma Q = 1.于是可以得到：

再帶入上式，可以求出Q：

可以看出，固定其他參數(shù)后，類別的概率密度計算公式就是后驗(yàn)概率

另外，至此，Q已經(jīng)求出，就可以根據(jù)前面的（3）式，得到一個下界。然后接下來的M步，就可以根據(jù)上面得到的下界函數(shù)，極大化，求得參數(shù)θ。

一般的EM算法的步驟如下：

--------------------------------------------------------
其實(shí)，到現(xiàn)在為止，EM的思想什么的跟前面的高斯混合模型是一樣的，前面寫這么多，就是為了告訴你，為什么E步中，Q要是后驗(yàn)概率。

2.2 保證EM收斂。

我們只需要證明

就行了。
筆記上的推導(dǎo)式能夠看明白的，這里，畫個圖，來加深理解。

如圖，橫坐標(biāo)是θ，縱坐標(biāo)是l(θ)的值：

最上面的曲線是p(x)的最大似然估計，整個算法就是在不停地逼近最大似然估計值，最終得到最大似然估計時的參數(shù)θ即為所求。

下面的曲線，就是在固定Q_i以后，得到的下界函數(shù)，也是θ的函數(shù)。比如，最下面的曲線，就是在剛剛開始時，隨機(jī)指定好類別以后（相當(dāng)于固定了Q₀）得到的第一個下界函數(shù)，θ₀是在每個樣例的Q₀已知的情況下（有監(jiān)督），通過極大似然得到的。

（一開始，就可以認(rèn)為，極大似然函數(shù)l(θ)其實(shí)是Q_i和θ兩個參數(shù)的函數(shù)，而EM的過程，其實(shí)就是，固定一個，然后最大化l(θ)求得另一個參數(shù)，然后再固定求得的參數(shù)再去最大化另一個參數(shù)，類似于坐標(biāo)上升法，不斷地逼近最優(yōu)值，學(xué)到最終的參數(shù)。）
現(xiàn)在開始EM算法，E步，根據(jù)上一步得到的θ₀，用后驗(yàn)概率

求得每個類別的分布Q_i，然后就是M步，固定Q_i，最大化此時得到的下界函數(shù)。得到新的參數(shù)θ₁。

對應(yīng)到圖上就是

• E步：
  先根據(jù)剛剛開始得到的參數(shù)θ₀，用后驗(yàn)概率（由前面證明可知此時會得到最好的下界）求得Q₁。
• M步：
  固定Q₁，此時下界又公式（3）可以求得，即：圖中的l₀(θ)，最大化這個函數(shù)，得到新的估計的參數(shù)θ₁。
• 不斷循環(huán)上面兩步，知道最終，下界函數(shù)的最大值逼近了或者等于原 極大似然函數(shù)的最大值，此時這個下界函數(shù)的估計的參數(shù)θ_i就是要求的值。

圖中對應(yīng)到EM算法中：

• 1、在E步中根據(jù)Q得到的下界，確實(shí)都是原極大似然函數(shù)的下界。

• 2、可以更加直觀的理解公式4/5/6、圖中的A點(diǎn)對應(yīng)l₁(θ₁)，B點(diǎn)對應(yīng)公式4中l(wèi)₀(θ₁)，C點(diǎn)對應(yīng)公式5/6中l(wèi)₀(θ₀)。

• 3、另外，我們發(fā)現(xiàn)。圖中的C點(diǎn)和A點(diǎn)是l₀下界函數(shù)和l₁下界函數(shù)的交點(diǎn)。這說明此時的l₀函數(shù)是在固定了θ之后，能找到的最好的下界函數(shù)了此時的Q值就是Q₀。

EM算法為什么有E，是因?yàn)槔昧薐ensen不等式，在每一步中，都得到了期望的下界。

關(guān)于重新審視混合高斯模型中的公式推導(dǎo)，可以看看講義中的筆記，便于理解，這里不贅述了。

3、總結(jié)

有監(jiān)督學(xué)習(xí)，只有一個變量，根據(jù)數(shù)據(jù)可以直接求出參數(shù)θ。

聚類問題，無監(jiān)督學(xué)習(xí)，不知道類別標(biāo)簽，所以有兩個變量，一個是參數(shù)θ，一個是類別標(biāo)簽z。

但是，可以參考前面所講的坐標(biāo)上升法，一次固定一個變量，最大化函數(shù)估計出另一個變量的，然后逐步逼近極值。

對應(yīng)到EM算法中，就是E步估計隱含變量，M步估計其他參數(shù)，交替將極值推向最大。

EM中還有“硬”指定和“軟”指定的概念，“軟”指定看似更為合理，但計算量要大，“硬”指定在某些場合如K-means中更為實(shí)用（要是保持一個樣本點(diǎn)到其他所有中心的概率，就會很麻煩）。