SHOGUN  6.0.0
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 
14 
15 #include <shogun/kernel/Kernel.h>
18 #include <shogun/io/SGIO.h>
19 
20 using namespace shogun;
21 
24  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
25 {
26  SG_UNSTABLE("CScatterSVM::CScatterSVM()", "\n")
27 }
28 
31  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
32 {
33 }
34 
37  norm_wc(NULL), norm_wc_len(0), norm_wcw(NULL), norm_wcw_len(0), rho(0), m_num_classes(0)
38 {
39 }
40 
42 {
43  SG_FREE(norm_wc);
44  SG_FREE(norm_wcw);
45 }
46 
47 void CScatterSVM::register_params()
48 {
49  SG_ADD((machine_int_t*) &scatter_type, "scatter_type", "Type of scatter SVM", MS_NOT_AVAILABLE);
50  m_parameters->add_vector(&norm_wc, &norm_wc_len, "norm_wc", "Norm of w_c");
51  m_parameters->add_vector(&norm_wcw, &norm_wcw_len, "norm_wcw", "Norm of w_cw");
52  SG_ADD(&rho, "rho", "Scatter SVM rho", MS_NOT_AVAILABLE);
53  SG_ADD(&m_num_classes, "m_num_classes", "Number of classes", MS_NOT_AVAILABLE);
54 }
55 
57 {
60 
62  int32_t num_vectors = m_labels->get_num_labels();
63 
64  if (data)
65  {
66  if (m_labels->get_num_labels() != data->get_num_vectors())
67  SG_ERROR("Number of training vectors does not match number of labels\n")
68  m_kernel->init(data, data);
69  }
70 
71  int32_t* numc=SG_MALLOC(int32_t, m_num_classes);
73 
74  for (int32_t i=0; i<num_vectors; i++)
75  numc[(int32_t) ((CMulticlassLabels*) m_labels)->get_int_label(i)]++;
76 
77  int32_t Nc=0;
78  int32_t Nmin=num_vectors;
79  for (int32_t i=0; i<m_num_classes; i++)
80  {
81  if (numc[i]>0)
82  {
83  Nc++;
84  Nmin=CMath::min(Nmin, numc[i]);
85  }
86 
87  }
88  SG_FREE(numc);
89  m_num_classes=Nc;
90 
91  bool result=false;
92 
94  {
95  result=train_no_bias_libsvm();
96  }
97 
99  {
100  float64_t nu_min=((float64_t) Nc)/num_vectors;
101  float64_t nu_max=((float64_t) Nc)*Nmin/num_vectors;
102 
103  SG_INFO("valid nu interval [%f ... %f]\n", nu_min, nu_max)
104 
105  if (get_nu()<nu_min || get_nu()>nu_max)
106  SG_ERROR("nu out of valid range [%f ... %f]\n", nu_min, nu_max)
107 
108  result=train_testrule12();
109  }
110  else
111  SG_ERROR("Unknown Scatter type\n")
112 
113  return result;
114 }
115 
116 bool CScatterSVM::train_no_bias_libsvm()
117 {
118  svm_problem problem;
119  svm_parameter param;
120  struct svm_model* model = nullptr;
121 
122  struct svm_node* x_space;
123 
124  problem.l=m_labels->get_num_labels();
125  SG_INFO("%d trainlabels\n", problem.l)
126 
127  problem.y=SG_MALLOC(float64_t, problem.l);
128  problem.x=SG_MALLOC(struct svm_node*, problem.l);
129  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
130 
131  for (int32_t i=0; i<problem.l; i++)
132  {
133  problem.y[i]=+1;
134  problem.x[i]=&x_space[2*i];
135  x_space[2*i].index=i;
136  x_space[2*i+1].index=-1;
137  }
138 
139  int32_t weights_label[2]={-1,+1};
140  float64_t weights[2]={1.0,get_C()/get_C()};
141 
143  ASSERT(m_kernel->get_num_vec_lhs()==problem.l)
144 
145  param.svm_type=C_SVC; // Nu MC SVM
146  param.kernel_type = LINEAR;
147  param.degree = 3;
148  param.gamma = 0; // 1/k
149  param.coef0 = 0;
150  param.nu = get_nu(); // Nu
151  CKernelNormalizer* prev_normalizer=m_kernel->get_normalizer();
153  m_num_classes-1, -1, m_labels, prev_normalizer));
154  param.kernel=m_kernel;
156  param.C = 0;
157  param.eps = get_epsilon();
158  param.p = 0.1;
159  param.shrinking = 0;
160  param.nr_weight = 2;
161  param.weight_label = weights_label;
162  param.weight = weights;
163  param.nr_class=m_num_classes;
164  param.use_bias = svm_proto()->get_bias_enabled();
165 
166  const char* error_msg = svm_check_parameter(&problem,&param);
167 
168  if(error_msg)
169  SG_ERROR("Error: %s\n",error_msg)
170 
171  model = svm_train(&problem, &param);
172  m_kernel->set_normalizer(prev_normalizer);
173  SG_UNREF(prev_normalizer);
174 
175  if (model)
176  {
177  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
178 
179  ASSERT(model->nr_class==m_num_classes)
181 
182  rho=model->rho[0];
183 
184  SG_FREE(norm_wcw);
187 
188  for (int32_t i=0; i<m_num_classes; i++)
189  {
190  int32_t num_sv=model->nSV[i];
191 
192  CSVM* svm=new CSVM(num_sv);
193  svm->set_bias(model->rho[i+1]);
194  norm_wcw[i]=model->normwcw[i];
195 
196 
197  for (int32_t j=0; j<num_sv; j++)
198  {
199  svm->set_alpha(j, model->sv_coef[i][j]);
200  svm->set_support_vector(j, model->SV[i][j].index);
201  }
202 
203  set_svm(i, svm);
204  }
205 
206  SG_FREE(problem.x);
207  SG_FREE(problem.y);
208  SG_FREE(x_space);
209  for (int32_t i=0; i<m_num_classes; i++)
210  {
211  SG_FREE(model->SV[i]);
212  model->SV[i]=NULL;
213  }
214  svm_destroy_model(model);
215 
217  compute_norm_wc();
218 
219  model=NULL;
220  return true;
221  }
222  else
223  return false;
224 }
225 
226 
227 
228 bool CScatterSVM::train_testrule12()
229 {
230  svm_problem problem;
231  svm_parameter param;
232  struct svm_model* model = nullptr;
233 
234  struct svm_node* x_space;
235  problem.l=m_labels->get_num_labels();
236  SG_INFO("%d trainlabels\n", problem.l)
237 
238  problem.y=SG_MALLOC(float64_t, problem.l);
239  problem.x=SG_MALLOC(struct svm_node*, problem.l);
240  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
241 
242  for (int32_t i=0; i<problem.l; i++)
243  {
244  problem.y[i]=((CMulticlassLabels*) m_labels)->get_label(i);
245  problem.x[i]=&x_space[2*i];
246  x_space[2*i].index=i;
247  x_space[2*i+1].index=-1;
248  }
249 
250  int32_t weights_label[2]={-1,+1};
251  float64_t weights[2]={1.0,get_C()/get_C()};
252 
254  ASSERT(m_kernel->get_num_vec_lhs()==problem.l)
255 
256  param.svm_type=NU_MULTICLASS_SVC; // Nu MC SVM
257  param.kernel_type = LINEAR;
258  param.degree = 3;
259  param.gamma = 0; // 1/k
260  param.coef0 = 0;
261  param.nu = get_nu(); // Nu
262  param.kernel=m_kernel;
264  param.C = 0;
265  param.eps = get_epsilon();
266  param.p = 0.1;
267  param.shrinking = 0;
268  param.nr_weight = 2;
269  param.weight_label = weights_label;
270  param.weight = weights;
271  param.nr_class=m_num_classes;
272  param.use_bias = svm_proto()->get_bias_enabled();
273 
274  const char* error_msg = svm_check_parameter(&problem,&param);
275 
276  if(error_msg)
277  SG_ERROR("Error: %s\n",error_msg)
278 
279  model = svm_train(&problem, &param);
280 
281  if (model)
282  {
283  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef))
284 
285  ASSERT(model->nr_class==m_num_classes)
287 
288  rho=model->rho[0];
289 
290  SG_FREE(norm_wcw);
293 
294  for (int32_t i=0; i<m_num_classes; i++)
295  {
296  int32_t num_sv=model->nSV[i];
297 
298  CSVM* svm=new CSVM(num_sv);
299  svm->set_bias(model->rho[i+1]);
300  norm_wcw[i]=model->normwcw[i];
301 
302 
303  for (int32_t j=0; j<num_sv; j++)
304  {
305  svm->set_alpha(j, model->sv_coef[i][j]);
306  svm->set_support_vector(j, model->SV[i][j].index);
307  }
308 
309  set_svm(i, svm);
310  }
311 
312  SG_FREE(problem.x);
313  SG_FREE(problem.y);
314  SG_FREE(x_space);
315  for (int32_t i=0; i<m_num_classes; i++)
316  {
317  SG_FREE(model->SV[i]);
318  model->SV[i]=NULL;
319  }
320  svm_destroy_model(model);
321 
323  compute_norm_wc();
324 
325  model=NULL;
326  return true;
327  }
328  else
329  return false;
330 }
331 
332 void CScatterSVM::compute_norm_wc()
333 {
334  SG_FREE(norm_wc);
335  norm_wc = SG_MALLOC(float64_t, m_machines->get_num_elements());
337  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
338  norm_wc[i]=0;
339 
340 
341  for (int c=0; c<m_machines->get_num_elements(); c++)
342  {
343  CSVM* svm=get_svm(c);
344  int32_t num_sv = svm->get_num_support_vectors();
345 
346  for (int32_t i=0; i<num_sv; i++)
347  {
348  int32_t ii=svm->get_support_vector(i);
349  for (int32_t j=0; j<num_sv; j++)
350  {
351  int32_t jj=svm->get_support_vector(j);
352  norm_wc[c]+=svm->get_alpha(i)*m_kernel->kernel(ii,jj)*svm->get_alpha(j);
353  }
354  }
355  }
356 
357  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
358  norm_wc[i]=CMath::sqrt(norm_wc[i]);
359 
361 }
362 
364 {
365  CMulticlassLabels* output=NULL;
366  if (!m_kernel)
367  {
368  SG_ERROR("SVM can not proceed without kernel!\n")
369  return NULL;
370  }
371 
373  return NULL;
374 
375  int32_t num_vectors=m_kernel->get_num_vec_rhs();
376 
377  output=new CMulticlassLabels(num_vectors);
378  SG_REF(output);
379 
380  if (scatter_type == TEST_RULE1)
381  {
383  for (int32_t i=0; i<num_vectors; i++)
384  output->set_label(i, apply_one(i));
385  }
386 
387  else
388  {
390  ASSERT(num_vectors==output->get_num_labels())
391  CLabels** outputs=SG_MALLOC(CLabels*, m_machines->get_num_elements());
392 
393  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
394  {
395  //SG_PRINT("svm %d\n", i)
396  CSVM *svm = get_svm(i);
397  ASSERT(svm)
398  svm->set_kernel(m_kernel);
399  svm->set_labels(m_labels);
400  outputs[i]=svm->apply();
401  SG_UNREF(svm);
402  }
403 
404  for (int32_t i=0; i<num_vectors; i++)
405  {
406  int32_t winner=0;
407  float64_t max_out=((CRegressionLabels*) outputs[0])->get_label(i)/norm_wc[0];
408 
409  for (int32_t j=1; j<m_machines->get_num_elements(); j++)
410  {
411  float64_t out=((CRegressionLabels*) outputs[j])->get_label(i)/norm_wc[j];
412 
413  if (out>max_out)
414  {
415  winner=j;
416  max_out=out;
417  }
418  }
419 
420  output->set_label(i, winner);
421  }
422 
423  for (int32_t i=0; i<m_machines->get_num_elements(); i++)
424  SG_UNREF(outputs[i]);
425 
426  SG_FREE(outputs);
427  }
428 
429  return output;
430 }
431 
433 {
435  float64_t* outputs=SG_MALLOC(float64_t, m_machines->get_num_elements());
436  int32_t winner=0;
437 
438  if (scatter_type == TEST_RULE1)
439  {
440  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
441  outputs[c]=get_svm(c)->get_bias()-rho;
442 
443  for (int32_t c=0; c<m_machines->get_num_elements(); c++)
444  {
445  float64_t v=0;
446 
447  for (int32_t i=0; i<get_svm(c)->get_num_support_vectors(); i++)
448  {
449  float64_t alpha=get_svm(c)->get_alpha(i);
450  int32_t svidx=get_svm(c)->get_support_vector(i);
451  v += alpha*m_kernel->kernel(svidx, num);
452  }
453 
454  outputs[c] += v;
455  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
456  outputs[j] -= v/m_machines->get_num_elements();
457  }
458 
459  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
460  outputs[j]/=norm_wcw[j];
461 
462  float64_t max_out=outputs[0];
463  for (int32_t j=0; j<m_machines->get_num_elements(); j++)
464  {
465  if (outputs[j]>max_out)
466  {
467  max_out=outputs[j];
468  winner=j;
469  }
470  }
471  }
472 
473  else
474  {
475  float64_t max_out=get_svm(0)->apply_one(num)/norm_wc[0];
476 
477  for (int32_t i=1; i<m_machines->get_num_elements(); i++)
478  {
479  outputs[i]=get_svm(i)->apply_one(num)/norm_wc[i];
480  if (outputs[i]>max_out)
481  {
482  winner=i;
483  max_out=outputs[i];
484  }
485  }
486  }
487 
488  SG_FREE(outputs);
489  return winner;
490 }
virtual float64_t apply_one(int32_t num)
virtual bool init(CFeatures *lhs, CFeatures *rhs)
Definition: Kernel.cpp:81
virtual bool train_machine(CFeatures *data=NULL)
Definition: ScatterSVM.cpp:56
#define SG_INFO(...)
Definition: SGIO.h:117
virtual ELabelType get_label_type() const =0
Real Labels are real-valued labels.
float64_t * norm_wcw
Definition: ScatterSVM.h:119
virtual float64_t apply_one(int32_t num)
Definition: ScatterSVM.cpp:432
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:133
virtual int32_t get_num_vectors() const =0
CLabels * m_labels
Definition: Machine.h:365
#define SG_ERROR(...)
Definition: SGIO.h:128
Parameter * m_parameters
Definition: SGObject.h:567
virtual int32_t get_num_labels() const
float64_t kernel(int32_t idx_a, int32_t idx_b)
float64_t * norm_wc
Definition: ScatterSVM.h:115
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)
Multiclass Labels for multi-class classification.
virtual CKernelNormalizer * get_normalizer()
Definition: Kernel.cpp:145
#define ASSERT(x)
Definition: SGIO.h:200
class MultiClassSVM
Definition: MulticlassSVM.h:28
void set_bias(float64_t bias)
CMulticlassStrategy * m_multiclass_strategy
virtual ~CScatterSVM()
Definition: ScatterSVM.cpp:41
double float64_t
Definition: common.h:60
bool set_alpha(int32_t idx, float64_t val)
SCATTER_TYPE scatter_type
Definition: ScatterSVM.h:112
float64_t get_alpha(int32_t idx)
the scatter kernel normalizer
bool set_support_vector(int32_t idx, int32_t val)
static void fill_vector(T *vec, int32_t len, T value)
Definition: SGVector.cpp:264
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()
#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:32
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:30
bool create_multiclass_svm(int32_t num_classes)
static T min(T a, T b)
Definition: Math.h:153
A generic Support Vector Machine Interface.
Definition: SVM.h:49
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:363
virtual bool has_features()
virtual void set_labels(CLabels *lab)
Definition: Machine.cpp:65
#define SG_UNSTABLE(func,...)
Definition: SGIO.h:131
CSVM * get_svm(int32_t num)
Definition: MulticlassSVM.h:76
void display_vector(const char *name="vector", const char *prefix="") const
Definition: SGVector.cpp:396
virtual CLabels * apply(CFeatures *data=NULL)
Definition: Machine.cpp:152

SHOGUN Machine Learning Toolbox - Documentation