QpSvmDecomp Class Reference

Quadratic program solver for SVMs. More...

#include <QuadraticProgram.h>

Inheritance diagram for QpSvmDecomp:
QPSolver

List of all members.

Public Member Functions

 QpSvmDecomp (CachedMatrix &quadraticPart)
 Constructor.
virtual ~QpSvmDecomp ()
 Destructor.
double Solve (const Array< double > &linearPart, const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector, double eps=0.001, double threshold=1e100)
 solve the quadratic program
double ComputeInnerProduct (unsigned int index, const Array< double > &coeff)
 compute the inner product of a training example with a linear combination of the training examples
void getGradient (Array< double > &grad)
 return the gradient of the objective function in the optimum
void setVerbose (bool verbose=false)
 enable/disable console status output
void setStrategy (const char *strategy=NULL)
 set the working set strategy parameter
void setShrinking (bool shrinking=true)
 enable/disable shrinking
SharkInt64 iterations ()
 Return the number of iterations used to solve the problem.
bool isOptimal ()
 Is the solution optimal up to the given epsilon?
void setMaxIterations (SharkInt64 maxiter=-1)
 set the maximal number of iterations the solver is allowed to perform
void setMaxSeconds (int seconds=-1)
 set the maximal number of seconds the solver is allowed to run

Protected Member Functions

bool MVP (unsigned int &i, unsigned int &j)
 Select the most violatig pair (MVP).
bool HMG (unsigned int &i, unsigned int &j)
 Select a working set according to the hybrid maximum gain (HMG) algorithm.
bool Libsvm28 (unsigned int &i, unsigned int &j)
 Select a working set according to the second order algorithm of LIBSVM 2.8.
virtual bool SelectWorkingSet (unsigned int &i, unsigned int &j)
 Select a working set.
void SelectWSS ()
 Choose a suitable working set algorithm.
void Shrink ()
 Shrink the problem.
void Unshrink (bool complete=false)
 Active all variables.
void FlipCoordinates (unsigned int i, unsigned int j)
 exchange two variables via the permutation

Protected Attributes

unsigned int dimension
 problem dimension
CachedMatrixquadratic
 representation of the quadratic part of the objective function
Array< double > linear
 linear part of the objective function
Array< double > boxMin
 box constraint lower bound, that is, minimal variable value
Array< double > boxMax
 box constraint upper bound, that is, maximal variable value
SharkInt64 iter
 solution statistics: number of iterations
bool optimal
 is the solution found (near) optimal or has the solver stopped due to an interation or time constraint?
SharkInt64 maxIter
 maximum number of iterations
int maxSeconds
 maximum number of seconds
bool printInfo
 should the solver print its status to the standard output?
const char * WSS_Strategy
 working set selection strategy to follow
bool useShrinking
 should the solver use the shrinking heuristics?
bool(QpSvmDecomp::* currentWSS )(unsigned int &, unsigned int &)
 pointer to the currently used working set selection algorithm
unsigned int active
 number of currently active variables
Array< unsigned int > permutation
 permutation of the variables alpha, gradient, etc.
Array< double > diagonal
 diagonal matrix entries The diagonal array is of fixed size and not subject to shrinking.
Array< double > gradient
 gradient of the objective function The gradient array is of fixed size and not subject to shrinking.
Array< double > alpha
 Solution candidate.
bool bFirst
 indicator of the first decomposition iteration
unsigned int old_i
 first component of the previous working set
unsigned int old_j
 second component of the previous working set
double epsilon
 stopping condition - solution accuracy
bool bUnshrinked
 true if the problem has already been unshrinked

Detailed Description

Quadratic program solver for SVMs.

The purpose of the QpSvmDecomp class is two-fold: First, a QpSvmDecomp object is a description of a quadratic program, that is, an optimization problem composed of a quadratic objective function and a set of linear constraints. Second, this class is an efficient solver for this kind of problem.
This class is designed for the representation and solution of a special family of quadratic programs occuring as dual optimization problems in various kinds of support vector machine (SVM) formulations. These problems have the following structure (for $ \alpha \in R^{\ell} $):
maximize $ W(\alpha) = v^T \alpha - \frac{1}{2} \alpha^T M \alpha $
s.t. $ \sum_{i=1}^{\ell} \alpha_i = z $ (equality constraint)
and $ l_i \leq \alpha_i \leq u_i $ for all $ 1 \leq i \leq \ell $ (box constraints).
Here, z is a number, v is any vector and M is a positive definite symmetric quadratic matrix. $ l_i \leq u_i $ are lower and upper bounds on the variables.
In contrast to a general quadratic program there is only one equality constraint, which is restricted to a special form. The inequality constraints have to take the special form of a box. These properties make the SMO algorithm (Platt, 1999) and variants thereof (Fan et al., 2005; Glasmachers and Igel, 2006) directly applicable.
This solver uses the basic SMO algorithm with caching and shrinking techniques (Joachims, 1998) and a switching between two highly efficient worling set selection algorithms based on second order information. Because the SelectWorkingSet method is virtual, it is easy to implement other strategies if needed.
For practical considerations the solver supports several stopping conditions. Usually, the optimization stops if the Karush-Kuhn-Tucker (KKT) condition for optimality are satisfied up to a certain accuracy. In the case the optimal function value is known a priori it is possible to stop as soon as the objective is above a given threshold. In both cases it is very difficult to predict the runtime. Therefore the solver can stop after a predefined number of iterations or after a predefined time period. In these cases the solution found will not be near optimal. Usually this happens only during model selection while investigating hyperparameters with poor generatlization ability.

Definition at line 526 of file QuadraticProgram.h.


Constructor & Destructor Documentation

QpSvmDecomp::QpSvmDecomp ( CachedMatrix quadraticPart  ) 

Constructor.

Parameters:
quadratic quadratic part of the objective function and matrix cache

Definition at line 729 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, diagonal, dimension, CachedMatrix::Entry(), QPMatrix::getMatrixSize(), gradient, i, linear, maxIter, maxSeconds, permutation, printInfo, quadratic, useShrinking, and WSS_Strategy.

QpSvmDecomp::~QpSvmDecomp (  )  [virtual]

Destructor.

Definition at line 758 of file QuadraticProgram.cpp.


Member Function Documentation

double QpSvmDecomp::ComputeInnerProduct ( unsigned int  index,
const Array< double > &  coeff 
)

compute the inner product of a training example with a linear combination of the training examples

This method computes the inner product of a training example with a linear combination of all training examples. This computation is fast as it makes use of the kernel cache if possible.
Parameters:
index index of the training example
coeff list of coefficients of the training examples
Returns:
result of the inner product

Definition at line 921 of file QuadraticProgram.cpp.

References dimension, CachedMatrix::Entry(), CachedMatrix::getCacheRowSize(), i, permutation, quadratic, and CachedMatrix::Row().

Referenced by LOO::error().

void QpSvmDecomp::FlipCoordinates ( unsigned int  i,
unsigned int  j 
) [protected]

exchange two variables via the permutation

Definition at line 1350 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, diagonal, CachedMatrix::FlipColumnsAndRows(), gradient, linear, old_i, old_j, permutation, quadratic, and XCHG_A.

Referenced by Shrink(), and Unshrink().

void QpSvmDecomp::getGradient ( Array< double > &  grad  ) 

return the gradient of the objective function in the optimum

Parameters:
grad gradient of the objective function

Definition at line 949 of file QuadraticProgram.cpp.

References dimension, gradient, i, and permutation.

Referenced by LOO::ComputeB(), and SVM_Optimizer::optimize().

bool QpSvmDecomp::HMG ( unsigned int &  i,
unsigned int &  j 
) [protected]

Select a working set according to the hybrid maximum gain (HMG) algorithm.

Returns:
true if the solution is already sufficiently optimal
Parameters:
i first working set component
j second working set component

Definition at line 986 of file QuadraticProgram.cpp.

References active, alpha, bFirst, boxMax, boxMin, diagonal, epsilon, gradient, Libsvm28(), old_i, old_j, printInfo, quadratic, and CachedMatrix::Row().

Referenced by SelectWSS().

bool QpSvmDecomp::isOptimal (  )  [inline]

Is the solution optimal up to the given epsilon?

Definition at line 609 of file QuadraticProgram.h.

References optimal.

Referenced by SpanBound1::error(), SpanBound::error(), LOO::error(), SpanBound1::errorDerivative(), and RadiusMargin::solveProblems().

SharkInt64 QpSvmDecomp::iterations (  )  [inline]

Return the number of iterations used to solve the problem.

Definition at line 603 of file QuadraticProgram.h.

References iter.

Referenced by SpanBound::error(), LOO::error(), and RadiusMargin::solveProblems().

bool QpSvmDecomp::Libsvm28 ( unsigned int &  i,
unsigned int &  j 
) [protected]

Select a working set according to the second order algorithm of LIBSVM 2.8.

Returns:
true if the solution is already sufficiently optimal
Parameters:
i first working set component
j second working set component

Definition at line 1107 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, diagonal, epsilon, gradient, quadratic, and CachedMatrix::Row().

Referenced by HMG(), and SelectWSS().

bool QpSvmDecomp::MVP ( unsigned int &  i,
unsigned int &  j 
) [protected]

Select the most violatig pair (MVP).

Returns:
true if the solution is already sufficiently optimal
Parameters:
i first working set component
j second working set component

Definition at line 956 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, epsilon, and gradient.

Referenced by SelectWSS().

bool QpSvmDecomp::SelectWorkingSet ( unsigned int &  i,
unsigned int &  j 
) [protected, virtual]

Select a working set.

This member is implemented as a wrapper to HMG.
Returns:
true if the solution is already sufficiently optimal
Parameters:
i first working set component
j second working set component

Definition at line 1158 of file QuadraticProgram.cpp.

References currentWSS, old_i, and old_j.

Referenced by Solve().

void QpSvmDecomp::SelectWSS (  )  [protected]

Choose a suitable working set algorithm.

Definition at line 1168 of file QuadraticProgram.cpp.

References active, currentWSS, CachedMatrix::getMaxCacheSize(), HMG(), Libsvm28(), MVP(), quadratic, and WSS_Strategy.

Referenced by Shrink(), and Solve().

void QpSvmDecomp::setMaxIterations ( SharkInt64  maxiter = -1  )  [inline]

set the maximal number of iterations the solver is allowed to perform

Parameters:
maxiter maximal number of iterations, -1 for infinity

Definition at line 617 of file QuadraticProgram.h.

References maxIter.

Referenced by LOO::error(), SVM_Optimizer::optimize(), and RadiusMargin::solveProblems().

void QpSvmDecomp::setMaxSeconds ( int  seconds = -1  )  [inline]

set the maximal number of seconds the solver is allowed to run

Parameters:
seconds maximal number of seconds, -1 for infinity

Definition at line 625 of file QuadraticProgram.h.

References maxSeconds.

Referenced by SVM_Optimizer::optimize().

void QpSvmDecomp::setShrinking ( bool  shrinking = true  )  [inline]

enable/disable shrinking

Definition at line 597 of file QuadraticProgram.h.

References useShrinking.

void QpSvmDecomp::setStrategy ( const char *  strategy = NULL  )  [inline]

set the working set strategy parameter

Definition at line 591 of file QuadraticProgram.h.

References WSS_Strategy.

void QpSvmDecomp::setVerbose ( bool  verbose = false  )  [inline]

enable/disable console status output

Definition at line 585 of file QuadraticProgram.h.

References printInfo.

Referenced by SVM_Optimizer::optimize().

void QpSvmDecomp::Shrink (  )  [protected]
double QpSvmDecomp::Solve ( const Array< double > &  linearPart,
const Array< double > &  boxLower,
const Array< double > &  boxUpper,
Array< double > &  solutionVector,
double  eps = 0.001,
double  threshold = 1e100 
)

solve the quadratic program

This is the core method of the QpSvmDecomp class. It computes the solution of the problem defined by the parameters. This interface allows for the solution of multiple problems with the same quadratic part, reusing the matrix cache, but with arbirtrary linear part, box constraints and stopping conditions.
Parameters:
linearPart linear part v of the target function
boxLower vector l of lower bounds
boxUpper vector u of upper bounds
solutionVector input: initial feasible vector $ \alpha $; output: solution $ \alpha^* $
eps solution accuracy, in terms of the maximum KKT violation
threshold threshold to use for the objective value stopping criterion
Returns:
objective value at the optimum

Definition at line 763 of file QuadraticProgram.cpp.

References active, alpha, bFirst, boxMax, boxMin, bUnshrinked, diagonal, dimension, epsilon, gradient, i, iter, linear, maxIter, maxSeconds, optimal, permutation, printInfo, quadratic, CachedMatrix::Row(), SelectWorkingSet(), SelectWSS(), Shrink(), Unshrink(), and useShrinking.

Referenced by SpanBound::error(), LOO::error(), SVM_Optimizer::optimize(), and RadiusMargin::solveProblems().

void QpSvmDecomp::Unshrink ( bool  complete = false  )  [protected]

Active all variables.

Definition at line 1283 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, dimension, FlipCoordinates(), gradient, i, linear, old_i, old_j, printInfo, quadratic, and CachedMatrix::Row().

Referenced by Shrink(), and Solve().


Member Data Documentation

unsigned int QpSvmDecomp::active [protected]

number of currently active variables

Definition at line 673 of file QuadraticProgram.h.

Referenced by HMG(), Libsvm28(), MVP(), SelectWSS(), Shrink(), Solve(), and Unshrink().

Array<double> QpSvmDecomp::alpha [protected]

Solution candidate.

Definition at line 687 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().

bool QpSvmDecomp::bFirst [protected]

indicator of the first decomposition iteration

Definition at line 690 of file QuadraticProgram.h.

Referenced by HMG(), and Solve().

Array<double> QpSvmDecomp::boxMax [protected]

box constraint upper bound, that is, maximal variable value

Definition at line 644 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().

Array<double> QpSvmDecomp::boxMin [protected]

box constraint lower bound, that is, minimal variable value

Definition at line 641 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().

bool QpSvmDecomp::bUnshrinked [protected]

true if the problem has already been unshrinked

Definition at line 741 of file QuadraticProgram.h.

Referenced by Shrink(), and Solve().

bool(QpSvmDecomp::* QpSvmDecomp::currentWSS)(unsigned int &, unsigned int &) [protected]

pointer to the currently used working set selection algorithm

Referenced by SelectWorkingSet(), and SelectWSS().

Array<double> QpSvmDecomp::diagonal [protected]

diagonal matrix entries The diagonal array is of fixed size and not subject to shrinking.

Definition at line 680 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), Libsvm28(), QpSvmDecomp(), and Solve().

unsigned int QpSvmDecomp::dimension [protected]

problem dimension

Definition at line 632 of file QuadraticProgram.h.

Referenced by ComputeInnerProduct(), getGradient(), QpSvmDecomp(), Solve(), and Unshrink().

double QpSvmDecomp::epsilon [protected]

stopping condition - solution accuracy

Definition at line 699 of file QuadraticProgram.h.

Referenced by HMG(), Libsvm28(), MVP(), Shrink(), and Solve().

Array<double> QpSvmDecomp::gradient [protected]

gradient of the objective function The gradient array is of fixed size and not subject to shrinking.

Definition at line 684 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), getGradient(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().

SharkInt64 QpSvmDecomp::iter [protected]

solution statistics: number of iterations

Definition at line 647 of file QuadraticProgram.h.

Referenced by iterations(), and Solve().

Array<double> QpSvmDecomp::linear [protected]

linear part of the objective function

Definition at line 638 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), QpSvmDecomp(), Solve(), and Unshrink().

SharkInt64 QpSvmDecomp::maxIter [protected]

maximum number of iterations

Definition at line 655 of file QuadraticProgram.h.

Referenced by QpSvmDecomp(), setMaxIterations(), and Solve().

int QpSvmDecomp::maxSeconds [protected]

maximum number of seconds

Definition at line 658 of file QuadraticProgram.h.

Referenced by QpSvmDecomp(), setMaxSeconds(), and Solve().

unsigned int QpSvmDecomp::old_i [protected]

first component of the previous working set

Definition at line 693 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), SelectWorkingSet(), Shrink(), and Unshrink().

unsigned int QpSvmDecomp::old_j [protected]

second component of the previous working set

Definition at line 696 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), HMG(), SelectWorkingSet(), Shrink(), and Unshrink().

bool QpSvmDecomp::optimal [protected]

is the solution found (near) optimal or has the solver stopped due to an interation or time constraint?

Definition at line 652 of file QuadraticProgram.h.

Referenced by isOptimal(), and Solve().

Array<unsigned int> QpSvmDecomp::permutation [protected]

permutation of the variables alpha, gradient, etc.

Definition at line 676 of file QuadraticProgram.h.

Referenced by ComputeInnerProduct(), FlipCoordinates(), getGradient(), QpSvmDecomp(), and Solve().

bool QpSvmDecomp::printInfo [protected]

should the solver print its status to the standard output?

Definition at line 661 of file QuadraticProgram.h.

Referenced by HMG(), QpSvmDecomp(), setVerbose(), Shrink(), Solve(), and Unshrink().

representation of the quadratic part of the objective function

Definition at line 635 of file QuadraticProgram.h.

Referenced by ComputeInnerProduct(), FlipCoordinates(), HMG(), Libsvm28(), QpSvmDecomp(), SelectWSS(), Shrink(), Solve(), and Unshrink().

bool QpSvmDecomp::useShrinking [protected]

should the solver use the shrinking heuristics?

Definition at line 667 of file QuadraticProgram.h.

Referenced by QpSvmDecomp(), setShrinking(), and Solve().

const char* QpSvmDecomp::WSS_Strategy [protected]

working set selection strategy to follow

Definition at line 664 of file QuadraticProgram.h.

Referenced by QpSvmDecomp(), SelectWSS(), and setStrategy().


The documentation for this class was generated from the following files: