SHOGUN  6.1.3
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/base/progress.h>
50 #include <shogun/lib/config.h>
51 
52 #include <vector>
53 #include <algorithm>
54 #include <ctime>
55 #include <algorithm>
56 #ifndef _MSC_VER
57 #include <sys/time.h>
58 #endif
59 
60 #include <shogun/io/SGIO.h>
61 #include <shogun/lib/Signal.h>
62 #include <shogun/lib/Time.h>
67 #include <shogun/kernel/Kernel.h>
69 
70 using namespace shogun;
71 
72 namespace shogun
73 {
74  static larank_kcache_t* larank_kcache_create (CKernel* kernelfunc)
75  {
76  larank_kcache_t *self;
77  self = SG_CALLOC (larank_kcache_t, 1);
78  self->l = 0;
79  self->maxrowlen = 0;
80  self->func = kernelfunc;
81  self->prevbuddy = self;
82  self->nextbuddy = self;
83  self->cursize = sizeof (larank_kcache_t);
84  self->maxsize = 256 * 1024 * 1024;
85  self->qprev = SG_MALLOC(int32_t, 1);
86  self->qnext = SG_MALLOC(int32_t, 1);
87  self->rnext = self->qnext + 1;
88  self->rprev = self->qprev + 1;
89  self->rprev[-1] = -1;
90  self->rnext[-1] = -1;
91  return self;
92  }
93 
94  static void xtruncate (larank_kcache_t * self, int32_t k, int32_t nlen)
95  {
96  int32_t olen = self->rsize[k];
97  if (nlen < olen)
98  {
99  float32_t *ndata;
100  float32_t *odata = self->rdata[k];
101  if (nlen > 0)
102  {
103  ndata = SG_MALLOC(float32_t, nlen);
104  sg_memcpy (ndata, odata, nlen * sizeof (float32_t));
105  }
106  else
107  {
108  ndata = 0;
109  self->rnext[self->rprev[k]] = self->rnext[k];
110  self->rprev[self->rnext[k]] = self->rprev[k];
111  self->rnext[k] = self->rprev[k] = k;
112  }
113  SG_FREE (odata);
114  self->rdata[k] = ndata;
115  self->rsize[k] = nlen;
116  self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
117  }
118  }
119 
120  static void xpurge (larank_kcache_t * self)
121  {
122  if (self->cursize > self->maxsize)
123  {
124  int32_t k = self->rprev[-1];
125  while (self->cursize > self->maxsize && k != self->rnext[-1])
126  {
127  int32_t pk = self->rprev[k];
128  xtruncate (self, k, 0);
129  k = pk;
130  }
131  }
132  }
133 
134  static void larank_kcache_set_maximum_size (larank_kcache_t * self, int64_t entries)
135  {
136  ASSERT (self)
137  ASSERT (entries > 0)
138  self->maxsize = entries;
139  xpurge (self);
140  }
141 
142  static void larank_kcache_destroy (larank_kcache_t * self)
143  {
144  if (self)
145  {
146  int32_t i;
147  larank_kcache_t *nb = self->nextbuddy;
148  larank_kcache_t *pb = self->prevbuddy;
149  pb->nextbuddy = nb;
150  nb->prevbuddy = pb;
151  /* delete */
152  if (self->i2r)
153  SG_FREE (self->i2r);
154  if (self->r2i)
155  SG_FREE (self->r2i);
156  if (self->rdata)
157  for (i = 0; i < self->l; i++)
158  if (self->rdata[i])
159  SG_FREE (self->rdata[i]);
160  if (self->rdata)
161  SG_FREE (self->rdata);
162  if (self->rsize)
163  SG_FREE (self->rsize);
164  if (self->rdiag)
165  SG_FREE (self->rdiag);
166  if (self->qnext)
167  SG_FREE (self->qnext);
168  if (self->qprev)
169  SG_FREE (self->qprev);
170  memset (self, 0, sizeof (larank_kcache_t));
171  SG_FREE (self);
172  }
173  }
174 
175  static void xminsize (larank_kcache_t * self, int32_t n)
176  {
177  int32_t ol = self->l;
178  if (n > ol)
179  {
180  int32_t i;
181  int32_t nl = CMath::max (256, ol);
182  while (nl < n)
183  nl = nl + nl;
184  self->i2r = SG_REALLOC (int32_t, self->i2r, self->l, nl);
185  self->r2i = SG_REALLOC (int32_t, self->r2i, self->l, nl);
186  self->rsize = SG_REALLOC (int32_t, self->rsize, self->l, nl);
187  self->qnext = SG_REALLOC (int32_t, self->qnext, 1+self->l, (1 + nl));
188  self->qprev = SG_REALLOC (int32_t, self->qprev, 1+self->l, (1 + nl));
189  self->rdiag = SG_REALLOC (float32_t, self->rdiag, self->l, nl);
190  self->rdata = SG_REALLOC (float32_t*, self->rdata, self->l, nl);
191  self->rnext = self->qnext + 1;
192  self->rprev = self->qprev + 1;
193  for (i = ol; i < nl; i++)
194  {
195  self->i2r[i] = i;
196  self->r2i[i] = i;
197  self->rsize[i] = -1;
198  self->rnext[i] = i;
199  self->rprev[i] = i;
200  self->rdata[i] = 0;
201  }
202  self->l = nl;
203  }
204  }
205 
206  static int32_t* larank_kcache_r2i (larank_kcache_t * self, int32_t n)
207  {
208  xminsize (self, n);
209  return self->r2i;
210  }
211 
212  static void xextend (larank_kcache_t * self, int32_t k, int32_t nlen)
213  {
214  int32_t olen = self->rsize[k];
215  if (nlen > olen)
216  {
217  float32_t *ndata = SG_MALLOC(float32_t, nlen);
218  if (olen > 0)
219  {
220  float32_t *odata = self->rdata[k];
221  sg_memcpy (ndata, odata, olen * sizeof (float32_t));
222  SG_FREE (odata);
223  }
224  self->rdata[k] = ndata;
225  self->rsize[k] = nlen;
226  self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
227  self->maxrowlen = CMath::max (self->maxrowlen, nlen);
228  }
229  }
230 
231  static void xswap (larank_kcache_t * self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
232  {
233  /* swap row data */
234  if (r1 < self->maxrowlen || r2 < self->maxrowlen)
235  {
236  int32_t mrl = 0;
237  int32_t k = self->rnext[-1];
238  while (k >= 0)
239  {
240  int32_t nk = self->rnext[k];
241  int32_t n = self->rsize[k];
242  int32_t rr = self->i2r[k];
243  float32_t *d = self->rdata[k];
244  if (r1 < n)
245  {
246  if (r2 < n)
247  {
248  float32_t t1 = d[r1];
249  float32_t t2 = d[r2];
250  d[r1] = t2;
251  d[r2] = t1;
252  }
253  else if (rr == r2)
254  {
255  d[r1] = self->rdiag[k];
256  }
257  else
258  {
259  int32_t arsize = self->rsize[i2];
260  if (rr < arsize && rr != r1)
261  d[r1] = self->rdata[i2][rr];
262  else
263  xtruncate (self, k, r1);
264  }
265  }
266  else if (r2 < n)
267  {
268  if (rr == r1)
269  {
270  d[r2] = self->rdiag[k];
271  }
272  else
273  {
274  int32_t arsize = self->rsize[i1];
275  if (rr < arsize && rr != r2)
276  d[r2] = self->rdata[i1][rr];
277  else
278  xtruncate (self, k, r2);
279  }
280  }
281  mrl = CMath::max (mrl, self->rsize[k]);
282  k = nk;
283  }
284  self->maxrowlen = mrl;
285  }
286  /* swap r2i and i2r */
287  self->r2i[r1] = i2;
288  self->r2i[r2] = i1;
289  self->i2r[i1] = r2;
290  self->i2r[i2] = r1;
291  }
292 
293  static void larank_kcache_swap_rr (larank_kcache_t * self, int32_t r1, int32_t r2)
294  {
295  xminsize (self, 1 + CMath::max(r1, r2));
296  xswap (self, self->r2i[r1], self->r2i[r2], r1, r2);
297  }
298 
299  static void larank_kcache_swap_ri (larank_kcache_t * self, int32_t r1, int32_t i2)
300  {
301  xminsize (self, 1 + CMath::max (r1, i2));
302  xswap (self, self->r2i[r1], i2, r1, self->i2r[i2]);
303  }
304 
305  static float64_t xquery (larank_kcache_t * self, int32_t i, int32_t j)
306  {
307  /* search buddies */
308  larank_kcache_t *cache = self->nextbuddy;
309  do
310  {
311  int32_t l = cache->l;
312  if (i < l && j < l)
313  {
314  int32_t s = cache->rsize[i];
315  int32_t p = cache->i2r[j];
316  if (p < s)
317  return cache->rdata[i][p];
318  if (i == j && s >= 0)
319  return cache->rdiag[i];
320  p = cache->i2r[i];
321  s = cache->rsize[j];
322  if (p < s)
323  return cache->rdata[j][p];
324  }
325  cache = cache->nextbuddy;
326  }
327  while (cache != self);
328  /* compute */
329  return self->func->kernel(i, j);
330  }
331 
332 
333  static float64_t larank_kcache_query (larank_kcache_t * self, int32_t i, int32_t j)
334  {
335  ASSERT (self)
336  ASSERT (i >= 0)
337  ASSERT (j >= 0)
338  return xquery (self, i, j);
339  }
340 
341 
342  static void larank_kcache_set_buddy (larank_kcache_t * self, larank_kcache_t * buddy)
343  {
344  larank_kcache_t *p = self;
345  larank_kcache_t *selflast = self->prevbuddy;
346  larank_kcache_t *buddylast = buddy->prevbuddy;
347  /* check functions are identical */
348  ASSERT (self->func == buddy->func)
349  /* make sure we are not already buddies */
350  do
351  {
352  if (p == buddy)
353  return;
354  p = p->nextbuddy;
355  }
356  while (p != self);
357  /* link */
358  selflast->nextbuddy = buddy;
359  buddy->prevbuddy = selflast;
360  buddylast->nextbuddy = self;
361  self->prevbuddy = buddylast;
362  }
363 
364 
365  static float32_t* larank_kcache_query_row (larank_kcache_t * self, int32_t i, int32_t len)
366  {
367  ASSERT (i >= 0)
368  if (i < self->l && len <= self->rsize[i])
369  {
370  self->rnext[self->rprev[i]] = self->rnext[i];
371  self->rprev[self->rnext[i]] = self->rprev[i];
372  }
373  else
374  {
375  int32_t olen, p;
376  float32_t *d;
377  if (i >= self->l || len >= self->l)
378  xminsize (self, CMath::max (1 + i, len));
379  olen = self->rsize[i];
380  if (olen < len)
381  {
382  if (olen < 0)
383  {
384  self->rdiag[i] = self->func->kernel(i, i);
385  olen = self->rsize[i] = 0;
386  }
387  xextend (self, i, len);
388  d = self->rdata[i];
389  self->rsize[i] = olen;
390  for (p = olen; p < len; p++)
391  d[p] = larank_kcache_query (self, self->r2i[p], i);
392  self->rsize[i] = len;
393  }
394  self->rnext[self->rprev[i]] = self->rnext[i];
395  self->rprev[self->rnext[i]] = self->rprev[i];
396  xpurge (self);
397  }
398  self->rprev[i] = -1;
399  self->rnext[i] = self->rnext[-1];
400  self->rnext[self->rprev[i]] = i;
401  self->rprev[self->rnext[i]] = i;
402  return self->rdata[i];
403  }
404 
405 }
406 
407 
408 // Initializing an output class (basically creating a kernel cache for it)
409 void LaRankOutput::initialize (CKernel* kfunc, int64_t cache)
410 {
411  kernel = larank_kcache_create (kfunc);
412  larank_kcache_set_maximum_size (kernel, cache * 1024 * 1024);
413  m_beta = SGVector<float32_t>(1);
414  g = SG_MALLOC(float32_t, 1);
415  *g=0;
416  l = 0;
417 }
418 
419 // Destroying an output class (basically destroying the kernel cache)
420 void LaRankOutput::destroy ()
421 {
422  larank_kcache_destroy (kernel);
423  kernel=NULL;
424  SG_FREE(g);
425  g=NULL;
426 }
427 
428 // !Important! Computing the score of a given input vector for the actual output
429 float64_t LaRankOutput::computeScore (int32_t x_id)
430 {
431  if (l == 0)
432  return 0;
433  else
434  {
435  SGVector<float32_t> row(larank_kcache_query_row (kernel, x_id, l), l, false);
436  return linalg::dot (m_beta, row);
437  }
438 }
439 
440 // !Important! Computing the gradient of a given input vector for the actual output
441 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
442 {
443  return (yi == ythis ? 1 : 0) - computeScore (xi_id);
444 }
445 
446 // Updating the solution in the actual output
447 void LaRankOutput::update (int32_t x_id, float64_t lambda, float64_t gp)
448 {
449  int32_t *r2i = larank_kcache_r2i (kernel, l);
450  int64_t xr = l + 1;
451  for (int32_t r = 0; r < l; r++)
452  if (r2i[r] == x_id)
453  {
454  xr = r;
455  break;
456  }
457 
458  // updates the cache order and the beta coefficient
459  if (xr < l)
460  {
461  m_beta[xr]+=lambda;
462  }
463  else
464  {
465  larank_kcache_swap_ri (kernel, l, x_id);
466  g = SG_REALLOC(float32_t, g, l, l+1);
467  m_beta.resize_vector(l+1);
468  g[l]=gp;
469  m_beta[l]=lambda;
470  l++;
471  }
472 
473  // update stored gradients
474  float32_t *row = larank_kcache_query_row (kernel, x_id, l);
475  for (int32_t r = 0; r < l; r++)
476  {
477  float64_t oldg = g[r];
478  g[r]=oldg - lambda * row[r];
479  }
480 }
481 
482 // Linking the cahe of this output to the cache of an other "buddy" output
483 // so that if a requested value is not found in this cache, you can ask your buddy if it has it.
484 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
485 {
486  larank_kcache_set_buddy (bud, kernel);
487 }
488 
489 // Removing useless support vectors (for which beta=0)
490 int32_t LaRankOutput::cleanup ()
491 {
492  int32_t count = 0;
493  std::vector < int32_t >idx;
494  for (int32_t x = 0; x < l; x++)
495  {
496  if ((m_beta[x] < FLT_EPSILON) && (m_beta[x] > -FLT_EPSILON))
497  {
498  idx.push_back (x);
499  count++;
500  }
501  }
502  int32_t new_l = l - count;
503  for (int32_t xx = 0; xx < count; xx++)
504  {
505  int32_t i = idx[xx] - xx;
506  for (int32_t r = i; r < (l - 1); r++)
507  {
508  larank_kcache_swap_rr (kernel, r, int64_t(r) + 1);
509  m_beta[r]=m_beta[r + 1];
510  g[r]=g[r + 1];
511  }
512  }
513  m_beta.resize_vector(new_l+1);
514  g = SG_REALLOC(float32_t, g, l, new_l+1);
515  m_beta[new_l]=0;
516  g[new_l]=0;
517  l = new_l;
518  return count;
519 }
520 
521 // --- Below are information or "get" functions --- //
522 //
523 float64_t LaRankOutput::getW2 ()
524 {
525  float64_t sum = 0;
526  int32_t *r2i = larank_kcache_r2i (kernel, l + 1);
527  for (int32_t r = 0; r < l; r++)
528  {
529  SGVector<float32_t> row_r(larank_kcache_query_row (kernel, r2i[r], l), l, false);
530  sum += m_beta[r] * linalg::dot (m_beta, row_r);
531  }
532  return sum;
533 }
534 
535 float64_t LaRankOutput::getKii (int32_t x_id)
536 {
537  return larank_kcache_query (kernel, x_id, x_id);
538 }
539 
540 //
541 float64_t LaRankOutput::getBeta (int32_t x_id)
542 {
543  int32_t *r2i = larank_kcache_r2i (kernel, l);
544  int32_t xr = -1;
545  for (int32_t r = 0; r < l; r++)
546  if (r2i[r] == x_id)
547  {
548  xr = r;
549  break;
550  }
551  return (xr < 0 ? 0 : m_beta[xr]);
552 }
553 
554 //
555 float64_t LaRankOutput::getGradient (int32_t x_id)
556 {
557  int32_t *r2i = larank_kcache_r2i (kernel, l);
558  int32_t xr = -1;
559  for (int32_t r = 0; r < l; r++)
560  if (r2i[r] == x_id)
561  {
562  xr = r;
563  break;
564  }
565  return (xr < 0 ? 0 : g[xr]);
566 }
567 bool LaRankOutput::isSupportVector (int32_t x_id) const
568 {
569  int32_t *r2i = larank_kcache_r2i (kernel, l);
570  int32_t xr = -1;
571  for (int32_t r = 0; r < l; r++)
572  if (r2i[r] == x_id)
573  {
574  xr = r;
575  break;
576  }
577  return (xr >= 0);
578 }
579 
580 //
581 int32_t LaRankOutput::getSV (float32_t* &sv) const
582 {
583  sv=SG_MALLOC(float32_t, l);
584  int32_t *r2i = larank_kcache_r2i (kernel, l);
585  for (int32_t r = 0; r < l; r++)
586  sv[r]=r2i[r];
587  return l;
588 }
589 
591  nb_seen_examples (0), nb_removed (0),
592  n_pro (0), n_rep (0), n_opt (0),
593  w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
594  batch_mode(true), step(0), max_iteration(1000)
595 {
596 }
597 
600  nb_seen_examples (0), nb_removed (0),
601  n_pro (0), n_rep (0), n_opt (0),
602  w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
603  batch_mode(true), step(0), max_iteration(1000)
604 {
605 }
606 
608 {
609  destroy();
610 }
611 
613 {
614  tau = 0.0001;
615 
619 
620  if (data)
621  {
622  if (data->get_num_vectors() != m_labels->get_num_labels())
623  {
624  SG_ERROR("Numbert of vectors (%d) does not match number of labels (%d)\n",
626  }
627  m_kernel->init(data, data);
628  }
629 
631 
634 
635  int32_t n_it = 1;
636  float64_t gap = DBL_MAX;
637 
638  auto pb = progress(range(0, 10), *this->io);
639  SG_INFO("Training on %d examples\n", nb_train)
640  while (gap > get_C() && (!cancel_computation()) &&
641  n_it < max_iteration) // stopping criteria
642  {
643  float64_t tr_err = 0;
644  int32_t ind = step;
645  for (int32_t i = 0; i < nb_train; i++)
646  {
647  int32_t y=((CMulticlassLabels*) m_labels)->get_label(i);
648  if (add (i, y) != y) // call the add function
649  tr_err++;
650 
651  if (ind && i / ind)
652  {
653  SG_DEBUG("Done: %d %% Train error (online): %f%%\n",
654  (int32_t) (((float64_t) i) / nb_train * 100), (tr_err / ((float64_t) i + 1)) * 100);
655  ind += step;
656  }
657  }
658 
659  SG_DEBUG("End of iteration %d\n", n_it)
660  SG_DEBUG("Train error (online): %f%%\n", (tr_err / nb_train) * 100)
661  gap = computeGap ();
662  pb.print_absolute(
663  gap, -CMath::log10(gap), -CMath::log10(DBL_MAX),
664  -CMath::log10(get_C()));
665 
666  if (!batch_mode) // skip stopping criteria if online mode
667  gap = 0;
668  n_it++;
669  }
670  pb.complete_absolute();
671 
672  if (n_it >= max_iteration && gap > get_C())
673  {
674  SG_WARNING(
675  "LaRank did not converge after %d iterations.\n", max_iteration)
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  SGVector<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:97
static void xtruncate(larank_kcache_t *self, int32_t k, int32_t nlen)
Definition: LaRank.cpp:94
static float32_t * larank_kcache_query_row(larank_kcache_t *self, int32_t i, int32_t len)
Definition: LaRank.cpp:365
#define SG_INFO(...)
Definition: SGIO.h:117
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 T max(T a, T b)
Definition: Math.h:149
static void larank_kcache_set_maximum_size(larank_kcache_t *self, int64_t entries)
Definition: LaRank.cpp:134
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:612
virtual int32_t get_num_labels() const =0
PRange< T > progress(Range< T > range, const SGIO &io, std::string prefix="PROGRESS: ", SG_PRG_MODE mode=UTF8, std::function< bool()> condition=[](){return true;})
Definition: progress.h:712
static void xswap(larank_kcache_t *self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
Definition: LaRank.cpp:231
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:693
int32_t max_iteration
Max number of iterations before training is stopped.
Definition: LaRank.h:514
virtual int32_t get_num_vectors() const =0
CLabels * m_labels
Definition: Machine.h:436
#define SG_ERROR(...)
Definition: SGIO.h:128
#define REQUIRE(x,...)
Definition: SGIO.h:181
T dot(const SGVector< T > &a, const SGVector< T > &b)
static float64_t larank_kcache_query(larank_kcache_t *self, int32_t i, int32_t j)
Definition: LaRank.cpp:333
virtual int32_t add(int32_t x_id, int32_t yi)
Definition: LaRank.cpp:714
Range< T > range(T rend)
Definition: range.h:136
virtual int32_t get_num_vec_lhs()
virtual float64_t computeGap()
Definition: LaRank.cpp:816
static uint64_t random()
Definition: Math.h:811
static void larank_kcache_set_buddy(larank_kcache_t *self, larank_kcache_t *buddy)
Definition: LaRank.cpp:342
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:212
Multiclass Labels for multi-class classification.
static float64_t xquery(larank_kcache_t *self, int32_t i, int32_t j)
Definition: LaRank.cpp:305
static void larank_kcache_swap_rr(larank_kcache_t *self, int32_t r1, int32_t r2)
Definition: LaRank.cpp:293
#define ASSERT(x)
Definition: SGIO.h:176
float64_t getDual()
Definition: LaRank.cpp:891
class MultiClassSVM
Definition: MulticlassSVM.h:28
void set_bias(float64_t bias)
virtual ~CLaRank()
Definition: LaRank.cpp:607
double float64_t
Definition: common.h:60
bool set_alpha(int32_t idx, float64_t val)
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:206
virtual uint32_t getNumOutputs() const
Definition: LaRank.cpp:847
virtual int32_t get_num_vec_rhs()
static void larank_kcache_destroy(larank_kcache_t *self)
Definition: LaRank.cpp:142
float float32_t
Definition: common.h:59
SG_FORCED_INLINE bool cancel_computation() const
Definition: Machine.h:319
static void xminsize(larank_kcache_t *self, int32_t n)
Definition: LaRank.cpp:175
#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:299
static larank_kcache_t * larank_kcache_create(CKernel *kernelfunc)
Definition: LaRank.cpp:74
The class Features is the base class of all feature objects.
Definition: Features.h:69
bool create_multiclass_svm(int32_t num_classes)
void(* update)(float *foo, float bar)
Definition: JLCoverTree.h:533
static void xpurge(larank_kcache_t *self)
Definition: LaRank.cpp:120
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
static T min(T a, T b)
Definition: Math.h:138
void set_max_iteration(int32_t max_iter)
Definition: LaRank.cpp:853

SHOGUN Machine Learning Toolbox - Documentation