E-M (Expectation-Maximization) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

L’algorithme Expectation-Maximization (E-M) est une méthode itérative d’estimation statistique conçue pour les modèles probabilistes comportant des variables latentes (non observées) ou des données manquantes. Il fonctionne en alternant deux phases : l’étape E (Espérance), qui calcule les espérances des variables latentes conditionnellement aux données observées et aux paramètres courants ; et l’étape M (Maximisation), qui met à jour les paramètres en maximisant l’espérance de la log-vraisemblance complète. Chaque itération garantit une augmentation (ou stabilité) de la vraisemblance, conduisant à une convergence vers un maximum local. Cet algorithme est au cœur des Gaussian Mixture Models (GMM), des modèles de Markov cachés, de l’analyse factorielle probabiliste, et de nombreux autres modèles en apprentissage non supervisé.

Principe mathématique

L’algorithme E-M résout un problème fondamental : comment estimer les paramètres θ d’un modèle probabiliste p(x, z | θ) lorsque les variables latentes z ne sont pas observées ?

La log-vraisemblance incomplète

Étant donné un ensemble de données observées X = {x₁, x₂, …, xₙ}, l’objectif est de maximiser la log-vraisemblance incomplète :

L(θ) = log p(X | θ) = log Σ_z p(X, z | θ)

Le problème est que la somme sur les variables latentes z se trouve à l’intérieur du logarithme, ce qui rend l’optimisation directe très difficile : la dérivée du logarithme d’une somme n’admet généralement pas de solution analytique fermée.

La borne inférieure ELBO

L’idée clé de l’algorithme E-M est de transformer ce problème en optimisant une borne inférieure de la log-vraisemblance, appelée ELBO (Evidence Lower BOund) ou borne de Jensen :

ELBO(q, θ) = Σ_z q(z) log(p(X, z | θ) / q(z))

où q(z) est une distribution auxiliaire sur les variables latentes. Par la convexité du logarithme et l’inégalité de Jensen, on a :

L(θ) ≥ ELBO(q, θ)

Cette borne est serrée (égalité atteinte) lorsque q(z) = p(z | X, θ), c’est-à-dire lorsque q est exactement la distribution postérieure des variables latentes.

L’étape E (Espérance)

À l’itération t, avec les paramètres courants θ_t₋₁, on fixe q(z) à la distribution postérieure des variables latentes :

q(z) = p(z | X, θ_t₋₁)

Ce choix rend la borne ELBO égale à la log-vraisemblance incomplète L(θ_t₋₁). On calcule donc les espérances des variables latentes (ou de fonctions suffisantes de ces variables) sous cette distribution postérieure et on les « gèle ».

L’étape M (Maximisation)

Ensuite, on met à jour les paramètres en maximisant la borne ELBO par rapport à θ, en gardant q(z) fixée :

θt = argmaxθ ELBO(q, θ)

Comme q a été choisie pour rendre la borne serrée à θ_t₋₁, et qu’on maximise ensuite cette borne, on obtient nécessairement :

L(θ_t) ≥ L(θ_t₋₁)

Convergence garantie

Chaque itération E-M augmente monotoniquement la log-vraisemblance incomplète. Comme cette dernière est bornée supérieurement, l’algorithme converge vers un point stationnaire, typiquement un maximum local. Cette convergence est garantie mais ne garantit pas l’optimum global : plusieurs redémarrages avec initialisations différentes sont nécessaires pour atténuer ce risque.

Intuition : le puzzle aux pièces invisibles

Imaginez un puzzle dont vous ne voyez que des morceaux épars, sans l’image du modèle ; vous savez qu’il existe une image cohérente, mais vous ignorez quel morceau appartient à quelle région.

L’algorithme E-M fonctionne exactement comme cette démarche :

Étape E — Deviner : pour chaque morceau, on estime la probabilité qu’il appartienne à chaque région possible. On ne prend pas de décision ferme ; on fait des suppositions pondérées en fonction de ce qu’on sait pour l’instant. C’est l’espérance.

Étape M — Ajuster : en utilisant toutes ces suppositions ensemble, on recalcule la meilleure image globale possible ; quelles sont les caractéristiques de chaque région ? où se situent leurs centres ? comment sont-elles dispersées ? C’est la maximisation.

Répéter : une fois l’image mise à jour, on revient à l’étape E avec une meilleure estimation de base, on affine les suppositions, puis on ré-ajuste l’image. Cycle après cycle, le puzzle s’assemble de plus en plus précisément.

Cette alternance entre incertitude maîtrisée (E) et décision informée (M) est ce qui rend E-M si puissant : il ne rejette pas l’ambiguïté, il l’exploite.

Implémentation Python avec scikit-learn

L’application la plus courante de l’algorithme E-M en machine learning est le Gaussian Mixture Model (GMM), où les variables latentes sont les affectations de cluster et les paramètres à estimer sont les moyennes, covariances et poids de chaque composante gaussienne.

Simulation de données avec variables latentes

import numpy as np
import matplotlib.pyplot as plt
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs

# Générer des données synthétiques avec 3 groupes latents
X, y_true = make_blobs(
    n_samples=500,
    centers=3,
    cluster_std=[1.0, 1.5, 2.0],
    random_state=42
)

print(f"Données: {X.shape[0]} échantillons, {X.shape[1]} dimensions")
print(f"Vrais labels: {np.bincount(y_true)}")

Ajustement du modèle E-M via GaussianMixture

# Ajustement d’un GMM avec l’algorithme E-M
n_components = 3
gmm = GaussianMixture(
    n_components=n_components,
    covariance_type="full",
    max_iter=200,
    n_init=5,
    random_state=42
)

gmm.fit(X)

# Résultats
print(f"\nConvergence en {gmm.n_iter_} itérations")
print(f"Log-vraisemblance finale: {gmm.score(X):.4f}")
print(f"Poids des composantes: {gmm.weights_}")
print(f"Moyennes:\n{gmm.means_}")

# Prédictions de clusters
y_pred = gmm.predict(X)

Visualisation de la convergence

# Tracer la courbe de convergence de la log-vraisemblance
plt.figure(figsize=(10, 6))
iterations = range(1, gmm.n_iter_ + 1)
plt.plot(iterations, gmm._lower_bound_, "b-o", markersize=4)
plt.xlabel("Itération", fontsize=12)
plt.ylabel("Borne ELBO", fontsize=12)
plt.title("Convergence de l’algorithme E-M (GMM)", fontsize=14)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("em_convergence.png", dpi=150)
plt.show()

Visualisation des clusters et des ellipses de covariance

def plot_gmm_clusters(X, gmm, labels, title):
    fig, ax = plt.subplots(figsize=(10, 6))
    scatter = ax.scatter(X[:, 0], X[:, 1], c=labels, cmap="viridis",
                         s=30, alpha=0.7, edgecolors="white", linewidth=0.5)

    # Dessiner les ellipses de covariance
    from matplotlib.patches import Ellipse
    for i in range(gmm.n_components):
        cov = gmm.covariances_[i]
        mean = gmm.means_[i]
        weight = gmm.weights_[i]

        # Calcul des valeurs/vecteurs propres pour l’ellipse
        eigenvalues, eigenvectors = np.linalg.eigh(cov)
        angle = np.arctan2(eigenvectors[1, 0], eigenvectors[0, 0])
        angle = 180 * angle / np.pi

        # Ellipse à 2σ (~95% de probabilité)
        width, height = 2 * np.sqrt(eigenvalues)
        ellipse = Ellipse(xy=mean, width=4*width, height=4*height,
                          angle=angle, alpha=0.2,
                          edgecolor="black", linewidth=1.5,
                          facecolor=f"C{i}")
        ax.add_patch(ellipse)
        ax.plot(mean[0], mean[1], "k+", markersize=15,
                markeredgewidth=2)

    ax.set_xlabel("X₁", fontsize=12)
    ax.set_ylabel("X₂", fontsize=12)
    ax.set_title(title, fontsize=14)
    plt.tight_layout()
    plt.savefig("em_clusters.png", dpi=150)
    plt.show()

# Afficher les résultats
plot_gmm_clusters(X, gmm, y_pred,
                  "Clustering GMM par algorithme E-M")

Probabilités postérieures (affectations douces)

Contrairement au K-Means qui attribue chaque point à un seul cluster (affectation dure), GMM fournit des probabilités postérieures pour chaque point ; c’est l’essence même de l’affectation douce issue de l’étape E :

# Probabilités postérieures (affectation douce)
posteriors = gmm.predict_proba(X)
print("\nExemple de probabilités postérieures pour 5 points:")
print(posteriors[:5])

# Points ambigus (probabilité maximale < 0.8)
max_prob = posteriors.max(axis=1)
ambiguous = np.sum(max_prob < 0.8)
print(f"\nPoints ambigus (confiance < 80%): {ambiguous}/{len(X)}")

Hyperparamètres clés

Le choix des hyperparamètres influence fortement le comportement de l’algorithme E-M :

Sélection du nombre de composantes

L’algorithme E-M ne détermine pas automatiquement le nombre de composantes. On utilise généralement le critère d’information bayésien (BIC) ou le critère d’information d’Akaike (AIC) :

# Sélection du nombre optimal de composantes via BIC
bic_scores = []
aic_scores = []
n_range = range(1, 8)

for k in n_range:
    gmm_temp = GaussianMixture(n_components=k, random_state=42)
    gmm_temp.fit(X)
    bic_scores.append(gmm_temp.bic(X))
    aic_scores.append(gmm_temp.aic(X))

# Le meilleur k minimise le BIC
best_k_bic = n_range[np.argmin(bic_scores)]
print(f"Nombre optimal de composantes (BIC): {best_k_bic}")

Avantages et limites

Avantages

• Gestion naturelle de l’incertitude : contrairement aux algorithmes d’affectation dure comme k-means, E-M fournit des probabilités postérieures pour chaque affectation, permettant de quantifier l’ambiguïté de chaque point.
• Clusters ovales : avec une covariance complète, GMM peut modéliser des clusters elliptiques orientés, là où k-means ne trouve que des sphères.
• Convergence garantie : la log-vraisemblance augmente monotônement à chaque itération, contrairement à des algorithmes comme k-means qui peuvent osciller.
• Généricité remarquable : E-M est un cadre général ; il s’applique bien au-delà des GMM ; modèles de Markov cachés (algorithme de Baum-Welch), analyse factorielle, mélange de distributions, et même des problèmes de données manquantes.
• Fondation probabiliste solide : chaque étape a une interprétation statistique claire, permettant des dérivations rigoureuses et des généralisations.

Limites

• Sensibilité à l’initialisation : E-M converge vers un maximum local, qui peut être très éloigné de l’optimum global. Un mauvais départ mène à de mauvais résultats.
• Convergence parfois lente : dans certaines configurations, la progression de la log-vraisemblance est extrêmement lente dans les dernières itérations (convergence linéaire).
• Nécessité de connaître k : le nombre de composantes doit être spécifié à priori ou sélectionné par validation.
• Sensibilité aux outliers : une distribution gaussienne a des queues légères ; les valeurs aberrantes peuvent biaiser l’estimation des paramètres.
• Malédiction de la dimensionnalité : avec « covariance_type=full », le nombre de paramètres croît quadratiquement avec la dimension, ce qui peut nécessiter des régularisations.

4 cas d’usage concrets

1. Clustering probabiliste en biologie

En génomique, E-M permet de regrouper des cellules ou des gènes selon leur profil d’expression. Les probabilités postérieures identifient les cellules de transition ; celles qui appartiennent également à plusieurs clusters, reflétant des états biologiques intermédiaires dans des processus comme la différenciation cellulaire.

2. Imputation de données manquantes

Lorsque des valeurs sont manquantes dans un jeu de données, on peut les traiter comme des variables latentes. L’étape E estime les valeurs manquantes conditionnellement aux valeurs observées ; l’étape M met à jour les paramètres du modèle. Cette approche est supérieure à la simple imputation par la moyenne car elle préserve la structure de covariance.

3. Séparation de sources audio

Dans un enregistrement où plusieurs personnes parlent simultanément, chaque source est une composante latente. E-M peut estimer les paramètres spectraux de chaque source et les séparer en attribuant chaque échantillon de fréquence-temporelle à la source la plus probable. C’est le principe derrière les algorithmes de résolution du problème du cocktail party.

4. Modèles de Markov cachés (HMM)

L’algorithme de Baum-Welch, utilisé pour l’apprentissage des HMM, est un cas particulier d’E-M : l’étape E calcule les probabilités des états cachés via l’algorithme forward-backward, et l’étape M met à jour les probabilités de transition et d’émission. Applications ; reconnaissance de la parole, annotation de séquences génomiques (gènes vs. non-gènes), analyse du langage naturel.

Voir aussi

• Implémentation de l’Algorithme de Cramer et Calcul de Déterminant en Python
• Optimisez Votre Code Python avec SOP et POS : Guide Complet pour les Débutants