Skip to main content

# 6: Optimización y Método del Gradiente Descendiente

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Vamos a describir el método del gradiente descente, que sirve para encontrar un punto donde la función $$f: \mathbb{R}^n \rightarrow \mathbb{R}$$ alcanza un valor mínimo.

El proceso se puede resumir en:

• Comenzamos eligiendo un valor arbitrario inicial de x.
• Buscamos la dirección v en la que $$f$$ decrece más rápidamente alrededor de x. A v le llamamos dirección de máximo descenso.
• Variamos “un poco” los valores iniciales en la dirección v:
$\mathbf{x}\rightarrow \textbf{x}+\varepsilon\textbf{v}$

• Repetimos.

​​​​​Nos detenemos ahora en el segundo paso de este proceso: cómo determinar la dirección de descenso más rápido. Como se ha visto en la sección anterior: $f(\textbf{x}+\textbf{v}) \approx f(\textbf{x}) + \textbf{v} \nabla f(\textbf{x}) \, .$ Por la definición de producto escalar, suponiendo que v es un vector de módulo 1, la expresión anterior se escribe $f(\textbf{x}+ \textbf{v} ) \approx f(\textbf{x}) + \textbf{v} \nabla f(\textbf{x}) = f(\textbf{x}) + \|\nabla f (\textbf{x})\|\cos(\theta) \, ,$ donde $$\theta$$ es el ángulo que forman los vectores v y $$\nabla f(\textbf{x})$$.

Con vistas a que $$f$$ decrezca lo más rápido posible, debemos elegir $$\theta$$ de forma que $$cos(\theta)$$ sea lo menor posible, esto es, $$cos(\theta)= -1$$.

Esto ocurre cuando $$\theta$$ vale $$\pi$$ ($$180^0$$) o, lo que es lo mismo, si v tiene el sentido opuesto a $$\nabla f(\textbf{x})$$.
El proceso queda reescrito como:

• Comenzamos eligiendo un valor arbitrario inicial de x.
• La dirección v que hace descender más rápidamente a f alrededor de x es $$-\nabla f(\textbf{x})$$. Calculamos $$\nabla f(\textbf{x})$$.
• Variamos un poco los valores iniciales en la dirección v:
$\mathbf{x}\rightarrow \textbf{x}-\varepsilon\nabla f(\textbf{x})$

• Repetimos.

​​​​​​Para aplicar este algoritmo iterativo es necesario fijar dos parámetros: el número de iteraciones y el valor de $$\varepsilon$$ (que se conoce como tasa de aprendizaje).

• Se dirá que el algoritmo converge si la sucesión de soluciones en el proceso iterativo se acerca a la solución óptima (esto es, el mínimo global). La cantidad de iteraciones que se necesita para que el método del gradiente descendente converja puede variar mucho (dependiendo del problema, desde unas pocas iteraciones hasta miles de ellas). En cualquier caso, la tasa de aprendizaje condicionará el número mínimo de iteraciones necesario para la convergencia.
• La tasa de aprendizaje $$\varepsilon$$ es una constante, con $$0< \varepsilon < 1$$, que afectará de forma significativa la efectividad del algoritmo: un valor demasiado pequeño puede llevar a que el algoritmo precise un número elevado de iteraciones antes de converger; mientras que si el valor asignado es demasiado grande, puede saltarse el mínimo global (pasando a tomar valores mayores) y no proporcionar una buena solución.

Sin embargo, este método no puede asegurar la convergencia al valor que minimiza globalmente la pérdida. La situación idílica sería la de una función de pérdida convexa, con un mínimo global bien definido (imaginémoslo como un paraboloide). Sin embargo, la mayoría de funciones de pérdida para modelos no-lineales son no convexas. Esto significa que pueden poseer varios mínimos locales, que no tienen por qué coincidir con el mínimo global. Al usar el método del gradiente descendente, si el algoritmo llega a un mínimo local, verá que aquí el gradiente es cero y que la pérdida crece en todas las direcciones; pero esto no significa que hayamos encontrado el mínimo global de la pérdida. Al empezar a iterar en un punto aleatorio, no tenemos garantía de que el algoritmo vaya a ir descendiendo hacia el mínimo global. De hecho, lo más probable es que acabe convergiendo en un mínimo local (puesto que habrá más). Aquí es donde nace la necesidad de otros métodos que tomen la idea del gradiente descendente pero que lo lleven un poco más allá para solucionar este problema.

##### Método del gradiente descendente estocástico

Este método trata de solucionar el problema de la convergencia a un mínimo local añadiendo ruido al gradiente en cada iteración. De esta forma, en cada iteración, el gradiente se irá moviendo cuesta abajo en promedio; pero no en la dirección de máximo descenso. De hecho, podría incluso no moverse cuesta abajo en alguna iteración. Esto permite escapar de los mínimos locales para poder acabar llegando al mínimo global.

La forma de introducir aleatoriedad es sencilla: en cada iteración se usa solamente un subset determinado de los datos de entrenamiento para actualizar los pesos; no utiliza todos. De esta forma la actualización quedará sesgada hacia ese subset determinado, la pérdida con respecto a esos datos exclusivamente. Esta actualización puede no hacer que la pérdida total disminuya. La regla de actualización es:

$\phi_{t+1}=\phi_{t}-\varepsilon \sum_{i\in B_{t}}\frac{\partial l_{i}[\phi]}{\partial \phi}$

$$B_{t}$$ es el subset de datos que se usarán en cada iteración para actualizar la pérdida. En la práctica, es como si en cada iteración se estuviera minimizando una pérdida distinta. Si se elige ese subset para que contenga todos los datos, recuperamos el método del gradiente descendente habitual. El lector podría preguntarse por qué este método, que debería ser peor puesto que usa menos datos, ofrece mejores resultados que el convencional. Existen una serie de propiedades interesantes:

1. Los elementos usados en cada iteración se eligen sin reemplazamiento, por lo que acaban contribuyendo todos los elementos por igual.
2. Es computacionalmente más eficiente usar este método puesto que solo se calcula el gradiente de un pequeño set de datos.
3. Permite escapar mínimos locales por el ruido añadido.
4. Reduce las posibilidades de atascarse en puntos de silla (donde el gradiente es cero, pero no son mínimos locales ni globales).​​​
##### ADAM (Adaptive Moment Estimation)

Es otro método que trata de mejorar el método del gradiente descendente. En este caso lo hace añadiendo un momento, es decir, los parámetros se actualizan con una media ponderada de todos los gradientes anteriores. En particular, pondera el valor actual y el de la iteración previa (que también fue calculado usando los demás). La regla de actualización es la siguiente:

$m_{t+1}=\beta m_{t} + (1- \beta) \sum_{i\in B_{t}} \frac{\partial l_{i}[\phi]}{\partial \phi}$

$\phi_{t+1}=\phi_{t}-\varepsilon m_{t+1}$

$$m_{t}$$ es el momento en la t-ésima iteración y $$\beta$$ controla cuánto se ponderan los gradientes anteriores con respecto al nuevo. Cada paso es una suma ponderada de los gradientes anteriores. Esto permite tener una trayectoria más suave y un menor comportamiento oscilatorio en los valles. Vemos que la suma sigue siendo sobre un subset, así que funciona igual que el gradiente descendiente estocástico, heredando sus propiedades.

Otro añadido que hace ADAM es solucionar el siguiente problema: gradientes mayores llevan a mayores ajustes de los parámetros (cuando quizás habría que ser más cauteloso) y gradientes pequeños llevan a ajustes muy pequeños en los parámetros (cuando quizás habría que explorar más allá). La solución a este problema es normalizar los gradientes para que, en cada paso, el avance esté dado siempre por la tasa de aprendizaje y el gradiente simplemente indique la dirección. Es decir:

$v_{t+1}=\left(\frac{\partial L[\phi]}{\partial \phi}\right) ^2 \longrightarrow \phi_{t+1}=\phi_{t}-\varepsilon \frac{m_{t+1}}{\sqrt{v_{t+1}}+\varphi}$

La suma de $$\varphi$$ es para evitar la división por cero cuando el módulo del gradiente es muy pequeño. Ahora estamos realizando una media ponderada sobre la historia de todos los gradientes. Otra posible mejora es añadir momento (considerar los previos valores) tanto en el gradiente como en su cuadrado:

$m_{t+1}=\beta m_{t} + (1- \beta) \sum_{i\in B_{t}} \frac{\partial l_{i}[\phi]}{\partial \phi}$

$v_{t+1}=\gamma v_{t} + (1- \gamma) \sum_{i\in B_{t}} \left(\frac{\partial l_{i}[\phi]}{\partial \phi}\right)^2$

Un problema que se plantea ahora es que siempre estamos usando la misma ponderación de los nuevos datos: para las primeras iteraciones (donde tenemos muy pocos datos y debería ponderarse mucho el nuevo valor) y para las últimas (donde ya van muchos datos calculados y tendrían que ponderar poco los nuevos datos). Esta ponderación se incorpora mediante:

$\hat{m}_{t+1}=\frac{m_{t+1}}{1-\beta^{t+1}}$

$\hat{v}_{t+1}=\frac{v_{t+1}}{1-\gamma^{t+1}}$

$\phi_{t+1}=\phi_{t}-\varepsilon \frac{\hat{m}_{t+1}}{\sqrt{\hat{v}_{t+1}}+\varphi}$

Este algoritmo converge más fácilmente al mínimo global de la pérdida y se mueve adecuadamente en todas las direcciones del espacio de parámetros.

6: Optimización y Método del Gradiente Descendiente is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.

• Was this article helpful?