24

J'ai lu quelques explications sur l'algorithme EM (par exemple de Bishop's Pattern Recognition and Machine Learning et de Roger and Gerolami First Course on Machine Learning). La dérivation de EM est ok, je le comprends. Je comprends également pourquoi l'algorithme couvre quelque chose: à chaque étape, nous améliorons le résultat et la probabilité est limitée par 1,0, donc en utilisant un simple fait (si une fonction augmente et est limitée, elle converge), nous savons que l'algorithme converge vers une solution.

Cependant, comment savons-nous qu'il s'agit d'un minimum local? À chaque étape, nous considérons une seule coordonnée (variable latente ou paramètres), donc nous pourrions manquer quelque chose, comme le minimum local nécessitant un déplacement des deux coordonnées à la fois.

Je pense que c'est un problème similaire à celui de la classe générale d'algorithmes d'escalade, dont EM est un exemple. Donc, pour un algorithme d'alpinisme général, nous avons ce problème pour la fonction f (x, y) = x * y. Si nous partons du point (0, 0), alors seulement en considérant les deux directions à la fois, nous pouvons remonter à partir de la valeur 0.

missing-data convergence expectation-maximization michal
la source

3

La probabilité n'est limitée que pour les variances fixes. Autrement dit, dans la situation binomiale, la variance est ; ou dans la situation gaussienne, si la variance est supposée connue. Si la variance est inconnue et doit être estimée, la probabilité n'est pas limitée. De plus, dans l'algorithme EM, il existe une séparation générique des paramètres manquants et, au moins pour les statisticiens fréquentistes, mais les surfaces peuvent en effet avoir des selles.

p (1 - p)

$p(1-p)$

StasK

@Stask Je ne suis pas sûr que la probabilité soit généralement limitée même avec des variances fixes. Vous limitez-vous à une famille particulière?

Glen_b -Reinstate Monica

27

EM n'est pas garanti de converger vers un minimum local. Il est seulement garanti de converger vers un point à gradient nul par rapport aux paramètres. Ainsi, il peut en effet se coincer aux points de selle.

Tom Minka
la source

1

Pour des exemples, voir pp. 20 et 38 ici , p. 85 ici - essayez "saddle point" dans Amazon reader.

StasK

13

Tout d'abord, il est possible que EM converge vers un min local , un max local ou un point de selle de la fonction de vraisemblance. Plus précisément, comme l'a souligné Tom Minka , l'EM est garanti de converger vers un point à gradient nul .

Je peux penser à deux façons de voir cela; la première vue est pure intuition, et la deuxième vue est l'esquisse d'une preuve formelle. Tout d'abord, je vais expliquer très brièvement comment fonctionne la SE:

$t$ $b_t(\theta)$ $L(\theta)$ $\theta_t = \arg\max_\theta b_t(\theta)$

Maximisation des attentes en tant que montée de gradient

$t$ $b_t$ $L$ $\theta_{t-1}$ $g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$ $\theta_t$ $\theta_{t-1} + \eta g$

$\theta^*$ $\theta^*$

Esquisse d'une preuve formelle

\begin{matrix} (1) & lim_{t \to \infty} L (θ_{t}) - b_{t} (θ_{t}) = 0. \end{matrix}

$\lim_{t \rightarrow \infty} L(\theta_t) - b_t(\theta_t) = 0. \tag{1}$

\begin{matrix} (2) & lim_{t \to \infty} \nabla L (θ_{t}) = \nabla b_{t} (θ_{t}) . \end{matrix}

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = \nabla b_t(\theta_t). \tag{2}$

(1)

$(1)$

(2)

$(2)$

θ_{t} = \arg max_{θ} b_{t} (θ)

$\theta_t = \arg\max_\theta b_t(\theta)$

\nabla b_{t} (θ_{t}) = 0

$\nabla b_t(\theta_t)=0$

lim_{t \to \infty} \nabla L (θ_{t}) = 0

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = 0$

Sobi
la source

Pourquoi l'algorithme de maximisation des attentes est-il garanti de converger vers un optimum local?

Réponses:

Maximisation des attentes en tant que montée de gradient

Esquisse d'une preuve formelle