src/AdaBoostMHLearner.cpp

00001 /*
00002 * This file is part of MultiBoost, a multi-class 
00003 * AdaBoost learner/classifier
00004 *
00005 * Copyright (C) 2005 Norman Casagrande
00006 * For informations write to nova77@gmail.com
00007 *
00008 * This library is free software; you can redistribute it and/or
00009 * modify it under the terms of the GNU Lesser General Public
00010 * License as published by the Free Software Foundation; either
00011 * version 2.1 of the License, or (at your option) any later version.
00012 *
00013 * This library is distributed in the hope that it will be useful,
00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016 * Lesser General Public License for more details.
00017 *
00018 * You should have received a copy of the GNU Lesser General Public
00019 * License along with this library; if not, write to the Free Software
00020 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00021 *
00022 */
00023 
00024 #include <ctime> // for time
00025 #include <cmath> // for exp
00026 #include <fstream> // for ofstream of the step-by-step data
00027 #include <limits>
00028 
00029 #include "IO/OutputInfo.h"
00030 #include "IO/Serialization.h" // to save the found strong hypothesis
00031 #include "Utils/Utils.h" // for addAndCheckExtension
00032 #include "Defaults.h" // for defaultLearner
00033 
00034 #include "AdaBoostMHLearner.h"
00035 
00036 namespace MultiBoost {
00037 
00038 // -----------------------------------------------------------------------------------
00039 
00040 AdaBoostLearner::AdaBoostLearner(nor_utils::Args& args, int verbose)
00041 : _args(args), _maxTime(-1), _theta(0), _verbose(verbose), _outputInfoFile(""),
00042   _smallVal(1E-10)
00043 {
00044    // The file with the step-by-step information
00045    if ( args.hasArgument("-outputinfo") )
00046         args.getValue("-outputinfo", 0, _outputInfoFile);
00047 
00049    // get the learner type, if given
00050    _basicLearnerName = defaultLearner; // default learner. Defined in Defaults.h
00051 
00052    if ( args.hasArgument("-learnertype") )
00053    {
00054       string learnerString;
00055       args.getValue("-learnertype", 0, learnerString);
00056 
00057       if ( !BaseLearner::RegisteredLearners().hasLearner(learnerString) )
00058       {
00059          // Not found in the registered!
00060          cerr << "ERROR: learner <" << learnerString << "> not found in the registered learners!" << endl;
00061          exit(1);
00062       }
00063       else
00064          _basicLearnerName = learnerString;
00065    }
00066 
00067    if (_verbose > 1)    
00068       cout << "--> Using learner: " << _basicLearnerName << endl;
00069 
00071    // get the output strong hypothesis file name, if given
00072    if ( args.hasArgument("-shypname") )
00073         args.getValue("-shypname", 0, _shypFileName);
00074    else
00075       _shypFileName = string(SHYP_NAME);
00076 
00077    _shypFileName = nor_utils::addAndCheckExtension(_shypFileName, SHYP_EXTENSION);
00078 
00080    // Set time limit
00081    if ( args.hasArgument("-timelimit") )
00082    {
00083       args.getValue("-timelimit", 0, _maxTime);   
00084       if (_verbose > 1)    
00085          cout << "--> Overall Time Limit: " << _maxTime << " minutes" << endl;
00086    }
00087 
00088    // Set the value of theta
00089    if ( args.hasArgument("-edgeoffset") )
00090         args.getValue("-edgeoffset", 0, _theta);  
00091 
00092 }
00093 
00094 // -----------------------------------------------------------------------------------
00095 
00096 void AdaBoostLearner::run(int numIterations, const string& trainFileName, const string& testFileName)
00097 {
00098    time_t startTime, currentTime;
00099    time(&startTime);
00100 
00101    // get the registered weak learner
00102    BaseLearner* pWeakHypothesisSource = BaseLearner::RegisteredLearners().getLearner(_basicLearnerName);
00103    Serialization ss(_shypFileName, _basicLearnerName);
00104 
00105    // get the training input data, and load it
00106    InputData* pTrainData = pWeakHypothesisSource->createInputData();
00107    pTrainData->initOptions(_args);
00108    pTrainData->load(trainFileName, IT_TRAIN, _verbose);
00109 
00110    // get the testing input data, and load it
00111    InputData* pTestData = NULL;
00112    if ( !testFileName.empty() )
00113    {
00114       pTestData = pWeakHypothesisSource->createInputData();
00115       pTestData->initOptions(_args);
00116       pTestData->load(testFileName, IT_TEST, _verbose);
00117    }
00118 
00119    // The output information object
00120    OutputInfo* pOutInfo = NULL;
00121 
00122    if ( !_outputInfoFile.empty() )
00123       pOutInfo = new OutputInfo(_outputInfoFile);
00124 
00125    if (_verbose == 1)
00126       cout << "Learning in progress..." << endl;
00127 
00129    for (int t = 0; t < numIterations; ++t)
00130    {
00131       if (_verbose > 1)
00132          cout << " ------ WORKING ON ITERATION " << t << " ------ " << endl;
00133 
00134       BaseLearner* pWeakHypothesis = pWeakHypothesisSource->create();
00135       pWeakHypothesis->initOptions(_args);
00136       pWeakHypothesis->run(pTrainData);
00137 
00138       // Output the step-by-step informations
00139       if ( pOutInfo )
00140       {
00141          pOutInfo->outputIteration(t);
00142          pOutInfo->outputError(pTrainData, pWeakHypothesis);
00143          if (pTestData)
00144             pOutInfo->outputError(pTestData, pWeakHypothesis);
00145          pOutInfo->outputMargins(pTrainData, pWeakHypothesis);
00146          pOutInfo->outputEdge(pTrainData, pWeakHypothesis);
00147          pOutInfo->endLine();
00148       }
00149       
00150       // Updates the weights and returns the edge
00151       double gamma = updateWeights(pTrainData, pWeakHypothesis);
00152 
00153       // If gamma <= theta the algorithm must stop.
00154       // If theta == 0 and gamma is 0, it means that the weak learner is no better than chance
00155       // and no further training is possible.
00156       if (gamma <= _theta)
00157       {
00158          if (_verbose > 0)
00159          {
00160             cout << "Can't train any further: gamma = " << gamma 
00161                  << " (with and edge offset (theta)=" << _theta << ")" << endl;
00162          }
00163          break; 
00164       }
00165 
00166       // append the current weak learner to strong hypothesis file,
00167       // that is, serialize it.
00168       ss.appendHypothesis(t, pWeakHypothesis);
00169 
00170       // Add it to the internal list of weak hypotheses
00171       _foundHypotheses.push_back(pWeakHypothesis);
00172 
00173       // check if the time limit has been reached
00174       if (_maxTime > 0)
00175       {
00176          time( &currentTime );
00177          double diff = difftime(currentTime, startTime); // difftime is in seconds
00178          diff /= 60; // = minutes
00179 
00180          if (diff > _maxTime)
00181          {
00182             if (_verbose > 0)
00183                cout << "Time limit of " << _maxTime 
00184                     << " minutes has been reached!" << endl;
00185             break;     
00186          }
00187       } // check for maxtime
00188 
00189    }  // loop on iterations
00191 
00192    // Free the two input data objects
00193    if (pTrainData)
00194       delete pTrainData;
00195    if (pTestData)
00196       delete pTestData;
00197 
00198    if (pOutInfo)
00199       delete pOutInfo;
00200 
00201    if (_verbose > 0)
00202       cout << "Learning completed." << endl;
00203 }
00204 
00205 // -------------------------------------------------------------------------
00206 
00207 double AdaBoostLearner::updateWeights(InputData* pData, BaseLearner* pWeakHypothesis)
00208 {
00209    const int numExamples = pData->getNumExamples();
00210    const int numClasses = ClassMappings::getNumClasses();
00211 
00212    double Z = 0; // The normalization factor
00213 
00214    // recompute weights
00215    // computing the normalization factor Z
00216    for (int i = 0; i < numExamples; ++i)
00217    {
00218       for (int l = 0; l < numClasses; ++l)
00219       {
00220          Z += pData->getWeight(i, l) * // w
00221               exp( 
00222               -pWeakHypothesis->getAlpha() * // -alpha
00223                pWeakHypothesis->classify(pData, i, l) * // h_l(x_i)
00224                pData->getBinaryClass(i, l) // y_i
00225               );
00226       } // numClasses
00227    } // numExamples
00228 
00229    // The edge. It measures the
00230    // accuracy of the current weak hypothesis relative to random guessing
00231    double gamma = 0;
00232 
00233    // Now do the real re-weight
00234    // (and compute the edge at the same time)
00235    for (int i = 0; i < numExamples; ++i)
00236    {
00237       for (int l = 0; l < numClasses; ++l)
00238       {  
00239          double hy = pWeakHypothesis->classify(pData, i, l) * // h_l(x_i)
00240                      pData->getBinaryClass(i, l); // y_i
00241 
00242          double w = pData->getWeight(i, l);
00243 
00244          gamma += w * hy;
00245 
00246          // The new weight is  w * exp( -alpha * h(x_i) * y_i ) / Z
00247          pData->setWeight( i, l, 
00248                            w * exp( -pWeakHypothesis->getAlpha() * hy  ) / Z );
00249       } // numClasses
00250    } // numExamples
00251 
00252    return gamma;
00253 }
00254 
00255 
00256 // -------------------------------------------------------------------------
00257 
00258 } // end of namespace MultiBoost

Generated on Mon Nov 28 21:43:46 2005 for MultiBoost by  doxygen 1.4.5