Algorithme espérance-maximisation

L'algorithme espérance-maximisation (en anglais expectation-maximization algorithm, souvent abrégé EM) est un algorithme itératif qui permet de trouver les paramètres du maximum de vraisemblance d'un modèle probabiliste lorsque ce dernier dépend de variables latentes non observables. Il a été proposé par Dempster et al. en 1977. De nombreuses variantes ont par la suite été proposées, formant une classe entière d'algorithmes. On utilise souvent l'algorithme EM pour la classification de données (clustering, ou partitionnement de données), l'apprentissage automatique, ou la vision artificielle. On peut également citer son utilisation en dans le cadre de la reconstruction tomographique. L'algorithme d'espérance-maximisation consiste à itérer les deux étapes suivantes : étape E : une étape d'évaluation de l'espérance, où l'on calcule l'espérance de la vraisemblance en tenant compte des dernières variables observées, étape M : une étape de maximisation, où l'on estime le maximum de vraisemblance des paramètres en maximisant la vraisemblance trouvée à l'étape E. On utilise à chaque fois les paramètres trouvés en l'étape M comme point de départ d'une nouvelle étape E d'évaluation de l'espérance. Pour résoudre le problème d'apprentissage des modèles de Markov cachés (HMM), c’est-à-dire la détermination des paramètres du modèle markovien, on utilise l'algorithme de Baum-Welch. Considérons un échantillon x = (x , ... , x) d'individus suivant une loi f(x,θ) paramétrée par θ. On cherche à déterminer le paramètre θ maximisant la log-vraisemblance donnée par Cet algorithme est particulièrement utile lorsque la maximisation de L est très complexe mais que, sous réserve de connaître certaines données judicieusement choisies, on peut très simplement déterminer θ. Dans ce cas, on s'appuie sur des données complétées par un vecteur z = (z , ... , z) inconnu. En notant f(z x,θ) la probabilité de z sachant x et le paramètre θ, on peut définir la log-vraisemblance complétée comme la quantité Ainsi, on écrit la log-vraisemblance initiale comme : L'algorithme EM est une procédure itérative basée sur l'espérance des données complétées conditionnellement au paramètre courant.