59 using namespace shogun;
65 larank_kcache_t *
self;
69 self->func = kernelfunc;
70 self->prevbuddy =
self;
71 self->nextbuddy =
self;
72 self->cursize =
sizeof (larank_kcache_t);
73 self->maxsize = 256 * 1024 * 1024;
76 self->rnext =
self->qnext + 1;
77 self->rprev =
self->qprev + 1;
83 static void xtruncate (larank_kcache_t *
self, int32_t k, int32_t nlen)
85 int32_t olen =
self->rsize[k];
93 memcpy (ndata, odata, nlen *
sizeof (
float32_t));
98 self->rnext[
self->rprev[k]] =
self->rnext[k];
99 self->rprev[
self->rnext[k]] =
self->rprev[k];
100 self->rnext[k] =
self->rprev[k] = k;
103 self->rdata[k] = ndata;
104 self->rsize[k] = nlen;
105 self->cursize += (int64_t) (nlen - olen) *
sizeof (
float32_t);
109 static void xpurge (larank_kcache_t *
self)
111 if (self->cursize > self->maxsize)
113 int32_t k =
self->rprev[-1];
114 while (self->cursize > self->maxsize && k != self->rnext[-1])
116 int32_t pk =
self->rprev[k];
127 self->maxsize = entries;
136 larank_kcache_t *nb =
self->nextbuddy;
137 larank_kcache_t *pb =
self->prevbuddy;
146 for (i = 0; i <
self->l; i++)
159 memset (
self, 0,
sizeof (larank_kcache_t));
164 static void xminsize (larank_kcache_t *
self, int32_t n)
166 int32_t ol =
self->l;
173 self->i2r =
SG_REALLOC (int32_t, self->i2r, nl);
174 self->r2i =
SG_REALLOC (int32_t, self->r2i, nl);
175 self->rsize =
SG_REALLOC (int32_t, self->rsize, nl);
176 self->qnext =
SG_REALLOC (int32_t, self->qnext, (1 + nl));
177 self->qprev =
SG_REALLOC (int32_t, self->qprev, (1 + nl));
180 self->rnext =
self->qnext + 1;
181 self->rprev =
self->qprev + 1;
182 for (i = ol; i < nl; i++)
201 static void xextend (larank_kcache_t *
self, int32_t k, int32_t nlen)
203 int32_t olen =
self->rsize[k];
210 memcpy (ndata, odata, olen *
sizeof (
float32_t));
213 self->rdata[k] = ndata;
214 self->rsize[k] = nlen;
215 self->cursize += (int64_t) (nlen - olen) *
sizeof (
float32_t);
216 self->maxrowlen =
CMath::max (self->maxrowlen, nlen);
220 static void xswap (larank_kcache_t *
self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
223 if (r1 < self->maxrowlen || r2 < self->maxrowlen)
226 int32_t k =
self->rnext[-1];
229 int32_t nk =
self->rnext[k];
230 int32_t n =
self->rsize[k];
231 int32_t rr =
self->i2r[k];
244 d[r1] =
self->rdiag[k];
248 int32_t arsize =
self->rsize[i2];
249 if (rr < arsize && rr != r1)
250 d[r1] =
self->rdata[i2][rr];
259 d[r2] =
self->rdiag[k];
263 int32_t arsize =
self->rsize[i1];
264 if (rr < arsize && rr != r2)
265 d[r2] =
self->rdata[i1][rr];
273 self->maxrowlen = mrl;
285 xswap (
self, self->r2i[r1], self->r2i[r2], r1, r2);
291 xswap (
self, self->r2i[r1], i2, r1, self->i2r[i2]);
297 larank_kcache_t *cache =
self->nextbuddy;
300 int32_t l = cache->l;
303 int32_t s = cache->rsize[i];
304 int32_t p = cache->i2r[j];
306 return cache->rdata[i][p];
307 if (i == j && s >= 0)
308 return cache->rdiag[i];
312 return cache->rdata[j][p];
314 cache = cache->nextbuddy;
316 while (cache !=
self);
318 return self->func->kernel(i, j);
327 return xquery (
self, i, j);
333 larank_kcache_t *p =
self;
334 larank_kcache_t *selflast =
self->prevbuddy;
335 larank_kcache_t *buddylast = buddy->prevbuddy;
337 ASSERT (self->func == buddy->func);
347 selflast->nextbuddy = buddy;
348 buddy->prevbuddy = selflast;
349 buddylast->nextbuddy =
self;
350 self->prevbuddy = buddylast;
357 if (i < self->l && len <= self->rsize[i])
359 self->rnext[
self->rprev[i]] =
self->rnext[i];
360 self->rprev[
self->rnext[i]] =
self->rprev[i];
366 if (i >= self->l || len >= self->l)
368 olen =
self->rsize[i];
373 self->rdiag[i] =
self->func->kernel(i, i);
374 olen =
self->rsize[i] = 0;
378 self->rsize[i] = olen;
379 for (p = olen; p < len; p++)
381 self->rsize[i] = len;
383 self->rnext[
self->rprev[i]] =
self->rnext[i];
384 self->rprev[
self->rnext[i]] =
self->rprev[i];
388 self->rnext[i] =
self->rnext[-1];
389 self->rnext[
self->rprev[i]] = i;
390 self->rprev[
self->rnext[i]] = i;
391 return self->rdata[i];
410 void LaRankOutput::destroy ()
421 float64_t LaRankOutput::computeScore (int32_t x_id)
433 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
435 return (yi == ythis ? 1 : 0) - computeScore (xi_id);
443 for (int32_t r = 0; r < l; r++)
467 for (int32_t r = 0; r < l; r++)
470 g[r]=oldg - lambda * row[r];
476 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
482 int32_t LaRankOutput::cleanup ()
485 std::vector < int32_t >idx;
486 for (int32_t x = 0; x < l; x++)
488 if ((beta[x] < FLT_EPSILON) && (beta[x] > -FLT_EPSILON))
494 int32_t new_l = l - count;
495 for (int32_t xx = 0; xx < count; xx++)
497 int32_t i = idx[xx] - xx;
498 for (int32_t r = i; r < (l - 1); r++)
519 for (int32_t r = 0; r < l; r++)
527 float64_t LaRankOutput::getKii (int32_t x_id)
533 float64_t LaRankOutput::getBeta (int32_t x_id)
537 for (int32_t r = 0; r < l; r++)
543 return (xr < 0 ? 0 : beta[xr]);
547 float64_t LaRankOutput::getGradient (int32_t x_id)
551 for (int32_t r = 0; r < l; r++)
557 return (xr < 0 ? 0 : g[xr]);
559 bool LaRankOutput::isSupportVector (int32_t x_id)
const
563 for (int32_t r = 0; r < l; r++)
573 int32_t LaRankOutput::getSV (
float32_t* &sv)
const
577 for (int32_t r = 0; r < l; r++)
583 nb_seen_examples (0), nb_removed (0),
584 n_pro (0), n_rep (0), n_opt (0),
585 w_pro (1), w_rep (1), w_opt (1), y0 (0), dual (0),
586 batch_mode(true), step(0)
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), dual (0),
595 batch_mode(true), step(0)
617 SG_ERROR(
"Numbert of vectors (%d) does not match number of labels (%d)\n",
631 SG_INFO(
"Training on %d examples\n", nb_train);
636 for (int32_t i = 0; i <
nb_train; i++)
644 SG_DEBUG(
"Done: %d %% Train error (online): %f%%\n",
650 SG_DEBUG(
"End of iteration %d\n", n_it++);
651 SG_DEBUG(
"Train error (online): %f%%\n", (tr_err / nb_train) * 100);
660 int32_t num_classes = outputs.size();
662 SG_DEBUG(
"%d classes\n", num_classes);
666 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
668 const LaRankOutput* o=&(it->second);
670 larank_kcache_t* k=o->getKernel();
671 int32_t l=o->get_l();
676 SG_DEBUG(
"svm[%d] has %d sv, b=%f\n", i, l, 0.0);
680 for (int32_t j=0; j<l; j++)
702 outputs.insert (std::make_pair (yi, LaRankOutput ()));
703 LaRankOutput *cur = getOutput (yi);
705 if (outputs.size () == 1)
706 y0 = outputs.begin ()->first;
708 if (outputs.size () > 1)
710 LaRankOutput *out0 = getOutput (y0);
711 cur->set_kernel_buddy (out0->getKernel ());
715 LaRankPattern tpattern (x_id, yi);
716 LaRankPattern & pattern = (patterns.isPattern (x_id)) ? patterns.getPattern (x_id) : tpattern;
720 process_return_t pro_ret = process (pattern, processNew);
721 float64_t dual_increase = pro_ret.dual_increase;
723 float64_t coeff = dual_increase / (0.00001 + duration);
724 dual += dual_increase;
726 w_pro = 0.05 * coeff + (1 - 0.05) * w_pro;
734 if (w_pro < prop_min)
736 if (w_rep < prop_min)
738 if (w_opt < prop_min)
740 w_sum = w_pro + w_rep + w_opt;
746 else if ((r > w_pro) && (r <= w_pro + w_rep))
751 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
752 dual += ldual_increase;
754 w_rep = 0.05 * lcoeff + (1 - 0.05) * w_rep;
761 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
762 dual += ldual_increase;
764 w_opt = 0.05 * lcoeff + (1 - 0.05) * w_opt;
767 if (nb_seen_examples % 100 == 0)
768 nb_removed += cleanup ();
769 return pro_ret.ypred;
777 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
779 float64_t score = it->second.computeScore (x_id);
780 if (score > score_max)
791 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
792 it->second.destroy ();
801 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
803 const LaRankPattern & p = patterns[i];
806 LaRankOutput *out = getOutput (p.y);
809 sum_bi += out->getBeta (p.x_id);
810 float64_t gi = out->computeGradient (p.x_id, p.y, p.y);
812 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
814 if (it->first != p.y && it->second.isSupportVector (p.x_id))
817 it->second.computeGradient (p.x_id, p.y, it->first);
830 return outputs.size ();
837 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
840 res += it->second.getSV (sv);
850 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
852 const LaRankPattern & p = patterns[i];
855 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
856 if (it->second.getBeta (p.x_id))
857 res += it->second.getBeta (p.x_id) * it->second.computeScore (p.x_id);
866 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
868 const LaRankPattern & p = patterns[i];
871 LaRankOutput *out = getOutput (p.y);
874 res += out->getBeta (p.x_id);
879 LaRankOutput *CLaRank::getOutput (int32_t index)
881 outputhash_t::iterator it = outputs.find (index);
882 return it == outputs.end ()? NULL : &it->second;
886 CLaRank::process_return_t CLaRank::process (
const LaRankPattern & pattern, process_type ptype)
888 process_return_t pro_ret = process_return_t (0, 0);
893 std::vector < outputgradient_t > outputgradients;
897 std::vector < outputgradient_t > outputscores;
900 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
902 if (ptype != processOptimize
903 || it->second.isSupportVector (pattern.x_id))
906 it->second.computeGradient (pattern.x_id, pattern.y, it->first);
907 outputgradients.push_back (outputgradient_t (it->first, g));
908 if (it->first == pattern.y)
909 outputscores.push_back (outputgradient_t (it->first, (1 - g)));
911 outputscores.push_back (outputgradient_t (it->first, -g));
915 std::sort (outputgradients.begin (), outputgradients.end ());
920 std::sort (outputscores.begin (), outputscores.end ());
921 pro_ret.ypred = outputscores[0].output;
926 outputgradient_t ygp;
927 LaRankOutput *outp = NULL;
929 for (p = 0; p < outputgradients.size (); ++p)
931 outputgradient_t & current = outputgradients[p];
932 LaRankOutput *output = getOutput (current.output);
933 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
934 bool goodclass = current.output == pattern.y;
935 if ((!support && goodclass) ||
936 (support && output->getBeta (pattern.x_id) < (goodclass ?
C1 : 0)))
943 if (p == outputgradients.size ())
949 outputgradient_t ygm;
950 LaRankOutput *outm = NULL;
952 for (m = outputgradients.size () - 1; m >= 0; --m)
954 outputgradient_t & current = outputgradients[m];
955 LaRankOutput *output = getOutput (current.output);
956 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
957 bool goodclass = current.output == pattern.y;
958 if (!goodclass || (support && output->getBeta (pattern.x_id) > 0))
971 if ((ygp.gradient - ygm.gradient) <
tau)
973 if (ptype == processNew)
974 patterns.insert (pattern);
979 float64_t kii = outp->getKii (pattern.x_id);
980 float64_t lambda = (ygp.gradient - ygm.gradient) / (2 * kii);
981 if (ptype == processOptimize || outp->isSupportVector (pattern.x_id))
983 float64_t beta = outp->getBeta (pattern.x_id);
984 if (ygp.output == pattern.y)
995 outp->update (pattern.x_id, lambda, ygp.gradient);
996 outm->update (pattern.x_id, -lambda, ygm.gradient);
998 pro_ret.dual_increase = lambda * ((ygp.gradient - ygm.gradient) - lambda * kii);
1005 if (patterns.size ())
1007 for (int32_t n = 0; n < 10; ++n)
1009 process_return_t pro_ret = process (patterns.sample (), processOld);
1010 if (pro_ret.dual_increase)
1011 return pro_ret.dual_increase;
1021 if (patterns.size ())
1023 for (int32_t n = 0; n < 10; ++n)
1025 process_return_t pro_ret =
1026 process (patterns.sample(), processOptimize);
1027 dual_increase += pro_ret.dual_increase;
1030 return dual_increase;
1034 uint32_t CLaRank::cleanup ()