source: trunk/lib/classifier/SVM.h @ 545

// $Id: SVM.h 545 2006-03-06 13:35:45Z peter $

#ifndef _theplu_classifier_svm_ 
#define _theplu_classifier_svm_ 

#include <c++_tools/classifier/DataLookup2D.h>
#include <c++_tools/classifier/KernelLookup.h>
#include <c++_tools/classifier/SupervisedClassifier.h>
#include <c++_tools/classifier/Target.h>
#include <c++_tools/gslapi/vector.h>

#include <cassert>
#include <utility>
#include <vector>


namespace theplu {
namespace classifier {  

  // @internal Class keeping track of which samples are support vectors and
  // not. The first nof_sv elements in the vector are indices of the
  // support vectors
  //
  class Index
  {

  public:
    //Default Contructor
    Index(); 

    // 
    Index(const size_t);

    // @return index_first
    inline size_t index_first(void) const 
    { assert(index_first_<n()); return index_first_; }

    // @return index_second
    inline size_t index_second(void) const 
    { assert(index_second_<n()); return index_second_; }

    // synch the object against alpha
    void init(const gslapi::vector& alpha, const double);

    // @return nof samples
    inline size_t n(void) const { return vec_.size(); }

    // @return nof support vectors
    inline size_t nof_sv(void) const { return nof_sv_; }

    // making first to an nsv. If already sv, nothing happens.
    void nsv_first(void);

    // making first to an nsv. If already sv, nothing happens.
    void nsv_second(void);   

    // randomizes the nsv part of vector and sets index_first to
    // nof_sv_ (the first nsv)
    void shuffle(void);

    // making first to a sv. If already sv, nothing happens.
    void sv_first(void);

    // making first to a sv. If already sv, nothing happens.
    void sv_second(void);

    //
    void update_first(const size_t);

    //
    void update_second(const size_t);

    // @return value_first
    inline size_t value_first(void) const 
    { assert(value_first_<n()); return value_first_; }

    // @return const ref value_second
    inline size_t value_second(void) const 
    { assert(value_first_<n()); return value_second_; }

    inline size_t operator()(size_t i) const { 
      assert(i<n()); assert(vec_[i]<n()); return vec_[i]; }

  private:
    size_t index_first_;
    size_t index_second_;
    size_t nof_sv_;
    std::vector<size_t> vec_;
    size_t value_first_; // vec_[index_first_] exists for fast access
    size_t value_second_; // vec_[index_second_] exists for fast access
    
  };

  ///
  /// Class for SVM using Keerthi's second modification of Platt's
  /// Sequential Minimal Optimization. The SVM uses all data given for
  /// training. If validation or testing is wanted this should be
  /// taken care of outside (in the kernel).
  ///   
  class SVM : public SupervisedClassifier
  {
  
  public:
    ///
    /// Constructor taking the kernel and the target vector as
    /// input. 
    ///
    /// @note if the @a target or @a kernel
    /// is destroyed the behaviour is undefined.
    ///
    SVM(const KernelLookup& kernel, const Target& target);

    ///
    /// Constructor taking the kernel, the target vector, the score
    /// used to rank data inputs, and the number of top ranked data
    /// inputs to use in the classification.
    ///
    /// @note if the @a target or @a kernel
    /// is destroyed the behaviour is undefined.
    ///
    /// @note make no effect yet
    SVM(const KernelLookup& kernel, const Target& target,
        statistics::Score&, const size_t);

    ///
    /// @todo doc
    ///
    SupervisedClassifier* 
    make_classifier(const DataLookup2D&, const Target&) const;

    ///
    /// @return \f$\alpha\f$
    ///
    inline const gslapi::vector& alpha(void) const { return alpha_; }

    ///
    /// The C-parameter is the balance term (see train()). A very
    /// large C means the training will be focused on getting samples
    /// correctly classified, with risk for overfitting and poor
    /// generalisation. A too small C will result in a training where
    /// misclassifications are not penalized. C is weighted with
    /// respect to the size, so \f$ n_+C_+ = n_-C_- \f$, meaning a
    /// misclassificaion of the smaller group is penalized
    /// harder. This balance is equivalent to the one occuring for
    /// regression with regularisation, or ANN-training with a
    /// weight-decay term. Default is C set to infinity.
    ///
    /// @returns mean of vector \f$ C_i \f$
    ///
    inline double C(void) const { return 1/C_inverse_; }

    ///
    /// Default is max_epochs set to 10,000,000.
    ///
    /// @return number of maximal epochs
    ///
    inline long int max_epochs(void) const {return max_epochs_;}
    
    /// 
    /// The output is calculated as \f$ o_i = \sum \alpha_j t_j K_{ij}
    /// + bias \f$, where \f$ t \f$ is the target.
    ///
    /// @return output
    /// 
    inline const theplu::gslapi::vector& output(void) const { return output_; }

    ///
    /// Generate prediction @a output from @a input. The prediction is
    /// returned in @a output. The output has 2 rows. The first row is
    /// for binary target true, and the second is for binary target
    /// false. The second row is superfluous because it the first row
    /// negated. It exist just to be aligned with multi-class
    /// SupervisedClassifiers. Each column in @a input and @a output
    /// corresponds to a sample to predict. Each row in @a input
    /// corresponds to a training sample, and more exactly row i in @a
    /// input should correspond to row i in KernelLookup that was used
    /// for training.
    ///
    void predict(const DataLookup2D& input, gslapi::matrix& output) const;

    ///
    /// @return output from data @a input
    ///
    double predict(const DataLookup1D& input) const;

    ///
    /// @return output from data @a input with corresponding @a weight
    ///
    double predict(const DataLookup1D& input, const DataLookup1D& weight) const;

    ///
    /// Function sets \f$ \alpha=0 \f$ and makes SVM untrained.
    ///
    inline void reset(void) 
    { trained_=false; alpha_=gslapi::vector(target_.size(),0); }

    ///
    /// Training the SVM following Platt's SMO, with Keerti's
    /// modifacation. Minimizing \f$ \frac{1}{2}\sum
    /// y_iy_j\alpha_i\alpha_j(K_{ij}+\frac{1}{C_i}\delta_{ij}) \f$,
    /// which corresponds to minimizing \f$ \sum w_i^2+\sum C_i\xi_i^2
    /// \f$. 
    ///
    bool train();

       
      
  private:
    ///
    /// Copy constructor. (not implemented)
    /// 
    SVM(const SVM&);
         
    ///
    /// Calculates bounds for alpha2
    ///
    void bounds(double&, double&) const;

    ///
    /// @brief calculates the bias term
    ///
    /// @return true if successful
    ///
    bool calculate_bias(void);

    ///
    ///   Private function choosing which two elements that should be
    ///   updated. First checking for the biggest violation (output - target =
    ///   0) among support vectors (alpha!=0). If no violation was found check
    ///   sequentially among the other samples. If no violation there as
    ///   well training is completed
    ///
    ///  @return true if a pair of samples that violate the conditions
    ///  can be found
    ///
    bool choose(const theplu::gslapi::vector&);

    ///
    /// @return kernel modified with diagonal term (soft margin)
    ///
    inline double kernel_mod(const size_t i, const size_t j) const 
    { return i!=j ? (*kernel_)(i,j) : (*kernel_)(i,j) + C_inverse_; }
    
    /// @return 1 if i belong to binary target true else -1
    inline int target(size_t i) const { return target_.binary(i) ? 1 : -1; }

    gslapi::vector alpha_;
    double bias_;
    double C_inverse_;
    const KernelLookup* kernel_; 
    unsigned long int max_epochs_;
    gslapi::vector output_;
    bool owner_;
    Index sample_;
    bool trained_;
    double tolerance_;
    

  };

  ///
  /// @todo The output operator for the SVM class.
  ///
  //std::ostream& operator<< (std::ostream& s, const SVM&);
  
  
}} // of namespace classifier and namespace theplu

#endif