Descenso de gradiente estocástico (SGD) es un enfoque simple pero muy eficiente para ajustar clasificadores lineales y regresores bajo funciones de pérdida convexa como (lineal) Máquinas de vectores de soporte y Regresión logística. Aunque SGD ha existido en la comunidad de aprendizaje automático durante mucho tiempo, recientemente ha recibido una atención considerable en el contexto del aprendizaje a gran escala.

SGD se ha aplicado con éxito a problemas de aprendizaje automático dispersos y a gran escala que se encuentran a menudo en la clasificación de texto y el procesamiento del lenguaje natural. Dado que los datos son escasos, los clasificadores de este módulo se adaptan fácilmente a problemas con más de 10 ^ 5 ejemplos de entrenamiento y más de 10 ^ 5 características.

Estrictamente hablando, SGD es simplemente una técnica de optimización y no corresponde a una familia específica de modelos de aprendizaje automático. Es solo un camino entrenar un modelo. A menudo, una instancia de SGDClassifier o SGDRegressor tendrá un estimador equivalente en la API de scikit-learn, potencialmente usando una técnica de optimización diferente. Por ejemplo, usando SGDClassifier(loss="log") resultados en regresión logística, es decir, un modelo equivalente a LogisticRegression que se instala a través de SGD en lugar de ser instalado por uno de los otros solucionadores en LogisticRegression. Similar, SGDRegressor(loss="squared_loss", penalty='l2') y Ridge resolver el mismo problema de optimización, a través de diferentes medios.

Las ventajas del descenso de gradiente estocástico son:

  • Eficiencia.
  • Facilidad de implementación (muchas oportunidades para ajustar el código).

Las desventajas del descenso de gradiente estocástico incluyen:

  • SGD requiere varios hiperparámetros, como el parámetro de regularización y el número de iteraciones.
  • SGD es sensible a la escala de características.

Advertencia

Asegúrate de permutar (mezclar) tus datos de entrenamiento antes de ajustar el modelo o usar shuffle=True para mezclar después de cada iteración (usado por defecto). Además, idealmente, las características deben estandarizarse usando, por ejemplo, make_pipeline(StandardScaler(), SGDClassifier()) (ver Oleoductos).

1.5.1. Clasificación

La clase SGDClassifier implementa una rutina de aprendizaje de descenso de gradiente estocástico simple que admite diferentes funciones de pérdida y penalizaciones para la clasificación. A continuación se muestra el límite de decisión de un SGDClassifier entrenado con la pérdida de bisagra, equivalente a una SVM lineal.

../_images/sphx_glr_plot_sgd_separating_hyperplane_0011.png

Como otros clasificadores, SGD debe estar equipado con dos matrices: una matriz X of shape (n_samples, n_features) que contiene las muestras de entrenamiento, y una matriz y de shape (n_samples,) que contiene los valores objetivo (etiquetas de clase) para las muestras de entrenamiento:

>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0., 0.], [1., 1.]]
>>> y = [0, 1]
>>> clf = SGDClassifier(loss="hinge", penalty="l2", max_iter=5)
>>> clf.fit(X, y)
SGDClassifier(max_iter=5)

Una vez ajustado, el modelo se puede utilizar para predecir nuevos valores:

>>> clf.predict([[2., 2.]])
array([1])

SGD ajusta un modelo lineal a los datos de entrenamiento. los coef_ atributo contiene los parámetros del modelo:

>>> clf.coef_
array([[9.9..., 9.9...]])

los intercept_ El atributo contiene la intersección (también conocida como compensación o sesgo):

>>> clf.intercept_
array([-9.9...])

Si el modelo debe utilizar una intersección o no, es decir, un hiperplano sesgado, está controlado por el parámetro fit_intercept.

La distancia con signo al hiperplano (calculada como el producto escalar entre los coeficientes y la muestra de entrada, más la intersección) viene dada por SGDClassifier.decision_function:

>>> clf.decision_function([[2., 2.]])
array([29.6...])

La función de pérdida de hormigón se puede configurar a través del loss parámetro. SGDClassifier admite las siguientes funciones de pérdida:

  • loss="hinge": Máquina de vectores de soporte lineal (margen suave),
  • loss="modified_huber": pérdida de bisagra suavizada,
  • loss="log": Regresión logística,
  • y todas las pérdidas de regresión a continuación. En este caso, el objetivo se codifica como -1 o 1 y el problema se trata como un problema de regresión. La clase predicha luego corresponde al signo del objetivo predicho.

por favor refiérase a sección matemática a continuación para fórmulas. Las dos primeras funciones de pérdida son perezosas, solo actualizan los parámetros del modelo si un ejemplo viola la restricción de margen, lo que hace que el entrenamiento sea muy eficiente y puede resultar en modelos más dispersos (es decir, con más coeficientes cero), incluso cuando se usa la penalización L2.

Utilizando loss="log" o loss="modified_huber" habilita el predict_proba método, que da un vector de estimaciones de probabilidad (P (y | x) ) por muestra (X):

>>> clf = SGDClassifier(loss="log", max_iter=5).fit(X, y)
>>> clf.predict_proba([[1., 1.]])
array([[0.00..., 0.99...]])

La penalización concreta se puede establecer mediante el penalty parámetro. SGD admite las siguientes sanciones:

  • penalty="l2": Penalización de la norma L2 activada coef_.
  • penalty="l1": Penalización de la norma L1 en coef_.
  • penalty="elasticnet": Combinación convexa de L2 y L1; (1 - l1_ratio) * L2 + l1_ratio * L1.

La configuración predeterminada es penalty="l2". La penalización L1 conduce a soluciones escasas, lo que lleva a la mayoría de los coeficientes a cero. El Elastic Net 11 resuelve algunas deficiencias de la penalización L1 en presencia de atributos altamente correlacionados. El parámetro l1_ratio controla la combinación convexa de penalización L1 y L2.

SGDClassifier admite la clasificación de clases múltiples mediante la combinación de varios clasificadores binarios en un esquema de “uno contra todos” (OVA). Para cada uno de los (K ) clases, se aprende un clasificador binario que discrimina entre eso y todos los demás (K-1 ) clases. En el momento de la prueba, calculamos la puntuación de confianza (es decir, las distancias firmadas al hiperplano) para cada clasificador y elegimos la clase con la mayor confianza. La Figura siguiente ilustra el enfoque OVA en el conjunto de datos del iris. Las líneas discontinuas representan los tres clasificadores OVA; los colores de fondo muestran la superficie de decisión inducida por los tres clasificadores.

../_images/sphx_glr_plot_sgd_iris_0011.png

En el caso de clasificación multiclase coef_ es una matriz bidimensional de forma (n_classes, n_features) y intercept_ es una matriz unidimensional de forma (n_classes,). La i-ésima fila de coef_ contiene el vector de peso del clasificador OVA para la i-ésima clase; las clases están indexadas en orden ascendente (ver atributo classes_). Nótese que, en principio, dado que permiten crear un modelo de probabilidad, loss="log" y loss="modified_huber" son más adecuados para la clasificación de uno contra todos.

SGDClassifier admite tanto clases ponderadas como instancias ponderadas a través de los parámetros de ajuste class_weight y sample_weight. Vea los ejemplos a continuación y la cadena de documentos de SGDClassifier.fit para mayor información.

SGDClassifier admite SGD promediado (ASGD) 10. El promedio se puede habilitar configurando average=True. ASGD realiza las mismas actualizaciones que el SGD normal (consulte Formulación matemática), pero en lugar de utilizar el último valor de los coeficientes como coef_ atributo (es decir, los valores de la última actualización), coef_ se establece en su lugar en el promedio valor de los coeficientes en todas las actualizaciones. Lo mismo se hace para el intercept_ atributo. Cuando se usa ASGD, la tasa de aprendizaje puede ser mayor e incluso constante, lo que lleva en algunos conjuntos de datos a acelerar el tiempo de entrenamiento.

Para la clasificación con una pérdida logística, otra variante de SGD con una estrategia de promediado está disponible con el algoritmo de gradiente medio estocástico (SAG), disponible como solucionador en LogisticRegression.

Ejemplos:

  • SGD: margen máximo que separa el hiperplano,
  • Trazar SGD de clases múltiples en el conjunto de datos de iris
  • SGD: muestras ponderadas
  • Comparación de varios solucionadores en línea
  • SVM: hiperplano separador para clases no balanceadas (Vea la nota en el ejemplo)

1.5.2. Regresión

La clase SGDRegressor implementa una rutina de aprendizaje de descenso de gradiente estocástico simple que admite diferentes funciones de pérdida y penalizaciones para adaptarse a modelos de regresión lineal. SGDRegressor es muy adecuado para problemas de regresión con una gran cantidad de muestras de entrenamiento (> 10.000), para otros problemas recomendamos Ridge, Lasso, o ElasticNet.

La función de pérdida de hormigón se puede configurar a través del loss parámetro. SGDRegressor admite las siguientes funciones de pérdida:

  • loss="squared_loss": Mínimos cuadrados ordinarios,
  • loss="huber": Pérdida de Huber para regresión robusta,
  • loss="epsilon_insensitive": Regresión de vectores de soporte lineal.

por favor refiérase a sección matemática a continuación para fórmulas. Las funciones de pérdida insensibles a Huber y épsilon se pueden utilizar para una regresión robusta. El ancho de la región insensible debe especificarse mediante el parámetro epsilon. Este parámetro depende de la escala de las variables objetivo.

los penalty El parámetro determina la regularización que se utilizará (consulte la descripción anterior en la sección de clasificación).

SGDRegressor también admite un promedio de SGD 10 (en este caso, de nuevo, consulte la descripción anterior en la sección de clasificación).

Para la regresión con una pérdida al cuadrado y una penalización de 12, está disponible otra variante de SGD con una estrategia de promediado con el algoritmo de gradiente medio estocástico (SAG), disponible como solucionador en Ridge.

1.5.3. Descenso de gradiente estocástico para datos dispersos

Nota

La implementación escasa produce resultados ligeramente diferentes de la implementación densa, debido a una tasa de aprendizaje reducida para la intercepción. Ver Detalles de implementacion.

Hay soporte incorporado para datos dispersos dados en cualquier matriz en un formato compatible con scipy.sparse. Sin embargo, para obtener la máxima eficiencia, utilice el formato de matriz de RSE como se define en scipy.sparse.csr_matrix.

Ejemplos:

  • Clasificación de documentos de texto usando características dispersas

1.5.4. Complejidad

La principal ventaja de SGD es su eficiencia, que es básicamente lineal en el número de ejemplos de entrenamiento. Si X es una matriz de tamaño (n, p), el entrenamiento tiene un costo de (O (kn bar p) ), donde k es el número de iteraciones (épocas) y ( bar p ) es el número medio de atributos distintos de cero por muestra.

Sin embargo, los resultados teóricos recientes muestran que el tiempo de ejecución para obtener la precisión de optimización deseada no aumenta a medida que aumenta el tamaño del conjunto de entrenamiento.

1.5.5. Criterio de parada

Las clases SGDClassifier y SGDRegressor proporcionan dos criterios para detener el algoritmo cuando se alcanza un nivel determinado de convergencia:

  • Con early_stopping=True, los datos de entrada se dividen en un conjunto de entrenamiento y un conjunto de validación. A continuación, el modelo se ajusta al conjunto de entrenamiento y el criterio de detención se basa en la puntuación de predicción (utilizando el score método) calculado en el conjunto de validación. El tamaño del conjunto de validación se puede cambiar con el parámetro validation_fraction.
  • Con early_stopping=False, el modelo se ajusta a todos los datos de entrada y el criterio de parada se basa en la función objetivo calculada en los datos de entrenamiento.

En ambos casos, el criterio se evalúa una vez por época y el algoritmo se detiene cuando el criterio no mejora. n_iter_no_change veces seguidas. La mejora se evalúa con tolerancia absoluta. tol, y el algoritmo se detiene en cualquier caso después de un número máximo de iteraciones max_iter.

1.5.6. Consejos de uso práctico

  • El descenso de gradiente estocástico es sensible al escalado de características, por lo que se recomienda encarecidamente escalar sus datos. Por ejemplo, escale cada atributo en el vector de entrada X a [0,1] o [-1,+1], o estandarícelo para tener media 0 y varianza 1. Tenga en cuenta que el mismo Se debe aplicar una escala al vector de prueba para obtener resultados significativos. Esto se puede hacer fácilmente usando StandardScaler:

    from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)  # Don't cheat - fit only on training data
X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)  # apply same transformation to test data

# Or better yet: use a pipeline!
from sklearn.pipeline import make_pipeline
est = make_pipeline(StandardScaler(), SGDClassifier())
est.fit(X_train)
est.predict(X_test)

    Si sus atributos tienen una escala intrínseca (por ejemplo, frecuencias de palabras o características de los indicadores), no es necesario escalar.

  • Encontrar un plazo de regularización razonable (alfa) se realiza mejor mediante la búsqueda automática de hiperparámetros, p. ej. GridSearchCV o RandomizedSearchCV, generalmente en el rango 10.0**-np.arange(1,7).
  • Empíricamente, encontramos que SGD converge después de observar aproximadamente 10 ^ 6 muestras de entrenamiento. Por lo tanto, una primera estimación razonable del número de iteraciones es max_iter = np.ceil(10**6 / n), dónde n es el tamaño del conjunto de entrenamiento.
  • Si aplica SGD a las características extraídas mediante PCA, descubrimos que a menudo es aconsejable escalar los valores de las características por alguna constante c de manera que la norma L2 promedio de los datos de entrenamiento sea igual a uno.
  • Descubrimos que el SGD promedio funciona mejor con una mayor cantidad de funciones y una eta0 más alta

Referencias:

1.5.7. Formulación matemática

Describimos aquí los detalles matemáticos del procedimiento SGD. En 12 se puede encontrar una buena descripción general de las tasas de convergencia.

Dado un conjunto de ejemplos de formación ((x_1, y_1), ldots, (x_n, y_n) ) dónde (x_i in mathbf {R} ^ m ) y (y_i in mathcal {R} ) ( (y_i in {-1, 1} ) para la clasificación), nuestro objetivo es aprender una función de puntuación lineal (f (x) = w ^ T x + b ) con parámetros de modelo (w in mathbf {R} ^ m ) e interceptar (b in mathbf {R} ). Para hacer predicciones para la clasificación binaria, simplemente miramos el signo de (f (x) ). Para encontrar los parámetros del modelo, minimizamos el error de entrenamiento regularizado dado por

[E(w,b) = frac{1}{n}sum_{i=1}^{n} L(y_i, f(x_i)) + alpha R(w)]

dónde (L ) es una función de pérdida que mide el (mal) ajuste del modelo y (R ) es un término de regularización (también conocido como penalización) que penaliza la complejidad del modelo; ( alpha> 0 ) es un hiperparámetro no negativo que controla la fuerza de regularización.

Diferentes opciones para (L ) implican diferentes clasificadores o regresores:

  • Bisagra (margen suave): equivalente a la clasificación de vectores de soporte. (L (y_i, f (x_i)) = max (0, 1 – y_i f (x_i)) ).
  • Perceptrón: (L (y_i, f (x_i)) = max (0, – y_i f (x_i)) ).
  • Huber modificado: (L (y_i, f (x_i)) = max (0, 1 – y_i f (x_i)) ^ 2 ) si (y_i f (x_i)> 1 ), y (L (y_i, f (x_i)) = -4 y_i f (x_i) ) de lo contrario.
  • Log: equivalente a Regresión logística. (L (y_i, f (x_i)) = log (1 + exp (-y_i f (x_i))) ).
  • Mínimos cuadrados: regresión lineal (cresta o lazo según (R )). (L (y_i, f (x_i)) = frac {1} {2} (y_i – f (x_i)) ^ 2 ).
  • Huber: menos sensible a los valores atípicos que a los mínimos cuadrados. Es equivalente a mínimos cuadrados cuando (| y_i – f (x_i) | leq varepsilon ), y (L (y_i, f (x_i)) = varepsilon | y_i – f (x_i) | – frac {1} {2} varepsilon ^ 2 ) de lo contrario.
  • Epsilon-Insensitive: (margen suave) equivalente a Support Vector Regression. (L (y_i, f (x_i)) = max (0, | y_i – f (x_i) | – varepsilon) ).

Todas las funciones de pérdida anteriores se pueden considerar como un límite superior del error de clasificación errónea (pérdida cero-uno) como se muestra en la Figura siguiente.

../_images/sphx_glr_plot_sgd_loss_functions_0011.png

Opciones populares para el período de regularización (R ) (los penalty parámetro) incluyen:

  • Norma L2: (R (w): = frac {1} {2} sum_ {j = 1} ^ {m} w_j ^ 2 = || w || _2 ^ 2 ),
  • Norma L1: (R (w): = sum_ {j = 1} ^ {m} | w_j | ), lo que conduce a soluciones escasas.
  • Red elástica: (R (w): = frac { rho} {2} sum_ {j = 1} ^ {n} w_j ^ 2 + (1- rho) sum_ {j = 1} ^ {m} | w_j | ), una combinación convexa de L2 y L1, donde ( rho ) es dado por 1 - l1_ratio.

La siguiente figura muestra los contornos de los diferentes términos de regularización en un espacio de parámetros bidimensional ( (m = 2 )) cuando (R (w) = 1 ).

../_images/sphx_glr_plot_sgd_penalties_0011.png

1.5.7.1. SGD

El descenso de gradiente estocástico es un método de optimización para problemas de optimización sin restricciones. A diferencia del descenso de gradiente (por lotes), SGD se aproxima al gradiente real de (E (w, b) ) considerando un solo ejemplo de entrenamiento a la vez.

La clase SGDClassifier implementa una rutina de aprendizaje SGD de primer orden. El algoritmo itera sobre los ejemplos de entrenamiento y para cada ejemplo actualiza los parámetros del modelo de acuerdo con la regla de actualización dada por

[w leftarrow w – eta left[alpha frac{partial R(w)}{partial w} + frac{partial L(w^T x_i + b, y_i)}{partial w}right]]

dónde ( eta ) es la tasa de aprendizaje que controla el tamaño del paso en el espacio de parámetros. La intercepción (B) se actualiza de manera similar pero sin regularización (y con decaimiento adicional para matrices dispersas, como se detalla en Detalles de implementacion).

La tasa de aprendizaje ( eta ) puede ser constante o gradualmente decayendo. Para la clasificación, el programa de tasa de aprendizaje predeterminado (learning_rate="optimal") es dado por

[eta^{
1.5.8. Detalles de implementacion

La implementación de SGD está influenciada por Stochastic Gradient SVM de 7. Similar a SvmSGD, el vector de peso se representa como el producto de un escalar y un vector que permite una actualización de peso eficiente en el caso de la regularización L2. En el caso de entrada escasa X, la intersección se actualiza con una tasa de aprendizaje menor (multiplicada por 0,01) para tener en cuenta el hecho de que se actualiza con más frecuencia. Los ejemplos de formación se recogen de forma secuencial y la tasa de aprendizaje se reduce después de cada ejemplo observado. Adoptamos el programa de tasa de aprendizaje de 8. Para la clasificación de clases múltiples, se utiliza un enfoque de “uno contra todos”. Usamos el algoritmo de gradiente truncado propuesto en 9 para la regularización L1 (y Elastic Net). El código está escrito en Cython.

Referencias:

7

“Descenso de gradiente estocástico” L. Bottou – Sitio web, 2010.

8

“Pegasos: solucionador de sub-gradiente estimado primordial para svm” S. Shalev-Shwartz, Y. Singer, N. Srebro – En Proceedings of ICML ’07.

9

“Entrenamiento de descenso de gradiente estocástico para modelos log-lineales regularizados en l1 con penalización acumulativa” Y. Tsuruoka, J. Tsujii, S. Ananiadou – En Proceedings of the AFNLP / ACL ’09.

10(1,2)

“Hacia un aprendizaje óptimo a gran escala en una sola pasada con descenso de gradiente estocástico promedio” Xu, Wei

11

“Regularización y selección de variables a través de la red elástica” H. Zou, T. Hastie – Revista de la Real Sociedad de Estadística Serie B, 67 (2), 301-320.

12

“Resolver problemas de predicción lineal a gran escala utilizando algoritmos de descenso de gradientes estocásticos” T. Zhang – En Actas de ICML ’04.