Expectation maximization

January 20, 2018

Definition: MLE(or MAP) when some data is missing or hidden

Given: $x=(x_1, …, x_n)$ observed

Model: $X,Z \sim P_{\theta}$ for some (unknown) $\theta \in \Theta$ , $P_\theta$ usually a type of exponential family. X表示观测变量数据，Z表示隐藏变量数据。X和Z在一起表示完全数据(complete-data), 单独X表示不完全数据(incomplete-data)

Goal: $\theta_{MLE} \in \underset{\theta}{\operatorname{argmax}} P_{\theta}(X)$

Issue: $P_{\theta}(X)=\sum_{z}P_{\theta}(X,Z)$ difficult to maximization. ⊕
比如GMM，难以找到最优解.

Algo:

Initinalize $\theta_0 \in \Theta$
For
- E-step: determine $P(Z \mid X)$ and $Q(\theta, \theta_t) = E_{\theta_t}(log P_{\theta}(X,Z) \mid X=x)=\sum_{z}log P(X,Z)P(Z \mid X)$
- M-step: $\theta_{t+1} \in \underset{\theta}{\operatorname{argmax}} Q(\theta, \theta_t)$ , with $P(Z \mid X)$ fixed

Notes:

Not guaranteed to give $\theta_{MLE}$
Convergence can be slow
MLE may overfit, MAP maybe better

直观解释

假设有A，B两个硬币，这两个硬币扔出正面(head那一面)的概率未知，按下面步骤进行估计。

step 1: 随机选择一个硬币，用选中硬币扔10次，得到一组实验数据序列(比如：H,T,H,T,H,H,T…)
step 2: 上述步骤共做5组。

5组实验选择的硬币已知

whatisem

5组实验选择的硬币未知

whatisem

假设 $x=(1,0,1,1,0,1,...)$ 是观测到的序列(H记为1,T记为0组成的长度为10的序列)，
选硬币A的概率为 $P(z=A)=\pi_1$ ,选硬币B的概率为 $P(z=B)=\pi_2 = 1-\pi_1$
A出现正面的概率为 $\theta_1$ ,B出现正面的概率为 $\theta_2$

则一组实验模型可写作 $P_{\theta}(x)=\sum_{z}P_{\theta}(x,z) =\sum_{z}P(z)P(x \mid z)=\pi_1\theta_{1}^{x}(1-\theta_{1})^{1-x}+\pi_2\theta_{2}^{x}(1-\theta_{2})^{1-x}$

整个实验可以写作 $z_{i}=[1,0]$ 表示第i组实验选择的是A硬币, $z_i=[0,1]$ 表示第i组选择的是B硬币

$\begin{align*}P(X_1, .., X_5,z_1,…,z_5) &=\prod_{i=1}^{5}P(\{x_{i}^1,…,x_{i}^{10}\} \mid z_i)\prod_{i=1}^{5}P(z_i) \\ &=\prod_{i=1}^{5}\prod_{j=1}^{10} P(x_{i}^j \mid z_i)\prod_{i=1}^{5}\prod_{k=1}^{2}\pi_{k}^{z_{ik}} \\ &=\prod_{i=1}^{5}\prod_{j=1}^{10}\prod_{k=1}^{2}[\theta_{k}^{x_{i}^j}(1-\theta_k)^{(1-x_{i}^j)}]^{z_{ik}}\prod_{i=1}^{5}\prod_{k=1}^{2}\pi_{k}^{z_{ik}} \end{align*}$

Initinalize

看公式，参数有3个： $\pi_1,\theta_1,\theta_2$

假设: $\pi_1=0.5;\theta_1=0.6;\theta_2=0.5$

E-step

Determine $P(Z \mid X)$ :

$\begin{align*}P(z_{ik} \mid \{x_{i}^1,…,x_{i}^{10}\}) &= \frac{P(x_i,z_{ik})}{P(x_i)}=\frac{P(z_{ik})P(x_i \mid z_{ik})}{P(x_i)} \\&=\frac{\pi_k\prod_{j=1}^{10}\theta_{k}^{x_{i}^j}(1-\theta_k)^{(1-x_{i}^j)}}{\pi_1\prod_{j=1}^{10}\theta_{1}^{x_{i}^j}(1-\theta_1)^{(1-x_{i}^j)}+\pi_2\prod_{j=1}^{10}\theta_{2}^{x_{i}^j}(1-\theta_2)^{(1-x_{i}^j)}} \end{align*}$

比如对于第一组实验，估计是硬币A的概率为 $P(z_{11} \mid x_1)=\frac{0.5 \times 0.6^{5} \times 0.4^{5}}{0.5 \times 0.6^{5} \times 0.4^{5}+0.5 \times 0.5^{10}}\approx 0.45$

$\begin{align*}Q(\theta, \theta_t) &= E_{\theta_t}(log P_{\theta}(X,Z) \mid X=x) \\ &=\sum_{z}log P(X,Z)P(Z \mid X) \\&=\sum_{i=1}^{5}\sum_{j=1}^{10}\sum_{k=1}^{2}P(z_{ik} \mid x_i)z_{ik}log[\theta_{k}^{x_{i}^j}(1-\theta_k)^{(1-x_{i}^j)}]+\sum_{i=1}^{5}\sum_{k=1}^{2}P(z_{ik} \mid x_i)z_{ik}log(\pi_{k}) \\ &=\sum_{i=1}^{5}\sum_{j=1}^{10}\sum_{k=1}^{2}P(z_{ik} \mid x_i)z_{ik}[{x_{i}^j}log(\theta_{k})+{(1-x_{i}^j)}log(1-\theta_k)]+const\end{align*}$

M-step

对 $Q(\theta, \theta_t)$ 中的参数求导，得到

$\begin{align*} \frac{\partial Q}{ \partial \theta_1}=\sum_{i=1}^{5}\sum_{j=1}^{10}P(z_{i1} \mid x_i)[\frac{x_{i}^j}{\theta_1}-\frac{1-x_{i}^j}{1-\theta_1}]=0\end{align*}$

最终可得到

$\begin{align*}\theta_1=\frac{\sum_{i=1}^{5}\sum_{j=1}^{10}P(z_{i1} \mid x_i)x_{i}^j}{\sum_{i=1}^{5}10 \times P(z_{i1} \mid x_i)} \\ \theta_2=\frac{\sum_{i=1}^{5}\sum_{j=1}^{10}P(z_{i2} \mid x_i)x_{i}^j}{\sum_{i=1}^{5}10 \times P(z_{i2} \mid x_i)} \end{align*}$

比如: $\theta_1=\frac{0.45 \times 5+0.8 \times 9 + 0.73 \times 8 + 0.35 \times 4 + 0.65 \times 7}{0.45 \times 10+0.8 \times 10 + 0.73 \times 10 + 0.35 \times 10 + 0.65 \times 10} \approx 0.71$

Reference

mathematicalmonk:(ML 16.3) Expectation-Maximization (EM) algorithm
What is the expectation maximization algorithm?
李航.《统计学习方法》第九章-EM算法及其推广
Stefanos Zafeiriou Adv. Statistical Machine Learning (course 495)