SHOGUN  6.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
LaRank.cpp
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  * aint64_t 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.c,v 1.9 2007/01/25 22:42:09 leonb Exp $
47  **********************************************************************/
48 
49 #include <shogun/lib/config.h>
50 
51 #include <vector>
52 #include <algorithm>
53 #include <ctime>
54 #include <algorithm>
55 #ifndef _MSC_VER
56 #include <sys/time.h>
57 #endif
58 
59 #include <shogun/io/SGIO.h>
60 #include <shogun/lib/Signal.h>
61 #include <shogun/lib/Time.h>
65 #include <shogun/kernel/Kernel.h>
67 
68 using namespace shogun;
69 
70 namespace shogun
71 {
72  static larank_kcache_t* larank_kcache_create (CKernel* kernelfunc)
73  {
74  larank_kcache_t *self;
75  self = SG_CALLOC (larank_kcache_t, 1);
76  self->l = 0;
77  self->maxrowlen = 0;
78  self->func = kernelfunc;
79  self->prevbuddy = self;
80  self->nextbuddy = self;
81  self->cursize = sizeof (larank_kcache_t);
82  self->maxsize = 256 * 1024 * 1024;
83  self->qprev = SG_MALLOC(int32_t, 1);
84  self->qnext = SG_MALLOC(int32_t, 1);
85  self->rnext = self->qnext + 1;
86  self->rprev = self->qprev + 1;
87  self->rprev[-1] = -1;
88  self->rnext[-1] = -1;
89  return self;
90  }
91 
92  static void xtruncate (larank_kcache_t * self, int32_t k, int32_t nlen)
93  {
94  int32_t olen = self->rsize[k];
95  if (nlen < olen)
96  {
97  float32_t *ndata;
98  float32_t *odata = self->rdata[k];
99  if (nlen > 0)
100  {
101  ndata = SG_MALLOC(float32_t, nlen);
102  sg_memcpy (ndata, odata, nlen * sizeof (float32_t));
103  }
104  else
105  {
106  ndata = 0;
107  self->rnext[self->rprev[k]] = self->rnext[k];
108  self->rprev[self->rnext[k]] = self->rprev[k];
109  self->rnext[k] = self->rprev[k] = k;
110  }
111  SG_FREE (odata);
112  self->rdata[k] = ndata;
113  self->rsize[k] = nlen;
114  self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
115  }
116  }
117 
118  static void xpurge (larank_kcache_t * self)
119  {
120  if (self->cursize > self->maxsize)
121  {
122  int32_t k = self->rprev[-1];
123  while (self->cursize > self->maxsize && k != self->rnext[-1])
124  {
125  int32_t pk = self->rprev[k];
126  xtruncate (self, k, 0);
127  k = pk;
128  }
129  }
130  }
131 
132  static void larank_kcache_set_maximum_size (larank_kcache_t * self, int64_t entries)
133  {
134  ASSERT (self)
135  ASSERT (entries > 0)
136  self->maxsize = entries;
137  xpurge (self);
138  }
139 
140  static void larank_kcache_destroy (larank_kcache_t * self)
141  {
142  if (self)
143  {
144  int32_t i;
145  larank_kcache_t *nb = self->nextbuddy;
146  larank_kcache_t *pb = self->prevbuddy;
147  pb->nextbuddy = nb;
148  nb->prevbuddy = pb;
149  /* delete */
150  if (self->i2r)
151  SG_FREE (self->i2r);
152  if (self->r2i)
153  SG_FREE (self->r2i);
154  if (self->rdata)
155  for (i = 0; i < self->l; i++)
156  if (self->rdata[i])
157  SG_FREE (self->rdata[i]);
158  if (self->rdata)
159  SG_FREE (self->rdata);
160  if (self->rsize)
161  SG_FREE (self->rsize);
162  if (self->rdiag)
163  SG_FREE (self->rdiag);
164  if (self->qnext)
165  SG_FREE (self->qnext);
166  if (self->qprev)
167  SG_FREE (self->qprev);
168  memset (self, 0, sizeof (larank_kcache_t));
169  SG_FREE (self);
170  }
171  }
172 
173  static void xminsize (larank_kcache_t * self, int32_t n)
174  {
175  int32_t ol = self->l;
176  if (n > ol)
177  {
178  int32_t i;
179  int32_t nl = CMath::max (256, ol);
180  while (nl < n)
181  nl = nl + nl;
182  self->i2r = SG_REALLOC (int32_t, self->i2r, self->l, nl);
183  self->r2i = SG_REALLOC (int32_t, self->r2i, self->l, nl);
184  self->rsize = SG_REALLOC (int32_t, self->rsize, self->l, nl);
185  self->qnext = SG_REALLOC (int32_t, self->qnext, 1+self->l, (1 + nl));
186  self->qprev = SG_REALLOC (int32_t, self->qprev, 1+self->l, (1 + nl));
187  self->rdiag = SG_REALLOC (float32_t, self->rdiag, self->l, nl);
188  self->rdata = SG_REALLOC (float32_t*, self->rdata, self->l, nl);
189  self->rnext = self->qnext + 1;
190  self->rprev = self->qprev + 1;
191  for (i = ol; i < nl; i++)
192  {
193  self->i2r[i] = i;
194  self->r2i[i] = i;
195  self->rsize[i] = -1;
196  self->rnext[i] = i;
197  self->rprev[i] = i;
198  self->rdata[i] = 0;
199  }
200  self->l = nl;
201  }
202  }
203 
204  static int32_t* larank_kcache_r2i (larank_kcache_t * self, int32_t n)
205  {
206  xminsize (self, n);
207  return self->r2i;
208  }
209 
210  static void xextend (larank_kcache_t * self, int32_t k, int32_t nlen)
211  {
212  int32_t olen = self->rsize[k];
213  if (nlen > olen)
214  {
215  float32_t *ndata = SG_MALLOC(float32_t, nlen);
216  if (olen > 0)
217  {
218  float32_t *odata = self->rdata[k];
219  sg_memcpy (ndata, odata, olen * sizeof (float32_t));
220  SG_FREE (odata);
221  }
222  self->rdata[k] = ndata;
223  self->rsize[k] = nlen;
224  self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
225  self->maxrowlen = CMath::max (self->maxrowlen, nlen);
226  }
227  }
228 
229  static void xswap (larank_kcache_t * self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
230  {
231  /* swap row data */
232  if (r1 < self->maxrowlen || r2 < self->maxrowlen)
233  {
234  int32_t mrl = 0;
235  int32_t k = self->rnext[-1];
236  while (k >= 0)
237  {
238  int32_t nk = self->rnext[k];
239  int32_t n = self->rsize[k];
240  int32_t rr = self->i2r[k];
241  float32_t *d = self->rdata[k];
242  if (r1 < n)
243  {
244  if (r2 < n)
245  {
246  float32_t t1 = d[r1];
247  float32_t t2 = d[r2];
248  d[r1] = t2;
249  d[r2] = t1;
250  }
251  else if (rr == r2)
252  {
253  d[r1] = self->rdiag[k];
254  }
255  else
256  {
257  int32_t arsize = self->rsize[i2];
258  if (rr < arsize && rr != r1)
259  d[r1] = self->rdata[i2][rr];
260  else
261  xtruncate (self, k, r1);
262  }
263  }
264  else if (r2 < n)
265  {
266  if (rr == r1)
267  {
268  d[r2] = self->rdiag[k];
269  }
270  else
271  {
272  int32_t arsize = self->rsize[i1];
273  if (rr < arsize && rr != r2)
274  d[r2] = self->rdata[i1][rr];
275  else
276  xtruncate (self, k, r2);
277  }
278  }
279  mrl = CMath::max (mrl, self->rsize[k]);
280  k = nk;
281  }
282  self->maxrowlen = mrl;
283  }
284  /* swap r2i and i2r */
285  self->r2i[r1] = i2;
286  self->r2i[r2] = i1;
287  self->i2r[i1] = r2;
288  self->i2r[i2] = r1;
289  }
290 
291  static void larank_kcache_swap_rr (larank_kcache_t * self, int32_t r1, int32_t r2)
292  {
293  xminsize (self, 1 + CMath::max(r1, r2));
294  xswap (self, self->r2i[r1], self->r2i[r2], r1, r2);
295  }
296 
297  static void larank_kcache_swap_ri (larank_kcache_t * self, int32_t r1, int32_t i2)
298  {
299  xminsize (self, 1 + CMath::max (r1, i2));
300  xswap (self, self->r2i[r1], i2, r1, self->i2r[i2]);
301  }
302 
303  static float64_t xquery (larank_kcache_t * self, int32_t i, int32_t j)
304  {
305  /* search buddies */
306  larank_kcache_t *cache = self->nextbuddy;
307  do
308  {
309  int32_t l = cache->l;
310  if (i < l && j < l)
311  {
312  int32_t s = cache->rsize[i];
313  int32_t p = cache->i2r[j];
314  if (p < s)
315  return cache->rdata[i][p];
316  if (i == j && s >= 0)
317  return cache->rdiag[i];
318  p = cache->i2r[i];
319  s = cache->rsize[j];
320  if (p < s)
321  return cache->rdata[j][p];
322  }
323  cache = cache->nextbuddy;
324  }
325  while (cache != self);
326  /* compute */
327  return self->func->kernel(i, j);
328  }
329 
330 
331  static float64_t larank_kcache_query (larank_kcache_t * self, int32_t i, int32_t j)
332  {
333  ASSERT (self)
334  ASSERT (i >= 0)
335  ASSERT (j >= 0)
336  return xquery (self, i, j);
337  }
338 
339 
340  static void larank_kcache_set_buddy (larank_kcache_t * self, larank_kcache_t * buddy)
341  {
342  larank_kcache_t *p = self;
343  larank_kcache_t *selflast = self->prevbuddy;
344  larank_kcache_t *buddylast = buddy->prevbuddy;
345  /* check functions are identical */
346  ASSERT (self->func == buddy->func)
347  /* make sure we are not already buddies */
348  do
349  {
350  if (p == buddy)
351  return;
352  p = p->nextbuddy;
353  }
354  while (p != self);
355  /* link */
356  selflast->nextbuddy = buddy;
357  buddy->prevbuddy = selflast;
358  buddylast->nextbuddy = self;
359  self->prevbuddy = buddylast;
360  }
361 
362 
363  static float32_t* larank_kcache_query_row (larank_kcache_t * self, int32_t i, int32_t len)
364  {
365  ASSERT (i >= 0)
366  if (i < self->l && len <= self->rsize[i])
367  {
368  self->rnext[self->rprev[i]] = self->rnext[i];
369  self->rprev[self->rnext[i]] = self->rprev[i];
370  }
371  else
372  {
373  int32_t olen, p;
374  float32_t *d;
375  if (i >= self->l || len >= self->l)
376  xminsize (self, CMath::max (1 + i, len));
377  olen = self->rsize[i];
378  if (olen < len)
379  {
380  if (olen < 0)
381  {
382  self->rdiag[i] = self->func->kernel(i, i);
383  olen = self->rsize[i] = 0;
384  }
385  xextend (self, i, len);
386  d = self->rdata[i];
387  self->rsize[i] = olen;
388  for (p = olen; p < len; p++)
389  d[p] = larank_kcache_query (self, self->r2i[p], i);
390  self->rsize[i] = len;
391  }
392  self->rnext[self->rprev[i]] = self->rnext[i];
393  self->rprev[self->rnext[i]] = self->rprev[i];
394  xpurge (self);
395  }
396  self->rprev[i] = -1;
397  self->rnext[i] = self->rnext[-1];
398  self->rnext[self->rprev[i]] = i;
399  self->rprev[self->rnext[i]] = i;
400  return self->rdata[i];
401  }
402 
403 }
404 
405 
406 // Initializing an output class (basically creating a kernel cache for it)
407 void LaRankOutput::initialize (CKernel* kfunc, int64_t cache)
408 {
409  kernel = larank_kcache_create (kfunc);
410  larank_kcache_set_maximum_size (kernel, cache * 1024 * 1024);
411  beta = SG_MALLOC(float32_t, 1);
412  g = SG_MALLOC(float32_t, 1);
413  *beta=0;
414  *g=0;
415  l = 0;
416 }
417 
418 // Destroying an output class (basically destroying the kernel cache)
419 void LaRankOutput::destroy ()
420 {
421  larank_kcache_destroy (kernel);
422  kernel=NULL;
423  SG_FREE(beta);
424  SG_FREE(g);
425  beta=NULL;
426  g=NULL;
427 }
428 
429 // !Important! Computing the score of a given input vector for the actual output
430 float64_t LaRankOutput::computeScore (int32_t x_id)
431 {
432  if (l == 0)
433  return 0;
434  else
435  {
436  float32_t *row = larank_kcache_query_row (kernel, x_id, l);
437  return CMath::dot (beta, row, l);
438  }
439 }
440 
441 // !Important! Computing the gradient of a given input vector for the actual output
442 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
443 {
444  return (yi == ythis ? 1 : 0) - computeScore (xi_id);
445 }
446 
447 // Updating the solution in the actual output
448 void LaRankOutput::update (int32_t x_id, float64_t lambda, float64_t gp)
449 {
450  int32_t *r2i = larank_kcache_r2i (kernel, l);
451  int64_t xr = l + 1;
452  for (int32_t r = 0; r < l; r++)
453  if (r2i[r] == x_id)
454  {
455  xr = r;
456  break;
457  }
458 
459  // updates the cache order and the beta coefficient
460  if (xr < l)
461  {
462  beta[xr]+=lambda;
463  }
464  else
465  {
466  larank_kcache_swap_ri (kernel, l, x_id);
467  g = SG_REALLOC(float32_t, g, l, l+1);
468  beta = SG_REALLOC(float32_t, beta, l, l+1);
469  g[l]=gp;
470  beta[l]=lambda;
471  l++;
472  }
473 
474  // update stored gradients
475  float32_t *row = larank_kcache_query_row (kernel, x_id, l);
476  for (int32_t r = 0; r < l; r++)
477  {
478  float64_t oldg = g[r];
479  g[r]=oldg - lambda * row[r];
480  }
481 }
482 
483 // Linking the cahe of this output to the cache of an other "buddy" output
484 // so that if a requested value is not found in this cache, you can ask your buddy if it has it.
485 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
486 {
487  larank_kcache_set_buddy (bud, kernel);
488 }
489 
490 // Removing useless support vectors (for which beta=0)
491 int32_t LaRankOutput::cleanup ()
492 {
493  int32_t count = 0;
494  std::vector < int32_t >idx;
495  for (int32_t x = 0; x < l; x++)
496  {
497  if ((beta[x] < FLT_EPSILON) && (beta[x] > -FLT_EPSILON))
498  {
499  idx.push_back (x);
500  count++;
501  }
502  }
503  int32_t new_l = l - count;
504  for (int32_t xx = 0; xx < count; xx++)
505  {
506  int32_t i = idx[xx] - xx;
507  for (int32_t r = i; r < (l - 1); r++)
508  {
509  larank_kcache_swap_rr (kernel, r, int64_t(r) + 1);
510  beta[r]=beta[r + 1];
511  g[r]=g[r + 1];
512  }
513  }
514  beta = SG_REALLOC(float32_t, beta, l, new_l+1);
515  g = SG_REALLOC(float32_t, g, l, new_l+1);
516  beta[new_l]=0;
517  g[new_l]=0;
518  l = new_l;
519  return count;
520 }
521 
522 // --- Below are information or "get" functions --- //
523 //
524 float64_t LaRankOutput::getW2 ()
525 {
526  float64_t sum = 0;
527  int32_t *r2i = larank_kcache_r2i (kernel, l + 1);
528  for (int32_t r = 0; r < l; r++)
529  {
530  float32_t *row_r = larank_kcache_query_row (kernel, r2i[r], l);
531  sum += beta[r] * CMath::dot (beta, row_r, l);
532  }
533  return sum;
534 }
535 
536 float64_t LaRankOutput::getKii (int32_t x_id)
537 {
538  return larank_kcache_query (kernel, x_id, x_id);
539 }
540 
541 //
542 float64_t LaRankOutput::getBeta (int32_t x_id)
543 {
544  int32_t *r2i = larank_kcache_r2i (kernel, l);
545  int32_t xr = -1;
546  for (int32_t r = 0; r < l; r++)
547  if (r2i[r] == x_id)
548  {
549  xr = r;
550  break;
551  }
552  return (xr < 0 ? 0 : beta[xr]);
553 }
554 
555 //
556 float64_t LaRankOutput::getGradient (int32_t x_id)
557 {
558  int32_t *r2i = larank_kcache_r2i (kernel, l);
559  int32_t xr = -1;
560  for (int32_t r = 0; r < l; r++)
561  if (r2i[r] == x_id)
562  {
563  xr = r;
564  break;
565  }
566  return (xr < 0 ? 0 : g[xr]);
567 }
568 bool LaRankOutput::isSupportVector (int32_t x_id) const
569 {
570  int32_t *r2i = larank_kcache_r2i (kernel, l);
571  int32_t xr = -1;
572  for (int32_t r = 0; r < l; r++)
573  if (r2i[r] == x_id)
574  {
575  xr = r;
576  break;
577  }
578  return (xr >= 0);
579 }
580 
581 //
582 int32_t LaRankOutput::getSV (float32_t* &sv) const
583 {
584  sv=SG_MALLOC(float32_t, l);
585  int32_t *r2i = larank_kcache_r2i (kernel, l);
586  for (int32_t r = 0; r < l; r++)
587  sv[r]=r2i[r];
588  return l;
589 }
590 
592  nb_seen_examples (0), nb_removed (0),
593  n_pro (0), n_rep (0), n_opt (0),
594  w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
595  batch_mode(true), step(0), max_iteration(1000)
596 {
597 }
598 
601  nb_seen_examples (0), nb_removed (0),
602  n_pro (0), n_rep (0), n_opt (0),
603  w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
604  batch_mode(true), step(0), max_iteration(1000)
605 {
606 }
607 
609 {
610  destroy();
611 }
612 
614 {
615  tau = 0.0001;
616 
620 
622 
623  if (data)
624  {
625  if (data->get_num_vectors() != m_labels->get_num_labels())
626  {
627  SG_ERROR("Numbert of vectors (%d) does not match number of labels (%d)\n",
629  }
630  m_kernel->init(data, data);
631  }
632 
634 
637 
638  int32_t n_it = 1;
639  float64_t gap = DBL_MAX;
640 
641  SG_INFO("Training on %d examples\n", nb_train)
642  while (gap > get_C() && (!CSignal::cancel_computations()) &&
643  n_it < max_iteration) // stopping criteria
644  {
645  float64_t tr_err = 0;
646  int32_t ind = step;
647  for (int32_t i = 0; i < nb_train; i++)
648  {
649  int32_t y=((CMulticlassLabels*) m_labels)->get_label(i);
650  if (add (i, y) != y) // call the add function
651  tr_err++;
652 
653  if (ind && i / ind)
654  {
655  SG_DEBUG("Done: %d %% Train error (online): %f%%\n",
656  (int32_t) (((float64_t) i) / nb_train * 100), (tr_err / ((float64_t) i + 1)) * 100);
657  ind += step;
658  }
659  }
660 
661  SG_DEBUG("End of iteration %d\n", n_it)
662  SG_DEBUG("Train error (online): %f%%\n", (tr_err / nb_train) * 100)
663  gap = computeGap ();
664  SG_ABS_PROGRESS(gap, -CMath::log10(gap), -CMath::log10(DBL_MAX), -CMath::log10(get_C()), 6)
665 
666  if (!batch_mode) // skip stopping criteria if online mode
667  gap = 0;
668  n_it++;
669  }
670  SG_DONE()
671 
672  if (n_it >= max_iteration && gap > get_C())
673  {
674  SG_WARNING("LaRank did not converge after %d iterations.\n",
676  }
677 
678  int32_t num_classes = outputs.size();
679  create_multiclass_svm(num_classes);
680  SG_DEBUG("%d classes\n", num_classes)
681 
682  // Used for saving a model file
683  int32_t i=0;
684  for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
685  {
686  const LaRankOutput* o=&(it->second);
687 
688  larank_kcache_t* k=o->getKernel();
689  int32_t l=o->get_l();
690  float32_t* beta=o->getBetas();
691  int32_t *r2i = larank_kcache_r2i (k, l);
692 
693  ASSERT(l>0)
694  SG_DEBUG("svm[%d] has %d sv, b=%f\n", i, l, 0.0)
695 
696  CSVM* svm=new CSVM(l);
697 
698  for (int32_t j=0; j<l; j++)
699  {
700  svm->set_alpha(j, beta[j]);
701  svm->set_support_vector(j, r2i[j]);
702  }
703 
704  svm->set_bias(0);
705  set_svm(i, svm);
706  i++;
707  }
708  destroy();
709 
710  return true;
711 }
712 
713 // LEARNING FUNCTION: add new patterns and run optimization steps selected with adaptative schedule
714 int32_t CLaRank::add (int32_t x_id, int32_t yi)
715 {
716  ++nb_seen_examples;
717  // create a new output object if this one has never been seen before
718  if (!getOutput (yi))
719  {
720  outputs.insert (std::make_pair (yi, LaRankOutput ()));
721  LaRankOutput *cur = getOutput (yi);
722  cur->initialize (m_kernel, cache);
723  if (outputs.size () == 1)
724  y0 = outputs.begin ()->first;
725  // link the cache of this new output to a buddy
726  if (outputs.size () > 1)
727  {
728  LaRankOutput *out0 = getOutput (y0);
729  cur->set_kernel_buddy (out0->getKernel ());
730  }
731  }
732 
733  LaRankPattern tpattern (x_id, yi);
734  LaRankPattern & pattern = (patterns.isPattern (x_id)) ? patterns.getPattern (x_id) : tpattern;
735 
736  // ProcessNew with the "fresh" pattern
737  float64_t time1 = CTime::get_curtime();
738  process_return_t pro_ret = process (pattern, processNew);
739  float64_t dual_increase = pro_ret.dual_increase;
740  float64_t duration = (CTime::get_curtime() - time1);
741  float64_t coeff = dual_increase / (0.00001 + duration);
742  m_dual += dual_increase;
743  n_pro++;
744  w_pro = 0.05 * coeff + (1 - 0.05) * w_pro;
745 
746  // ProcessOld & Optimize until ready for a new processnew
747  // (Adaptative schedule here)
748  for (;;)
749  {
750  float64_t w_sum = w_pro + w_rep + w_opt;
751  float64_t prop_min = w_sum / 20;
752  if (w_pro < prop_min)
753  w_pro = prop_min;
754  if (w_rep < prop_min)
755  w_rep = prop_min;
756  if (w_opt < prop_min)
757  w_opt = prop_min;
758  w_sum = w_pro + w_rep + w_opt;
759  float64_t r = CMath::random(0.0, w_sum);
760  if (r <= w_pro)
761  {
762  break;
763  }
764  else if ((r > w_pro) && (r <= w_pro + w_rep)) // ProcessOld here
765  {
766  float64_t ltime1 = CTime::get_curtime ();
767  float64_t ldual_increase = reprocess ();
768  float64_t lduration = (CTime::get_curtime () - ltime1);
769  float64_t lcoeff = ldual_increase / (0.00001 + lduration);
770  m_dual += ldual_increase;
771  n_rep++;
772  w_rep = 0.05 * lcoeff + (1 - 0.05) * w_rep;
773  }
774  else // Optimize here
775  {
776  float64_t ltime1 = CTime::get_curtime ();
777  float64_t ldual_increase = optimize ();
778  float64_t lduration = (CTime::get_curtime () - ltime1);
779  float64_t lcoeff = ldual_increase / (0.00001 + lduration);
780  m_dual += ldual_increase;
781  n_opt++;
782  w_opt = 0.05 * lcoeff + (1 - 0.05) * w_opt;
783  }
784  }
785  if (nb_seen_examples % 100 == 0) // Cleanup useless Support Vectors/Patterns sometimes
786  nb_removed += cleanup ();
787  return pro_ret.ypred;
788 }
789 
790 // PREDICTION FUNCTION: main function in la_rank_classify
791 int32_t CLaRank::predict (int32_t x_id)
792 {
793  int32_t res = -1;
794  float64_t score_max = -DBL_MAX;
795  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
796  {
797  float64_t score = it->second.computeScore (x_id);
798  if (score > score_max)
799  {
800  score_max = score;
801  res = it->first;
802  }
803  }
804  return res;
805 }
806 
808 {
809  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
810  it->second.destroy ();
811  outputs.clear();
812 }
813 
814 
815 // Compute Duality gap (costly but used in stopping criteria in batch mode)
817 {
818  float64_t sum_sl = 0;
819  float64_t sum_bi = 0;
820  for (uint32_t i = 0; i < patterns.maxcount (); ++i)
821  {
822  const LaRankPattern & p = patterns[i];
823  if (!p.exists ())
824  continue;
825  LaRankOutput *out = getOutput (p.y);
826  if (!out)
827  continue;
828  sum_bi += out->getBeta (p.x_id);
829  float64_t gi = out->computeGradient (p.x_id, p.y, p.y);
830  float64_t gmin = DBL_MAX;
831  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
832  {
833  if (it->first != p.y && it->second.isSupportVector (p.x_id))
834  {
835  float64_t g =
836  it->second.computeGradient (p.x_id, p.y, it->first);
837  if (g < gmin)
838  gmin = g;
839  }
840  }
841  sum_sl += CMath::max (0.0, gi - gmin);
842  }
843  return CMath::max (0.0, computeW2 () + get_C() * sum_sl - sum_bi);
844 }
845 
846 // Nuber of classes so far
847 uint32_t CLaRank::getNumOutputs () const
848 {
849  return outputs.size ();
850 }
851 
852 // Set max number of iterations before training is stopped
853 void CLaRank::set_max_iteration(int32_t max_iter)
854 {
855  REQUIRE(max_iter > 0,
856  "Max iteration (given: %d) must be positive.\n",
857  max_iter);
858  max_iteration = max_iter;
859 }
860 
861 // Number of Support Vectors
862 int32_t CLaRank::getNSV ()
863 {
864  int32_t res = 0;
865  for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
866  {
867  float32_t* sv=NULL;
868  res += it->second.getSV (sv);
869  SG_FREE(sv);
870  }
871  return res;
872 }
873 
874 // Norm of the parameters vector
876 {
877  float64_t res = 0;
878  for (uint32_t i = 0; i < patterns.maxcount (); ++i)
879  {
880  const LaRankPattern & p = patterns[i];
881  if (!p.exists ())
882  continue;
883  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
884  if (it->second.getBeta (p.x_id))
885  res += it->second.getBeta (p.x_id) * it->second.computeScore (p.x_id);
886  }
887  return res;
888 }
889 
890 // Compute Dual objective value
892 {
893  float64_t res = 0;
894  for (uint32_t i = 0; i < patterns.maxcount (); ++i)
895  {
896  const LaRankPattern & p = patterns[i];
897  if (!p.exists ())
898  continue;
899  LaRankOutput *out = getOutput (p.y);
900  if (!out)
901  continue;
902  res += out->getBeta (p.x_id);
903  }
904  return res - computeW2 () / 2;
905 }
906 
907 LaRankOutput *CLaRank::getOutput (int32_t index)
908 {
909  outputhash_t::iterator it = outputs.find (index);
910  return it == outputs.end ()? NULL : &it->second;
911 }
912 
913 // IMPORTANT Main SMO optimization step
914 CLaRank::process_return_t CLaRank::process (const LaRankPattern & pattern, process_type ptype)
915 {
916  process_return_t pro_ret = process_return_t (0, 0);
917 
918  /*
919  ** compute gradient and sort
920  */
921  std::vector < outputgradient_t > outputgradients(getNumOutputs ());
922  std::vector < outputgradient_t > outputscores(getNumOutputs ());
923 
924  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
925  {
926  if (ptype != processOptimize
927  || it->second.isSupportVector (pattern.x_id))
928  {
929  float64_t g =
930  it->second.computeGradient (pattern.x_id, pattern.y, it->first);
931  outputgradients.push_back (outputgradient_t (it->first, g));
932  if (it->first == pattern.y)
933  outputscores.push_back (outputgradient_t (it->first, (1 - g)));
934  else
935  outputscores.push_back (outputgradient_t (it->first, -g));
936  }
937  }
938 
939  std::sort (outputgradients.begin (), outputgradients.end ());
940 
941  /*
942  ** determine the prediction
943  */
944  std::sort (outputscores.begin (), outputscores.end ());
945  pro_ret.ypred = outputscores[0].output;
946 
947  /*
948  ** Find yp (1st part of the pair)
949  */
950  outputgradient_t ygp;
951  LaRankOutput *outp = NULL;
952  uint32_t p;
953  for (p = 0; p < outputgradients.size (); ++p)
954  {
955  outputgradient_t & current = outputgradients[p];
956  LaRankOutput *output = getOutput (current.output);
957  bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
958  bool goodclass = current.output == pattern.y;
959  if ((!support && goodclass) ||
960  (support && output->getBeta (pattern.x_id) < (goodclass ? get_C() : 0)))
961  {
962  ygp = current;
963  outp = output;
964  break;
965  }
966  }
967  if (p == outputgradients.size ())
968  return pro_ret;
969 
970  /*
971  ** Find ym (2nd part of the pair)
972  */
973  outputgradient_t ygm;
974  LaRankOutput *outm = NULL;
975  int32_t m;
976  for (m = outputgradients.size () - 1; m >= 0; --m)
977  {
978  outputgradient_t & current = outputgradients[m];
979  LaRankOutput *output = getOutput (current.output);
980  bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
981  bool goodclass = current.output == pattern.y;
982  if (!goodclass || (support && output->getBeta (pattern.x_id) > 0))
983  {
984  ygm = current;
985  outm = output;
986  break;
987  }
988  }
989  if (m < 0)
990  return pro_ret;
991 
992  /*
993  ** Throw or Insert pattern
994  */
995  if ((ygp.gradient - ygm.gradient) < tau)
996  return pro_ret;
997  if (ptype == processNew)
998  patterns.insert (pattern);
999 
1000  /*
1001  ** compute lambda and clip it
1002  */
1003  float64_t kii = outp->getKii (pattern.x_id);
1004  float64_t lambda = (ygp.gradient - ygm.gradient) / (2 * kii);
1005  if (ptype == processOptimize || outp->isSupportVector (pattern.x_id))
1006  {
1007  float64_t beta = outp->getBeta (pattern.x_id);
1008  if (ygp.output == pattern.y)
1009  lambda = CMath::min (lambda, get_C() - beta);
1010  else
1011  lambda = CMath::min (lambda, fabs (beta));
1012  }
1013  else
1014  lambda = CMath::min (lambda, get_C());
1015 
1016  /*
1017  ** update the solution
1018  */
1019  outp->update (pattern.x_id, lambda, ygp.gradient);
1020  outm->update (pattern.x_id, -lambda, ygm.gradient);
1021 
1022  pro_ret.dual_increase = lambda * ((ygp.gradient - ygm.gradient) - lambda * kii);
1023  return pro_ret;
1024 }
1025 
1026 // ProcessOld
1027 float64_t CLaRank::reprocess ()
1028 {
1029  if (patterns.size ())
1030  {
1031  for (int32_t n = 0; n < 10; ++n)
1032  {
1033  process_return_t pro_ret = process (patterns.sample (), processOld);
1034  if (pro_ret.dual_increase)
1035  return pro_ret.dual_increase;
1036  }
1037  }
1038  return 0;
1039 }
1040 
1041 // Optimize
1042 float64_t CLaRank::optimize ()
1043 {
1044  float64_t dual_increase = 0;
1045  if (patterns.size ())
1046  {
1047  for (int32_t n = 0; n < 10; ++n)
1048  {
1049  process_return_t pro_ret =
1050  process (patterns.sample(), processOptimize);
1051  dual_increase += pro_ret.dual_increase;
1052  }
1053  }
1054  return dual_increase;
1055 }
1056 
1057 // remove patterns and return the number of patterns that were removed
1058 uint32_t CLaRank::cleanup ()
1059 {
1060  /*
1061  for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
1062  it->second.cleanup ();
1063 
1064  uint32_t res = 0;
1065  for (uint32_t i = 0; i < patterns.size (); ++i)
1066  {
1067  LaRankPattern & p = patterns[i];
1068  if (p.exists () && !outputs[p.y].isSupportVector (p.x_id))
1069  {
1070  patterns.remove (i);
1071  ++res;
1072  }
1073  }
1074  return res;
1075  */
1076  return 0;
1077 }
virtual bool init(CFeatures *lhs, CFeatures *rhs)
Definition: Kernel.cpp:96
static void xtruncate(larank_kcache_t *self, int32_t k, int32_t nlen)
Definition: LaRank.cpp:92
static float32_t * larank_kcache_query_row(larank_kcache_t *self, int32_t i, int32_t len)
Definition: LaRank.cpp:363
#define SG_INFO(...)
Definition: SGIO.h:117
#define SG_DONE()
Definition: SGIO.h:156
bool batch_mode
whether to use online learning or batch training
Definition: LaRank.h:508
virtual void destroy()
Definition: LaRank.cpp:807
int32_t getNSV()
Definition: LaRank.cpp:862
virtual ELabelType get_label_type() const =0
static void larank_kcache_set_maximum_size(larank_kcache_t *self, int64_t entries)
Definition: LaRank.cpp:132
The class Labels models labels, i.e. class assignments of objects.
Definition: Labels.h:43
int64_t cache
cache
Definition: LaRank.h:506
bool train_machine(CFeatures *data)
Definition: LaRank.cpp:613
virtual int32_t get_num_labels() const =0
static void xswap(larank_kcache_t *self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
Definition: LaRank.cpp:229
float64_t tau
tau
Definition: LaRank.h:501
multi-class labels 0,1,...
Definition: LabelTypes.h:20
static float64_t log10(float64_t v)
Definition: Math.h:892
int32_t max_iteration
Max number of iterations before training is stopped.
Definition: LaRank.h:514
void(* update)(float *foo, float bar)
Definition: JLCoverTree.h:533
virtual int32_t get_num_vectors() const =0
CLabels * m_labels
Definition: Machine.h:365
#define SG_ERROR(...)
Definition: SGIO.h:128
#define REQUIRE(x,...)
Definition: SGIO.h:205
static float64_t larank_kcache_query(larank_kcache_t *self, int32_t i, int32_t j)
Definition: LaRank.cpp:331
virtual int32_t add(int32_t x_id, int32_t yi)
Definition: LaRank.cpp:714
virtual int32_t get_num_vec_lhs()
virtual float64_t computeGap()
Definition: LaRank.cpp:816
static uint64_t random()
Definition: Math.h:1014
static void larank_kcache_set_buddy(larank_kcache_t *self, larank_kcache_t *buddy)
Definition: LaRank.cpp:340
static float64_t get_curtime()
Definition: Time.h:116
float64_t computeW2()
Definition: LaRank.cpp:875
int32_t nb_train
nb train
Definition: LaRank.h:504
static void xextend(larank_kcache_t *self, int32_t k, int32_t nlen)
Definition: LaRank.cpp:210
Multiclass Labels for multi-class classification.
static float64_t xquery(larank_kcache_t *self, int32_t i, int32_t j)
Definition: LaRank.cpp:303
static void larank_kcache_swap_rr(larank_kcache_t *self, int32_t r1, int32_t r2)
Definition: LaRank.cpp:291
#define ASSERT(x)
Definition: SGIO.h:200
float64_t getDual()
Definition: LaRank.cpp:891
class MultiClassSVM
Definition: MulticlassSVM.h:28
void set_bias(float64_t bias)
static void clear_cancel()
Definition: Signal.cpp:126
virtual ~CLaRank()
Definition: LaRank.cpp:608
double float64_t
Definition: common.h:60
bool set_alpha(int32_t idx, float64_t val)
static T max(T a, T b)
Definition: Math.h:164
bool set_support_vector(int32_t idx, int32_t val)
static int32_t * larank_kcache_r2i(larank_kcache_t *self, int32_t n)
Definition: LaRank.cpp:204
static float64_t dot(const bool *v1, const bool *v2, int32_t n)
Compute dot product between v1 and v2 (blas optimized)
Definition: Math.h:622
virtual uint32_t getNumOutputs() const
Definition: LaRank.cpp:847
static bool cancel_computations()
Definition: Signal.h:111
virtual int32_t get_num_vec_rhs()
#define SG_ABS_PROGRESS(...)
Definition: SGIO.h:151
static void larank_kcache_destroy(larank_kcache_t *self)
Definition: LaRank.cpp:140
float float32_t
Definition: common.h:59
static void xminsize(larank_kcache_t *self, int32_t n)
Definition: LaRank.cpp:173
#define SG_DEBUG(...)
Definition: SGIO.h:106
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
T sum(const Container< T > &a, bool no_diag=false)
static void larank_kcache_swap_ri(larank_kcache_t *self, int32_t r1, int32_t i2)
Definition: LaRank.cpp:297
static larank_kcache_t * larank_kcache_create(CKernel *kernelfunc)
Definition: LaRank.cpp:72
The class Features is the base class of all feature objects.
Definition: Features.h:68
bool create_multiclass_svm(int32_t num_classes)
static T min(T a, T b)
Definition: Math.h:153
static void xpurge(larank_kcache_t *self)
Definition: LaRank.cpp:118
A generic Support Vector Machine Interface.
Definition: SVM.h:49
virtual int32_t predict(int32_t x_id)
Definition: LaRank.cpp:791
The Kernel base class.
int32_t get_cache_size()
#define SG_WARNING(...)
Definition: SGIO.h:127
multiclass one vs rest strategy used to train generic multiclass machines for K-class problems with b...
bool set_svm(int32_t num, CSVM *svm)
int32_t step
progess output
Definition: LaRank.h:511
void set_max_iteration(int32_t max_iter)
Definition: LaRank.cpp:853

SHOGUN Machine Learning Toolbox - Documentation