NICE_VisLearning/classifier/fpclassifier/logisticregression/SLR.cpp

#ifdef NICE_USELIB_OPENMP
#include <omp.h>
#endif

#include "vislearning/classifier/fpclassifier/logisticregression/SLR.h"
#include "vislearning/cbaselib/FeaturePool.h"

#include <iostream>

#define SLRDEBUG
#define featnorm

using namespace OBJREC;
using namespace std;
using namespace NICE;

SLR::SLR ()
{
}

SLR::SLR ( const Config *_conf, string section ) : conf ( _conf )
{
  maxiter = conf->gI ( section, "maxiter", 20000 );
  resamp_decay = conf->gD ( section, "resamp_decay", 0.5 );
  convergence_tol = conf->gD ( section, "convergence_tol", 1e-7 );
  min_resamp =  conf->gD ( section, "min_resamp", 0.001 );
  lambda = conf->gD ( section, "lambda", 0.1 );
  samplesperclass = conf->gD ( section, "samplesperclass", 200.0 );
  weight.setDim ( 0 );
  fdim = 0;
}

SLR::~SLR()
{
  //clean up
}

double SLR::classify ( Example & pce )
{
  double result;
  SparseVector *svec;

  if ( weight.getDim() == 0 )
    return 0.0;

  bool newvec = false;

  if ( pce.svec != NULL )
  {
    svec = pce.svec;
  }
  else
  {
    Vector x;

    x = * ( pce.vec );

#ifdef featnorm
    for ( int m = 0; m < ( int ) x.size(); m++ )
    {
      x[m] = ( x[m] - minval[m] ) / ( maxval[m] - minval[m] );
    }
#endif
    svec = new SparseVector ( x );

    svec->setDim ( x.size() );

    newvec = true;

  }

  if ( weight.size() == 0 )
    result = 0.0;
  else
  {
    result = 1.0 / ( 1.0 + exp ( -svec->innerProduct ( weight ) ) );
  }

  if ( newvec )
    delete svec;

  return result;
}

void SLR::train ( FeaturePool & _fp, Examples & examples, int classno )
{

  cout << "start train" << endl;
  fp = FeaturePool ( _fp );

  // Anzahl von Merkmalen
  int fanz = examples.size();
  assert ( fanz >= 2 );

  // Merkmalsdimension bestimmen
  Vector x;
  fp.calcFeatureVector ( examples[0].second, x );
  fdim = x.size();
  assert ( fdim > 0 );

  stepwise_regression ( examples, classno );
  cout << "end train" << endl;
}

void SLR::restore ( istream & is, int format )
{
  weight.restore ( is, format );
  fdim = ( int ) weight.getDim();
  maxval.resize ( fdim );
  minval.resize ( fdim );
  for ( int i = 0; i < fdim; i++ )
  {
    is >> maxval[i];
    is >> minval[i];
  }
}

void SLR::store ( ostream & os, int format ) const

{
  if ( format != -9999 ) {
    weight.store ( os, format );
    for ( int i = 0; i < fdim; i++ )
    {
      os << maxval[i] << " " << minval[i] << endl;
    }
  } else {
    weight.store ( os, format );
  }
}

void SLR::clear ()
{
//TODO: einbauen
}

int SLR::stepwise_regression ( Examples &x, int classno )
{
  // initialize randomization
  srand ( time ( NULL ) );
  //srand (1);

  cout << "start regression" << endl;

  // get the number of features
  int fnum = x.size();

  // create Datamatrix
  GMSparseVectorMatrix X;

  GMSparseVectorMatrix Y;

  vector<int> count ( 2, 0 );

  maxval.resize ( fdim );
  minval.resize ( fdim );

  if ( x[0].second.svec == NULL ) //input normal vectors
  {
    Vector feat;

    for ( int i = 0; i < fdim; i++ )
    {
      maxval[i] = numeric_limits<double>::min();
      minval[i] = numeric_limits<double>::max();
    }

    for ( int i = 0; i < fnum; i++ )
    {
      int pos = 0;
      if ( x[i].first != classno )
        pos = 1;

      ++count[pos];

      fp.calcFeatureVector ( x[i].second, feat );
#ifdef featnorm
      for ( int m = 0; m < ( int ) feat.size(); m++ )
      {
        minval[m] = std::min ( minval[m], feat[m] );
        maxval[m] = std::max ( maxval[m], feat[m] );
      }
#endif
      fdim = feat.size();
    }
  }
  else //input Sparse Vectors
  {
    for ( int i = 0; i < fnum; i++ )
    {
      int pos = 0;
      if ( x[i].first != classno )
        pos = 1;

      ++count[pos];
    }
    fdim = x[0].second.svec->getDim();
  }

  if ( count[0] == 0 || count[1] == 0 )
  {
    cerr << "not enought samples " << count[0] << " : " << count[1] << endl;
    weight.setDim ( 0 );
    return -1;
  }

  double samples = std::min ( count[0], count[1] );
  samples = std::min ( samples, samplesperclass );
  //samples = std::max(samples, 200);
  //samples = samplesperclass;

  vector<double> rands ( 2, 0.0 );
  vector<double> allsizes ( 2, 0.0 );
  for ( int i = 0; i < 2; i++ )
  {
    rands[i] = 1.0;        //use all samples (default if samples>count[i])
    if ( samples > 0 && samples < 1 ) rands[i] = samples;    //use relative number of samples wrt. class size
    if ( samples > 1 && samples <= count[i] ) rands[i] = samples / ( double ) count[i]; //use (approximately) fixed absolute number of samples for each class
    allsizes[i] = count[i];
    count[i] = 0;
  }

  for ( int i = 0; i < fnum; i++ )
  {
    int pos = 0;
    if ( x[i].first != classno )
      pos = 1;


    double r = ( double ) rand() / ( double ) RAND_MAX;

    if ( r > rands[pos] )
      continue;
    ++count[pos];

    if ( x[0].second.svec == NULL )
    {
      Vector feat;
      fp.calcFeatureVector ( x[i].second, feat );
#ifdef featnorm
      for ( int m = 0; m < ( int ) feat.size(); m++ )
      {
        feat[m] = ( feat[m] - minval[m] ) / ( maxval[m] - minval[m] );
      }
#endif

      X.addRow ( feat );
    }
    else
    {
      X.addRow ( x[i].second.svec );
    }
    SparseVector *v = new SparseVector ( 2 );
    ( *v ) [pos] = 1.0;
    Y.addRow ( v );
  }
  Y.setDel();

  if ( x[0].second.svec == NULL )
    X.setDel();

  for ( int i = 0; i < 2; i++ )
  {
    cerr << "Examples for class " << i << ": " << count[i] << " out of " << allsizes[i] << " with p = " << rands[i] << endl;
  }

#undef NORMALIZATION
#ifdef NORMALIZATION
  GMSparseVectorMatrix Xred;
  Xred.resize ( X.rows(), X.cols() );

  for ( int r = 0; r < ( int ) Xred.rows(); r++ )
  {
    for ( int c = 0; c < ( int ) Xred.cols(); c++ )
    {
      double tmp = X[r].get ( c );

      if ( Y[r].get ( 0 ) == 1 )
        tmp *= count[0] / fnum;
      else
        tmp *= count[1] / fnum;

      if ( fabs ( tmp ) > 10e-7 )
        Xred[r][c] = tmp;
    }
  }
#endif

  fnum = X.rows();

  GMSparseVectorMatrix xY;
#ifdef NORMALIZATION
  Xred.mult ( Y, xY, true );
#else
  X.mult ( Y, xY, true );
#endif

  weight.setDim ( fdim );

  // for faster Computing Xw = X*w
  GMSparseVectorMatrix Xw;
  X.mult ( weight, Xw, false, true );
  SparseVector S ( fnum );

  for ( int r = 0; r < fnum; r++ )
  {
    S[r] = 0.0;
    for ( int c = 0; c < 2; c++ )
    {
      S[r] += exp ( Xw[r].get ( c ) );
    }
  }

  // for faster computing ac[i] = (maxClassNo-1)/(2*maxClassNo) * Sum_j (x_i (j))^2

  Vector ac ( fdim );
  Vector lm_2_ac ( fdim );

  for ( int f = 0; f < fdim; f++ )
  {
    ac[f] = 0.0;
    for ( int a = 0; a < fnum; a++ )
    {
      ac[f] += X[a].get ( f ) * X[a].get ( f );
    }
    ac[f] *= 0.25;
    lm_2_ac[f] = ( lambda / 2.0 ) / ac[f];
  }

  // initialize the iterative optimization
  double incr = numeric_limits<double>::max();
  long non_zero = 0;
  long wasted_basis = 0;
  long needed_basis = 0;

  // prob of resample each weight
  vector<double> p_resamp;
  p_resamp.resize ( fdim );

  // loop over cycles
  long cycle = 0;

  for ( cycle = 0; cycle < maxiter; cycle++ )
  {
#ifdef SLRDEBUG
    cerr << "iteration: " << cycle << " of " << maxiter << endl;
#endif
    // zero out the diffs for assessing change
    double sum2_w_diff = 0.0;
    double sum2_w_old = 0.0;
    wasted_basis = 0;
    if ( cycle == 1 )
      needed_basis = 0;

    // update each weight
//#pragma omp parallel for
    for ( int basis = 0; basis < fdim; basis++ ) // über alle Dimensionen
    {
      int changed = 0;
      // get the starting weight
      double w_old = weight.get ( basis );

      // set the p_resamp if it's the first cycle
      if ( cycle == 0 )
      {
        p_resamp[basis] = 1.0;
      }

      // see if we're gonna update
      double rval = ( double ) rand() / ( double ) RAND_MAX;

      if ( ( w_old != 0 ) || ( rval < p_resamp[basis] ) )
      {
        // calc the probability
        double XdotP = 0.0;
        for ( int i = 0; i < fnum; i++ )
        {
#ifdef NORMALIZATION
          double e = Xred[i].get ( basis ) * exp ( Xw[i].get ( 0 ) ) / S[i];
#else
          double e = X[i].get ( basis ) * exp ( Xw[i].get ( 0 ) ) / S[i];
#endif
          if ( finite ( e ) )
            XdotP += e;
#ifdef SLRDEBUG
          else
            throw "numerical problems";
#endif
        }

        // get the gradient
        double grad = xY[basis].get ( 0 ) - XdotP;
        // set the new weight
        double w_new = w_old + grad / ac[basis];

        // test that we're within bounds
        if ( w_new > lm_2_ac[basis] )
        {
          // more towards bounds, but keep it
          w_new -= lm_2_ac[basis];
          changed = 1;

          // umark from being zero if necessary
          if ( w_old == 0.0 )
          {
            non_zero += 1;

            // reset the p_resample
            p_resamp[basis] = 1.0;

            // we needed the basis
            needed_basis += 1;
          }
        }
        else if ( w_new < -lm_2_ac[basis] )
        {
          // more towards bounds, but keep it
          w_new += lm_2_ac[basis];
          changed = 1;

          // umark from being zero if necessary
          if ( w_old == 0.0 )
          {
            non_zero += 1;

            // reset the p_resample
            p_resamp[basis] = 1.0;

            // we needed the basis
            needed_basis += 1;
          }
        }
        else
        {
          // gonna zero it out
          w_new = 0.0;

          // decrease the p_resamp
          p_resamp[basis] -= ( p_resamp[basis] - min_resamp ) * resamp_decay;

          // set the number of non-zero
          if ( w_old == 0.0 )
          {
            // we didn't change
            changed = 0;

            // and wasted a basis
            wasted_basis += 1;
          }
          else
          {
            // we changed
            changed = 1;

            // must update num non_zero
            non_zero -= 1;
          }
        }
        // process changes if necessary
        if ( changed == 1 )
        {
          // update the expected values
          double w_diff = w_new - w_old;
          for ( int i = 0; i < fnum; i++ )
          {
            double E_old = exp ( Xw[i].get ( 0 ) );
            double val = X[i].get ( basis ) * w_diff;
            if ( Xw[i].get ( 0 ) == 0.0 )
            {
              if ( fabs ( val ) > 10e-7 )
                Xw[i][0] = val;
            }
            else
              Xw[i][0] += X[i].get ( basis ) * w_diff;
            double E_new_m = exp ( Xw[i].get ( 0 ) );

            S[i] += E_new_m - E_old;
          }

          // update the weight
          if ( w_new == 0.0 )
          {
            if ( weight.get ( basis ) != 0.0 )
            {
              weight.erase ( basis );
            }
          }
          else
            weight[basis] = w_new;
          // keep track of the sqrt sum squared diffs
//#pragma omp critical
          sum2_w_diff += w_diff * w_diff;
        }
        // no matter what we keep track of the old
//#pragma omp critical
        sum2_w_old += w_old * w_old;
      }
    }

    // finished a cycle, assess convergence
    incr = sqrt ( sum2_w_diff ) / ( sqrt ( sum2_w_old ) + numeric_limits<double>::epsilon() );
#ifdef SLRDEBUG
    cout << "sum2_w_diff: " << sum2_w_diff << " sum2_w_old " << sum2_w_old << endl;
    cout << "convcrit: " << incr << " tol: " << convergence_tol << endl;
    //cout << "sum2_w_wold = " << sum2_w_old << " sum2_w_diff = " << sum2_w_diff << endl;
#endif
    if ( incr < convergence_tol )
    {
      // we converged!!!
      break;
    }
  }

  // finished updating weights
  // assess convergence
  cerr << "end regression after " << cycle << " steps"  << endl;
  return cycle;
}