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

Question

He leído un par de explicaciones del algoritmo EM (por ejemplo, del libro Pattern Recognition and Machine Learning de Bishop y del Primer Curso de Aprendizaje Automático de Roger y Gerolami). La derivación de EM está bien, la entiendo. También entiendo por qué el algoritmo converge a algo: en cada paso mejoramos el resultado y la probabilidad está limitada por 1,0, así que usando 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 sólo una coordenada (ya sea la variable latente o los parámetros), por lo que podríamos pasar por alto algo, como que el mínimo local requiere moverse por ambas coordenadas a la vez.

Creo que se trata de un problema similar al de la clase general de algoritmos de ascenso de colinas, de los que el EM es un ejemplo. Así que para un algoritmo general de escalada tenemos este problema para la función f(x, y) = x*y. Si empezamos desde el punto (0, 0), entonces sólo considerando ambas direcciones a la vez somos capaces de subir desde el valor 0.

Answer 1

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

Answer 2

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

Se me ocurren dos maneras de ver esto; la primera es una pura intuición, y la segunda es el esbozo de una prueba formal. En primer lugar, explicaré muy brevemente cómo funciona la EM:

Maximización de las expectativas (EM) es una técnica de optimización de límites secuenciales donde en la iteración $t$ construimos primero un límite (inferior) $b_t(\theta)$ en la función de probabilidad $L(\theta)$ y luego maximizar el límite para obtener la nueva solución $\theta_t = \arg\max_\theta b_t(\theta)$ y seguir haciéndolo hasta que la nueva solución no cambie.

Maximización de expectativas como ascenso de gradiente

En cada iteración $t$ , EM requiere que el límite $b_t$ toca la función de probabilidad $L$ en la solución de la iteración anterior, es decir $\theta_{t-1}$ lo que implica que sus gradientes son también los mismos; es decir $g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$ . Por lo tanto, EM es al menos tan bueno como el ascenso por pendiente porque $\theta_t$ es al menos tan bueno como $\theta_{t-1} + \eta g$ . En otras palabras:

si EM converge a $\theta^*$ entonces $\theta^*$ es un punto convergente para el ascenso por gradiente también y EM satisface cualquier propiedad compartida entre las soluciones de ascenso por gradiente (incluyendo el valor de gradiente cero).

Esbozo de una prueba formal

Se puede demostrar que la diferencia entre los límites y la función de probabilidad converge a cero; es decir $$ \lim_{t \rightarrow \infty} L(\theta_t) - b_t(\theta_t) = 0. \tag{1} $$ Se puede demostrar que el gradiente del límite también converge al gradiente de la función de verosimilitud; es decir: $$ \lim_{t \rightarrow \infty} \nabla L(\theta_t) = \nabla b_t(\theta_t). \tag{2} $$ Debido a $(1)$ et $(2)$ y que los límites utilizados en EM son diferenciables, y que $\theta_t = \arg\max_\theta b_t(\theta)$ tenemos que $\nabla b_t(\theta_t)=0$ y, por lo tanto, $\lim_{t \rightarrow \infty} \nabla L(\theta_t) = 0$ .