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