24

He leído un par de explicaciones del algoritmo EM (p. Ej., De Bishop's Pattern Recognition and Machine Learning y Roger and Gerolami First Course on Machine Learning). La derivación de EM está bien, lo entiendo. También entiendo por qué el algoritmo cubre algo: en cada paso mejoramos el resultado y la probabilidad está limitada por 1.0, por lo que al usar un hecho simple (si una función aumenta y está limitada, entonces converge) sabemos que el algoritmo converge a alguna solución

Sin embargo, ¿cómo sabemos que es un mínimo local? En cada paso estamos considerando solo una coordenada (ya sea variable latente o parámetros), por lo que podríamos perder algo, como que el mínimo local requiere moverse por ambas coordenadas a la vez.

Esto creo que es un problema similar al de la clase general de algoritmos de escalada, de los cuales EM es una instancia. Entonces, para un algoritmo general de escalada tenemos este problema para la función f (x, y) = x * y. Si comenzamos desde el punto (0, 0), entonces solo al considerar ambas direcciones a la vez, podemos movernos hacia arriba desde el valor 0.

missing-data convergence expectation-maximization michal
fuente

3

La probabilidad está limitada solo para las variaciones fijas. Es decir, en la situación binomial, la varianza es

p (1 - p)

$p(1-p)$ ; o en la situación gaussiana, si se supone que se conoce la varianza. Si la varianza es desconocida y debe estimarse, la probabilidad no está limitada. Además, en el algoritmo EM, existe una separación genérica de los parámetros faltantes y, al menos para los estadísticos frecuentistas, pero las superficies pueden tener monturas.

StasK

@ Tarea No estoy seguro de que la probabilidad generalmente esté limitada incluso con variaciones fijas. ¿Estás restringiendo a alguna familia en particular?

Glen_b -Reinstate Monica

27

No se garantiza que EM converja a un mínimo local. Solo se garantiza la convergencia a un punto con gradiente cero con respecto a los parámetros. Por lo tanto, puede atascarse en los puntos de silla.

Tom Minka
fuente

1

Para ver ejemplos, véanse las págs. 20 y 38 aquí , pág. 85 aquí : prueba "saddle point" en Amazon reader.

StasK

13

En primer lugar, es posible que EM converja a un mínimo local , un máximo local o un punto de referencia de la función de probabilidad. Más precisamente, como señaló Tom Minka , se garantiza que EM convergerá a un punto con gradiente cero .

Puedo pensar en dos formas de ver esto; La primera vista es pura intuición, y la segunda vista es el bosquejo de una prueba formal. Primero, explicaré muy brevemente cómo funciona EM:

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

Expectativa Maximización como ascenso en gradiente

$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^*$

Bosquejo de una prueba formal

\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)$

, tenemos que

θ_{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
fuente

¿Por qué se garantiza que el algoritmo de maximización de expectativas converja a un óptimo local?

Respuestas:

Expectativa Maximización como ascenso en gradiente

Bosquejo de una prueba formal