CombinedKernel.cpp

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 1999-2008 Soeren Sonnenburg
00008  * Written (W) 1999-2008 Gunnar Raetsch
00009  * Copyright (C) 1999-2008 Fraunhofer Institute FIRST and Max-Planck-Society
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     //we have to do the optimization business ourselves but lets
00320     //make sure we start cleanly
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     //clean up
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*) &params);
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*)&params[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*) &params[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         { // compute the usual way for any non-optimized kernel
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*) &params);
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*)&params[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(&params[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             { // compute the usual way for any non-optimized kernel
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 }

SHOGUN Machine Learning Toolbox - Documentation