SHOGUN  v3.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 <set>
57 #include <map>
58 #define STDEXT_NAMESPACE __gnu_cxx
59 #define std_hash_map std::map
60 #define std_hash_set std::set
61 
62 #include <shogun/io/SGIO.h>
63 #include <shogun/kernel/Kernel.h>
65 
66 namespace shogun
67 {
68 #ifndef DOXYGEN_SHOULD_SKIP_THIS
69  struct larank_kcache_s;
70  typedef struct larank_kcache_s larank_kcache_t;
71  struct larank_kcache_s
72  {
73  CKernel* func;
74  larank_kcache_t *prevbuddy;
75  larank_kcache_t *nextbuddy;
76  int64_t maxsize;
77  int64_t cursize;
78  int32_t l;
79  int32_t *i2r;
80  int32_t *r2i;
81  int32_t maxrowlen;
82  /* Rows */
83  int32_t *rsize;
84  float32_t *rdiag;
85  float32_t **rdata;
86  int32_t *rnext;
87  int32_t *rprev;
88  int32_t *qnext;
89  int32_t *qprev;
90  };
91 
92  /*
93  ** OUTPUT: one per class of the raining set, keep tracks of support
94  * vectors and their beta coefficients
95  */
96  class LaRankOutput
97  {
98  public:
99  LaRankOutput () : beta(NULL), g(NULL), kernel(NULL), l(0)
100  {
101  }
102  virtual ~LaRankOutput ()
103  {
104  destroy();
105  }
106 
107  // Initializing an output class (basically creating a kernel cache for it)
108  void initialize (CKernel* kfunc, int64_t cache);
109 
110  // Destroying an output class (basically destroying the kernel cache)
111  void destroy ();
112 
113  // !Important! Computing the score of a given input vector for the actual output
114  float64_t computeScore (int32_t x_id);
115 
116  // !Important! Computing the gradient of a given input vector for the actual output
117  float64_t computeGradient (int32_t xi_id, int32_t yi, int32_t ythis);
118 
119  // Updating the solution in the actual output
120  void update (int32_t x_id, float64_t lambda, float64_t gp);
121 
122  // Linking the cache of this output to the cache of an other "buddy" output
123  // so that if a requested value is not found in this cache, you can
124  // ask your buddy if it has it.
125  void set_kernel_buddy (larank_kcache_t * bud);
126 
127  // Removing useless support vectors (for which beta=0)
128  int32_t cleanup ();
129 
130  // --- Below are information or "get" functions --- //
131 
132  //
133  inline larank_kcache_t *getKernel () const
134  {
135  return kernel;
136  }
137  //
138  inline int32_t get_l () const
139  {
140  return l;
141  }
142 
143  //
144  float64_t getW2 ();
145 
146  //
147  float64_t getKii (int32_t x_id);
148 
149  //
150  float64_t getBeta (int32_t x_id);
151 
152  //
153  inline float32_t* getBetas () const
154  {
155  return beta;
156  }
157 
158  //
159  float64_t getGradient (int32_t x_id);
160 
161  //
162  bool isSupportVector (int32_t x_id) const;
163 
164  //
165  int32_t getSV (float32_t* &sv) const;
166 
167  private:
168  // the solution of LaRank relative to the actual class is stored in
169  // this parameters
170  float32_t* beta; // Beta coefficiens
171  float32_t* g; // Strored gradient derivatives
172  larank_kcache_t *kernel; // Cache for kernel values
173  int32_t l; // Number of support vectors
174  };
175 
176  /*
177  ** LARANKPATTERN: to keep track of the support patterns
178  */
179  class LaRankPattern
180  {
181  public:
182  LaRankPattern (int32_t x_index, int32_t label)
183  : x_id (x_index), y (label) {}
184  LaRankPattern ()
185  : x_id (0) {}
186 
187  bool exists () const
188  {
189  return x_id >= 0;
190  }
191 
192  void clear ()
193  {
194  x_id = -1;
195  }
196 
197  int32_t x_id;
198  int32_t y;
199  };
200 
201  /*
202  ** LARANKPATTERNS: the collection of support patterns
203  */
204  class LaRankPatterns
205  {
206  public:
207  LaRankPatterns () {}
208  ~LaRankPatterns () {}
209 
210  void insert (const LaRankPattern & pattern)
211  {
212  if (!isPattern (pattern.x_id))
213  {
214  if (freeidx.size ())
215  {
216  std_hash_set < uint32_t >::iterator it = freeidx.begin ();
217  patterns[*it] = pattern;
218  x_id2rank[pattern.x_id] = *it;
219  freeidx.erase (it);
220  }
221  else
222  {
223  patterns.push_back (pattern);
224  x_id2rank[pattern.x_id] = patterns.size () - 1;
225  }
226  }
227  else
228  {
229  int32_t rank = getPatternRank (pattern.x_id);
230  patterns[rank] = pattern;
231  }
232  }
233 
234  void remove (uint32_t i)
235  {
236  x_id2rank[patterns[i].x_id] = 0;
237  patterns[i].clear ();
238  freeidx.insert (i);
239  }
240 
241  bool empty () const
242  {
243  return patterns.size () == freeidx.size ();
244  }
245 
246  uint32_t size () const
247  {
248  return patterns.size () - freeidx.size ();
249  }
250 
251  LaRankPattern & sample ()
252  {
253  ASSERT (!empty ())
254  while (true)
255  {
256  uint32_t r = CMath::random(uint32_t(0), uint32_t(patterns.size ()-1));
257  if (patterns[r].exists ())
258  return patterns[r];
259  }
260  return patterns[0];
261  }
262 
263  uint32_t getPatternRank (int32_t x_id)
264  {
265  return x_id2rank[x_id];
266  }
267 
268  bool isPattern (int32_t x_id)
269  {
270  return x_id2rank[x_id] != 0;
271  }
272 
273  LaRankPattern & getPattern (int32_t x_id)
274  {
275  uint32_t rank = x_id2rank[x_id];
276  return patterns[rank];
277  }
278 
279  uint32_t maxcount () const
280  {
281  return patterns.size ();
282  }
283 
284  LaRankPattern & operator [] (uint32_t i)
285  {
286  return patterns[i];
287  }
288 
289  const LaRankPattern & operator [] (uint32_t i) const
290  {
291  return patterns[i];
292  }
293 
294  private:
295  std_hash_set < uint32_t >freeidx;
296  std::vector < LaRankPattern > patterns;
297  std_hash_map < int32_t, uint32_t >x_id2rank;
298  };
299 
300 
301 #endif // DOXYGEN_SHOULD_SKIP_THIS
302 
303 
307  class CLaRank: public CMulticlassSVM
308  {
309  public:
310  CLaRank ();
311 
318  CLaRank(float64_t C, CKernel* k, CLabels* lab);
319 
320  virtual ~CLaRank ();
321 
322  // LEARNING FUNCTION: add new patterns and run optimization steps
323  // selected with adaptative schedule
328  virtual int32_t add (int32_t x_id, int32_t yi);
329 
330  // PREDICTION FUNCTION: main function in la_rank_classify
334  virtual int32_t predict (int32_t x_id);
335 
337  virtual void destroy ();
338 
339  // Compute Duality gap (costly but used in stopping criteria in batch mode)
341  virtual float64_t computeGap ();
342 
343  // Nuber of classes so far
345  virtual uint32_t getNumOutputs () const;
346 
347  // Number of Support Vectors
349  int32_t getNSV ();
350 
351  // Norm of the parameters vector
353  float64_t computeW2 ();
354 
355  // Compute Dual objective value
357  float64_t getDual ();
358 
364 
366  virtual const char* get_name() const { return "LaRank"; }
367 
371  void set_batch_mode(bool enable) { batch_mode=enable; };
373  bool get_batch_mode() { return batch_mode; };
377  void set_tau(float64_t t) { tau=t; };
381  float64_t get_tau() { return tau; };
382 
383  protected:
385  bool train_machine(CFeatures* data);
386 
387  private:
388  /*
389  ** MAIN DARK OPTIMIZATION PROCESSES
390  */
391 
392  // Hash Table used to store the different outputs
394  typedef std_hash_map < int32_t, LaRankOutput > outputhash_t; // class index -> LaRankOutput
395 
397  outputhash_t outputs;
398 
399  LaRankOutput *getOutput (int32_t index);
400 
401  //
402  LaRankPatterns patterns;
403 
404  // Parameters
405  int32_t nb_seen_examples;
406  int32_t nb_removed;
407 
408  // Numbers of each operation performed so far
409  int32_t n_pro;
410  int32_t n_rep;
411  int32_t n_opt;
412 
413  // Running estimates for each operations
414  float64_t w_pro;
415  float64_t w_rep;
416  float64_t w_opt;
417 
418  int32_t y0;
419  float64_t m_dual;
420 
421  struct outputgradient_t
422  {
423  outputgradient_t (int32_t result_output, float64_t result_gradient)
424  : output (result_output), gradient (result_gradient) {}
425  outputgradient_t ()
426  : output (0), gradient (0) {}
427 
428  int32_t output;
429  float64_t gradient;
430 
431  bool operator < (const outputgradient_t & og) const
432  {
433  return gradient > og.gradient;
434  }
435  };
436 
437  //3 types of operations in LaRank
438  enum process_type
439  {
440  processNew,
441  processOld,
442  processOptimize
443  };
444 
445  struct process_return_t
446  {
447  process_return_t (float64_t dual, int32_t yprediction)
448  : dual_increase (dual), ypred (yprediction) {}
449  process_return_t () {}
450  float64_t dual_increase;
451  int32_t ypred;
452  };
453 
454  // IMPORTANT Main SMO optimization step
455  process_return_t process (const LaRankPattern & pattern, process_type ptype);
456 
457  // ProcessOld
458  float64_t reprocess ();
459 
460  // Optimize
461  float64_t optimize ();
462 
463  // remove patterns and return the number of patterns that were removed
464  uint32_t cleanup ();
465 
466  protected:
467 
469  std_hash_set < int32_t >classes;
470 
472  inline uint32_t class_count () const
473  {
474  return classes.size ();
475  }
476 
479 
481  int32_t nb_train;
483  int64_t cache;
486 
488  int32_t step;
489  };
490 }
491 #endif // LARANK_H

SHOGUN Machine Learning Toolbox - Documentation