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

Classes
struct	Example
	data structure describing one training example More...

struct	PreferedSelectionStrategy
	Working set selection eturning th S2DO working set. More...

struct	Variable
	data structure describing one m_variables of the problem More...

Public Types
typedef Matrix::QpFloatType	QpFloatType

Public Member Functions
	QpMcBoxDecomp (Matrix &kernel, QpSparseArray< QpFloatType > const &M, Data< unsigned int > const &target, RealMatrix const &linearMat, double C)

void	setShrinking (bool shrinking=true)
	enable/disable shrinking More...

RealMatrix	solution () const
	Return the solution found. More...

double	alpha (std::size_t i, std::size_t p) const

RealMatrix	solutionGradient () const
	Return the gradient of the solution. More...

double	functionValue () const
	Compute the objective value of the current solution. More...

unsigned int	label (std::size_t i)

std::size_t	dimensions () const

std::size_t	cardP () const

std::size_t	getNumExamples () const

double	checkKKT () const
	return the largest KKT violation More...

void	addDeltaLinear (RealMatrix const &deltaLinear)
	change the linear part of the problem by some delta More...

void	updateSMO (std::size_t v, std::size_t w)

bool	shrink (double epsilon)
	Shrink the problem. More...

void	unshrink ()
	Activate all variables. More...

double	selectWorkingSet (std::size_t &i, std::size_t &j)
	select the working set More...

Protected Member Functions
void	gradientUpdate (std::size_t r, double mu, QpFloatType *q)

void	deactivateVariable (std::size_t v)
	shrink a variable More...

void	deactivateExample (std::size_t e)
	shrink an m_examples More...

std::size_t	originalIndex (std::size_t v) const
	Returns the original index of the example of a variable in the dataset before optimization. More...

Protected Attributes
bool	bUnshrinked
	true if the problem has already been unshrinked More...

Matrix &	m_kernelMatrix
	kernel matrix (precomputed matrix or matrix cache) More...

QpSparseArray< QpFloatType > const &	m_M
	kernel modifiers More...

double	m_C
	complexity constant; upper bound on all variabless More...

unsigned int	m_classes
	number of m_classes in the problem More...

std::size_t	m_cardP
	number of dual m_numVariables per example More...

std::size_t	m_numExamples
	number of m_examples in the problem (size of the kernel matrix) More...

std::size_t	m_numVariables
	number of m_numVariables in the problem = m_examples times m_cardP More...

RealVector	m_linear
	m_linear part of the objective function More...

RealVector	m_alpha
	solution candidate More...

RealVector	m_gradient

std::vector< Example >	m_examples
	information about each training example More...

std::vector< Variable >	m_variables
	information about each m_variables of the problem More...

std::vector< std::size_t >	m_storage1
	space for the example[i].var pointers More...

std::vector< std::size_t >	m_storage2
	space for the example[i].avar pointers More...

std::size_t	m_activeEx
	number of currently active m_examples More...

std::size_t	m_activeVar
	number of currently active variabless More...

bool	m_useShrinking
	should the m_problem use the shrinking heuristics? More...

Detailed Description

template<class Matrix>
class shark::QpMcBoxDecomp< Matrix >

Definition at line 50 of file QpMcBoxDecomp.h.

Member Typedef Documentation

◆ QpFloatType

template<class Matrix>

typedef Matrix::QpFloatType shark::QpMcBoxDecomp< Matrix >::QpFloatType

Definition at line 53 of file QpMcBoxDecomp.h.

Constructor & Destructor Documentation

◆ QpMcBoxDecomp()

template<class Matrix>

shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp	(	Matrix &	kernel,
		QpSparseArray< QpFloatType > const &	M,
		Data< unsigned int > const &	target,
		RealMatrix const &	linearMat,
		double	C
	)

inline

Constructor

Parameters

kernel	kernel matrix - cache or pre-computed matrix
M	kernel modifiers in the format \( M_(y_i, p, y_j, q) = _M(classes(y_i\|P\|+p_i)+y_j, q) \)
target	the target labels for the variables
linearMat	the linear part of the problem
C	upper bound for all box variables, lower bound is 0.

Definition at line 74 of file QpMcBoxDecomp.h.

Member Function Documentation

◆ addDeltaLinear()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::addDeltaLinear ( RealMatrix const & deltaLinear )

inline

change the linear part of the problem by some delta

Definition at line 198 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_cardP, shark::QpMcBoxDecomp< Matrix >::m_gradient, shark::QpMcBoxDecomp< Matrix >::m_linear, shark::QpMcBoxDecomp< Matrix >::m_numExamples, shark::QpMcBoxDecomp< Matrix >::m_numVariables, shark::QpMcBoxDecomp< Matrix >::m_variables, shark::QpMcBoxDecomp< Matrix >::originalIndex(), and SIZE_CHECK.

◆ alpha()

template<class Matrix>

double shark::QpMcBoxDecomp< Matrix >::alpha	(	std::size_t	i,
		std::size_t	p
	)		const

inline

Definition at line 144 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_alpha, and shark::QpMcBoxDecomp< Matrix >::m_cardP.

◆ cardP()

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::cardP ( ) const

inline

Definition at line 169 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_cardP.

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

◆ checkKKT()

template<class Matrix>

double shark::QpMcBoxDecomp< Matrix >::checkKKT ( ) const

inline

return the largest KKT violation

Definition at line 178 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_activeVar, shark::QpMcBoxDecomp< Matrix >::m_alpha, shark::QpMcBoxDecomp< Matrix >::m_C, and shark::QpMcBoxDecomp< Matrix >::m_gradient.

◆ deactivateExample()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::deactivateExample ( std::size_t e )

inlineprotected

shrink an m_examples

Definition at line 528 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_activeEx, shark::QpMcBoxDecomp< Matrix >::m_activeVar, shark::QpMcBoxDecomp< Matrix >::m_cardP, shark::QpMcBoxDecomp< Matrix >::m_examples, shark::QpMcBoxDecomp< Matrix >::m_kernelMatrix, shark::QpMcBoxDecomp< Matrix >::m_variables, SHARK_ASSERT, and shark::swap().

◆ deactivateVariable()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::deactivateVariable ( std::size_t v )

inlineprotected

shrink a variable

Definition at line 490 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::Example::active, shark::QpMcBoxDecomp< Matrix >::Example::avar, h, shark::QpMcBoxDecomp< Matrix >::m_activeVar, shark::QpMcBoxDecomp< Matrix >::m_alpha, shark::QpMcBoxDecomp< Matrix >::m_examples, shark::QpMcBoxDecomp< Matrix >::m_gradient, shark::QpMcBoxDecomp< Matrix >::m_linear, shark::QpMcBoxDecomp< Matrix >::m_variables, shark::swap(), and shark::QpMcBoxDecomp< Matrix >::Example::var.

◆ dimensions()

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::dimensions ( ) const

inline

Definition at line 166 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_numVariables.

◆ functionValue()

template<class Matrix>

double shark::QpMcBoxDecomp< Matrix >::functionValue ( ) const

inline

Compute the objective value of the current solution.

Definition at line 158 of file QpMcBoxDecomp.h.

◆ getNumExamples()

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::getNumExamples ( ) const

inline

Definition at line 173 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_numExamples.

◆ gradientUpdate()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::gradientUpdate	(	std::size_t	r,
		double	mu,
		QpFloatType *	q
	)

inlineprotected

Definition at line 466 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_activeEx, and shark::QpMcBoxDecomp< Matrix >::m_examples.

Referenced by shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ label()

template<class Matrix>

unsigned int shark::QpMcBoxDecomp< Matrix >::label ( std::size_t i )

inline

Definition at line 162 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_examples.

◆ originalIndex()

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::originalIndex ( std::size_t v ) const

inlineprotected

Returns the original index of the example of a variable in the dataset before optimization.

Shrinking is an internal detail so the communication with the outside world uses the original indizes.

Definition at line 552 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_examples, and shark::QpMcBoxDecomp< Matrix >::m_variables.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::solution(), and shark::QpMcBoxDecomp< Matrix >::solutionGradient().

◆ selectWorkingSet()

template<class Matrix>

double shark::QpMcBoxDecomp< Matrix >::selectWorkingSet	(	std::size_t &	i,
		std::size_t &	j
	)

inline

select the working set

Select one or two numVariables 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 variables. The working set may be invalid if the method reports a KKT violation of zero, indicating optimality.

Definition at line 390 of file QpMcBoxDecomp.h.

◆ setShrinking()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::setShrinking ( bool shrinking = true )

inline

enable/disable shrinking

Definition at line 129 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_useShrinking.

◆ shrink()

template<class Matrix>

bool shark::QpMcBoxDecomp< Matrix >::shrink ( double epsilon )

inline

Shrink the problem.

Definition at line 272 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::bUnshrinked, shark::QpMcBoxDecomp< Matrix >::m_activeVar, shark::QpMcBoxDecomp< Matrix >::m_alpha, shark::QpMcBoxDecomp< Matrix >::m_C, and shark::QpMcBoxDecomp< Matrix >::m_useShrinking.

◆ solution()

template<class Matrix>

RealMatrix shark::QpMcBoxDecomp< Matrix >::solution ( ) const

inline

Return the solution found.

Definition at line 135 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_alpha, shark::QpMcBoxDecomp< Matrix >::m_cardP, shark::QpMcBoxDecomp< Matrix >::m_numVariables, shark::QpMcBoxDecomp< Matrix >::m_variables, and shark::QpMcBoxDecomp< Matrix >::originalIndex().

◆ solutionGradient()

template<class Matrix>

RealMatrix shark::QpMcBoxDecomp< Matrix >::solutionGradient ( ) const

inline

Return the gradient of the solution.

Definition at line 148 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_cardP, shark::QpMcBoxDecomp< Matrix >::m_gradient, shark::QpMcBoxDecomp< Matrix >::m_numVariables, shark::QpMcBoxDecomp< Matrix >::m_variables, and shark::QpMcBoxDecomp< Matrix >::originalIndex().

◆ unshrink()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::unshrink ( )

inline

Activate all variables.

Definition at line 332 of file QpMcBoxDecomp.h.

References shark::QpMcBoxDecomp< Matrix >::m_activeVar, and shark::QpMcBoxDecomp< Matrix >::m_numVariables.

◆ updateSMO()

template<class Matrix>

void shark::QpMcBoxDecomp< Matrix >::updateSMO	(	std::size_t	v,
		std::size_t	w
	)

inline

Definition at line 210 of file QpMcBoxDecomp.h.

Member Data Documentation

◆ bUnshrinked

template<class Matrix>

bool shark::QpMcBoxDecomp< Matrix >::bUnshrinked

protected

true if the problem has already been unshrinked

Definition at line 487 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::shrink().

◆ m_activeEx

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::m_activeEx

protected

number of currently active m_examples

Definition at line 629 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::gradientUpdate(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_activeVar

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::m_activeVar

protected

number of currently active variabless

Definition at line 632 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::checkKKT(), shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), shark::QpMcBoxDecomp< Matrix >::shrink(), shark::QpMcBoxDecomp< Matrix >::unshrink(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_alpha

template<class Matrix>

RealVector shark::QpMcBoxDecomp< Matrix >::m_alpha

protected

solution candidate

Definition at line 610 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::alpha(), shark::QpMcBoxDecomp< Matrix >::checkKKT(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), shark::QpMcBoxDecomp< Matrix >::shrink(), shark::QpMcBoxDecomp< Matrix >::solution(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_C

template<class Matrix>

double shark::QpMcBoxDecomp< Matrix >::m_C

protected

complexity constant; upper bound on all variabless

Definition at line 592 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::checkKKT(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), shark::QpMcBoxDecomp< Matrix >::shrink(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_cardP

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::m_cardP

protected

number of dual m_numVariables per example

Definition at line 598 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::alpha(), shark::QpMcBoxDecomp< Matrix >::cardP(), shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::solution(), shark::QpMcBoxDecomp< Matrix >::solutionGradient(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_classes

template<class Matrix>

unsigned int shark::QpMcBoxDecomp< Matrix >::m_classes

protected

number of m_classes in the problem

Definition at line 595 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_examples

template<class Matrix>

std::vector<Example> shark::QpMcBoxDecomp< Matrix >::m_examples

protected

information about each training example

Definition at line 617 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), shark::QpMcBoxDecomp< Matrix >::gradientUpdate(), shark::QpMcBoxDecomp< Matrix >::label(), shark::QpMcBoxDecomp< Matrix >::originalIndex(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_gradient

template<class Matrix>

RealVector shark::QpMcBoxDecomp< Matrix >::m_gradient

protected

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

Definition at line 614 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::checkKKT(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), shark::QpMcBoxDecomp< Matrix >::solutionGradient(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_kernelMatrix

template<class Matrix>

Matrix& shark::QpMcBoxDecomp< Matrix >::m_kernelMatrix

protected

kernel matrix (precomputed matrix or matrix cache)

Definition at line 586 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_linear

template<class Matrix>

RealVector shark::QpMcBoxDecomp< Matrix >::m_linear

protected

m_linear part of the objective function

Definition at line 607 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), and shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp().

◆ m_M

template<class Matrix>

QpSparseArray<QpFloatType> const& shark::QpMcBoxDecomp< Matrix >::m_M

protected

kernel modifiers

Definition at line 589 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

◆ m_numExamples

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::m_numExamples

protected

number of m_examples in the problem (size of the kernel matrix)

Definition at line 601 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::getNumExamples(), and shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp().

◆ m_numVariables

template<class Matrix>

std::size_t shark::QpMcBoxDecomp< Matrix >::m_numVariables

protected

number of m_numVariables in the problem = m_examples times m_cardP

Definition at line 604 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::dimensions(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::solution(), shark::QpMcBoxDecomp< Matrix >::solutionGradient(), and shark::QpMcBoxDecomp< Matrix >::unshrink().

◆ m_storage1

template<class Matrix>

std::vector<std::size_t> shark::QpMcBoxDecomp< Matrix >::m_storage1

protected

space for the example[i].var pointers

Definition at line 623 of file QpMcBoxDecomp.h.

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

◆ m_storage2

template<class Matrix>

std::vector<std::size_t> shark::QpMcBoxDecomp< Matrix >::m_storage2

protected

space for the example[i].avar pointers

Definition at line 626 of file QpMcBoxDecomp.h.

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

◆ m_useShrinking

template<class Matrix>

bool shark::QpMcBoxDecomp< Matrix >::m_useShrinking

protected

should the m_problem use the shrinking heuristics?

Definition at line 635 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::setShrinking(), and shark::QpMcBoxDecomp< Matrix >::shrink().

◆ m_variables

template<class Matrix>

std::vector<Variable> shark::QpMcBoxDecomp< Matrix >::m_variables

protected

information about each m_variables of the problem

Definition at line 620 of file QpMcBoxDecomp.h.

Referenced by shark::QpMcBoxDecomp< Matrix >::addDeltaLinear(), shark::QpMcBoxDecomp< Matrix >::deactivateExample(), shark::QpMcBoxDecomp< Matrix >::deactivateVariable(), shark::QpMcBoxDecomp< Matrix >::originalIndex(), shark::QpMcBoxDecomp< Matrix >::QpMcBoxDecomp(), shark::QpMcBoxDecomp< Matrix >::selectWorkingSet(), shark::QpMcBoxDecomp< Matrix >::solution(), shark::QpMcBoxDecomp< Matrix >::solutionGradient(), and shark::QpMcBoxDecomp< Matrix >::updateSMO().

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

include/shark/Algorithms/QP/QpMcBoxDecomp.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class Matrix> class shark::QpMcBoxDecomp< Matrix >

Member Typedef Documentation

◆ QpFloatType

Constructor & Destructor Documentation

◆ QpMcBoxDecomp()

Member Function Documentation

◆ addDeltaLinear()

◆ alpha()

◆ cardP()

◆ checkKKT()

◆ deactivateExample()

◆ deactivateVariable()

◆ dimensions()

◆ functionValue()

◆ getNumExamples()

◆ gradientUpdate()

◆ label()

◆ originalIndex()

◆ selectWorkingSet()

◆ setShrinking()

◆ shrink()

◆ solution()

◆ solutionGradient()

◆ unshrink()

◆ updateSMO()

Member Data Documentation

◆ bUnshrinked

◆ m_activeEx

◆ m_activeVar

◆ m_alpha

◆ m_C

◆ m_cardP

◆ m_classes

◆ m_examples

◆ m_gradient

◆ m_kernelMatrix

◆ m_linear

◆ m_M

◆ m_numExamples

◆ m_numVariables

◆ m_storage1

◆ m_storage2

◆ m_useShrinking

◆ m_variables

template<class Matrix>
class shark::QpMcBoxDecomp< Matrix >