src/AdaBoostMHLearner.cpp

/*
* This file is part of MultiBoost, a multi-class 
* AdaBoost learner/classifier
*
* Copyright (C) 2005 Norman Casagrande
* For informations write to nova77@gmail.com
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*
*/

#include <ctime> // for time
#include <cmath> // for exp
#include <fstream> // for ofstream of the step-by-step data
#include <limits>

#include "IO/OutputInfo.h"
#include "IO/Serialization.h" // to save the found strong hypothesis
#include "Utils/Utils.h" // for addAndCheckExtension
#include "Defaults.h" // for defaultLearner

#include "AdaBoostMHLearner.h"

namespace MultiBoost {

// -----------------------------------------------------------------------------------

AdaBoostLearner::AdaBoostLearner(nor_utils::Args& args, int verbose)
: _args(args), _maxTime(-1), _theta(0), _verbose(verbose), _outputInfoFile(""),
  _smallVal(1E-10)
{
   // The file with the step-by-step information
   if ( args.hasArgument("-outputinfo") )
        args.getValue("-outputinfo", 0, _outputInfoFile);

   // get the learner type, if given
   _basicLearnerName = defaultLearner; // default learner. Defined in Defaults.h

   if ( args.hasArgument("-learnertype") )
   {
      string learnerString;
      args.getValue("-learnertype", 0, learnerString);

      if ( !BaseLearner::RegisteredLearners().hasLearner(learnerString) )
      {
         // Not found in the registered!
         cerr << "ERROR: learner <" << learnerString << "> not found in the registered learners!" << endl;
         exit(1);
      }
      else
         _basicLearnerName = learnerString;
   }

   if (_verbose > 1)    
      cout << "--> Using learner: " << _basicLearnerName << endl;

   // get the output strong hypothesis file name, if given
   if ( args.hasArgument("-shypname") )
        args.getValue("-shypname", 0, _shypFileName);
   else
      _shypFileName = string(SHYP_NAME);

   _shypFileName = nor_utils::addAndCheckExtension(_shypFileName, SHYP_EXTENSION);

   // Set time limit
   if ( args.hasArgument("-timelimit") )
   {
      args.getValue("-timelimit", 0, _maxTime);   
      if (_verbose > 1)    
         cout << "--> Overall Time Limit: " << _maxTime << " minutes" << endl;
   }

   // Set the value of theta
   if ( args.hasArgument("-edgeoffset") )
        args.getValue("-edgeoffset", 0, _theta);  

}

// -----------------------------------------------------------------------------------

void AdaBoostLearner::run(int numIterations, const string& trainFileName, const string& testFileName)
{
   time_t startTime, currentTime;
   time(&startTime);

   // get the registered weak learner
   BaseLearner* pWeakHypothesisSource = BaseLearner::RegisteredLearners().getLearner(_basicLearnerName);
   Serialization ss(_shypFileName, _basicLearnerName);

   // get the training input data, and load it
   InputData* pTrainData = pWeakHypothesisSource->createInputData();
   pTrainData->initOptions(_args);
   pTrainData->load(trainFileName, IT_TRAIN, _verbose);

   // get the testing input data, and load it
   InputData* pTestData = NULL;
   if ( !testFileName.empty() )
   {
      pTestData = pWeakHypothesisSource->createInputData();
      pTestData->initOptions(_args);
      pTestData->load(testFileName, IT_TEST, _verbose);
   }

   // The output information object
   OutputInfo* pOutInfo = NULL;

   if ( !_outputInfoFile.empty() )
      pOutInfo = new OutputInfo(_outputInfoFile);

   if (_verbose == 1)
      cout << "Learning in progress..." << endl;

   for (int t = 0; t < numIterations; ++t)
   {
      if (_verbose > 1)
         cout << " ------ WORKING ON ITERATION " << t << " ------ " << endl;

      BaseLearner* pWeakHypothesis = pWeakHypothesisSource->create();
      pWeakHypothesis->initOptions(_args);
      pWeakHypothesis->run(pTrainData);

      // Output the step-by-step informations
      if ( pOutInfo )
      {
         pOutInfo->outputIteration(t);
         pOutInfo->outputError(pTrainData, pWeakHypothesis);
         if (pTestData)
            pOutInfo->outputError(pTestData, pWeakHypothesis);
         pOutInfo->outputMargins(pTrainData, pWeakHypothesis);
         pOutInfo->outputEdge(pTrainData, pWeakHypothesis);
         pOutInfo->endLine();
      }
      
      // Updates the weights and returns the edge
      double gamma = updateWeights(pTrainData, pWeakHypothesis);

      // If gamma <= theta the algorithm must stop.
      // If theta == 0 and gamma is 0, it means that the weak learner is no better than chance
      // and no further training is possible.
      if (gamma <= _theta)
      {
         if (_verbose > 0)
         {
            cout << "Can't train any further: gamma = " << gamma 
                 << " (with and edge offset (theta)=" << _theta << ")" << endl;
         }
         break; 
      }

      // append the current weak learner to strong hypothesis file,
      // that is, serialize it.
      ss.appendHypothesis(t, pWeakHypothesis);

      // Add it to the internal list of weak hypotheses
      _foundHypotheses.push_back(pWeakHypothesis);

      // check if the time limit has been reached
      if (_maxTime > 0)
      {
         time( &currentTime );
         double diff = difftime(currentTime, startTime); // difftime is in seconds
         diff /= 60; // = minutes

         if (diff > _maxTime)
         {
            if (_verbose > 0)
               cout << "Time limit of " << _maxTime 
                    << " minutes has been reached!" << endl;
            break;     
         }
      } // check for maxtime

   }  // loop on iterations

   // Free the two input data objects
   if (pTrainData)
      delete pTrainData;
   if (pTestData)
      delete pTestData;

   if (pOutInfo)
      delete pOutInfo;

   if (_verbose > 0)
      cout << "Learning completed." << endl;
}

// -------------------------------------------------------------------------

double AdaBoostLearner::updateWeights(InputData* pData, BaseLearner* pWeakHypothesis)
{
   const int numExamples = pData->getNumExamples();
   const int numClasses = ClassMappings::getNumClasses();

   double Z = 0; // The normalization factor

   // recompute weights
   // computing the normalization factor Z
   for (int i = 0; i < numExamples; ++i)
   {
      for (int l = 0; l < numClasses; ++l)
      {
         Z += pData->getWeight(i, l) * // w
              exp( 
              -pWeakHypothesis->getAlpha() * // -alpha
               pWeakHypothesis->classify(pData, i, l) * // h_l(x_i)
               pData->getBinaryClass(i, l) // y_i
              );
      } // numClasses
   } // numExamples

   // The edge. It measures the
   // accuracy of the current weak hypothesis relative to random guessing
   double gamma = 0;

   // Now do the real re-weight
   // (and compute the edge at the same time)
   for (int i = 0; i < numExamples; ++i)
   {
      for (int l = 0; l < numClasses; ++l)
      {  
         double hy = pWeakHypothesis->classify(pData, i, l) * // h_l(x_i)
                     pData->getBinaryClass(i, l); // y_i

         double w = pData->getWeight(i, l);

         gamma += w * hy;

         // The new weight is  w * exp( -alpha * h(x_i) * y_i ) / Z
         pData->setWeight( i, l, 
                           w * exp( -pWeakHypothesis->getAlpha() * hy  ) / Z );
      } // numClasses
   } // numExamples

   return gamma;
}


// -------------------------------------------------------------------------

} // end of namespace MultiBoost

---