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

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

directory svm -> classifier

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