SHOGUN  6.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
ScatterSVM.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2009 Soeren Sonnenburg
8  * Written (W) 2009 Marius Kloft
9  * Copyright (C) 2009 TU Berlin and Max-Planck-Society
10  */
12 
13 #ifdef USE_SVMLIGHT
15 #endif //USE_SVMLIGHT
16 
17 #include <shogun/kernel/Kernel.h>
20 #include <shogun/io/SGIO.h>
21 
22 using namespace shogun;
23 
26  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
27 {
28  SG_UNSTABLE("CScatterSVM::CScatterSVM()", "\n")
29 }
30 
32 : CMulticlassSVM(new CMulticlassOneVsRestStrategy()), scatter_type(type),
33  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
34 {
35 }
36 
38 : CMulticlassSVM(new CMulticlassOneVsRestStrategy(), C, k, lab), scatter_type(NO_BIAS_LIBSVM),
39  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
40 {
41 }
42 
44 {
45  SG_FREE(norm_wc);
46  SG_FREE(norm_wcw);
47 }
48 
49 void CScatterSVM::register_params()
50 {
51  SG_ADD((machine_int_t*) &scatter_type, "scatter_type", "Type of scatter SVM", MS_NOT_AVAILABLE);
52  m_parameters->add_vector(&norm_wc, &norm_wc_len, "norm_wc", "Norm of w_c");
53  m_parameters->add_vector(&norm_wcw, &norm_wcw_len, "norm_wcw", "Norm of w_cw");
54  SG_ADD(&rho, "rho", "Scatter SVM rho", MS_NOT_AVAILABLE);
55  SG_ADD(&m_num_classes, "m_num_classes", "Number of classes", MS_NOT_AVAILABLE);
56 }
57 
59 {
62 
64  int32_t num_vectors = m_labels->get_num_labels();
65 
66  if (data)
67  {
68  if (m_labels->get_num_labels() != data->get_num_vectors())
69  SG_ERROR("Number of training vectors does not match number of labels\n")
70  m_kernel->init(data, data);
71  }
72 
73  int32_t* numc=SG_MALLOC(int32_t, m_num_classes);
75 
76  for (int32_t i=0; i<num_vectors; i++)
77  numc[(int32_t) ((CMulticlassLabels*) m_labels)->get_int_label(i)]++;
78 
79  int32_t Nc=0;
80  int32_t Nmin=num_vectors;
81  for (int32_t i=0; i<m_num_classes; i++)
82  {
83  if (numc[i]>0)
84  {
85  Nc++;
86  Nmin=CMath::min(Nmin, numc[i]);
87  }
88 
89  }
90  SG_FREE(numc);
91  m_num_classes=Nc;
92 
93  bool result=false;
94 
96  {
97  result=train_no_bias_libsvm();
98  }
99 #ifdef USE_SVMLIGHT
100  else if (scatter_type==NO_BIAS_SVMLIGHT)
101  {
102  result=train_no_bias_svmlight();
103  }
104 #endif //USE_SVMLIGHT
106  {
107  float64_t nu_min=((float64_t) Nc)/num_vectors;
108  float64_t nu_max=((float64_t) Nc)*Nmin/num_vectors;
109 
110  SG_INFO("valid nu interval [%f ... %f]\n", nu_min, nu_max)
111 
112  if (get_nu()<nu_min || get_nu()>nu_max)
113  SG_ERROR("nu out of valid range [%f ... %f]\n", nu_min, nu_max)
114 
115  result=train_testrule12();
116  }
117  else
118  SG_ERROR("Unknown Scatter type\n")
119 
120  return result;
121 }
122 
123 bool CScatterSVM::train_no_bias_libsvm()
124 {
125  svm_problem problem;
126  svm_parameter param;
127  struct svm_model* model = nullptr;
128 
129  struct svm_node* x_space;
130 
131  problem.l=m_labels->get_num_labels();
132  SG_INFO("%d trainlabels\n", problem.l)
133 
134  problem.y=SG_MALLOC(float64_t, problem.l);
135  problem.x=SG_MALLOC(struct svm_node*, problem.l);
136  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
137 
138  for (int32_t i=0; i<problem.l; i++)
139  {
140  problem.y[i]=+1;
141  problem.x[i]=&x_space[2*i];
142  x_space[2*i].index=i;
143  x_space[2*i+1].index=-1;
144  }
145 
146  int32_t weights_label[2]={-1,+1};
147  float64_t weights[2]={1.0,get_C()/get_C()};
148 
150  ASSERT(m_kernel->get_num_vec_lhs()==problem.l)
151 
152  param.svm_type=C_SVC; // Nu MC SVM
153  param.kernel_type = LINEAR;
154  param.degree = 3;
155  param.gamma = 0; // 1/k
156  param.coef0 = 0;
157  param.nu = get_nu(); // Nu
158  CKernelNormalizer* prev_normalizer=m_kernel->get_normalizer();
160  m_num_classes-1, -1, m_labels, prev_normalizer));
161  param.kernel=m_kernel;
163  param.C = 0;
164  param.eps = get_epsilon();
165  param.p = 0.1;
166  param.shrinking = 0;
167  param.nr_weight = 2;
168  param.weight_label = weights_label;
169  param.weight = weights;
170  param.nr_class=m_num_classes;
171  param.use_bias = svm_proto()->get_bias_enabled();
172 
173  const char* error_msg = svm_check_parameter(&problem,&param);
174 
175  if(error_msg)
176  SG_ERROR("Error: %s\n",error_msg)
177 
178  model = svm_train(&problem, &param);
179  m_kernel->set_normalizer(prev_normalizer);
180  SG_UNREF(prev_normalizer);
181 
182  if (model)
183  {
184  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
185 
186  ASSERT(model->nr_class==m_num_classes)
188 
189  rho=model->rho[0];
190 
191  SG_FREE(norm_wcw);
192  norm_wcw = SG_MALLOC(float64_t, m_machines->get_num_elements());
193  norm_wcw_len = m_machines->get_num_elements();
194 
195  for (int32_t i=0; i<m_num_classes; i++)
196  {
197  int32_t num_sv=model->nSV[i];
198 
199  CSVM* svm=new CSVM(num_sv);
200  svm->set_bias(model->rho[i+1]);
201  norm_wcw[i]=model->normwcw[i];
202 
203 
204  for (int32_t j=0; j<num_sv; j++)
205  {
206  svm->set_alpha(j, model->sv_coef[i][j]);
207  svm->set_support_vector(j, model->SV[i][j].index);
208  }
209 
210  set_svm(i, svm);
211  }
212 
213  SG_FREE(problem.x);
214  SG_FREE(problem.y);
215  SG_FREE(x_space);
216  for (int32_t i=0; i<m_num_classes; i++)
217  {
218  SG_FREE(model->SV[i]);
219  model->SV[i]=NULL;
220  }
221  svm_destroy_model(model);
222 
224  compute_norm_wc();
225 
226  model=NULL;
227  return true;
228  }
229  else
230  return false;
231 }
232 
233 #ifdef USE_SVMLIGHT
234 bool CScatterSVM::train_no_bias_svmlight()
235 {
236  CKernelNormalizer* prev_normalizer=m_kernel->get_normalizer();
238  m_num_classes-1, -1, m_labels, prev_normalizer);
241 
243  light->set_linadd_enabled(false);
244  light->train();
245 
246  SG_FREE(norm_wcw);
247  norm_wcw = SG_MALLOC(float64_t, m_num_classes);
249 
250  int32_t num_sv=light->get_num_support_vectors();
251  svm_proto()->create_new_model(num_sv);
252 
253  for (int32_t i=0; i<num_sv; i++)
254  {
255  svm_proto()->set_alpha(i, light->get_alpha(i));
257  }
258 
259  m_kernel->set_normalizer(prev_normalizer);
260  return true;
261 }
262 #endif //USE_SVMLIGHT
263 
264 bool CScatterSVM::train_testrule12()
265 {
266  svm_problem problem;
267  svm_parameter param;
268  struct svm_model* model = nullptr;
269 
270  struct svm_node* x_space;
271  problem.l=m_labels->get_num_labels();
272  SG_INFO("%d trainlabels\n", problem.l)
273 
274  problem.y=SG_MALLOC(float64_t, problem.l);
275  problem.x=SG_MALLOC(struct svm_node*, problem.l);
276  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
277 
278  for (int32_t i=0; i<problem.l; i++)
279  {
280  problem.y[i]=((CMulticlassLabels*) m_labels)->get_label(i);
281  problem.x[i]=&x_space[2*i];
282  x_space[2*i].index=i;
283  x_space[2*i+1].index=-1;
284  }
285 
286  int32_t weights_label[2]={-1,+1};
287  float64_t weights[2]={1.0,get_C()/get_C()};
288 
290  ASSERT(m_kernel->get_num_vec_lhs()==problem.l)
291 
292  param.svm_type=NU_MULTICLASS_SVC; // Nu MC SVM
293  param.kernel_type = LINEAR;
294  param.degree = 3;
295  param.gamma = 0; // 1/k
296  param.coef0 = 0;
297  param.nu = get_nu(); // Nu
298  param.kernel=m_kernel;
300  param.C = 0;
301  param.eps = get_epsilon();
302  param.p = 0.1;
303  param.shrinking = 0;
304  param.nr_weight = 2;
305  param.weight_label = weights_label;
306  param.weight = weights;
307  param.nr_class=m_num_classes;
308  param.use_bias = svm_proto()->get_bias_enabled();
309 
310  const char* error_msg = svm_check_parameter(&problem,&param);
311 
312  if(error_msg)
313  SG_ERROR("Error: %s\n",error_msg)
314 
315  model = svm_train(&problem, &param);
316 
317  if (model)
318  {
319  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
320 
321  ASSERT(model->nr_class==m_num_classes)
322  create_multiclass_svm(m_num_classes);
323 
324  rho=model->rho[0];
325 
326  SG_FREE(norm_wcw);
327  norm_wcw = SG_MALLOC(float64_t, m_machines->get_num_elements());
328  norm_wcw_len = m_machines->get_num_elements();
329 
330  for (int32_t i=0; i<m_num_classes; i++)
331  {
332  int32_t num_sv=model->nSV[i];
333 
334  CSVM* svm=new CSVM(num_sv);
335  svm->set_bias(model->rho[i+1]);
336  norm_wcw[i]=model->normwcw[i];
337 
338 
339  for (int32_t j=0; j<num_sv; j++)
340  {
341  svm->set_alpha(j, model->sv_coef[i][j]);
342  svm->set_support_vector(j, model->SV[i][j].index);
343  }
344 
345  set_svm(i, svm);
346  }
347 
348  SG_FREE(problem.x);
349  SG_FREE(problem.y);
350  SG_FREE(x_space);
351  for (int32_t i=0; i<m_num_classes; i++)
352  {
353  SG_FREE(model->SV[i]);
354  model->SV[i]=NULL;
355  }
356  svm_destroy_model(model);
357 
359  compute_norm_wc();
360 
361  model=NULL;
362  return true;
363  }
364  else
365  return false;
366 }
367 
368 void CScatterSVM::compute_norm_wc()
369 {
370  SG_FREE(norm_wc);
371  norm_wc = SG_MALLOC(float64_t, m_machines->get_num_elements());
373  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
374  norm_wc[i]=0;
375 
376 
377  for (int c=0; c<m_machines->get_num_elements(); c++)
378  {
379  CSVM* svm=get_svm(c);
380  int32_t num_sv = svm->get_num_support_vectors();
381 
382  for (int32_t i=0; i<num_sv; i++)
383  {
384  int32_t ii=svm->get_support_vector(i);
385  for (int32_t j=0; j<num_sv; j++)
386  {
387  int32_t jj=svm->get_support_vector(j);
388  norm_wc[c]+=svm->get_alpha(i)*m_kernel->kernel(ii,jj)*svm->get_alpha(j);
389  }
390  }
391  }
392 
393  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
394  norm_wc[i]=CMath::sqrt(norm_wc[i]);
395 
397 }
398 
400 {
401  CMulticlassLabels* output=NULL;
402  if (!m_kernel)
403  {
404  SG_ERROR("SVM can not proceed without kernel!\n")
405  return NULL;
406  }
407 
409  return NULL;
410 
411  int32_t num_vectors=m_kernel->get_num_vec_rhs();
412 
413  output=new CMulticlassLabels(num_vectors);
414  SG_REF(output);
415 
416  if (scatter_type == TEST_RULE1)
417  {
419  for (int32_t i=0; i<num_vectors; i++)
420  output->set_label(i, apply_one(i));
421  }
422 #ifdef USE_SVMLIGHT
423  else if (scatter_type == NO_BIAS_SVMLIGHT)
424  {
425  float64_t* outputs=SG_MALLOC(float64_t, num_vectors*m_num_classes);
426  SGVector<float64_t>::fill_vector(outputs,num_vectors*m_num_classes,0.0);
427 
428  for (int32_t i=0; i<num_vectors; i++)
429  {
430  for (int32_t j=0; j<svm_proto()->get_num_support_vectors(); j++)
431  {
432  float64_t score=m_kernel->kernel(svm_proto()->get_support_vector(j), i)*svm_proto()->get_alpha(j);
433  int32_t label=((CMulticlassLabels*) m_labels)->get_int_label(svm_proto()->get_support_vector(j));
434  for (int32_t c=0; c<m_num_classes; c++)
435  {
436  float64_t s= (label==c) ? (m_num_classes-1) : (-1);
437  outputs[c+i*m_num_classes]+=s*score;
438  }
439  }
440  }
441 
442  for (int32_t i=0; i<num_vectors; i++)
443  {
444  int32_t winner=0;
445  float64_t max_out=outputs[i*m_num_classes+0];
446 
447  for (int32_t j=1; j<m_num_classes; j++)
448  {
449  float64_t out=outputs[i*m_num_classes+j];
450 
451  if (out>max_out)
452  {
453  winner=j;
454  max_out=out;
455  }
456  }
457 
458  output->set_label(i, winner);
459  }
460 
461  SG_FREE(outputs);
462  }
463 #endif //USE_SVMLIGHT
464  else
465  {
467  ASSERT(num_vectors==output->get_num_labels())
468  CLabels** outputs=SG_MALLOC(CLabels*, m_machines->get_num_elements());
469 
470  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
471  {
472  //SG_PRINT("svm %d\n", i)
473  CSVM *svm = get_svm(i);
474  ASSERT(svm)
475  svm->set_kernel(m_kernel);
476  svm->set_labels(m_labels);
477  outputs[i]=svm->apply();
478  SG_UNREF(svm);
479  }
480 
481  for (int32_t i=0; i<num_vectors; i++)
482  {
483  int32_t winner=0;
484  float64_t max_out=((CRegressionLabels*) outputs[0])->get_label(i)/norm_wc[0];
485 
486  for (int32_t j=1; j<m_machines->get_num_elements(); j++)
487  {
488  float64_t out=((CRegressionLabels*) outputs[j])->get_label(i)/norm_wc[j];
489 
490  if (out>max_out)
491  {
492  winner=j;
493  max_out=out;
494  }
495  }
496 
497  output->set_label(i, winner);
498  }
499 
500  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
501  SG_UNREF(outputs[i]);
502 
503  SG_FREE(outputs);
504  }
505 
506  return output;
507 }
508 
509 float64_t CScatterSVM::apply_one(int32_t num)
510 {
512  float64_t* outputs=SG_MALLOC(float64_t, m_machines->get_num_elements());
513  int32_t winner=0;
514 
515  if (scatter_type == TEST_RULE1)
516  {
517  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
518  outputs[c]=get_svm(c)->get_bias()-rho;
519 
520  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
521  {
522  float64_t v=0;
523 
524  for (int32_t i=0; i<get_svm(c)->get_num_support_vectors(); i++)
525  {
526  float64_t alpha=get_svm(c)->get_alpha(i);
527  int32_t svidx=get_svm(c)->get_support_vector(i);
528  v += alpha*m_kernel->kernel(svidx, num);
529  }
530 
531  outputs[c] += v;
532  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
533  outputs[j] -= v/m_machines->get_num_elements();
534  }
535 
536  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
537  outputs[j]/=norm_wcw[j];
538 
539  float64_t max_out=outputs[0];
540  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
541  {
542  if (outputs[j]>max_out)
543  {
544  max_out=outputs[j];
545  winner=j;
546  }
547  }
548  }
549 #ifdef USE_SVMLIGHT
550  else if (scatter_type == NO_BIAS_SVMLIGHT)
551  {
552  SG_ERROR("Use classify...\n")
553  }
554 #endif //USE_SVMLIGHT
555  else
556  {
557  float64_t max_out=get_svm(0)->apply_one(num)/norm_wc[0];
558 
559  for (int32_t i=1; i<m_machines->get_num_elements(); i++)
560  {
561  outputs[i]=get_svm(i)->apply_one(num)/norm_wc[i];
562  if (outputs[i]>max_out)
563  {
564  winner=i;
565  max_out=outputs[i];
566  }
567  }
568  }
569 
570  SG_FREE(outputs);
571  return winner;
572 }
virtual float64_t apply_one(int32_t num)
virtual bool init(CFeatures *lhs, CFeatures *rhs)
Definition: Kernel.cpp:96
virtual bool train_machine(CFeatures *data=NULL)
Definition: ScatterSVM.cpp:58
#define SG_INFO(...)
Definition: SGIO.h:117
static void fill_vector(T *vec, int32_t len, T value)
Definition: SGVector.cpp:264
virtual ELabelType get_label_type() const =0
Real Labels are real-valued labels.
float64_t * norm_wcw
Definition: ScatterSVM.h:124
virtual float64_t apply_one(int32_t num)
Definition: ScatterSVM.cpp:509
virtual int32_t get_num_labels() const
no bias w/ libsvm
Definition: ScatterSVM.h:27
The class Labels models labels, i.e. class assignments of objects.
Definition: Labels.h:43
virtual int32_t get_num_labels() const =0
multi-class labels 0,1,...
Definition: LabelTypes.h:20
virtual bool set_normalizer(CKernelNormalizer *normalizer)
Definition: Kernel.cpp:148
virtual int32_t get_num_vectors() const =0
CLabels * m_labels
Definition: Machine.h:365
#define SG_ERROR(...)
Definition: SGIO.h:128
Trains a one class C SVM.
Parameter * m_parameters
Definition: SGObject.h:567
float64_t kernel(int32_t idx_a, int32_t idx_b)
float64_t * norm_wc
Definition: ScatterSVM.h:120
virtual int32_t get_num_vec_lhs()
#define SG_REF(x)
Definition: SGObject.h:52
int32_t cache_size
cache_size in MB
bool set_label(int32_t idx, float64_t label)
void display_vector(const char *name="vector", const char *prefix="") const
Definition: SGVector.cpp:396
Multiclass Labels for multi-class classification.
virtual CKernelNormalizer * get_normalizer()
Definition: Kernel.cpp:160
#define ASSERT(x)
Definition: SGIO.h:200
class MultiClassSVM
Definition: MulticlassSVM.h:28
void set_bias(float64_t bias)
CMulticlassStrategy * m_multiclass_strategy
no bias w/ svmlight
Definition: ScatterSVM.h:30
virtual ~CScatterSVM()
Definition: ScatterSVM.cpp:43
double float64_t
Definition: common.h:60
bool set_alpha(int32_t idx, float64_t val)
SCATTER_TYPE scatter_type
Definition: ScatterSVM.h:117
float64_t get_alpha(int32_t idx)
the scatter kernel normalizer
bool set_support_vector(int32_t idx, int32_t val)
The class Kernel Normalizer defines a function to post-process kernel values.
int32_t get_support_vector(int32_t idx)
virtual int32_t get_num_vec_rhs()
virtual bool init_normalizer()
Definition: Kernel.cpp:166
#define SG_UNREF(x)
Definition: SGObject.h:53
void add_vector(bool **param, index_t *length, const char *name, const char *description="")
Definition: Parameter.cpp:335
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
int machine_int_t
Definition: common.h:69
SCATTER_TYPE
Definition: ScatterSVM.h:24
training with bias using test rule 2
Definition: ScatterSVM.h:35
The class Features is the base class of all feature objects.
Definition: Features.h:68
training with bias using test rule 1
Definition: ScatterSVM.h:33
bool create_multiclass_svm(int32_t num_classes)
static T min(T a, T b)
Definition: Math.h:153
virtual bool train(CFeatures *data=NULL)
Definition: Machine.cpp:39
A generic Support Vector Machine Interface.
Definition: SVM.h:49
void set_linadd_enabled(bool enable)
The Kernel base class.
int32_t get_cache_size()
void set_kernel(CKernel *k)
multiclass one vs rest strategy used to train generic multiclass machines for K-class problems with b...
bool set_svm(int32_t num, CSVM *svm)
#define SG_ADD(...)
Definition: SGObject.h:94
static float32_t sqrt(float32_t x)
Definition: Math.h:454
virtual CLabels * classify_one_vs_rest()
Definition: ScatterSVM.cpp:399
virtual bool has_features()
virtual void set_labels(CLabels *lab)
Definition: Machine.cpp:65
#define SG_UNSTABLE(func,...)
Definition: SGIO.h:131
bool create_new_model(int32_t num)
CSVM * get_svm(int32_t num)
Definition: MulticlassSVM.h:76
virtual CLabels * apply(CFeatures *data=NULL)
Definition: Machine.cpp:152

SHOGUN Machine Learning Toolbox - Documentation