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

Last change on this file since 527 was 527, checked in by Peter, 16 years ago

Modified Kernel to be built from MatrixLookup? rather than
gslapi::matrix. Also changed interface to create DataLookup1D from
DataLookup2D - is now coherent with gslapi.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.0 KB
Line 
1// $Id: SVM.h 527 2006-03-01 11:23:53Z peter $
2
3#ifndef _theplu_classifier_svm_
4#define _theplu_classifier_svm_
5
6#include <c++_tools/classifier/DataLookup2D.h>
7#include <c++_tools/classifier/KernelLookup.h>
8#include <c++_tools/classifier/SupervisedClassifier.h>
9#include <c++_tools/classifier/Target.h>
10#include <c++_tools/gslapi/vector.h>
11
12#include <cassert>
13#include <utility>
14#include <vector>
15
16
17namespace theplu {
18namespace classifier { 
19
20  // @internal Class keeping track of which samples are support vectors and
21  // not. The first nof_sv elements in the vector are indices of the
22  // support vectors
23  //
24  class Index
25  {
26
27  public:
28    //Default Contructor
29    Index(); 
30
31    //
32    Index(const size_t);
33
34    // @return index_first
35    inline size_t index_first(void) const 
36    { assert(index_first_<n()); return index_first_; }
37
38    // @return index_second
39    inline size_t index_second(void) const 
40    { assert(index_second_<n()); return index_second_; }
41
42    // synch the object against alpha
43    void init(const gslapi::vector& alpha, const double);
44
45    // @return nof samples
46    inline size_t n(void) const { return vec_.size(); }
47
48    // @return nof support vectors
49    inline size_t nof_sv(void) const { return nof_sv_; }
50
51    // making first to an nsv. If already sv, nothing happens.
52    void nsv_first(void);
53
54    // making first to an nsv. If already sv, nothing happens.
55    void nsv_second(void);   
56
57    // randomizes the nsv part of vector and sets index_first to
58    // nof_sv_ (the first nsv)
59    void shuffle(void);
60
61    // making first to a sv. If already sv, nothing happens.
62    void sv_first(void);
63
64    // making first to a sv. If already sv, nothing happens.
65    void sv_second(void);
66
67    //
68    void update_first(const size_t);
69
70    //
71    void update_second(const size_t);
72
73    // @return value_first
74    inline size_t value_first(void) const 
75    { assert(value_first_<n()); return value_first_; }
76
77    // @return const ref value_second
78    inline size_t value_second(void) const 
79    { assert(value_first_<n()); return value_second_; }
80
81    inline size_t operator()(size_t i) const { 
82      assert(i<n()); assert(vec_[i]<n()); return vec_[i]; }
83
84  private:
85    size_t index_first_;
86    size_t index_second_;
87    size_t nof_sv_;
88    std::vector<size_t> vec_;
89    size_t value_first_; // vec_[index_first_] exists for fast access
90    size_t value_second_; // vec_[index_second_] exists for fast access
91   
92  };
93
94  ///
95  /// Class for SVM using Keerthi's second modification of Platt's
96  /// Sequential Minimal Optimization. The SVM uses all data given for
97  /// training. If validation or testing is wanted this should be
98  /// taken care of outside (in the kernel).
99  ///   
100  class SVM : public SupervisedClassifier
101  {
102 
103  public:
104    ///
105    /// Constructor taking the kernel and the target vector as
106    /// input.
107    ///
108    /// @note if the @a target or @a kernel
109    /// is destroyed the behaviour is undefined.
110    ///
111    SVM(const KernelLookup& kernel, const Target& target);
112
113    ///
114    /// @todo doc
115    ///
116    SupervisedClassifier* 
117    make_classifier(const DataLookup2D&, const Target&) const;
118
119    ///
120    /// @return \f$\alpha\f$
121    ///
122    inline const gslapi::vector& alpha(void) const { return alpha_; }
123
124    ///
125    /// The C-parameter is the balance term (see train()). A very
126    /// large C means the training will be focused on getting samples
127    /// correctly classified, with risk for overfitting and poor
128    /// generalisation. A too small C will result in a training where
129    /// misclassifications are not penalized. C is weighted with
130    /// respect to the size, so \f$ n_+C_+ = n_-C_- \f$, meaning a
131    /// misclassificaion of the smaller group is penalized
132    /// harder. This balance is equivalent to the one occuring for
133    /// regression with regularisation, or ANN-training with a
134    /// weight-decay term. Default is C set to infinity.
135    ///
136    /// @returns mean of vector \f$ C_i \f$
137    ///
138    inline double C(void) const { return 1/C_inverse_; }
139
140    ///
141    /// Default is max_epochs set to 10,000,000.
142    ///
143    /// @return number of maximal epochs
144    ///
145    inline long int max_epochs(void) const {return max_epochs_;}
146   
147    ///
148    /// The output is calculated as \f$ o_i = \sum \alpha_j t_j K_{ij}
149    /// + bias \f$, where \f$ t \f$ is the target.
150    ///
151    /// @return output
152    ///
153    inline const theplu::gslapi::vector& output(void) const { return output_; }
154
155    ///
156    /// Generate prediction @a output from @a input. The prediction is
157    /// returned in @a output. The output has 2 rows. The first row is
158    /// for binary target true, and the second is for binary target
159    /// false. The second row is superfluous because it the first row
160    /// negated. It exist just to be aligned with multi-class
161    /// SupervisedClassifiers. Each column in @a input and @a output
162    /// corresponds to a sample to predict. Each row in @a input
163    /// corresponds to a training sample, and more exactly row i in @a
164    /// input should correspond to row i in KernelLookup that was used
165    /// for training.
166    ///
167    void predict(const DataLookup2D& input, gslapi::matrix& output) const;
168
169    ///
170    /// @return output from data @a input
171    ///
172    double predict(const gslapi::vector& input) const;
173
174    ///
175    /// Function sets \f$ \alpha=0 \f$ and makes SVM untrained.
176    ///
177    inline void reset(void) 
178    { trained_=false; alpha_=gslapi::vector(target_.size(),0); }
179
180    ///
181    /// Training the SVM following Platt's SMO, with Keerti's
182    /// modifacation. Minimizing \f$ \frac{1}{2}\sum
183    /// y_iy_j\alpha_i\alpha_j(K_{ij}+\frac{1}{C_i}\delta_{ij}) \f$,
184    /// which corresponds to minimizing \f$ \sum w_i^2+\sum C_i\xi_i^2
185    /// \f$.
186    ///
187    bool train();
188
189       
190     
191  private:
192    ///
193    /// Copy constructor. (not implemented)
194    ///
195    SVM(const SVM&);
196         
197    ///
198    /// Calculates bounds for alpha2
199    ///
200    void bounds(double&, double&) const;
201
202    ///
203    /// @brief calculates the bias term
204    ///
205    /// @return true if successful
206    ///
207    bool calculate_bias(void);
208
209    ///
210    ///   Private function choosing which two elements that should be
211    ///   updated. First checking for the biggest violation (output - target =
212    ///   0) among support vectors (alpha!=0). If no violation was found check
213    ///   sequentially among the other samples. If no violation there as
214    ///   well training is completed
215    ///
216    ///  @return true if a pair of samples that violate the conditions
217    ///  can be found
218    ///
219    bool choose(const theplu::gslapi::vector&);
220
221    ///
222    /// @return kernel modified with diagonal term (soft margin)
223    ///
224    inline double kernel_mod(const size_t i, const size_t j) const 
225    { return i!=j ? (*kernel_)(i,j) : (*kernel_)(i,j) + C_inverse_; }
226   
227    /// @return 1 if i belong to binary target true else -1
228    inline int target(size_t i) const { return target_.binary(i) ? 1 : -1; }
229
230    gslapi::vector alpha_;
231    double bias_;
232    double C_inverse_;
233    const KernelLookup* kernel_; 
234    unsigned long int max_epochs_;
235    gslapi::vector output_;
236    Index sample_;
237    const Target& target_; 
238    bool trained_;
239    double tolerance_;
240   
241
242  };
243
244  ///
245  /// @todo The output operator for the SVM class.
246  ///
247  //std::ostream& operator<< (std::ostream& s, const SVM&);
248 
249 
250}} // of namespace classifier and namespace theplu
251
252#endif
Note: See TracBrowser for help on using the repository browser.