SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LaRank.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 // Main functions of the LaRank algorithm for soving Multiclass SVM
3 // Copyright (C) 2008- Antoine Bordes
4 // Shogun specific adjustments (w) 2009 Soeren Sonnenburg
5 
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License, or (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA
19 //
20 /***********************************************************************
21  *
22  * LUSH Lisp Universal Shell
23  * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI.
24  * Includes parts of TL3:
25  * Copyright (C) 1987-1999 Leon Bottou and Neuristique.
26  * Includes selected parts of SN3.2:
27  * Copyright (C) 1991-2001 AT&T Corp.
28  *
29  * This program is free software; you can redistribute it and/or modify
30  * it under the terms of the GNU General Public License as published by
31  * the Free Software Foundation; either version 2 of the License, or
32  * (at your option) any later version.
33  *
34  * This program is distributed in the hope that it will be useful,
35  * but WITHOUT ANY WARRANTY; without even the implied warranty of
36  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
37  * GNU General Public License for more details.
38  *
39  * You should have received a copy of the GNU General Public License
40  * along with this program; if not, write to the Free Software
41  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA
42  *
43  ***********************************************************************/
44 
45 /***********************************************************************
46  * $Id: kcache.h,v 1.8 2007/01/25 22:42:09 leonb Exp $
47  **********************************************************************/
48 
49 #ifndef LARANK_H
50 #define LARANK_H
51 
52 #include <ctime>
53 #include <vector>
54 #include <algorithm>
55 #include <sys/time.h>
56 #include <ext/hash_map>
57 #include <ext/hash_set>
58 
59 #define STDEXT_NAMESPACE __gnu_cxx
60 #define std_hash_map STDEXT_NAMESPACE::hash_map
61 #define std_hash_set STDEXT_NAMESPACE::hash_set
62 
63 #include <shogun/io/SGIO.h>
64 #include <shogun/kernel/Kernel.h>
66 
67 namespace shogun
68 {
69 #ifndef DOXYGEN_SHOULD_SKIP_THIS
70  struct larank_kcache_s;
71  typedef struct larank_kcache_s larank_kcache_t;
72  struct larank_kcache_s
73  {
74  CKernel* func;
75  larank_kcache_t *prevbuddy;
76  larank_kcache_t *nextbuddy;
77  int64_t maxsize;
78  int64_t cursize;
79  int32_t l;
80  int32_t *i2r;
81  int32_t *r2i;
82  int32_t maxrowlen;
83  /* Rows */
84  int32_t *rsize;
85  float32_t *rdiag;
86  float32_t **rdata;
87  int32_t *rnext;
88  int32_t *rprev;
89  int32_t *qnext;
90  int32_t *qprev;
91  };
92 
93  /*
94  ** OUTPUT: one per class of the raining set, keep tracks of support
95  * vectors and their beta coefficients
96  */
97  class LaRankOutput
98  {
99  public:
100  LaRankOutput () : beta(NULL), g(NULL), kernel(NULL), l(0)
101  {
102  }
103  virtual ~LaRankOutput ()
104  {
105  destroy();
106  }
107 
108  // Initializing an output class (basically creating a kernel cache for it)
109  void initialize (CKernel* kfunc, int64_t cache);
110 
111  // Destroying an output class (basically destroying the kernel cache)
112  void destroy ();
113 
114  // !Important! Computing the score of a given input vector for the actual output
115  float64_t computeScore (int32_t x_id);
116 
117  // !Important! Computing the gradient of a given input vector for the actual output
118  float64_t computeGradient (int32_t xi_id, int32_t yi, int32_t ythis);
119 
120  // Updating the solution in the actual output
121  void update (int32_t x_id, float64_t lambda, float64_t gp);
122 
123  // Linking the cache of this output to the cache of an other "buddy" output
124  // so that if a requested value is not found in this cache, you can
125  // ask your buddy if it has it.
126  void set_kernel_buddy (larank_kcache_t * bud);
127 
128  // Removing useless support vectors (for which beta=0)
129  int32_t cleanup ();
130 
131  // --- Below are information or "get" functions --- //
132 
133  //
134  inline larank_kcache_t *getKernel () const
135  {
136  return kernel;
137  }
138  //
139  inline int32_t get_l () const
140  {
141  return l;
142  }
143 
144  //
145  float64_t getW2 ();
146 
147  //
148  float64_t getKii (int32_t x_id);
149 
150  //
151  float64_t getBeta (int32_t x_id);
152 
153  //
154  inline float32_t* getBetas () const
155  {
156  return beta;
157  }
158 
159  //
160  float64_t getGradient (int32_t x_id);
161 
162  //
163  bool isSupportVector (int32_t x_id) const;
164 
165  //
166  int32_t getSV (float32_t* &sv) const;
167 
168  private:
169  // the solution of LaRank relative to the actual class is stored in
170  // this parameters
171  float32_t* beta; // Beta coefficiens
172  float32_t* g; // Strored gradient derivatives
173  larank_kcache_t *kernel; // Cache for kernel values
174  int32_t l; // Number of support vectors
175  };
176 
177  /*
178  ** LARANKPATTERN: to keep track of the support patterns
179  */
180  class LaRankPattern
181  {
182  public:
183  LaRankPattern (int32_t x_index, int32_t label)
184  : x_id (x_index), y (label) {}
185  LaRankPattern ()
186  : x_id (0) {}
187 
188  bool exists () const
189  {
190  return x_id >= 0;
191  }
192 
193  void clear ()
194  {
195  x_id = -1;
196  }
197 
198  int32_t x_id;
199  int32_t y;
200  };
201 
202  /*
203  ** LARANKPATTERNS: the collection of support patterns
204  */
205  class LaRankPatterns
206  {
207  public:
208  LaRankPatterns () {}
209  ~LaRankPatterns () {}
210 
211  void insert (const LaRankPattern & pattern)
212  {
213  if (!isPattern (pattern.x_id))
214  {
215  if (freeidx.size ())
216  {
217  std_hash_set < uint32_t >::iterator it = freeidx.begin ();
218  patterns[*it] = pattern;
219  x_id2rank[pattern.x_id] = *it;
220  freeidx.erase (it);
221  }
222  else
223  {
224  patterns.push_back (pattern);
225  x_id2rank[pattern.x_id] = patterns.size () - 1;
226  }
227  }
228  else
229  {
230  int32_t rank = getPatternRank (pattern.x_id);
231  patterns[rank] = pattern;
232  }
233  }
234 
235  void remove (uint32_t i)
236  {
237  x_id2rank[patterns[i].x_id] = 0;
238  patterns[i].clear ();
239  freeidx.insert (i);
240  }
241 
242  bool empty () const
243  {
244  return patterns.size () == freeidx.size ();
245  }
246 
247  uint32_t size () const
248  {
249  return patterns.size () - freeidx.size ();
250  }
251 
252  LaRankPattern & sample ()
253  {
254  ASSERT (!empty ());
255  while (true)
256  {
257  uint32_t r = CMath::random(0, patterns.size ()-1);
258  if (patterns[r].exists ())
259  return patterns[r];
260  }
261  return patterns[0];
262  }
263 
264  uint32_t getPatternRank (int32_t x_id)
265  {
266  return x_id2rank[x_id];
267  }
268 
269  bool isPattern (int32_t x_id)
270  {
271  return x_id2rank[x_id] != 0;
272  }
273 
274  LaRankPattern & getPattern (int32_t x_id)
275  {
276  uint32_t rank = x_id2rank[x_id];
277  return patterns[rank];
278  }
279 
280  uint32_t maxcount () const
281  {
282  return patterns.size ();
283  }
284 
285  LaRankPattern & operator [] (uint32_t i)
286  {
287  return patterns[i];
288  }
289 
290  const LaRankPattern & operator [] (uint32_t i) const
291  {
292  return patterns[i];
293  }
294 
295  private:
296  std_hash_set < uint32_t >freeidx;
297  std::vector < LaRankPattern > patterns;
298  std_hash_map < int32_t, uint32_t >x_id2rank;
299  };
300 
301 
302 #endif // DOXYGEN_SHOULD_SKIP_THIS
303 
304 
308  class CLaRank: public CMultiClassSVM
309  {
310  public:
311  CLaRank ();
312 
319  CLaRank(float64_t C, CKernel* k, CLabels* lab);
320 
321  virtual ~CLaRank ();
322 
323  // LEARNING FUNCTION: add new patterns and run optimization steps
324  // selected with adaptative schedule
329  virtual int32_t add (int32_t x_id, int32_t yi);
330 
331  // PREDICTION FUNCTION: main function in la_rank_classify
335  virtual int32_t predict (int32_t x_id);
336 
338  virtual void destroy ();
339 
340  // Compute Duality gap (costly but used in stopping criteria in batch mode)
342  virtual float64_t computeGap ();
343 
344  // Nuber of classes so far
346  virtual uint32_t getNumOutputs () const;
347 
348  // Number of Support Vectors
350  int32_t getNSV ();
351 
352  // Norm of the parameters vector
354  float64_t computeW2 ();
355 
356  // Compute Dual objective value
358  float64_t getDual ();
359 
364  virtual inline EClassifierType get_classifier_type() { return CT_LARANK; }
365 
367  inline virtual const char* get_name() const { return "LaRank"; }
368 
372  void set_batch_mode(bool enable) { batch_mode=enable; };
374  bool get_batch_mode() { return batch_mode; };
378  void set_tau(float64_t t) { tau=t; };
382  float64_t get_tau() { return tau; };
383 
384  protected:
386  bool train_machine(CFeatures* data);
387 
388  private:
389  /*
390  ** MAIN DARK OPTIMIZATION PROCESSES
391  */
392 
393  // Hash Table used to store the different outputs
395  typedef std_hash_map < int32_t, LaRankOutput > outputhash_t; // class index -> LaRankOutput
396 
398  outputhash_t outputs;
399 
400  LaRankOutput *getOutput (int32_t index);
401 
402  //
403  LaRankPatterns patterns;
404 
405  // Parameters
406  int32_t nb_seen_examples;
407  int32_t nb_removed;
408 
409  // Numbers of each operation performed so far
410  int32_t n_pro;
411  int32_t n_rep;
412  int32_t n_opt;
413 
414  // Running estimates for each operations
415  float64_t w_pro;
416  float64_t w_rep;
417  float64_t w_opt;
418 
419  int32_t y0;
420  float64_t dual;
421 
422  struct outputgradient_t
423  {
424  outputgradient_t (int32_t result_output, float64_t result_gradient)
425  : output (result_output), gradient (result_gradient) {}
426  outputgradient_t ()
427  : output (0), gradient (0) {}
428 
429  int32_t output;
430  float64_t gradient;
431 
432  bool operator < (const outputgradient_t & og) const
433  {
434  return gradient > og.gradient;
435  }
436  };
437 
438  //3 types of operations in LaRank
439  enum process_type
440  {
441  processNew,
442  processOld,
443  processOptimize
444  };
445 
446  struct process_return_t
447  {
448  process_return_t (float64_t dual, int32_t yprediction)
449  : dual_increase (dual), ypred (yprediction) {}
450  process_return_t () {}
451  float64_t dual_increase;
452  int32_t ypred;
453  };
454 
455  // IMPORTANT Main SMO optimization step
456  process_return_t process (const LaRankPattern & pattern, process_type ptype);
457 
458  // ProcessOld
459  float64_t reprocess ();
460 
461  // Optimize
462  float64_t optimize ();
463 
464  // remove patterns and return the number of patterns that were removed
465  uint32_t cleanup ();
466 
467  protected:
468 
470  std_hash_set < int32_t >classes;
471 
473  inline uint32_t class_count () const
474  {
475  return classes.size ();
476  }
477 
480 
482  int32_t nb_train;
484  int64_t cache;
487 
489  int32_t step;
490  };
491 }
492 #endif // LARANK_H

SHOGUN Machine Learning Toolbox - Documentation