Descenso del gradiente

El descenso del gradiente o gradiente descendiente es un algoritmo de optimización iterativo de primer orden que permite encontrar mínimos locales en una función diferenciable. La idea es tomar pasos de manera repetida en dirección contraria al gradiente. Esto se hace ya que esta dirección es la del descenso más empinado. Si se toman pasos con la misma dirección del gradiente, se encontrará el máximo local de la función; a esto se le conoce como el gradiente ascendente. Este algoritmo es utilizado para entrenar modelos de aprendizaje máquina y redes neuronales.

Descenso del gradiente en 2D

Historia

El gradiente descendiente se le atribuye generalmente a Augustin-Louis Cauchy, quien fue el primero en sugerirlo en 1847​. Jacques Hadamard propuso un métodos similar en 1907​. Haskell Curry fue el primero en estudiar las propiedades de convergencia para problemas de optimización no lineal en 1944​. Desde entonces el método ha sido estudiado y utilizado a fondo.​

Requisitos

Para poder utilizar el algoritmo del gradiente descendiente la función de la cual se desea encontrar el mínimo local debe cumplir con lo siguiente:

1. La función debe ser diferenciable.
2. La función debe ser convexa:

Una función f es convexa si:

$f(\lambda x_{1}+(1-\lambda )x_{2})<\lambda f(x_{1})+(1-\lambda )f(x_{2})$

donde:

$\lambda \in \mathbb {R}$,

$0\leq \lambda \leq 1$

Descripción

Idea General​

Para una función $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ en un punto $p=(x_{1},...,x_{n})$ su gradiente se define como:

$\nabla f(p)={\begin{vmatrix}{\delta f \over \delta x_{1}}(p)\\\vdots \\{\delta f \over \delta x_{n}}(p)\end{vmatrix}}$

El gradiente descendiente calcula iterativamente el siguiente punto utilizando el gradiente del punto actual. Este punto es escalado con una razón de aprendizaje $\gamma \in \mathbb {R} ^{+}$. Se tiene entonces que el gradiente descendiente utiliza la siguiente expresión:

$p_{n+1}=p_{n}-\gamma \nabla f(p_{n})$

Algoritmo

El algoritmo del gradiente descendiente calcula iterativamente el siguiente punto usando el gradiente del punto en turno. Lo escala con la razón de aprendizaje y resta este resultado a la posición actual. Si la razón  de aprendizaje es muy pequeña, el algoritmo tarda en converger. Si la razón de aprendizaje es muy grande, el algoritmo puede no llegar a converger. El algoritmo del gradiente descendiente consta de los siguientes pasos:

1. Se elige un punto de salida de manera aleatoria,
2. Se calcula el gradiente en ese punto,
3. Se determina el siguiente punto de acuerdo con: $p_{n+1}=p_{n}-\gamma \nabla f(p_{n})$
4. Se detiene el algoritmo con una de las siguientes condiciones de paro:
   • Se llega a un número máximo de iteraciones predeterminado.
   • El tamaño del paso dado por el algoritmo es menor que un valor de tolerancia establecido.

Implementación en Python

import numpy as np
from typing import Callable, Tuple, List

def grad_desc(x: np.array, f: Callable, gf: Callable, lr=0.01, maxiter=100, tol=0.001) -> Tuple[np.array, List[np.array], int]:
    """
    Esta función implementa el algoritmo de descenso por gradiente para minimizar una función de 
    múltiples variables. Comienza en un punto inicial x y realiza actualizaciones iterativas 
    utilizando el gradiente de la función objetivo con un factor de aprendizaje fijo especificado.
    El proceso se repite hasta que la norma del gradiente cae por debajo de una tolerancia o se
    alcanza un número máximo de iteraciones.

    Args:
        x (np.array): Punto inicial.
        f (Callable): Función objetivo a minimizar.
        gf (Callable): Gradiente de la función objetivo.
        lr (float, optional): Factor de aprendizaje. Por defecto es 0,01.
        maxiter (int, optional): Número máximo de iteraciones. Por defecto es 100.
        tol (float, optional): Tolerancia para la norma del gradiente que determina la convergencia. 

    Returns:
        Tuple[np.ndarray, List[np.array], int]: Una tupla con tres elementos:
            - El punto aproximado al mínimo.
            - Una lista de puntos intermedios (arrays) calculados durante la optimización.
            - El número de iteraciones realizadas.
            
    Ejemplo de uso:
    
        def funcion_objetivo(x):
            return x[0]**2 + x[1]**2

        def gradiente_funcion_objetivo(x):
            return np.array([2 * x[0], 2 * x[1]])

        punto_inicial = np.array([3, 4])

        # Aplicar el descenso por gradiente
        resultado, puntos, iteraciones = grad_desc(punto_inicial, funcion_objetivo, gradiente_funcion_objetivo)
    """
    points = []  
    nit = 0
    gradient = gf(x)

    while nit < maxiter and np.linalg.norm(gradient) >= tol:

        x =  x - lr * gradient 
        
        gradient = gf(x)
        points.append(x)
        nit += 1

    return x, points, nit

Tipos de Gradiente Descendiente​

Con sondeo lineal

El descenso de gradiente con sondeo lineal guarda una notable similitud con el algoritmo del gradiente descendiente convencional. La distinción principal radica en que, en cada iteración, el valor del factor de aprendizaje 𝛾 se ajusta mediante la minimización de una nueva función unidimensional de la forma: $g(\gamma )=f(p_{n}-\gamma \nabla f(p_{n}))$, donde la única variable involucrada es $\gamma$. Esta característica permite aprovechar técnicas de optimización unidimensional, como la búsqueda de la sección dorada o la trisección, para determinar el valor óptimo de $\gamma$.

Batch

El gradiente descendiente batch suma el error para cada punto en un conjunto de entrenamiento, actualizando el modelo hasta que se hayan evaluado todos los ejemplos de entrenamiento disponibles. El proceso de batch provee mayor eficiencia a nivel computacional para conjuntos de datos grandes. Usualmente produce un error de gradiente estable y llega a converger.

Estocástico

El descenso de gradiente estocástico corre una época de entrenamiento para cada ejemplo en el conjunto de datos y actualiza los parámetros de cada ejemplo de entrenamiento uno a la vez. El gradiente descendiente estocástico realiza menos operaciones por actualización que el gradiente descendiente tradicional.

Mini-Batch

Combina elementos del gradiente descendiente batch y del gradiente descendiente estocástico. Divide el conjunto de entrenamiento en subconjuntos más pequeños y actualiza los parámetros de cada subconjunto.

Problemas del Gradiente Descendiente

Gradiente Explosivo

Este problema se presenta cuando el gradiente es demasiado grande, creando un modelo inestable. En este caso los pesos o ponderaciones asignados en el modelo crecerán demasiado. Una solución a este problema es utilizar una técnica para reducir la dimensionalidad y así reducir la complejidad del modelo.

Desvanecimiento del Gradiente

Durante el entrenamiento o ajuste de los parámetros de una red neuronal se utiliza la propagación hacia atrás con gradiente descendiente. Con cada iteración o paso el gradiente se hace más y más pequeño conforme la propagación hacia atrás llega a capas más profundas; el gradiente se desvanece. Esto trae como consecuencia que no se actualizan las conexiones de las capas más bajas o profundas y por lo tanto el entrenamiento no converge a una solución que sea de utilidad.