EM算法

EM算法

EM算法基本思想

? 最大期望算法（Expectation-Maximization algorithm, EM），是一類通過迭代進(jìn)行極大似然估計(jì)的優(yōu)化算法，通常作為牛頓迭代法的替代，用于對包含隱變量或缺失數(shù)據(jù)的概率模型進(jìn)行參數(shù)估計(jì)。

? 最大期望算法基本思想是經(jīng)過兩個(gè)步驟交替進(jìn)行計(jì)算：

? 第一步是計(jì)算期望（E），利用對隱藏變量的現(xiàn)有估計(jì)值，計(jì)算其最大似然估計(jì)值

? 第二步是最大化（M），最大化在E步上求得的最大似然值來計(jì)算參數(shù)的值。

? M步上找到的參數(shù)估計(jì)值被用于下一個(gè)E步計(jì)算中，這個(gè)過程不斷交替進(jìn)行。

EM算法推導(dǎo)

? 對于m個(gè)樣本觀察數(shù)據(jù)x=(x^{1},x^{2},...,x^{m})，現(xiàn)在想找出樣本的模型參數(shù)\theta，其極大化模型分布的對數(shù)似然函數(shù)為：
\theta = \mathop{\arg\max}_\theta\sum\limits_{i=1}^m logP(x^{(i)};\theta)
如果得到的觀察數(shù)據(jù)有未觀察到的隱含數(shù)據(jù)z=(z^{(1)},z^{(2)},...z^{(m)})，極大化模型分布的對數(shù)似然函數(shù)則為：
\theta =\mathop{\arg\max}_\theta\sum\limits_{i=1}^m logP(x^{(i)};\theta) = \mathop{\arg\max}_\theta\sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}, z^{(i)};\theta) \tag{a}
由于上式不能直接求出\theta，采用縮放技巧：
\sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}, z^{(i)};\theta) = \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}, z^{(i)};\theta)}{Q_i(z^{(i)})} \\ \geqslant \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}, z^{(i)};\theta)}{Q_i(z^{(i)})}
上式用到了Jensen不等式：
log\sum\limits_j\lambda_jy_j \geqslant \sum\limits_j\lambda_jlogy_j\;\;, \lambda_j \geqslant 0, \sum\limits_j\lambda_j =1
并且引入了一個(gè)未知的新分布Q_i(z^{(i)})。

此時(shí)，如果需要滿足Jensen不等式中的等號(hào)，所以有：
\frac{P(x^{(i)}, z^{(i)};\theta)}{Q_i(z^{(i)})} =c, c為常數(shù)
由于Q_i(z^{(i)})是一個(gè)分布，所以滿足
\sum\limits_{z}Q_i(z^{(i)}) =1
綜上，可得：
Q_i(z^{(i)}) = \frac{P(x^{(i)}， z^{(i)};\theta)}{\sum\limits_{z}P(x^{(i)}, z^{(i)};\theta)} = \frac{P(x^{(i)}, z^{(i)};\theta)}{P(x^{(i)};\theta)} = P( z^{(i)}|x^{(i)};\theta)
如果Q_i(z^{(i)}) = P( z^{(i)}|x^{(i)};\theta) ，則第(1)式是我們的包含隱藏?cái)?shù)據(jù)的對數(shù)似然的一個(gè)下界。如果我們能極大化這個(gè)下界，則也在嘗試極大化我們的對數(shù)似然。即我們需要最大化下式：
\mathop{\arg\max}_\theta \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}， z^{(i)};\theta)}{Q_i(z^{(i)})}
簡化得：
\mathop{\arg\max}_\theta \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log{P(x^{(i)}, z^{(i)};\theta)}
以上即為EM算法的M步，\sum\limits_{z^{(i)}}Q_i(z^{(i)})log{P(x^{(i)}, z^{(i)};\theta)}?可理解為logP(x^{(i)}, z^{(i)};\theta)基于條件概率分布Q_i(z^{(i)})的期望。以上即為EM算法中E步和M步的具體數(shù)學(xué)含義。

圖解EM算法

? 考慮上一節(jié)中的（a）式，表達(dá)式中存在隱變量，直接找到參數(shù)估計(jì)比較困難，通過EM算法迭代求解下界的最大值到收斂為止。

在這里插入圖片描述

? 圖片中的紫色部分是我們的目標(biāo)模型p(x|\theta)，該模型復(fù)雜，難以求解析解，為了消除隱變量z^{(i)}的影響，我們可以選擇一個(gè)不包含z^{(i)}的模型r(x|\theta)，使其滿足條件r(x|\theta) \leqslant p(x|\theta)。

求解步驟如下：

（1）選取\theta_1，使得r(x|\theta_1) = p(x|\theta_1)，然后對此時(shí)的r求取最大值，得到極值點(diǎn)\theta_2，實(shí)現(xiàn)參數(shù)的更新。

（2）重復(fù)以上過程到收斂為止，在更新過程中始終滿足r \leqslant p.

EM算法流程

輸入：觀察數(shù)據(jù)x=(x^{(1)},x^{(2)},...x^{(m)})，聯(lián)合分布p(x,z ;\theta)，條件分布p(z|x; \theta)，最大迭代次數(shù)J

1）隨機(jī)初始化模型參數(shù)\theta的初值\theta^0。

2）for \ j \ from \ 1 \ to \ J：

? a） E步。計(jì)算聯(lián)合分布的條件概率期望：
Q_i(z^{(i)}) = P( z^{(i)}|x^{(i)}, \theta^{j})

L(\theta, \theta^{j}) = \sum\limits_{i=1}^m\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}, \theta^{j})log{P(x^{(i)}, z^{(i)};\theta)}

? b） M步。極大化L(\theta, \theta^{j})，得到\theta^{j+1}:
\theta^{j+1} = \mathop{\arg\max}_\theta L(\theta, \theta^{j})
? c） 如果\theta^{j+1}收斂，則算法結(jié)束。否則繼續(xù)回到步驟a）進(jìn)行E步迭代。

輸出：模型參數(shù)\theta?。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容