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 46 of file SubGradientLPM.h.

Inheritance diagram for CSubGradientLPM:
Inheritance graph
[legend]

List of all members.

Public Member Functions

 CSubGradientLPM ()
 CSubGradientLPM (float64_t C, CDotFeatures *traindat, CLabels *trainlab)
virtual ~CSubGradientLPM ()
virtual EClassifierType get_classifier_type ()
virtual bool train ()
void set_C (float64_t c1, float64_t c2)
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

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

Constructor & Destructor Documentation

CSubGradientLPM::CSubGradientLPM (  ) 

Definition at line 30 of file SubGradientLPM.cpp.

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

Definition at line 36 of file SubGradientLPM.cpp.

CSubGradientLPM::~CSubGradientLPM (  )  [virtual]

Definition at line 46 of file SubGradientLPM.cpp.


Member Function Documentation

void CSubGradientLPM::cleanup (  )  [protected]

de-alloc helper arrays

Definition at line 502 of file SubGradientLPM.cpp.

float64_t CSubGradientLPM::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 326 of file SubGradientLPM.cpp.

float64_t CSubGradientLPM::compute_objective ( int32_t  num_feat,
int32_t  num_vec 
) [protected]

compute svm objective

Definition at line 412 of file SubGradientLPM.cpp.

void CSubGradientLPM::compute_projection ( int32_t  num_feat,
int32_t  num_vec 
) [protected]

compute projection

Definition at line 425 of file SubGradientLPM.cpp.

int32_t CSubGradientLPM::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 51 of file SubGradientLPM.cpp.

bool CSubGradientLPM::get_bias_enabled (  ) 

Definition at line 64 of file SubGradientLPM.h.

float64_t CSubGradientLPM::get_C1 (  ) 

Definition at line 60 of file SubGradientLPM.h.

float64_t CSubGradientLPM::get_C2 (  ) 

Definition at line 61 of file SubGradientLPM.h.

virtual EClassifierType CSubGradientLPM::get_classifier_type (  )  [virtual]

get classifier type

Returns:
classifier type NONE

Reimplemented from CClassifier.

Definition at line 55 of file SubGradientLPM.h.

float64_t CSubGradientLPM::get_epsilon (  ) 

Definition at line 67 of file SubGradientLPM.h.

virtual const char* CSubGradientLPM::get_name (  )  const [protected, virtual]
Returns:
object name

Implements CSGObject.

Definition at line 111 of file SubGradientLPM.h.

int32_t CSubGradientLPM::get_qpsize (  ) 

Definition at line 70 of file SubGradientLPM.h.

int32_t CSubGradientLPM::get_qpsize_max (  ) 

Definition at line 73 of file SubGradientLPM.h.

void CSubGradientLPM::init ( int32_t  num_vec,
int32_t  num_feat 
) [protected]

alloc helper arrays

Definition at line 436 of file SubGradientLPM.cpp.

float64_t CSubGradientLPM::line_search ( int32_t  num_feat,
int32_t  num_vec 
) [protected]

performs a line search to determine step size

Definition at line 243 of file SubGradientLPM.cpp.

void CSubGradientLPM::set_bias_enabled ( bool  enable_bias  ) 

Definition at line 63 of file SubGradientLPM.h.

void CSubGradientLPM::set_C ( float64_t  c1,
float64_t  c2 
)

Definition at line 58 of file SubGradientLPM.h.

void CSubGradientLPM::set_epsilon ( float64_t  eps  ) 

Definition at line 66 of file SubGradientLPM.h.

void CSubGradientLPM::set_qpsize ( int32_t  q  ) 

Definition at line 69 of file SubGradientLPM.h.

void CSubGradientLPM::set_qpsize_max ( int32_t  q  ) 

Definition at line 72 of file SubGradientLPM.h.

bool CSubGradientLPM::train (  )  [virtual]

train classifier

Returns:
whether training was successful

Reimplemented from CClassifier.

Definition at line 542 of file SubGradientLPM.cpp.

void CSubGradientLPM::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 222 of file SubGradientLPM.cpp.

void CSubGradientLPM::update_projection ( float64_t  alpha,
int32_t  num_vec 
) [protected]

only computes updates on the projection

Definition at line 431 of file SubGradientLPM.cpp.


Member Data Documentation

uint8_t* CSubGradientLPM::active [protected]

Definition at line 128 of file SubGradientLPM.h.

Definition at line 118 of file SubGradientLPM.h.

Definition at line 158 of file SubGradientLPM.h.

Definition at line 114 of file SubGradientLPM.h.

Definition at line 115 of file SubGradientLPM.h.

int32_t CSubGradientLPM::delta_active [protected]

Definition at line 132 of file SubGradientLPM.h.

int32_t CSubGradientLPM::delta_bound [protected]

Definition at line 133 of file SubGradientLPM.h.

Definition at line 116 of file SubGradientLPM.h.

Definition at line 152 of file SubGradientLPM.h.

Definition at line 153 of file SubGradientLPM.h.

Definition at line 151 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::hinge_idx [protected]

Definition at line 155 of file SubGradientLPM.h.

Definition at line 154 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::idx_active [protected]

Definition at line 130 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::idx_bound [protected]

Definition at line 131 of file SubGradientLPM.h.

Definition at line 124 of file SubGradientLPM.h.

int32_t CSubGradientLPM::neg_idx [protected]

Definition at line 146 of file SubGradientLPM.h.

Definition at line 125 of file SubGradientLPM.h.

uint8_t* CSubGradientLPM::old_active [protected]

Definition at line 129 of file SubGradientLPM.h.

Definition at line 141 of file SubGradientLPM.h.

int32_t CSubGradientLPM::pos_idx [protected]

Definition at line 145 of file SubGradientLPM.h.

Definition at line 134 of file SubGradientLPM.h.

int32_t CSubGradientLPM::qpsize [protected]

Definition at line 119 of file SubGradientLPM.h.

int32_t CSubGradientLPM::qpsize_limit [protected]

Definition at line 121 of file SubGradientLPM.h.

int32_t CSubGradientLPM::qpsize_max [protected]

Definition at line 120 of file SubGradientLPM.h.

Definition at line 160 of file SubGradientLPM.h.

Definition at line 139 of file SubGradientLPM.h.

Definition at line 142 of file SubGradientLPM.h.

Definition at line 135 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::tmp_proj_idx [protected]

Definition at line 136 of file SubGradientLPM.h.

bool CSubGradientLPM::use_bias [protected]

Definition at line 122 of file SubGradientLPM.h.

Definition at line 140 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::w_neg [protected]

Definition at line 150 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::w_pos [protected]

Definition at line 148 of file SubGradientLPM.h.

int32_t* CSubGradientLPM::w_zero [protected]

Definition at line 149 of file SubGradientLPM.h.

Definition at line 117 of file SubGradientLPM.h.

int32_t CSubGradientLPM::zero_idx [protected]

Definition at line 147 of file SubGradientLPM.h.


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

SHOGUN Machine Learning Toolbox - Documentation