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

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

?

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