El método del gradiente conjugado es un algoritmo utilizado para la optimización de funciones convexas. Se utiliza principalmente en problemas de optimización numérica, como la minimización de funciones cuadráticas o la resolución de sistemas de ecuaciones lineales.

En el contexto del machine learning, el método del gradiente conjugado puede utilizarse para optimizar funciones objetivo, como la función de costo en algoritmos de aprendizaje supervisado, como regresión lineal o logística, y en algoritmos de aprendizaje no supervisado, como el análisis de componentes principales (PCA).

La idea principal detrás del método del gradiente conjugado es encontrar el mínimo de una función minimizando su gradiente, buscando la dirección en la que la función decrece rápidamente. Sin embargo, en lugar de avanzar en la dirección del gradiente en cada paso, el método del gradiente conjugado busca una dirección "conjugada" que permita converger más eficientemente hacia el mínimo.

¿Qué es una dirección conjugada?

El algoritmo del gradiente conjugado se basa en calcular sucesivas direcciones conjugadas y ajustar el tamaño de paso en cada dirección para minimizar la función objetivo. Esto se logra mediante la búsqueda de línea en cada dirección conjugada.

Este algoritmo es más eficiente resolviendo problemas lineares que el descenso del gradiente:

¿Qué es el descenso del gradiente?

Donde A es simétrica y positiva definida.

En una búsqueda de línea determinamos la dirección de ascenso más pronunciada y luego seleccionamos el tamaño del paso. Por ejemplo, en el método de ascenso de gradiente, tomamos un tamaño de paso igual al gradiente multiplicado por la tasa de aprendizaje. Para la figura de la izquierda a continuación, la dirección más profunda según el contorno del gradiente (el eclipse punteado) se mueve hacia la derecha. El siguiente movimiento puede ir hacia arriba y ligeramente hacia la izquierda según la pendiente más pronunciada en el punto actual. El problema es que al girar ligeramente hacia la izquierda estamos deshaciendo parte del progreso.

El método de gradiente conjugado es un método de Búsqueda Lineal, pero para cada movimiento, no deshace parte de los movimientos realizados anteriormente, como hemos visto que hace el ascenso del gradiente. Optimiza una ecuación cuadrática en menos pasos que el ascenso de gradiente. Si x es N-dimensional (N parámetros), podemos encontrar el punto óptimo en como máximo N pasos. Para cada movimiento, queremos una dirección conjugada con todos los movimientos anteriores. Esto garantiza que no deshacemos parte de los movimientos que hicimos. En resumen, si x es de 4 dimensiones, se deberían necesitar como máximo 4 movimientos para alcanzar el punto óptimo.

¿Qué es la Búsqueda Lineal?

1. 1. Iniciamos el ascenso en una dirección particular.

2. 2. Nos instalamos en el punto óptimo para esa dirección.

3. 2. Encontramos una nueva dirección $d_{(j)}$ que es $A$-conjugada con cualquier dirección de movimiento anterior $d_{(i)}$.

Matemáticamente, significa que cualquier nueva dirección $d_{(j)}$ debe obedecer al conjugado $A$ con todas las direcciones anteriores $d_{(i)}$:

Donde:

1. 1. $d_{(i)}^T$ representa la transpuesta de $d_{(i)}$.

2. 2. $A$ es una matriz simétrica definida positiva.

3. 2. $d_{(j)}$ es otro vector.

Donde $A$ es la matriz en la ecuación cuadrática. A continuación, se muestran algunos otros ejemplos de vectores conjugados $A$ en el espacio 2D.

Los vectores $A$-conjugados son independientes entre sí. Por lo tanto, N vectores conjugados pueden abarcar un espacio de N dimensiones.

La parte clave del método CG es encontrar $α$ y $d$. Aquí hay un resumen de cómo se encuentran $α$ y $d$ en cada iteración del método CG:

1. 1. Dirección de búsqueda ($d$): En cada iteración del método CG, se calcula una dirección de búsqueda $d$, conjugada con respecto a las direcciones de búsqueda anteriores. Esto se hace para asegurar que el método de gradiente conjugado converja de manera eficiente hacia la solución del problema. La fórmula para calcular $d$ se basa en la dirección del gradiente negativo y las direcciones de búsqueda anteriores.

   

   En la imagen se puede observar que la dirección 2 es conjugada (ortogonal) a su dirección anterior 1.

2. 2. Longitud del paso ($α$): Una vez que se ha calculado la dirección de búsqueda $d$, se determina la longitud del paso $α$ a lo largo de esta dirección. Este paso es crucial ya que determina qué tan lejos moverse desde el punto actual en la dirección de búsqueda $d$. La longitud del paso $α$ se calcula para minimizar la función objetivo a lo largo de la dirección de búsqueda $d$.

   

   En la imagen de arriba se puede ver la importancia de calcular dicha longitud, porque si no lo hacemos y elegimos una al azar, puede suceder que sea menor o mayor de lo necesario y no alcancemos el punto óptimo.

Algoritmo

A continuación se explicará paso a paso el algoritmo del Método del Gradiente Conjugado.

Comenzamos con una suposición aleatoria (o fundamentada) para la solución en $X$ ($X_{0}$) y calculamos la siguiente suposición $X_{1}$ con $α$ y $d$.

$r_{0}:=b-Ax_{0}$

Se establece $d_{0}$ como la dirección de búsqueda inicial.

$d_{0}:=r_{0}$

$k:=0$

Se inicializa $k$ que servirá como iterador en el ciclo de búsqueda del punto óptimo.

$Inicio-Ciclo$

$α_{k}:=\frac{r_{k}^Tr_{k}}{d_{k}^TAd_{k}}$

* $α_{k}$ es el tamaño del paso en la k-ésima iteración, que se utiliza para actualizar la solución en esa iteración.

* El superíndice $T$ denota la transposición.
* $r_{k}$ es el residuo en la k-ésima iteración del algoritmo del gradiente conjugado.
* $d_{k}$ es la dirección de búsqueda en la k-ésima iteración.
* $A$ es la matriz simétrica y definida positiva asociada al problema de optimización.

$x_{k+1}$ es el siguiente punto al que nos debemos mover. Esta fórmula actualiza la solución $x$ en la k-ésima iteración ($x_{k}$) moviéndola a lo largo de la dirección de búsqueda $d_{k}$ multiplicada por el tamaño del paso $α_{k}$, lo cual nos lleva a la nueva posición $x_{k+1}$.

$x_{k+1}:=x_{k}+α_{k}d_{k}$

$r_{k+1}:=r_{k}-α_{k}Ad_{k}$

* $r_{k+1}$ es el error restante desde el punto óptimo al que nos moveremos.
* $r_{k}$ es el residuo en la k-ésima iteración.
* $α_{k}$ es el tamaño del paso o longitud del paso en la dirección de búsqueda.
* $Ad_{k}$ es la dirección conjugada en la k-ésima iteración.
Aquí, $α_{k}$ se ajusta para minimizar la función en la dirección de búsqueda $Ad_{k}$, lo que garantiza que el método avance hacia el mínimo de manera eficiente. La dirección conjugada es esencial porque asegura que la búsqueda se realice en direcciones ortogonales a las iteraciones anteriores, lo que evita el retraso en la convergencia y acelera el proceso de optimización

Si el nuevo residuo $r_{k+1}$ es más pequeño que un valor arbitrario (en este caso 0.05), salimos del ciclo. Esto se debe a que un residuo pequeño indica que la diferencia entre el punto actual y el punto óptimo es insignificante, lo que sugiere que la solución encontrada es cercana a la solución óptima.

$Si (r_{k+1} < 0.05): Final-Ciclo$

$β_{k}:=\frac{r_{k+1}^Tr_{k+1}}{r_{k}^Tr_{k}}$

El coeficiente $β_{k}$ se utiliza para ponderar la influencia de la dirección de búsqueda en la iteración anterior en la dirección de búsqueda actual. Esto ayuda a garantizar que las direcciones de búsqueda en iteraciones sucesivas sean conjugadas entre sí, lo que puede conducir a una convergencia más rápida hacia el mínimo de la función objetivo. Este coeficiente se calcula mediante el método de Método de Fletcher-Reeves.

$β_{k}d_{k}$ es la nueva dirección A-Ortogonal. Se utiliza en el algoritmo del gradiente conjugado para actualizar la dirección de búsqueda en la k-ésima iteración ($d_{k}$) a la siguiente iteración ($d_{k+1}$). La idea detrás de esta actualización es garantizar que las direcciones de búsqueda en iteraciones sucesivas sean conjugadas entre sí, lo que mejorara la convergencia del algoritmo del gradiente conjugado.

$d_{k+1}:=r_{k+1}+β_{k}d_{k}$

$k:=k+1$

Se suma 1 a $k$ para la siguiente iteración.

$Final-Ciclo$

Ejemplo

Supongamos que tenemos los siguientes vectores:

También usaremos como parámetro de corte si el residuo es menor a 0.05.

Calculamos $r_{0}$ y $d_{0}$:

Ahora entramos en el bucle:

1. Ciclo 1:

   $$α_{k}:=\frac{r_{k}^Tr_{k}}{d_{k}^TAd_{k}}\rightarrow\frac{\begin{bmatrix} 1 & 2 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \end{bmatrix}}{\begin{bmatrix} 1 & 2 \end{bmatrix}\begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \end{bmatrix}}\rightarrow0.25$$
   $$x_{k+1}:=x_{k}+α_{k}d_{k}\rightarrow\begin{bmatrix} 0 \\ 0 \end{bmatrix}+0.25\begin{bmatrix} 1 \\ 2 \end{bmatrix}\rightarrow\begin{bmatrix} 0.25 \\ 0.5 \end{bmatrix}$$
   $$r_{k+1}:=r_{k}-α_{k}Ad_{k}\rightarrow\begin{bmatrix} 1 \\ 2 \end{bmatrix}-0.25\begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \end{bmatrix}\rightarrow\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}$$
   $$Si (r_{k+1} < 0.05): Final-Ciclo$$

   Calculamos la norma del vector $r_{k+1}$ que es 0.55. Dado que no es menor a 0.05, no salimos del ciclo.

   $$β_{k}:=\frac{r_{k+1}^Tr_{k+1}}{r_{k}^Tr_{k}}\rightarrow\frac{\begin{bmatrix} -0.5 & 0.25 \end{bmatrix}\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}}{\begin{bmatrix} 1 & 2 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \end{bmatrix}}\rightarrow0.0625$$
   $$d_{k+1}:=r_{k+1}+β_{k}d_{k}\rightarrow\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}+0.0625\begin{bmatrix} 1 \\ 2 \end{bmatrix}\rightarrow\begin{bmatrix} -0.4375 \\ 0.375 \end{bmatrix}$$

2. Ciclo 2:

   $$α_{k}:=\frac{r_{k}^Tr_{k}}{d_{k}^TAd_{k}}\rightarrow\frac{\begin{bmatrix} -0.5 & 0.25 \end{bmatrix}\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}}{\begin{bmatrix} -0.4375 & 0.375 \end{bmatrix}\begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} -0.4375 \\ 0.375 \end{bmatrix}}\rightarrow0.3636$$
   $$x_{k+1}:=x_{k}+α_{k}d_{k}\rightarrow\begin{bmatrix} 0.25 \\ 0.5 \end{bmatrix}+0.3636\begin{bmatrix} -0.4375 \\ 0.375 \end{bmatrix}\rightarrow\begin{bmatrix} 0.09090909 \\ 0.63636364 \end{bmatrix}$$
   $$r_{k+1}:=r_{k}-α_{k}Ad_{k}\rightarrow\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}-0.3636\begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} -0.4375 \\ 0.375 \end{bmatrix}\rightarrow\begin{bmatrix} -0.5 \\ 0.25 \end{bmatrix}-0.3636\begin{bmatrix} -1,375 \\ 0,6875 \end{bmatrix}\rightarrow\begin{bmatrix} 0 \\ 0 \end{bmatrix}$$
   $$Si (r_{k+1} < 0.05): Final-Ciclo$$

   Calculamos la norma del vector $r_{k+1}$ que es 0, un valor menor a 0.05, por lo tanto, damos por terminado el procedimiento.

En el contexto del machine learning, podemos usar las direcciones de búsqueda que calculamos en este procedimiento junto con algún otro método como Búsqueda Lineal para actualizar los parámetros de nuestro modelo y de esa manera mejorar el rendimiento.

Conclusiones:

El método del gradiente conjugado es una herramienta poderosa y eficiente para resolver una variedad de problemas de optimización en ciencia de la computación, ingeniería y aprendizaje automático, gracias a su rápida convergencia y menor requerimiento de memoria. Este método se puede aplicar en una variedad de problemas de machine learning y aprendizaje automático, especialmente en aquellos que involucran optimización de funciones no lineales y restricciones de región de confianza. Su eficiencia y capacidad para manejar problemas grandes lo hacen útil en una variedad de contextos en machine learning.

Hemos llegado al final de este artículo. Espero que te halla resultado útil y que hallas disfrutado leyéndolo tanto como yo disfrute escribiéndolo 😁.