SHOGUN  v3.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
MKLMulticlass.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) 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 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation