Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme espérance-maximisation
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.