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:

Definition at line 48 of file SubGradientLPM.h.

List of all members.

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
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
void compute_projection (int32_t num_feat, int32_t num_vec)
 compute projection
void update_projection (float64_t alpha, int32_t num_vec)
 only computes updates on the projection
void init (int32_t num_vec, int32_t num_feat)
 alloc helper arrays
void cleanup ()
 de-alloc helper arrays
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
int32_t * tmp_proj_idx
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_b
int32_t * hinge_idx
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 [protected, virtual]
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

c_neg new C constant for negatively labeled examples
c_pos new 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  )  [protected, virtual]

train classifier

data training data (parameter can be avoided if distance or kernel-based classifiers are used and distance/kernels are initialized with train data)
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.

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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation