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