SHOGUN
v1.1.0
|
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) 2009 Alexander Binder 00008 * Copyright (C) 2009 Fraunhofer Institute FIRST and Max-Planck-Society 00009 */ 00010 00011 #include <shogun/classifier/mkl/MKLMultiClass.h> 00012 #include <shogun/io/SGIO.h> 00013 00014 using namespace shogun; 00015 00016 00017 CMKLMultiClass::CMKLMultiClass() 00018 : CMultiClassSVM(ONE_VS_REST) 00019 { 00020 svm=NULL; 00021 lpw=NULL; 00022 00023 mkl_eps=0.01; 00024 max_num_mkl_iters=999; 00025 pnorm=1; 00026 } 00027 00028 CMKLMultiClass::CMKLMultiClass(float64_t C, CKernel* k, CLabels* lab) 00029 : CMultiClassSVM(ONE_VS_REST, C, k, lab) 00030 { 00031 svm=NULL; 00032 lpw=NULL; 00033 00034 mkl_eps=0.01; 00035 max_num_mkl_iters=999; 00036 pnorm=1; 00037 } 00038 00039 00040 CMKLMultiClass::~CMKLMultiClass() 00041 { 00042 SG_UNREF(svm); 00043 svm=NULL; 00044 delete lpw; 00045 lpw=NULL; 00046 } 00047 00048 CMKLMultiClass::CMKLMultiClass( const CMKLMultiClass & cm) 00049 : CMultiClassSVM(ONE_VS_REST) 00050 { 00051 svm=NULL; 00052 lpw=NULL; 00053 SG_ERROR( 00054 " CMKLMultiClass::CMKLMultiClass(const CMKLMultiClass & cm): must " 00055 "not be called, glpk structure is currently not copyable"); 00056 } 00057 00058 CMKLMultiClass CMKLMultiClass::operator=( const CMKLMultiClass & cm) 00059 { 00060 SG_ERROR( 00061 " CMKLMultiClass CMKLMultiClass::operator=(...): must " 00062 "not be called, glpk structure is currently not copyable"); 00063 return (*this); 00064 } 00065 00066 00067 void CMKLMultiClass::initsvm() 00068 { 00069 if (!labels) 00070 { 00071 SG_ERROR("CMKLMultiClass::initsvm(): the set labels is NULL\n"); 00072 } 00073 00074 SG_UNREF(svm); 00075 svm=new CGMNPSVM; 00076 SG_REF(svm); 00077 00078 svm->set_C(get_C1(),get_C2()); 00079 svm->set_epsilon(epsilon); 00080 00081 if (labels->get_num_labels()<=0) 00082 { 00083 SG_ERROR("CMKLMultiClass::initsvm(): the number of labels is " 00084 "nonpositive, do not know how to handle this!\n"); 00085 } 00086 00087 svm->set_labels(labels); 00088 } 00089 00090 void CMKLMultiClass::initlpsolver() 00091 { 00092 if (!kernel) 00093 { 00094 SG_ERROR("CMKLMultiClass::initlpsolver(): the set kernel is NULL\n"); 00095 } 00096 00097 if (kernel->get_kernel_type()!=K_COMBINED) 00098 { 00099 SG_ERROR("CMKLMultiClass::initlpsolver(): given kernel is not of type" 00100 " K_COMBINED %d required by Multiclass Mkl \n", 00101 kernel->get_kernel_type()); 00102 } 00103 00104 int numker=dynamic_cast<CCombinedKernel *>(kernel)->get_num_subkernels(); 00105 00106 ASSERT(numker>0); 00107 /* 00108 if (lpw) 00109 { 00110 delete lpw; 00111 } 00112 */ 00113 00114 //lpw=new MKLMultiClassGLPK; 00115 if(pnorm>1) 00116 { 00117 lpw=new MKLMultiClassGradient; 00118 lpw->set_mkl_norm(pnorm); 00119 } 00120 else 00121 { 00122 lpw=new MKLMultiClassGLPK; 00123 } 00124 lpw->setup(numker); 00125 00126 } 00127 00128 00129 bool CMKLMultiClass::evaluatefinishcriterion(const int32_t 00130 numberofsilpiterations) 00131 { 00132 if ( (max_num_mkl_iters>0) && (numberofsilpiterations>=max_num_mkl_iters) ) 00133 { 00134 return(true); 00135 } 00136 00137 if (weightshistory.size()>1) 00138 { 00139 std::vector<float64_t> wold,wnew; 00140 00141 wold=weightshistory[ weightshistory.size()-2 ]; 00142 wnew=weightshistory.back(); 00143 float64_t delta=0; 00144 00145 ASSERT (wold.size()==wnew.size()); 00146 00147 00148 if((pnorm<=1)&&(!normweightssquared.empty())) 00149 { 00150 00151 delta=0; 00152 for (size_t i=0;i< wnew.size();++i) 00153 { 00154 delta+=(wold[i]-wnew[i])*(wold[i]-wnew[i]); 00155 } 00156 delta=sqrt(delta); 00157 SG_SDEBUG("L1 Norm chosen, weight delta %f \n",delta); 00158 00159 00160 //check dual gap part for mkl 00161 int32_t maxind=0; 00162 float64_t maxval=normweightssquared[maxind]; 00163 delta=0; 00164 for (size_t i=0;i< wnew.size();++i) 00165 { 00166 delta+=normweightssquared[i]*wnew[i]; 00167 if(wnew[i]>maxval) 00168 { 00169 maxind=i; 00170 maxval=wnew[i]; 00171 } 00172 } 00173 delta-=normweightssquared[maxind]; 00174 delta=fabs(delta); 00175 SG_SDEBUG("L1 Norm chosen, MKL part of duality gap %f \n",delta); 00176 if( (delta < mkl_eps) && (numberofsilpiterations>=1) ) 00177 { 00178 return(true); 00179 } 00180 00181 00182 00183 } 00184 else 00185 { 00186 delta=0; 00187 for (size_t i=0;i< wnew.size();++i) 00188 { 00189 delta+=(wold[i]-wnew[i])*(wold[i]-wnew[i]); 00190 } 00191 delta=sqrt(delta); 00192 SG_SDEBUG("Lp Norm chosen, weight delta %f \n",delta); 00193 00194 if( (delta < mkl_eps) && (numberofsilpiterations>=1) ) 00195 { 00196 return(true); 00197 } 00198 00199 } 00200 } 00201 00202 return(false); 00203 } 00204 00205 void CMKLMultiClass::addingweightsstep( const std::vector<float64_t> & 00206 curweights) 00207 { 00208 00209 if (weightshistory.size()>2) 00210 { 00211 weightshistory.erase(weightshistory.begin()); 00212 } 00213 00214 float64_t* weights(NULL); 00215 weights=SG_MALLOC(float64_t, curweights.size()); 00216 std::copy(curweights.begin(),curweights.end(),weights); 00217 00218 kernel->set_subkernel_weights(SGVector<float64_t>(weights, curweights.size())); 00219 SG_FREE(weights); 00220 weights=NULL; 00221 00222 initsvm(); 00223 00224 svm->set_kernel(kernel); 00225 svm->train(); 00226 00227 float64_t sumofsignfreealphas=getsumofsignfreealphas(); 00228 int32_t numkernels= 00229 dynamic_cast<CCombinedKernel *>(kernel)->get_num_subkernels(); 00230 00231 00232 normweightssquared.resize(numkernels); 00233 for (int32_t ind=0; ind < numkernels; ++ind ) 00234 { 00235 normweightssquared[ind]=getsquarenormofprimalcoefficients( ind ); 00236 } 00237 00238 lpw->addconstraint(normweightssquared,sumofsignfreealphas); 00239 } 00240 00241 float64_t CMKLMultiClass::getsumofsignfreealphas() 00242 { 00243 00244 std::vector<int> trainlabels2(labels->get_num_labels()); 00245 SGVector<int32_t> lab=labels->get_int_labels(); 00246 std::copy(lab.vector,lab.vector+lab.vlen, trainlabels2.begin()); 00247 lab.free_vector(); 00248 00249 ASSERT (trainlabels2.size()>0); 00250 float64_t sum=0; 00251 00252 for (int32_t nc=0; nc< labels->get_num_classes();++nc) 00253 { 00254 CSVM * sm=svm->get_svm(nc); 00255 00256 float64_t bia=sm->get_bias(); 00257 sum+= bia*bia; 00258 00259 SG_UNREF(sm); 00260 } 00261 00262 index_t basealphas_y = 0, basealphas_x = 0; 00263 float64_t* basealphas = svm->get_basealphas_ptr(&basealphas_y, 00264 &basealphas_x); 00265 00266 for (size_t lb=0; lb< trainlabels2.size();++lb) 00267 { 00268 for (int32_t nc=0; nc< labels->get_num_classes();++nc) 00269 { 00270 CSVM * sm=svm->get_svm(nc); 00271 00272 if ((int)nc!=trainlabels2[lb]) 00273 { 00274 CSVM * sm2=svm->get_svm(trainlabels2[lb]); 00275 00276 float64_t bia1=sm2->get_bias(); 00277 float64_t bia2=sm->get_bias(); 00278 SG_UNREF(sm2); 00279 00280 sum+= -basealphas[lb*basealphas_y + nc]*(bia1-bia2-1); 00281 } 00282 SG_UNREF(sm); 00283 } 00284 } 00285 00286 return(sum); 00287 } 00288 00289 float64_t CMKLMultiClass::getsquarenormofprimalcoefficients( 00290 const int32_t ind) 00291 { 00292 CKernel * ker=dynamic_cast<CCombinedKernel *>(kernel)->get_kernel(ind); 00293 00294 float64_t tmp=0; 00295 00296 for (int32_t classindex=0; classindex< labels->get_num_classes(); 00297 ++classindex) 00298 { 00299 CSVM * sm=svm->get_svm(classindex); 00300 00301 for (int32_t i=0; i < sm->get_num_support_vectors(); ++i) 00302 { 00303 float64_t alphai=sm->get_alpha(i); 00304 int32_t svindi= sm->get_support_vector(i); 00305 00306 for (int32_t k=0; k < sm->get_num_support_vectors(); ++k) 00307 { 00308 float64_t alphak=sm->get_alpha(k); 00309 int32_t svindk=sm->get_support_vector(k); 00310 00311 tmp+=alphai*ker->kernel(svindi,svindk) 00312 *alphak; 00313 00314 } 00315 } 00316 SG_UNREF(sm); 00317 } 00318 SG_UNREF(ker); 00319 ker=NULL; 00320 00321 return(tmp); 00322 } 00323 00324 00325 bool CMKLMultiClass::train_machine(CFeatures* data) 00326 { 00327 int numcl=labels->get_num_classes(); 00328 ASSERT(kernel); 00329 ASSERT(labels && labels->get_num_labels()); 00330 00331 if (data) 00332 { 00333 if (labels->get_num_labels() != data->get_num_vectors()) 00334 SG_ERROR("Number of training vectors does not match number of " 00335 "labels\n"); 00336 kernel->init(data, data); 00337 } 00338 00339 initlpsolver(); 00340 00341 weightshistory.clear(); 00342 00343 int32_t numkernels= 00344 dynamic_cast<CCombinedKernel *>(kernel)->get_num_subkernels(); 00345 00346 ::std::vector<float64_t> curweights(numkernels,1.0/numkernels); 00347 weightshistory.push_back(curweights); 00348 00349 addingweightsstep(curweights); 00350 00351 int32_t numberofsilpiterations=0; 00352 bool final=false; 00353 while (!final) 00354 { 00355 00356 //curweights.clear(); 00357 lpw->computeweights(curweights); 00358 weightshistory.push_back(curweights); 00359 00360 00361 final=evaluatefinishcriterion(numberofsilpiterations); 00362 ++numberofsilpiterations; 00363 00364 addingweightsstep(curweights); 00365 00366 } // while(false==final) 00367 00368 00369 //set alphas, bias, support vecs 00370 ASSERT(numcl>=1); 00371 create_multiclass_svm(numcl); 00372 00373 for (int32_t i=0; i<numcl; i++) 00374 { 00375 CSVM* osvm=svm->get_svm(i); 00376 CSVM* nsvm=new CSVM(osvm->get_num_support_vectors()); 00377 00378 for (int32_t k=0; k<osvm->get_num_support_vectors() ; k++) 00379 { 00380 nsvm->set_alpha(k, osvm->get_alpha(k) ); 00381 nsvm->set_support_vector(k,osvm->get_support_vector(k) ); 00382 } 00383 nsvm->set_bias(osvm->get_bias() ); 00384 set_svm(i, nsvm); 00385 00386 SG_UNREF(osvm); 00387 osvm=NULL; 00388 } 00389 00390 SG_UNREF(svm); 00391 svm=NULL; 00392 if (lpw) 00393 { 00394 delete lpw; 00395 } 00396 lpw=NULL; 00397 return(true); 00398 } 00399 00400 00401 00402 00403 float64_t* CMKLMultiClass::getsubkernelweights(int32_t & numweights) 00404 { 00405 if ( weightshistory.empty() ) 00406 { 00407 numweights=0; 00408 return NULL; 00409 } 00410 00411 std::vector<float64_t> subkerw=weightshistory.back(); 00412 numweights=weightshistory.back().size(); 00413 00414 float64_t* res=SG_MALLOC(float64_t, numweights); 00415 std::copy(weightshistory.back().begin(), weightshistory.back().end(),res); 00416 return res; 00417 } 00418 00419 void CMKLMultiClass::set_mkl_epsilon(float64_t eps ) 00420 { 00421 mkl_eps=eps; 00422 } 00423 00424 void CMKLMultiClass::set_max_num_mkliters(int32_t maxnum) 00425 { 00426 max_num_mkl_iters=maxnum; 00427 } 00428 00429 void CMKLMultiClass::set_mkl_norm(float64_t norm) 00430 { 00431 pnorm=norm; 00432 if(pnorm<1 ) 00433 SG_ERROR("CMKLMultiClass::set_mkl_norm(float64_t norm) : parameter pnorm<1"); 00434 }