Stochastic Gradient Descent SVM classifier

SVMSGD provides a fast and easy-to-use implementation of the SVM classifier using the Stochastic Gradient Descent approach, as presented in [bottou2010large].

The classifier has following parameters:

• model type,
• margin type,
• margin regularization (lambda),
• initial step size (gamma_0),
• step decreasing power (c),
• and termination criteria.

The model type may have one of the following values: 'SGD' and 'ASGD'.

• SGD is the classic version of SVMSGD classifier: every next step is calculated by the formula:

  w_{t+1} = w_t - gamma(t) * (dQ_i/dw)|_{w = w_t}
  

  where

  • w_t is the weights vector for decision function at step t,
  • gamma(t) is the step size of model parameters at the iteration t, it is decreased on each step by the formula gamma(t) = gamma_0 * (1 + lambda*gamma_0*t)^(-c)
  • Q_i is the target functional from SVM task for sample with number i, this sample is chosen stochastically on each step of the algorithm.

• ASGD is Average Stochastic Gradient Descent SVM Classifier. ASGD classifier averages weights vector on each step of algorithm by the formula wHat_{t+1} = t/(1+t) * wHat_t + 1/(1+t) * w_{t+1}.

The recommended model type is ASGD (following [bottou2010large]).

The margin type may have one of the following values:

• SoftMargin You should use 'HardMargin' type, if you have linearly separable sets.
• HardMargin You should use 'SoftMargin' type, if you have non-linearly separable sets or sets with outliers.

In the general case (if you know nothing about linear separability of your sets), use 'SoftMargin'.

The other parameters may be described as follows:

• Margin regularization parameter is responsible for weights decreasing at each step and for the strength of restrictions on outliers (the less the parameter, the less probability that an outlier will be ignored). Recommended value for SGD model is 0.0001, for ASGD model is 0.00001.
• Initial step size parameter is the initial value for the step size gamma(t). You will have to find the best initial step for your problem.
• Step decreasing power is the power parameter for gamma(t) decreasing by the formula, mentioned above. Recommended value for SGD model is 1, for ASGD model is 0.75.
• Termination criteria can be 'Count', 'EPS', or 'Count+EPS'. You will have to find the best termination criteria for your problem.

Note that the parameters margin regularization, initial step size, and step decreasing power should be positive.

To use SVMSGD algorithm do as follows:

• first, create the cv.SVMSGD object. The algorithm will set optimal parameters by default, but you can set your own parameters via properties cv.SVMSGD.SvmsgdType, cv.SVMSGD.MarginType, cv.SVMSGD.MarginRegularization, cv.SVMSGD.InitialStepSize, and cv.SVMSGD.StepDecreasingPower.
• then the SVM model can be trained using the train features and the correspondent labels by the method cv.SVMSGD.train.
• after that, the label of a new feature vector can be predicted using the method cv.SVMSGD.predict.

Example:

% Create empty object
svmsgd = cv.SVMSGD();
% Train the Stochastic Gradient Descent SVM
svmsgd.train(trainData);
% Predict labels for the new samples
svmsgd.predict(samples, responses);

References

[bottou2010large]:

Leon Bottou. "Large-scale machine learning with stochastic gradient descent". In Proceedings of COMPSTAT 2010, pages 177-186. Springer.