所謂EM算法，指的是就是Expect-Maximum算法，是一種非常有用的算法。假設這么一個問題，我們有一堆樣本集合X，我們已知該樣本總體的分布類型（比如是高斯分布），但是我們不知道這個分布的參數具體是多少，我們希望有方法能夠根據這些觀測到的樣本集合來估計出這個分布的參數。怎么辦呢？于是就有了極大似然估計，該方法思路很簡單，計算出這些樣本出現的分布概率公式，該公式肯定包含了這些參數作為公式的因子。我們的目標是使得該樣本出現的概率最大，那么剩下的問題就是一個數學問題了，選擇合適的參數值使得這個公式的值最大，比如求導等等。極大似然估計的的思路很直接，選擇一個目標函數，使該目標函數最大。

如果我們在對上述問題再加一點難度，除了分布參數我們不知道，另外還有一些隱藏的變量我們也不知道，或者說觀測到得數據不完整，在這種情況下，包含了隱藏變量的目標函數往往沒有解析解，因此無法估算出這些參數變量。那我們又該怎么估計出這些參數和這些缺失的隱藏變量呢？解決的方法就是EM算法。關于EM算法，52npl上有一篇博客做了比較深刻的說明，請參閱。這里對其說明進行一些評注，便于大家理解。

EM算法的目標是找出有隱性變量的概率模型的最大可能性解，它分為2個步驟，E-step和M-step，E-step根據最初假設的模型參數值或者上一步的模型參數計算出隱性變量的后驗概率，其實就是隱性變量的期望，M-step根據這個E-step的后驗概率重新計算出模型參數，然后再重復這兩個步驟，直至目標函數收斂。

觀測到的變量組成的向量我們表示成X，所有隱性變量組成的向量為Z，模型的參數表示成（一個或多個參數）。在分類問題中，Z就表示的是可能的潛在分類，X就是需要分類的數據，我們得目標是找出模型的參數和隱性變量來使得X出現的概率最大，也就是最大（其實本來可以寫成，但是不是隨機變量而是一個參數，所以將 | 改成；）

由于很多模型的概率都帶有指數，所以在上加一個對數ln，這個對數并不影響其極值，的最大值也就是ln的最大值。

假設是上的一個概率分布，那么就有，

公式（1）

最后一步是基于琴生不等式，所謂琴生不等式

需要注意的是，中國大陸數學界某些機構關于函數凹凸性定義和國外的定義是相反的。Convex Function在某些國內的數學書中指凹函數。Concave Function指凸函數。但在中國大陸涉及經濟學的很多書中，凹凸性的提法和國外的提法是一致的，也就是和數學教材是反的。舉個例子，同濟大學高等數學教材對函數的凹凸性定義與本文相反，本條目的凹凸性是指其上方圖是凹集或凸集，而同濟大學高等數學教材則是指其下方圖是凹集或凸集，兩者定義正好相反。

在本文中，ln是一個凹函數。

根據公式（1），我們看到了的下界是多少。EM算法分為2步：

第一步：E-step

其目的是計算出的下界，以及在此下界時，的值。

根據琴聲不等式，我們得知在到達下界時的條件為

公式（2）

c為常數。我們已知，那么此臨界條件下由公式（2）就有

公式2變化一下如下

公式3

第二步：M-step

在E-step中，我們得到了的下界以及此下界時的值，那么在M-step中我們的目標就變成了通過變換參數來最大化這個下界。下界提高了，那么值也會提高。

M-step本質上就是求ln的極值點，求極值點的方法就不用再啰嗦了吧，求偏導，通過_求參數

_{EM算法概要如下}

EM算法通過不斷提高目標函數的下界的方法來尋找目標函數的最大值，因為通過M-step使得的下界不斷提高，只要存在最大值，那么EM算法一定會收斂。

做了這么多分析，舉兩個例子，可能會更容易理解。先看第一個例子，來自文獻[3]：

?

混合高斯模型

數據X是一個實例集合，它由k個不同的正態分布混合而成的分布生成，這里涉及k個不同的正態分布的混合，而且我們還不知道哪個變量實例由哪個分布生成的。因此這是一個涉及隱藏變量的典型例子?？梢园衙總€實例完整描述成，其中xi是第i個實例的觀測值，表示k個正態分布中的哪一個用于生成xi，確切得講，當xi由第j個正態分布產生時，zij為1，否則為0。由此Z向量只有一個分量為1，其它分量為0。這里xi是實例描述中已經觀察到的變量，是隱藏變量。k個正態分布的均值就是我們需要估計的模型參數。

算法伊始，我們首先假設一個模型參數初始值，接下來就是計算我們的目標函數，該目標函數的公式推導如下：

公式2

接下來就是E-step.我們的目標是選擇一個概率分布使得達到下界，我們就有

這里E[Zij]=實例Xi由第j個高斯分布生成的概率

?

那此時我們目標函數的值根據公式2就是

公式3

接下來就是M-step，在確定的情況下，選擇合適參數使得最大化，根據公式2，這就是一個數學問題，對公式3求偏導，你會發現參數的極值點為

然后算法就利用估算出的參數再重復計算E-step，M-step直至收斂。

因子分析

所謂因子分析，就是指從變量群中提取公共因子的方法，該因子是用來描述隱藏在觀測變量中的一些更基本的，但又無法直接測量到的隱性變量。EM算法也可以用來解決這樣的問題，從而能夠估算出隱藏的公共因子及該模型的參數。文獻4的博客給出了一個很好的說明，講得比較清楚。這里主要是引用這篇文章的內容，加入一些自己的評論，使其更便于理解。

舉個因子分析的例子，有m個n維特征向量的樣本集，每個樣本實例表示為，樣本實例的生成模型為

其中是樣本點，其維度為n，其表示為

代表因子，該因子存在于一個k維向量空間，該k維空間就代表因子的維度空間，也就是說每一個實例變量實際上是由這k維的因子所決定的，我們目標就是估算出實例變量的k維因子。其公式表示如下

因子遵循多元正態分布，。表示單位矩陣，對角線元素為1，其他元素為0.

是一個變換矩陣，有時也被稱為裝載矩陣，其目的是將因子映射到樣本的n維空間。

是一個n維向量，其含義是樣本的中心點。

是一個n維向量，表示的是真實樣本和模型的誤差，同一樣，它也遵循多元高斯分布，?其中是一個n x n對角矩陣

下面來分析EM算法的使用，首先明確我們的目標，我們的目標是根據樣本實例集估算出參數值，，。有了這三個參數我們就能根據模型以及樣本實例計算出每個樣本對應的因子向量（也就是隱藏變量），一個矩陣方程組變化而已。

回想EM算法，那么對應因子分析，其E-step如下：

我們將觀測到得實例變量X和隱藏變量Z組成一個聯合的變量Y，該聯合變量Y也符合多元高斯分布。為什么Y也符合多元高斯分布呢？很簡單，首先Z是一個多元高斯分布，而X是多元高斯分布變量Z的一個線性變化，所以X也是一個多元高斯分布(參見文獻[5]，多元正態分布的線性變化仍然是)，那么X，Z組合成的變量Y也符合高斯分布。其公式代表如下：

參見文獻[5]，你會發現多元正態分布的另外一個特性，多元正態分布的條件分布仍然是多元正態分布

該特性表述如下：

對應我們的例子,就有

這個過程中利用了z和獨立假設()

公式如下

那么就可以得到Y的分布：

、

套用上述的特性-性質6，就有

這就是我們的目標。E-step就到此為止。再看M-step，M-step的目標函數如下

分別對3個參數求該目標函數的偏導，得到3個偏導公式，讓其都為0，組成一個方程組。該方程組的解就是我們待沽參數。

具體的公式推導參見文獻[4]，文獻[4]給出了比較詳細的推導，如果對多元高斯分布了解的比較深入的話，該推導應該不難讀懂。

個人覺得文獻[3]中關于EM的講述有一些瑕疵，講得不是很清楚，但是文中的例子倒是可以作為參考。文獻[4],[5]對此講述的比較清楚，是個非常不錯的參考，值得一讀。

?

參考文獻：

[1]理解EM算法 52nlp

[2]http://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0

[3]數據挖掘原理與算法-毛國君

[4]?http://www.cnblogs.com/jerrylead/archive/2011/05/11/2043317.html

[5]多維高斯分布講解?http://www.docin.com/p-121202383.html

[6] EM算法http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html

[7] The Top Ten Algorithms in Data Mining