¿Utiliza la integración de Runge-Kutta para aumentar la velocidad y la estabilidad del descenso de gradiente?

Question

¿Utiliza la integración de Runge-Kutta para aumentar la velocidad y la estabilidad del descenso de gradiente?

Matemáticas
mínimos cuadrados
descenso de gradiente
métodos numéricos
runge-kutta-métodos
ecuaciones diferenciales ordinarias

Lucas Hutchison

Para un problema de descenso de gradiente con $\mathbf{x}\in \mathbb{R}^N$ Puedo evaluar el gradiente $\mathbf{\nabla}_\mathbf{x} \in \mathbb{R}^N$ que reduce el error de mínimos cuadrados, $y$ . Sin embargo, simplemente actualizando la posición usando $\mathbf{x'} = \mathbf{x} + \mathbf{\nabla}_\mathbf{x}$ converge muy lentamente al mínimo global del error de mínimos cuadrados (que también es el mínimo global de la magnitud del gradiente, donde el gradiente es cero). Intenté simplemente escalar el paso, es decir $\mathbf{x'} = \mathbf{x} + h\mathbf{\nabla}_\mathbf{x}$ , sin embargo, si bien esto mejora drásticamente los tiempos de convergencia en algunos casos, puede volverse inestable en otros (particularmente cuando algunos de los componentes de $\mathbf{\nabla}_\mathbf{x}$ son mucho más grandes que otros: escalar todos los componentes del gradiente puede hacer que el método de descenso del gradiente "suba por el costado de un cañón" en lugar de descender por el cañón, y el sistema puede oscilar o explotar).

Me gustaría usar el método Runge-Kutta de tercer orden para seguir la curvatura del espacio degradado, de modo que pueda dar pasos más grandes sin que el sistema explote. He aplicado esto para simular sistemas de masa-resorte antes (usando la integración de Runge-Kutta para integrar la aceleración para encontrar la velocidad y la velocidad para encontrar la posición); sin embargo, no puedo entender cómo aplicarlo a este problema de descenso de gradiente.

Creo que tengo un malentendido fundamental sobre cómo funcionan los métodos de Runge-Kutta. Requieren una función $f=(x, y)$ por definir, que creo que calcula el gradiente de la curva en $x$ . Sin embargo no entiendo porque $y$ necesita ser suministrado a la función - no es $y$ una función de $x$ ?

¿Se puede incluso aplicar Runge-Kutta al problema del descenso del gradiente? Parece que debería haber una forma de adaptar Runge-Kutta al descenso de gradiente, ya que cada paso de actualización $\mathbf{x'} = \mathbf{x} + \mathbf{\nabla}_\mathbf{x}$ es básicamente un paso de integración. es el tamaño del paso $h$ simplemente la magnitud del gradiente, es decir $h_i = |{\mathbf{\nabla}_{\mathbf{x}_i}}|$ y $\mathbf{y}_i = {\mathbf{\nabla}_{\mathbf{x}_i}} / h_i$ ?

Si Runge-Kutta no es aplicable aquí, ¿alguien puede sugerir un algoritmo de descenso de gradiente robusto y rápido para probar?

Un poco más de detalle: en el caso de este problema, la superficie de gradiente es bastante suave y bastante convexa (hay pocos mínimos locales, si es que hay alguno, que no sean mínimos globales), pero la superficie de error es menos convexa. En otras palabras, a veces el descenso del gradiente continuará descendiendo por la pendiente del gradiente en la dirección del mínimo global del gradiente, y el error de mínimos cuadrados aumentará temporalmente antes de disminuir al mínimo global de error de mínimos cuadrados. (El gradiente no se calcula a partir de la medida de error de mínimos cuadrados en sí, sino que utiliza un método diferente que identifica directamente la mejor solución de mínimos cuadrados localmente, lo que acerca el sistema a la solución de mínimos cuadrados globalmente óptima). Por lo tanto, el gradiente es más confiable para el descenso de gradiente que la pendiente de la superficie de error de mínimos cuadrados.

Lucas Hutchison

@RodrigodeAzevedo gracias, arreglado

Lucas Hutchison

@RodrigodeAzevedo Sinceramente, no sé cómo aclarar más mi pregunta. Permítanme hacer una pregunta más directa: ¿es posible usar Runge-Kutta como un algoritmo de descenso de gradiente, es decir, se puede convertir un algoritmo de integración en un algoritmo de descenso de gradiente? Mi instinto dice que puede, pero tengo problemas para descubrir cómo hacerlo.

rodrigo de azevedo

¿Tienes algo así en mente?

Lucas Hutchison

Estoy tratando de implementar el punto más cercano iterativo, que requiere un descenso de gradiente en el espacio de rotación y traducción para alinear dos nubes de puntos. Sin embargo, también estoy interesado en acelerar el entrenamiento de redes profundas mediante el uso de Runge-Kutta para predecir la curvatura de la superficie de error, lo que permitiría tamaños de paso de descenso de gradiente más grandes.

rodrigo de azevedo

Eso no respondió del todo a mi pregunta.

Respuestas (1)

¿Utiliza la integración de Runge-Kutta para aumentar la velocidad y la estabilidad del descenso de gradiente?

@RodrigodeAzevedo Sinceramente, no sé cómo aclarar más mi pregunta. Permítanme hacer una pregunta más directa: ¿es posible usar Runge-Kutta como un algoritmo de descenso de gradiente, es decir, se puede convertir un algoritmo de integración en un algoritmo de descenso de gradiente? Mi instinto dice que puede, pero tengo problemas para descubrir cómo hacerlo.
Estoy tratando de implementar el punto más cercano iterativo, que requiere un descenso de gradiente en el espacio de rotación y traducción para alinear dos nubes de puntos. Sin embargo, también estoy interesado en acelerar el entrenamiento de redes profundas mediante el uso de Runge-Kutta para predecir la curvatura de la superficie de error, lo que permitiría tamaños de paso de descenso de gradiente más grandes.

uranix · Answer 1

Primero, los métodos de descenso de gradiente y Runge-Kutta resuelven diferentes problemas.

El descenso de gradiente es un método para encontrar un extremo de $f(\mathbf x)$ resolviendo $\mathbf g(\mathbf x) = \nabla f(\mathbf x) = 0$ . El descenso de gradiente simplemente hace $X_{norte + 1} = X_{norte} + α_{norte} gramo (X_{norte})$ $\mathbf x_{n+1} = \mathbf x_{n} + \alpha_n \mathbf g(\mathbf x_n)$ con $\alpha_n$ ser arreglado o elegido inteligentemente.
Los métodos de Runge-Kutta se utilizan para resolver ODE, es decir, resolver un problema de valor inicial $X^{'} (t) = F (t, X (t)) X (0) = X_{0} .$ $\mathbf x'(t) = \mathbf F(t, \mathbf x(t))\\ \mathbf x(0) = \mathbf x_0.$ El método RK más simple es el método de Euler, que tiene una forma bastante similar a la GD. $X_{norte + 1} = X_{norte} + (t_{norte + 1} - t_{norte}) F (t_{norte}, X_{norte})$ $\mathbf x_{n+1} = \mathbf x_n + (t_{n+1} - t_n) \mathbf F(t_n, \mathbf x_n)$

En otras palabras, GD puede tratarse como el método de Euler aplicado a una EDO

\begin{matrix} (*) & X^{'} (t) = \pm gramo (X) X (0) = X_{0} . \end{matrix}

$\mathbf x'(t) = \pm \mathbf g(\mathbf x)\\ \tag{*} \mathbf x(0) = \mathbf x_0.$ solía

\pm

$\pm$ desde

α_{n}

$\alpha_n$ puede ser positivo o negativo (dependiendo de si está buscando un mínimo o un máximo). Las ODE generalmente se resuelven hacia adelante en el tiempo, por lo que

t_{n + 1} - t_{n}

$t_{n+1} - t_n$ es positivo.

La solución que estás buscando es el estado estacionario. $\mathbf x(\infty)$ en el que el lado izquierdo (y, en consecuencia, el lado derecho) se vuelve cero. El signo correcto también asegura que $\mathbf x(t)$ realmente tiende al estado estacionario y no a alejarse de él.

Además, asumiré que el signo correcto es $+$ .

Puede usar métodos RK de orden superior para el problema (*). Por ejemplo, la regla del punto medio

X_{norte + 1 / 2} = X_{norte} + \frac{Δ t_{norte}}{2} gramo (X_{norte}) X_{norte + 1} = X_{norte} + Δ t_{norte} gramo (X_{norte + 1 / 2})

$\mathbf x_{n+1/2} = \mathbf x_{n} + \frac{\Delta t_n}{2} \mathbf g(\mathbf x_n)\\ \mathbf x_{n+1} = \mathbf x_{n} + \Delta t_n \mathbf g(\mathbf x_{n+1/2})$

Se sabe que los métodos RK de orden superior son más precisos que el método de Euler. Esa es la trayectoria numérica (formada por $\mathbf x_n$ secuencia) está mucho más cerca de la verdadera trayectoria $\mathbf x(t)$ , que es la verdadera solución de (*). Desafortunadamente, no necesita esta propiedad. De hecho, no te importa lo cerca que estés $\mathbf x_n$ están a la trayectoria verdadera, en cambio, le interesa qué tan cerca están sus $\mathbf x_n$ a $\mathbf x(\infty)$ .

Es atractivo elegir $\Delta t_n$ grande, por lo que uno se acerca más rápido a la $t = \infty$ . Desafortunadamente, no funciona de esa manera, porque todos los métodos explícitos para ODE (y cualquier método RK es uno de ellos) tienen una condición de estabilidad que restringe el paso más grande $\Delta t$ . De hecho, incluso eligiendo $\Delta t$ cerca de ese límite tampoco funcionará, ya que el método oscilará hacia adelante y hacia atrás (exactamente como lo hace GD). Elegir $\Delta t$ que maximiza la velocidad de convergencia no es trivial.

Otro hecho decepcionante es el fenómeno de la rigidez. Probablemente sepas que hay funciones patológicas $f(\mathbf x)$ para lo cual GD converge muy lentamente. Por lo general, sucede cuando la matriz Hessiana de $f$ está mal acondicionado. Para estos casos, los sistemas correspondientes (*) son (infamemente) conocidos en integración numérica como problemas rígidos. Para estos problemas, todos los métodos explícitos funcionan aproximadamente igual: el límite para $\Delta t$ y se cree que la velocidad de convergencia es prácticamente la misma.

Los problemas rígidos a menudo se resuelven mediante métodos implícitos. Esos métodos no se pueden convertir a un método similar a GD, ya que requieren resolver un problema no lineal para cada iteración. Y este problema es más o menos equivalente al propio problema de minimización. Por ejemplo, el método implícito de Euler tiene la forma

X_{norte + 1} = X_{norte} + Δ t_{norte} gramo (X_{norte + 1}) .

$\mathbf x_{n+1} = \mathbf x_{n} + \Delta t_n \mathbf g(\mathbf x_{n+1}).$ Separando lo conocido

x_{n}

$\mathbf x_n$ y desconocido

x_{n + 1}

$\mathbf x_{n+1}$ da un problema no lineal para

x_{n + 1}

$\mathbf x_{n+1}$

GRAMO (X_{norte + 1}) \equiv X_{norte + 1} - Δ t_{norte} gramo (X_{norte + 1}) = X_{norte}

$\mathbf G(\mathbf x_{n+1}) \equiv \mathbf x_{n+1} - \Delta t_n \mathbf g(\mathbf x_{n+1}) = \mathbf x_{n}$ Este problema es solo un poco más simple de resolver que el original.

g (x) = 0

$\mathbf g(\mathbf x) = 0$ .

Resumiendo todo lo anterior: el uso de métodos más precisos para (*) no lo llevará a la solución más rápido. En su lugar, es posible que desee utilizar el método de gradientes conjugados u otros métodos especializados en problemas de minimización, que posiblemente involucren más información sobre la función.

¿Utiliza la integración de Runge-Kutta para aumentar la velocidad y la estabilidad del descenso de gradiente?

Lucas Hutchison

Lucas Hutchison

Lucas Hutchison

rodrigo de azevedo

Lucas Hutchison

rodrigo de azevedo

Respuestas (1)

uranix

Lucas Hutchison

NDSolve resuelve esta ecuación diferencial ordinaria solo "a medias"

Cómo usar un círculo tangente en un método numérico para una ecuación diferencial de valores complejos

Recomendaciones de libros de análisis numérico y ecuaciones diferenciales que se centran en los temas dados.

Diferencias esenciales entre Runge-Kutta y Adams-Bashforth

Métodos numéricos (para ODE/PDE) que podrían tomar soluciones aproximadas/buenas conjeturas iniciales y refinarlas aún más hasta cierta precisión

Solución numérica de una ecuación diferencial lineal con coeficientes no constantes

Ecuación diferencial ordinaria no lineal

Algoritmo de retropropagación

Problema verbal de ecuación diferencial fuga de agua y=x2y=x2y=x^2

Resolviendo desbordamiento para raíces cuadráticas