L'algorithme EM

pour maximiser une vraisemblance difficile, on monte une borne inférieure facile, et on recommence

1 · CRITÈRE ET BORNE DE JENSEN

$$\ell(\theta)=\sum_{i=1}^{n}\log\sum_{k=1}^{2}\pi_k\,\varphi(x_i;\mu_k,\sigma_k) \;\ge\;Q(\theta\mid\theta^{(q)})+H^{(q)}$$

$$Q(\theta\mid\theta^{(q)})=\sum_{i,k}t^{(q)}_{ik}\log\big(\pi_k\,\varphi(x_i;\mu_k,\sigma_k)\big), \qquad H^{(q)}=-\sum_{i,k}t^{(q)}_{ik}\log t^{(q)}_{ik}\ \ \text{(ne dépend pas de }\theta)$$

$$\textbf{E : }\ t^{(q)}_{ik}=\frac{\pi_k\varphi(x_i;\mu_k,\sigma_k)}{\sum_l\pi_l\varphi(x_i;\mu_l,\sigma_l)}\ \text{ (égalité en } \theta^{(q)}) \qquad \textbf{M : }\ \theta^{(q+1)}=\arg\max_\theta Q(\theta\mid\theta^{(q)})$$

2 · À TOI : PLACE LES CENTRES DE DÉPART, PUIS ITÈRE

données sur la droite, colorées par leur responsabilité $t_{i2}$ — tire les triangles pour placer $\mu_1$, $\mu_2$ initiaux

critère le long du pas $\theta^{(q)}\to\theta^{(q+1)}$ : $\ell$ (noir) et borne $Q(\cdot\mid\theta^{(q)})+H^{(q)}$ (bleu)

$\ell(\theta^{(q)})$ au fil des itérations

écart $\delta$ proportion $\pi_2$

Une étape E suivie d'une étape M forment une itération. Dans le panneau de gauche, l'abscisse $\tau$ parcourt la droite $\theta^{(q)}+\tau(\theta^{(q+1)}-\theta^{(q)})$ (en $\operatorname{logit}\pi$ et $\log\sigma$) : $\tau=0$ est $\theta^{(q)}$, $\tau=1$ est $\theta^{(q+1)}$.

3 · RAPPELS

Le logarithme d'une somme n'a pas de maximum explicite. Jensen (log concave) donne $$\log\sum_k t_{ik}\frac{a_{ik}}{t_{ik}}\;\ge\;\sum_k t_{ik}\log\frac{a_{ik}}{t_{ik}}\,;$$ la borne $Q+H$ se maximise en forme close (seul $Q$ dépend de $\theta$).
Identité clé : $\ell(\theta)=Q(\theta\mid\theta^{(q)})+H^{(q)}+\sum_i\mathrm{KL}\big(t^{(q)}_i\,\|\,p(z_i\mid x_i,\theta)\big)$. Le KL est nul en $\theta=\theta^{(q)}$ (borne tangente), l'étape M fait monter $Q$, donc $\ell(\theta^{(q+1)})\ge Q(\theta^{(q+1)}\mid\theta^{(q)})+H^{(q)}\ge Q(\theta^{(q)}\mid\theta^{(q)})+H^{(q)}=\ell(\theta^{(q)})$.
Étape M explicite : $n_k=\sum_i t_{ik}$, $\pi_k=n_k/n$, $\mu_k=\frac1{n_k}\sum_i t_{ik}x_i$, $\sigma_k^2=\frac1{n_k}\sum_i t_{ik}(x_i-\mu_k)^2$.
EM converge vers un point stationnaire, souvent un maximum local : le départ compte. La vraisemblance n'est pas bornée (une composante qui se resserre sur un seul point, $\sigma_k\to0$).
Lien avec les k-means : variances égales qui tendent vers 0, responsabilités qui deviennent 0 ou 1, et EM devient l'algorithme de Lloyd.