4
$\begingroup$

I have a question regarding the code of function SGDClassifier, from library scikit-learn, which implements linear classification using the stochastic gradient descent (SGD) algorithm. It concerns its application for the Support Vector Machine (SVM) model - i.e. SVM is parametrized by a hinge loss function and a L2 penalty function. The SVM decision function is:

$$ d(x) = sign\left(f(x)\right) = sign\left(w^Tx\right) $$

The optimal solution $w^*$ is found by solving the following regularized problem ($[x]_+ \equiv \max[0,x]$):

$$ \min_w \left(\sum_{i=1}^{n}{\left[1-y_i\,w^Tx_i\right]_+}+\lambda\|w\|^2\right) $$

From [Bottou, 2012], page 3, I recall the SGD algorithm's main update equation for the SVM:

$$ w \leftarrow w \ - \ \eta_t \left(\lambda w - y_tx_t\mathbf{1}_{\{y_tw^Tx_t<1\}} \right) $$

However, I am having trouble finding this same equation in SGDClassifier. The code of SGDClassifier is based on the function _plain_sgd() written in Cython: for an optimal learning rate (2), a hinge loss $-$ see definition of dloss in the code from line 108 on; dloss for a hinge loss function (SVM) is in line 160 $-$ and a L2 penalty (2), and ignoring class and sample weights, I have the impression the value for the update of $w$ is computed in line 639 and is equal to -eta * dloss:

$$ w \leftarrow w \ - \ \eta_ty_t\mathbf{1}_{\{y_tw^Tx_t<1\}} $$

There is a last computation in line 656:

w.add(x_data_ptr, x_ind_ptr, xnnz, update)

But I do not understand what this does.

Is there anything I have missed on _plain_sgd code? Has anybody a clue on where these differences come from? Especially given that scikit-learn claims that they follow Bottou's approach:

The implementation of SGD is influenced by the Stochastic Gradient SVM of Léon Bottou.

$\endgroup$
3
$\begingroup$

As you said, with $L_2$ regularization, the update is:

\begin{equation} w \leftarrow w - \eta_t\lambda w - \eta_t y_t x_t 1_{\{...\}} \end{equation}

The first two terms corresponds to a simple scaling. It is updated with the line:

w.scale(max(0, 1.0 - ((1.0 - l1_ratio) * eta * alpha)))

where the weight w are not really updated: to be fast, only a scaling coefficients is updated.

The last term of the update is done with the line:

w.add(x_data_ptr, x_ind_ptr, xnnz, update)

The key element is that if the update is sparse, we don't want to update all the weights. The second step only apply the non-zero updates, but the first step would affects all the weights. To avoid that, only a scaling coefficient is updated.

You might want to check the code of the weight vector.

$\endgroup$
1
$\begingroup$

While i can't give you a complete analysis, i'm pretty sure, that these differences are due to the fact, that the implementation is targeting sparsity in the data.

Have a look at the Bottou paper you linked, especially part 5.1! There is a special treatment mentioned for sparse input and the update rule is splitted into several lines.

Further evidence:

  • the code-line w.add(x_data_ptr, x_ind_ptr, xnnz, update) you refer to: xnnz means most of the time nonzeros (as in nonzeros of sparse-matrix) like for example here
  • sklearns SGDClassifier is sparse-matrix ready (see here)
  • personal experience tells me that sparsity-information is used!
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.