SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SVRLight.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) 1999-2009 Soeren Sonnenburg
8  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
9  */
10 
11 #include <shogun/lib/config.h>
12 
13 #ifdef USE_SVMLIGHT
14 
15 #include <shogun/io/SGIO.h>
17 #include <shogun/lib/Signal.h>
23 
24 #include <unistd.h>
25 
26 #ifdef USE_CPLEX
27 extern "C" {
28 #include <ilcplex/cplex.h>
29 }
30 #endif
31 
32 #include <shogun/base/Parallel.h>
33 
34 #ifdef HAVE_PTHREAD
35 #include <pthread.h>
36 #endif
37 
38 using namespace shogun;
39 
40 #ifndef DOXYGEN_SHOULD_SKIP_THIS
41 struct S_THREAD_PARAM_SVRLIGHT
42 {
43  float64_t* lin;
44  int32_t start, end;
45  int32_t* active2dnum;
46  int32_t* docs;
47  CKernel* kernel;
48  int32_t num_vectors;
49 };
50 #endif // DOXYGEN_SHOULD_SKIP_THIS
51 
53 : CSVMLight(C, k, lab)
54 {
55  set_tube_epsilon(eps);
56 }
57 
59 : CSVMLight()
60 {
61 }
62 
65 {
66 }
67 
69 {
70  return CT_SVRLIGHT;
71 }
72 
74 {
75  //certain setup params
76  verbosity=1;
77  init_margin=0.15;
78  init_iter=500;
81 
82  strcpy (learn_parm->predfile, "");
83  learn_parm->biased_hyperplane=1;
84  learn_parm->sharedslack=0;
85  learn_parm->remove_inconsistent=0;
86  learn_parm->skip_final_opt_check=1;
87  learn_parm->svm_maxqpsize=get_qpsize();
88  learn_parm->svm_newvarsinqp=learn_parm->svm_maxqpsize-1;
89  learn_parm->maxiter=100000;
90  learn_parm->svm_iter_to_shrink=100;
91  learn_parm->svm_c=get_C1();
92  learn_parm->transduction_posratio=0.33;
93  learn_parm->svm_costratio=get_C2()/get_C1();
94  learn_parm->svm_costratio_unlab=1.0;
95  learn_parm->svm_unlabbound=1E-5;
96  learn_parm->epsilon_crit=epsilon; // GU: better decrease it ... ??
97  learn_parm->epsilon_a=1E-15;
98  learn_parm->compute_loo=0;
99  learn_parm->rho=1.0;
100  learn_parm->xa_depth=0;
101 
102  if (!kernel)
103  {
104  SG_ERROR("SVR_light can not proceed without kernel!\n")
105  return false ;
106  }
107 
108  if (!m_labels)
109  {
110  SG_ERROR("SVR_light can not proceed without labels!\n")
111  return false;
112  }
113 
114  if (data)
115  {
116  if (m_labels->get_num_labels() != data->get_num_vectors())
117  SG_ERROR("Number of training vectors does not match number of labels\n")
118  kernel->init(data, data);
119  }
120 
122  kernel->clear_normal();
123 
124  // output some info
125  SG_DEBUG("qpsize = %i\n", learn_parm->svm_maxqpsize)
126  SG_DEBUG("epsilon = %1.1e\n", learn_parm->epsilon_crit)
127  SG_DEBUG("kernel->has_property(KP_LINADD) = %i\n", kernel->has_property(KP_LINADD))
128  SG_DEBUG("kernel->has_property(KP_KERNCOMBINATION) = %i\n", kernel->has_property(KP_KERNCOMBINATION))
129  SG_DEBUG("get_linadd_enabled() = %i\n", get_linadd_enabled())
130  SG_DEBUG("kernel->get_num_subkernels() = %i\n", kernel->get_num_subkernels())
131 
134 
135  SG_DEBUG("use_kernel_cache = %i\n", use_kernel_cache)
136 
137  // train the svm
138  svr_learn();
139 
140  // brain damaged svm light work around
141  create_new_model(model->sv_num-1);
142  set_bias(-model->b);
143  for (int32_t i=0; i<model->sv_num-1; i++)
144  {
145  set_alpha(i, model->alpha[i+1]);
146  set_support_vector(i, model->supvec[i+1]);
147  }
148 
150  kernel->clear_normal() ;
151 
152  return true ;
153 }
154 
156 {
157  int32_t *inconsistent, i, j;
158  int32_t upsupvecnum;
159  float64_t maxdiff, *lin, *c, *a;
160  int32_t iterations;
161  float64_t *xi_fullset; /* buffer for storing xi on full sample in loo */
162  float64_t *a_fullset; /* buffer for storing alpha on full sample in loo */
163  TIMING timing_profile;
164  SHRINK_STATE shrink_state;
165  int32_t* label;
166  int32_t* docs;
167 
169  int32_t totdoc=m_labels->get_num_labels();
170  num_vectors=totdoc;
171 
172  // set up regression problem in standard form
173  docs=SG_MALLOC(int32_t, 2*totdoc);
174  label=SG_MALLOC(int32_t, 2*totdoc);
175  c = SG_MALLOC(float64_t, 2*totdoc);
176 
177  for(i=0;i<totdoc;i++) {
178  docs[i]=i;
179  j=2*totdoc-1-i;
180  label[i]=+1;
181  c[i]=((CRegressionLabels*) m_labels)->get_label(i);
182  docs[j]=j;
183  label[j]=-1;
184  c[j]=((CRegressionLabels*) m_labels)->get_label(i);
185  }
186  totdoc*=2;
187 
188  //prepare kernel cache for regression (i.e. cachelines are twice of current size)
190 
192  {
194 
195  for (index_t k_idx=0; k_idx<k->get_num_kernels(); k_idx++)
196  {
197  CKernel* kn = k->get_kernel(k_idx);
199  SG_UNREF(kn);
200  }
201  }
202 
203  timing_profile.time_kernel=0;
204  timing_profile.time_opti=0;
205  timing_profile.time_shrink=0;
206  timing_profile.time_update=0;
207  timing_profile.time_model=0;
208  timing_profile.time_check=0;
209  timing_profile.time_select=0;
210 
211  SG_FREE(W);
212  W=NULL;
213 
215  {
216  W = SG_MALLOC(float64_t, totdoc*kernel->get_num_subkernels());
217  for (i=0; i<totdoc*kernel->get_num_subkernels(); i++)
218  W[i]=0;
219  }
220 
221  /* make sure -n value is reasonable */
222  if((learn_parm->svm_newvarsinqp < 2)
223  || (learn_parm->svm_newvarsinqp > learn_parm->svm_maxqpsize)) {
224  learn_parm->svm_newvarsinqp=learn_parm->svm_maxqpsize;
225  }
226 
227  init_shrink_state(&shrink_state,totdoc,(int32_t)MAXSHRINK);
228 
229  inconsistent = SG_MALLOC(int32_t, totdoc);
230  a = SG_MALLOC(float64_t, totdoc);
231  a_fullset = SG_MALLOC(float64_t, totdoc);
232  xi_fullset = SG_MALLOC(float64_t, totdoc);
233  lin = SG_MALLOC(float64_t, totdoc);
234  learn_parm->svm_cost = SG_MALLOC(float64_t, totdoc);
235  if (m_linear_term.vlen>0)
237  else
238  {
239  learn_parm->eps=SG_MALLOC(float64_t, totdoc); /* equivalent regression epsilon for classification */
241  }
242 
243  SG_FREE(model->supvec);
244  SG_FREE(model->alpha);
245  SG_FREE(model->index);
246  model->supvec = SG_MALLOC(int32_t, totdoc+2);
247  model->alpha = SG_MALLOC(float64_t, totdoc+2);
248  model->index = SG_MALLOC(int32_t, totdoc+2);
249 
250  model->at_upper_bound=0;
251  model->b=0;
252  model->supvec[0]=0; /* element 0 reserved and empty for now */
253  model->alpha[0]=0;
254  model->totdoc=totdoc;
255 
256  model->kernel=kernel;
257 
258  model->sv_num=1;
259  model->loo_error=-1;
260  model->loo_recall=-1;
261  model->loo_precision=-1;
262  model->xa_error=-1;
263  model->xa_recall=-1;
264  model->xa_precision=-1;
265 
266  for(i=0;i<totdoc;i++) { /* various inits */
267  inconsistent[i]=0;
268  a[i]=0;
269  lin[i]=0;
270 
271  if(label[i] > 0) {
272  learn_parm->svm_cost[i]=learn_parm->svm_c*learn_parm->svm_costratio*
273  fabs((float64_t)label[i]);
274  }
275  else if(label[i] < 0) {
276  learn_parm->svm_cost[i]=learn_parm->svm_c*fabs((float64_t)label[i]);
277  }
278  else
279  ASSERT(false)
280  }
281 
282  if(verbosity==1) {
283  SG_DEBUG("Optimizing...\n")
284  }
285 
286  /* train the svm */
287  SG_DEBUG("num_train: %d\n", totdoc)
288  iterations=optimize_to_convergence(docs,label,totdoc,
289  &shrink_state,inconsistent,a,lin,
290  c,&timing_profile,
291  &maxdiff,(int32_t)-1,
292  (int32_t)1);
293 
294 
295  if(verbosity>=1) {
296  SG_DONE()
297  SG_INFO("(%ld iterations)\n",iterations)
298  SG_INFO("Optimization finished (maxdiff=%.8f).\n",maxdiff)
299  SG_INFO("obj = %.16f, rho = %.16f\n",get_objective(),model->b)
300 
301  upsupvecnum=0;
302 
303  SG_DEBUG("num sv: %d\n", model->sv_num)
304  for(i=1;i<model->sv_num;i++)
305  {
306  if(fabs(model->alpha[i]) >=
307  (learn_parm->svm_cost[model->supvec[i]]-
308  learn_parm->epsilon_a))
309  upsupvecnum++;
310  }
311  SG_INFO("Number of SV: %d (including %d at upper bound)\n",
312  model->sv_num-1,upsupvecnum);
313  }
314 
315  /* this makes sure the model we return does not contain pointers to the
316  temporary documents */
317  for(i=1;i<model->sv_num;i++) {
318  j=model->supvec[i];
319  if(j >= (totdoc/2)) {
320  j=totdoc-j-1;
321  }
322  model->supvec[i]=j;
323  }
324 
325  shrink_state_cleanup(&shrink_state);
326  SG_FREE(label);
327  SG_FREE(inconsistent);
328  SG_FREE(c);
329  SG_FREE(a);
330  SG_FREE(a_fullset);
331  SG_FREE(xi_fullset);
332  SG_FREE(lin);
333  SG_FREE(learn_parm->svm_cost);
334  SG_FREE(docs);
335 }
336 
338  float64_t *a, float64_t *lin, float64_t *c, float64_t* eps, int32_t *label,
339  int32_t totdoc)
340 {
341  /* calculate value of objective function */
342  float64_t criterion=0;
343 
344  for(int32_t i=0;i<totdoc;i++)
345  criterion+=(eps[i]-(float64_t)label[i]*c[i])*a[i]+0.5*a[i]*label[i]*lin[i];
346 
347  /* float64_t check=0;
348  for(int32_t i=0;i<totdoc;i++)
349  {
350  check+=a[i]*eps-a[i]*label[i]*c[i];
351  for(int32_t j=0;j<totdoc;j++)
352  check+= 0.5*a[i]*label[i]*a[j]*label[j]*compute_kernel(i,j);
353 
354  }
355 
356  SG_INFO("REGRESSION OBJECTIVE %f vs. CHECK %f (diff %f)\n", criterion, check, criterion-check) */
357 
358  return(criterion);
359 }
360 
362 {
363  S_THREAD_PARAM_SVRLIGHT * params = (S_THREAD_PARAM_SVRLIGHT*) params_ ;
364 
365  int32_t jj=0, j=0 ;
366 
367  for(jj=params->start;(jj<params->end) && (j=params->active2dnum[jj])>=0;jj++)
368  params->lin[j]+=params->kernel->compute_optimized(CSVRLight::regression_fix_index2(params->docs[j], params->num_vectors));
369 
370  return NULL ;
371 }
372 
374 {
375  if (i>=num_vectors)
376  i=2*num_vectors-1-i;
377 
378  return i;
379 }
380 
382  int32_t i, int32_t num_vectors)
383 {
384  if (i>=num_vectors)
385  i=2*num_vectors-1-i;
386 
387  return i;
388 }
389 
391 {
394  return kernel->kernel(i, j);
395 }
396 
398  int32_t* docs, int32_t* label, int32_t *active2dnum, float64_t *a,
399  float64_t *a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
400  float64_t *aicache, float64_t* c)
401  /* keep track of the linear component */
402  /* lin of the gradient etc. by updating */
403  /* based on the change of the variables */
404  /* in the current working set */
405 {
406  register int32_t i=0,ii=0,j=0,jj=0;
407 
409  {
410  if (callback)
411  {
412  update_linear_component_mkl_linadd(docs, label, active2dnum, a, a_old, working2dnum,
413  totdoc, lin, aicache, c) ;
414  }
415  else
416  {
417  kernel->clear_normal();
418 
419  int32_t num_working=0;
420  for(ii=0;(i=working2dnum[ii])>=0;ii++) {
421  if(a[i] != a_old[i]) {
422  kernel->add_to_normal(regression_fix_index(docs[i]), (a[i]-a_old[i])*(float64_t)label[i]);
423  num_working++;
424  }
425  }
426 
427  if (num_working>0)
428  {
429  if (parallel->get_num_threads() < 2)
430  {
431  for(jj=0;(j=active2dnum[jj])>=0;jj++) {
432  lin[j]+=kernel->compute_optimized(regression_fix_index(docs[j]));
433  }
434  }
435 #ifdef HAVE_PTHREAD
436  else
437  {
438  int32_t num_elem = 0 ;
439  for(jj=0;(j=active2dnum[jj])>=0;jj++) num_elem++ ;
440 
441  pthread_t* threads = SG_MALLOC(pthread_t, parallel->get_num_threads()-1);
442  S_THREAD_PARAM_SVRLIGHT* params = SG_MALLOC(S_THREAD_PARAM_SVRLIGHT, parallel->get_num_threads()-1);
443  int32_t start = 0 ;
444  int32_t step = num_elem/parallel->get_num_threads() ;
445  int32_t end = step ;
446 
447  for (int32_t t=0; t<parallel->get_num_threads()-1; t++)
448  {
449  params[t].kernel = kernel ;
450  params[t].lin = lin ;
451  params[t].docs = docs ;
452  params[t].active2dnum=active2dnum ;
453  params[t].start = start ;
454  params[t].end = end ;
455  params[t].num_vectors=num_vectors ;
456 
457  start=end ;
458  end+=step ;
459  pthread_create(&threads[t], NULL, update_linear_component_linadd_helper, (void*)&params[t]) ;
460  }
461 
462  for(jj=params[parallel->get_num_threads()-2].end;(j=active2dnum[jj])>=0;jj++) {
463  lin[j]+=kernel->compute_optimized(regression_fix_index(docs[j]));
464  }
465  void* ret;
466  for (int32_t t=0; t<parallel->get_num_threads()-1; t++)
467  pthread_join(threads[t], &ret) ;
468 
469  SG_FREE(params);
470  SG_FREE(threads);
471  }
472 #endif
473  }
474  }
475  }
476  else
477  {
478  if (callback)
479  {
480  update_linear_component_mkl(docs, label, active2dnum,
481  a, a_old, working2dnum, totdoc, lin, aicache, c) ;
482  }
483  else {
484  for(jj=0;(i=working2dnum[jj])>=0;jj++) {
485  if(a[i] != a_old[i]) {
486  kernel->get_kernel_row(i,active2dnum,aicache);
487  for(ii=0;(j=active2dnum[ii])>=0;ii++)
488  lin[j]+=(a[i]-a_old[i])*aicache[j]*(float64_t)label[i];
489  }
490  }
491  }
492  }
493 }
494 
496  int32_t* docs, int32_t* label, int32_t *active2dnum, float64_t *a,
497  float64_t *a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
498  float64_t *aicache, float64_t* c)
499 {
500  int32_t num = totdoc;
501  int32_t num_weights = -1;
502  int32_t num_kernels = kernel->get_num_subkernels() ;
503  const float64_t* old_beta = kernel->get_subkernel_weights(num_weights);
504 
505  ASSERT(num_weights==num_kernels)
506 
507  if ((kernel->get_kernel_type()==K_COMBINED) &&
508  (!((CCombinedKernel*)kernel)->get_append_subkernel_weights()))// for combined kernel
509  {
511 
512  int32_t n = 0, i, j ;
513 
514  for (index_t k_idx=0; k_idx<k->get_num_kernels(); k_idx++)
515  {
516  CKernel* kn = k->get_kernel(k_idx);
517  for(i=0;i<num;i++)
518  {
519  if(a[i] != a_old[i])
520  {
521  kn->get_kernel_row(i,NULL,aicache, true);
522  for(j=0;j<num;j++)
523  W[j*num_kernels+n]+=(a[i]-a_old[i])*aicache[regression_fix_index(j)]*(float64_t)label[i];
524  }
525  }
526  SG_UNREF(kn);
527  n++ ;
528  }
529  }
530  else // hope the kernel is fast ...
531  {
532  float64_t* w_backup = SG_MALLOC(float64_t, num_kernels);
533  float64_t* w1 = SG_MALLOC(float64_t, num_kernels);
534 
535  // backup and set to zero
536  for (int32_t i=0; i<num_kernels; i++)
537  {
538  w_backup[i] = old_beta[i] ;
539  w1[i]=0.0 ;
540  }
541  for (int32_t n=0; n<num_kernels; n++)
542  {
543  w1[n]=1.0 ;
545 
546  for(int32_t i=0;i<num;i++)
547  {
548  if(a[i] != a_old[i])
549  {
550  for(int32_t j=0;j<num;j++)
551  W[j*num_kernels+n]+=(a[i]-a_old[i])*compute_kernel(i,j)*(float64_t)label[i];
552  }
553  }
554  w1[n]=0.0 ;
555  }
556 
557  // restore old weights
558  kernel->set_subkernel_weights(SGVector<float64_t>(w_backup,num_weights));
559 
560  SG_FREE(w_backup);
561  SG_FREE(w1);
562  }
563 
564  call_mkl_callback(a, label, lin, c, totdoc);
565 }
566 
567 
569  int32_t* docs, int32_t* label, int32_t *active2dnum, float64_t *a,
570  float64_t *a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
571  float64_t *aicache, float64_t* c)
572 {
573  // kernel with LP_LINADD property is assumed to have
574  // compute_by_subkernel functions
575  int32_t num_weights = -1;
576  int32_t num_kernels = kernel->get_num_subkernels() ;
577  const float64_t* old_beta = kernel->get_subkernel_weights(num_weights);
578 
579  ASSERT(num_weights==num_kernels)
580 
581  float64_t* w_backup=SG_MALLOC(float64_t, num_kernels);
582  float64_t* w1=SG_MALLOC(float64_t, num_kernels);
583 
584  // backup and set to one
585  for (int32_t i=0; i<num_kernels; i++)
586  {
587  w_backup[i] = old_beta[i] ;
588  w1[i]=1.0 ;
589  }
590  // set the kernel weights
592 
593  // create normal update (with changed alphas only)
594  kernel->clear_normal();
595  for(int32_t ii=0, i=0;(i=working2dnum[ii])>=0;ii++) {
596  if(a[i] != a_old[i]) {
597  kernel->add_to_normal(regression_fix_index(docs[i]), (a[i]-a_old[i])*(float64_t)label[i]);
598  }
599  }
600 
601  // determine contributions of different kernels
602  for (int32_t i=0; i<num_vectors; i++)
603  kernel->compute_by_subkernel(i,&W[i*num_kernels]) ;
604 
605  // restore old weights
606  kernel->set_subkernel_weights(SGVector<float64_t>(w_backup,num_weights));
607 
608  call_mkl_callback(a, label, lin, c, totdoc);
609 }
610 
611 void CSVRLight::call_mkl_callback(float64_t* a, int32_t* label, float64_t* lin, float64_t* c, int32_t totdoc)
612 {
613  int32_t num = totdoc;
614  int32_t num_kernels = kernel->get_num_subkernels() ;
615  float64_t sumalpha = 0;
616  float64_t* sumw=SG_MALLOC(float64_t, num_kernels);
617 
618  for (int32_t i=0; i<num; i++)
619  sumalpha-=a[i]*(learn_parm->eps[i]-label[i]*c[i]);
620 
621 #ifdef HAVE_LAPACK
622  int nk = (int) num_kernels; // calling external lib
623  double* alphay = SG_MALLOC(double, num);
624  for (int32_t i=0; i<num; i++)
625  alphay[i]=a[i]*label[i];
626 
627  for (int32_t i=0; i<num_kernels; i++)
628  sumw[i]=0;
629 
630  cblas_dgemv(CblasColMajor, CblasNoTrans, nk, (int) num, 0.5, (double*) W,
631  nk, (double*) alphay, 1, 1.0, (double*) sumw, 1);
632 
633  SG_FREE(alphay);
634 #else
635  for (int32_t d=0; d<num_kernels; d++)
636  {
637  sumw[d]=0;
638  for(int32_t i=0; i<num; i++)
639  sumw[d] += 0.5*a[i]*label[i]*W[i*num_kernels+d];
640  }
641 #endif
642 
643  if (callback)
644  mkl_converged=callback(mkl, sumw, sumalpha);
645 
646  const float64_t* new_beta = kernel->get_subkernel_weights(num_kernels);
647 
648  // update lin
649 #ifdef HAVE_LAPACK
650  cblas_dgemv(CblasColMajor, CblasTrans, nk, (int) num, 1.0, (double*) W,
651  nk, (double*) new_beta, 1, 0.0, (double*) lin, 1);
652 #else
653  for(int32_t i=0; i<num; i++)
654  lin[i]=0 ;
655  for (int32_t d=0; d<num_kernels; d++)
656  if (new_beta[d]!=0)
657  for(int32_t i=0; i<num; i++)
658  lin[i] += new_beta[d]*W[i*num_kernels+d] ;
659 #endif
660 
661 
662  SG_FREE(sumw);
663 }
664 
665 
667  int32_t* label, float64_t *a, SHRINK_STATE *shrink_state, float64_t *lin,
668  float64_t *c, int32_t totdoc, int32_t iteration, int32_t *inconsistent,
669  int32_t* docs, float64_t *aicache, float64_t *maxdiff)
670  /* Make all variables active again which had been removed by
671  shrinking. */
672  /* Computes lin for those variables from scratch. */
673 {
674  register int32_t i=0,j,ii=0,jj,t,*changed2dnum,*inactive2dnum;
675  int32_t *changed,*inactive;
676  register float64_t *a_old,dist;
677  float64_t ex_c,target;
678 
679  if (kernel->has_property(KP_LINADD) && get_linadd_enabled()) { /* special linear case */
680  a_old=shrink_state->last_a;
681 
682  kernel->clear_normal();
683  int32_t num_modified=0;
684  for(i=0;i<totdoc;i++) {
685  if(a[i] != a_old[i]) {
686  kernel->add_to_normal(regression_fix_index(docs[i]), ((a[i]-a_old[i])*(float64_t)label[i]));
687  a_old[i]=a[i];
688  num_modified++;
689  }
690  }
691 
692  if (num_modified>0)
693  {
694  for(i=0;i<totdoc;i++) {
695  if(!shrink_state->active[i]) {
696  lin[i]=shrink_state->last_lin[i]+kernel->compute_optimized(regression_fix_index(docs[i]));
697  }
698  shrink_state->last_lin[i]=lin[i];
699  }
700  }
701  }
702  else
703  {
704  changed=SG_MALLOC(int32_t, totdoc);
705  changed2dnum=SG_MALLOC(int32_t, totdoc+11);
706  inactive=SG_MALLOC(int32_t, totdoc);
707  inactive2dnum=SG_MALLOC(int32_t, totdoc+11);
708  for(t=shrink_state->deactnum-1;(t>=0) && shrink_state->a_history[t];t--) {
709  if(verbosity>=2) {
710  SG_INFO("%ld..",t)
711  }
712  a_old=shrink_state->a_history[t];
713  for(i=0;i<totdoc;i++) {
714  inactive[i]=((!shrink_state->active[i])
715  && (shrink_state->inactive_since[i] == t));
716  changed[i]= (a[i] != a_old[i]);
717  }
718  compute_index(inactive,totdoc,inactive2dnum);
719  compute_index(changed,totdoc,changed2dnum);
720 
721  for(ii=0;(i=changed2dnum[ii])>=0;ii++) {
722  CKernelMachine::kernel->get_kernel_row(i,inactive2dnum,aicache);
723  for(jj=0;(j=inactive2dnum[jj])>=0;jj++)
724  lin[j]+=(a[i]-a_old[i])*aicache[j]*(float64_t)label[i];
725  }
726  }
727  SG_FREE(changed);
728  SG_FREE(changed2dnum);
729  SG_FREE(inactive);
730  SG_FREE(inactive2dnum);
731  }
732 
733  (*maxdiff)=0;
734  for(i=0;i<totdoc;i++) {
735  shrink_state->inactive_since[i]=shrink_state->deactnum-1;
736  if(!inconsistent[i]) {
737  dist=(lin[i]-model->b)*(float64_t)label[i];
738  target=-(learn_parm->eps[i]-(float64_t)label[i]*c[i]);
739  ex_c=learn_parm->svm_cost[i]-learn_parm->epsilon_a;
740  if((a[i]>learn_parm->epsilon_a) && (dist > target)) {
741  if((dist-target)>(*maxdiff)) /* largest violation */
742  (*maxdiff)=dist-target;
743  }
744  else if((a[i]<ex_c) && (dist < target)) {
745  if((target-dist)>(*maxdiff)) /* largest violation */
746  (*maxdiff)=target-dist;
747  }
748  if((a[i]>(0+learn_parm->epsilon_a))
749  && (a[i]<ex_c)) {
750  shrink_state->active[i]=1; /* not at bound */
751  }
752  else if((a[i]<=(0+learn_parm->epsilon_a)) && (dist < (target+learn_parm->epsilon_shrink))) {
753  shrink_state->active[i]=1;
754  }
755  else if((a[i]>=ex_c)
756  && (dist > (target-learn_parm->epsilon_shrink))) {
757  shrink_state->active[i]=1;
758  }
759  else if(learn_parm->sharedslack) { /* make all active when sharedslack */
760  shrink_state->active[i]=1;
761  }
762  }
763  }
764  if (use_kernel_cache) { /* update history for non-linear */
765  for(i=0;i<totdoc;i++) {
766  (shrink_state->a_history[shrink_state->deactnum-1])[i]=a[i];
767  }
768  for(t=shrink_state->deactnum-2;(t>=0) && shrink_state->a_history[t];t--) {
769  SG_FREE(shrink_state->a_history[t]);
770  shrink_state->a_history[t]=0;
771  }
772  }
773 }
774 #endif //USE_SVMLIGHT

SHOGUN Machine Learning Toolbox - Documentation