EM算法用于含有隱變量的概率模型參數(shù)的極大似然估計产上。這里首先對隱變量解釋辆亏，舉下面的例子

（三硬幣模型）假設(shè)有3枚硬幣，分別記做 $A$ 骨稿， $B$ 笨鸡， $C$ ，這些硬幣正面出現(xiàn)的概率分別是 $\pi$ 坦冠， $p$ 和 $q$ 形耗。進行如下擲硬幣試驗：先擲硬幣 $A$ ，根據(jù)其結(jié)果選出硬幣 $B$ 或硬幣 $C$ 辙浑，正面選硬幣 $B$ 激涤，反面選硬幣 $C$ ；然后擲選出的硬幣判呕，擲硬幣的結(jié)果倦踢，出現(xiàn)正面記做1送滞，出現(xiàn)反面記做0；獨立的重復(fù) $n$ 次試驗（這里辱挥， $n=10$ ）犁嗅，觀測結(jié)果如下：
$1,1,0,1,0,0,1,0,1,1$
假設(shè)能觀測到擲硬幣的結(jié)果，不能觀測擲硬幣的過程晤碘，問如何估計三硬幣正面出現(xiàn)的概率褂微，即三硬幣模型的參數(shù) $\pi$ ， $p$ 和 $q$ 哼蛆。

其中擲硬幣 $A$ 的結(jié)果是未觀測的蕊梧，叫做隱變量，記做 $z$ 腮介。將觀測數(shù)據(jù)表示為 $Y=(Y_1,Y_2,\cdots,Y_n)^T$ 肥矢，未觀測數(shù)據(jù)表示為 $Z=(Z_1,Z_2,\cdots,Z_n)^T$ ，則觀測數(shù)據(jù)的似然函數(shù)為
$P(Y|\theta)=\sum_ZP(Y,Z|\theta)=\sum_ZP(Z|\theta)P(Y|Z,\theta)\tag1$
即
$P(Y|\theta)=\prod_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_i}+(1-\pi)q^{y_j}(1-q)^{1-y_j}]\tag2$
對模型參數(shù) $\theta=(\pi,p,q)$ 進行極大似然估計叠洗，即
$\hat\theta=\arg\max_\theta\log P(Y|\theta)\tag3$
因為擲硬幣 $A$ 的結(jié)果未知甘改，所以沒有這個問題解析解，只能通過迭代的方式灭抑，逐步增加對數(shù)似然函數(shù)十艾，找到一個解。EM算法解決的就是這樣的一類問題腾节。

接下來首先提出EM算法忘嫉，然后對其進行解釋。

EM算法

EM算法叫做Exception maximization算法案腺，顧名思義庆冕，包含求期望（Exception ）和極大化（maximization）兩個步驟。

輸入：觀測變量數(shù)據(jù) $Y$ 劈榨，隱變量數(shù)據(jù) $Z$ 访递，聯(lián)合分布 $P(Y,Z|\theta)$ ，條件分布 $P(Z|Y,\theta)$ 同辣；

輸出：模型參數(shù) $\theta$ 拷姿。

（1）選擇參數(shù)的初值 $\theta^{(0)}$ ，開始迭代旱函；

（2）E步：記 $\theta^{(i)}$ 為第 $i$ 次迭代參數(shù) $\theta$ 的估計值响巢，在第 $i+1$ 次迭代的E步，計算
$\begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}$
這里 $P(Z|Y,\theta^{(i)})$ 是在給定觀測數(shù)據(jù) $Y$ 和當(dāng)前參數(shù)估計 $\theta^{(i)}$ 下隱變量數(shù)據(jù) $Z$ 的條件概率分布棒妨；

（3）M步：求使 $Q(\theta,\theta^{(i)})$ 極大化的 $\theta$ 抵乓，確定第 $i+1$ 次迭代的參數(shù)的估計值 $\theta^{(i+1)}$
$\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})$
（4）重復(fù)第(2)步和第(3)步，直到收斂。

第(2)步中 $Q(\theta,\theta^{(i)})$ 是EM算法的核心灾炭，稱為Q函數(shù)。

Q函數(shù)定義：完全數(shù)據(jù)的對數(shù)似然函數(shù) $\log P(Y,Z|\theta)$ 關(guān)于給定觀測數(shù)據(jù) $Y$ 和當(dāng)前參數(shù) $\theta^{(i)}$ 下對未觀測數(shù)據(jù) $Z$ 的條件概率分布 $P(Z|Y,\theta^{(i)})$ 的期望稱為Q函數(shù)颅眶，即
$Q(\theta,\theta^{(i)})=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]$
因為 $E_Z[g(z)]=\sum_Zp(z)g(z)$ 蜈出，所以
$\begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}\tag4$
其中，因為數(shù)據(jù) $Y$ 未包含隱變量 $Z$ 的結(jié)果涛酗，所以稱為不完全數(shù)據(jù)铡原， $\log P(Y|\theta)$ 稱為不完全數(shù)據(jù)的對數(shù)似然函數(shù)，而數(shù)據(jù) $Y,Z$ 則稱為完全數(shù)據(jù)商叹， $\log P(Y,Z|\theta)$ 稱為完全數(shù)據(jù)的對數(shù)似然函數(shù)燕刻。
下面關(guān)于EM算法作幾點說明：

步驟（1）參數(shù)的初值可以任意選擇，但需注意EM算法對初值是敏感的剖笙。
步驟（2）E步求 $Q(\theta,\theta^{(i)})$ 卵洗。Q函數(shù)式中 $Z$ 是未觀測數(shù)據(jù)， $Y$ 是觀測數(shù)據(jù)弥咪，注意过蹂， $Q(\theta,\theta^{(i)})$ 的第1個變元表示要極大化的參數(shù)，第2個變元表示參數(shù)的當(dāng)前估計值聚至。每次迭代實際在求Q函數(shù)及其極大酷勺。
步驟（3）M步求 $Q(\theta,\theta^{(i)})$ 的極大化，得到 $\theta^{(i+1)}$ 扳躬，完成一次迭代 $\theta^{(i)}\rightarrow\theta^{(i+1)}$ 脆诉。
步驟（4）給出停止迭代的條件，一般是對較小的正數(shù) $\varepsilon_1$ 贷币， $\varepsilon_2$ 击胜，若滿足

$||\theta^{(i+1)}-\theta^{(i)}||\lt\varepsilon_1\ \ 或\ \ ||Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})||\lt\varepsilon_2$

? 則停止迭代。

下面給出這種做法為什么可以對觀測數(shù)據(jù)（不完全數(shù)據(jù)）進行極大似然估計片择。

EM算法的導(dǎo)出

對于一個含有隱變量的模型潜的，目標(biāo)是極大化觀測數(shù)據(jù)（不完全數(shù)據(jù)） $Y$ 關(guān)于參數(shù) $\theta$ 的對數(shù)似然函數(shù)，即最大化
$L(\theta)=\log P(Y|\theta)=\log\sum_ZP(Y,Z|\theta)=\log\bigg(\sum_ZP(Y|Z,\theta)P(Z|\theta)\bigg)\tag5$
上面第一步用到邊緣概率和聯(lián)合概率的關(guān)系 $P(Y|\theta)=\sum_ZP(Y,Z|\theta)$ 字管，第二步用到的是條件分布公式 $P(AB)=P(A|B)P(B)$ 啰挪。對這一對數(shù)似然函數(shù)極大化的困難是因為上式中包含未觀測數(shù)據(jù) $Z$ 。

但是如果通過第 $i$ 次迭代得到估計的參數(shù) $\theta^{(i)}$ 嘲叔，此時再找到一個參數(shù) $\theta$ 亡呵，使得 $L(\theta)\gt L(\theta^{(i)})$ （和IIS算法思路有點類似），那么同樣也可以起到極大似然估計的效果硫戈。為此锰什，考慮兩者的差
$L(\theta)-L(\theta^{(i)})=\log\bigg(\sum_ZP(Y|Z,\theta)P(z|\theta)\bigg)-\log P(Y|\theta^{(i)})$

利用Jensen不等式，過程略，得到其下界：
$L(\theta)-L(\theta^{(i)})\geq\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag6$
于是得到對數(shù)似然函數(shù)的下界
$L(\theta)\geq L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag7$
定義
$B(\theta,\theta^{(i)})\hat=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\tag8$
則
$L(\theta)\geq B(\theta,\theta^{(i)})$
并且
$\begin{align} B(\theta^{(i)},\theta^{(i)})&=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta^{(i)})P(Z|\theta^{(i)})}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ &=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}\\ &=L(\theta^{(i)}) \end{align}$
即可以使 $B(\theta,\theta^{(i)})$ 可以增大的 $\theta$ 汁胆，也可以使 $L(\theta)$ 增大梭姓，所以極大似然估計變成了使 $B(\theta,\theta^{(i)})$ 極大化的問題，即
$\theta^{(i+1)}=\arg\max_\theta B(\theta,\theta^{(i)})$
所以
$\theta^{(i+1)}=\arg\max_\theta B(\theta,\theta^{(i)})=\arg\max_\theta\bigg(L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\bigg)$
省去不包含變量 $\theta$ 的常數(shù)項 $L(\theta^{(i)})$ 嫩码， $P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})$ 誉尖，得到
$\begin{align} \theta^{(i+1)}&=\arg\max_\theta\bigg(\sum_ZP(Z|Y,\theta^{(i)})\log P(Y|Z,\theta)P(Z|\theta)\bigg)\\ &=\arg\max_\theta\bigg(\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta)\bigg)\\ &=\arg\max_\theta Q(\theta,\theta^{(i)}) \end{align}$
所以，在EM算法中最大化Q函數(shù)铸题，就等同于最大對數(shù)似然函數(shù)的下界铡恕，從而進行極大似然估計。但是這種算法并不能保證找到全局最優(yōu)值丢间。

EM算法可以用于無監(jiān)督學(xué)習(xí)探熔，略。EM算法的收斂性證明略烘挫。

EM算法在高斯混合模型學(xué)習(xí)中的應(yīng)用

高斯混合模型定義

高斯混合模型是指具有如下形式的概率分布模型：
$P(y|\theta)=\sum_{k=1}^K\alpha_k\phi(y|\theta_k)\tag9$
其中诀艰， $\alpha_k$ 是系數(shù)， $\alpha_k\geq0$ 墙牌， $\sum_{k=1}^K\alpha_k=1$ 涡驮； $\phi(y|\theta_k)$ 是高斯分布密度， $\theta_k=(\mu_k,\sigma_k^2)$ 喜滨，
$\phi(y|\theta_k)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)$
稱為第 $k$ 個模型捉捅。

高斯混合模型參數(shù)估計的EM算法

可以設(shè)想觀測數(shù)據(jù) $y_j$ ， $j=1,2,\cdots,N$ 虽风，是這樣產(chǎn)生的：首先棒口，依概率 $\alpha_k$ 選擇第 $k$ 個高斯分布分模型 $\phi(y|\theta_k)$ ；然后依第 $k$ 個分模型的概率分布 $\phi(y|\theta_k)$ 生成觀測數(shù)據(jù) $y_j$ 辜膝，這是觀測數(shù)據(jù) $y_j$ 无牵， $j=1,2,\cdots,N$ ，是已知的厂抖；反應(yīng)觀測數(shù)據(jù) $y_j$ 來自第 $k$ 個分模型的數(shù)據(jù)是未知的茎毁， $k=1,2,\cdots,K$ ，以隱變量 $\gamma_{jk}$ 表示忱辅，其定義如下：
$\gamma_{jk}= \begin{cases}1,\ \ &第j個觀測來自第k個分模型\\ 0,\ \ & 否則 \end{cases}\\ j=1,2,\cdots,N;\ \ k=1,2,\cdots,K$
$\gamma_{jk}$ 是0,1隨機變量七蜘。

有了觀測數(shù)據(jù) $y_j$ 及未觀測數(shù)據(jù) $\gamma_{jk}$ ，那么完全數(shù)據(jù)是
$(y_j,\gamma_{j1},\gamma_{j2},\cdots,\gamma_{jK}),\ \ j=1,2,\cdots,N$
于是可以寫出完全數(shù)據(jù)的似然函數(shù)：
$\begin{align} P(y,\gamma|\theta)&=\prod_{j=1}^NP(y_j,\gamma_{j1},\gamma_{j2},\cdots,\gamma_{jK}|\theta)\\ &=\prod_{k=1}^K\prod_{j=1}^N[\alpha_k\phi(y_j|\theta_k)]^{\gamma_{jk}}\\ &=\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N[\phi(y_j|\theta_k)]^{\gamma_{jk}}\\ &=\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N\bigg[\frac{1}{\sqrt{2\pi}\sigma_k}\exp\bigg(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\bigg)\bigg]^{\gamma_{jk}} \end{align}$
其中墙懂， $n_k=\sum_{j=1}^N\gamma_{jk}$ （依賴第 $k$ 個分類器的樣本數(shù)）橡卤， $\sum_{k=1}^Kn_k=N$ 。

那么完全數(shù)據(jù)的對數(shù)似然函數(shù)為
$\log P(y,\gamma|\theta)=\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}$
確定Q函數(shù)
$\begin{align} Q(\theta,\theta^{(i)})&=E_{P(\gamma|y,\theta^{(i)})}[\log P(y,\gamma|\theta)]\\ &=E_{P(\gamma|y,\theta^{(i)})}\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\\ &=\sum_{k=1}^K\bigg\{\sum_{j=1}^N(E\gamma_{jk})\log\alpha_k+\sum_{j=1}^N(E\gamma_{jk})\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\\ \end{align}\tag{10}$
其中
$\begin{align} E\gamma_{jk}&=\hat\gamma_{jk}=E(\gamma_{jk}|y,\theta)=P(\gamma_{jk}=1|y,\theta)\\ &=\frac{P(\gamma_{jk}=1,y_j|\theta)}{\sum_{k=1}^KP(\gamma_{jk}=1,y_j|\theta)}\\ &=\frac{P(y_j|\gamma_{jk}=1,\theta)P(\gamma_{jk}=1|\theta)}{\sum_{k=1}^KP(y_j|\gamma_{jk}=1,\theta)P(\gamma_{jk}=1|\theta)} \end{align}$

$\hat\gamma_{jk}$ 是在當(dāng)前模型參數(shù)下第 $j$ 個觀測數(shù)據(jù)來自第 $k$ 個分模型的概率损搬，稱為分模型 $k$ 對觀測數(shù)據(jù) $y_j$ 的響應(yīng)度碧库。

根據(jù)開頭的描述柜与， $P(y_j|\gamma_{jk}=1,\theta)=\phi(y_k|\theta_k)$ ， $P(\gamma_{jk}=1|\theta)=\alpha_k$ 嵌灰，所以
$E\gamma_{jk}=\hat\gamma_{jk}=E(\gamma_{jk}|y,\theta)=\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)}\tag{11}$
將 $\hat\gamma_{jk}=E\gamma_{jk}$ 及 $n_k=\sum_{j=1}^NE\gamma_{jk}$ （此處的 $n_k$ 實際為 $E_{P(\gamma_{jk}|y,\theta)}n_k$ 弄匕， $n_k=\sum_{j=1}^N\gamma_{jk}$ ）代入公式(10)得到
$Q(\theta,\theta^{(i)})=\sum_{k=1}^K\bigg\{n_k\log\alpha_k+\sum_{j=1}^N\hat\gamma_{jk}\bigg[\log(\frac1{\sqrt{2\pi}})-\log\sigma_k-\frac1{2\sigma_k^2}(y_j-\mu_k^2)\bigg]\bigg\}\tag{12}$
接下來需要求Q函數(shù)的極大化（極大化觀測數(shù)據(jù)對數(shù)似然函數(shù)的下界），即
$\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})$
其中 $\theta=(\alpha_k,\mu_k,\sigma_k^2)$ 伞鲫， $k=1,2,\cdots,K$ 粘茄，將公式(12)對 $\mu_k$ 和 $\sigma_k^2$ 求偏導(dǎo)等于0，得到第 $i+1$ 次的更新值 $\hat\mu_k$ 和 $\hat\sigma_k^2$ 秕脓，同樣將公式(12)對 $\alpha_k$ 求偏導(dǎo)等于0，加上條件 $\sum_{k=1}^K\alpha_k=1$ 儒搭，求得更新值 $\hat\alpha_k$ 吠架。計算更新值時 $\hat\gamma_{jk}$ ， $n_k$ 用到的參數(shù)是第 $i$ 次更新得到的值搂鲫，所以可以通過迭代的方式不斷更新參數(shù)直到收斂傍药。求得的 $\hat\mu_k$ ， $\hat\sigma_k^2$ 和 $\hat\alpha_k$ 為
$\hat\mu_k=\frac{\sum_{j=1}^N}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K\tag{13}$

$\hat\sigma_k^2=\frac{\sum_{j=1}^N\hat\gamma_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K\tag{14}$

$\hat\alpha_k=\frac{n_k}N=\frac{\sum_{j=1}^N\hat\gamma_{jk}}N,\ \ k=1,2,\cdots,K\tag{15}$

高斯混合模型參數(shù)估計的EM算法

輸入：觀測數(shù)據(jù) $y_1,y_2,\cdots,y_N$ 魂仍，高斯混合模型拐辽；

輸出：高斯混合模型參數(shù)。

（1）取參數(shù)的初始值開始迭代（初值敏感）

（2）E步：依據(jù)當(dāng)前模型參數(shù)擦酌，計算分模型 $k$ 對觀測數(shù)據(jù) $y_j$ 的響應(yīng)度
$\hat\gamma_{jk}=\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)},\ \ j=1,2,\cdots,N;\ \ k=1,2,\cdots,K$
（3）M步：計算新一輪迭代的模型參數(shù)
$\hat\mu_k=\frac{\sum_{j=1}^N}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K$

$\hat\sigma_k^2=\frac{\sum_{j=1}^N\hat\gamma_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^N\hat\gamma_{jk}},\ \ k=1,2,\cdots,K$

$\hat\alpha_k=\frac{n_k}N=\frac{\sum_{j=1}^N\hat\gamma_{jk}}N,\ \ k=1,2,\cdots,K$

（4）重復(fù)第(2)步和第(3)步俱诸，直到收斂。

統(tǒng)計機器學(xué)習(xí)-EM算法（期望極大算法）

統(tǒng)計機器學(xué)習(xí)-EM算法（期望極大算法）

EM算法

EM算法的導(dǎo)出

EM算法在高斯混合模型學(xué)習(xí)中的應(yīng)用

高斯混合模型定義

高斯混合模型參數(shù)估計的EM算法

高斯混合模型參數(shù)估計的EM算法