機(jī)器學(xué)習(xí)算法深度總結(jié)(9)-EM算法

概率模型有時既有觀測變量, 又有隱變量, 當(dāng)存在隱變量時, 直接的最大似然估計(jì)無法直接搞定零院。
EM算法是一種迭代算法, 對于含有隱變量(hidden variable)的概率模型參數(shù)的極大似然估計(jì)或極大后驗(yàn)概率估計(jì).
EM算法每次迭代分兩步: E步, 求期望; M步, 求極大; 因此EM算法稱為期望極大算法.

最經(jīng)典的例子就是拋3個硬幣:

假設(shè)三枚硬幣, 分別記作A,B,C裕偿，正面出現(xiàn)的概率分別為 $\pi, p, q$ . ,拋A硬幣決定B和C(A正面, 選B; A反面, 選C), 然后拋B或者C決定正反面, 正面記1, 反面記0; 然后估算3個硬幣的正反面概率值崖媚。

下面對著三枚硬幣建模模型:
$\begin{align*} P(y|\theta) &= \sum_z P(y,z|\theta) = \sum_z P(z|\theta)P(y|z,\theta) \\ &= \pi p^y(1-p)^{1-y} + (1-\pi)q^y(1-q)^{1-y} \ \ (1) \end{align*}$
上式, 隨機(jī)變量y是觀測變量, 一次試驗(yàn)最終結(jié)果是1, 則y=1; 否則, y=0; 隨機(jī)變量z是隱變量, 表示中間為觀測到的擲硬幣A的結(jié)果; $\theta=(\pi, p, q)$ 是模型參數(shù), 這模型是以上數(shù)據(jù)的生成模型.

注意: 對隱變量的理解是理解EM算法的第一要義, 這里, 隨機(jī)變量y的數(shù)據(jù)可以觀測, 但是隨機(jī)變量z的數(shù)據(jù)不可觀測.

我們可以簡單的來核對一下這個概率模型寫得對不對。我們畫出一次拋擲硬幣的整個過程塑顺，并計(jì)算出相應(yīng)的概率汤求。然后帶入到上面的公式中就可以知道模型構(gòu)建是否正確了。

case	A(z)	B	C	prob
1	1	1	-	$\pi * p$
2	1	0	-	$\pi * (1-p)$
3	0	-	1	$(1-\pi)*q$
4	0	-	0	$(1-\pi)*(1-q)$

分析:

試驗(yàn)結(jié)果為1
根據(jù)上表, 有 $P(y=1) = P(case1)+P(case3) = \pi * p + (1-\pi)*q$
同時, y=1帶入上式(1), 有:
$P(y=1|\theta) =\pi p^1(1-p)^{1-1} + (1-\pi)q^1(1-q)^{1-1} = \pi p + (1-\pi)q$
試驗(yàn)結(jié)果為0
根據(jù)上表, 有 $P(y=0) = P(case2)+P(case4) = \pi * (1-p) + (1-\pi)*(1-q)$
同時, y=1帶入上式(1), 有:
$P(y=0|\theta) =\pi p^0(1-p)^{1-0} + (1-\pi)q^0(1-q)^{1-0} = \pi * (1-p) + (1-\pi)*(1-q)$
可見, 公式(1)符合實(shí)際實(shí)驗(yàn)結(jié)果.

用極大似然估計(jì)求參數(shù) $\theta$ :
觀測數(shù)據(jù) $Y=(Y_1,\cdots,Y_n)^T$ , 為觀測數(shù)據(jù) $Z=(Z_1,\cdots,Z_n)^T$ , 則觀測數(shù)據(jù)的似然函數(shù)為:
$P(Y|\theta) = \sum_Z P(Z|\theta)P(Y|Z,\theta)$
即,
$P(Y|\theta) = \prod_{j=1}^n[ \pi p^{y_j}(1-p)^{1-y_j} + (1-\pi)q^{y_j}(1-q)^{1-y_j}]$
考慮求模型參數(shù) $\theta=(\pi, p, q)$ 的極大似然估計(jì):
$\hat \theta = \arg \underset{\theta}{\max} \log P(Y|\theta)$
該問題沒有解析解, 只能通過迭代的方法求解, EM算法便是可求解這一問題的一種迭代算法.

一般地, 用Y表示觀測變量的數(shù)據(jù), Z表示隱變量的數(shù)據(jù), Y和Z連在一起稱為完全數(shù)據(jù), 觀測數(shù)據(jù)Y又稱不完全數(shù)據(jù).

不完全數(shù)據(jù)Y的概率分布是 $P(Y|\theta)$ , 對數(shù)似然函數(shù) $L(\theta) = \log P(Y|\theta)$
完全數(shù)據(jù)Y和Z的聯(lián)合概率分布 $P(Y,Z|\theta)$ , 對數(shù)似然函數(shù)是 $\log P(Y,Z|\theta)$

EM算法通過迭代求 $L(\theta) = \log P(Y|\theta)$ 的極大似然估計(jì), 每次迭代先求E(期望), 后求M(極大化).

Q函數(shù):

完全數(shù)據(jù)的對數(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)}]$

EM算法:
輸入: 觀測變量數(shù)據(jù), 隱變量數(shù)據(jù)Z, 二者聯(lián)合分布 $P(Y,Z|\theta)$ , 條件分布 $P(Z|Y,\theta)$
輸出: 模型參數(shù) $\theta$

(1) 選擇參數(shù)的初值 $\theta^{(0)}$ , 開始迭代
注意: EM算法對初始值敏感, 不同的初值可能得到不同的參數(shù)估計(jì)值
(2) E步: 第i+1次迭代的E步, 計(jì)算:
$\begin{align*} Q(\theta, \theta^{(i)}) &= E_Z[\log P(Y,Z|\theta) | Y, \theta^{(i)}] \\ &=\sum_Z\log P(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{align*}$
這里 , $Q^{(i)}$ 是第i次迭代參數(shù) $\theta$ 的估計(jì)值, $P(Z|Y, \theta^{(i)})$ 是在觀測數(shù)據(jù)Y和當(dāng)前參數(shù)估計(jì) $\theta^{(i)}$ 下隱變量數(shù)據(jù)Z的條件概率分布
(3)M步: 求使 $Q(\theta, \theta^{(i)})$ 極大化的 $\theta$ , 確定第i+1次迭代的參數(shù)估計(jì)值 $\theta^{(i+1)}$ , 完成一次迭代 $\theta^{(i)} \rightarrow \theta^{(i+1)}$ :
$\theta^{(i+1)} = \arg \underset{\theta}{\max} Q(\theta, \theta^{(i)})$
每次迭代使似然函數(shù)增大或達(dá)到局部極值.
(4) 重復(fù)(2)(3)步, 直到收斂.
迭代終止條件, 一般是對較小的 $\epsilon_1,\epsilon_2$ , 若滿足:
$\|\theta^{(i+1)}-\theta^{(i)} \| < \epsilon_1 \; \; \text{or} \; \; \| Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)}) \| < \epsilon_2$
則停止迭代.