EM Algorithm EM算法

---

EM algorithm is a iterative optimazation algorithm. EM is the abbreviation of expectation maximization. EM do not apply for all the optimization problems.

Remember! EM always converge but it can be a local optima.

EM applys for GMM, K-Means clustering, HMM, etc.

Jensen’s Inequality

convex function $f, f'' > 0$f,f′′>0; concave function $f, f''<0$f,f′′<0
$E[f(x)] \geq f(E[x]) \ \ \ \ \ f$E[f(x)]≥f(E[x])     f is convex
$E[f(x)] \leq f(E[x]) \ \ \ \ \ f$E[f(x)]≤f(E[x])     f is concave
If and only if $x$x is constant equal sign is taken.
图片来源

EM

$\{z_i\}_{i=1\sim N}${zi​}i=1∼N​ — $x_i$xi​ belongs to $(z_i)^{th}$(zi​)th distribution
$Q_i(z_i)$Qi​(zi​) — the probability distribution of $z_i$zi​
(You can also turn $z_i$zi​ into a vector and each dimension represents the probability.)

---

MLE:
$l(\theta) = \sum\limits_{i=1}^N\log[\sum\limits_{z_i} P(x_i,z_i|\theta)]$l(θ)=i=1∑N​log[zi​∑​P(xi​,zi​∣θ)]

---

$\theta_i$θi​ — the parameter of $i^{th}$ith iteration

$randomize \ \theta_0 \\ while (!converge) \\ \{ \\ \ \ \ \ \ \ \ \ E-step: \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Q_i(z_i) = \frac{P(x_i, z_i|\theta_k)}{\sum\limits_{z_i} P(x_i,z_i|\theta_k)} \\ \ \ \ \ \ \ \ \ M-step: \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \theta_{k+1} = \arg\max\limits_{\theta}\sum\limits_{i=1}^N\sum\limits_{z_i} Q_i(z_i)\log \frac{P(x_i,z_i|\theta)}{Q_i(z_i)}\\ \}$randomize θ0​while(!converge){        E−step:                 Qi​(zi​)=zi​∑​P(xi​,zi​∣θk​)P(xi​,zi​∣θk​)​        M−step:                 θk+1​=argθmax​i=1∑N​zi​∑​Qi​(zi​)logQi​(zi​)P(xi​,zi​∣θ)​}

Jensen’s inequality applys in M-step and the prove of convergence. More details