src/WeakLearners/StumpLearner.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 <cassert>
#include <limits> // for numeric_limits<>
#include <cmath>

#include "WeakLearners/StumpLearner.h"

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

namespace MultiBoost {

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

void StumpLearner::initOptions(nor_utils::Args& args)
{
   // Set the value of theta
   if ( args.hasArgument("-edgeoffset") )
      args.getValue("-edgeoffset", 0, _theta);   

   // set abstention
   if ( args.hasArgument("-abstention") )
   {
      string abstType;
      args.getValue("-abstention", 0, abstType);

      if (abstType == "greedy")
         _abstention = ABST_GREEDY;
      else if (abstType == "full")
         _abstention = ABST_FULL;
      else
      {
         cerr << "ERROR: Invalid type of abstention <" << abstType << ">!!" << endl;
         exit(1);
      }
   }
}

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

void StumpLearner::declareArguments(nor_utils::Args& args)
{
   args.declareArgument("-abstention", 
                        "Activate the abstention. Available types are:\n"
                        "  greedy: sorting and checking in O(k^2)\n"
                        "  full: the O(2^k) full search", 1, "<type>");
}

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

InputData* StumpLearner::createInputData()
{
   return new SortedData();
}

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

char StumpLearner::classify(InputData* pData, const int idx, const int classIdx)
{
   return _v[classIdx] * phi( pData->getValue(idx, _selectedColumn), classIdx );
}

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

double StumpLearner::getEnergy(vector<sRates>& mu, double& alpha, vector<char>& v)
{
   const int numClasses = ClassMappings::getNumClasses();

   sRates eps;

   // Get the overall error and correct rates
   for (int l = 0; l < numClasses; ++l)
   {
      eps.rMin += mu[l].rMin;
      eps.rPls += mu[l].rPls;
   }

   // assert: eps- + eps+ + eps0 = 1
   assert( eps.rMin + eps.rPls <= 1 + _smallVal &&
           eps.rMin + eps.rPls >= 1 - _smallVal);

   double currEnergy;
   if ( nor_utils::is_zero(_theta) )
   {
      alpha = getAlpha(eps.rMin, eps.rPls);
      currEnergy = 2 * sqrt( eps.rMin * eps.rPls );
   }
   else
   {
      alpha = getAlpha(eps.rMin, eps.rPls, _theta);
      currEnergy = exp( _theta * alpha ) * 
                  ( eps.rMin * exp(alpha) + eps.rPls * exp(alpha) );
   }

   // perform abstention
   switch(_abstention)
   {
      case ABST_GREEDY:
         // alpha and v are updated!
         currEnergy = doGreedyAbstention(mu, currEnergy, eps, alpha, v);
         break;
      case ABST_FULL:
         // alpha and v are updated!
         currEnergy = doFullAbstention(mu, currEnergy, eps, alpha, v);
         break;
      case ABST_NO_ABSTENTION:
         break;
   }

   // Condition: eps_pls > eps_min!!
   if (eps.rMin >= eps.rPls)
      currEnergy = numeric_limits<double>::max();

   return currEnergy; // this is what we are trying to minimize: 2*sqrt(eps+*eps-)+eps0
}

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

double StumpLearner::doGreedyAbstention(vector<sRates>& mu, double currEnergy, 
                                        sRates& eps, double& alpha, vector<char>& v)
{
   const int numClasses = ClassMappings::getNumClasses();

   // Abstention is performed by evaluating the class-wise error
   // and the case in which one element (the one with the highest mu_pls * mu_min value)
   // is ignored, that is has v[el] = 0

   // Sorting the energies for each vote
   sort(mu.begin(), mu.end());

   bool changed;
   sRates newEps;
   double newAlpha;
   double newEnergy;

   do
   {
      changed = false;

      for (int l = 0; l < numClasses; ++l)
      {
         if ( v[ mu[l].classIdx ] != 0 ) 
         {
            newEps.rMin = eps.rMin - mu[l].rMin;
            newEps.rPls = eps.rPls - mu[l].rPls;
            newEps.rZero = eps.rZero + mu[l].rZero;

            if ( nor_utils::is_zero(_theta) )
            {
               newEnergy = 2 * sqrt(newEps.rMin * newEps.rPls) + newEps.rZero;
               newAlpha = getAlpha(newEps.rMin, newEps.rPls);
            }
            else
            {
               newAlpha = getAlpha(newEps.rMin, newEps.rPls, _theta);
               newEnergy = exp( _theta * newAlpha ) *
                           ( newEps.rPls * exp(-newAlpha) + 
                             newEps.rMin * exp(newAlpha) + 
                             newEps.rZero );
            }

            if ( newEnergy < currEnergy + _smallVal)
            {
               // ok, this is v = 0!!
               changed = true;

               currEnergy = newEnergy;
               eps = newEps;

               v[ mu[l].classIdx ] = 0;
               alpha = newAlpha;

               // assert: eps- + eps+ + eps0 = 1
               assert( eps.rMin + eps.rPls + eps.rZero <= 1 + _smallVal &&
                       eps.rMin + eps.rPls + eps.rZero >= 1 - _smallVal );
            }
         } // if
      } //for

   } while (changed);

   return currEnergy;
}

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

double StumpLearner::doFullAbstention(const vector<sRates>& mu, double currEnergy, 
                                      sRates& eps, double& alpha, vector<char>& v)
{
   const int numClasses = ClassMappings::getNumClasses();

   vector<char> best(numClasses, 1);
   vector<char> candidate(numClasses);
   sRates newEps; // candidate
   double newAlpha;
   double newEnergy;

   sRates bestEps;

   for (int l = 1; l < numClasses; ++l)
   {
      // starts with an array with just one 0 (and the rest 1), 
      // then two 0, then three 0, etc..
      fill( candidate.begin(), candidate.begin()+l, 0 );
      fill( candidate.begin()+l, candidate.end(), 1 );

      // checks all the possible permutations of such array
      do {

         newEps = eps;

         for ( int j = 0; j < numClasses; ++j )
         {
            if ( candidate[j] == 0 )
            {
               newEps.rMin -= mu[j].rMin;
               newEps.rPls -= mu[j].rPls;
               newEps.rZero += mu[j].rZero;
            }
         }

         if ( nor_utils::is_zero(_theta) )
         {
            newEnergy = 2 * sqrt(newEps.rMin * newEps.rPls) + newEps.rZero;
            newAlpha = getAlpha(newEps.rMin, newEps.rPls);
         }
         else
         {
            newAlpha = getAlpha(newEps.rMin, newEps.rPls, _theta);
            newEnergy = exp( _theta * newAlpha ) *
                        ( newEps.rPls * exp(-newAlpha) + 
                          newEps.rMin * exp(newAlpha) + 
                          newEps.rZero );
         }

         if ( newEnergy < currEnergy + _smallVal)
         {
            currEnergy = newEnergy;

            best = candidate;
            alpha = newAlpha;
            bestEps = newEps;

            // assert: eps- + eps+ + eps0 = 1
            assert( newEps.rMin + newEps.rPls + newEps.rZero <= 1 + _smallVal &&
                    newEps.rMin + newEps.rPls + newEps.rZero >= 1 - _smallVal );
         }

      } while ( next_permutation(candidate.begin(), candidate.end()) );

   }

   for (int l = 0; l < numClasses; ++l)
      v[l] *= best[l];

   eps = bestEps;

   return currEnergy; // this is what we are trying to minimize: 2*sqrt(eps+*eps-)+eps0
}

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

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

   // save selectedCoulumn
   outputStream << Serialization::standardTag("column", _selectedColumn, numTabs) << endl;

   vector<int> vInt(_v.size());
   copy(_v.begin(), _v.end(), vInt.begin()); // copy to an integer array to allow serialization of a number
   // save the v vector
   outputStream << Serialization::vectorTag("vArray", vInt, numTabs) << endl;
}

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

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

   _selectedColumn = UnSerialization::seekAndParseEnclosedValue<int>(st, "column");

   // move until vArray tag
   string rawTag;
   string tag, tagParam, tagValue;
 
   // need to use an int because the string stream will load characters for char
   vector<int> vInt;

   // load vArray data
   UnSerialization::seekAndParseVectorTag(st, "vArray", vInt);
   for (vector<int>::const_iterator it = vInt.begin(); it != vInt.end(); ++it)
      _v.push_back((char)*it);

}

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

} // end of namespace MultiBoost

---