La ecuación de Langevin como un algoritmo de minimización global
El algoritmo de descenso de gradiente es una de las técnicas de optimización más populares en el aprendizaje automático. Se presenta en tres sabores : pendiente de gradiente (vainilla) o “vainilla” (GD), pendiente de gradiente estocástica (SGD), y pendiente de gradiente de mini lotes que difiere en la cantidad de datos utilizados para calcular el gradiente de la función de pérdida en cada iteración.
El objetivo de este artículo es describir el progreso en la búsqueda de optimizadores globales basados en Langevin Dynamics (LD), un enfoque de modelado para molecular movimiento que tiene sus orígenes en trabajos de Albert Einstein y Paul Langevin sobre mecánica estadística a principios de la década de 1900.
Proporcionaré una elegante explicación de la perspectiva de la física teórica y por qué las variantes de pendiente de gradiente son optimizadores globales eficientes.
El Año Milagroso
No había ninguna señal de que una revolución estuviera a punto de ocurrir. En 1904, si Albert Einstein hubiera abandonado la física, es probable que sus colegas científicos ni siquiera lo hubieran notado. Afortunadamente, eso no sucedió. En 1905, el joven empleado de patentes publicó cuatro artículos que revolucionaron la ciencia.
Movimiento aleatorio en un fluido [19659006] En uno de esos documentos Einstein derivó un modelo para el llamado [movimiento browniano el movimiento aleatorio de partículas suspendidas en un líquido causado por colisiones con movimientos más pequeños y rápidos. moléculas ( granos de polen que se mueven en el agua, por ejemplo ).
En este documento, sin ayuda de nadie. confirmó la existencia de átomos y moléculas que dieron origen a una nueva rama de la física llamada dinámica molecular y creó un nuevo campo de matemáticas aplicadas conocido como cálculo estocástico .
Langevin Dynamics
En 1908, tres años después de Einstein publis. Hed sus documentos emblemáticos, el físico francés Paul Langevin publicó otro artículo innovador donde generalizó la teoría de Einstein y desarrolló una nueva ecuación diferencial que describe el movimiento browniano, hoy conocido como la ecuación de Langev . (LE)
donde x es la posición de la partícula en movimiento, m es su masa, R representa una fuerza (aleatoria) generada por colisiones con las moléculas más pequeñas y rápidas del fluido (consulte la animación anterior) y F representa cualquier otra fuerza externa. La fuerza aleatoria R es un proceso gaussiano estacionario correlacionado delta con la siguiente media y varianza:
El término “delta “correlacionado” significa que las fuerzas en dos momentos diferentes tienen una correlación cero. La LE fue la primera ecuación matemática que describió la termodinámica fuera de equilibrio.
Si la masa de la partícula es lo suficientemente pequeña, podemos establecer el lado izquierdo a cero. Además, podemos expresar una fuerza ( conservativa ) como el derivado de alguna energía potencial. Obtenemos:
Ahora, escribiendo
donde δt es un intervalo de tiempo pequeño, y moviendo términos alrededor, obtenemos la ecuación de Langevin discretizada para una partícula con masa pequeña:
Expresada de esta manera, la ecuación de Langevin describe los desplazamientos incrementales de una partícula que experimenta un movimiento browniano.
Un Interludio corto: un pitón Código para Brownian Motion
Aquí se puede encontrar una implementación en Python de Brownian motion . Para simular un proceso Brownian discreto 2D se utilizan dos procesos 1D. Los pasos de los códigos son:
- Primero, se elige el número de pasos de tiempo, pasos.
- Las coordenadasx y y son sumas acumulativas de saltos aleatorios (la función np.cumsum () se usa para calcularlos)
- Los puntos intermedios X y Yare se calculan por interpolación utilizando np.interp ()
- El movimiento se representa mediante la función plot ()
El código es:
importa numpy como np importa matplotlib .pyplot as plt % matplotlib en línea
pasos = 5000 random.seed (42) x, y = np.cumsum (np.random.randn (pasos)), np.cumsum ( np.random.randn (pasos))
puntos = 10 ip = lambda x, pasos, puntos: np.interp (np.arange (pasos * puntos), np.arange (pasos) * puntos, x) X, Y = ip (x, pasos, puntos), ip (y, pasos, puntos)
fig, ax = plt.subplots (1, 1, figsize = (10 , 10)) ax.set_title (& # 039; Brownian Motion & # 039; ) ax.set_xlabel (& # 039; x & # 039;) ax.set_ylabel (& # 039; y & # 039;) ax.plot (X, Y, color = & # 039; azul & # 039;, marcador = & # 039; o & # 039 ;, markersize = 1)
Langevin Dynamics and Global Minima [19659033] Una propiedad importante de la dinámica de Langevin es que la distribución de difusión p ( x ) del proceso estocástico x t t ) (donde x ( t ) obedece la ecuación de Langevin dada anteriormente) se convierte en una distribución estacionaria la ubicua distribución de Boltzmann (BD)
que se concentra en torno al mínimo global E ([19659015] x ) (por su forma funcional, podemos ver fácilmente que el BD alcanza el máximo global de la energía potencial E ( x )). Más precisamente como lo muestra Hajek y otros, si la temperatura disminuye lentamente a cero siguiendo los pasos discretos:
luego p ( x ) convergerá a la distribución de Boltzmann para valores grandes de n (y x convergerá al mínimo global de E ( x ). La ecuación de Langevin para temperaturas dependientes del tiempo generalmente se interpreta como una descripción de la descomposición de los estados físicos metastables en el estado fundamental del sistema (que es el mínimo global de la energía). Por lo tanto, se puede usar la dinámica de Langevin para diseñar algoritmos que sean minimizadores globales incluso de la función no convexa potencial .
Este principio es la base de la técnica de recocido simulado utilizada . para obtener el óptimo global aproximado de funciones.
Gradiente Descendimiento de algoritmos
Ahora cambiaré a engranajes a algoritmos de optimización de aprendizaje automático.
El descenso de gradiente es un algoritmo de optimización iterativo simple para minimizar (o maximizar) las funciones. En el contexto del aprendizaje automático, estas funciones son las funciones de pérdida (o funciones de costo). Para concretar, considere una función de pérdida multivariable L ( w ) definida para todos los puntos w alrededor de algún punto fijo p . El algoritmo GD se basa en la propiedad simple de que al comenzar en cualquier punto p la función L ( w ) disminuye más rápidamente en la dirección de su gradiente negativo:
Uno comienza adivinando un valor inicial para el mínimo (desconocido) y calcula la secuencia
siguiendo el proceso iterativo
donde γ es la velocidad de aprendizaje, que se permite cambiar en cada iteración n . Si la función de pérdida L y su gradiente tienen ciertas propiedades y la variación de la velocidad de aprendizaje se elige siguiendo ciertos protocolos local la convergencia está garantizada (la convergencia a un mínimo global está garantizada solo si L es convexa ya que para las funciones convexas, cualquier mínimo local también es global).
Gradiente de gradiente estocástico (SGD) ) y Mini-Batch Gradient Descent
En contraste con el algoritmo GD básico, que escanea el conjunto de datos completo en cada iteración, SGD y el GD de mini lotes usa solo un subconjunto de los datos de entrenamiento. SGD utiliza una única muestra de los datos de entrenamiento para actualizar el gradiente en cada iteración, es decir, a medida que se desplaza por los datos de entrenamiento, realiza la actualización anterior de w para cada ejemplo de entrenamiento. Mini-batch GD realiza actualizaciones de parámetros utilizando mini-batches de ejemplos de entrenamiento.
Pongamos esto en términos matemáticos. Para un conjunto de entrenamiento general
la función de pérdida tiene la forma general:
En el caso del descenso de gradiente de mini lotes, la suma solo se termina Los ejemplos de entrenamiento dentro del lote. SGD, en particular, utiliza una sola muestra. Estos procedimientos tienen dos ventajas principales en comparación con GD de vainilla: son mucho más rápidos y pueden manejar conjuntos de datos que son mucho más grandes (ya que usan una o unas pocas muestras).
Definición de G y g como se indica a continuación, tenemos en este caso:
En la gran animación a continuación por Alec Radford, la convergencia SGD se muestra junto con otras métodos ( estos otros métodos no mencionados en este artículo, son mejoras más recientes de SGD).
Aprendizaje automático y física: Pendiente de pendiente como un proceso de Langevin
El siguiente (y último) paso es crucial para el argumento. Omití los aspectos más rigurosos para la idea principal a presentar.
Podemos escribir el mini gradiente de lotes como una suma entre el gradiente completo y un η: [194590103] [194590003]
Ahora sustituyendo esta expresión en la expresión de iteración GD obtenemos:
Paso de iteración de pendiente de gradiente de mini lotes.
Un enlace elegante
Comparando la expresión de la pendiente de gradiente de mini lotes La iteración con la ecuación de Langevin podemos notar inmediatamente su similitud. Más precisamente, se vuelven idénticos usando la siguiente correspondencia:
Sustituyendo δt por γ en la segunda expresión, encontramos que
SGD o algoritmos de descenso de gradiente de mini lotes son por lo tanto formalmente análogo a los procesos de Langevin y eso explica por qué, dado que la velocidad de aprendizaje varía de acuerdo con los protocolos mencionados anteriormente, tienen una probabilidad muy alta de seleccionar mínimos globales.
Este resultado está lejos de ser nuevo. De hecho hay muchas pruebas de que la adición de un término de ruido a la recursión de pendiente del gradiente habitual hace que el algoritmo converja a los mínimos globales. Se debe enfatizar que es el “protocolo de enfriamiento” de la velocidad de aprendizaje lo que proporciona la aleatorización “extra” crucial que permite que el algoritmo escape los mínimos locales y converja al global.
Conclusión
En este artículo, Mostré que al pensar en los procesos estocásticos o en gradientes de mini lotes como procesos estocásticos de Langevin (con energía identificada con la función de pérdida) e incluir un nivel adicional de aleatorización a través de la tasa de aprendizaje, podemos entender por qué estos algoritmos pueden funcionar tan bien como optimizadores globales. Es un resultado elegante que muestra que examinar un problema desde múltiples puntos de vista suele ser extremadamente útil.
¡Gracias por leer!
My Github y mi sitio web personal www.marcotavora.me tienen (con suerte) otras cosas interesantes tanto sobre la ciencia de datos como sobre física.
Como siempre, ¡la crítica constructiva y los comentarios son bienvenidos!
Aprendizaje automático y movimiento de partículas en líquidos: originalmente se publicó un enlace elegante en Hacia la ciencia de datos en Medium, donde las personas continúan la conversación resaltando y respondiendo a esta historia.