Classifier_adaBoost.hpp

Go to the documentation of this file.

// Copyright (C) 2011 the authors listed below
// http://ecocpak.sourceforge.net
//
// Authors:
// - Dimitrios Bouzas (bouzas at ieee dot org)
// - Nikolaos Arvanitopoulos (niarvani at ieee dot org)
// - Anastasios Tefas (tefas at aiia dot csd dot auth dot gr)
//
// This file is part of the ECOC PAK C++ library. It is
// provided without any warranty of fitness for any purpose.
//
// You can redistribute this file and/or modify it under
// the terms of the GNU Lesser General Public License (LGPL)
// as published by the Free Software Foundation, either
// version 3 of the License or (at your option) any later
// version.
// (see http://www.opensource.org/licenses for more info)




#ifndef _CLASSIFIER_ADABOOST_H_
#define _CLASSIFIER_ADABOOST_H_



#include "Classifier.hpp"



class Classifier_weak
  {
  public:

  // ---------------------------------------------------------------- //
  // ------------------------ Constructors -------------------------- //
  // ---------------------------------------------------------------- //

  // Copy ctor -- Overloaded
  Classifier_weak
    (
    const Classifier_weak& c
    );

  // User defined ctor for weak classifier -- Overloaded
  Classifier_weak
    (
    u32 fea,
    double theta,
    int p,
    double alpha
    );

  // ---------------------------------------------------------------- //
  // ---------------------- Member Functions ------------------------ //
  // ---------------------------------------------------------------- //

  // ---------------------------------------------------------------- //
  // --------------------- Overloaded Operators --------------------- //
  // ---------------------------------------------------------------- //

  // ---------------------------------------------------------------- //
  // -------------------------- Attributes -------------------------- //
  // ---------------------------------------------------------------- //

  // feature
  u32 fea;

  // theta threshold
  double theta;

  // label
  int p;

  // alpha
  double alpha;
  };


Classifier_weak::Classifier_weak
  (
  const Classifier_weak& c
  )
  {
  // feature
  fea = c.fea;

  // theta threshold
  theta = c.theta;

  // label
  p = c.p;

  // alpha
  alpha = c.alpha;
  }



Classifier_weak::Classifier_weak
  (
  u32 _fea,
  double _theta,
  int _p,
  double _alpha
  )
  {
  // feature's number
  fea   = _fea;

  // threshold
  theta = _theta;

  // label
  p     = _p;

  // alpha
  alpha = _alpha;
  }



class Classifier_adaBoost : public Classifier
  {
  public:

  // ---------------------------------------------------------------- //
  // ------------------------ Constructors -------------------------- //
  // ---------------------------------------------------------------- //

  // Copy ctor -- Overloaded
  Classifier_adaBoost
    (
    const Classifier_adaBoost& c
    );

  // User defined ctor adaBoost -- Overloaded
  Classifier_adaBoost
    (
    const mat& A,
    const mat& B
    );

  // ---------------------------------------------------------------- //
  // ---------------------- Member Functions ------------------------ //
  // ---------------------------------------------------------------- //

  // return prediction value of classifier for input feature vector
  double predict(const rowvec& t) const;

  // ---------------------------------------------------------------- //
  // --------------------- Overloaded Operators --------------------- //
  // ---------------------------------------------------------------- //

  // ---------------------------------------------------------------- //
  // -------------------------- Attributes -------------------------- //
  // ---------------------------------------------------------------- //

  // vector with weak classifiers
  vector<Classifier_weak> L;
  };



Classifier_adaBoost::Classifier_adaBoost
  (
  const Classifier_adaBoost& c
  )
  {
  // update the plus and minus classes
  pos = c.pos;
  neg = c.neg;

  // update number of possitive and negative samples
  n_pos = c.n_pos;
  n_neg = c.n_neg;

  // update training error
  training_error = c.training_error;

  // copy vector of weak classifiers
  for(u32 i = 0; i < c.L.size(); i++)
    {
    L.push_back(c.L[i]);
    }

  }



Classifier_adaBoost::Classifier_adaBoost
  (
  const mat& A,
  const mat& B
  )
  {
  // number of positive class feature vectors
  n_pos = A.n_rows;

  // number of negative class feature vectors
  n_neg = B.n_rows;

  // number of features
  const u32 n_fea = A.n_cols;

  // number of training feature vectors -- training samples
  const u32 n_samples = n_pos + n_neg;

  // maximum number of iterations
  const u32 mxiter = param.degree;

  // initialize positive class weights
  rowvec w1 = ones<rowvec>(n_pos);

  // initialize negative class weights
  rowvec w2 = ones<rowvec>(n_neg);

  // initialize errors vector
  vec err = zeros<vec>(mxiter);

  // iterate through number of iterations
  for(u32 i = 0; i < mxiter; i++)
    {
    // normalization constant of weights
    double tw = accu(w1) + accu(w2);

    // classes are seperable break loop
    if(tw == 0)
      {
      break;
      }

    // normalize weights (convex sum)
    w1 /= tw;
    w2 /= tw;

    // --- train weak classifier --- //
    mat V = join_cols(A,B);
    vec dummy = ones<vec>(n_samples);

    mat W = trans(join_rows(w1, w2)) * ones<rowvec>(n_fea);

    rowvec valsumW = sum(W);

    mat Y = join_cols(ones<mat>(n_pos, n_fea), zeros<mat>(n_neg, n_fea));

    mat V_sort = sort(V);
    umat inds = zeros<umat>(n_samples, n_fea);
    mat W_sort = zeros<mat>(n_samples, n_fea);
    mat Y_sort = zeros<mat>(n_samples, n_fea);
    for(u32 j = 0; j < n_fea; j++)
      {
      inds.col(j) = sort_index(V.col(j));

      for(u32 l = 0; l < n_samples; l++)
        {
        W_sort(l,j) = W(inds(l,j), j);
        Y_sort(l,j) = Y(inds(l,j), j);
        }

      }

    mat P_cum = cumsum(Y_sort % W_sort);

    mat N_cum = cumsum((ones<mat>(n_samples, n_fea) - Y_sort) % W_sort);

    mat PN_cum1 = ((dummy * max(P_cum)) - P_cum) + N_cum;
    mat PN_cum2 = ((dummy * max(N_cum)) - N_cum) + P_cum;

    rowvec min1 = zeros<rowvec>(n_fea);
    urowvec thresh_ind1 = zeros<urowvec>(n_fea);
    rowvec min2 = zeros<rowvec>(n_fea);
    urowvec thresh_ind2 = zeros<urowvec>(n_fea);
    for(u32 j = 0; j < n_fea; j++)
      {
      vec tmpv = PN_cum1.col(j);
      min1[j] = tmpv.min(thresh_ind1[j]);
      tmpv = PN_cum2.col(j);
      min2[j] =  tmpv.min(thresh_ind2[j]);
      }

    uvec inds1 = find(min1 > min2);
    uvec inds2 = find(min1 <= min2);

    urowvec thresh_ind = zeros<urowvec>(n_fea);
    for(u32 j = 0; j < inds1.n_elem; j++)
      {
      thresh_ind[inds1[j]] = thresh_ind2[inds1[j]];
      }

    mat PN_cum = zeros<mat>(n_samples, n_fea);
    if(inds1.n_elem > 0)
      {
      for(u32 j = 0; j < inds1.n_elem; j++)
        {
        PN_cum.col(inds1[j]) = PN_cum2.col(inds1[j]);
        }

      }

    for(u32 j = 0; j < inds2.n_elem; j++)
      {
      thresh_ind[inds2[j]] = thresh_ind1[inds2[j]];
      }

    for(u32 j = 0; j < inds2.n_elem; j++)
      {
      PN_cum.col(inds2[j]) = PN_cum1.col(inds2[j]);
      }

    uvec inds3 = find(thresh_ind == n_samples);
    for(u32 j = 0; j < inds3.n_elem; j++)
      {
      thresh_ind[inds3[j]]--;
      }

    vec displacement = linspace(0, n_fea - 1, n_fea);

    urowvec thr_ind = conv_to<urowvec>::from(thresh_ind + trans(n_samples * displacement));

    rowvec thr = zeros<rowvec>(thr_ind.n_elem);
    for(u32 j = 0; j < thr_ind.n_elem; j++)
      {
      thr[j] = (V_sort[thr_ind[j]] + V_sort[thr_ind[j] + 1]) / 2.0;
      }

    rowvec p = zeros<rowvec>(thr_ind.n_elem);
    for(u32 j = 0; j < thr_ind.n_elem; j++)
      {
      p[j] = ((P_cum[thr_ind[j]] > N_cum[thr_ind[j]])? 1 : -1);
      }

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

    mat classes = conv_to<mat>::from(((dummy * p) % join_cols(A,B)) < (dummy * (p % thr)));

    rowvec error = sum((trans(join_rows(w1, w2)) * ones<rowvec>(n_fea))
                    % (classes != join_cols(ones<mat>(n_pos, n_fea), zeros<mat>(n_neg, n_fea))));

    u32 feature0;
    err[i] = error.min(feature0);

    double beta0 = err[i] / (1.0 - err[i]);

    // create and save weak classifier
    L.push_back
      (
      Classifier_weak
        (
        feature0,
        thr[feature0],
        p[feature0],
        -log10(beta0 + math::eps())
        )
      );


    // update weights for positive class
    vec fe =
      conv_to<vec>::from((p[feature0] * A.col(feature0)) < (p[feature0] * thr[feature0]));

    for(u32 j = 0; j < fe.n_elem; j++)
      {
      fe[j] = pow(beta0, fe[j]);
      }

    w1 = w1 % trans(fe);

    // update weights for negative class
    fe = conv_to<vec>::from((p[feature0] * B.col(feature0)) >= (p[feature0] * thr[feature0]));
    for(u32 j = 0; j < fe.n_elem; j++)
      {
      fe[j] = pow(beta0, fe[j]);
      }

    w2 = w2 % trans(fe);

    if(err[i] >= 0.5)
      {
      break;
      }

    // compute training error
    // u32 missed = 0;
    // for(u32 j = 0; j < n_pos; j++)
    //   {
    //   if(predict(A.row(j)) != 1)
    //     {
    //     missed++;
    //     }
    //   }

    // for(u32 j = 0; j < n_pos; j++)
    //   {
    //   if(predict(B.row(j)) != -1)
    //     {
    //     missed++;
    //     }
    //   }

    // if(double(missed) / double(n_samples) < math::eps())
    //   {
    //   break;
    //   }
    }

  }



inline
double
Classifier_adaBoost::predict(const rowvec& t) const
  {
  // cummulative sum
  double cm = 0.0;

  // cummulative threshold
  double thr = 0.0;

  // for each weak classifier
  for(u32 i = 0; i < L.size(); i++)
    {
    cm += (L[i].alpha * ((L[i].p * t[L[i].fea] < L[i].p * L[i].theta)? 1.0 : 0.0));
    thr += L[i].alpha;
    }

  return ((cm >= thr / 2.0)? 1.0 : -1.0);
  }



#endif