Pourquoi la maximisation des attentes est importante pour les modèles de mélange?

15

De nombreuses publications mettent l'accent sur la méthode de maximisation des attentes sur les modèles de mélange (mélange de gaussien, modèle de Markov caché, etc.).

Pourquoi l'EM est important? EM est juste un moyen d'optimisation et n'est pas largement utilisé comme méthode basée sur un gradient (gradient décent ou méthode de newton / quasi-newton) ou autre méthode sans gradient discutée ICI . De plus, EM a toujours un problème de minima locaux.

Est-ce parce que le processus est intuitif et peut facilement être transformé en code? Ou quelles autres raisons?

Haitao Du
la source

Réponses:

14

En principe, les approches EM et d'optimisation standard peuvent fonctionner pour ajuster les distributions de mélange. Comme EM, les solveurs d'optimisation convexes convergeront vers un optimum local. Mais, une variété d'algorithmes d'optimisation existent pour rechercher de meilleures solutions en présence de multiples optima locaux. Pour autant que je sache, l'algorithme avec la meilleure vitesse de convergence dépendra du problème.

L'un des avantages de l'EM est qu'il produit naturellement des paramètres valides pour la distribution du mélange à chaque itération. En revanche, les algorithmes d'optimisation standard devraient imposer des contraintes. Par exemple, disons que vous ajustez un modèle de mélange gaussien. Une approche de programmation non linéaire standard exigerait que les matrices de covariance contraignantes soient semi-définies positives, et que les poids des composants du mélange soient non négatifs et additionnés à un.

Pour obtenir de bonnes performances sur des problèmes de grande dimension, un solveur de programmation non linéaire doit généralement exploiter le gradient. Donc, vous devez soit dériver le gradient, soit le calculer avec une différenciation automatique. Les dégradés sont également nécessaires pour les fonctions de contrainte s'ils n'ont pas de forme standard. La méthode de Newton et les approches connexes (par exemple les méthodes de région de confiance) ont également besoin de la Hesse. Une différenciation finie ou des méthodes sans dérivé pourraient être utilisées si le gradient n'est pas disponible, mais les performances ont tendance à mal évoluer à mesure que le nombre de paramètres augmente. En revanche, EM ne nécessite pas le gradient.

EM est conceptuellement intuitif, ce qui est une grande vertu. Cela vaut également pour les approches d'optimisation standard. Il existe de nombreux détails de mise en œuvre, mais le concept global est simple. Il est souvent possible d'utiliser des solveurs d'optimisation standard qui résument ces détails sous le capot. Dans ces cas, un utilisateur n'a qu'à fournir la fonction objective, les contraintes et les gradients, et possède suffisamment de connaissances pratiques pour sélectionner un solveur bien adapté au problème. Mais, des connaissances spécialisées sont certainement nécessaires si elles arrivent au point où l'utilisateur doit penser ou implémenter des détails de bas niveau de l'algorithme d'optimisation.

Un autre avantage de l'algorithme EM est qu'il peut être utilisé dans les cas où certaines valeurs de données manquent.

Également intéressant (y compris les commentaires):

user20160
la source
Les contraintes dans le cas des modèles de mélange peuvent souvent être renforcées par reparamétrage. Par exemple, peut être fait en optimisant sur q iR et p i = exp ( q i )jepje=1qjeR . pje=exp(qje)jexp(qj)
bayerj
1
Oui, c'est certainement vrai. Ce serait une forme d'imposition de contraintes du point de vue de l'utilisateur (qui doit le coder), mais pas du point de vue du solveur (qui ne reçoit plus directement la contrainte correspondante). Une autre astuce: une matrice de covariance peut être exprimée en utilisant la matrice sans contrainte U , où C = U T U . Mais cela augmente à la fois le calcul et le nombre de paramètres par rapport à l'utilisation directe de C et à la contrainte à être une matrice symétrique semi-définie positive. CUC=UTUC
user20160
Oui, bonne perspective pour le déplacer du solveur vers l'utilisateur. Vous ne pouvez également considérer que le triangulaire . De cette façon, vous ne spécifiez pas trop le système car la plupart des paramètres sont à 0 . U0
bayerj
Droite, droite, décomposition cholesky. Bien mieux.
user20160
1
+1 bonne réponse! pourriez-vous expliquer davantage "il produit naturellement des paramètres valides pour la distribution du mélange à chaque itération"? Pour d'autres méthodes, nous avons toujours des valeurs de variable de décision pour chaque itération, non?
Haitao Du
2

Je pense que la réponse de user20160 fournit une très bonne explication, la raison la plus importante qui rend les méthodes basées sur un gradient non appropriées ici est la contrainte pour que les matrices de covariance soient semi-définies positives, et les coefficients de mélange pour être non négatifs et résumer à un.

Je veux juste souligner que si nous limitons les matrices de covariance à la diagonale, alors ces deux contraintes peuvent être exprimées facilement.

Une matrice de covariance diagonale peut s'écrire

Σ=[σ12σN2]
ϕk=epk/Kepje
alors les deux contraintes sont satisfaites, et les gradients peuvent être évalués simplement par rétropropagation.

De plus, cela nous permet d'optimiser directement la vraisemblance réelle au lieu de la limite inférieure variationnelle (ELBO), ce qui élimine le besoin de variables latentes.

Cependant, même dans de tels cas, l'EM s'avère souvent être un meilleur algorithme que le gradient décent.

dontloo
la source