optiml.ml.svm.smo module

class optiml.ml.svm.smo.SMO(quad, X, y, K, kernel, C, tol=0.001, verbose=False)

Bases: ABC

Base abstract class for the sequential minimal optimization (SMO) algorithm used to train the dual SVM formulation.

The dual of a training problem, whether of a classifier or of a regressor, is the same quadratic program over a box with one linear equality constraint

min 1/2 alphas^T Q alphas + q^T alphas ,

0 <= alphas <= C , s^T alphas = 0 ,

written over a dual index space of size n_dual, of the map giving the sample each dual index refers to, of the signs s and of the linear coefficients q. A classifier has one dual index per sample, with the sign of its target and a coefficient of -1; a regressor has two, one per side of the insensitivity tube, with opposite signs. Everything else, this class included, is written in terms of those alone, which is why the same iteration trains both.

The iteration is the one of Platt with the working set selection of Keerthi et al. and of Fan, Chen and Lin: the first index of the pair is the maximal violating one, the second is the one that decreases the objective the most among those that make a violating pair with it. The gradient of the dual is maintained, so that both are read off a single scan of the active set, and the active set is shrunk of what provably cannot be selected any more.

Subclasses provide the dual index space and read the solution back out of the multipliers, and nothing else.

Parameters:

• quad (Quadratic instance) – The quadratic objective of the dual problem, used to monitor the cost during the optimization.

• X (ndarray of shape (n_samples, n_features)) – Training data.

• y (ndarray of shape (n_samples,)) – Target values associated with X.

• K (ndarray of shape (n_samples, n_samples)) – Precomputed kernel (Gram) matrix of the training data.

• kernel (Kernel instance) – The kernel function used to build K. If it is a LinearKernel the primal weight vector w is recovered from the multipliers.

• C (float) – Regularization parameter, i.e., the upper bound on the Lagrange multipliers.

• tol (float, default=1e-3) – Tolerance for the KKT stopping criterion.

• verbose (bool or int, default=False) – Controls the verbosity of progress messages to stdout.

minimize()

set_C(C)

Changes the trade-off parameter, i.e. the upper bound on the multipliers, keeping the solution of the previous call as the starting point of the next one.

The gradient of the dual is affine in the multipliers, in the linear term and in the diagonal alike, so the change is followed exactly, and in O( n_dual ) time rather than in the O( n_dual^2 ) that recomputing it from scratch costs. When the bound decreases the multipliers that exceed it are scaled rather than clipped, which is what keeps them feasible for the equality constraint as well, the latter being homogeneous, and keeps them in the proportions the previous solve had put them in.

set_epsilon(epsilon)

Changes the half-width of the insensitivity tube, which only moves the linear term of the dual by the same amount on every dual index, hence is followed in O( n_dual ) as well. Meaningless for a classifier, whose linear term does not depend on it.

follow_path(c, to, pinned=())

Moves the multiplier of the dual index c towards to keeping every other dual index at its own optimality condition, which is the incremental and decremental algorithm of Cauwenberghs and Poggio.

The multipliers of the margin indices and the bias follow the one of c along the direction that the free system gives, up to the first event: the multiplier of c arrives, its own condition starts holding, a margin multiplier reaches a bound, or a bounded index reaches the margin. At each event the direction is recomputed and the walk resumes, so what is left behind is optimal at every point of the path and exact when it stops. Growing a multiplier from zero learns a sample, driving it to zero unlearns one, and the two are the same walk taken in opposite directions.

Since two consecutive events differ by one index, the inverse of the matrix of the free system is kept across them and followed with rank-one updates, which cost the square of the order of the system rather than its cube. Building it costs more than one solve, so a walk that ends at its first event never builds it, and it is computed again from scratch every so many updates, so that what each of them loses in accuracy does not pile up.

Returns the number of events taken, or -1 if the path could not be followed, in which case the multipliers are still feasible but they are not the solution asked for and the caller has to fall back on minimize().

unlearn(i)

Drives the multipliers of the sample i to zero keeping every other one at its own optimality condition, so that what is left is the exact solution of the training problem without that sample, at the cost of one walk along the solution path rather than of a training. This is what makes the leave-one-out estimate, and the k-fold that unlearns one fold at a time, cost a walk each instead of a training each.

Returns the number of events taken, or -1 if the path could not be followed.

class optiml.ml.svm.smo.SMOClassifier(quad, X, y, K, kernel, C, tol=0.001, verbose=False)

Bases: SMO

The dual index space of a classifier: one dual index per sample, with the sign of its target and a linear coefficient of -1.

Parameters:

• quad (Quadratic instance) – The quadratic objective of the dual problem, used to monitor the cost during the optimization.

• X (ndarray of shape (n_samples, n_features)) – Training data.

• y (ndarray of shape (n_samples,)) – Target values associated with X.

• K (ndarray of shape (n_samples, n_samples)) – Precomputed kernel (Gram) matrix of the training data.

• kernel (Kernel instance) – The kernel function used to build K. If it is a LinearKernel the primal weight vector w is recovered from the multipliers.

• C (float) – Regularization parameter, i.e., the upper bound on the Lagrange multipliers.

• tol (float, default=1e-3) – Tolerance for the KKT stopping criterion.

• verbose (bool or int, default=False) – Controls the verbosity of progress messages to stdout.

follow_path(c, to, pinned=())

Moves the multiplier of the dual index c towards to keeping every other dual index at its own optimality condition, which is the incremental and decremental algorithm of Cauwenberghs and Poggio.

The multipliers of the margin indices and the bias follow the one of c along the direction that the free system gives, up to the first event: the multiplier of c arrives, its own condition starts holding, a margin multiplier reaches a bound, or a bounded index reaches the margin. At each event the direction is recomputed and the walk resumes, so what is left behind is optimal at every point of the path and exact when it stops. Growing a multiplier from zero learns a sample, driving it to zero unlearns one, and the two are the same walk taken in opposite directions.

Since two consecutive events differ by one index, the inverse of the matrix of the free system is kept across them and followed with rank-one updates, which cost the square of the order of the system rather than its cube. Building it costs more than one solve, so a walk that ends at its first event never builds it, and it is computed again from scratch every so many updates, so that what each of them loses in accuracy does not pile up.

Returns the number of events taken, or -1 if the path could not be followed, in which case the multipliers are still feasible but they are not the solution asked for and the caller has to fall back on minimize().

minimize()

set_C(C)

Changes the trade-off parameter, i.e. the upper bound on the multipliers, keeping the solution of the previous call as the starting point of the next one.

The gradient of the dual is affine in the multipliers, in the linear term and in the diagonal alike, so the change is followed exactly, and in O( n_dual ) time rather than in the O( n_dual^2 ) that recomputing it from scratch costs. When the bound decreases the multipliers that exceed it are scaled rather than clipped, which is what keeps them feasible for the equality constraint as well, the latter being homogeneous, and keeps them in the proportions the previous solve had put them in.

set_epsilon(epsilon)

Changes the half-width of the insensitivity tube, which only moves the linear term of the dual by the same amount on every dual index, hence is followed in O( n_dual ) as well. Meaningless for a classifier, whose linear term does not depend on it.

unlearn(i)

Drives the multipliers of the sample i to zero keeping every other one at its own optimality condition, so that what is left is the exact solution of the training problem without that sample, at the cost of one walk along the solution path rather than of a training. This is what makes the leave-one-out estimate, and the k-fold that unlearns one fold at a time, cost a walk each instead of a training each.

Returns the number of events taken, or -1 if the path could not be followed.

class optiml.ml.svm.smo.SMORegression(quad, X, y, K, kernel, C, epsilon, tol=0.001, verbose=False)

Bases: SMO

The dual index space of a regressor: two dual indices per sample, one per side of the insensitivity tube, with opposite signs and the target of the sample shifted by the half-width of the tube.

Parameters:

• quad (Quadratic instance) – The quadratic objective of the dual problem, used to monitor the cost during the optimization.

• X (ndarray of shape (n_samples, n_features)) – Training data.

• y (ndarray of shape (n_samples,)) – Target values associated with X.

• K (ndarray of shape (n_samples, n_samples)) – Precomputed kernel (Gram) matrix of the training data.

• kernel (Kernel instance) – The kernel function used to build K. If it is a LinearKernel the primal weight vector w is recovered from the multipliers.

• C (float) – Regularization parameter, i.e., the upper bound on the Lagrange multipliers.

• tol (float, default=1e-3) – Tolerance for the KKT stopping criterion.

• verbose (bool or int, default=False) – Controls the verbosity of progress messages to stdout.

set_epsilon(epsilon)

Changes the half-width of the insensitivity tube, which only moves the linear term of the dual by the same amount on every dual index, hence is followed in O( n_dual ) as well. Meaningless for a classifier, whose linear term does not depend on it.

follow_path(c, to, pinned=())

Moves the multiplier of the dual index c towards to keeping every other dual index at its own optimality condition, which is the incremental and decremental algorithm of Cauwenberghs and Poggio.

The multipliers of the margin indices and the bias follow the one of c along the direction that the free system gives, up to the first event: the multiplier of c arrives, its own condition starts holding, a margin multiplier reaches a bound, or a bounded index reaches the margin. At each event the direction is recomputed and the walk resumes, so what is left behind is optimal at every point of the path and exact when it stops. Growing a multiplier from zero learns a sample, driving it to zero unlearns one, and the two are the same walk taken in opposite directions.

Since two consecutive events differ by one index, the inverse of the matrix of the free system is kept across them and followed with rank-one updates, which cost the square of the order of the system rather than its cube. Building it costs more than one solve, so a walk that ends at its first event never builds it, and it is computed again from scratch every so many updates, so that what each of them loses in accuracy does not pile up.

Returns the number of events taken, or -1 if the path could not be followed, in which case the multipliers are still feasible but they are not the solution asked for and the caller has to fall back on minimize().

minimize()

set_C(C)

Changes the trade-off parameter, i.e. the upper bound on the multipliers, keeping the solution of the previous call as the starting point of the next one.

The gradient of the dual is affine in the multipliers, in the linear term and in the diagonal alike, so the change is followed exactly, and in O( n_dual ) time rather than in the O( n_dual^2 ) that recomputing it from scratch costs. When the bound decreases the multipliers that exceed it are scaled rather than clipped, which is what keeps them feasible for the equality constraint as well, the latter being homogeneous, and keeps them in the proportions the previous solve had put them in.

unlearn(i)

Drives the multipliers of the sample i to zero keeping every other one at its own optimality condition, so that what is left is the exact solution of the training problem without that sample, at the cost of one walk along the solution path rather than of a training. This is what makes the leave-one-out estimate, and the k-fold that unlearns one fold at a time, cost a walk each instead of a training each.

Returns the number of events taken, or -1 if the path could not be followed.