61 using namespace shogun;
67 larank_kcache_t *
self;
68 self = SG_CALLOC (larank_kcache_t, 1);
71 self->func = kernelfunc;
72 self->prevbuddy =
self;
73 self->nextbuddy =
self;
74 self->cursize =
sizeof (larank_kcache_t);
75 self->maxsize = 256 * 1024 * 1024;
76 self->qprev = SG_MALLOC(int32_t, 1);
77 self->qnext = SG_MALLOC(int32_t, 1);
78 self->rnext =
self->qnext + 1;
79 self->rprev =
self->qprev + 1;
85 static void xtruncate (larank_kcache_t *
self, int32_t k, int32_t nlen)
87 int32_t olen =
self->rsize[k];
95 memcpy (ndata, odata, nlen *
sizeof (
float32_t));
100 self->rnext[
self->rprev[k]] =
self->rnext[k];
101 self->rprev[
self->rnext[k]] =
self->rprev[k];
102 self->rnext[k] =
self->rprev[k] = k;
105 self->rdata[k] = ndata;
106 self->rsize[k] = nlen;
107 self->cursize += (int64_t) (nlen - olen) *
sizeof (
float32_t);
111 static void xpurge (larank_kcache_t *
self)
113 if (self->cursize > self->maxsize)
115 int32_t k =
self->rprev[-1];
116 while (self->cursize > self->maxsize && k != self->rnext[-1])
118 int32_t pk =
self->rprev[k];
129 self->maxsize = entries;
138 larank_kcache_t *nb =
self->nextbuddy;
139 larank_kcache_t *pb =
self->prevbuddy;
148 for (i = 0; i <
self->l; i++)
150 SG_FREE (self->rdata[i]);
152 SG_FREE (self->rdata);
154 SG_FREE (self->rsize);
156 SG_FREE (self->rdiag);
158 SG_FREE (self->qnext);
160 SG_FREE (self->qprev);
161 memset (
self, 0,
sizeof (larank_kcache_t));
166 static void xminsize (larank_kcache_t *
self, int32_t n)
168 int32_t ol =
self->l;
175 self->i2r = SG_REALLOC (int32_t, self->i2r, self->l, nl);
176 self->r2i = SG_REALLOC (int32_t, self->r2i, self->l, nl);
177 self->rsize = SG_REALLOC (int32_t, self->rsize, self->l, nl);
178 self->qnext = SG_REALLOC (int32_t, self->qnext, 1+self->l, (1 + nl));
179 self->qprev = SG_REALLOC (int32_t, self->qprev, 1+self->l, (1 + nl));
180 self->rdiag = SG_REALLOC (
float32_t, self->rdiag, self->l, nl);
181 self->rdata = SG_REALLOC (
float32_t*, self->rdata, self->l, nl);
182 self->rnext =
self->qnext + 1;
183 self->rprev =
self->qprev + 1;
184 for (i = ol; i < nl; i++)
203 static void xextend (larank_kcache_t *
self, int32_t k, int32_t nlen)
205 int32_t olen =
self->rsize[k];
212 memcpy (ndata, odata, olen *
sizeof (
float32_t));
215 self->rdata[k] = ndata;
216 self->rsize[k] = nlen;
217 self->cursize += (int64_t) (nlen - olen) *
sizeof (
float32_t);
218 self->maxrowlen =
CMath::max (self->maxrowlen, nlen);
222 static void xswap (larank_kcache_t *
self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
225 if (r1 < self->maxrowlen || r2 < self->maxrowlen)
228 int32_t k =
self->rnext[-1];
231 int32_t nk =
self->rnext[k];
232 int32_t n =
self->rsize[k];
233 int32_t rr =
self->i2r[k];
246 d[r1] =
self->rdiag[k];
250 int32_t arsize =
self->rsize[i2];
251 if (rr < arsize && rr != r1)
252 d[r1] =
self->rdata[i2][rr];
261 d[r2] =
self->rdiag[k];
265 int32_t arsize =
self->rsize[i1];
266 if (rr < arsize && rr != r2)
267 d[r2] =
self->rdata[i1][rr];
275 self->maxrowlen = mrl;
287 xswap (
self, self->r2i[r1], self->r2i[r2], r1, r2);
293 xswap (
self, self->r2i[r1], i2, r1, self->i2r[i2]);
299 larank_kcache_t *cache =
self->nextbuddy;
302 int32_t l = cache->l;
305 int32_t s = cache->rsize[i];
306 int32_t p = cache->i2r[j];
308 return cache->rdata[i][p];
309 if (i == j && s >= 0)
310 return cache->rdiag[i];
314 return cache->rdata[j][p];
316 cache = cache->nextbuddy;
318 while (cache !=
self);
320 return self->func->kernel(i, j);
329 return xquery (
self, i, j);
335 larank_kcache_t *p =
self;
336 larank_kcache_t *selflast =
self->prevbuddy;
337 larank_kcache_t *buddylast = buddy->prevbuddy;
339 ASSERT (self->func == buddy->func)
349 selflast->nextbuddy = buddy;
350 buddy->prevbuddy = selflast;
351 buddylast->nextbuddy =
self;
352 self->prevbuddy = buddylast;
359 if (i < self->l && len <= self->rsize[i])
361 self->rnext[
self->rprev[i]] =
self->rnext[i];
362 self->rprev[
self->rnext[i]] =
self->rprev[i];
368 if (i >= self->l || len >= self->l)
370 olen =
self->rsize[i];
375 self->rdiag[i] =
self->func->kernel(i, i);
376 olen =
self->rsize[i] = 0;
380 self->rsize[i] = olen;
381 for (p = olen; p < len; p++)
383 self->rsize[i] = len;
385 self->rnext[
self->rprev[i]] =
self->rnext[i];
386 self->rprev[
self->rnext[i]] =
self->rprev[i];
390 self->rnext[i] =
self->rnext[-1];
391 self->rnext[
self->rprev[i]] = i;
392 self->rprev[
self->rnext[i]] = i;
393 return self->rdata[i];
400 void LaRankOutput::initialize (
CKernel* kfunc, int64_t cache)
412 void LaRankOutput::destroy ()
423 float64_t LaRankOutput::computeScore (int32_t x_id)
435 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
437 return (yi == ythis ? 1 : 0) - computeScore (xi_id);
445 for (int32_t r = 0; r < l; r++)
461 beta = SG_REALLOC(
float32_t, beta, l, l+1);
469 for (int32_t r = 0; r < l; r++)
472 g[r]=oldg - lambda * row[r];
478 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
484 int32_t LaRankOutput::cleanup ()
487 std::vector < int32_t >idx;
488 for (int32_t x = 0; x < l; x++)
490 if ((beta[x] < FLT_EPSILON) && (beta[x] > -FLT_EPSILON))
496 int32_t new_l = l - count;
497 for (int32_t xx = 0; xx < count; xx++)
499 int32_t i = idx[xx] - xx;
500 for (int32_t r = i; r < (l - 1); r++)
507 beta = SG_REALLOC(
float32_t, beta, l, new_l+1);
508 g = SG_REALLOC(
float32_t, g, l, new_l+1);
521 for (int32_t r = 0; r < l; r++)
529 float64_t LaRankOutput::getKii (int32_t x_id)
535 float64_t LaRankOutput::getBeta (int32_t x_id)
539 for (int32_t r = 0; r < l; r++)
545 return (xr < 0 ? 0 : beta[xr]);
549 float64_t LaRankOutput::getGradient (int32_t x_id)
553 for (int32_t r = 0; r < l; r++)
559 return (xr < 0 ? 0 : g[xr]);
561 bool LaRankOutput::isSupportVector (int32_t x_id)
const
565 for (int32_t r = 0; r < l; r++)
575 int32_t LaRankOutput::getSV (
float32_t* &sv)
const
579 for (int32_t r = 0; r < l; r++)
585 nb_seen_examples (0), nb_removed (0),
586 n_pro (0), n_rep (0), n_opt (0),
587 w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
588 batch_mode(true), step(0)
594 nb_seen_examples (0), nb_removed (0),
595 n_pro (0), n_rep (0), n_opt (0),
596 w_pro (1), w_rep (1), w_opt (1), y0 (0), m_dual (0),
597 batch_mode(true), step(0)
620 SG_ERROR(
"Numbert of vectors (%d) does not match number of labels (%d)\n",
639 for (int32_t i = 0; i <
nb_train; i++)
647 SG_DEBUG(
"Done: %d %% Train error (online): %f%%\n",
653 SG_DEBUG(
"End of iteration %d\n", n_it++)
654 SG_DEBUG(
"Train error (online): %f%%\n", (tr_err / nb_train) * 100)
663 int32_t num_classes = outputs.size();
665 SG_DEBUG(
"%d classes\n", num_classes)
669 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
671 const LaRankOutput* o=&(it->second);
673 larank_kcache_t* k=o->getKernel();
674 int32_t l=o->get_l();
679 SG_DEBUG(
"svm[%d] has %d sv, b=%f\n", i, l, 0.0)
683 for (int32_t j=0; j<l; j++)
705 outputs.insert (std::make_pair (yi, LaRankOutput ()));
706 LaRankOutput *cur = getOutput (yi);
708 if (outputs.size () == 1)
709 y0 = outputs.begin ()->first;
711 if (outputs.size () > 1)
713 LaRankOutput *out0 = getOutput (y0);
714 cur->set_kernel_buddy (out0->getKernel ());
718 LaRankPattern tpattern (x_id, yi);
719 LaRankPattern & pattern = (patterns.isPattern (x_id)) ? patterns.getPattern (x_id) : tpattern;
723 process_return_t pro_ret = process (pattern, processNew);
724 float64_t dual_increase = pro_ret.dual_increase;
726 float64_t coeff = dual_increase / (0.00001 + duration);
727 m_dual += dual_increase;
729 w_pro = 0.05 * coeff + (1 - 0.05) * w_pro;
737 if (w_pro < prop_min)
739 if (w_rep < prop_min)
741 if (w_opt < prop_min)
743 w_sum = w_pro + w_rep + w_opt;
749 else if ((r > w_pro) && (r <= w_pro + w_rep))
754 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
755 m_dual += ldual_increase;
757 w_rep = 0.05 * lcoeff + (1 - 0.05) * w_rep;
764 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
765 m_dual += ldual_increase;
767 w_opt = 0.05 * lcoeff + (1 - 0.05) * w_opt;
770 if (nb_seen_examples % 100 == 0)
771 nb_removed += cleanup ();
772 return pro_ret.ypred;
780 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
782 float64_t score = it->second.computeScore (x_id);
783 if (score > score_max)
794 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
795 it->second.destroy ();
805 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
807 const LaRankPattern & p = patterns[i];
810 LaRankOutput *out = getOutput (p.y);
813 sum_bi += out->getBeta (p.x_id);
814 float64_t gi = out->computeGradient (p.x_id, p.y, p.y);
816 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
818 if (it->first != p.y && it->second.isSupportVector (p.x_id))
821 it->second.computeGradient (p.x_id, p.y, it->first);
834 return outputs.size ();
841 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
844 res += it->second.getSV (sv);
854 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
856 const LaRankPattern & p = patterns[i];
859 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
860 if (it->second.getBeta (p.x_id))
861 res += it->second.getBeta (p.x_id) * it->second.computeScore (p.x_id);
870 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
872 const LaRankPattern & p = patterns[i];
875 LaRankOutput *out = getOutput (p.y);
878 res += out->getBeta (p.x_id);
883 LaRankOutput *CLaRank::getOutput (int32_t index)
885 outputhash_t::iterator it = outputs.find (index);
886 return it == outputs.end ()? NULL : &it->second;
890 CLaRank::process_return_t CLaRank::process (
const LaRankPattern & pattern, process_type ptype)
892 process_return_t pro_ret = process_return_t (0, 0);
897 std::vector < outputgradient_t > outputgradients;
901 std::vector < outputgradient_t > outputscores;
904 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
906 if (ptype != processOptimize
907 || it->second.isSupportVector (pattern.x_id))
910 it->second.computeGradient (pattern.x_id, pattern.y, it->first);
911 outputgradients.push_back (outputgradient_t (it->first, g));
912 if (it->first == pattern.y)
913 outputscores.push_back (outputgradient_t (it->first, (1 - g)));
915 outputscores.push_back (outputgradient_t (it->first, -g));
919 std::sort (outputgradients.begin (), outputgradients.end ());
924 std::sort (outputscores.begin (), outputscores.end ());
925 pro_ret.ypred = outputscores[0].output;
930 outputgradient_t ygp;
931 LaRankOutput *outp = NULL;
933 for (p = 0; p < outputgradients.size (); ++p)
935 outputgradient_t & current = outputgradients[p];
936 LaRankOutput *output = getOutput (current.output);
937 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
938 bool goodclass = current.output == pattern.y;
939 if ((!support && goodclass) ||
940 (support && output->getBeta (pattern.x_id) < (goodclass ?
get_C() : 0)))
947 if (p == outputgradients.size ())
953 outputgradient_t ygm;
954 LaRankOutput *outm = NULL;
956 for (m = outputgradients.size () - 1; m >= 0; --m)
958 outputgradient_t & current = outputgradients[m];
959 LaRankOutput *output = getOutput (current.output);
960 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
961 bool goodclass = current.output == pattern.y;
962 if (!goodclass || (support && output->getBeta (pattern.x_id) > 0))
975 if ((ygp.gradient - ygm.gradient) <
tau)
977 if (ptype == processNew)
978 patterns.insert (pattern);
983 float64_t kii = outp->getKii (pattern.x_id);
984 float64_t lambda = (ygp.gradient - ygm.gradient) / (2 * kii);
985 if (ptype == processOptimize || outp->isSupportVector (pattern.x_id))
987 float64_t beta = outp->getBeta (pattern.x_id);
988 if (ygp.output == pattern.y)
999 outp->update (pattern.x_id, lambda, ygp.gradient);
1000 outm->update (pattern.x_id, -lambda, ygm.gradient);
1002 pro_ret.dual_increase = lambda * ((ygp.gradient - ygm.gradient) - lambda * kii);
1009 if (patterns.size ())
1011 for (int32_t n = 0; n < 10; ++n)
1013 process_return_t pro_ret = process (patterns.sample (), processOld);
1014 if (pro_ret.dual_increase)
1015 return pro_ret.dual_increase;
1025 if (patterns.size ())
1027 for (int32_t n = 0; n < 10; ++n)
1029 process_return_t pro_ret =
1030 process (patterns.sample(), processOptimize);
1031 dual_increase += pro_ret.dual_increase;
1034 return dual_increase;
1038 uint32_t CLaRank::cleanup ()