SHOGUN  v2.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CombinedKernel.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  * Written (W) 1999-2008 Gunnar Raetsch
9  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
10  */
11 
12 #include <shogun/lib/common.h>
13 #include <shogun/io/SGIO.h>
14 #include <shogun/lib/Signal.h>
15 #include <shogun/base/Parallel.h>
16 
17 #include <shogun/kernel/Kernel.h>
21 #include <string.h>
22 
23 #ifndef WIN32
24 #include <pthread.h>
25 #endif
26 
27 using namespace shogun;
28 
29 #ifndef DOXYGEN_SHOULD_SKIP_THIS
30 struct S_THREAD_PARAM
31 {
32  CKernel* kernel;
33  float64_t* result;
34  int32_t* vec_idx;
35  int32_t start;
36  int32_t end;
38  float64_t* weights;
39  int32_t* IDX;
40  int32_t num_suppvec;
41 };
42 #endif // DOXYGEN_SHOULD_SKIP_THIS
43 
44 CCombinedKernel::CCombinedKernel(int32_t size, bool asw)
45 : CKernel(size), append_subkernel_weights(asw)
46 {
47  init();
48 
50  SG_INFO( "(subkernel weights are appended)\n") ;
51 
52  SG_INFO("Combined kernel created (%p)\n", this) ;
53 }
54 
56 {
59 
60  cleanup();
62 
63  SG_INFO("Combined kernel deleted (%p).\n", this);
64 }
65 
66 bool CCombinedKernel::init(CFeatures* l, CFeatures* r)
67 {
68  CKernel::init(l,r);
73 
74  CFeatures* lf=NULL;
75  CFeatures* rf=NULL;
76  CKernel* k=NULL;
77 
78  bool result=true;
79 
80  CListElement* lfc = NULL;
81  CListElement* rfc = NULL;
82  lf=((CCombinedFeatures*) l)->get_first_feature_obj(lfc);
83  rf=((CCombinedFeatures*) r)->get_first_feature_obj(rfc);
84  CListElement* current = NULL;
85  k=get_first_kernel(current);
86 
87  while ( result && k )
88  {
89  // skip over features - the custom kernel does not need any
90  if (k->get_kernel_type() != K_CUSTOM)
91  {
92  if (!lf || !rf)
93  {
94  SG_UNREF(lf);
95  SG_UNREF(rf);
96  SG_UNREF(k);
97  SG_ERROR( "CombinedKernel: Number of features/kernels does not match - bailing out\n");
98  }
99 
100  SG_DEBUG( "Initializing 0x%p - \"%s\"\n", this, k->get_name());
101  result=k->init(lf,rf);
102  SG_UNREF(lf);
103  SG_UNREF(rf);
104 
105  lf=((CCombinedFeatures*) l)->get_next_feature_obj(lfc) ;
106  rf=((CCombinedFeatures*) r)->get_next_feature_obj(rfc) ;
107  }
108  else
109  {
110  SG_DEBUG( "Initializing 0x%p - \"%s\" (skipping init, this is a CUSTOM kernel)\n", this, k->get_name());
111  if (!k->has_features())
112  SG_ERROR("No kernel matrix was assigned to this Custom kernel\n");
113  if (k->get_num_vec_lhs() != num_lhs)
114  SG_ERROR("Number of lhs-feature vectors (%d) not match with number of rows (%d) of custom kernel\n", num_lhs, k->get_num_vec_lhs());
115  if (k->get_num_vec_rhs() != num_rhs)
116  SG_ERROR("Number of rhs-feature vectors (%d) not match with number of cols (%d) of custom kernel\n", num_rhs, k->get_num_vec_rhs());
117  }
118 
119  SG_UNREF(k);
120  k=get_next_kernel(current) ;
121  }
122 
123  if (!result)
124  {
125  SG_INFO( "CombinedKernel: Initialising the following kernel failed\n");
126  if (k)
127  k->list_kernel();
128  else
129  SG_INFO( "<NULL>\n");
130  return false;
131  }
132 
133  if ((lf!=NULL) || (rf!=NULL) || (k!=NULL))
134  {
135  SG_UNREF(lf);
136  SG_UNREF(rf);
137  SG_UNREF(k);
138  SG_ERROR( "CombinedKernel: Number of features/kernels does not match - bailing out\n");
139  }
140 
141  init_normalizer();
142  initialized=true;
143  return true;
144 }
145 
147 {
149 
150  CListElement* current = NULL ;
151  CKernel* k=get_first_kernel(current);
152 
153  while (k)
154  {
155  if (k->get_kernel_type() != K_CUSTOM)
156  k->remove_lhs();
157 
158  SG_UNREF(k);
159  k=get_next_kernel(current);
160  }
162 
163  num_lhs=0;
164 }
165 
167 {
168  CListElement* current = NULL ;
169  CKernel* k=get_first_kernel(current);
170 
171  while (k)
172  {
173  if (k->get_kernel_type() != K_CUSTOM)
174  k->remove_rhs();
175  SG_UNREF(k);
176  k=get_next_kernel(current);
177  }
179 
180  num_rhs=0;
181 }
182 
184 {
186 
187  CListElement* current = NULL ;
188  CKernel* k=get_first_kernel(current);
189 
190  while (k)
191  {
192  if (k->get_kernel_type() != K_CUSTOM)
193  k->remove_lhs_and_rhs();
194  SG_UNREF(k);
195  k=get_next_kernel(current);
196  }
197 
199 
200  num_lhs=0;
201  num_rhs=0;
202 }
203 
205 {
206  CListElement* current = NULL ;
207  CKernel* k=get_first_kernel(current);
208 
209  while (k)
210  {
211  k->cleanup();
212  SG_UNREF(k);
213  k=get_next_kernel(current);
214  }
215 
217 
219 
220  num_lhs=0;
221  num_rhs=0;
222 }
223 
225 {
226  CKernel* k;
227 
228  SG_INFO( "BEGIN COMBINED KERNEL LIST - ");
229  this->list_kernel();
230 
231  CListElement* current = NULL ;
232  k=get_first_kernel(current);
233  while (k)
234  {
235  k->list_kernel();
236  SG_UNREF(k);
237  k=get_next_kernel(current);
238  }
239  SG_INFO( "END COMBINED KERNEL LIST - ");
240 }
241 
242 float64_t CCombinedKernel::compute(int32_t x, int32_t y)
243 {
244  float64_t result=0;
245  CListElement* current = NULL ;
246  CKernel* k=get_first_kernel(current);
247  while (k)
248  {
249  if (k->get_combined_kernel_weight()!=0)
250  result += k->get_combined_kernel_weight() * k->kernel(x,y);
251  SG_UNREF(k);
252  k=get_next_kernel(current);
253  }
254 
255  return result;
256 }
257 
259  int32_t count, int32_t *IDX, float64_t *weights)
260 {
261  SG_DEBUG( "initializing CCombinedKernel optimization\n");
262 
264 
265  CListElement* current=NULL;
266  CKernel *k=get_first_kernel(current);
267  bool have_non_optimizable=false;
268 
269  while(k)
270  {
271  bool ret=true;
272 
273  if (k && k->has_property(KP_LINADD))
274  ret=k->init_optimization(count, IDX, weights);
275  else
276  {
277  SG_WARNING("non-optimizable kernel 0x%X in kernel-list\n", k);
278  have_non_optimizable=true;
279  }
280 
281  if (!ret)
282  {
283  have_non_optimizable=true;
284  SG_WARNING("init_optimization of kernel 0x%X failed\n", k);
285  }
286 
287  SG_UNREF(k);
288  k=get_next_kernel(current);
289  }
290 
291  if (have_non_optimizable)
292  {
293  SG_WARNING( "some kernels in the kernel-list are not optimized\n");
294 
295  sv_idx=SG_MALLOC(int32_t, count);
296  sv_weight=SG_MALLOC(float64_t, count);
297  sv_count=count;
298  for (int32_t i=0; i<count; i++)
299  {
300  sv_idx[i]=IDX[i];
301  sv_weight[i]=weights[i];
302  }
303  }
304  set_is_initialized(true);
305 
306  return true;
307 }
308 
310 {
311  CListElement* current = NULL ;
312  CKernel* k = get_first_kernel(current);
313 
314  while(k)
315  {
316  if (k->has_property(KP_LINADD))
317  k->delete_optimization();
318 
319  SG_UNREF(k);
320  k = get_next_kernel(current);
321  }
322 
323  SG_FREE(sv_idx);
324  sv_idx = NULL;
325 
327  sv_weight = NULL;
328 
329  sv_count = 0;
330  set_is_initialized(false);
331 
332  return true;
333 }
334 
336  int32_t num_vec, int32_t* vec_idx, float64_t* result, int32_t num_suppvec,
337  int32_t* IDX, float64_t* weights, float64_t factor)
338 {
339  ASSERT(num_vec<=get_num_vec_rhs())
340  ASSERT(num_vec>0);
341  ASSERT(vec_idx);
342  ASSERT(result);
343 
344  //we have to do the optimization business ourselves but lets
345  //make sure we start cleanly
347 
348  CListElement* current = NULL ;
349  CKernel * k = get_first_kernel(current) ;
350 
351  while(k)
352  {
353  if (k && k->has_property(KP_BATCHEVALUATION))
354  {
355  if (k->get_combined_kernel_weight()!=0)
356  k->compute_batch(num_vec, vec_idx, result, num_suppvec, IDX, weights, k->get_combined_kernel_weight());
357  }
358  else
359  emulate_compute_batch(k, num_vec, vec_idx, result, num_suppvec, IDX, weights);
360 
361  SG_UNREF(k);
362  k = get_next_kernel(current);
363  }
364 
365  //clean up
367 }
368 
370 {
371  S_THREAD_PARAM* params= (S_THREAD_PARAM*) p;
372  int32_t* vec_idx=params->vec_idx;
373  CKernel* k=params->kernel;
374  float64_t* result=params->result;
375 
376  for (int32_t i=params->start; i<params->end; i++)
377  result[i] += k->get_combined_kernel_weight()*k->compute_optimized(vec_idx[i]);
378 
379  return NULL;
380 }
381 
383 {
384  S_THREAD_PARAM* params= (S_THREAD_PARAM*) p;
385  int32_t* vec_idx=params->vec_idx;
386  CKernel* k=params->kernel;
387  float64_t* result=params->result;
388  float64_t* weights=params->weights;
389  int32_t* IDX=params->IDX;
390  int32_t num_suppvec=params->num_suppvec;
391 
392  for (int32_t i=params->start; i<params->end; i++)
393  {
394  float64_t sub_result=0;
395  for (int32_t j=0; j<num_suppvec; j++)
396  sub_result += weights[j] * k->kernel(IDX[j], vec_idx[i]);
397 
398  result[i] += k->get_combined_kernel_weight()*sub_result;
399  }
400 
401  return NULL;
402 }
403 
405  CKernel* k, int32_t num_vec, int32_t* vec_idx, float64_t* result,
406  int32_t num_suppvec, int32_t* IDX, float64_t* weights)
407 {
408  ASSERT(k);
409  ASSERT(result);
410 
411  if (k->has_property(KP_LINADD))
412  {
413  if (k->get_combined_kernel_weight()!=0)
414  {
415  k->init_optimization(num_suppvec, IDX, weights);
416 
417  int32_t num_threads=parallel->get_num_threads();
418  ASSERT(num_threads>0);
419 
420  if (num_threads < 2)
421  {
422  S_THREAD_PARAM params;
423  params.kernel=k;
424  params.result=result;
425  params.start=0;
426  params.end=num_vec;
427  params.vec_idx = vec_idx;
428  compute_optimized_kernel_helper((void*) &params);
429  }
430 #ifdef HAVE_PTHREAD
431  else
432  {
433  pthread_t* threads = SG_MALLOC(pthread_t, num_threads-1);
434  S_THREAD_PARAM* params = SG_MALLOC(S_THREAD_PARAM, num_threads);
435  int32_t step= num_vec/num_threads;
436 
437  int32_t t;
438 
439  for (t=0; t<num_threads-1; t++)
440  {
441  params[t].kernel = k;
442  params[t].result = result;
443  params[t].start = t*step;
444  params[t].end = (t+1)*step;
445  params[t].vec_idx = vec_idx;
446  pthread_create(&threads[t], NULL, CCombinedKernel::compute_optimized_kernel_helper, (void*)&params[t]);
447  }
448 
449  params[t].kernel = k;
450  params[t].result = result;
451  params[t].start = t*step;
452  params[t].end = num_vec;
453  params[t].vec_idx = vec_idx;
454  compute_optimized_kernel_helper((void*) &params[t]);
455 
456  for (t=0; t<num_threads-1; t++)
457  pthread_join(threads[t], NULL);
458 
459  SG_FREE(params);
460  SG_FREE(threads);
461  }
462 #endif /* HAVE_PTHREAD */
463 
464  k->delete_optimization();
465  }
466  }
467  else
468  {
469  ASSERT(IDX!=NULL || num_suppvec==0);
470  ASSERT(weights!=NULL || num_suppvec==0);
471 
472  if (k->get_combined_kernel_weight()!=0)
473  { // compute the usual way for any non-optimized kernel
474  int32_t num_threads=parallel->get_num_threads();
475  ASSERT(num_threads>0);
476 
477  if (num_threads < 2)
478  {
479  S_THREAD_PARAM params;
480  params.kernel=k;
481  params.result=result;
482  params.start=0;
483  params.end=num_vec;
484  params.vec_idx = vec_idx;
485  params.IDX = IDX;
486  params.weights = weights;
487  params.num_suppvec = num_suppvec;
488  compute_kernel_helper((void*) &params);
489  }
490 #ifdef HAVE_PTHREAD
491  else
492  {
493  pthread_t* threads = SG_MALLOC(pthread_t, num_threads-1);
494  S_THREAD_PARAM* params = SG_MALLOC(S_THREAD_PARAM, num_threads);
495  int32_t step= num_vec/num_threads;
496 
497  int32_t t;
498 
499  for (t=0; t<num_threads-1; t++)
500  {
501  params[t].kernel = k;
502  params[t].result = result;
503  params[t].start = t*step;
504  params[t].end = (t+1)*step;
505  params[t].vec_idx = vec_idx;
506  params[t].IDX = IDX;
507  params[t].weights = weights;
508  params[t].num_suppvec = num_suppvec;
509  pthread_create(&threads[t], NULL, CCombinedKernel::compute_kernel_helper, (void*)&params[t]);
510  }
511 
512  params[t].kernel = k;
513  params[t].result = result;
514  params[t].start = t*step;
515  params[t].end = num_vec;
516  params[t].vec_idx = vec_idx;
517  params[t].IDX = IDX;
518  params[t].weights = weights;
519  params[t].num_suppvec = num_suppvec;
520  compute_kernel_helper(&params[t]);
521 
522  for (t=0; t<num_threads-1; t++)
523  pthread_join(threads[t], NULL);
524 
525  SG_FREE(params);
526  SG_FREE(threads);
527  }
528 #endif /* HAVE_PTHREAD */
529  }
530  }
531 }
532 
534 {
535  if (!get_is_initialized())
536  {
537  SG_ERROR("CCombinedKernel optimization not initialized\n");
538  return 0;
539  }
540 
541  float64_t result=0;
542 
543  CListElement* current=NULL;
544  CKernel *k=get_first_kernel(current);
545  while (k)
546  {
547  if (k->has_property(KP_LINADD) &&
548  k->get_is_initialized())
549  {
550  if (k->get_combined_kernel_weight()!=0)
551  {
552  result +=
554  }
555  }
556  else
557  {
558  ASSERT(sv_idx!=NULL || sv_count==0);
559  ASSERT(sv_weight!=NULL || sv_count==0);
560 
561  if (k->get_combined_kernel_weight()!=0)
562  { // compute the usual way for any non-optimized kernel
563  float64_t sub_result=0;
564  for (int32_t j=0; j<sv_count; j++)
565  sub_result += sv_weight[j] * k->kernel(sv_idx[j], idx);
566 
567  result += k->get_combined_kernel_weight()*sub_result;
568  }
569  }
570 
571  SG_UNREF(k);
572  k=get_next_kernel(current);
573  }
574 
575  return result;
576 }
577 
578 void CCombinedKernel::add_to_normal(int32_t idx, float64_t weight)
579 {
580  CListElement* current = NULL ;
581  CKernel* k = get_first_kernel(current);
582 
583  while(k)
584  {
585  k->add_to_normal(idx, weight);
586  SG_UNREF(k);
587  k = get_next_kernel(current);
588  }
589  set_is_initialized(true) ;
590 }
591 
593 {
594  CListElement* current = NULL ;
595  CKernel* k = get_first_kernel(current);
596 
597  while(k)
598  {
599  k->clear_normal() ;
600  SG_UNREF(k);
601  k = get_next_kernel(current);
602  }
603  set_is_initialized(true) ;
604 }
605 
607  int32_t idx, float64_t * subkernel_contrib)
608 {
610  {
611  int32_t i=0 ;
612  CListElement* current = NULL ;
613  CKernel* k = get_first_kernel(current);
614  while(k)
615  {
616  int32_t num = -1 ;
617  k->get_subkernel_weights(num);
618  if (num>1)
619  k->compute_by_subkernel(idx, &subkernel_contrib[i]) ;
620  else
621  subkernel_contrib[i] += k->get_combined_kernel_weight() * k->compute_optimized(idx) ;
622 
623  SG_UNREF(k);
624  k = get_next_kernel(current);
625  i += num ;
626  }
627  }
628  else
629  {
630  int32_t i=0 ;
631  CListElement* current = NULL ;
632  CKernel* k = get_first_kernel(current);
633  while(k)
634  {
635  if (k->get_combined_kernel_weight()!=0)
636  subkernel_contrib[i] += k->get_combined_kernel_weight() * k->compute_optimized(idx) ;
637 
638  SG_UNREF(k);
639  k = get_next_kernel(current);
640  i++ ;
641  }
642  }
643 }
644 
646 {
647  SG_DEBUG("entering CCombinedKernel::get_subkernel_weights()\n");
648 
649  num_weights = get_num_subkernels() ;
652 
654  {
655  SG_DEBUG("appending kernel weights\n");
656 
657  int32_t i=0 ;
658  CListElement* current = NULL ;
659  CKernel* k = get_first_kernel(current);
660  while(k)
661  {
662  int32_t num = -1 ;
663  const float64_t *w = k->get_subkernel_weights(num);
664  ASSERT(num==k->get_num_subkernels());
665  for (int32_t j=0; j<num; j++)
666  subkernel_weights_buffer[i+j]=w[j] ;
667 
668  SG_UNREF(k);
669  k = get_next_kernel(current);
670  i += num ;
671  }
672  }
673  else
674  {
675  SG_DEBUG("not appending kernel weights\n");
676  int32_t i=0 ;
677  CListElement* current = NULL ;
678  CKernel* k = get_first_kernel(current);
679  while(k)
680  {
682 
683  SG_UNREF(k);
684  k = get_next_kernel(current);
685  i++ ;
686  }
687  }
688 
689  SG_DEBUG("leaving CCombinedKernel::get_subkernel_weights()\n");
690  return subkernel_weights_buffer ;
691 }
692 
694 {
695  int32_t num=0;
696  const float64_t* w=get_subkernel_weights(num);
697 
698  float64_t* weights = SG_MALLOC(float64_t, num);
699  for (int32_t i=0; i<num; i++)
700  weights[i] = w[i];
701 
702  return SGVector<float64_t>(weights, num);
703 }
704 
706 {
708  {
709  int32_t i=0 ;
710  CListElement* current = NULL ;
711  CKernel* k = get_first_kernel(current);
712  while(k)
713  {
714  int32_t num = k->get_num_subkernels() ;
715  ASSERT(i<weights.vlen);
716  k->set_subkernel_weights(SGVector<float64_t>(&weights.vector[i],num, false));
717 
718  SG_UNREF(k);
719  k = get_next_kernel(current);
720  i += num ;
721  }
722  }
723  else
724  {
725  int32_t i=0 ;
726  CListElement* current = NULL ;
727  CKernel* k = get_first_kernel(current);
728  while(k)
729  {
730  ASSERT(i<weights.vlen);
731  k->set_combined_kernel_weight(weights.vector[i]);
732 
733  SG_UNREF(k);
734  k = get_next_kernel(current);
735  i++ ;
736  }
737  }
738 }
739 
741 {
742  CKernel* k = get_first_kernel();
743 
744  while(k)
745  {
746  k->set_optimization_type(t);
747 
748  SG_UNREF(k);
749  k = get_next_kernel();
750  }
751 
753 }
754 
756 {
757  CKernel* k = get_first_kernel();
758 
759  if (!k)
760  return false;
761 
762  CList* new_kernel_list = new CList(true);
763 
764  while(k)
765  {
766  new_kernel_list->append_element(new CCustomKernel(k));
767 
768  SG_UNREF(k);
769  k = get_next_kernel();
770  }
771 
773  kernel_list=new_kernel_list;
775 
776  return true;
777 }
778 
779 void CCombinedKernel::init()
780 {
781  sv_count=0;
782  sv_idx=NULL;
783  sv_weight=NULL;
785  initialized=false;
786 
788  kernel_list=new CList(true);
790 
791  SG_ADD((CSGObject**) &kernel_list, "kernel_list", "List of kernels.",
792  MS_AVAILABLE);
793  m_parameters->add_vector(&sv_idx, &sv_count, "sv_idx",
794  "Support vector index.");
795  m_parameters->add_vector(&sv_weight, &sv_count, "sv_weight",
796  "Support vector weights.");
797  SG_ADD(&append_subkernel_weights, "append_subkernel_weights",
798  "If subkernel weights are appended.", MS_AVAILABLE);
799  SG_ADD(&initialized, "initialized", "Whether kernel is ready to be used.",
801 }
802 
804  CSGObject* obj, index_t index)
805 {
806  SGMatrix<float64_t> result(0,0);
807 
808  if (strcmp(param->m_name, "combined_kernel_weight") == 0)
809  {
810  CListElement* current = NULL ;
811  CKernel* k = get_first_kernel(current);
812 
814  {
815  while(k)
816  {
817  result = k->get_parameter_gradient(param, obj, index);
818 
819  SG_UNREF(k);
820 
821  if (result.num_cols*result.num_rows > 0)
822  return result;
823 
824  k = get_next_kernel(current);
825  }
826  }
827 
828  else
829  {
830  while(k)
831  {
832  if(obj == k)
833  {
834  result = k->get_kernel_matrix();
835  SG_UNREF(k);
836  return result;
837  }
838 
839  SG_UNREF(k);
840 
841  k = get_next_kernel(current);
842  }
843  }
844  }
845 
846  else
847  {
848  CListElement* current = NULL ;
849  CKernel* k = get_first_kernel(current);
850  float64_t coeff;
851  while(k)
852  {
853  SGMatrix<float64_t> derivative =
854  k->get_parameter_gradient(param, obj, index);
855 
856  coeff = 1.0;
857 
859  coeff = k->get_combined_kernel_weight();
860 
861 
862  for (index_t g = 0; g < derivative.num_rows; g++)
863  {
864  for (index_t h = 0; h < derivative.num_cols; h++)
865  derivative(g,h) *= coeff;
866  }
867 
868  if (derivative.num_cols*derivative.num_rows > 0)
869  {
870  if (result.num_cols == 0 && result.num_rows == 0)
871  result = derivative;
872 
873  else
874  {
875  for (index_t g = 0; g < derivative.num_rows; g++)
876  {
877  for (index_t h = 0; h < derivative.num_cols; h++)
878  result(g,h) += derivative(g,h);
879  }
880  }
881  }
882 
883  SG_UNREF(k);
884  k = get_next_kernel(current);
885  }
886  }
887 
888  return result;
889 }

SHOGUN Machine Learning Toolbox - Documentation