QpCrammerSingerDecomp Class Reference

Quadratic program solver for the multi class SVM as proposed by Crammer and Singer. More...

#include <QuadraticProgram.h>

Inheritance diagram for QpCrammerSingerDecomp:

List of all members.

Classes

struct tExample

data structure describing one training example More...

struct tVariable

data structure describing one variable of the problem More...

Public Member Functions

QpCrammerSingerDecomp (CachedMatrix &kernel, const Array< double > &y, unsigned int classes)

Constructor.

virtual ~QpCrammerSingerDecomp ()

Destructor.

void Solve (Array< double > &solutionVector, double beta, double eps=0.001)

solve the quadratic program

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

Protected Member Functions

double SelectWorkingSet (unsigned int &i, unsigned int &j)

void Shrink ()

Shrink the problem.

void Unshrink (bool complete=false)

Active all variables.

void DeactivateVariable (unsigned int v)

shrink a variable

void DeactivateExample (unsigned int e)

shrink an examples

Protected Attributes

std::vector< tExample > example

information about each training example

std::vector< tVariable > variable

information about each variable of the problem

std::vector< unsigned int > storage

space for the example[i].variables pointers

unsigned int examples

unsigned int classes

unsigned int variables

CachedMatrix & kernelMatrix

kernel matrix cache

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

unsigned int activeEx

number of currently active examples

unsigned int activeVar

number of currently active variables

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.

double epsilon

stopping condition - solution accuracy

bool bUnshrinked

true if the problem has already been unshrinked

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

Detailed Description

Quadratic program solver for the multi class SVM as proposed by Crammer and Singer.

: This algorithm solves the same quadratic program introduced in:

K. Crammer, Y. Singer. On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines. In Journal of Machine Learning Research, pp. 265-292 (2001).

Definition at line 1095 of file QuadraticProgram.h.

Constructor & Destructor Documentation

QpCrammerSingerDecomp::QpCrammerSingerDecomp	(	CachedMatrix &	kernel,
		const Array< double > &	y,
		unsigned int	classes
	)

Constructor.

Parameters:

	kernel	kernel matrix cache
	method	problem properties
	classes	number of classes

Definition at line 2254 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, diagonal, CachedMatrix::Entry(), example, examples, QPMatrix::getMatrixSize(), gradient, i, kernelMatrix, linear, maxIter, storage, variable, and variables.

QpCrammerSingerDecomp::~QpCrammerSingerDecomp ( ) [virtual]

Destructor.

Definition at line 2298 of file QuadraticProgram.cpp.

Member Function Documentation

void QpCrammerSingerDecomp::DeactivateExample ( unsigned int e ) [protected]

shrink an examples

Definition at line 2660 of file QuadraticProgram.cpp.

References activeEx, CachedMatrix::CacheRowRelease(), classes, diagonal, example, CachedMatrix::FlipColumnsAndRows(), kernelMatrix, variable, XCHG_A, and XCHG_V.

Referenced by Shrink().

void QpCrammerSingerDecomp::DeactivateVariable ( unsigned int v ) [protected]

shrink a variable

Definition at line 2629 of file QuadraticProgram.cpp.

References QpCrammerSingerDecomp::tExample::active, activeVar, alpha, boxMax, boxMin, example, gradient, linear, variable, QpCrammerSingerDecomp::tExample::variables, XCHG_A, and XCHG_V.

Referenced by Shrink().

bool QpCrammerSingerDecomp::isOptimal ( ) [inline]

Is the solution optimal up to the given epsilon?

Definition at line 1125 of file QuadraticProgram.h.

References optimal.

SharkInt64 QpCrammerSingerDecomp::iterations ( ) [inline]

Return the number of iterations used to solve the problem.

Definition at line 1119 of file QuadraticProgram.h.

References iter.

double QpCrammerSingerDecomp::SelectWorkingSet	(	unsigned int &	i,
		unsigned int &	j
	)			`[protected]`

Definition at line 2470 of file QuadraticProgram.cpp.

References QpCrammerSingerDecomp::tExample::active, activeEx, alpha, boxMax, boxMin, example, gradient, and QpCrammerSingerDecomp::tExample::variables.

Referenced by Shrink(), and Solve().

void QpCrammerSingerDecomp::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 1133 of file QuadraticProgram.h.

References maxIter.

Referenced by SVM_Optimizer::optimize().

void QpCrammerSingerDecomp::Shrink ( ) [protected]

Shrink the problem.

Definition at line 2515 of file QuadraticProgram.cpp.

References QpCrammerSingerDecomp::tExample::active, activeEx, alpha, boxMax, boxMin, bUnshrinked, CachedMatrix::CacheRowResize(), DeactivateExample(), DeactivateVariable(), epsilon, example, CachedMatrix::getCacheRowSize(), gradient, i, kernelMatrix, SelectWorkingSet(), Unshrink(), and QpCrammerSingerDecomp::tExample::variables.

Referenced by Solve(), and Unshrink().

void QpCrammerSingerDecomp::Solve	(	Array< double > &	solutionVector,
		double	beta,
		double	eps = `0.001`
	)

solve the quadratic program

Parameters:

	solutionVector	input: initial feasible vector $\alpha$ ; output: solution $\alpha^*$
	beta	regularization constant (corresponding to 1/C in the C-SVM)
	eps	solution accuracy, in terms of the maximum KKT violation

Definition at line 2303 of file QuadraticProgram.cpp.

References QpCrammerSingerDecomp::tExample::active, activeEx, activeVar, alpha, boxMax, boxMin, bUnshrinked, classes, diagonal, epsilon, example, examples, gradient, i, iter, kernelMatrix, linear, maxIter, optimal, CachedMatrix::Row(), SelectWorkingSet(), Shrink(), Unshrink(), variable, QpCrammerSingerDecomp::tExample::variables, and variables.

Referenced by SVM_Optimizer::optimize().

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

Active all variables.

Definition at line 2594 of file QuadraticProgram.cpp.

References activeEx, activeVar, alpha, classes, example, examples, gradient, i, kernelMatrix, linear, CachedMatrix::Row(), Shrink(), variable, and variables.

Referenced by Shrink(), and Solve().

Member Data Documentation

unsigned int QpCrammerSingerDecomp::activeEx [protected]

number of currently active examples

Definition at line 1182 of file QuadraticProgram.h.

Referenced by DeactivateExample(), SelectWorkingSet(), Shrink(), Solve(), and Unshrink().

unsigned int QpCrammerSingerDecomp::activeVar [protected]

number of currently active variables

Definition at line 1185 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), Solve(), and Unshrink().

Array<double> QpCrammerSingerDecomp::alpha [protected]

Solution candidate.

Definition at line 1196 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), QpCrammerSingerDecomp(), SelectWorkingSet(), Shrink(), Solve(), and Unshrink().

Array<double> QpCrammerSingerDecomp::boxMax [protected]

box constraint upper bound, that is, maximal variable value

Definition at line 1179 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), QpCrammerSingerDecomp(), SelectWorkingSet(), Shrink(), and Solve().

Array<double> QpCrammerSingerDecomp::boxMin [protected]

box constraint lower bound, that is, minimal variable value

Definition at line 1176 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), QpCrammerSingerDecomp(), SelectWorkingSet(), Shrink(), and Solve().

bool QpCrammerSingerDecomp::bUnshrinked [protected]

true if the problem has already been unshrinked

Definition at line 1210 of file QuadraticProgram.h.

Referenced by Shrink(), and Solve().

unsigned int QpCrammerSingerDecomp::classes [protected]

Definition at line 1166 of file QuadraticProgram.h.

Referenced by DeactivateExample(), Solve(), and Unshrink().

Array<double> QpCrammerSingerDecomp::diagonal [protected]

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

Definition at line 1189 of file QuadraticProgram.h.

Referenced by DeactivateExample(), QpCrammerSingerDecomp(), and Solve().

double QpCrammerSingerDecomp::epsilon [protected]

stopping condition - solution accuracy

Definition at line 1199 of file QuadraticProgram.h.

Referenced by Shrink(), and Solve().

std::vector<tExample> QpCrammerSingerDecomp::example [protected]

information about each training example

Definition at line 1157 of file QuadraticProgram.h.

Referenced by DeactivateExample(), DeactivateVariable(), QpCrammerSingerDecomp(), SelectWorkingSet(), Shrink(), Solve(), and Unshrink().

unsigned int QpCrammerSingerDecomp::examples [protected]

Definition at line 1165 of file QuadraticProgram.h.

Referenced by QpCrammerSingerDecomp(), Solve(), and Unshrink().

Array<double> QpCrammerSingerDecomp::gradient [protected]

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

Definition at line 1193 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), QpCrammerSingerDecomp(), SelectWorkingSet(), Shrink(), Solve(), and Unshrink().

SharkInt64 QpCrammerSingerDecomp::iter [protected]

solution statistics: number of iterations

Definition at line 1219 of file QuadraticProgram.h.

Referenced by iterations(), and Solve().

CachedMatrix& QpCrammerSingerDecomp::kernelMatrix [protected]

kernel matrix cache

Definition at line 1170 of file QuadraticProgram.h.

Referenced by DeactivateExample(), QpCrammerSingerDecomp(), Shrink(), Solve(), and Unshrink().

Array<double> QpCrammerSingerDecomp::linear [protected]

linear part of the objective function

Definition at line 1173 of file QuadraticProgram.h.

Referenced by DeactivateVariable(), QpCrammerSingerDecomp(), Solve(), and Unshrink().

SharkInt64 QpCrammerSingerDecomp::maxIter [protected]

maximum number of iterations

Definition at line 1227 of file QuadraticProgram.h.

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

bool QpCrammerSingerDecomp::optimal [protected]

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

Definition at line 1224 of file QuadraticProgram.h.

Referenced by isOptimal(), and Solve().

std::vector<unsigned int> QpCrammerSingerDecomp::storage [protected]

space for the example[i].variables pointers

Definition at line 1163 of file QuadraticProgram.h.

Referenced by QpCrammerSingerDecomp().

std::vector<tVariable> QpCrammerSingerDecomp::variable [protected]

information about each variable of the problem

Definition at line 1160 of file QuadraticProgram.h.

Referenced by DeactivateExample(), DeactivateVariable(), QpCrammerSingerDecomp(), Solve(), and Unshrink().

unsigned int QpCrammerSingerDecomp::variables [protected]

Definition at line 1167 of file QuadraticProgram.h.

Referenced by QpCrammerSingerDecomp(), Solve(), and Unshrink().

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


Classes
struct	tExample
	data structure describing one training example More...
struct	tVariable
	data structure describing one variable of the problem More...
Public Member Functions
	QpCrammerSingerDecomp (CachedMatrix &kernel, const Array< double > &y, unsigned int classes)
	Constructor.
virtual	~QpCrammerSingerDecomp ()
	Destructor.
void	Solve (Array< double > &solutionVector, double beta, double eps=0.001)
	solve the quadratic program
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
Protected Member Functions
double	SelectWorkingSet (unsigned int &i, unsigned int &j)
void	Shrink ()
	Shrink the problem.
void	Unshrink (bool complete=false)
	Active all variables.
void	DeactivateVariable (unsigned int v)
	shrink a variable
void	DeactivateExample (unsigned int e)
	shrink an examples
Protected Attributes
std::vector< tExample >	example
	information about each training example
std::vector< tVariable >	variable
	information about each variable of the problem
std::vector< unsigned int >	storage
	space for the example[i].variables pointers
unsigned int	examples
unsigned int	classes
unsigned int	variables
CachedMatrix &	kernelMatrix
	kernel matrix cache
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
unsigned int	activeEx
	number of currently active examples
unsigned int	activeVar
	number of currently active variables
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.
double	epsilon
	stopping condition - solution accuracy
bool	bUnshrinked
	true if the problem has already been unshrinked
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