SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 
12 
13 #include <shogun/kernel/Kernel.h>
16 #include <shogun/io/SGIO.h>
17 
18 using namespace shogun;
19 
21 : CMultiClassSVM(ONE_VS_REST), scatter_type(NO_BIAS_LIBSVM),
22  model(NULL), norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
23 {
24  SG_UNSTABLE("CScatterSVM::CScatterSVM()", "\n");
25 }
26 
28 : CMultiClassSVM(ONE_VS_REST), scatter_type(type), model(NULL),
29  norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
30 {
31 }
32 
34 : CMultiClassSVM(ONE_VS_REST, C, k, lab), scatter_type(NO_BIAS_LIBSVM), model(NULL),
35  norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
36 {
37 }
38 
40 {
43 }
44 
46 {
49  int32_t num_vectors = labels->get_num_labels();
50 
51  if (data)
52  {
53  if (labels->get_num_labels() != data->get_num_vectors())
54  SG_ERROR("Number of training vectors does not match number of labels\n");
55  kernel->init(data, data);
56  }
57 
58  int32_t* numc=SG_MALLOC(int32_t, m_num_classes);
59  CMath::fill_vector(numc, m_num_classes, 0);
60 
61  for (int32_t i=0; i<num_vectors; i++)
62  numc[(int32_t) labels->get_int_label(i)]++;
63 
64  int32_t Nc=0;
65  int32_t Nmin=num_vectors;
66  for (int32_t i=0; i<m_num_classes; i++)
67  {
68  if (numc[i]>0)
69  {
70  Nc++;
71  Nmin=CMath::min(Nmin, numc[i]);
72  }
73 
74  }
75  SG_FREE(numc);
76  m_num_classes=m_num_classes;
77 
78  bool result=false;
79 
81  {
82  result=train_no_bias_libsvm();
83  }
84 
86  {
87  float64_t nu_min=((float64_t) Nc)/num_vectors;
88  float64_t nu_max=((float64_t) Nc)*Nmin/num_vectors;
89 
90  SG_INFO("valid nu interval [%f ... %f]\n", nu_min, nu_max);
91 
92  if (get_nu()<nu_min || get_nu()>nu_max)
93  SG_ERROR("nu out of valid range [%f ... %f]\n", nu_min, nu_max);
94 
95  result=train_testrule12();
96  }
97  else
98  SG_ERROR("Unknown Scatter type\n");
99 
100  return result;
101 }
102 
103 bool CScatterSVM::train_no_bias_libsvm()
104 {
105  struct svm_node* x_space;
106 
108  SG_INFO( "%d trainlabels\n", problem.l);
109 
111  problem.x=SG_MALLOC(struct svm_node*, problem.l);
112  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
113 
114  for (int32_t i=0; i<problem.l; i++)
115  {
116  problem.y[i]=+1;
117  problem.x[i]=&x_space[2*i];
118  x_space[2*i].index=i;
119  x_space[2*i+1].index=-1;
120  }
121 
122  int32_t weights_label[2]={-1,+1};
123  float64_t weights[2]={1.0,get_C2()/get_C1()};
124 
127 
128  param.svm_type=C_SVC; // Nu MC SVM
129  param.kernel_type = LINEAR;
130  param.degree = 3;
131  param.gamma = 0; // 1/k
132  param.coef0 = 0;
133  param.nu = get_nu(); // Nu
134  CKernelNormalizer* prev_normalizer=kernel->get_normalizer();
136  m_num_classes-1, -1, labels, prev_normalizer));
137  param.kernel=kernel;
138  param.cache_size = kernel->get_cache_size();
139  param.C = 0;
140  param.eps = epsilon;
141  param.p = 0.1;
142  param.shrinking = 0;
143  param.nr_weight = 2;
144  param.weight_label = weights_label;
145  param.weight = weights;
146  param.nr_class=m_num_classes;
147  param.use_bias = get_bias_enabled();
148 
149  const char* error_msg = svm_check_parameter(&problem,&param);
150 
151  if(error_msg)
152  SG_ERROR("Error: %s\n",error_msg);
153 
154  model = svm_train(&problem, &param);
155  kernel->set_normalizer(prev_normalizer);
156  SG_UNREF(prev_normalizer);
157 
158  if (model)
159  {
160  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef));
161 
162  ASSERT(model->nr_class==m_num_classes);
164 
165  rho=model->rho[0];
166 
167  SG_FREE(norm_wcw);
169 
170  for (int32_t i=0; i<m_num_classes; i++)
171  {
172  int32_t num_sv=model->nSV[i];
173 
174  CSVM* svm=new CSVM(num_sv);
175  svm->set_bias(model->rho[i+1]);
176  norm_wcw[i]=model->normwcw[i];
177 
178 
179  for (int32_t j=0; j<num_sv; j++)
180  {
181  svm->set_alpha(j, model->sv_coef[i][j]);
182  svm->set_support_vector(j, model->SV[i][j].index);
183  }
184 
185  set_svm(i, svm);
186  }
187 
188  SG_FREE(problem.x);
189  SG_FREE(problem.y);
190  SG_FREE(x_space);
191  for (int32_t i=0; i<m_num_classes; i++)
192  {
193  SG_FREE(model->SV[i]);
194  model->SV[i]=NULL;
195  }
196  svm_destroy_model(model);
197 
199  compute_norm_wc();
200 
201  model=NULL;
202  return true;
203  }
204  else
205  return false;
206 }
207 
208 
209 
210 bool CScatterSVM::train_testrule12()
211 {
212  struct svm_node* x_space;
214  SG_INFO( "%d trainlabels\n", problem.l);
215 
217  problem.x=SG_MALLOC(struct svm_node*, problem.l);
218  x_space=SG_MALLOC(struct svm_node, 2*problem.l);
219 
220  for (int32_t i=0; i<problem.l; i++)
221  {
222  problem.y[i]=labels->get_label(i);
223  problem.x[i]=&x_space[2*i];
224  x_space[2*i].index=i;
225  x_space[2*i+1].index=-1;
226  }
227 
228  int32_t weights_label[2]={-1,+1};
229  float64_t weights[2]={1.0,get_C2()/get_C1()};
230 
233 
234  param.svm_type=NU_MULTICLASS_SVC; // Nu MC SVM
235  param.kernel_type = LINEAR;
236  param.degree = 3;
237  param.gamma = 0; // 1/k
238  param.coef0 = 0;
239  param.nu = get_nu(); // Nu
240  param.kernel=kernel;
241  param.cache_size = kernel->get_cache_size();
242  param.C = 0;
243  param.eps = epsilon;
244  param.p = 0.1;
245  param.shrinking = 0;
246  param.nr_weight = 2;
247  param.weight_label = weights_label;
248  param.weight = weights;
249  param.nr_class=m_num_classes;
250  param.use_bias = get_bias_enabled();
251 
252  const char* error_msg = svm_check_parameter(&problem,&param);
253 
254  if(error_msg)
255  SG_ERROR("Error: %s\n",error_msg);
256 
257  model = svm_train(&problem, &param);
258 
259  if (model)
260  {
261  ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef));
262 
263  ASSERT(model->nr_class==m_num_classes);
264  create_multiclass_svm(m_num_classes);
265 
266  rho=model->rho[0];
267 
268  SG_FREE(norm_wcw);
270 
271  for (int32_t i=0; i<m_num_classes; i++)
272  {
273  int32_t num_sv=model->nSV[i];
274 
275  CSVM* svm=new CSVM(num_sv);
276  svm->set_bias(model->rho[i+1]);
277  norm_wcw[i]=model->normwcw[i];
278 
279 
280  for (int32_t j=0; j<num_sv; j++)
281  {
282  svm->set_alpha(j, model->sv_coef[i][j]);
283  svm->set_support_vector(j, model->SV[i][j].index);
284  }
285 
286  set_svm(i, svm);
287  }
288 
289  SG_FREE(problem.x);
290  SG_FREE(problem.y);
291  SG_FREE(x_space);
292  for (int32_t i=0; i<m_num_classes; i++)
293  {
294  SG_FREE(model->SV[i]);
295  model->SV[i]=NULL;
296  }
297  svm_destroy_model(model);
298 
300  compute_norm_wc();
301 
302  model=NULL;
303  return true;
304  }
305  else
306  return false;
307 }
308 
309 void CScatterSVM::compute_norm_wc()
310 {
311  SG_FREE(norm_wc);
313  for (int32_t i=0; i<m_num_svms; i++)
314  norm_wc[i]=0;
315 
316 
317  for (int c=0; c<m_num_svms; c++)
318  {
319  CSVM* svm=m_svms[c];
320  int32_t num_sv = svm->get_num_support_vectors();
321 
322  for (int32_t i=0; i<num_sv; i++)
323  {
324  int32_t ii=svm->get_support_vector(i);
325  for (int32_t j=0; j<num_sv; j++)
326  {
327  int32_t jj=svm->get_support_vector(j);
328  norm_wc[c]+=svm->get_alpha(i)*kernel->kernel(ii,jj)*svm->get_alpha(j);
329  }
330  }
331  }
332 
333  for (int32_t i=0; i<m_num_svms; i++)
334  norm_wc[i]=CMath::sqrt(norm_wc[i]);
335 
336  CMath::display_vector(norm_wc, m_num_svms, "norm_wc");
337 }
338 
340 {
341  CLabels* output=NULL;
342  if (!kernel)
343  {
344  SG_ERROR( "SVM can not proceed without kernel!\n");
345  return false ;
346  }
347 
349  {
350  int32_t num_vectors=kernel->get_num_vec_rhs();
351 
352  output=new CLabels(num_vectors);
353  SG_REF(output);
354 
355  if (scatter_type == TEST_RULE1)
356  {
357  ASSERT(m_num_svms>0);
358  for (int32_t i=0; i<num_vectors; i++)
359  output->set_label(i, apply(i));
360  }
361 
362  else
363  {
364  ASSERT(m_num_svms>0);
365  ASSERT(num_vectors==output->get_num_labels());
366  CLabels** outputs=SG_MALLOC(CLabels*, m_num_svms);
367 
368  for (int32_t i=0; i<m_num_svms; i++)
369  {
370  //SG_PRINT("svm %d\n", i);
371  ASSERT(m_svms[i]);
372  m_svms[i]->set_kernel(kernel);
373  m_svms[i]->set_labels(labels);
374  outputs[i]=m_svms[i]->apply();
375  }
376 
377  for (int32_t i=0; i<num_vectors; i++)
378  {
379  int32_t winner=0;
380  float64_t max_out=outputs[0]->get_label(i)/norm_wc[0];
381 
382  for (int32_t j=1; j<m_num_svms; j++)
383  {
384  float64_t out=outputs[j]->get_label(i)/norm_wc[j];
385 
386  if (out>max_out)
387  {
388  winner=j;
389  max_out=out;
390  }
391  }
392 
393  output->set_label(i, winner);
394  }
395 
396  for (int32_t i=0; i<m_num_svms; i++)
397  SG_UNREF(outputs[i]);
398 
399  SG_FREE(outputs);
400  }
401  }
402 
403  return output;
404 }
405 
407 {
408  ASSERT(m_num_svms>0);
409  float64_t* outputs=SG_MALLOC(float64_t, m_num_svms);
410  int32_t winner=0;
411 
412  if (scatter_type == TEST_RULE1)
413  {
414  for (int32_t c=0; c<m_num_svms; c++)
415  outputs[c]=m_svms[c]->get_bias()-rho;
416 
417  for (int32_t c=0; c<m_num_svms; c++)
418  {
419  float64_t v=0;
420 
421  for (int32_t i=0; i<m_svms[c]->get_num_support_vectors(); i++)
422  {
423  float64_t alpha=m_svms[c]->get_alpha(i);
424  int32_t svidx=m_svms[c]->get_support_vector(i);
425  v += alpha*kernel->kernel(svidx, num);
426  }
427 
428  outputs[c] += v;
429  for (int32_t j=0; j<m_num_svms; j++)
430  outputs[j] -= v/m_num_svms;
431  }
432 
433  for (int32_t j=0; j<m_num_svms; j++)
434  outputs[j]/=norm_wcw[j];
435 
436  float64_t max_out=outputs[0];
437  for (int32_t j=0; j<m_num_svms; j++)
438  {
439  if (outputs[j]>max_out)
440  {
441  max_out=outputs[j];
442  winner=j;
443  }
444  }
445  }
446 
447  else
448  {
449  float64_t max_out=m_svms[0]->apply(num)/norm_wc[0];
450 
451  for (int32_t i=1; i<m_num_svms; i++)
452  {
453  outputs[i]=m_svms[i]->apply(num)/norm_wc[i];
454  if (outputs[i]>max_out)
455  {
456  winner=i;
457  max_out=outputs[i];
458  }
459  }
460  }
461 
462  SG_FREE(outputs);
463  return winner;
464 }

SHOGUN Machine Learning Toolbox - Documentation