Quelle est la différence entre EM et Gradient Ascent?

Quelle est la différence entre les algorithmes EM (Expectation Maximization) et Gradient Ascent (or descente)? Y a-t-il une condition sous laquelle ils sont équivalents?

gradient-descent expectation-maximization Aslan986
la source

Réponses:

De:

Xu L et Jordan MI (1996). Sur les propriétés de convergence de l'algorithme EM pour les mélanges gaussiens . Calcul neuronal 2: 129-151.

Abstrait:

Nous montrons que l'étape EM dans l'espace des paramètres est obtenue à partir du gradient via une matrice de projection P, et nous fournissons une expression explicite pour la matrice.

Page 2

En particulier, nous montrons que l'étape EM peut être obtenue en pré-multipliant le gradient par une matrice de dénit positive. Nous fournissons une expression explicite pour la matrice ...

Page 3

Autrement dit, l'algorithme EM peut être considéré comme un algorithme de montée à gradient métrique variable ...

Autrement dit, l'article fournit des transformations explicites de l'algorithme EM en ascension en gradient, Newton, quasi-Newton.

De wikipedia

Il existe d'autres méthodes pour trouver des estimations du maximum de vraisemblance, telles que la descente de gradient, le gradient conjugué ou les variations de la méthode de Gauss – Newton. Contrairement à l'EM, ces méthodes nécessitent généralement l'évaluation des dérivées premières et / ou secondes de la fonction de vraisemblance.

Ron Coleman
la source

Cette réponse semble suggérer que l'EM et la descente de gradient sont fondamentalement le même algorithme, avec des transformations disponibles pour passer d'un algorithme à l'autre. Ce n'est certainement pas vrai en général et dépend fortement du modèle génératif pris en considération. L'article cité ne tire des conclusions que pour les modèles de mélange gaussiens (qui sont des modèles génératifs relativement simples), et à juste titre. D'après mon expérience (certes limitée), lorsque le modèle est hautement non linéaire et que le rôle des variables latentes est important, l'EM est le seul moyen de dériver des règles de mise à jour sensées.

bleu

Non, ils ne sont pas équivalents. En particulier, la convergence EM est beaucoup plus lente.

Si vous êtes intéressé par un point de vue d'optimisation sur EM, dans cet article, vous verrez que l'algorithme EM est un cas particulier d'une classe plus large d'algorithmes (algorithmes de point proximal).

Elvis
la source

Ou pour une idée similaire, Hinton et Neal (1998)

conjugateprior

"La convergence EM est beaucoup plus lente"; ce n'est pas bien défini, et certainement pas généralement vrai. Les algorithmes EM sont une classe entière d'algorithmes. Pour de nombreux problèmes, un certain algorithme EM est l' état de l'art.

Cliff AB

@CliffAB, n'hésitez pas à en dire plus, j'aimerais lire vos arguments - en lisant cette réponse depuis 4 ans, je me rends compte que je ne répondrais pas à cela aujourd'hui. Depuis lors, j'ai découvert que dans de nombreux cas, l'EM est une ascension en gradient avec un paramètre de `` vitesse d'apprentissage '' en fonction du point actuel ... (je peux modifier cette réponse dans un certain temps pour pointer les résultats du genre)

Elvis

Une "convergence plus lente" pourrait être définie en termes de taux de convergence. Le taux de convergence d'une ascension en gradient dépendra du «taux d'apprentissage», qui n'est pas facile à choisir, ce qui rend l'ascension en gradient difficile dans de nombreux cas. Cependant, j'ai toujours le sentiment que même si l'EM peut être dans certains cas le seul algorithme réalisable (les dérivées de la probabilité ou la probabilité elle-même étant difficile à calculer), son taux de convergence est faible, par rapport à une méthode de type Newton.

Elvis

"L'algorithme EM est en réalité une classe entière d'algorithmes; celui dans lequel la fonction cible d'origine est difficile à optimiser, mais si une autre variable était connue, la solution serait beaucoup plus facile (généralement sous forme fermée). Le schéma de base consiste à remplir la variable attendue en fonction des valeurs actuelles des autres paramètres, puis à mettre à jour les paramètres en fonction de la valeur attendue de la variable. Il a été démontré que la vitesse à laquelle l'algorithme converge dépend de la valeur informative des données imputées; plus les données manquantes sont «informatives», plus la convergence est lente.

Cliff AB