shark::QpMcDecomp< Matrix > Class Template Reference

Quadratic program solver for multi class SVM problems. More...

#include <shark/Algorithms/QP/QpMcDecomp.h>

Classes

struct  tExample
 data structure describing one training example More...
 
struct  tVariable
 data structure describing one variable of the problem More...
 

Public Types

typedef Matrix::QpFloatType QpFloatType
 
typedef blas::matrix< QpFloatTypeQpMatrixType
 
typedef blas::matrix_row< QpMatrixTypeQpMatrixRowType
 
typedef blas::matrix_column< QpMatrixTypeQpMatrixColumnType
 

Public Member Functions

 QpMcDecomp (Matrix &kernel, RealMatrix const &_gamma, UIntVector const &_rho, QpSparseArray< QpFloatType > const &_nu, QpSparseArray< QpFloatType > const &_M, bool sumToZeroConstraint)
 
void solve (Data< unsigned int > const &target, double C, RealVector &solutionAlpha, QpStoppingCondition &stop, QpSolutionProperties *prop=NULL, RealVector *solutionBias=NULL)
 solve the quadratic program More...
 
void solveSMO (Data< unsigned int > const &target, double C, RealVector &solutionAlpha, QpStoppingCondition &stop, QpSolutionProperties *prop=NULL, RealVector *solutionBias=NULL)
 solve the quadratic program with SMO More...
 
void setShrinking (bool shrinking=true)
 enable/disable shrinking More...
 

Protected Member Functions

void initializeLP ()
 
void solveForBias (double epsilon)
 
void solveEdge (double &alpha, double g, double Q, double U, double &mu)
 
void solve2D_box (double &alphai, double &alphaj, double gi, double gj, double Qii, double Qij, double Qjj, double Ui, double Uj, double &mui, double &muj)
 
void solve2D_triangle (double &alphai, double &alphaj, double &alphasum, double gi, double gj, double Qii, double Qij, double Qjj, double &mui, double &muj)
 
double checkKKT ()
 return the largest KKT violation More...
 
double selectWorkingSet (std::size_t &i, std::size_t &j)
 select the working set More...
 
double selectWorkingSetSMO (std::size_t &i, std::size_t &j)
 select the working set for SMO More...
 
void shrink (double epsilon)
 Shrink the problem. More...
 
void unshrink (double epsilon, bool complete)
 Activate all variables. More...
 
void deactivateVariable (std::size_t v)
 shrink a variable More...
 
void deactivateExample (std::size_t e)
 shrink an examples More...
 

Protected Attributes

bool bUnshrinked
 true if the problem has already been unshrinked More...
 
std::vector< tExampleexample
 information about each training example More...
 
std::vector< tVariablevariable
 information about each variable of the problem More...
 
std::vector< std::size_t > storage1
 space for the example[i].var pointers More...
 
std::vector< std::size_t > storage2
 space for the example[i].avar pointers More...
 
std::size_t examples
 number of examples in the problem (size of the kernel matrix) More...
 
unsigned int classes
 number of classes in the problem More...
 
unsigned int cardP
 number of dual variables per example More...
 
unsigned int cardR
 number of slack variables per example More...
 
std::size_t variables
 number of variables in the problem = examples times cardP More...
 
Matrix & kernelMatrix
 kernel matrix (precomputed matrix or matrix cache) More...
 
RealMatrix const & gamma
 target margins More...
 
UIntVector const & rho
 mapping connecting constraints (dual variables) to slack variables More...
 
QpSparseArray< QpFloatType > const & nu
 margin coefficients More...
 
QpSparseArray< QpFloatType > const & M
 kernel modifiers More...
 
bool sumToZero
 indicates whether there a sum-to-zero constraint in the problem More...
 
double C
 complexity constant; upper bound on all variables More...
 
RealVector linear
 linear part of the objective function More...
 
std::size_t activeEx
 number of currently active examples More...
 
std::size_t activeVar
 number of currently active variables More...
 
RealVector gradient
 
RealVector alpha
 solution candidate More...
 
RealVector * bias
 solution candidate More...
 
bool useShrinking
 should the solver use the shrinking heuristics? More...
 

Detailed Description

template<class Matrix>
class shark::QpMcDecomp< Matrix >

Quadratic program solver for multi class SVM problems.

This quadratic program solver solves the following primal SVM problem:

\( \min_{w, b, \xi} \quad \frac{1}{2} \sum_c \|w_c\|^2 + C \cdot \sum_{i,r} \xi_{i,r} \)
\( \text{s.t.} \quad \forall i, p: \quad \sum_c \nu_{y_i,p,c} \big( \langle w_c, \phi(x_i) \rangle + b_c \big) \geq \gamma_{p,y_i} - \xi_{i,\rho(p)} \)
\( \text{and} \quad \forall i, r: \quad \xi_{i,r} \geq 0 \)
\( \text{and} \quad \left[ \sum_c \langle w_c, \phi(\cdot) \rangle + b_c = 0 \right] \)
The last so-called sum-to-zero constraint in square brackets is optinal, and so is the presence of the bias variables b. The index i runs over all training examples, p runs over the constraint index set P, r runs over the slack variables index set R, and c runs over the classes. The coefficients \( \nu_{y,p,c} \) define the margin functions (absolute or relative), \( \gamma_{y,p} \) are target margins for these functions, \( \phi \) is a feature map for the kernel function, and \( \rho : P \to R \) connects constraints and slack variables, and depends on the surrogate loss function. Currently, the solver supports only the cases \( \rho = \operatorname{id} \) (sum-loss) and \( |R| = 1 \) (max-loss).
The solver applies a mixed strategy between solving the dual w.r.t. the variables w for fixed b, and solving the primal for b with fixed w. This strategy allows for the application of efficient decomposition algorithms even to seemingly involved cases, like the multi-class SVM by Crammer&Singer with bias parameter.
The implementation of this solver is relatively efficient. It exploits the sparsity of the quadratic term of the dual objective function for relative margins, and it provides caching and shrinking techniques on the level of training examples (and the kernel matrix) and variables (for gradient updates).

Definition at line 187 of file QpMcDecomp.h.

Member Typedef Documentation

§ QpFloatType

template<class Matrix>
typedef Matrix::QpFloatType shark::QpMcDecomp< Matrix >::QpFloatType

Definition at line 195 of file QpMcDecomp.h.

§ QpMatrixColumnType

template<class Matrix>
typedef blas::matrix_column<QpMatrixType> shark::QpMcDecomp< Matrix >::QpMatrixColumnType

Definition at line 198 of file QpMcDecomp.h.

§ QpMatrixRowType

template<class Matrix>
typedef blas::matrix_row<QpMatrixType> shark::QpMcDecomp< Matrix >::QpMatrixRowType

Definition at line 197 of file QpMcDecomp.h.

§ QpMatrixType

template<class Matrix>
typedef blas::matrix<QpFloatType> shark::QpMcDecomp< Matrix >::QpMatrixType

Definition at line 196 of file QpMcDecomp.h.

Constructor & Destructor Documentation

§ QpMcDecomp()

template<class Matrix>
shark::QpMcDecomp< Matrix >::QpMcDecomp ( Matrix &  kernel,
RealMatrix const &  _gamma,
UIntVector const &  _rho,
QpSparseArray< QpFloatType > const &  _nu,
QpSparseArray< QpFloatType > const &  _M,
bool  sumToZeroConstraint 
)
inline

Constructor

Parameters
kernelkernel matrix - cache or pre-computed matrix
_gamma_gamma(y, p) is the target margin of constraint p for examples of class y
_rhomapping from constraints to slack variables
_numargin coefficients in the format \( \nu_{y,p,c} = _\nu(|P|*y+p, c) \)
_Mkernel modifiers in the format \( M_(y_i, p, y_j, q) = _M(classes*(y_i*|P|+p_i)+y_j, q) \)
sumToZeroConstraintenable or disable the sum-to-zero constraint

Definition at line 207 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::cardP, shark::QpMcDecomp< Matrix >::cardR, shark::QpMcDecomp< Matrix >::classes, shark::QpMcDecomp< Matrix >::examples, shark::QpMcDecomp< Matrix >::gamma, shark::QpMcDecomp< Matrix >::kernelMatrix, shark::QpMcDecomp< Matrix >::M, shark::QpMcDecomp< Matrix >::nu, shark::QpMcDecomp< Matrix >::rho, SHARK_CHECK, SHARKEXCEPTION, shark::QpMcDecomp< Matrix >::useShrinking, and shark::QpMcDecomp< Matrix >::variables.

Member Function Documentation

§ checkKKT()

§ deactivateExample()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::deactivateExample ( std::size_t  e)
inlineprotected

§ deactivateVariable()

§ initializeLP()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::initializeLP ( )
inlineprotected

Initialize the linear project member LP for solving the problem with bias parameters.

Definition at line 882 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::solve(), and shark::QpMcDecomp< Matrix >::solveSMO().

§ selectWorkingSet()

template<class Matrix>
double shark::QpMcDecomp< Matrix >::selectWorkingSet ( std::size_t &  i,
std::size_t &  j 
)
inlineprotected

select the working set

Select one or two variables for the sub-problem and return the maximal KKT violation. The method MAY select the same index for i and j. In that case the working set consists of a single variable. The working set may be invalid if the method reports a KKT violation of zero, indicating optimality.

Definition at line 1439 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::tExample::active, shark::QpMcDecomp< Matrix >::activeEx, shark::QpMcDecomp< Matrix >::activeVar, shark::QpMcDecomp< Matrix >::alpha, shark::QpMcDecomp< Matrix >::tExample::avar, shark::QpMcDecomp< Matrix >::C, shark::QpMcDecomp< Matrix >::cardP, shark::QpMcDecomp< Matrix >::cardR, shark::QpMcDecomp< Matrix >::classes, shark::QpSparseArray< QpFloatType >::Row::defaultvalue, shark::QpMcDecomp< Matrix >::tVariable::diagonal, shark::QpSparseArray< QpFloatType >::Row::entry, GAIN_SELECTION_BOX, GAIN_SELECTION_TRIANGLE, shark::QpMcDecomp< Matrix >::gradient, shark::QpMcDecomp< Matrix >::tVariable::i, shark::QpSparseArray< QpFloatType >::Entry::index, shark::QpMcDecomp< Matrix >::kernelMatrix, shark::QpMcDecomp< Matrix >::M, shark::QpMcDecomp< Matrix >::tVariable::p, shark::blas::row(), SHARK_ASSERT, shark::QpSparseArray< QpFloatType >::Row::size, shark::QpSparseArray< QpFloatType >::Entry::value, shark::QpMcDecomp< Matrix >::tExample::var, shark::QpMcDecomp< Matrix >::variable, shark::QpMcDecomp< Matrix >::tExample::varsum, and shark::QpMcDecomp< Matrix >::tExample::y.

Referenced by shark::QpMcDecomp< Matrix >::solve().

§ selectWorkingSetSMO()

template<class Matrix>
double shark::QpMcDecomp< Matrix >::selectWorkingSetSMO ( std::size_t &  i,
std::size_t &  j 
)
inlineprotected

select the working set for SMO

Select one or two variables for the sub-problem and return the maximal KKT violation. The method MAY select the same index for i and j. In that case the working set consists of a single variable. The working set may be invalid if the method reports a KKT violation of zero, indicating optimality.

Definition at line 1720 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::activeVar, shark::QpMcDecomp< Matrix >::alpha, shark::QpMcDecomp< Matrix >::C, shark::QpMcDecomp< Matrix >::cardP, shark::QpMcDecomp< Matrix >::cardR, shark::QpMcDecomp< Matrix >::gradient, SHARKEXCEPTION, and shark::QpMcDecomp< Matrix >::variable.

Referenced by shark::QpMcDecomp< Matrix >::solveSMO().

§ setShrinking()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::setShrinking ( bool  shrinking = true)
inline

enable/disable shrinking

Definition at line 876 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::useShrinking.

Referenced by shark::McSvmMMRTrainer< InputType, CacheType >::train().

§ shrink()

§ solve()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::solve ( Data< unsigned int > const &  target,
double  C,
RealVector &  solutionAlpha,
QpStoppingCondition stop,
QpSolutionProperties prop = NULL,
RealVector *  solutionBias = NULL 
)
inline

solve the quadratic program

Parameters
targetclass labels in {0, ..., classes-1}
Cregularization constant, upper bound on all variables
solutionAlphainput: initial feasible vector \( \alpha \); output: solution \( \alpha^* \)
stopstopping condition(s)
propsolution properties (may be NULL)
solutionBiasinput: initial bias parameters \( b \); output: solution \( b^* \). If this parameter is NULL, then the corresponding problem without bias is solved.

Definition at line 258 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::activeEx, shark::QpMcDecomp< Matrix >::activeVar, shark::QpMcDecomp< Matrix >::alpha, shark::QpMcDecomp< Matrix >::bias, shark::QpMcDecomp< Matrix >::bUnshrinked, shark::QpMcDecomp< Matrix >::C, shark::QpMcDecomp< Matrix >::cardP, shark::QpMcDecomp< Matrix >::cardR, shark::QpMcDecomp< Matrix >::checkKKT(), shark::QpMcDecomp< Matrix >::classes, shark::Data< Type >::element(), shark::QpSparseArray< QpFloatType >::Row::entry, shark::QpMcDecomp< Matrix >::examples, shark::QpMcDecomp< Matrix >::gamma, shark::QpMcDecomp< Matrix >::gradient, GRADIENT_UPDATE, shark::QpSparseArray< QpFloatType >::Entry::index, shark::QpMcDecomp< Matrix >::initializeLP(), ITERATIONS_BETWEEN_SHRINKING, shark::QpMcDecomp< Matrix >::kernelMatrix, shark::QpMcDecomp< Matrix >::linear, shark::QpMcDecomp< Matrix >::M, shark::QpStoppingCondition::maxIterations, shark::QpStoppingCondition::maxSeconds, shark::QpStoppingCondition::minAccuracy, shark::Timer::now(), shark::QpMcDecomp< Matrix >::nu, shark::Data< Type >::numberOfElements(), shark::QpAccuracyReached, shark::QpMaxIterationsReached, shark::QpTimeout, shark::blas::row(), shark::QpMcDecomp< Matrix >::selectWorkingSet(), SHARK_ASSERT, shark::QpMcDecomp< Matrix >::shrink(), shark::QpSparseArray< QpFloatType >::Row::size, SIZE_CHECK, shark::QpMcDecomp< Matrix >::solve2D_box(), shark::QpMcDecomp< Matrix >::solve2D_triangle(), shark::QpMcDecomp< Matrix >::solveForBias(), shark::QpMcDecomp< Matrix >::storage1, shark::QpMcDecomp< Matrix >::storage2, shark::QpMcDecomp< Matrix >::unshrink(), shark::QpMcDecomp< Matrix >::useShrinking, shark::QpSparseArray< QpFloatType >::Entry::value, shark::QpMcDecomp< Matrix >::variable, shark::QpMcDecomp< Matrix >::variables, and w.

Referenced by shark::McSvmMMRTrainer< InputType, CacheType >::train().

§ solve2D_box()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::solve2D_box ( double &  alphai,
double &  alphaj,
double  gi,
double  gj,
double  Qii,
double  Qij,
double  Qjj,
double  Ui,
double  Uj,
double &  mui,
double &  muj 
)
inlineprotected

Exact solver for the S2DO problem for the case that the sub-problem has box-constraints. The method updates alpha and in addition returns the step mu.

Definition at line 1186 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::solveEdge().

Referenced by shark::QpMcDecomp< Matrix >::solve().

§ solve2D_triangle()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::solve2D_triangle ( double &  alphai,
double &  alphaj,
double &  alphasum,
double  gi,
double  gj,
double  Qii,
double  Qij,
double  Qjj,
double &  mui,
double &  muj 
)
inlineprotected

Exact solver for the S2DO problem for the case that the sub-problem has simplex-constraints. The method updates alpha and in addition returns the step mu.

Definition at line 1271 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::C, and shark::QpMcDecomp< Matrix >::solveEdge().

Referenced by shark::QpMcDecomp< Matrix >::solve().

§ solveEdge()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::solveEdge ( double &  alpha,
double  g,
double  Q,
double  U,
double &  mu 
)
inlineprotected

Exact solver for the one-dimensional sub-problem
maximize \( g \alpha - Q/2 \mu^2 \)
such that \( 0 \leq \alpha \leq U \)
The method returns the optimal alpha as well as the step mu leading to the update \( \alpha \leftarrow \alpha + \mu \).

Definition at line 1146 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::alpha.

Referenced by shark::QpMcDecomp< Matrix >::solve2D_box(), and shark::QpMcDecomp< Matrix >::solve2D_triangle().

§ solveForBias()

§ solveSMO()

template<class Matrix>
void shark::QpMcDecomp< Matrix >::solveSMO ( Data< unsigned int > const &  target,
double  C,
RealVector &  solutionAlpha,
QpStoppingCondition stop,
QpSolutionProperties prop = NULL,
RealVector *  solutionBias = NULL 
)
inline

solve the quadratic program with SMO

Parameters
targetclass labels in {0, ..., classes-1}
Cregularization constant, upper bound on all variables
solutionAlphainput: initial feasible vector \( \alpha \); output: solution \( \alpha^* \)
stopstopping condition(s)
propsolution properties (may be NULL)
solutionBiasinput: initial bias parameters \( b \); output: solution \( b^* \). If this parameter is NULL, then the corresponding problem without bias is solved.

Definition at line 605 of file QpMcDecomp.h.

References shark::QpMcDecomp< Matrix >::activeEx, shark::QpMcDecomp< Matrix >::activeVar, shark::QpMcDecomp< Matrix >::alpha, shark::QpMcDecomp< Matrix >::bias, shark::QpMcDecomp< Matrix >::bUnshrinked, shark::QpMcDecomp< Matrix >::C, shark::QpMcDecomp< Matrix >::cardP, shark::QpMcDecomp< Matrix >::cardR, shark::QpMcDecomp< Matrix >::checkKKT(), shark::QpMcDecomp< Matrix >::classes, shark::Data< Type >::element(), shark::QpSparseArray< QpFloatType >::Row::entry, shark::QpMcDecomp< Matrix >::examples, shark::QpMcDecomp< Matrix >::gamma, shark::QpMcDecomp< Matrix >::gradient, GRADIENT_UPDATE, shark::QpSparseArray< QpFloatType >::Entry::index, shark::QpMcDecomp< Matrix >::initializeLP(), ITERATIONS_BETWEEN_SHRINKING, shark::QpMcDecomp< Matrix >::kernelMatrix, shark::QpMcDecomp< Matrix >::linear, shark::QpMcDecomp< Matrix >::M, shark::QpStoppingCondition::maxIterations, shark::QpStoppingCondition::maxSeconds, shark::QpStoppingCondition::minAccuracy, shark::Timer::now(), shark::QpMcDecomp< Matrix >::nu, shark::Data< Type >::numberOfElements(), shark::QpAccuracyReached, shark::QpMaxIterationsReached, shark::QpTimeout, shark::blas::row(), shark::QpMcDecomp< Matrix >::selectWorkingSetSMO(), SHARKEXCEPTION, shark::QpMcDecomp< Matrix >::shrink(), shark::QpSparseArray< QpFloatType >::Row::size, SIZE_CHECK, shark::QpMcDecomp< Matrix >::solveForBias(), shark::QpMcDecomp< Matrix >::storage1, shark::QpMcDecomp< Matrix >::storage2, shark::QpMcDecomp< Matrix >::unshrink(), shark::QpMcDecomp< Matrix >::useShrinking, shark::QpSparseArray< QpFloatType >::Entry::value, shark::QpMcDecomp< Matrix >::variable, shark::QpMcDecomp< Matrix >::variables, and w.

Referenced by shark::McSvmMMRTrainer< InputType, CacheType >::train().

§ unshrink()

Member Data Documentation

§ activeEx

§ activeVar

§ alpha

§ bias

template<class Matrix>
RealVector* shark::QpMcDecomp< Matrix >::bias
protected

§ bUnshrinked

template<class Matrix>
bool shark::QpMcDecomp< Matrix >::bUnshrinked
protected

true if the problem has already been unshrinked

Definition at line 1904 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::shrink(), shark::QpMcDecomp< Matrix >::solve(), and shark::QpMcDecomp< Matrix >::solveSMO().

§ C

§ cardP

§ cardR

§ classes

§ example

template<class Matrix>
std::vector<tExample> shark::QpMcDecomp< Matrix >::example
protected

information about each training example

Definition at line 1992 of file QpMcDecomp.h.

§ examples

template<class Matrix>
std::size_t shark::QpMcDecomp< Matrix >::examples
protected

§ gamma

template<class Matrix>
RealMatrix const& shark::QpMcDecomp< Matrix >::gamma
protected

§ gradient

§ kernelMatrix

§ linear

template<class Matrix>
RealVector shark::QpMcDecomp< Matrix >::linear
protected

§ M

§ nu

§ rho

template<class Matrix>
UIntVector const& shark::QpMcDecomp< Matrix >::rho
protected

mapping connecting constraints (dual variables) to slack variables

Definition at line 2025 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::QpMcDecomp().

§ storage1

template<class Matrix>
std::vector<std::size_t> shark::QpMcDecomp< Matrix >::storage1
protected

space for the example[i].var pointers

Definition at line 1998 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::solve(), and shark::QpMcDecomp< Matrix >::solveSMO().

§ storage2

template<class Matrix>
std::vector<std::size_t> shark::QpMcDecomp< Matrix >::storage2
protected

space for the example[i].avar pointers

Definition at line 2001 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::solve(), and shark::QpMcDecomp< Matrix >::solveSMO().

§ sumToZero

template<class Matrix>
bool shark::QpMcDecomp< Matrix >::sumToZero
protected

indicates whether there a sum-to-zero constraint in the problem

Definition at line 2034 of file QpMcDecomp.h.

Referenced by shark::QpMcDecomp< Matrix >::solveForBias().

§ useShrinking

template<class Matrix>
bool shark::QpMcDecomp< Matrix >::useShrinking
protected

§ variable

§ variables

template<class Matrix>
std::size_t shark::QpMcDecomp< Matrix >::variables
protected

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