source: branches/peters_vector/lib/classifier/SVM.h @ 469

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

non compiling checking before revision after design meeting

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