machine learning - Expectation-maximization algorithm (EM) (機器學習 - 最大期望演算法)

◎作用

是在機率模型中尋找依賴不可觀察的變量(Observed Variable)的參數最大似然估計(Maximum Likelihood) 以及 最大後驗(posterior)估計的算法

◎前置資訊

• 期望值 : 輸出 X 機率的總和 ，離散資料為$\sum_{i}^{} \mathbf{p}_{i}\mathbf{x}_{i}$，連續資料為$\int_{}^{} \mathbf{x}f(x) \text{d}x$
• jensen不等式 : 若 f 為 凹函數 ，則 $f(\sum_{i}^{}\lambda_i x_i) \geq \sum_{i}^{}\lambda_if( x_i)$，log屬於凹函數

由log圖可以發現
若 p介於0到1
$f[(1-p)x + py]$是在log線上移動
$(1-p)f(x)+ pf(y)$在直線上移動
因此
$f[(1-p)x + py] \geq (1-p)f(x)+ pf(y)$
Note: 當x與y 兩點相等(重疊)，等號成立

◎簡述

假設Maximum Likelihood
$\mathfrak{L}(\Theta) = \sum_{i=1}^{m}\log P(x_{i};\Theta)$
強制z(latent variable)取出，如果x為身高分布，那麼z可以為性別
$ = \sum_{i}^{}\log \sum_{z^{i}}^{}P(x^{i},z^{i};\Theta)$
在分子分母中加入z的機率分布Q(期望Exceptation)，原式不變
$ = \sum_{i}^{}\log \sum_{z^{i}}^{}Q(z^{i})\frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$
利用jensen不等式
$ \geq \sum_{i}^{} \sum_{z^{i}}^{}Q(z^{i}) log \frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$
利用jensen不等式那張圖，想像$\frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$ 在x軸上有的2個值

而$Q(z^{i})$則介於0到1之間的值，控制2點間直線間移動
因此$log \ Q(z^{i})\frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$為2點直線移動取值後，對其值做log (黑色箭頭所指)
而$Q(z^{i}) log \ \frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$，取log後在直線移動取值(藍點)
因此為了要不等式相等，必須讓$\frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$為常數(2點相等重疊)，
$\frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})} = c$
得到正比資訊，且Q機率相加必須等於1
$Q(z^{i})\propto P(x^{i},z^{i};\Theta) and \sum_{i}^{}Q(z^{i})=1$
經過貝式定理，得到Q為
$Q(z^{i}) = \frac{P(x^{i},z^{i};\Theta)}{\sum_{z}^{}P(x^{i},z;\Theta)} = \frac{P(x^{i},z^{i};\Theta)}{P(x^{i};\Theta)}=P(z^{i}|x^{i};\Theta)$

◎EM簡述

E : 依據上次的參數，或者初始值，對所有i，求Q
$Q(z^{i})=P(z^{i}|x^{i};\Theta)$
M : 固定Q，求可以使L最大的新參數值 $ \Theta = arg\max_{\Theta}\sum_{i}^{} \sum_{z^{i}}^{}Q(z^{i}) log \frac{P(x^{i},z^{i};\Theta)}{Q(z^{i})}$
不斷迭代EM，直到收斂(convergence)