Descenso de gradiente

El descenso de gradiente es un algoritmo de optimización iterativo de primer orden para encontrar un mínimo local de una función diferenciable . La idea es dar pasos repetidos en la dirección opuesta al gradiente (o gradiente aproximado) de la función en el punto actual, porque esta es la dirección de descenso más pronunciado. Por el contrario, dar un paso en la dirección del gradiente conducirá a un máximo local de esa función; el procedimiento se conoce como ascenso en pendiente .

">

Reproducir medios

Descenso de gradiente en 2D

El descenso de gradiente se atribuye generalmente a Cauchy , quien lo sugirió por primera vez en 1847. ^[1] Hadamard propuso de forma independiente un método similar en 1907. ^[2]^[3] Sus propiedades de convergencia para problemas de optimización no lineal fueron estudiadas por primera vez por Haskell Curry en 1944. , ^[4] con el método cada vez más estudiado y utilizado en las décadas siguientes, ^[5]^[6] también llamado a menudo descenso más empinado.

Descripción

Ilustración de descenso de gradiente en una serie de conjuntos de niveles

El descenso de gradiente se basa en la observación de que si la función multivariable ${\ Displaystyle F (\ mathbf {x})}$ está definido y diferenciable en una vecindad de un punto ${\ Displaystyle \ mathbf {a}}$ , luego ${\ Displaystyle F (\ mathbf {x})}$ Disminuye más rápido si se pasa de ${\ Displaystyle \ mathbf {a}}$ en la dirección del gradiente negativo de ${\ Displaystyle F}$ a ${\ Displaystyle \ mathbf {a}, - \ nabla F (\ mathbf {a})}$ . De ello se deduce que, si

{\ Displaystyle \ mathbf {a} _ {n + 1} = \ mathbf {a} _ {n} - \ gamma \ nabla F (\ mathbf {a} _ {n})}

para ${\ Displaystyle \ gamma \ in \ mathbb {R} _ {+}}$ lo suficientemente pequeño, entonces ${\ Displaystyle F (\ mathbf {a_ {n}}) \ geq F (\ mathbf {a_ {n + 1}})}$ . En otras palabras, el término ${\ Displaystyle \ gamma \ nabla F (\ mathbf {a})}$ se resta de ${\ Displaystyle \ mathbf {a}}$ porque queremos movernos en contra de la pendiente, hacia el mínimo local. Con esta observación en mente, uno comienza con una suposición ${\ Displaystyle \ mathbf {x} _ {0}}$ por un mínimo local de ${\ Displaystyle F}$ , y considera la secuencia ${\ Displaystyle \ mathbf {x} _ {0}, \ mathbf {x} _ {1}, \ mathbf {x} _ {2}, \ ldots}$ tal que

{\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} \ nabla F (\ mathbf {x} _ {n}), \ n \ geq 0.}

Tenemos una secuencia monótona

{\ Displaystyle F (\ mathbf {x} _ {0}) \ geq F (\ mathbf {x} _ {1}) \ geq F (\ mathbf {x} _ {2}) \ geq \ cdots,}

entonces, con suerte, la secuencia ${\ Displaystyle (\ mathbf {x} _ {n})}$ converge al mínimo local deseado. Tenga en cuenta que el valor del tamaño del paso ${\ Displaystyle \ gamma}$ se permite cambiar en cada iteración. Con ciertas suposiciones sobre la función ${\ Displaystyle F}$ (por ejemplo, ${\ Displaystyle F}$ convexo y ${\ Displaystyle \ nabla F}$ Lipschitz ) y elecciones particulares de ${\ Displaystyle \ gamma}$ (p. ej., elegido mediante una búsqueda de líneas que satisfaga las condiciones de Wolfe o el método Barzilai-Borwein ^[7]^{[8] que se} muestra a continuación),

{\ Displaystyle \ gamma _ {n} = {\ frac {\ left | \ left (\ mathbf {x} _ {n} - \ mathbf {x} _ {n-1} \ right) ^ {T} \ left [\ nabla F (\ mathbf {x} _ {n}) - \ nabla F (\ mathbf {x} _ {n-1}) \ derecha] \ derecha |} {\ izquierda \ | \ nabla F (\ mathbf {x} _ {n}) - \ nabla F (\ mathbf {x} _ {n-1}) \ right \ | ^ {2}}}}

se puede garantizar la convergencia a un mínimo local. Cuando la función ${\ Displaystyle F}$ es convexo , todos los mínimos locales también son mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global.

Este proceso se ilustra en la imagen adyacente. Aquí, ${\ Displaystyle F}$ se supone que está definido en el plano y que su gráfico tiene forma de cuenco . Las curvas azules son las curvas de nivel , es decir, las regiones en las que el valor de ${\ Displaystyle F}$ es constante. Una flecha roja que se origina en un punto muestra la dirección del gradiente negativo en ese punto. Tenga en cuenta que el gradiente (negativo) en un punto es ortogonal a la línea de contorno que pasa por ese punto. Vemos que el descenso de gradiente nos lleva al fondo del cuenco, es decir, al punto donde el valor de la función ${\ Displaystyle F}$ es mínimo.

Una analogía para comprender el descenso de gradientes

Niebla en las montañas

La intuición básica detrás del descenso de gradientes puede ilustrarse mediante un escenario hipotético. Una persona está atrapada en las montañas y está tratando de bajar (es decir, tratando de encontrar el mínimo global). Hay una densa niebla que hace que la visibilidad sea extremadamente baja. Por lo tanto, el camino de bajada de la montaña no es visible, por lo que deben usar la información local para encontrar el mínimo. Pueden usar el método de descenso en gradiente, que implica mirar la pendiente de la colina en su posición actual y luego proceder en la dirección con el descenso más empinado (es decir, cuesta abajo). Si estuvieran tratando de encontrar la cima de la montaña (es decir, el máximo), entonces continuarían en la dirección del ascenso más empinado (es decir, cuesta arriba). Usando este método, eventualmente encontrarían su camino hacia abajo de la montaña o posiblemente quedarían atrapados en algún agujero (es decir, el mínimo local o punto de silla ), como un lago de montaña. Sin embargo, suponga también que la pendiente de la colina no es inmediatamente obvia con una simple observación, sino que requiere un instrumento sofisticado para medir, que la persona tiene en ese momento. Se necesita bastante tiempo para medir la pendiente de la colina con el instrumento, por lo que deben minimizar el uso del instrumento si quieren bajar de la montaña antes de la puesta del sol. La dificultad entonces es elegir la frecuencia con la que deben medir la pendiente del cerro para no salirse de la pista.

En esta analogía, la persona representa el algoritmo y el camino recorrido por la montaña representa la secuencia de ajustes de parámetros que explorará el algoritmo. La pendiente de la colina representa la pendiente de la superficie de error en ese punto. El instrumento utilizado para medir la pendiente es la diferenciación (la pendiente de la superficie de error se puede calcular tomando la derivada de la función de error al cuadrado en ese punto). La dirección en la que eligen viajar se alinea con el gradiente de la superficie de error en ese punto. La cantidad de tiempo que viajan antes de tomar otra medida es el tamaño del paso.

Ejemplos de

El gradiente de descenso tiene problemas con funciones patológicas como la función de Rosenbrock que se muestra aquí.

{\ Displaystyle f (x_ {1}, x_ {2}) = (1-x_ {1}) ^ {2} +100 (x_ {2} -x_ {1} ^ {2}) ^ {2}. }

La función Rosenbrock tiene un estrecho valle curvo que contiene el mínimo. El fondo del valle es muy plano. Debido al valle plano curvo, la optimización se realiza en zigzag lentamente con pasos pequeños hacia el mínimo.

La naturaleza en zigzag del método también es evidente a continuación, donde el método de descenso de gradiente se aplica a

{\ Displaystyle F (x, y) = \ sin \ left ({\ frac {1} {2}} x ^ {2} - {\ frac {1} {4}} y ^ {2} +3 \ right ) \ cos \ left (2x + 1-e ^ {y} \ right).}

The gradient descent algorithm in action. (1: contour)

Elegir el tamaño del paso y la dirección de descenso

Desde que usó un tamaño de paso ${\ Displaystyle \ gamma}$ que es demasiado pequeño ralentizaría la convergencia, y una ${\ Displaystyle \ gamma}$ demasiado grande conduciría a la divergencia, encontrando un buen escenario de ${\ Displaystyle \ gamma}$ es un problema práctico importante. Philip Wolfe también abogó por utilizar "elecciones inteligentes de la dirección [de descenso]" en la práctica. ^[9] Si bien el uso de una dirección que se desvía de la dirección de descenso más pronunciada puede parecer contradictorio, la idea es que la pendiente más pequeña se puede compensar manteniéndose en una distancia mucho más larga.

Para razonar matemáticamente sobre esto, usemos una dirección ${\ Displaystyle \ mathbf {p} _ {n}}$ y tamaño de paso ${\ Displaystyle \ gamma _ {n}}$ y considere la actualización más general:

{\ Displaystyle \ mathbf {a} _ {n + 1} = \ mathbf {a} _ {n} - \ gamma _ {n} \, \ mathbf {p} _ {n}}

.

Encontrar una buena configuración de ${\ Displaystyle \ mathbf {p} _ {n}}$ y ${\ Displaystyle \ gamma _ {n}}$ requiere un poco de pensamiento. En primer lugar, nos gustaría que la dirección de actualización apunte cuesta abajo. Matemáticamente, dejando ${\ Displaystyle \ theta _ {n}}$ denotar el ángulo entre ${\ Displaystyle \ nabla F (\ mathbf {a_ {n}})}$ y ${\ Displaystyle \ mathbf {p} _ {n}}$ , esto requiere que ${\ Displaystyle \ cos \ theta _ {n}> 0.}$ Para decir más, necesitamos más información sobre la función objetivo que estamos optimizando. Bajo el supuesto bastante débil de que ${\ Displaystyle F}$ es continuamente diferenciable, podemos probar que: ^[10]

{\ Displaystyle F (\ mathbf {a} _ {n + 1}) \ leq F (\ mathbf {a} _ {n}) - \ gamma _ {n} \ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2} \ | \ mathbf {p} _ {n} \ | _ {2} \ left [\ cos \ theta _ {n} - \ max _ {t \ in [0,1 ]} {\ frac {\ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}} {\ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}}} \ right]}

( 1 )

Esta desigualdad implica que la cantidad por la que podemos estar seguros de que la función ${\ Displaystyle F}$ se reduce depende de una compensación entre los dos términos entre corchetes. El primer término entre corchetes mide el ángulo entre la dirección de descenso y la pendiente negativa. El segundo término mide la rapidez con que cambia el gradiente a lo largo de la dirección de descenso.

En principio, la desigualdad ( 1 ) podría optimizarse sobre ${\ Displaystyle \ mathbf {p} _ {n}}$ y ${\ Displaystyle \ gamma _ {n}}$ para elegir un tamaño y una dirección de paso óptimos. El problema es que evaluar el segundo término entre corchetes requiere evaluar ${\ Displaystyle \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n})}$ y las evaluaciones de gradientes adicionales son generalmente caras e indeseables. Algunas formas de solucionar este problema son:

Olvídese de los beneficios de una dirección de descenso inteligente estableciendo ${\ Displaystyle \ mathbf {p} _ {n} = \ nabla F (\ mathbf {a_ {n}})}$ y utilice la búsqueda de líneas para encontrar un tamaño de paso adecuado ${\ Displaystyle \ gamma _ {n}}$ , como uno que satisfaga las condiciones de Wolfe .
Asumiendo que ${\ Displaystyle F}$ es dos veces diferenciable, use su hessian ${\ Displaystyle \ nabla ^ {2} F}$ para estimar ${\ Displaystyle \ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n} ) \ | _ {2} \ approx \ | t \ gamma _ {n} \ nabla ^ {2} F (\ mathbf {a} _ {n}) \ mathbf {p} _ {n} \ |.}$ Entonces escoge ${\ Displaystyle \ mathbf {p} _ {n}}$ y ${\ Displaystyle \ gamma _ {n}}$ optimizando la desigualdad ( 1 ).
Asumiendo que ${\ Displaystyle \ nabla F}$ es Lipschitz , use su constante de Lipschitz ${\ Displaystyle L}$ al límite ${\ Displaystyle \ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ {n}) - \ nabla F (\ mathbf {a} _ {n} ) \ | _ {2} \ leq Lt \ gamma _ {n} \ | \ mathbf {p} _ {n} \ |.}$ Entonces escoge ${\ Displaystyle \ mathbf {p} _ {n}}$ y ${\ Displaystyle \ gamma _ {n}}$ optimizando la desigualdad ( 1 ).
Construya un modelo personalizado de ${\ Displaystyle \ max _ {t \ in [0,1]} {\ frac {\ | \ nabla F (\ mathbf {a} _ {n} -t \ gamma _ {n} \ mathbf {p} _ { n}) - \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}} {\ | \ nabla F (\ mathbf {a} _ {n}) \ | _ {2}}} }$ por ${\ Displaystyle F}$ . Entonces escoge ${\ Displaystyle \ mathbf {p} _ {n}}$ y ${\ Displaystyle \ gamma _ {n}}$ optimizando la desigualdad ( 1 ).
Bajo supuestos más sólidos sobre la función ${\ Displaystyle F}$ como la convexidad , pueden ser posibles técnicas más avanzadas .

Por lo general, siguiendo una de las recetas anteriores, se puede garantizar la convergencia a un mínimo local. Cuando la función ${\ Displaystyle F}$ es convexo , todos los mínimos locales también son mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global.

Solución de un sistema lineal

El algoritmo de descenso más pronunciado aplicado al filtro Wiener ^[11]

El descenso de gradiente se puede utilizar para resolver un sistema de ecuaciones lineales

{\ Displaystyle A \ mathbf {x} - \ mathbf {b} = 0}

reformulado como un problema de minimización cuadrática. Si la matriz del sistema ${\ Displaystyle A}$ es simétrica real y definida positiva , la función cuadrática para minimizar comúnmente es

{\ Displaystyle F (\ mathbf {x}) = \ mathbf {x} ^ {T} A \ mathbf {x} -2 \ mathbf {x} ^ {T} \ mathbf {b},}

así que eso

{\ Displaystyle \ nabla F (\ mathbf {x}) = 2 (A \ mathbf {x} - \ mathbf {b}).}

Para una matriz real general ${\ Displaystyle A}$ , mínimos cuadrados lineales definen

{\ Displaystyle F (\ mathbf {x}) = \ left \ | A \ mathbf {x} - \ mathbf {b} \ right \ | ^ {2}.}

En mínimos cuadrados lineales tradicionales de verdad ${\ Displaystyle A}$ y ${\ Displaystyle \ mathbf {b}}$ la norma euclidiana se utiliza, en cuyo caso

{\ Displaystyle \ nabla F (\ mathbf {x}) = 2A ^ {T} (A \ mathbf {x} - \ mathbf {b}).}

La búsqueda de línea de minimización, encontrar el tamaño óptimo de paso a nivel local ${\ Displaystyle \ gamma}$ en cada iteración, se puede realizar analíticamente para funciones cuadráticas y fórmulas explícitas para el óptimo localmente ${\ Displaystyle \ gamma}$ son conocidos. ^[5]^[12]

Por ejemplo, para una matriz real simétrica y definida positiva ${\ Displaystyle A}$ , un algoritmo simple puede ser el siguiente, ^[5]

{\ displaystyle {\ begin {alineado} & {\ text {repetir en el bucle:}} \\ & \ qquad \ mathbf {r}: = \ mathbf {b} - \ mathbf {Ax} \\ & \ qquad \ gamma: = {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r}} / {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {Ar}} \\ & \ qquad \ mathbf {x}: = \ mathbf {x} + \ gamma \ mathbf {r} \\ & \ qquad {\ hbox {if}} \ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r} { \ text {es lo suficientemente pequeño, luego sale del bucle}} \\ & {\ text {end repeat loop}} \\ & {\ text {return}} \ mathbf {x} {\ text {como resultado}} \ end {alineado}}}

Para evitar multiplicar por ${\ Displaystyle A}$ dos veces por iteración, observamos que ${\ Displaystyle \ mathbf {x}: = \ mathbf {x} + \ gamma \ mathbf {r}}$ implica ${\ Displaystyle \ mathbf {r}: = \ mathbf {r} - \ gamma \ mathbf {Ar}}$ , que proporciona el algoritmo tradicional, ^[13]

{\ displaystyle {\ begin {alineado} & \ mathbf {r}: = \ mathbf {b} - \ mathbf {Ax} \\ & {\ text {repetir en el bucle:}} \\ & \ qquad \ gamma: = {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r}} / {\ mathbf {r} ^ {\ mathsf {T}} \ mathbf {Ar}} \\ & \ qquad \ mathbf { x}: = \ mathbf {x} + \ gamma \ mathbf {r} \\ & \ qquad {\ hbox {if}} \ mathbf {r} ^ {\ mathsf {T}} \ mathbf {r} {\ text {es lo suficientemente pequeño, luego sale del ciclo}} \\ & \ qquad \ mathbf {r}: = \ mathbf {r} - \ gamma \ mathbf {Ar} \\ & {\ text {fin del ciclo de repetición}} \\ & {\ text {return}} \ mathbf {x} {\ text {como resultado}} \ end {alineado}}}

El método rara vez se usa para resolver ecuaciones lineales, siendo el método de gradiente conjugado una de las alternativas más populares. El número de iteraciones de descenso de gradiente es comúnmente proporcional al número de condición espectral ${\ Displaystyle \ kappa (A)}$ de la matriz del sistema ${\ Displaystyle A}$ (la relación entre los valores propios máximos y mínimos de ${\ Displaystyle A ^ {T} A}$ ) , mientras que la convergencia del método de gradiente conjugado generalmente se determina mediante una raíz cuadrada del número de condición, es decir, es mucho más rápido. Ambos métodos pueden beneficiarse del preacondicionamiento , donde el descenso del gradiente puede requerir menos suposiciones en el preacondicionador. ^[13]

Solución de un sistema no lineal

El descenso de gradiente también se puede utilizar para resolver un sistema de ecuaciones no lineales . A continuación se muestra un ejemplo que muestra cómo usar el descenso de gradiente para resolver tres variables desconocidas, x ₁ , x ₂ y x ₃ . Este ejemplo muestra una iteración del descenso de gradiente.

Considere el sistema de ecuaciones no lineal

{\ Displaystyle {\ begin {cases} 3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ tfrac {3} {2}} = 0 \\ 4x_ {1} ^ {2} - 625x_ {2} ^ {2} + 2x_ {2} -1 = 0 \\\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ tfrac {10 \ pi -3} {3 }} = 0 \ end {cases}}}

Introducimos la función asociada

{\ Displaystyle G (\ mathbf {x}) = {\ begin {bmatrix} 3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ tfrac {3} {2}} \\ 4x_ { 1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 \\\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ tfrac {10 \ pi -3} {3}} \\\ end {bmatrix}},}

dónde

{\ Displaystyle \ mathbf {x} = {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\\ end {bmatrix}}.}

Ahora se podría definir la función objetivo

{\ Displaystyle F (\ mathbf {x}) = {\ frac {1} {2}} G ^ {\ mathrm {T}} (\ mathbf {x}) G (\ mathbf {x}) = {\ frac {1} {2}} \ left [\ left (3x_ {1} - \ cos (x_ {2} x_ {3}) - {\ frac {3} {2}} \ right) ^ {2} + \ izquierda (4x_ {1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 \ derecha) ^ {2} + \ izquierda (\ exp (-x_ {1} x_ {2}) + 20x_ {3} + {\ frac {10 \ pi -3} {3}} \ right) ^ {2} \ right],}

que intentaremos minimizar. Como conjetura inicial, usemos

{\ Displaystyle \ mathbf {x} ^ {(0)} = \ mathbf {0} = {\ begin {bmatrix} 0 \\ 0 \\ 0 \\\ end {bmatrix}}.}

Lo sabemos

{\ Displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {0} - \ gamma _ {0} \ nabla F (\ mathbf {0}) = \ mathbf {0} - \ gamma _ {0} J_ {G} (\ mathbf {0}) ^ {\ mathrm {T}} G ​​(\ mathbf {0}),}

donde la matriz jacobiana ${\ Displaystyle J_ {G}}$ es dado por

{\ displaystyle J_ {G} (\ mathbf {x}) = {\ begin {bmatrix} 3 & \ sin (x_ {2} x_ {3}) x_ {3} & \ sin (x_ {2} x_ {3} ) x_ {2} \\ 8x_ {1} y - 1250x_ {2} + 2 y 0 \\ - x_ {2} \ exp {(-x_ {1} x_ {2})} y - x_ {1} \ exp ( -x_ {1} x_ {2}) y 20 \\\ end {bmatrix}}.}

Calculamos:

{\ displaystyle J_ {G} (\ mathbf {0}) = {\ begin {bmatrix} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 20 \ end {bmatrix}}, \ qquad G (\ mathbf {0}) = {\ begin { bmatrix} -2.5 \\ - 1 \\ 10.472 \ end {bmatrix}}.}

Por lo tanto

{\ displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {0} - \ gamma _ {0} {\ begin {bmatrix} -7.5 \\ - 2 \\ 209.44 \ end {bmatrix}},}

y

{\ displaystyle F (\ mathbf {0}) = 0.5 \ left ((- 2.5) ^ {2} + (- 1) ^ {2} + (10.472) ^ {2} \ right) = 58.456.}

Una animación que muestra las primeras 83 iteraciones de descenso de gradiente aplicadas a este ejemplo. Las superficies son isosuperficies de

{\ Displaystyle F (\ mathbf {x} ^ {(n)})}

en la suposición actual

{\ Displaystyle \ mathbf {x} ^ {(n)}}

, y las flechas muestran la dirección de descenso. Debido a un tamaño de paso pequeño y constante, la convergencia es lenta.

Ahora, un adecuado ${\ Displaystyle \ gamma _ {0}}$ debe ser encontrado de tal manera que

{\ Displaystyle F \ left (\ mathbf {x} ^ {(1)} \ right) \ leq F \ left (\ mathbf {x} ^ {(0)} \ right) = F (\ mathbf {0}) .}

Esto se puede hacer con cualquiera de una variedad de algoritmos de búsqueda de líneas . También se podría simplemente adivinar ${\ Displaystyle \ gamma _ {0} = 0.001,}$ lo que da

{\ displaystyle \ mathbf {x} ^ {(1)} = {\ begin {bmatrix} 0,0075 \\ 0,002 \\ - 0,20944 \\\ end {bmatrix}}.}

Al evaluar la función objetivo en este valor, se obtiene

{\ displaystyle F \ left (\ mathbf {x} ^ {(1)} \ right) = 0.5 \ left ((- 2.48) ^ {2} + (- 1.00) ^ {2} + (6.28) ^ {2 } \ right) = 23.306.}

La disminución de ${\ Displaystyle F (\ mathbf {0}) = 58,456}$ al valor del siguiente paso de

{\ Displaystyle F \ left (\ mathbf {x} ^ {(1)} \ right) = 23,306}

es una disminución considerable de la función objetivo. Más pasos reducirían su valor aún más, hasta que se encontrara una solución aproximada al sistema.

Comentarios

El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en dimensiones infinitas. En el último caso, el espacio de búsqueda es típicamente un espacio de función , y se calcula la derivada de Fréchet del funcional que se minimizará para determinar la dirección de descenso. ^[6]

Ese descenso de gradiente funciona en cualquier número de dimensiones (número finito al menos) puede verse como una consecuencia de la desigualdad de Cauchy-Schwarz . Ese artículo prueba que la magnitud del producto interno (punto) de dos vectores de cualquier dimensión se maximiza cuando son colineales. En el caso del descenso de gradiente, sería cuando el vector de ajustes de variables independientes es proporcional al vector de gradiente de derivadas parciales.

El descenso de gradiente puede tomar muchas iteraciones para calcular un mínimo local con la precisión requerida , si la curvatura en diferentes direcciones es muy diferente para la función dada. Para tales funciones, el preacondicionamiento , que cambia la geometría del espacio para dar forma a los conjuntos de niveles de función como círculos concéntricos , cura la convergencia lenta. Sin embargo, construir y aplicar el preacondicionamiento puede resultar computacionalmente costoso.

El descenso de gradiente se puede combinar con una búsqueda de línea , encontrando el tamaño de paso óptimo localmente ${\ Displaystyle \ gamma}$ en cada iteración. Realizar la búsqueda de línea puede llevar mucho tiempo. Por el contrario, utilizando un pequeño fijo ${\ Displaystyle \ gamma}$ puede producir una convergencia deficiente.

Los métodos basados en el método de Newton y la inversión del hessiano utilizando técnicas de gradiente conjugado pueden ser mejores alternativas. ^[14]^[15] Generalmente, estos métodos convergen en menos iteraciones, pero el costo de cada iteración es mayor. Un ejemplo es el método BFGS que consiste en calcular en cada paso una matriz por la cual se multiplica el vector de gradiente para ir en una "mejor" dirección, combinado con un algoritmo de búsqueda de línea más sofisticado , para encontrar el "mejor" valor de ${\ Displaystyle \ gamma.}$ Para problemas extremadamente grandes, donde dominan los problemas de memoria de la computadora, se debe usar un método de memoria limitada como L-BFGS en lugar de BFGS o el descenso más pronunciado.

El descenso de gradiente puede verse como la aplicación del método de Euler para resolver ecuaciones diferenciales ordinarias ${\ Displaystyle x '(t) = - \ nabla f (x (t))}$ a un flujo de gradiente . A su vez, esta ecuación puede derivarse como un controlador óptimo ^[16] para el sistema de control. ${\ Displaystyle x '(t) = u (t)}$ con ${\ Displaystyle u (t)}$ dado en el formulario de comentarios ${\ Displaystyle u (t) = - \ nabla f (x (t))}$ .

Modificaciones

El descenso en gradiente puede converger a un mínimo local y disminuir la velocidad en un vecindario de un punto de silla . Incluso para la minimización cuadrática sin restricciones, el descenso de gradiente desarrolla un patrón en zig-zag de iteraciones posteriores a medida que avanzan las iteraciones, lo que resulta en una convergencia lenta. Se han propuesto múltiples modificaciones del descenso de gradientes para abordar estas deficiencias.

Métodos de gradiente rápido

Yurii Nesterov ha propuesto ^[17] una modificación simple que permite una convergencia más rápida para problemas convexos y desde entonces se ha generalizado aún más. Para problemas suaves sin restricciones, el método se denomina método de gradiente rápido (FGM) o método de gradiente acelerado (AGM). Específicamente, si la función diferenciable ${\ Displaystyle F}$ es convexo y ${\ Displaystyle \ nabla F}$ es Lipschitz , y no se asume que ${\ Displaystyle F}$ es fuertemente convexo , entonces el error en el valor objetivo generado en cada paso ${\ Displaystyle k}$ por el método de descenso de gradiente estará delimitado por ${\ textstyle {\ mathcal {O}} \ left ({\ tfrac {1} {k}} \ right)}$ . Usando la técnica de aceleración de Nesterov, el error disminuye en ${\ textstyle {\ mathcal {O}} \ left ({\ tfrac {1} {k ^ {2}}} \ right)}$ . ^[18] Se sabe que la tasa ${\ Displaystyle {\ mathcal {O}} \ left ({k ^ {- 2}} \ right)}$ para la disminución de la función de costo es óptima para los métodos de optimización de primer orden. Sin embargo, existe la oportunidad de mejorar el algoritmo reduciendo el factor constante. El método de gradiente optimizado (OGM) ^[19] reduce esa constante en un factor de dos y es un método óptimo de primer orden para problemas a gran escala. ^[20]

Para problemas restringidos o no suaves, la MGF de Nesterov se denomina método de gradiente proximal rápido (FPGM), una aceleración del método de gradiente proximal .

Momento o método de bola pesada

Tratando de romper el patrón en zig-zag del descenso de gradiente, el método de la cantidad de movimiento o bola pesada utiliza un término de cantidad de movimiento en analogía con una bola pesada que se desliza sobre la superficie de valores de la función que se minimiza, ^[5] o el movimiento de masas en la dinámica newtoniana a través de un medio viscoso en un campo de fuerza conservador. ^{[21] El} descenso de gradiente con impulso recuerda la actualización de la solución en cada iteración y determina la siguiente actualización como una combinación lineal del gradiente y la actualización anterior. Para la minimización cuadrática sin restricciones, una tasa de convergencia teórica límite del método de bola pesada es asintóticamente igual que la del método de gradiente conjugado óptimo . ^[5]

Esta técnica se utiliza en el descenso de gradiente estocástico # Momentum y como una extensión de los algoritmos de retropropagación utilizados para entrenar redes neuronales artificiales . ^[22]^[23]

Extensiones

El descenso de gradiente se puede extender para manejar restricciones al incluir una proyección en el conjunto de restricciones. Este método solo es factible cuando la proyección se puede calcular de manera eficiente en una computadora. Bajo supuestos adecuados, este método converge. Este método es un caso específico del algoritmo hacia adelante y hacia atrás para inclusiones monótonas (que incluye programación convexa y desigualdades variacionales ). ^[24]

Ver también

Búsqueda de línea de retroceso
Método de gradiente conjugado
Descenso de gradiente estocástico
Rprop
Regla delta
Condiciones de Wolfe
Preacondicionamiento
Algoritmo de Broyden-Fletcher-Goldfarb-Shanno
Fórmula de Davidon-Fletcher-Powell
Método de Nelder-Mead
Algoritmo de Gauss-Newton
Montañismo
Recocido cuántico

Referencias

^ Lemaréchal, C. (2012). "Cauchy y el método de gradiente" (PDF) . Doc Math Extra : 251–254.
^ Hadamard, Jacques (1908). "Mémoire sur le problème d'analyse relatif à Véquilibre des plaques élastiques encastrées". Mémoires présentés par divers savants éstrangers à l'Académie des Sciences de l'Institut de France . 33 .
^ Courant, Richard (enero de 1943). "Métodos variacionales para la solución de problemas de equilibrio y vibraciones" . Toro. Amer. Matemáticas. Soc . 49 : 1-23. doi : 10.1090 / S0002-9904-1943-07818-4 - a través del Proyecto Euclid.
^ Curry, Haskell B. (1944). "El método de descenso más pronunciado para problemas de minimización no lineal" . Cuarto de galón. Apl. Matemáticas . 2 (3): 258–261. doi : 10.1090 / qam / 10667 .
^ a b c d e Polyak, Boris (1987). Introducción a la optimización .
^ a b Akilov, GP; Kantorovich, LV (1982). Análisis funcional (2ª ed.). Pergamon Press. ISBN 0-08-023036-9.
^ Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". Revista IMA de análisis numérico . 8 (1): 141-148. doi : 10.1093 / imanum / 8.1.141 .
^ Fletcher, R. (2005). "Sobre el método Barzilai-Borwein". En Qi, L .; Teo, K .; Yang, X. (eds.). Optimización y Control con Aplicaciones . Optimización aplicada. 96 . Boston: Springer. págs. 235-256. ISBN 0-387-24254-6.
^ Wolfe, Philip (1 de abril de 1969). "Condiciones de convergencia para métodos de ascenso" . Revisión SIAM . 11 (2): 226–235. doi : 10.1137 / 1011036 . ISSN 0036-1445 .
^ Bernstein, Jeremy; Vahdat, Arash; Yue, Yisong; Liu, Ming-Yu (12 de junio de 2020). "Sobre la distancia entre dos redes neuronales y la estabilidad del aprendizaje". arXiv : 2002.03432 [ cs.LG ].
^ Haykin, Simon S. Teoría del filtro adaptativo. Pearson Education India, 2008. - p. 108-142, 217-242
^ Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2ª ed.). Filadelfia, Pa .: Sociedad de Matemáticas Industriales y Aplicadas. págs. 195 . ISBN 978-0-89871-534-7.
^ a b Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado" . Procedia Informática . 51 : 276-285. doi : 10.1016 / j.procs.2015.05.241 .
^ Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (1992). Recetas numéricas en C: El arte de la informática científica (2ª ed.). Nueva York: Cambridge University Press. ISBN 0-521-43108-5.
^ Strutz, T. (2016). Ajuste de datos e incertidumbre: una introducción práctica a los mínimos cuadrados ponderados y más allá (2ª ed.). Springer Vieweg. ISBN 978-3-658-11455-8.
^ Ross, MI (1 de julio de 2019). "Una teoría de control óptimo para la optimización no lineal" . Revista de Matemática Computacional y Aplicada . 354 : 39–51. doi : 10.1016 / j.cam.2018.12.044 . ISSN 0377-0427 .
^ Nesterov, Yu. (2004). Conferencias introductorias sobre optimización convexa: un curso básico . Saltador. ISBN 1-4020-7553-7.
^ Vandenberghe, Lieven (2019). "Métodos de gradiente rápido" (PDF) . Apuntes de conferencias para EE236C en UCLA .
^ Kim, D .; Fessler, JA (2016). "Métodos optimizados de primer orden para una minimización convexa suave" . Matemáticas. Prog. 151 (1–2): 81–107. arXiv : 1406.5468 . doi : 10.1007 / s10107-015-0949-3 . PMC 5067109 . PMID 27765996 . S2CID 207055414 .
^ Drori, Yoel (2017). "La complejidad basada en información exacta de la minimización convexa suave". Revista de complejidad . 39 : 1-16. arXiv : 1606.01424 . doi : 10.1016 / j.jco.2016.11.001 . S2CID 205861966 .
^ Qian, Ning (enero de 1999). "En el término de impulso en algoritmos de aprendizaje de descenso de gradientes" (PDF) . Redes neuronales . 12 (1): 145-151. CiteSeerX 10.1.1.57.5612 . doi : 10.1016 / S0893-6080 (98) 00116-6 . PMID 12662723 . Archivado desde el original (PDF) el 8 de mayo de 2014 . Consultado el 17 de octubre de 2014 .
^ "Adaptación del impulso y la tasa de aprendizaje" . Universidad de Willamette . Consultado el 17 de octubre de 2014 .
^ Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del impulso" . Coursera . Consultado el 2 de octubre de 2018 .Parte de una serie de conferencias para el curso en línea de Coursera Neural Networks for Machine Learning Archivado el 31 de diciembre de 2016 en Wayback Machine .
^ Combettes, PL; Pesquet, J.-C. (2011). "Métodos de división proximal en el procesamiento de señales". En Bauschke, HH; Burachik, RS ; Combettes, PL; Elser, V .; Luke, DR; Wolkowicz, H. (eds.). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Nueva York: Springer. págs. 185–212. arXiv : 0912.3522 . ISBN 978-1-4419-9568-1.

Otras lecturas

Boyd, Stephen ; Vandenberghe, Lieven (2004). "Minimización sin restricciones" (PDF) . Optimización convexa . Nueva York: Cambridge University Press. págs. 457–520. ISBN 0-521-83378-7.
Chong, Edwin KP; Żak, Stanislaw H. (2013). "Métodos de gradiente" . Introducción a la optimización (cuarta edición). Hoboken: Wiley. págs. 131–160. ISBN 978-1-118-27901-4.
Himmelblau, David M. (1972). "Procedimientos de minimización sin restricciones mediante derivados". Programación no lineal aplicada . Nueva York: McGraw-Hill. págs. 63-132. ISBN 0-07-028921-2.

enlaces externos

Usando el descenso de gradiente en C ++, Boost, Ublas para regresión lineal
Una serie de videos de Khan Academy discute el ascenso en gradiente
Libro en línea que enseña el descenso de gradientes en el contexto de redes neuronales profundas
"Gradient Descent, cómo aprenden las redes neuronales" . 3Azul1Marrón . 16 de octubre de 2017 - a través de YouTube .

[1] Lemaréchal, C. (2012). "Cauchy y el método de gradiente" (PDF) . Doc Math Extra : 251–254.

[2] Hadamard, Jacques (1908). "Mémoire sur le problème d'analyse relatif à Véquilibre des plaques élastiques encastrées". Mémoires présentés par divers savants éstrangers à l'Académie des Sciences de l'Institut de France . 33 .

[3] Courant, Richard (enero de 1943). "Métodos variacionales para la solución de problemas de equilibrio y vibraciones" . Toro. Amer. Matemáticas. Soc . 49 : 1-23. doi : 10.1090 / S0002-9904-1943-07818-4 - a través del Proyecto Euclid.

[4] Curry, Haskell B. (1944). "El método de descenso más pronunciado para problemas de minimización no lineal" . Cuarto de galón. Apl. Matemáticas . 2 (3): 258–261. doi : 10.1090 / qam / 10667 .

[BP-5] Polyak, Boris (1987). Introducción a la optimización .

[AK82-6] Akilov, GP; Kantorovich, LV (1982). Análisis funcional (2ª ed.). Pergamon Press. ISBN 0-08-023036-9.

[7] Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". Revista IMA de análisis numérico . 8 (1): 141-148. doi : 10.1093 / imanum / 8.1.141 .

[8] Fletcher, R. (2005). "Sobre el método Barzilai-Borwein". En Qi, L .; Teo, K .; Yang, X. (eds.). Optimización y Control con Aplicaciones . Optimización aplicada. 96 . Boston: Springer. págs. 235-256. ISBN 0-387-24254-6.

[9] Wolfe, Philip (1 de abril de 1969). "Condiciones de convergencia para métodos de ascenso" . Revisión SIAM . 11 (2): 226–235. doi : 10.1137 / 1011036 . ISSN 0036-1445 .

[10] Bernstein, Jeremy; Vahdat, Arash; Yue, Yisong; Liu, Ming-Yu (12 de junio de 2020). "Sobre la distancia entre dos redes neuronales y la estabilidad del aprendizaje". arXiv : 2002.03432 [ cs.LG ].

[11] Haykin, Simon S. Teoría del filtro adaptativo. Pearson Education India, 2008. - p. 108-142, 217-242

[saad1996iterative-12] Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2ª ed.). Filadelfia, Pa .: Sociedad de Matemáticas Industriales y Aplicadas. págs. 195 . ISBN 978-0-89871-534-7.

[:0-13] Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado" . Procedia Informática . 51 : 276-285. doi : 10.1016 / j.procs.2015.05.241 .

[14] Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (1992). Recetas numéricas en C: El arte de la informática científica (2ª ed.). Nueva York: Cambridge University Press. ISBN 0-521-43108-5.

[15] Strutz, T. (2016). Ajuste de datos e incertidumbre: una introducción práctica a los mínimos cuadrados ponderados y más allá (2ª ed.). Springer Vieweg. ISBN 978-3-658-11455-8.

[16] Ross, MI (1 de julio de 2019). "Una teoría de control óptimo para la optimización no lineal" . Revista de Matemática Computacional y Aplicada . 354 : 39–51. doi : 10.1016 / j.cam.2018.12.044 . ISSN 0377-0427 .

[17] Nesterov, Yu. (2004). Conferencias introductorias sobre optimización convexa: un curso básico . Saltador. ISBN 1-4020-7553-7.

[18] Vandenberghe, Lieven (2019). "Métodos de gradiente rápido" (PDF) . Apuntes de conferencias para EE236C en UCLA .

[19] Kim, D .; Fessler, JA (2016). "Métodos optimizados de primer orden para una minimización convexa suave" . Matemáticas. Prog. 151 (1–2): 81–107. arXiv : 1406.5468 . doi : 10.1007 / s10107-015-0949-3 . PMC 5067109 . PMID 27765996 . S2CID 207055414 .

[20] Drori, Yoel (2017). "La complejidad basada en información exacta de la minimización convexa suave". Revista de complejidad . 39 : 1-16. arXiv : 1606.01424 . doi : 10.1016 / j.jco.2016.11.001 . S2CID 205861966 .

[21] Qian, Ning (enero de 1999). "En el término de impulso en algoritmos de aprendizaje de descenso de gradientes" (PDF) . Redes neuronales . 12 (1): 145-151. CiteSeerX 10.1.1.57.5612 . doi : 10.1016 / S0893-6080 (98) 00116-6 . PMID 12662723 . Archivado desde el original (PDF) el 8 de mayo de 2014 . Consultado el 17 de octubre de 2014 .

[22] "Adaptación del impulso y la tasa de aprendizaje" . Universidad de Willamette . Consultado el 17 de octubre de 2014 .

[23] Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del impulso" . Coursera . Consultado el 2 de octubre de 2018 .Parte de una serie de conferencias para el curso en línea de Coursera Neural Networks for Machine Learning Archivado el 31 de diciembre de 2016 en Wayback Machine .

[24] Combettes, PL; Pesquet, J.-C. (2011). "Métodos de división proximal en el procesamiento de señales". En Bauschke, HH; Burachik, RS ; Combettes, PL; Elser, V .; Luke, DR; Wolkowicz, H. (eds.). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Nueva York: Springer. págs. 185–212. arXiv : 0912.3522 . ISBN 978-1-4419-9568-1.

[1]