QpSvmDecomp Class Reference

Quadratic program solver for SVMs. More...

#include <QuadraticProgram.h>

Inheritance diagram for QpSvmDecomp:

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
CachedMatrix &	quadratic
	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]

Shrink the problem.

Definition at line 1197 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, bUnshrinked, CachedMatrix::CacheRowRelease(), CachedMatrix::CacheRowResize(), epsilon, FlipCoordinates(), CachedMatrix::getCacheRowSize(), gradient, old_i, old_j, printInfo, quadratic, SelectWSS(), and Unshrink().

Referenced by Solve().

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