1.5. Stochastic Gradient Descent¶

1.5.1. Classification¶

The class SGDClassifier implements a plain stochastic gradient descent learning routine which supports different loss functions and penalties for classification.

As other classifiers, SGD has to be fitted with two arrays: an array X of size [n_samples, n_features] holding the training samples, and an array Y of size [n_samples] holding the target values (class labels) for the training samples:

>>> 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)

After being fitted, the model can then be used to predict new values:

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

SGD fits a linear model to the training data. The member coef_ holds the model parameters:

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

Member intercept_ holds the intercept (aka offset or bias):

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

Whether or not the model should use an intercept, i.e. a biased hyperplane, is controlled by the parameter fit_intercept.

To get the signed distance to the hyperplane use SGDClassifier.decision_function:

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

The concrete loss function can be set via the loss parameter. SGDClassifier supports the following loss functions:

• loss="hinge": (soft-margin) linear Support Vector Machine,

• loss="modified_huber": smoothed hinge loss,

• loss="log": logistic regression,

• and all regression losses below.

The first two loss functions are lazy, they only update the model parameters if an example violates the margin constraint, which makes training very efficient and may result in sparser models, even when L2 penalty is used.

Using loss="log" or loss="modified_huber" enables the predict_proba method, which gives a vector of probability estimates \(P(y|x)\) per sample \(x\):

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

The concrete penalty can be set via the penalty parameter. SGD supports the following penalties:

• penalty="l2": L2 norm penalty on coef_.

• penalty="l1": L1 norm penalty on coef_.

• penalty="elasticnet": Convex combination of L2 and L1; (1 - l1_ratio) * L2 + l1_ratio * L1.

The default setting is penalty="l2". The L1 penalty leads to sparse solutions, driving most coefficients to zero. The Elastic Net solves some deficiencies of the L1 penalty in the presence of highly correlated attributes. The parameter l1_ratio controls the convex combination of L1 and L2 penalty.

SGDClassifier supports multi-class classification by combining multiple binary classifiers in a “one versus all” (OVA) scheme. For each of the \(K\) classes, a binary classifier is learned that discriminates between that and all other \(K-1\) classes. At testing time, we compute the confidence score (i.e. the signed distances to the hyperplane) for each classifier and choose the class with the highest confidence. The Figure below illustrates the OVA approach on the iris dataset. The dashed lines represent the three OVA classifiers; the background colors show the decision surface induced by the three classifiers.

In the case of multi-class classification coef_ is a two-dimensional array of shape=[n_classes, n_features] and intercept_ is a one-dimensional array of shape=[n_classes]. The i-th row of coef_ holds the weight vector of the OVA classifier for the i-th class; classes are indexed in ascending order (see attribute classes_). Note that, in principle, since they allow to create a probability model, loss="log" and loss="modified_huber" are more suitable for one-vs-all classification.

SGDClassifier supports both weighted classes and weighted instances via the fit parameters class_weight and sample_weight. See the examples below and the docstring of SGDClassifier.fit for further information.

SGDClassifier supports averaged SGD (ASGD). Averaging can be enabled by setting `average=True`. ASGD works by averaging the coefficients of the plain SGD over each iteration over a sample. When using ASGD the learning rate can be larger and even constant leading on some datasets to a speed up in training time.

For classification with a logistic loss, another variant of SGD with an averaging strategy is available with Stochastic Average Gradient (SAG) algorithm, available as a solver in LogisticRegression.

1.5.2. Regression¶

The class SGDRegressor implements a plain stochastic gradient descent learning routine which supports different loss functions and penalties to fit linear regression models. SGDRegressor is well suited for regression problems with a large number of training samples (> 10.000), for other problems we recommend Ridge, Lasso, or ElasticNet.

The concrete loss function can be set via the loss parameter. SGDRegressor supports the following loss functions:

• loss="squared_loss": Ordinary least squares,

• loss="huber": Huber loss for robust regression,

• loss="epsilon_insensitive": linear Support Vector Regression.

The Huber and epsilon-insensitive loss functions can be used for robust regression. The width of the insensitive region has to be specified via the parameter epsilon. This parameter depends on the scale of the target variables.

SGDRegressor supports averaged SGD as SGDClassifier. Averaging can be enabled by setting `average=True`.

For regression with a squared loss and a l2 penalty, another variant of SGD with an averaging strategy is available with Stochastic Average Gradient (SAG) algorithm, available as a solver in Ridge.

1.5.3. Stochastic Gradient Descent for sparse data¶

There is built-in support for sparse data given in any matrix in a format supported by scipy.sparse. For maximum efficiency, however, use the CSR matrix format as defined in scipy.sparse.csr_matrix.

1.5.4. Complexity¶

The major advantage of SGD is its efficiency, which is basically linear in the number of training examples. If X is a matrix of size (n, p) training has a cost of \(O(k n \bar p)\), where k is the number of iterations (epochs) and \(\bar p\) is the average number of non-zero attributes per sample.

Recent theoretical results, however, show that the runtime to get some desired optimization accuracy does not increase as the training set size increases.

1.5.5. Stopping criterion¶

The classes SGDClassifier and SGDRegressor provide two criteria to stop the algorithm when a given level of convergence is reached:

• With early_stopping=True, the input data is split into a training set and a validation set. The model is then fitted on the training set, and the stopping criterion is based on the prediction score computed on the validation set. The size of the validation set can be changed with the parameter validation_fraction.

• With early_stopping=False, the model is fitted on the entire input data and the stopping criterion is based on the objective function computed on the input data.

In both cases, the criterion is evaluated once by epoch, and the algorithm stops when the criterion does not improve n_iter_no_change times in a row. The improvement is evaluated with a tolerance tol, and the algorithm stops in any case after a maximum number of iteration max_iter.

1.5.6. Tips on Practical Use¶

• Stochastic Gradient Descent is sensitive to feature scaling, so it is highly recommended to scale your data. For example, scale each attribute on the input vector X to [0,1] or [-1,+1], or standardize it to have mean 0 and variance 1. Note that the same scaling must be applied to the test vector to obtain meaningful results. This can be easily done using 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
  

  If your attributes have an intrinsic scale (e.g. word frequencies or indicator features) scaling is not needed.

• Finding a reasonable regularization term \(\alpha\) is best done using GridSearchCV, usually in the range 10.0**-np.arange(1,7).

• Empirically, we found that SGD converges after observing approx. 10^6 training samples. Thus, a reasonable first guess for the number of iterations is max_iter = np.ceil(10**6 / n), where n is the size of the training set.

• If you apply SGD to features extracted using PCA we found that it is often wise to scale the feature values by some constant c such that the average L2 norm of the training data equals one.

• We found that Averaged SGD works best with a larger number of features and a higher eta0

1.5.7. Mathematical formulation¶

Given a set of training examples \((x_1, y_1), \ldots, (x_n, y_n)\) where \(x_i \in \mathbf{R}^m\) and \(y_i \in \{-1,1\}\), our goal is to learn a linear scoring function \(f(x) = w^T x + b\) with model parameters \(w \in \mathbf{R}^m\) and intercept \(b \in \mathbf{R}\). In order to make predictions, we simply look at the sign of \(f(x)\). A common choice to find the model parameters is by minimizing the regularized training error given by

where \(L\) is a loss function that measures model (mis)fit and \(R\) is a regularization term (aka penalty) that penalizes model complexity; \(\alpha > 0\) is a non-negative hyperparameter.

Different choices for \(L\) entail different classifiers such as

• Hinge: (soft-margin) Support Vector Machines.

• Log: Logistic Regression.

• Least-Squares: Ridge Regression.

• Epsilon-Insensitive: (soft-margin) Support Vector Regression.

All of the above loss functions can be regarded as an upper bound on the misclassification error (Zero-one loss) as shown in the Figure below.

Popular choices for the regularization term \(R\) include:

• L2 norm: \(R(w) := \frac{1}{2} \sum_{i=1}^{n} w_i^2\),

• L1 norm: \(R(w) := \sum_{i=1}^{n} |w_i|\), which leads to sparse solutions.

• Elastic Net: \(R(w) := \frac{\rho}{2} \sum_{i=1}^{n} w_i^2 + (1-\rho) \sum_{i=1}^{n} |w_i|\), a convex combination of L2 and L1, where \(\rho\) is given by 1 - l1_ratio.

The Figure below shows the contours of the different regularization terms in the parameter space when \(R(w) = 1\).

1.5.8. Implementation details¶

The implementation of SGD is influenced by the Stochastic Gradient SVM of Léon Bottou. Similar to SvmSGD, the weight vector is represented as the product of a scalar and a vector which allows an efficient weight update in the case of L2 regularization. In the case of sparse feature vectors, the intercept is updated with a smaller learning rate (multiplied by 0.01) to account for the fact that it is updated more frequently. Training examples are picked up sequentially and the learning rate is lowered after each observed example. We adopted the learning rate schedule from Shalev-Shwartz et al. 2007. For multi-class classification, a “one versus all” approach is used. We use the truncated gradient algorithm proposed by Tsuruoka et al. 2009 for L1 regularization (and the Elastic Net). The code is written in Cython.