SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
List of all members | Public Member Functions | Protected Member Functions | Protected Attributes
CSubGradientLPM Class Reference

Detailed Description

Class SubGradientSVM trains a linear classifier called Linear Programming Machine, i.e. a SVM using a $\ell_1$ norm regularizer.

It solves the following optimization problem using subgradient descent.

\begin{eqnarray*} \min_{{\bf w}={(\bf w^+},{\bf w^-}), b, {\bf \xi}} && \sum_{i=1}^N ( {\bf w}^+_i + {\bf w}^-_i) + C \sum_{i=1}^{N} \xi_i\\ \mbox{s.t.} && -y_i(({\bf w}^+-{\bf w}^-)^T {\bf x}_i + b)-{\bf \xi}_i \leq -1\\ && \quad {\bf x}_i \geq 0\\\ && {\bf w}_i \geq 0,\quad \forall i=1\dots N \end{eqnarray*}

Note that this implementation is not very stable numerically for a large number of dimensions. Also note that currently CPLEX is required to solve this problem.

See Also
CLPBoost
CLPM

Definition at line 48 of file SubGradientLPM.h.

Inheritance diagram for CSubGradientLPM:
Inheritance graph
[legend]

Public Member Functions

 CSubGradientLPM ()
 
 CSubGradientLPM (float64_t C, CDotFeatures *traindat, CLabels *trainlab)
 
virtual ~CSubGradientLPM ()
 
virtual EClassifierType get_classifier_type ()
 
void set_C (float64_t c_neg, float64_t c_pos)
 
float64_t get_C1 ()
 
float64_t get_C2 ()
 
void set_bias_enabled (bool enable_bias)
 
bool get_bias_enabled ()
 
void set_epsilon (float64_t eps)
 
float64_t get_epsilon ()
 
void set_qpsize (int32_t q)
 
int32_t get_qpsize ()
 
void set_qpsize_max (int32_t q)
 
int32_t get_qpsize_max ()
 

Protected Member Functions

int32_t find_active (int32_t num_feat, int32_t num_vec, int32_t &num_active, int32_t &num_bound)
 
void update_active (int32_t num_feat, int32_t num_vec)
 
float64_t compute_objective (int32_t num_feat, int32_t num_vec)
 compute svm objective More...
 
float64_t compute_min_subgradient (int32_t num_feat, int32_t num_vec, int32_t num_active, int32_t num_bound)
 
float64_t line_search (int32_t num_feat, int32_t num_vec)
 performs a line search to determine step size More...
 
void compute_projection (int32_t num_feat, int32_t num_vec)
 compute projection More...
 
void update_projection (float64_t alpha, int32_t num_vec)
 only computes updates on the projection More...
 
void init (int32_t num_vec, int32_t num_feat)
 alloc helper arrays More...
 
void cleanup ()
 de-alloc helper arrays More...
 
virtual const char * get_name () const
 
virtual bool train_machine (CFeatures *data=NULL)
 

Protected Attributes

float64_t C1
 
float64_t C2
 
float64_t epsilon
 
float64_t work_epsilon
 
float64_t autoselected_epsilon
 
int32_t qpsize
 
int32_t qpsize_max
 
int32_t qpsize_limit
 
bool use_bias
 
int32_t last_it_noimprovement
 
int32_t num_it_noimprovement
 
uint8_t * active
 
uint8_t * old_active
 
int32_t * idx_active
 
int32_t * idx_bound
 
int32_t delta_active
 
int32_t delta_bound
 
float64_t * proj
 
float64_t * tmp_proj
 
int32_t * tmp_proj_idx
 
float64_t * sum_CXy_active
 
float64_t * v
 
float64_t * old_v
 
float64_t sum_Cy_active
 
int32_t pos_idx
 
int32_t neg_idx
 
int32_t zero_idx
 
int32_t * w_pos
 
int32_t * w_zero
 
int32_t * w_neg
 
float64_t * grad_w
 
float64_t grad_b
 
float64_t * grad_proj
 
float64_t * hinge_point
 
int32_t * hinge_idx
 
float64_t * beta
 
CCplex * solver
 
float64_t lpmtim
 

Constructor & Destructor Documentation

CSubGradientLPM ( )

Definition at line 29 of file SubGradientLPM.cpp.

CSubGradientLPM ( float64_t  C,
CDotFeatures *  traindat,
CLabels *  trainlab 
)

Definition at line 35 of file SubGradientLPM.cpp.

~CSubGradientLPM ( )
virtual

Definition at line 45 of file SubGradientLPM.cpp.

Member Function Documentation

void cleanup ( )
protected

de-alloc helper arrays

Definition at line 501 of file SubGradientLPM.cpp.

float64_t compute_min_subgradient ( int32_t  num_feat,
int32_t  num_vec,
int32_t  num_active,
int32_t  num_bound 
)
protected

compute minimum norm subgradient return norm of minimum norm subgradient

Definition at line 325 of file SubGradientLPM.cpp.

float64_t compute_objective ( int32_t  num_feat,
int32_t  num_vec 
)
protected

compute svm objective

Definition at line 411 of file SubGradientLPM.cpp.

void compute_projection ( int32_t  num_feat,
int32_t  num_vec 
)
protected

compute projection

Definition at line 424 of file SubGradientLPM.cpp.

int32_t find_active ( int32_t  num_feat,
int32_t  num_vec,
int32_t &  num_active,
int32_t &  num_bound 
)
protected

returns number of changed constraints for precision work_epsilon and fills active array

Definition at line 50 of file SubGradientLPM.cpp.

bool get_bias_enabled ( )

Definition at line 71 of file SubGradientLPM.h.

float64_t get_C1 ( )

Definition at line 67 of file SubGradientLPM.h.

float64_t get_C2 ( )

Definition at line 68 of file SubGradientLPM.h.

virtual EClassifierType get_classifier_type ( )
virtual

Definition at line 57 of file SubGradientLPM.h.

float64_t get_epsilon ( )

Definition at line 74 of file SubGradientLPM.h.

virtual const char* get_name ( ) const
protectedvirtual
Returns
object name

Definition at line 118 of file SubGradientLPM.h.

int32_t get_qpsize ( )

Definition at line 77 of file SubGradientLPM.h.

int32_t get_qpsize_max ( )

Definition at line 80 of file SubGradientLPM.h.

void init ( int32_t  num_vec,
int32_t  num_feat 
)
protected

alloc helper arrays

Definition at line 435 of file SubGradientLPM.cpp.

float64_t line_search ( int32_t  num_feat,
int32_t  num_vec 
)
protected

performs a line search to determine step size

Definition at line 242 of file SubGradientLPM.cpp.

void set_bias_enabled ( bool  enable_bias)

Definition at line 70 of file SubGradientLPM.h.

void set_C ( float64_t  c_neg,
float64_t  c_pos 
)

set C

Parameters
c_negnew C constant for negatively labeled examples
c_posnew C constant for positively labeled examples

Definition at line 65 of file SubGradientLPM.h.

void set_epsilon ( float64_t  eps)

Definition at line 73 of file SubGradientLPM.h.

void set_qpsize ( int32_t  q)

Definition at line 76 of file SubGradientLPM.h.

void set_qpsize_max ( int32_t  q)

Definition at line 79 of file SubGradientLPM.h.

bool train_machine ( CFeatures *  data = NULL)
protectedvirtual

train classifier

Parameters
datatraining data (parameter can be avoided if distance or kernel-based classifiers are used and distance/kernels are initialized with train data)
Returns
whether training was successful

Definition at line 541 of file SubGradientLPM.cpp.

void update_active ( int32_t  num_feat,
int32_t  num_vec 
)
protected

swaps the active / old_active and computes idx_active, idx_bound and sum_CXy_active arrays and the sum_Cy_active variable

Definition at line 221 of file SubGradientLPM.cpp.

void update_projection ( float64_t  alpha,
int32_t  num_vec 
)
protected

only computes updates on the projection

Definition at line 430 of file SubGradientLPM.cpp.

Member Data Documentation

uint8_t* active
protected

Definition at line 146 of file SubGradientLPM.h.

float64_t autoselected_epsilon
protected

Definition at line 136 of file SubGradientLPM.h.

float64_t* beta
protected

Definition at line 176 of file SubGradientLPM.h.

float64_t C1
protected

Definition at line 132 of file SubGradientLPM.h.

float64_t C2
protected

Definition at line 133 of file SubGradientLPM.h.

int32_t delta_active
protected

Definition at line 150 of file SubGradientLPM.h.

int32_t delta_bound
protected

Definition at line 151 of file SubGradientLPM.h.

float64_t epsilon
protected

Definition at line 134 of file SubGradientLPM.h.

float64_t grad_b
protected

Definition at line 170 of file SubGradientLPM.h.

float64_t* grad_proj
protected

Definition at line 171 of file SubGradientLPM.h.

float64_t* grad_w
protected

Definition at line 169 of file SubGradientLPM.h.

int32_t* hinge_idx
protected

Definition at line 173 of file SubGradientLPM.h.

float64_t* hinge_point
protected

Definition at line 172 of file SubGradientLPM.h.

int32_t* idx_active
protected

Definition at line 148 of file SubGradientLPM.h.

int32_t* idx_bound
protected

Definition at line 149 of file SubGradientLPM.h.

int32_t last_it_noimprovement
protected

Definition at line 142 of file SubGradientLPM.h.

float64_t lpmtim
protected

Definition at line 179 of file SubGradientLPM.h.

int32_t neg_idx
protected

Definition at line 164 of file SubGradientLPM.h.

int32_t num_it_noimprovement
protected

Definition at line 143 of file SubGradientLPM.h.

uint8_t* old_active
protected

Definition at line 147 of file SubGradientLPM.h.

float64_t* old_v
protected

Definition at line 159 of file SubGradientLPM.h.

int32_t pos_idx
protected

Definition at line 163 of file SubGradientLPM.h.

float64_t* proj
protected

Definition at line 152 of file SubGradientLPM.h.

int32_t qpsize
protected

Definition at line 137 of file SubGradientLPM.h.

int32_t qpsize_limit
protected

Definition at line 139 of file SubGradientLPM.h.

int32_t qpsize_max
protected

Definition at line 138 of file SubGradientLPM.h.

CCplex* solver
protected

Definition at line 178 of file SubGradientLPM.h.

float64_t* sum_CXy_active
protected

Definition at line 157 of file SubGradientLPM.h.

float64_t sum_Cy_active
protected

Definition at line 160 of file SubGradientLPM.h.

float64_t* tmp_proj
protected

Definition at line 153 of file SubGradientLPM.h.

int32_t* tmp_proj_idx
protected

Definition at line 154 of file SubGradientLPM.h.

bool use_bias
protected

Definition at line 140 of file SubGradientLPM.h.

float64_t* v
protected

Definition at line 158 of file SubGradientLPM.h.

int32_t* w_neg
protected

Definition at line 168 of file SubGradientLPM.h.

int32_t* w_pos
protected

Definition at line 166 of file SubGradientLPM.h.

int32_t* w_zero
protected

Definition at line 167 of file SubGradientLPM.h.

float64_t work_epsilon
protected

Definition at line 135 of file SubGradientLPM.h.

int32_t zero_idx
protected

Definition at line 165 of file SubGradientLPM.h.

The documentation for this class was generated from the following files:
SHOGUN Machine Learning Toolbox - Documentation