00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "lib/common.h"
00013 #include "lib/io.h"
00014 #include "lib/Signal.h"
00015 #include "base/Parallel.h"
00016
00017 #include "kernel/Kernel.h"
00018 #include "kernel/CombinedKernel.h"
00019 #include "features/CombinedFeatures.h"
00020
00021 #include <string.h>
00022
00023 #ifndef WIN32
00024 #include <pthread.h>
00025 #endif
00026
00027 struct S_THREAD_PARAM
00028 {
00029 CKernel* kernel;
00030 DREAL* result;
00031 INT* vec_idx;
00032 INT start;
00033 INT end;
00035 DREAL* weights;
00036 INT* IDX;
00037 INT num_suppvec;
00038 };
00039
00040 CCombinedKernel::CCombinedKernel(INT size, bool asw)
00041 : CKernel(size), sv_count(0), sv_idx(NULL), sv_weight(NULL),
00042 subkernel_weights_buffer(NULL), append_subkernel_weights(asw)
00043 {
00044 properties |= KP_LINADD | KP_KERNCOMBINATION | KP_BATCHEVALUATION;
00045 kernel_list=new CList<CKernel*>(true);
00046 SG_INFO("Combined kernel created (%p)\n", this) ;
00047 if (append_subkernel_weights)
00048 SG_INFO( "(subkernel weights are appended)\n") ;
00049 }
00050
00051 CCombinedKernel::CCombinedKernel(CCombinedFeatures *l, CCombinedFeatures *r, bool asw)
00052 : CKernel(10), sv_count(0), sv_idx(NULL), sv_weight(NULL),
00053 subkernel_weights_buffer(NULL), append_subkernel_weights(asw)
00054 {
00055 properties |= KP_LINADD | KP_KERNCOMBINATION | KP_BATCHEVALUATION;
00056 kernel_list=new CList<CKernel*>(true);
00057 SG_INFO("Combined kernel created (%p)\n", this) ;
00058 if (append_subkernel_weights) {
00059 SG_INFO("(subkernel weights are appended)\n") ;
00060 }
00061
00062 init(l, r);
00063 }
00064
00065 CCombinedKernel::~CCombinedKernel()
00066 {
00067 delete[] subkernel_weights_buffer;
00068 subkernel_weights_buffer=NULL;
00069
00070 cleanup();
00071 delete kernel_list;
00072
00073 SG_INFO("Combined kernel deleted (%p).\n", this);
00074 }
00075
00076 bool CCombinedKernel::init(CFeatures* l, CFeatures* r)
00077 {
00078 CKernel::init(l,r);
00079 ASSERT(l->get_feature_class()==C_COMBINED);
00080 ASSERT(r->get_feature_class()==C_COMBINED);
00081 ASSERT(l->get_feature_type()==F_UNKNOWN);
00082 ASSERT(r->get_feature_type()==F_UNKNOWN);
00083
00084 CFeatures* lf=NULL;
00085 CFeatures* rf=NULL;
00086 CKernel* k=NULL;
00087
00088 bool result=true;
00089
00090 CListElement<CFeatures*>*lfc = NULL, *rfc = NULL ;
00091 lf=((CCombinedFeatures*) l)->get_first_feature_obj(lfc) ;
00092 rf=((CCombinedFeatures*) r)->get_first_feature_obj(rfc) ;
00093 CListElement<CKernel*>* current = NULL ;
00094 k=get_first_kernel(current) ;
00095
00096 result = 1 ;
00097
00098 if ( lf && rf && k)
00099 {
00100 if (l!=r)
00101 {
00102 while ( result && lf && rf && k )
00103 {
00104 SG_DEBUG( "Initializing 0x%p - \"%s\"\n", this, k->get_name());
00105 result=k->init(lf,rf);
00106
00107 lf=((CCombinedFeatures*) l)->get_next_feature_obj(lfc) ;
00108 rf=((CCombinedFeatures*) r)->get_next_feature_obj(rfc) ;
00109 k=get_next_kernel(current) ;
00110 }
00111 }
00112 else
00113 {
00114 while ( result && lf && k )
00115 {
00116 SG_DEBUG( "Initializing 0x%p - \"%s\"\n", this, k->get_name());
00117 result=k->init(lf,rf);
00118
00119 lf=((CCombinedFeatures*) l)->get_next_feature_obj(lfc) ;
00120 k=get_next_kernel(current) ;
00121 rf=lf ;
00122 }
00123 }
00124 }
00125
00126 if (!result)
00127 {
00128 SG_INFO( "CombinedKernel: Initialising the following kernel failed\n");
00129 if (k)
00130 k->list_kernel();
00131 else
00132 SG_INFO( "<NULL>\n");
00133 return false;
00134 }
00135
00136 if ((lf!=NULL) || (rf!=NULL) || (k!=NULL))
00137 {
00138 SG_INFO( "CombinedKernel: Number of features/kernels does not match - bailing out\n");
00139 return false;
00140 }
00141
00142 return true;
00143 }
00144
00145 void CCombinedKernel::remove_lhs()
00146 {
00147 delete_optimization();
00148
00149 #ifdef SVMLIGHT
00150 if (lhs)
00151 cache_reset() ;
00152 #endif
00153 lhs=NULL ;
00154
00155 CListElement<CKernel*> * current = NULL ;
00156 CKernel* k=get_first_kernel(current);
00157
00158 while (k)
00159 {
00160 k->remove_lhs();
00161 k=get_next_kernel(current);
00162 }
00163 }
00164
00165 void CCombinedKernel::remove_rhs()
00166 {
00167 #ifdef SVMLIGHT
00168 if (rhs)
00169 cache_reset() ;
00170 #endif
00171 rhs=NULL ;
00172
00173 CListElement<CKernel*> * current = NULL ;
00174 CKernel* k=get_first_kernel(current);
00175
00176 while (k)
00177 {
00178 k->remove_rhs();
00179 k=get_next_kernel(current);
00180 }
00181 }
00182
00183 void CCombinedKernel::cleanup()
00184 {
00185 CListElement<CKernel*> * current = NULL ;
00186 CKernel* k=get_first_kernel(current);
00187
00188 while (k)
00189 {
00190 k->cleanup();
00191 k=get_next_kernel(current);
00192 }
00193
00194 delete_optimization();
00195
00196 CKernel::cleanup();
00197 }
00198
00199 void CCombinedKernel::list_kernels()
00200 {
00201 CKernel* k;
00202
00203 SG_INFO( "BEGIN COMBINED KERNEL LIST - ");
00204 this->list_kernel();
00205
00206 CListElement<CKernel*> * current = NULL ;
00207 k=get_first_kernel(current);
00208 while (k)
00209 {
00210 k->list_kernel();
00211 k=get_next_kernel(current);
00212 }
00213 SG_INFO( "END COMBINED KERNEL LIST - ");
00214 }
00215
00216 DREAL CCombinedKernel::compute(INT x, INT y)
00217 {
00218 DREAL result=0;
00219 CListElement<CKernel*> * current = NULL ;
00220 CKernel* k=get_first_kernel(current);
00221 while (k)
00222 {
00223 if (k->get_combined_kernel_weight()!=0)
00224 result += k->get_combined_kernel_weight() * k->kernel(x,y);
00225 k=get_next_kernel(current);
00226 }
00227
00228 return result;
00229 }
00230
00231 bool CCombinedKernel::init_optimization(INT count, INT *IDX, DREAL * weights)
00232 {
00233 SG_DEBUG( "initializing CCombinedKernel optimization\n") ;
00234
00235 delete_optimization();
00236
00237 CListElement<CKernel*> * current = NULL ;
00238 CKernel * k = get_first_kernel(current) ;
00239 bool have_non_optimizable = false ;
00240
00241 while(k)
00242 {
00243 bool ret = true ;
00244
00245 if (k && k->has_property(KP_LINADD))
00246 ret = k->init_optimization(count, IDX, weights) ;
00247 else
00248 {
00249 SG_WARNING( "non-optimizable kernel 0x%X in kernel-list\n",k) ;
00250 have_non_optimizable = true ;
00251 }
00252
00253 if (!ret)
00254 {
00255 have_non_optimizable = true ;
00256 SG_WARNING( "init_optimization of kernel 0x%X failed\n",k) ;
00257 } ;
00258
00259 k = get_next_kernel(current) ;
00260 }
00261
00262 if (have_non_optimizable)
00263 {
00264 SG_WARNING( "some kernels in the kernel-list are not optimized\n") ;
00265
00266 sv_idx = new INT[count] ;
00267 sv_weight = new DREAL[count] ;
00268 sv_count = count ;
00269 int i ;
00270 for (i=0; i<count; i++)
00271 {
00272 sv_idx[i] = IDX[i] ;
00273 sv_weight[i] = weights[i] ;
00274 }
00275 }
00276 set_is_initialized(true) ;
00277
00278 return true ;
00279 } ;
00280
00281 bool CCombinedKernel::delete_optimization()
00282 {
00283 CListElement<CKernel*> * current = NULL ;
00284 CKernel* k = get_first_kernel(current);
00285
00286 while(k)
00287 {
00288 if (k->has_property(KP_LINADD))
00289 k->delete_optimization();
00290
00291 k = get_next_kernel(current);
00292 }
00293
00294 delete[] sv_idx;
00295 sv_idx = NULL;
00296
00297 delete[] sv_weight;
00298 sv_weight = NULL;
00299
00300 sv_count = 0;
00301 set_is_initialized(false);
00302
00303 return true;
00304 }
00305
00306 void CCombinedKernel::compute_batch(INT num_vec, INT* vec_idx, DREAL* result, INT num_suppvec, INT* IDX, DREAL* weights, DREAL factor)
00307 {
00308 ASSERT(rhs);
00309 ASSERT(num_vec<=rhs->get_num_vectors())
00310 ASSERT(num_vec>0);
00311 ASSERT(vec_idx);
00312 ASSERT(result);
00313
00314
00315
00316 delete_optimization();
00317
00318 CListElement<CKernel*> * current = NULL ;
00319 CKernel * k = get_first_kernel(current) ;
00320
00321 while(k)
00322 {
00323 if (k && k->has_property(KP_BATCHEVALUATION))
00324 {
00325 if (k->get_combined_kernel_weight()!=0)
00326 k->compute_batch(num_vec, vec_idx, result, num_suppvec, IDX, weights, k->get_combined_kernel_weight());
00327 }
00328 else
00329 emulate_compute_batch(k, num_vec, vec_idx, result, num_suppvec, IDX, weights);
00330
00331 k = get_next_kernel(current);
00332 }
00333
00334
00335 delete_optimization();
00336 }
00337
00338 void* CCombinedKernel::compute_optimized_kernel_helper(void* p)
00339 {
00340 S_THREAD_PARAM* params= (S_THREAD_PARAM*) p;
00341 INT* vec_idx=params->vec_idx;
00342 CKernel* k=params->kernel;
00343 DREAL* result=params->result;
00344
00345 for (INT i=params->start; i<params->end; i++)
00346 result[i] += k->get_combined_kernel_weight()*k->compute_optimized(vec_idx[i]);
00347
00348 return NULL;
00349 }
00350
00351 void* CCombinedKernel::compute_kernel_helper(void* p)
00352 {
00353 S_THREAD_PARAM* params= (S_THREAD_PARAM*) p;
00354 INT* vec_idx=params->vec_idx;
00355 CKernel* k=params->kernel;
00356 DREAL* result=params->result;
00357 DREAL* weights=params->weights;
00358 INT* IDX=params->IDX;
00359 INT num_suppvec=params->num_suppvec;
00360
00361 for (INT i=params->start; i<params->end; i++)
00362 {
00363 int j=0;
00364 DREAL sub_result=0 ;
00365 for (j=0; j<num_suppvec; j++)
00366 sub_result += weights[j] * k->kernel(IDX[j], vec_idx[i]) ;
00367
00368 result[i] += k->get_combined_kernel_weight()*sub_result ;
00369 }
00370
00371 return NULL;
00372 }
00373
00374 void CCombinedKernel::emulate_compute_batch(CKernel* k, INT num_vec, INT* vec_idx, DREAL* result, INT num_suppvec, INT* IDX, DREAL* weights)
00375 {
00376 ASSERT(k);
00377 ASSERT(result);
00378
00379 if (k->has_property(KP_LINADD))
00380 {
00381 if (k->get_combined_kernel_weight()!=0)
00382 {
00383 k->init_optimization(num_suppvec, IDX, weights);
00384
00385 INT num_threads=parallel.get_num_threads();
00386 ASSERT(num_threads>0);
00387
00388 if (num_threads < 2)
00389 {
00390 S_THREAD_PARAM params;
00391 params.kernel=k;
00392 params.result=result;
00393 params.start=0;
00394 params.end=num_vec;
00395 params.vec_idx = vec_idx;
00396 compute_optimized_kernel_helper((void*) ¶ms);
00397 }
00398 #ifndef WIN32
00399 else
00400 {
00401 pthread_t threads[num_threads-1];
00402 S_THREAD_PARAM params[num_threads];
00403 INT step= num_vec/num_threads;
00404
00405 INT t;
00406
00407 for (t=0; t<num_threads-1; t++)
00408 {
00409 params[t].kernel = k;
00410 params[t].result = result;
00411 params[t].start = t*step;
00412 params[t].end = (t+1)*step;
00413 params[t].vec_idx = vec_idx;
00414 pthread_create(&threads[t], NULL, CCombinedKernel::compute_optimized_kernel_helper, (void*)¶ms[t]);
00415 }
00416
00417 params[t].kernel = k;
00418 params[t].result = result;
00419 params[t].start = t*step;
00420 params[t].end = num_vec;
00421 params[t].vec_idx = vec_idx;
00422 compute_optimized_kernel_helper((void*) ¶ms[t]);
00423
00424 for (t=0; t<num_threads-1; t++)
00425 pthread_join(threads[t], NULL);
00426
00427 }
00428 #endif
00429
00430 k->delete_optimization();
00431 }
00432 }
00433 else
00434 {
00435 ASSERT(IDX!=NULL || num_suppvec==0);
00436 ASSERT(weights!=NULL || num_suppvec==0);
00437
00438 if (k->get_combined_kernel_weight()!=0)
00439 {
00440 INT num_threads=parallel.get_num_threads();
00441 ASSERT(num_threads>0);
00442
00443 if (num_threads < 2)
00444 {
00445 S_THREAD_PARAM params;
00446 params.kernel=k;
00447 params.result=result;
00448 params.start=0;
00449 params.end=num_vec;
00450 params.vec_idx = vec_idx;
00451 params.IDX = IDX;
00452 params.weights = weights;
00453 params.num_suppvec = num_suppvec;
00454 compute_kernel_helper((void*) ¶ms);
00455 }
00456 #ifndef WIN32
00457 else
00458 {
00459 pthread_t threads[num_threads-1];
00460 S_THREAD_PARAM params[num_threads];
00461 INT step= num_vec/num_threads;
00462
00463 INT t;
00464
00465 for (t=0; t<num_threads-1; t++)
00466 {
00467 params[t].kernel = k;
00468 params[t].result = result;
00469 params[t].start = t*step;
00470 params[t].end = (t+1)*step;
00471 params[t].vec_idx = vec_idx;
00472 params[t].IDX = IDX;
00473 params[t].weights = weights;
00474 params[t].num_suppvec = num_suppvec;
00475 pthread_create(&threads[t], NULL, CCombinedKernel::compute_kernel_helper, (void*)¶ms[t]);
00476 }
00477
00478 params[t].kernel = k;
00479 params[t].result = result;
00480 params[t].start = t*step;
00481 params[t].end = num_vec;
00482 params[t].vec_idx = vec_idx;
00483 params[t].IDX = IDX;
00484 params[t].weights = weights;
00485 params[t].num_suppvec = num_suppvec;
00486 compute_kernel_helper(¶ms[t]);
00487
00488 for (t=0; t<num_threads-1; t++)
00489 pthread_join(threads[t], NULL);
00490
00491 }
00492 #endif
00493 }
00494 }
00495 }
00496
00497 DREAL CCombinedKernel::compute_optimized(INT idx)
00498 {
00499 if (!get_is_initialized())
00500 {
00501 SG_ERROR( "CCombinedKernel optimization not initialized\n") ;
00502 return 0 ;
00503 }
00504
00505 DREAL result = 0 ;
00506
00507 CListElement<CKernel*> * current = NULL ;
00508 CKernel * k = get_first_kernel(current) ;
00509 while(k)
00510 {
00511 if (k && k->has_property(KP_LINADD) &&
00512 k->get_is_initialized())
00513 {
00514 if (k->get_combined_kernel_weight()!=0)
00515 result += k->get_combined_kernel_weight()*
00516 k->compute_optimized(idx) ;
00517 }
00518 else
00519 {
00520 ASSERT(sv_idx!=NULL || sv_count==0);
00521 ASSERT(sv_weight!=NULL || sv_count==0);
00522
00523 if (k->get_combined_kernel_weight()!=0)
00524 {
00525 int j=0;
00526 DREAL sub_result=0 ;
00527 for (j=0; j<sv_count; j++)
00528 sub_result += sv_weight[j] * k->kernel(sv_idx[j], idx) ;
00529
00530 result += k->get_combined_kernel_weight()*sub_result ;
00531 }
00532 } ;
00533
00534 k = get_next_kernel(current) ;
00535 }
00536
00537 return result;
00538 }
00539
00540 void CCombinedKernel::add_to_normal(INT idx, DREAL weight)
00541 {
00542 CListElement<CKernel*> * current = NULL ;
00543 CKernel* k = get_first_kernel(current);
00544
00545 while(k)
00546 {
00547 k->add_to_normal(idx, weight);
00548 k = get_next_kernel(current);
00549 }
00550 set_is_initialized(true) ;
00551 }
00552
00553 void CCombinedKernel::clear_normal()
00554 {
00555 CListElement<CKernel*> * current = NULL ;
00556 CKernel* k = get_first_kernel(current);
00557
00558 while(k)
00559 {
00560 k->clear_normal() ;
00561 k = get_next_kernel(current);
00562 }
00563 set_is_initialized(true) ;
00564 }
00565
00566 void CCombinedKernel::compute_by_subkernel(INT idx, DREAL * subkernel_contrib)
00567 {
00568 if (append_subkernel_weights)
00569 {
00570 INT i=0 ;
00571 CListElement<CKernel*> * current = NULL ;
00572 CKernel* k = get_first_kernel(current);
00573 while(k)
00574 {
00575 INT num = -1 ;
00576 k->get_subkernel_weights(num);
00577 if (num>1)
00578 k->compute_by_subkernel(idx, &subkernel_contrib[i]) ;
00579 else
00580 subkernel_contrib[i] += k->get_combined_kernel_weight() * k->compute_optimized(idx) ;
00581
00582 k = get_next_kernel(current);
00583 i += num ;
00584 }
00585 }
00586 else
00587 {
00588 INT i=0 ;
00589 CListElement<CKernel*> * current = NULL ;
00590 CKernel* k = get_first_kernel(current);
00591 while(k)
00592 {
00593 if (k->get_combined_kernel_weight()!=0)
00594 subkernel_contrib[i] += k->get_combined_kernel_weight() * k->compute_optimized(idx) ;
00595 k = get_next_kernel(current);
00596 i++ ;
00597 }
00598 }
00599 }
00600
00601 const DREAL* CCombinedKernel::get_subkernel_weights(INT& num_weights)
00602 {
00603 num_weights = get_num_subkernels() ;
00604 delete[] subkernel_weights_buffer ;
00605 subkernel_weights_buffer = new DREAL[num_weights] ;
00606
00607 if (append_subkernel_weights)
00608 {
00609 INT i=0 ;
00610 CListElement<CKernel*> * current = NULL ;
00611 CKernel* k = get_first_kernel(current);
00612 while(k)
00613 {
00614 INT num = -1 ;
00615 const DREAL *w = k->get_subkernel_weights(num);
00616 ASSERT(num==k->get_num_subkernels());
00617 for (INT j=0; j<num; j++)
00618 subkernel_weights_buffer[i+j]=w[j] ;
00619 k = get_next_kernel(current);
00620 i += num ;
00621 }
00622 }
00623 else
00624 {
00625 INT i=0 ;
00626 CListElement<CKernel*> * current = NULL ;
00627 CKernel* k = get_first_kernel(current);
00628 while(k)
00629 {
00630 subkernel_weights_buffer[i] = k->get_combined_kernel_weight();
00631 k = get_next_kernel(current);
00632 i++ ;
00633 }
00634 }
00635
00636 return subkernel_weights_buffer ;
00637 }
00638
00639 void CCombinedKernel::set_subkernel_weights(DREAL* weights, INT num_weights)
00640 {
00641 if (append_subkernel_weights)
00642 {
00643 INT i=0 ;
00644 CListElement<CKernel*> * current = NULL ;
00645 CKernel* k = get_first_kernel(current);
00646 while(k)
00647 {
00648 INT num = k->get_num_subkernels() ;
00649 k->set_subkernel_weights(&weights[i],num);
00650 k = get_next_kernel(current);
00651 i += num ;
00652 }
00653 }
00654 else
00655 {
00656 INT i=0 ;
00657 CListElement<CKernel*> * current = NULL ;
00658 CKernel* k = get_first_kernel(current);
00659 while(k)
00660 {
00661 k->set_combined_kernel_weight(weights[i]);
00662 k = get_next_kernel(current);
00663 i++ ;
00664 }
00665 }
00666 }
00667
00668 void CCombinedKernel::set_optimization_type(EOptimizationType t)
00669 {
00670 CListElement<CKernel*> * current = NULL ;
00671 CKernel* k = get_first_kernel(current);
00672
00673 while(k)
00674 {
00675 k->set_optimization_type(t);
00676 k = get_next_kernel(current);
00677 }
00678
00679 CKernel::set_optimization_type(t);
00680 }