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

SHOGUN Machine Learning Toolbox - Documentation