El descenso de gradiente estocástico (en inglés: Stochastic gradient descent, a menudo abreviado como SGD) es un método iterativo para optimizar una función objetivo con propiedades de suavidad adecuadas (por ejemplo, diferenciable o subdiferenciable). Puede considerarse una aproximación estocástica de la optimización por descenso de gradiente, ya que sustituye el gradiente real (calculado a partir de todo el conjunto de datos) por una estimación del mismo (calculada a partir de un subconjunto de datos seleccionados aleatoriamente). Especialmente en problemas de optimización de alta dimensión, esto reduce la elevadísima carga computacional, consiguiendo iteraciones más rápidas a cambio de una menor tasa de convergencia.
Aunque la idea básica de la aproximación estocástica se remonta al algoritmo Robbins-Monro de la década de 1950, el descenso de gradiente estocástico se ha convertido en un importante método de optimización en el aprendizaje automático.
Antecedentes Tanto la estimación estadística como el aprendizaje automático consideran el problema de minimizar una función objetivo que tiene la forma de una suma:
en la que el parámetro que minimiza será estimado. Cada una de las funciones sumando suele estar asociada a la observación -n del conjunto de datos (utilizado para el entrenamiento).
En la estadística clásica, los problemas de minimización de sumas surgen en los mínimos cuadrados y en la estimación de máxima verosimilitud (para observaciones independientes). La clase general de estimadores que surgen como minimizadores de sumas se denominan estimadores M (o M-estimador). Sin embargo, en estadística se reconoce desde hace tiempo que exigir incluso una minimización local es demasiado restrictivo para algunos problemas de estimación de máxima verosimilitud. Por lo tanto, los teóricos estadísticos contemporáneos suelen considerar puntos estacionarios de la función de verosimilitud (o ceros de su derivada, la función de puntuación y otras ecuaciones de estimación).
El problema de minimización de la suma también se plantea en la minimización del riesgo empírico. En este es el valor de la función de pérdida en el ejemplo de -n, y es el riesgo empírico.
Cuando se utiliza para minimizar la función anterior, un método de descenso de gradiente estándar (o "por lotes") realizaría las siguientes iteraciones:
donde es un step size (a veces llamado tasa de aprendizaje en el aprendizaje automático).
En muchos casos, las funciones sumando tienen una forma simple que permite evaluaciones económicas de la función suma y del gradiente de la suma. Por ejemplo, en estadística, las familias exponenciales de un parámetro permiten evaluaciones económicas de la función y del gradiente.
Sin embargo, en otros casos, la evaluación del gradiente de la suma puede requerir costosas evaluaciones de los gradientes de todas las funciones sumando. Cuando el conjunto de entrenamiento es enorme y no existen fórmulas sencillas, la evaluación de las sumas de gradientes resulta muy costosa, porque evaluar el gradiente requiere evaluar todos los gradientes de las funciones sumando. Para economizar el coste computacional en cada iteración, el descenso de gradiente estocástico muestrea un subconjunto de funciones sumando en cada paso (en inglés: step). Esto resulta muy eficaz en el caso de problemas de aprendizaje automático a gran escala.
Método iterativo miniaturadeimagen|Fluctuaciones en la función objetivo total a medida que se dan pasos de gradiente con respecto a minilotes. En el descenso de gradiente estocástico (o "en línea"), el verdadero gradiente de se aproxima por un gradiente en una sola muestra:
A medida que el algoritmo recorre el conjunto de entrenamiento, realiza la actualización anterior para cada muestra de entrenamiento. Se pueden realizar varias pasadas por el conjunto de entrenamiento hasta que el algoritmo converja. Si se hace esto, los datos pueden barajarse en cada pasada para evitar ciclos. Las implementaciones típicas pueden utilizar una tasa de aprendizaje adaptativa para que el algoritmo converja.
En pseudocódigo, el descenso de gradiente estocástico puede presentarse como: Elegir un vector inicial de parámetros y tasa de aprendizaje . Repita la operación hasta obtener un mínimo aproximado: Barajar aleatoriamente las muestras del conjunto de entrenamiento. Para , realizar:
Un compromiso entre calcular el gradiente verdadero y el gradiente en una sola muestra es calcular el gradiente contra más de una muestra de entrenamiento (llamado "mini-lote") en cada paso. Esto puede funcionar significativamente mejor que el descenso de gradiente estocástico "verdadero" descrito, porque el código puede hacer uso de bibliotecas de vectorización en lugar de calcular cada fase por separada, como se mostró por primera vez en el llamado "algoritmo de retropropagación en modo de lote". También puede dar lugar a una convergencia más suave, ya que el gradiente calculado en cada paso se promedia sobre más muestras de entrenamiento.
La convergencia del descenso de gradiente estocástico se ha analizado utilizando las teorías de la minimización convexa y de la aproximación estocástica. Brevemente, cuando las tasas de aprendizaje disminuyen con una tasa apropiada, y sujeto a supuestos relativamente suaves, el descenso de gradiente estocástico converge casi seguro a un mínimo global cuando la función objetivo es convexa o pseudoconvexa, y en caso contrario converge casi con seguridad a un mínimo local. Esto es, de hecho, una consecuencia del teorema de Robbins-Siegmund.
Ejemplo Supongamos que queremos ajustar una recta a un conjunto de entrenamiento con observaciones y las correspondientes respuestas estimadas utilizando mínimos cuadrados. La función objetivo a minimizar es:
La última línea del pseudocódigo anterior para este problema específico se convertirá en:
Nótese que en cada iteración (también llamada actualización), el gradiente sólo se evalúa en un único punto en lugar de en el conjunto de todas las muestras.
La diferencia clave en comparación con el descenso gradiente estándar (por lotes) es que sólo se utiliza un dato del conjunto de datos para calcular el paso, y el dato se elige aleatoriamente en cada paso.
Aplicaciones destacadas El descenso de gradiente estocástico es un algoritmo popular para entrenar una amplia gama de modelos de aprendizaje automático, incluyendo las máquinas de vectores de soporte (lineales), la regresión logística (véase, por ejemplo, Vowpal Wabbit) y los modelos en grafo. Combinado con el algoritmo de retropropagación, es el algoritmo estándar de facto para el entrenamiento de redes neuronales artificiales. También se ha informado de su uso en la comunidad geofísica, concretamente en aplicaciones de inversión de forma de onda completa (en inglés: Full Waveform Inversion, FWI).
El descenso de gradiente estocástico compite con el algoritmo L-BFGS, que también es ampliamente utilizado. El descenso de gradiente estocástico se ha utilizado al menos desde 1960 para el entrenamiento de modelos de regresión lineal, originalmente bajo el nombre de ADALINE.
Otro algoritmo de descenso de gradiente estocástico es el filtro adaptativo de mínimos cuadrados medios (en inglés: Least-Mean-Square algorithm, LMS).
Extensiones y variantes Se han propuesto y utilizado muchas mejoras del algoritmo básico de descenso de gradiente estocástico. En particular, en el aprendizaje automático, se ha reconocido que la necesidad de establecer una tasa de aprendizaje (step size) es problemática. Si se fija un parámetro demasiado alto, el algoritmo puede divergir; si se fija demasiado bajo, la convergencia es lenta. Una extensión conceptualmente simple del descenso de gradiente estocástico hace que la tasa de aprendizaje sea una función decreciente del número de iteraciones , dando un programa de tasa de aprendizaje, de modo que las primeras iteraciones causen grandes cambios en los parámetros, mientras que las posteriores sólo hacen un ajuste fino. Tales programas se conocen desde el trabajo de MacQueen sobre la agrupación -medias. Spall ofrece orientación práctica sobre la elección del step size en diversas variantes de SGD.
Actualizaciones implícitas (ISGD) Como ya se ha mencionado, el descenso de gradiente estocástico clásico suele ser sensible a la tasa de aprendizaje . Una convergencia rápida requiere grandes tasas de aprendizaje, pero esto puede inducir inestabilidad numérica. El problema puede resolverse en gran medida considerando actualizaciones implícitas en las que el gradiente estocástico se evalúa en la siguiente iterada en lugar de en la actual:
Esta ecuación está implícita ya que aparece en ambos lados de la ecuación. Se trata de una forma estocástica del método del gradiente proximal, ya que la actualización también puede escribirse como:
A modo de ejemplo, consideremos los mínimos cuadrados con características y observaciones . Queremos resolver:
en el que indica el producto interior. Obsérvese que podría tener "1" como primer elemento para incluir un intercepto. El descenso de gradiente estocástico clásico procede de la siguiente manera:
donde se muestrea uniformemente entre 1 y . Aunque la convergencia teórica de este procedimiento se produce bajo supuestos relativamente suaves, en la práctica el procedimiento puede ser bastante inestable. En particular, cuando está mal especificado de modo que tiene grandes valores propios absolutos con alta probabilidad, el procedimiento puede divergir numéricamente en unas pocas iteraciones. Por el contrario, el descenso de gradiente estocástico implícito (abreviado como ISGD) puede resolverse de forma cerrada como:
Este procedimiento se mantendrá numéricamente estable prácticamente para todas las ya que la tasa de aprendizaje está ahora normalizada. Esta comparación entre el descenso de gradiente estocástico clásico e implícito en el problema de mínimos cuadrados es muy similar a la comparación entre el filtro de mínimos cuadrados medios (LMS) y el filtro de mínimos cuadrados medios normalizados (NLMS).
Aunque una solución de forma cerrada para el ISGD sólo es posible en mínimos cuadrados, el procedimiento puede aplicarse eficazmente en una amplia gama de modelos. En concreto, supongamos que depende de sólo a través de una combinación lineal con las características , de modo que podemos escribir , donde puede depender de pero no en excepto a través de . Los mínimos cuadrados obedecen esta regla, al igual que la regresión logística y la mayoría de los modelos lineales generalizados. Por ejemplo, en mínimos cuadrados, y en regresión logística , donde es la función logística. En la regresión de Poisson y así sucesivamente.
En estos casos, la ISGD se aplica de la siguiente manera. Sea , donde es escalar. Entonces, ISGD es equivalente a:
El factor de escala puede hallarse mediante el método de bisección, ya que en la mayoría de los modelos regulares, como los modelos lineales generalizados mencionados, la función es decreciente, y por lo tanto los límites de búsqueda para son .
Momentum Otras propuestas incluyen el método del momentum o método de la bola pesada, que en el contexto del ML apareció en el artículo de Rumelhart, Hinton y Williams sobre el aprendizaje por retropropagación y tomó prestada la idea del artículo del matemático soviético Boris Polyak de 1964 sobre la resolución de ecuaciones funcionales. El descenso de gradiente estocástico con impulso recuerda la actualización en cada iteración, y determina la siguiente actualización como una combinación lineal del gradiente y la actualización anterior:
lo cual conduce a:
donde el parámetro que minimiza a será estimado, es un step size (a veces llamado tasa de aprendizaje en el aprendizaje automático) y es un factor de decaimiento exponencial entre 0 y 1 que determina la contribución relativa del gradiente actual y los gradientes anteriores al cambio de peso.