source: trunk/yat/classifier/SVM.cc @ 1100

// $Id$

/*
  Copyright (C) 2004, 2005 Jari Häkkinen, Peter Johansson
  Copyright (C) 2006 Jari Häkkinen, Markus Ringnér, Peter Johansson
  Copyright (C) 2007 Jari Häkkinen, Peter Johansson

  This file is part of the yat library, http://trac.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  The yat 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
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.
*/

#include "SVM.h"
#include "DataLookup2D.h"
#include "Target.h"
#include "yat/random/random.h"
#include "yat/statistics/Averager.h"
#include "yat/utility/matrix.h"
#include "yat/utility/vector.h"

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <limits>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

namespace theplu {
namespace yat {
namespace classifier {  

  SVM::SVM(void)
    : bias_(0),
      C_inverse_(0),
      kernel_(NULL),
      margin_(0),
      max_epochs_(100000),
      tolerance_(0.00000001),
      trained_(false)
  {
  }


  SVM::~SVM()
  {
    if (kernel_)
      delete kernel_;
  }


  const utility::vector& SVM::alpha(void) const
  {
    return alpha_;
  }


  double SVM::C(void) const
  {
    return 1.0/C_inverse_;
  }


  void SVM::calculate_margin(void)
  {
    margin_ = 0;
    for(size_t i = 0; i<alpha_.size(); ++i){
      margin_ += alpha_(i)*target(i)*kernel_mod(i,i)*alpha_(i)*target(i);
      for(size_t j = i+1; j<alpha_.size(); ++j)
        margin_ += 2*alpha_(i)*target(i)*kernel_mod(i,j)*alpha_(j)*target(j);
    }
  }


  const DataLookup2D& SVM::data(void) const
  {
    return *kernel_;
  }


  double SVM::kernel_mod(const size_t i, const size_t j) const
  {
    assert(kernel_);
    assert(i<kernel_->rows());
    assert(i<kernel_->columns());
    return i!=j ? (*kernel_)(i,j) : (*kernel_)(i,j) + C_inverse_;
  }


  SVM* SVM::make_classifier(void) const
  {
    return new SVM(*this);
  }


  long int SVM::max_epochs(void) const
  {
    return max_epochs_;
  }


  void SVM::max_epochs(long int n)
  {
    max_epochs_=n;
  }


  const theplu::yat::utility::vector& SVM::output(void) const
  {
    return output_;
  }

  void SVM::predict(const DataLookup2D& input, utility::matrix& prediction) const
  {
    try {
      const KernelLookup& input_kernel =dynamic_cast<const KernelLookup&>(input);
      assert(input.rows()==alpha_.size());
      prediction.resize(2,input.columns(),0);
      for (size_t i = 0; i<input.columns(); i++){
        for (size_t j = 0; j<input.rows(); j++){
          prediction(0,i) += target(j)*alpha_(j)*input_kernel(j,i);
          assert(target(j));
        }
        prediction(0,i) = margin_ * (prediction(0,i) + bias_);
      }
      
      for (size_t i = 0; i<prediction.columns(); i++)
        prediction(1,i) = -prediction(0,i);
    }
    catch (std::bad_cast) {
      std::string str = 
        "Error in SVM::predict: DataLookup2D of unexpected class.";
      throw std::runtime_error(str);
    }
    
  }

  double SVM::predict(const DataLookup1D& x) const
  {
    double y=0;
    for (size_t i=0; i<alpha_.size(); i++)
      y += alpha_(i)*target_(i)*kernel_->element(x,i);

    return margin_*(y+bias_);
  }

  double SVM::predict(const DataLookupWeighted1D& x) const
  {
    double y=0;
    for (size_t i=0; i<alpha_.size(); i++)
      y += alpha_(i)*target_(i)*kernel_->element(x,i);

    return margin_*(y+bias_);
  }

  int SVM::target(size_t i) const
  {
    assert(i<target_.size());
    return target_.binary(i) ? 1 : -1;
  }

  void SVM::train(const KernelLookup& kernel, const Target& targ) 
  {
    if (kernel_)
      delete kernel_;
    kernel_ = new KernelLookup(kernel);
    target_ = targ;
    
    alpha_ = utility::vector(targ.size(), 0.0);
    output_ = utility::vector(targ.size(), 0.0);
    // initializing variables for optimization
    assert(target_.size()==kernel_->rows());
    assert(target_.size()==alpha_.size());

    sample_.init(alpha_,tolerance_);
    utility::vector   E(target_.size(),0);
    for (size_t i=0; i<E.size(); i++) {
      for (size_t j=0; j<E.size(); j++) 
        E(i) += kernel_mod(i,j)*target(j)*alpha_(j);
      E(i)-=target(i);
    }
    assert(target_.size()==E.size());
    assert(target_.size()==sample_.size());

    unsigned long int epochs = 0;
    double alpha_new2;
    double alpha_new1;
    double u;
    double v;

    // Training loop
    while(choose(E)) {
      bounds(u,v);        
      double k = ( kernel_mod(sample_.value_first(), sample_.value_first()) + 
                   kernel_mod(sample_.value_second(), sample_.value_second()) - 
                   2*kernel_mod(sample_.value_first(), sample_.value_second()));
      
      double alpha_old1=alpha_(sample_.value_first());
      double alpha_old2=alpha_(sample_.value_second());
      alpha_new2 = ( alpha_(sample_.value_second()) + 
                     target(sample_.value_second())*
                     ( E(sample_.value_first())-E(sample_.value_second()) )/k );
      
      if (alpha_new2 > v)
        alpha_new2 = v;
      else if (alpha_new2<u)
        alpha_new2 = u;
      
      // Updating the alphas
      // if alpha is 'zero' make the sample a non-support vector
      if (alpha_new2 < tolerance_){
        sample_.nsv_second();
      }
      else{
        sample_.sv_second();
      }
      
      
      alpha_new1 = (alpha_(sample_.value_first()) + 
                    (target(sample_.value_first()) * 
                     target(sample_.value_second()) * 
                     (alpha_(sample_.value_second()) - alpha_new2) ));
            
      // if alpha is 'zero' make the sample a non-support vector
      if (alpha_new1 < tolerance_){
        sample_.nsv_first();
      }
      else
        sample_.sv_first();
      
      alpha_(sample_.value_first()) = alpha_new1;
      alpha_(sample_.value_second()) = alpha_new2;
      
      // update E vector
      // Peter, perhaps one should only update SVs, but what happens in choose?
      for (size_t i=0; i<E.size(); i++) {
        E(i)+=( kernel_mod(i,sample_.value_first())*
                target(sample_.value_first()) *
                (alpha_new1-alpha_old1) );
        E(i)+=( kernel_mod(i,sample_.value_second())*
                target(sample_.value_second()) *
                (alpha_new2-alpha_old2) );
      }
            
      epochs++;  
      if (epochs>max_epochs_){
        throw std::runtime_error("SVM: maximal number of epochs reached.");
      }
    }
    calculate_margin();
    calculate_bias();
    trained_ = true;
  }


  bool SVM::choose(const theplu::yat::utility::vector& E)
  {
    // First check for violation among SVs
    // E should be the same for all SVs
    // Choose that pair having largest violation/difference.
    sample_.update_second(0);
    sample_.update_first(0);
    if (sample_.nof_sv()>1){

      double max = E(sample_(0));
      double min = max;
      for (size_t i=1; i<sample_.nof_sv(); i++){ 
        assert(alpha_(sample_(i))>tolerance_);
        if (E(sample_(i)) > max){
          max = E(sample_(i));
          sample_.update_second(i);
        }
        else if (E(sample_(i))<min){
          min = E(sample_(i));
          sample_.update_first(i);
        }
      }
      assert(alpha_(sample_.value_first())>tolerance_);
      assert(alpha_(sample_.value_second())>tolerance_);

      if (E(sample_.value_second()) - E(sample_.value_first()) > 2*tolerance_){
        return true;
      }
      
      // If no violation check among non-support vectors
      sample_.shuffle();
      for (size_t i=sample_.nof_sv(); i<sample_.size();i++){
        if (target_.binary(sample_(i))){
          if(E(sample_(i)) < E(sample_.value_first()) - 2*tolerance_){
            sample_.update_second(i);
            return true;
          }
        }
        else{
          if(E(sample_(i)) > E(sample_.value_second()) + 2*tolerance_){
            sample_.update_first(i);
            return true;
          }
        }
      }
    }

    // if no support vectors - special case
    else{
      // to avoid getting stuck we shuffle
      sample_.shuffle();
      for (size_t i=0; i<sample_.size(); i++) {
        if (target(sample_(i))==1){
          for (size_t j=0; j<sample_.size(); j++) {
            if ( target(sample_(j))==-1 && 
                 E(sample_(i)) < E(sample_(j))+2*tolerance_ ){
              sample_.update_first(i);
              sample_.update_second(j);
              return true;
            }
          }
        }
      }
    }
    
    // If there is no violation then we should stop training
    return false;

  }
  
  
  void SVM::bounds( double& u, double& v) const
  {
    if (target(sample_.value_first())!=target(sample_.value_second())) {
      if (alpha_(sample_.value_second()) > alpha_(sample_.value_first())) {
        v = std::numeric_limits<double>::max();
        u = alpha_(sample_.value_second()) - alpha_(sample_.value_first());
      }
      else {
        v = (std::numeric_limits<double>::max() - 
             alpha_(sample_.value_first()) + 
             alpha_(sample_.value_second()));
        u = 0;
      }
    }
    else {       
      if (alpha_(sample_.value_second()) + alpha_(sample_.value_first()) > 
           std::numeric_limits<double>::max()) {
        u = (alpha_(sample_.value_second()) + alpha_(sample_.value_first()) - 
              std::numeric_limits<double>::max());
        v =  std::numeric_limits<double>::max();    
      }
      else {
        u = 0;
        v = alpha_(sample_.value_first()) + alpha_(sample_.value_second());
      }
    }
  }
  
  void SVM::calculate_bias(void)
  {

    // calculating output without bias
    for (size_t i=0; i<output_.size(); i++) {
      output_(i)=0;
      for (size_t j=0; j<output_.size(); j++) 
        output_(i)+=alpha_(j)*target(j) * (*kernel_)(i,j);
    }

    if (!sample_.nof_sv()){
      std::stringstream ss;
      ss << "yat::classifier::SVM::train() error: " 
         << "Cannot calculate bias because there is no support vector"; 
      throw std::runtime_error(ss.str());
    }

    // For samples with alpha>0, we have: target*output=1-alpha/C
    bias_=0;
    for (size_t i=0; i<sample_.nof_sv(); i++) 
      bias_+= ( target(sample_(i)) * (1-alpha_(sample_(i))*C_inverse_) - 
                output_(sample_(i)) );
    bias_=bias_/sample_.nof_sv();
    for (size_t i=0; i<output_.size(); i++) 
      output_(i) += bias_;
  }

  void SVM::set_C(const double C)
  {
    C_inverse_ = 1/C;
  }

}}} // of namespace classifier, yat, and theplu