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.

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
float64_tproj
float64_ttmp_proj
int32_t * tmp_proj_idx
float64_tsum_CXy_active
float64_tv
float64_told_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_tgrad_w
float64_t grad_b
float64_tgrad_proj
float64_thinge_point
int32_t * hinge_idx
float64_tbeta
CCplexsolver
float64_t lpmtim

Constructor & Destructor Documentation

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