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