Motivation de l'algorithme de maximisation des attentes

Dans l'approche de l'algorithme EM, nous utilisons l'inégalité de Jensen pour arriver à

$$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$

et définir par \ theta ^ {(k + 1)} = \ arg \ max _ {\ theta} \ int \ log p (z, x | \ theta) p (z | x , \ theta ^ {(k)}) dz$\theta^{(k+1)}$

$$\theta^{(k+1)}=\arg \max_{\theta}\int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz$$

Tout ce que je lis dans EM me laisse tomber, mais je me suis toujours senti mal à l'aise de ne pas avoir expliqué pourquoi l'algorithme EM se posait naturellement. Je comprends que $\log$ probabilité de \ log est généralement traitée pour traiter l'addition au lieu de la multiplication, mais l'apparition de $\log$ dans la définition de $\theta^{(k+1)}$ me semble pas motivée. Pourquoi devrait-on considérer $\log$ et pas d'autres fonctions monotones? Pour diverses raisons, je soupçonne que le «sens» ou la «motivation» derrière la maximisation des attentes a une sorte d'explication en termes de théorie de l'information et de statistiques suffisantes. S'il y avait une telle explication, ce serait beaucoup plus satisfaisant qu'un simple algorithme abstrait.

L'algorithme EM a différentes interprétations et peut se présenter sous différentes formes dans différentes applications.

Tout commence par la fonction de vraisemblance , ou de manière équivalente, la fonction log-vraisemblance nous voudrions maximiser. (Nous utilisons généralement le logarithme car il simplifie le calcul: il est strictement monotone, concave et .) Dans un monde idéal, la valeur de ne dépend que du paramètre du modèle , afin que nous puissions rechercher dans l'espace de et en trouver un qui maximise .log p ( x | θ ) log ( a b ) = log a + log b p θ θ $p(x \vert \theta)$$\log p(x \vert \theta)$$\log(ab) = \log a + \log b$$p$ $\theta$$\theta$$p$

Cependant, dans de nombreuses applications réelles intéressantes, les choses sont plus compliquées, car toutes les variables ne sont pas observées. Oui, nous pourrions observer directement , mais certaines autres variables sont pas observées. En raison des variables manquantes , nous sommes dans une sorte de situation de poule et oeufs: sans nous ne pouvons pas estimer le paramètre et sans nous ne pouvons pas déduire quelle est la valeur de .z z z θ θ $x$$z$ $z$$z$$\theta$$\theta$$z$

C'est là que l'algorithme EM entre en jeu. Nous commençons par une première estimation des paramètres du modèle et dérivons les valeurs attendues des variables manquantes (c'est-à-dire l'étape E). Lorsque nous avons les valeurs de , nous pouvons maximiser la probabilité par rapport aux paramètres (c'est-à-dire l'étape M, correspondant à l' équation dans l'énoncé du problème). Avec cette nous pouvons dériver les nouvelles valeurs attendues de (une autre étape E), etc. En un autre mot, à chaque étape, nous supposons l'un des deux, etz z θ arg max θ z z $\theta$$z$$z$$\theta$$\arg \max$$\theta$$z$$z$$\theta$, est connu. Nous répétons ce processus itératif jusqu'à ce que la probabilité ne puisse plus être augmentée.

Voici l'algorithme EM en bref. Il est bien connu que la probabilité ne diminuera jamais au cours de ce processus EM itératif. Mais gardez à l'esprit que l'algorithme EM ne garantit pas un optimum global. Autrement dit, il pourrait se retrouver avec un optimum local de la fonction de vraisemblance.

L'apparition de dans l'équation de est inévitable, car ici la fonction que vous souhaitez maximiser est écrite comme une log-vraisemblance.θ ( k + 1 $\log$$\theta^{(k+1)}$

Probabilité vs log-vraisemblance

Comme cela a déjà été dit, le est introduit en toute vraisemblance simplement parce qu'il est généralement plus facile d'optimiser les sommes que les produits. La raison pour laquelle nous ne considérons pas d'autres fonctions monotones est que le logarithme est la fonction unique qui a la propriété de transformer des produits en sommes.$\log$

Une autre façon de motiver le logarithme est la suivante: au lieu de maximiser la probabilité des données sous notre modèle, nous pourrions essayer de manière équivalente de minimiser la divergence de Kullback-Leibler entre la distribution des données, , et le distribution du modèle, ,p ( x ∣ θ $p_\text{data}(x)$$p(x \mid \theta)$

$$D_\text{KL}[p_\text{data}(x) \mid\mid p(x \mid \theta)] = \int p_\text{data}(x) \log \frac{p_\text{data}(x)}{p(x \mid \theta)} \, dx = const - \int p_\text{data}(x)\log p(x \mid \theta) \, dx.$$

Le premier terme sur le côté droit est constant dans les paramètres. Si nous avons échantillons de la distribution des données (nos points de données), nous pouvons approximer le deuxième terme avec la log-vraisemblance moyenne des données,$N$

$$\int p_\text{data}(x)\log p(x \mid \theta) \, dx \approx \frac{1}{N} \sum_n \log p(x_n \mid \theta).$$

Une autre vision de la SE

Je ne suis pas sûr que ce sera le genre d'explication que vous recherchez, mais j'ai trouvé la vue suivante de la maximisation des attentes beaucoup plus éclairante que sa motivation via l'inégalité de Jensen (vous pouvez trouver une description détaillée dans Neal & Hinton (1998) ou dans le livre PRML de Chris Bishop, chapitre 9.3).

Il n'est pas difficile de montrer que

$$\log p(x \mid \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz + D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)]$$

pour tout . Si nous appelons le premier terme à droite , cela implique queF ( q , θ $q(z \mid x)$$F(q, \theta)$

$$F(q, \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz = \log p(x \mid \theta) - D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)].$$

Parce que la divergence KL est toujours positive , est une borne inférieure de la log-vraisemblance pour chaque fixe . Maintenant, EM peut être considéré comme maximisant alternativement par rapport à et . En particulier, en définissant dans l'étape E, on minimise la divergence KL sur le côté droit et de maximiser ainsi .q F q θ q ( z ∣ x ) = p ( z ∣ x , θ ) $F(q, \theta)$$q$$F$$q$$\theta$$q(z \mid x) = p(z \mid x, \theta)$$F$

L'article que j'ai trouvé clarifiant en ce qui concerne la maximisation des attentes est le K-Means bayésien comme algorithme de "maximisation-attente" (pdf) par Welling et Kurihara.

Supposons que nous ayons un modèle probabiliste avec observations, variables aléatoires cachées et un total de paramètres . On nous donne un ensemble de données et sommes contraints (par des puissances supérieures) d'établir .x z θ D p ( z , θ | D $p(x,z,\theta)$$x$$z$$\theta$$D$$p(z,\theta|D)$

1. Échantillonnage de Gibbs

Nous pouvons approximer par échantillonnage. L'échantillonnage de Gibbs donne en alternant:p ( z , θ | D $p(z,\theta|D)$$p(z,\theta|D)$

$$\theta \sim p(\theta|z,D) \\ z \sim p(z|\theta,D)$$

2. Bayes variationnels

Au lieu de cela, nous pouvons essayer d'établir une distribution et et minimiser la différence avec la distribution que nous recherchons après . La différence entre les distributions a un nom de fantaisie pratique, la divergence KL. Pour minimiser nous mettons à jour:q ( z ) p ( θ , z | D ) K L [ q ( θ ) q ( z ) | | p ( θ , z | D ) $q(\theta)$$q(z)$$p(\theta,z|D)$$KL[q(\theta)q(z)||p(\theta,z|D)]$

$$q(\theta) \propto \exp (E [\log p(\theta,z,D) ]_{q(z)} ) \\ q(z) \propto \exp (E [\log p(\theta,z,D) ]_{q(\theta)} )$$

3. Attente-maximisation

Trouver des distributions de probabilité à part entière pour et pourrait être considéré comme extrême. Pourquoi ne considérons-nous pas plutôt une estimation ponctuelle pour l'un d'entre eux et gardons l'autre agréable et nuancé. Dans EM, le paramètre est établi comme étant indigne d'une distribution complète, et défini sur sa valeur MAP (Maximum A Posteriori), .θ θ θ $z$$\theta$$\theta$$\theta^*$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(z)} \\ q(z) = p(z|\theta^*,D)$$

Ici serait en fait une meilleure notation: l'opérateur argmax peut retourner plusieurs valeurs. Mais n'attaquons pas. Comparé aux Bayes variationnels, vous voyez que la correction du by ne change pas le résultat, donc ce n'est plus nécessaire.log $\theta^* \in \operatorname{argmax}$$\log$$\exp$

4. Maximisation-Attente

Il n'y a aucune raison de considérer comme un enfant gâté. Nous pouvons tout aussi bien utiliser les estimations ponctuelles pour nos variables cachées et donner aux paramètres le luxe d'une distribution complète.z ∗$z$$z^*$$\theta$

$$z^* = \underset{z}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(\theta)} \\ q(\theta) = p(\theta|z^*,D)$$

Si nos variables cachées sont des variables indicatrices, nous avons soudainement une méthode bon marché pour effectuer une inférence sur le nombre de grappes. C'est-à-dire: sélection de modèle (ou détection automatique de pertinence ou imaginez un autre nom de fantaisie).$z$

5. Modes conditionnels itérés

Bien sûr, l'enfant poster d'une inférence approximative est d'utiliser des estimations ponctuelles pour les paramètres ainsi que pour les observations .$\theta$$z$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} p(\theta,z^*,D) \\ z^* = \underset{z}{\operatorname{argmax}} p(\theta^*,z,D) \\ $$

Pour voir comment Maximization-Expectation se joue, je recommande fortement l'article. À mon avis, la force de cet article n'est cependant pas l'application à une alternative moyennes, mais cette exposition lucide et concise de l'approximation.$k$

Il existe une technique d'optimisation utile sous-jacente à l'algorithme EM. Cependant, il est généralement exprimé dans le langage de la théorie des probabilités, il est donc difficile de voir qu'au cœur se trouve une méthode qui n'a rien à voir avec la probabilité et l'attente.

Considérons le problème de la maximisation de (ou de manière équivalente ) par rapport à . Si vous écrivez une expression pour et la mettez égale à zéro, vous vous retrouverez souvent avec une équation transcendantale à résoudre. Celles-ci peuvent être désagréables.log g ( x ) x g ′ ( x

$$g(x)=\sum_i\exp(f_i(x))$$ $\log g(x)$$x$$g'(x)$

Supposons maintenant que les jouent bien ensemble dans le sens où leurs combinaisons linéaires vous donnent quelque chose de facile à optimiser. Par exemple, si tous les sont quadratiques en alors une combinaison linéaire des sera également quadratique, et donc facile à optimiser.f i ( x ) x f i ( x $f_i$$f_i(x)$$x$$f_i(x)$

Compte tenu de cette supposition, ce serait cool si, afin d'optimiser nous pourrions en quelque sorte mélanger le delà de la afin qu'il puisse répondre à la s et les éliminer. Ensuite, les pouvaient jouer ensemble. Mais nous ne pouvons pas faire ça.log ∑ exp f $\log g(x)=\log \sum_i\exp(f_i(x))$$\log$$\sum$$\exp$$f_i$

Faisons la prochaine meilleure chose. Nous allons créer une autre fonction similaire à . Et nous allons le faire à partir de combinaisons linéaires de .g f $h$$g$$f_i$

Disons que est une supposition pour une valeur optimale. Nous aimerions améliorer cela. Trouvons une autre fonction qui correspond à et sa dérivée à , c'est-à-dire et . Si vous tracez un graphique de dans un petit voisinage de cela ressemblera à . h g x 0 g ( x 0 ) = h ( x 0 ) g ′ ( x 0 ) = h ′ ( x 0 ) h x 0$x_0$$h$$g$$x_0$$g(x_0)=h(x_0)$$g'(x_0)=h'(x_0)$$h$$x_0$$g$

Vous pouvez montrer queNous voulons quelque chose qui corresponde à . Il y a un choix naturel:Vous pouvez voir qu'ils correspondent à . On obtientComme est une constante, nous avons une simple combinaison linéaire de dont la dérivée correspond à . Il suffit de choisir la constante en pour faire .x 0 h ( x ) = constante + ∑ i f i ( x ) exp ( f i ( x 0 ) ) . x = x 0 h ′ ( x ) =

$$g'(x)=\sum_i f_i'(x)\exp(f_i(x)).$$ $x_0$ $$h(x)=\mbox{constant}+\sum_i f_i(x)\exp(f_i(x_0)).$$ $x=x_0$x 0 f i ghg( x 0 )=h( x 0 $$h'(x)=\sum_i f_i'(x)\exp(f_i(x_0)).$$ $x_0$$f_i$$g$$h$$g(x_0)=h(x_0)$

Donc, en commençant par , nous formons et optimisons cela. Parce qu'il est similaire à dans le voisinage de nous espérons que l'optimum de est similaire à l'optimum de g. Une fois que vous avez une nouvelle estimation, construisez le suivant et répétez. h ( x ) g ( x ) x 0 h $x_0$$h(x)$$g(x)$$x_0$$h$$h$

J'espère que cela a motivé le choix de . C'est exactement la procédure qui se déroule en EM.$h$

Mais il y a un autre point important. En utilisant l'inégalité de Jensen, vous pouvez montrer que . Cela signifie que lorsque vous optimisez vous obtenez toujours un qui fait plus grand par rapport à . Ainsi, même si était motivé par sa similitude locale avec , il est sûr de maximiser globalement à chaque itération. L'espoir que j'ai mentionné ci-dessus n'est pas nécessaire.h ( x ) x g g ( x 0 ) h g $h(x)\le g(x)$$h(x)$$x$$g$$g(x_0)$$h$$g$$h$

Cela donne également un indice sur le moment d'utiliser EM: lorsque les combinaisons linéaires des arguments de la fonction sont plus faciles à optimiser. Par exemple, lorsqu'ils sont quadratiques - comme cela se produit lorsque vous travaillez avec des mélanges de gaussiens. Cela est particulièrement pertinent pour les statistiques où de nombreuses distributions standard proviennent de familles exponentielles .$\exp$

Comme vous l'avez dit, je n'entrerai pas dans les détails techniques. Il y a pas mal de tutoriels très sympas. Un de mes favoris est les notes de cours d' Andrew Ng . Jetez également un œil aux références ici .

1. EM est naturellement motivé dans les modèles de mélange et les modèles avec des facteurs cachés en général. Prenons par exemple le cas des modèles de mélange gaussiens (GMM). Ici, nous modélisons la densité des observations comme une somme pondérée de gaussiens: où est la probabilité que l'échantillon été causé / généré par la ième composante, est la moyenne de la distribution, et est la covariance matrice. La façon de comprendre cette expression est la suivante: chaque échantillon de données a été généré / provoqué par un composant, mais nous ne savons pas lequel. L'approche consiste alors à exprimer l'incertitude en termes de probabilité (p ( x ) = K ∑ i = 1 π i N ( x | μ i , Σ i ) π i x μ i Σ i π $K$

   $$p(x) = \sum_{i=1}^{K}\pi_{i} \mathcal{N}(x|\mu_{i}, \Sigma_{i})$$ $\pi_{i}$$x$$\mu_{i}$$\Sigma_{i}$$\pi_{i}$ représente les chances que la ième composante puisse prendre en compte cet échantillon), et prendre la somme pondérée. À titre d'exemple concret, imaginez que vous souhaitez regrouper des documents texte. L'idée est de supposer que chaque document appartient à un sujet (science, sport, ...) que vous ne connaissiez pas au préalable!. Les sujets possibles sont les variables cachées. Ensuite, vous recevez un tas de documents, et en comptant les n-grammes ou les fonctionnalités que vous extrayez, vous voulez ensuite trouver ces clusters et voir à quel cluster appartient chaque document. EM est une procédure qui s'attaque pas à pas à ce problème: l'étape d'attente tente d'améliorer les affectations des échantillons qu'elle a obtenus jusqu'à présent. L'étape de maximisation vous permet d'améliorer les paramètres du mélange, en d'autres termes, la forme des grappes.

2. Il ne s'agit pas d'utiliser des fonctions monotones mais des fonctions convexes. Et la raison en est l'inégalité de Jensen qui garantit que les estimations de l'algorithme EM s'amélioreront à chaque étape.