src/WeakLearners/MultiStumpLearner.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 "MultiStumpLearner.h"

#include "IO/Serialization.h"
#include "IO/SortedData.h"

#include <limits> // for numeric_limits<>
#include <cassert>

namespace MultiBoost {

REGISTER_LEARNER(MultiStumpLearner)

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

void MultiStumpLearner::run(InputData* pData)
{
   const int numClasses = ClassMappings::getNumClasses();
   const int numColumns = pData->getNumColumns();

   // set the smoothing value to avoid numerical problem
   // when theta=0.
   setSmoothingVal( 1.0 / (double)pData->getNumExamples() * 0.01 );

   // resize
   _leftErrors.resize(numClasses);
   _rightErrors.resize(numClasses);
   _bestErrors.resize(numClasses);
   _weightsPerClass.resize(numClasses);
   _halfWeightsPerClass.resize(numClasses);

   vector<sRates> mu(numClasses); // The class-wise rates. See BaseLearner::sMu for more info.

   vector<char> tmpV(numClasses); // The class-wise votes/abstentions
   vector<double> tmpThresholds(numClasses);
   double tmpAlpha;

   double bestE = numeric_limits<double>::max();
   double tmpE;

   for (int j = 0; j < numColumns; ++j)
   {
      findThresholds(pData, j, tmpThresholds, mu, tmpV);

      tmpE = getEnergy(mu, tmpAlpha, tmpV);
      if (tmpE < bestE)
      {
         // Store it in the current algorithm
         // note: I don't really like having so many temp variables
         // but the alternative would be a structure, which would need
         // to be inheritable to make things more consistent. But this would
         // make it less flexible. Therefore, I am still undecided. This
         // might change!

         _alpha = tmpAlpha;
         _v = tmpV;
         _selectedColumn = j;
         _thresholds = tmpThresholds;

         bestE = tmpE;
      }

   }

}

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

char MultiStumpLearner::phi(double val, int classIdx)
{
   if (val > _thresholds[classIdx])
      return +1;
   else
      return -1;
}

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

void MultiStumpLearner::findThresholds(InputData* pData, const int columnIdx, 
                                       vector<double>& thresholds,
                                       vector<sRates>& mu, vector<char>& v)
{
   const vpIterator dataBegin = static_cast<SortedData*>(pData)->getSortedBegin(columnIdx);
   const vpIterator dataEnd = static_cast<SortedData*>(pData)->getSortedEnd(columnIdx);

   const int numClasses = ClassMappings::getNumClasses();

   // resize and set to 0
   fill(_leftErrors.begin(), _leftErrors.end(), 0);
   fill(_weightsPerClass.begin(), _weightsPerClass.end(), 0);

   // get the number of examples
   const size_t numPoints = dataEnd - dataBegin;

   vpIterator currentSplitPos; // the iterator of the currently examined example
   vpIterator previousSplitPos; // the iterator of the example before the current example
   cvpIterator endArray; // the iterator on the last example (just before dataEnd)

   // Initialization of the class-wise error

   // The class-wise error on the right side of the threshold
   double tmpRightError;

   for (int l = 0; l < numClasses; ++l)
   {
      tmpRightError = 0;

      for( currentSplitPos = dataBegin; currentSplitPos != dataEnd; ++currentSplitPos)
      {
         double weight = pData->getWeight(currentSplitPos->first, l);

         // We assume that class "currClass" is always on the right side;
         // therefore, all points l that are not currClass (x) on right side,
         // are considered error.
         // <l x l x x x l x x> = 3 (if each example has weight 1)
         // ^-- tmpError: error if we set the cut at the extreme left side
         if ( pData->getClass(currentSplitPos->first) != l )
            tmpRightError += weight;

         _weightsPerClass[l] += weight;
      }

      _halfWeightsPerClass[l] = _weightsPerClass[l] / 2;

      assert(tmpRightError < 1);
      _rightErrors[l] = tmpRightError; // store the class-wise error
      _bestErrors[l] = numeric_limits<double>::max();
   }


   currentSplitPos = dataBegin; // reset position
   endArray = dataEnd;
   --endArray;

   double tmpError = 0;
   double bestError = numeric_limits<double>::max();
   bool flipIt;

   // find the best threshold (cutting point)
   while (currentSplitPos != endArray)
   {
      // at the first split we have
      // first split: x | x x x x x x x x ..
      //    previous -^   ^- current
      previousSplitPos = currentSplitPos;
      ++currentSplitPos; 

      // point at the same position: to skip because we cannot find a cutting point here!
      while ( previousSplitPos->second == currentSplitPos->second && currentSplitPos != endArray)
      {
         for (int l = 0; l < numClasses; ++l)
         { 
            if ( pData->getClass( previousSplitPos->first ) == l )
               _leftErrors[l] += pData->getWeight(previousSplitPos->first, l);
            else
               _rightErrors[l] -= pData->getWeight(previousSplitPos->first, l);
         }

         previousSplitPos = currentSplitPos;
         ++currentSplitPos; 
      }

      for (int l = 0; l < numClasses; ++l)
      { 
         if ( pData->getClass( previousSplitPos->first ) == l )
         {
            // c=current class, x=other class
            // .. c | x x c x c x .. 
            _leftErrors[l] += pData->getWeight(previousSplitPos->first, l);
         }
         else
         {
            // c=current class, x=other class
            // .. x | x x c x c x ..
            _rightErrors[l] -= pData->getWeight(previousSplitPos->first, l);
         }

         tmpError = _rightErrors[l] + _leftErrors[l];

         // switch the class-wise error if it is bigger than chance
         if(tmpError > _halfWeightsPerClass[l] + _smallVal)
         {
            tmpError = _weightsPerClass[l] - tmpError;
            flipIt = true;
         }
         else
            flipIt = false;

         // The summed error MUST be smaller than chance
         assert(tmpError <= _halfWeightsPerClass[l] + _smallVal); 

         // the overall error is smaller!
         if (tmpError < _bestErrors[l] + _smallVal)
         {
            _bestErrors[l] = tmpError;
            // compute the thresholds
            thresholds[l] = ( previousSplitPos->second + currentSplitPos->second ) / 2;

            // If we assume that class [l] is always on the right side,
            // here we must flip, as the lowest error is on the left side.
            // example:
            // c=current class, x=other class
            // .. c c c x | c x x x .. = 2 errors (if we flip!)
            if (flipIt)
               v[l] = -1;
            else
               v[l] = +1;

         }
      } // for l
   } // while (currentSplitPos != endArray)


   // Fill the mus. This could have been done in the threshold loop, 
   // but here is done just once
   for (int l = 0; l < numClasses; ++l)
   {
      mu[l].classIdx = l;

      mu[l].rPls  = _weightsPerClass[l]-_bestErrors[l];
      mu[l].rMin  = _bestErrors[l];
      mu[l].rZero = mu[l].rPls + mu[l].rMin;
   }

}

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

void MultiStumpLearner::save(ofstream& outputStream, const int numTabs)
{
   // Calling the super-class method
   StumpLearner::save(outputStream, numTabs);

   // save all the thresholds
   outputStream << Serialization::vectorTag("thArray", _thresholds, numTabs) << endl;
}

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

void MultiStumpLearner::load(nor_utils::StreamTokenizer& st)
{
   // Calling the super-class method
   StumpLearner::load(st);

   // load vArray data
   UnSerialization::seekAndParseVectorTag(st, "thArray", _thresholds);
}

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

} // end of namespace MultiBoost

---