Algoritmo de descenso de gradiente y sus variantes

Gradient Descent es un algoritmo de optimización utilizado para minimizar la función de costo en varios algoritmos de aprendizaje automático. Se utiliza básicamente para actualizar los parámetros del modelo de aprendizaje.

Tipos de pendiente Descenso:

1. Descenso de gradiente por lotes: Este es un tipo de descenso de gradiente que procesa todos los ejemplos de entrenamiento para cada iteración de descenso de gradiente. Pero si el número de ejemplos de entrenamiento es grande, entonces el descenso de gradiente por lotes es computacionalmente muy costoso. Por lo tanto, si el número de ejemplos de entrenamiento es grande, no se prefiere el descenso de gradiente por lotes. En su lugar, preferimos utilizar el descenso de gradiente estocástico o el descenso de gradiente de mini lotes.
2. Descenso de gradiente estocástico: Este es un tipo de descenso de gradiente que procesa 1 ejemplo de entrenamiento por iteración. Por lo tanto, los parámetros se actualizan incluso después de una iteración en la que solo se ha procesado un único ejemplo. Por lo tanto, esto es bastante más rápido que el descenso de gradiente por lotes. Pero nuevamente, cuando la cantidad de ejemplos de entrenamiento es grande, incluso entonces procesa solo un ejemplo, lo que puede ser una sobrecarga adicional para el sistema, ya que la cantidad de iteraciones será bastante grande.
3. Descenso de gradiente mini por lotes: este es un tipo de descenso de gradiente que funciona más rápido que el descenso de gradiente por lotes y el descenso de gradiente estocástico. Aquí b ejemplos donde b<m se procesan por iteración. Entonces, incluso si la cantidad de ejemplos de entrenamiento es grande, se procesa en lotes de ejemplos de entrenamiento b de una sola vez. Por lo tanto, funciona para ejemplos de entrenamiento más grandes y también con un número menor de iteraciones.

 
Variables utilizadas:
Sea m el número de ejemplos de entrenamiento.
Sea n el número de características.

Nota: si b == m, entonces el descenso de gradiente por lotes mini se comportará de manera similar al descenso de gradiente por lotes.

Algoritmo para el descenso del gradiente por lotes:
Sea h _θ (x) la hipótesis para la regresión lineal. Entonces, la función de costo viene dada por:
Sea Σ la suma de todos los ejemplos de entrenamiento desde i=1 hasta m.

Jtrain(θ) = (1/2m) Σ( hθ(x(i))  - y(i))2

Repeat {
 θj = θj – (learning rate/m) * Σ( hθ(x(i))  - y(i))xj(i)
    For every j =0 …n 
}

Donde x _j ⁽ⁱ⁾ representa la j ^-ésima característica del i ^-ésimo ejemplo de entrenamiento. Entonces, si m es muy grande (p. ej., 5 millones de muestras de entrenamiento), se necesitan horas o incluso días para converger al mínimo global. Por eso, para grandes conjuntos de datos, no se recomienda usar el descenso de gradiente por lotes, ya que ralentiza el aprendizaje.

 
Algoritmo para el descenso de gradiente estocástico:
1) Mezcla aleatoriamente el conjunto de datos para que los parámetros se puedan entrenar de manera uniforme para cada tipo de datos.
2) Como se mencionó anteriormente, toma en consideración un ejemplo por iteración.

Hence,
Let (x(i),y(i)) be the training example
Cost(θ, (x(i),y(i))) = (1/2) Σ( hθ(x(i))  - y(i))2

Jtrain(θ) = (1/m) Σ Cost(θ, (x(i),y(i)))

Repeat {

For i=1 to m{

         θj = θj – (learning rate) * Σ( hθ(x(i))  - y(i))xj(i)
        For every j =0 …n

                } 
}

 
Algoritmo para descenso de gradiente de mini lotes:
digamos que b es el número de ejemplos en un lote, donde b < m.
Suponga que b = 10, m = 100;

Nota: Sin embargo, podemos ajustar el tamaño del lote. Por lo general, se mantiene como una potencia de 2. La razón detrás de esto es que algunos hardware, como las GPU, logran un mejor tiempo de ejecución con tamaños de lote comunes, como la potencia de 2.

Repeat {
 For i=1,11, 21,…..,91

    Let Σ be the summation from i to i+9 represented by k. 

    θj = θj – (learning rate/size of (b) ) * Σ( hθ(x(k))  - y(k))xj(k)
        For every j =0 …n

}

 

Tendencias de convergencia en diferentes variantes de Gradient Descents:

En el caso de Descenso de gradiente por lotes, el algoritmo sigue un camino recto hacia el mínimo. Si la función de costo es convexa, entonces converge a un mínimo global y si la función de costo no es convexa, entonces converge a un mínimo local. Aquí, la tasa de aprendizaje generalmente se mantiene constante.

En caso de descenso de gradiente estocástico y descenso de gradiente de mini lotes, el algoritmo no converge sino que continúa fluctuando alrededor del mínimo global. Por lo tanto, para que converja, tenemos que cambiar lentamente la tasa de aprendizaje. Sin embargo, la convergencia del descenso de gradiente estocástico es mucho más ruidosa ya que en una iteración procesa solo un ejemplo de entrenamiento.