¿Cuál es la relación entre el algoritmo Metropolis-Hastings para Markov Chain Monte Carlo y Gradient Descent?

Como han señalado otros comentaristas, MCMC es una técnica de muestreo, mientras que el descenso de gradiente es una técnica de optimización. Dicho esto, puede ver la optimización como una forma de muestreo “sesgado”, donde intenta muestrear * exclusivamente * desde el pico de su distribución. Esto conduce a grandes similitudes entre las técnicas de optimización y los algoritmos MCMC, especialmente porque, para la mayoría de los problemas de optimización, la función objetivo es multimodal, y es beneficioso usar múltiples reinicios aleatorios o inyectar alguna otra forma de aleatoriedad en el algoritmo.

Ejemplo: descenso de gradiente estocástico y MCMC de golpear y correr. En el descenso de gradiente estocástico, en cada iteración uno se mueve en una dirección que es aproximadamente el gradiente, pero con algún error aleatorio. En MCMC de golpear y correr, uno se mueve en una dirección aleatoria de acuerdo con una distribución que está sesgada hacia la dirección de mayor aumento.

Otro ejemplo: recocido simulado (optimización) y templado simulado (MCMC). La mayoría de los métodos de optimización, incluido el método de Newton y el descenso de gradiente, tienen una gran debilidad para quedarse atascado en los óptimos locales. La idea detrás del recocido simulado es salir del óptimo local haciendo ocasionalmente grandes saltos. El temple simulado logra el mismo objetivo, en el contexto del muestreo MCMC. Esto se debe a que en MCMC, uno también tiene que preocuparse por quedar atrapado cerca de los modos locales (máximos locales) de la distribución, ya que entonces terminará tomando muestras desproporcionadamente del modo local en lugar de la distribución completa. De hecho, el templado simulado a menudo se usa como una versión más sofisticada del recocido simulado, para resolver problemas de optimización altamente convexos y de alta dimensión.

Son dos métodos diferentes utilizados para diferentes propósitos en diferentes entornos.

El descenso de gradiente se utiliza para la optimización en entornos frecuentistas. Por ejemplo, tiene un modelo parametrizado que supone que genera datos, puede usar el descenso de gradiente para encontrar las estimaciones de máxima probabilidad de los parámetros.

MCMC se usa a menudo para aproximar una distribución de probabilidad compleja de la cual no es fácil / posible muestrear. Suponga que desea calcular la expectativa de una cantidad (digamos media) bajo una distribución pero no sabe cómo muestrear, entonces construye un MCMC. MCMC se usa a menudo en la configuración bayesiana para aproximar la distribución posterior de los parámetros (recuerde que no hay estimaciones puntuales en la configuración bayesiana, por lo tanto, no hay gradiente de descenso).

Ahora, en ciertos casos, puede usar MCMC dentro del descenso de gradiente. Por ejemplo, en cada iteración de descenso de gradiente, suponga que la actualización de parámetros requiere que calcule una expectativa, luego puede usar MCMC para calcular eso. Por ejemplo, en el entrenamiento CRF (campo aleatorio condicional), cada actualización de parámetros requiere que calculemos las expectativas del modelo bajo los parámetros actuales.

No son similares en absoluto. El descenso de gradiente es un algoritmo de optimización genérico, y MCMC es una clase de algoritmos de muestreo. Los métodos MCMC pueden usarse para la optimización, pero también pueden usarse para calcular integrales y estadísticas bayesianas, y un montón de otras cosas.

Su descripción describe cualquier método iterativo, no necesariamente GD y MCMC. Y en el sentido de GD, a veces puedes modelar el espacio analíticamente, simplemente eliges no hacerlo.

GD trabaja con funciones en lugar de distribuciones de probabilidad. GD siempre puede moverse en la dirección mínima (porque tiene una función de algún tipo), pero MCMC debe confiar en un muestreo adecuado para moverse en la dirección correcta.

Los dos son muy diferentes. Lo único en común es que iteran y convergen principalmente.