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 "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     //we have to do the optimization business ourselves but lets
00315     //make sure we start cleanly
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     //clean up
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*) &params);
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*)&params[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*) &params[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         { // compute the usual way for any non-optimized kernel
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*) &params);
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*)&params[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(&params[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             { // compute the usual way for any non-optimized kernel
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 }

SHOGUN Machine Learning Toolbox - Documentation