Comprendre Espérance–Maximisation
Apprendre un modèle probabiliste à partir de données complètes est direct : la log-vraisemblance se décompose en un terme par paramètre, chaque dérivée partielle peut être annulée indépendamment, et chaque estimation se révèle être un rapport d’effectifs. La difficulté surgit quand certaines des variables figurant dans ces effectifs ne sont jamais observées - de quel groupe vient un point, quel thème a engendré un document, dans quel état se trouvait un processus.
EM transforme les effectifs manquants en effectifs espérés. À l’étape E, les paramètres courants servent à calculer, pour chaque exemple, la loi a posteriori des variables cachées ; l’appartenance fractionnaire ainsi attribuée s’appelle une responsabilité. À l’étape M, on applique telles quelles les formules du maximum de vraisemblance à données complètes, chaque effectif étant remplacé par une somme de responsabilités. Les deux étapes alternent jusqu’à ce que la log-vraisemblance cesse de bouger.
La garantie qui fait fonctionner tout cela est que chaque itération maximise une borne inférieure de la log-vraisemblance, borne qui la touche aux paramètres courants. Améliorer la borne ne peut donc pas dégrader la vraisemblance. L’invariant est véritablement utile à l’implémentation : si la log-vraisemblance baisse, le code est faux et non malchanceux.
Ce qui n’est pas garanti, c’est le maximum global. Des initialisations différentes convergent vers des points fixes différents, dont certains sont bien pires que d’autres ; le remède habituel consiste en quelques relances aléatoires dont on conserve l’ajustement de plus haute vraisemblance. Des solutions dégénérées sont également possibles - une composante du mélange peut se replier sur un point unique et faire tendre sa variance vers zéro, envoyant la vraisemblance à l’infini - ce qui explique pourquoi les implémentations imposent un plancher à la variance.
L’algorithme dépasse de loin le partitionnement. Apprendre les paramètres d’un réseau bayésien à nœuds cachés, apprendre les modèles de transition et de capteur d’un modèle de Markov caché à partir des seules observations (où l’étape E est exactement le lissage avant-arrière), et ajuster les modèles à variables latentes dans toute la statistique sont autant d’instances des deux mêmes étapes.
Comment calculer
θ⁽ⁱ⁺¹⁾ = argmax_θ Σ_z P(Z = z | x, θ⁽ⁱ⁾) · L(x, Z = z | θ)
où
- x
- toutes les valeurs observées, sur l’ensemble des exemples
- Z
- toutes les variables cachées, sur l’ensemble des exemples
- θ⁽ⁱ⁾
- les estimations des paramètres après i itérations
- P(Z = z | x, θ⁽ⁱ⁾)
- l’étape E : la loi a posteriori des variables cachées sous l’ajustement courant
- L(x, Z = z | θ)
- la log-vraisemblance des données complétées, maximisée à l’étape M
Exemple : Espérance–Maximisation
Prenez vingt points sur une droite, huit tirés d’un groupe étroit près de zéro et douze d’un groupe large près de cinq, les étiquettes étant retirées. Partant de la supposition grossière que les moyennes valent 0 et 5 et que les deux écarts-types valent 1, EM converge en 82 itérations, faisant croître la log-vraisemblance de façon monotone de −56,616239 à −46,633131 et s’arrêtant sur des poids 0,347288 et 0,652712, des moyennes 0,128189 et 4,581627, et des écarts-types 0,731077 et 2,367312.
Ces paramètres retrouvent exactement les étiquettes retirées. La coupure optimale du k-moyennes sur les mêmes données n’y parvient pas : elle place x = 1,7 dans le groupe étroit, puisque 1,7 se trouve à 1,571811 de la moyenne étroite et à 2,881627 de la large. EM compare des densités et non des distances, et la composante large est 3,24 fois plus étalée tout en portant le poids le plus lourd : elle emporte donc une responsabilité de 0,736211 sur ce point.
Les relances comptent. Sur 400 initialisations aléatoires de ces données, 385 ont atteint −46,633131 et les 15 restantes se sont arrêtées à −48,277387 - un ajustement franchement moins bon dont aucune itération supplémentaire ne permet de sortir.
Questions fréquentes
En quoi EM diffère-t-il du k-moyennes ?
Le k-moyennes affecte chaque point en entier à un groupe et compare des distances euclidiennes ; EM attribue des responsabilités fractionnaires et compare des densités pondérées, ce qui lui permet de tenir compte de composantes de largeurs et de tailles différentes. Le k-moyennes est à peu près le cas limite d’EM sur un mélange à variances sphériques égales et décroissantes.
Comment décide-t-on de la convergence ?
Le plus souvent en surveillant la log-vraisemblance et en s’arrêtant quand la variation entre itérations passe sous une tolérance. Comme la suite est croissante et majorée dans les problèmes bien posés, ce test se comporte bien ; la variation des paramètres sert parfois de critère complémentaire.
EM trouve-t-il le bon nombre de composantes ?
Non. Le nombre de composantes du mélange est fixé avant l’ajustement, exactement comme k dans le k-moyennes. Le choisir exige un critère de sélection de modèle tel que le BIC ou la vraisemblance validée croisée, car la log-vraisemblance seule s’améliore toujours quand on ajoute des composantes.
En résumé
EM est ce que devient le maximum de vraisemblance quand les effectifs ne peuvent pas être relevés : devinez-les à partir du modèle courant, réajustez, recommencez. La vraisemblance ne baisse jamais, ce qui rend l’algorithme facile à croire et facile à déboguer, mais il ne trouve jamais qu’un maximum local : relancez-le et gardez le meilleur ajustement.