SHOGUN  4.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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  model(NULL), norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
27 {
28  SG_UNSTABLE("CScatterSVM::CScatterSVM()", "\n")
29 }
30 
32 : CMulticlassSVM(new CMulticlassOneVsRestStrategy()), scatter_type(type), model(NULL),
33  norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
34 {
35 }
36 
38 : CMulticlassSVM(new CMulticlassOneVsRestStrategy(), C, k, lab), scatter_type(NO_BIAS_LIBSVM), model(NULL),
39  norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
40 {
41 }
42 
44 {
45  SG_FREE(norm_wc);
46  SG_FREE(norm_wcw);
47 }
48 
50 {
53 
55  int32_t num_vectors = m_labels->get_num_labels();
56 
57  if (data)
58  {
59  if (m_labels->get_num_labels() != data->get_num_vectors())
60  SG_ERROR("Number of training vectors does not match number of labels\n")
61  m_kernel->init(data, data);
62  }
63 
64  int32_t* numc=SG_MALLOC(int32_t, m_num_classes);
66 
67  for (int32_t i=0; i<num_vectors; i++)
68  numc[(int32_t) ((CMulticlassLabels*) m_labels)->get_int_label(i)]++;
69 
70  int32_t Nc=0;
71  int32_t Nmin=num_vectors;
72  for (int32_t i=0; i<m_num_classes; i++)
73  {
74  if (numc[i]>0)
75  {
76  Nc++;
77  Nmin=CMath::min(Nmin, numc[i]);
78  }
79 
80  }
81  SG_FREE(numc);
82  m_num_classes=Nc;
83 
84  bool result=false;
85 
87  {
88  result=train_no_bias_libsvm();
89  }
90 #ifdef USE_SVMLIGHT
92  {
93  result=train_no_bias_svmlight();
94  }
95 #endif //USE_SVMLIGHT
97  {
98  float64_t nu_min=((float64_t) Nc)/num_vectors;
99  float64_t nu_max=((float64_t) Nc)*Nmin/num_vectors;
100 
101  SG_INFO("valid nu interval [%f ... %f]\n", nu_min, nu_max)
102 
103  if (get_nu()<nu_min || get_nu()>nu_max)
104  SG_ERROR("nu out of valid range [%f ... %f]\n", nu_min, nu_max)
105 
106  result=train_testrule12();
107  }
108  else
109  SG_ERROR("Unknown Scatter type\n")
110 
111  return result;
112 }
113 
114 bool CScatterSVM::train_no_bias_libsvm()
115 {
116  struct svm_node* x_space;
117 
119  SG_INFO("%d trainlabels\n", problem.l)
120 
121  problem.y=SG_MALLOC(float64_t, problem.l);
122  problem.x=SG_MALLOC(struct svm_node*, problem.l);
123  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
124 
125  for (int32_t i=0; i<problem.l; i++)
126  {
127  problem.y[i]=+1;
128  problem.x[i]=&x_space[2*i];
129  x_space[2*i].index=i;
130  x_space[2*i+1].index=-1;
131  }
132 
133  int32_t weights_label[2]={-1,+1};
134  float64_t weights[2]={1.0,get_C()/get_C()};
135 
138 
139  param.svm_type=C_SVC; // Nu MC SVM
140  param.kernel_type = LINEAR;
141  param.degree = 3;
142  param.gamma = 0; // 1/k
143  param.coef0 = 0;
144  param.nu = get_nu(); // Nu
145  CKernelNormalizer* prev_normalizer=m_kernel->get_normalizer();
147  m_num_classes-1, -1, m_labels, prev_normalizer));
148  param.kernel=m_kernel;
149  param.cache_size = m_kernel->get_cache_size();
150  param.C = 0;
151  param.eps = get_epsilon();
152  param.p = 0.1;
153  param.shrinking = 0;
154  param.nr_weight = 2;
155  param.weight_label = weights_label;
156  param.weight = weights;
157  param.nr_class=m_num_classes;
158  param.use_bias = svm_proto()->get_bias_enabled();
159 
160  const char* error_msg = svm_check_parameter(&problem,&param);
161 
162  if(error_msg)
163  SG_ERROR("Error: %s\n",error_msg)
164 
165  model = svm_train(&problem, &param);
166  m_kernel->set_normalizer(prev_normalizer);
167  SG_UNREF(prev_normalizer);
168 
169  if (model)
170  {
171  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
172 
173  ASSERT(model->nr_class==m_num_classes)
175 
176  rho=model->rho[0];
177 
178  SG_FREE(norm_wcw);
179  norm_wcw = SG_MALLOC(float64_t, m_machines->get_num_elements());
180 
181  for (int32_t i=0; i<m_num_classes; i++)
182  {
183  int32_t num_sv=model->nSV[i];
184 
185  CSVM* svm=new CSVM(num_sv);
186  svm->set_bias(model->rho[i+1]);
187  norm_wcw[i]=model->normwcw[i];
188 
189 
190  for (int32_t j=0; j<num_sv; j++)
191  {
192  svm->set_alpha(j, model->sv_coef[i][j]);
193  svm->set_support_vector(j, model->SV[i][j].index);
194  }
195 
196  set_svm(i, svm);
197  }
198 
199  SG_FREE(problem.x);
200  SG_FREE(problem.y);
201  SG_FREE(x_space);
202  for (int32_t i=0; i<m_num_classes; i++)
203  {
204  SG_FREE(model->SV[i]);
205  model->SV[i]=NULL;
206  }
207  svm_destroy_model(model);
208 
210  compute_norm_wc();
211 
212  model=NULL;
213  return true;
214  }
215  else
216  return false;
217 }
218 
219 #ifdef USE_SVMLIGHT
220 bool CScatterSVM::train_no_bias_svmlight()
221 {
222  CKernelNormalizer* prev_normalizer=m_kernel->get_normalizer();
224  m_num_classes-1, -1, m_labels, prev_normalizer);
227 
229  light->set_linadd_enabled(false);
230  light->train();
231 
232  SG_FREE(norm_wcw);
233  norm_wcw = SG_MALLOC(float64_t, m_num_classes);
234 
235  int32_t num_sv=light->get_num_support_vectors();
236  svm_proto()->create_new_model(num_sv);
237 
238  for (int32_t i=0; i<num_sv; i++)
239  {
240  svm_proto()->set_alpha(i, light->get_alpha(i));
242  }
243 
244  m_kernel->set_normalizer(prev_normalizer);
245  return true;
246 }
247 #endif //USE_SVMLIGHT
248 
249 bool CScatterSVM::train_testrule12()
250 {
251  struct svm_node* x_space;
252  problem.l=m_labels->get_num_labels();
253  SG_INFO("%d trainlabels\n", problem.l)
254 
255  problem.y=SG_MALLOC(float64_t, problem.l);
256  problem.x=SG_MALLOC(struct svm_node*, problem.l);
257  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
258 
259  for (int32_t i=0; i<problem.l; i++)
260  {
261  problem.y[i]=((CMulticlassLabels*) m_labels)->get_label(i);
262  problem.x[i]=&x_space[2*i];
263  x_space[2*i].index=i;
264  x_space[2*i+1].index=-1;
265  }
266 
267  int32_t weights_label[2]={-1,+1};
268  float64_t weights[2]={1.0,get_C()/get_C()};
269 
271  ASSERT(m_kernel->get_num_vec_lhs()==problem.l)
272 
273  param.svm_type=NU_MULTICLASS_SVC; // Nu MC SVM
274  param.kernel_type = LINEAR;
275  param.degree = 3;
276  param.gamma = 0; // 1/k
277  param.coef0 = 0;
278  param.nu = get_nu(); // Nu
279  param.kernel=m_kernel;
281  param.C = 0;
282  param.eps = get_epsilon();
283  param.p = 0.1;
284  param.shrinking = 0;
285  param.nr_weight = 2;
286  param.weight_label = weights_label;
287  param.weight = weights;
288  param.nr_class=m_num_classes;
289  param.use_bias = svm_proto()->get_bias_enabled();
290 
291  const char* error_msg = svm_check_parameter(&problem,&param);
292 
293  if(error_msg)
294  SG_ERROR("Error: %s\n",error_msg)
295 
296  model = svm_train(&problem, &param);
297 
298  if (model)
299  {
300  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
301 
302  ASSERT(model->nr_class==m_num_classes)
303  create_multiclass_svm(m_num_classes);
304 
305  rho=model->rho[0];
306 
307  SG_FREE(norm_wcw);
308  norm_wcw = SG_MALLOC(float64_t, m_machines->get_num_elements());
309 
310  for (int32_t i=0; i<m_num_classes; i++)
311  {
312  int32_t num_sv=model->nSV[i];
313 
314  CSVM* svm=new CSVM(num_sv);
315  svm->set_bias(model->rho[i+1]);
316  norm_wcw[i]=model->normwcw[i];
317 
318 
319  for (int32_t j=0; j<num_sv; j++)
320  {
321  svm->set_alpha(j, model->sv_coef[i][j]);
322  svm->set_support_vector(j, model->SV[i][j].index);
323  }
324 
325  set_svm(i, svm);
326  }
327 
328  SG_FREE(problem.x);
329  SG_FREE(problem.y);
330  SG_FREE(x_space);
331  for (int32_t i=0; i<m_num_classes; i++)
332  {
333  SG_FREE(model->SV[i]);
334  model->SV[i]=NULL;
335  }
336  svm_destroy_model(model);
337 
339  compute_norm_wc();
340 
341  model=NULL;
342  return true;
343  }
344  else
345  return false;
346 }
347 
348 void CScatterSVM::compute_norm_wc()
349 {
350  SG_FREE(norm_wc);
351  norm_wc = SG_MALLOC(float64_t, m_machines->get_num_elements());
352  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
353  norm_wc[i]=0;
354 
355 
356  for (int c=0; c<m_machines->get_num_elements(); c++)
357  {
358  CSVM* svm=get_svm(c);
359  int32_t num_sv = svm->get_num_support_vectors();
360 
361  for (int32_t i=0; i<num_sv; i++)
362  {
363  int32_t ii=svm->get_support_vector(i);
364  for (int32_t j=0; j<num_sv; j++)
365  {
366  int32_t jj=svm->get_support_vector(j);
367  norm_wc[c]+=svm->get_alpha(i)*m_kernel->kernel(ii,jj)*svm->get_alpha(j);
368  }
369  }
370  }
371 
372  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
373  norm_wc[i]=CMath::sqrt(norm_wc[i]);
374 
376 }
377 
379 {
380  CMulticlassLabels* output=NULL;
381  if (!m_kernel)
382  {
383  SG_ERROR("SVM can not proceed without kernel!\n")
384  return NULL;
385  }
386 
388  return NULL;
389 
390  int32_t num_vectors=m_kernel->get_num_vec_rhs();
391 
392  output=new CMulticlassLabels(num_vectors);
393  SG_REF(output);
394 
395  if (scatter_type == TEST_RULE1)
396  {
398  for (int32_t i=0; i<num_vectors; i++)
399  output->set_label(i, apply_one(i));
400  }
401 #ifdef USE_SVMLIGHT
402  else if (scatter_type == NO_BIAS_SVMLIGHT)
403  {
404  float64_t* outputs=SG_MALLOC(float64_t, num_vectors*m_num_classes);
405  SGVector<float64_t>::fill_vector(outputs,num_vectors*m_num_classes,0.0);
406 
407  for (int32_t i=0; i<num_vectors; i++)
408  {
409  for (int32_t j=0; j<svm_proto()->get_num_support_vectors(); j++)
410  {
411  float64_t score=m_kernel->kernel(svm_proto()->get_support_vector(j), i)*svm_proto()->get_alpha(j);
412  int32_t label=((CMulticlassLabels*) m_labels)->get_int_label(svm_proto()->get_support_vector(j));
413  for (int32_t c=0; c<m_num_classes; c++)
414  {
415  float64_t s= (label==c) ? (m_num_classes-1) : (-1);
416  outputs[c+i*m_num_classes]+=s*score;
417  }
418  }
419  }
420 
421  for (int32_t i=0; i<num_vectors; i++)
422  {
423  int32_t winner=0;
424  float64_t max_out=outputs[i*m_num_classes+0];
425 
426  for (int32_t j=1; j<m_num_classes; j++)
427  {
428  float64_t out=outputs[i*m_num_classes+j];
429 
430  if (out>max_out)
431  {
432  winner=j;
433  max_out=out;
434  }
435  }
436 
437  output->set_label(i, winner);
438  }
439 
440  SG_FREE(outputs);
441  }
442 #endif //USE_SVMLIGHT
443  else
444  {
446  ASSERT(num_vectors==output->get_num_labels())
447  CLabels** outputs=SG_MALLOC(CLabels*, m_machines->get_num_elements());
448 
449  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
450  {
451  //SG_PRINT("svm %d\n", i)
452  CSVM *svm = get_svm(i);
453  ASSERT(svm)
454  svm->set_kernel(m_kernel);
455  svm->set_labels(m_labels);
456  outputs[i]=svm->apply();
457  SG_UNREF(svm);
458  }
459 
460  for (int32_t i=0; i<num_vectors; i++)
461  {
462  int32_t winner=0;
463  float64_t max_out=((CRegressionLabels*) outputs[0])->get_label(i)/norm_wc[0];
464 
465  for (int32_t j=1; j<m_machines->get_num_elements(); j++)
466  {
467  float64_t out=((CRegressionLabels*) outputs[j])->get_label(i)/norm_wc[j];
468 
469  if (out>max_out)
470  {
471  winner=j;
472  max_out=out;
473  }
474  }
475 
476  output->set_label(i, winner);
477  }
478 
479  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
480  SG_UNREF(outputs[i]);
481 
482  SG_FREE(outputs);
483  }
484 
485  return output;
486 }
487 
488 float64_t CScatterSVM::apply_one(int32_t num)
489 {
491  float64_t* outputs=SG_MALLOC(float64_t, m_machines->get_num_elements());
492  int32_t winner=0;
493 
494  if (scatter_type == TEST_RULE1)
495  {
496  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
497  outputs[c]=get_svm(c)->get_bias()-rho;
498 
499  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
500  {
501  float64_t v=0;
502 
503  for (int32_t i=0; i<get_svm(c)->get_num_support_vectors(); i++)
504  {
505  float64_t alpha=get_svm(c)->get_alpha(i);
506  int32_t svidx=get_svm(c)->get_support_vector(i);
507  v += alpha*m_kernel->kernel(svidx, num);
508  }
509 
510  outputs[c] += v;
511  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
512  outputs[j] -= v/m_machines->get_num_elements();
513  }
514 
515  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
516  outputs[j]/=norm_wcw[j];
517 
518  float64_t max_out=outputs[0];
519  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
520  {
521  if (outputs[j]>max_out)
522  {
523  max_out=outputs[j];
524  winner=j;
525  }
526  }
527  }
528 #ifdef USE_SVMLIGHT
529  else if (scatter_type == NO_BIAS_SVMLIGHT)
530  {
531  SG_ERROR("Use classify...\n")
532  }
533 #endif //USE_SVMLIGHT
534  else
535  {
536  float64_t max_out=get_svm(0)->apply_one(num)/norm_wc[0];
537 
538  for (int32_t i=1; i<m_machines->get_num_elements(); i++)
539  {
540  outputs[i]=get_svm(i)->apply_one(num)/norm_wc[i];
541  if (outputs[i]>max_out)
542  {
543  winner=i;
544  max_out=outputs[i];
545  }
546  }
547  }
548 
549  SG_FREE(outputs);
550  return winner;
551 }
virtual float64_t apply_one(int32_t num)
virtual bool init(CFeatures *lhs, CFeatures *rhs)
Definition: Kernel.cpp:98
virtual bool train_machine(CFeatures *data=NULL)
Definition: ScatterSVM.cpp:49
#define SG_INFO(...)
Definition: SGIO.h:118
static void fill_vector(T *vec, int32_t len, T value)
Definition: SGVector.cpp:223
virtual ELabelType get_label_type() const =0
Real Labels are real-valued labels.
float64_t * norm_wcw
Definition: ScatterSVM.h:129
virtual float64_t apply_one(int32_t num)
Definition: ScatterSVM.cpp:488
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:150
virtual int32_t get_num_vectors() const =0
CLabels * m_labels
Definition: Machine.h:361
#define SG_ERROR(...)
Definition: SGIO.h:129
Trains a one class C SVM.
float64_t kernel(int32_t idx_a, int32_t idx_b)
Definition: Kernel.h:206
float64_t * norm_wc
Definition: ScatterSVM.h:126
virtual int32_t get_num_vec_lhs()
Definition: Kernel.h:516
#define SG_REF(x)
Definition: SGObject.h:51
int32_t cache_size
cache_size in MB
Definition: Kernel.h:1047
bool set_label(int32_t idx, float64_t label)
void display_vector(const char *name="vector", const char *prefix="") const
Definition: SGVector.cpp:356
Multiclass Labels for multi-class classification.
virtual CKernelNormalizer * get_normalizer()
Definition: Kernel.cpp:162
#define ASSERT(x)
Definition: SGIO.h:201
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:50
bool set_alpha(int32_t idx, float64_t val)
SCATTER_TYPE scatter_type
Definition: ScatterSVM.h:115
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()
Definition: Kernel.h:525
virtual bool init_normalizer()
Definition: Kernel.cpp:168
#define SG_UNREF(x)
Definition: SGObject.h:52
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
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:157
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.
Definition: Kernel.h:158
int32_t get_cache_size()
Definition: Kernel.h:598
void set_kernel(CKernel *k)
svm_parameter param
Definition: ScatterSVM.h:120
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)
static float32_t sqrt(float32_t x)
Definition: Math.h:459
virtual CLabels * classify_one_vs_rest()
Definition: ScatterSVM.cpp:378
virtual bool has_features()
Definition: Kernel.h:534
virtual void set_labels(CLabels *lab)
Definition: Machine.cpp:65
#define SG_UNSTABLE(func,...)
Definition: SGIO.h:132
bool create_new_model(int32_t num)
CSVM * get_svm(int32_t num)
Definition: MulticlassSVM.h:76
svm_problem problem
Definition: ScatterSVM.h:118
struct svm_model * model
Definition: ScatterSVM.h:123
virtual CLabels * apply(CFeatures *data=NULL)
Definition: Machine.cpp:152

SHOGUN Machine Learning Toolbox - Documentation