49 #include <shogun/lib/config.h> 74 larank_kcache_t *
self;
75 self = SG_CALLOC (larank_kcache_t, 1);
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;
92 static void xtruncate (larank_kcache_t *
self, int32_t k, int32_t nlen)
94 int32_t olen =
self->rsize[k];
102 sg_memcpy (ndata, odata, nlen *
sizeof (
float32_t));
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;
112 self->rdata[k] = ndata;
113 self->rsize[k] = nlen;
114 self->cursize += (int64_t) (nlen - olen) *
sizeof (
float32_t);
118 static void xpurge (larank_kcache_t *
self)
120 if (self->cursize > self->maxsize)
122 int32_t k =
self->rprev[-1];
123 while (self->cursize > self->maxsize && k != self->rnext[-1])
125 int32_t pk =
self->rprev[k];
136 self->maxsize = entries;
145 larank_kcache_t *nb =
self->nextbuddy;
146 larank_kcache_t *pb =
self->prevbuddy;
155 for (i = 0; i <
self->l; i++)
157 SG_FREE (self->rdata[i]);
159 SG_FREE (self->rdata);
161 SG_FREE (self->rsize);
163 SG_FREE (self->rdiag);
165 SG_FREE (self->qnext);
167 SG_FREE (self->qprev);
168 memset (
self, 0,
sizeof (larank_kcache_t));
173 static void xminsize (larank_kcache_t *
self, int32_t n)
175 int32_t ol =
self->l;
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++)
210 static void xextend (larank_kcache_t *
self, int32_t k, int32_t nlen)
212 int32_t olen =
self->rsize[k];
219 sg_memcpy (ndata, odata, olen *
sizeof (
float32_t));
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);
229 static void xswap (larank_kcache_t *
self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
232 if (r1 < self->maxrowlen || r2 < self->maxrowlen)
235 int32_t k =
self->rnext[-1];
238 int32_t nk =
self->rnext[k];
239 int32_t n =
self->rsize[k];
240 int32_t rr =
self->i2r[k];
253 d[r1] =
self->rdiag[k];
257 int32_t arsize =
self->rsize[i2];
258 if (rr < arsize && rr != r1)
259 d[r1] =
self->rdata[i2][rr];
268 d[r2] =
self->rdiag[k];
272 int32_t arsize =
self->rsize[i1];
273 if (rr < arsize && rr != r2)
274 d[r2] =
self->rdata[i1][rr];
282 self->maxrowlen = mrl;
294 xswap (
self, self->r2i[r1], self->r2i[r2], r1, r2);
300 xswap (
self, self->r2i[r1], i2, r1, self->i2r[i2]);
306 larank_kcache_t *cache =
self->nextbuddy;
309 int32_t l = cache->l;
312 int32_t s = cache->rsize[i];
313 int32_t p = cache->i2r[j];
315 return cache->rdata[i][p];
316 if (i == j && s >= 0)
317 return cache->rdiag[i];
321 return cache->rdata[j][p];
323 cache = cache->nextbuddy;
325 while (cache !=
self);
327 return self->func->kernel(i, j);
336 return xquery (
self, i, j);
342 larank_kcache_t *p =
self;
343 larank_kcache_t *selflast =
self->prevbuddy;
344 larank_kcache_t *buddylast = buddy->prevbuddy;
346 ASSERT (self->func == buddy->func)
356 selflast->nextbuddy = buddy;
357 buddy->prevbuddy = selflast;
358 buddylast->nextbuddy =
self;
359 self->prevbuddy = buddylast;
366 if (i < self->l && len <= self->rsize[i])
368 self->rnext[
self->rprev[i]] =
self->rnext[i];
369 self->rprev[
self->rnext[i]] =
self->rprev[i];
375 if (i >= self->l || len >= self->l)
377 olen =
self->rsize[i];
382 self->rdiag[i] =
self->func->kernel(i, i);
383 olen =
self->rsize[i] = 0;
387 self->rsize[i] = olen;
388 for (p = olen; p < len; p++)
390 self->rsize[i] = len;
392 self->rnext[
self->rprev[i]] =
self->rnext[i];
393 self->rprev[
self->rnext[i]] =
self->rprev[i];
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];
407 void LaRankOutput::initialize (
CKernel* kfunc, int64_t cache)
419 void LaRankOutput::destroy ()
430 float64_t LaRankOutput::computeScore (int32_t x_id)
442 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
444 return (yi == ythis ? 1 : 0) - computeScore (xi_id);
452 for (int32_t r = 0; r < l; r++)
468 beta = SG_REALLOC(
float32_t, beta, l, l+1);
476 for (int32_t r = 0; r < l; r++)
479 g[r]=oldg - lambda * row[r];
485 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
491 int32_t LaRankOutput::cleanup ()
494 std::vector < int32_t >idx;
495 for (int32_t x = 0; x < l; x++)
497 if ((beta[x] < FLT_EPSILON) && (beta[x] > -FLT_EPSILON))
503 int32_t new_l = l - count;
504 for (int32_t xx = 0; xx < count; xx++)
506 int32_t i = idx[xx] - xx;
507 for (int32_t r = i; r < (l - 1); r++)
514 beta = SG_REALLOC(
float32_t, beta, l, new_l+1);
515 g = SG_REALLOC(
float32_t, g, l, new_l+1);
528 for (int32_t r = 0; r < l; r++)
536 float64_t LaRankOutput::getKii (int32_t x_id)
542 float64_t LaRankOutput::getBeta (int32_t x_id)
546 for (int32_t r = 0; r < l; r++)
552 return (xr < 0 ? 0 : beta[xr]);
556 float64_t LaRankOutput::getGradient (int32_t x_id)
560 for (int32_t r = 0; r < l; r++)
566 return (xr < 0 ? 0 : g[xr]);
568 bool LaRankOutput::isSupportVector (int32_t x_id)
const 572 for (int32_t r = 0; r < l; r++)
582 int32_t LaRankOutput::getSV (
float32_t* &sv)
const 586 for (int32_t r = 0; r < l; r++)
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)
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),
627 SG_ERROR(
"Numbert of vectors (%d) does not match number of labels (%d)\n",
647 for (int32_t i = 0; i <
nb_train; i++)
655 SG_DEBUG(
"Done: %d %% Train error (online): %f%%\n",
661 SG_DEBUG(
"End of iteration %d\n", n_it)
662 SG_DEBUG(
"Train error (online): %f%%\n", (tr_err / nb_train) * 100)
674 SG_WARNING(
"LaRank did not converge after %d iterations.\n",
678 int32_t num_classes = outputs.size();
680 SG_DEBUG(
"%d classes\n", num_classes)
684 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
686 const LaRankOutput* o=&(it->second);
688 larank_kcache_t* k=o->getKernel();
689 int32_t l=o->get_l();
694 SG_DEBUG(
"svm[%d] has %d sv, b=%f\n", i, l, 0.0)
698 for (int32_t j=0; j<l; j++)
720 outputs.insert (std::make_pair (yi, LaRankOutput ()));
721 LaRankOutput *cur = getOutput (yi);
723 if (outputs.size () == 1)
724 y0 = outputs.begin ()->first;
726 if (outputs.size () > 1)
728 LaRankOutput *out0 = getOutput (y0);
729 cur->set_kernel_buddy (out0->getKernel ());
733 LaRankPattern tpattern (x_id, yi);
734 LaRankPattern & pattern = (patterns.isPattern (x_id)) ? patterns.getPattern (x_id) : tpattern;
738 process_return_t pro_ret = process (pattern, processNew);
739 float64_t dual_increase = pro_ret.dual_increase;
741 float64_t coeff = dual_increase / (0.00001 + duration);
742 m_dual += dual_increase;
744 w_pro = 0.05 * coeff + (1 - 0.05) * w_pro;
752 if (w_pro < prop_min)
754 if (w_rep < prop_min)
756 if (w_opt < prop_min)
758 w_sum = w_pro + w_rep + w_opt;
764 else if ((r > w_pro) && (r <= w_pro + w_rep))
769 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
770 m_dual += ldual_increase;
772 w_rep = 0.05 * lcoeff + (1 - 0.05) * w_rep;
779 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
780 m_dual += ldual_increase;
782 w_opt = 0.05 * lcoeff + (1 - 0.05) * w_opt;
785 if (nb_seen_examples % 100 == 0)
786 nb_removed += cleanup ();
787 return pro_ret.ypred;
795 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
797 float64_t score = it->second.computeScore (x_id);
798 if (score > score_max)
809 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
810 it->second.destroy ();
820 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
822 const LaRankPattern & p = patterns[i];
825 LaRankOutput *out = getOutput (p.y);
828 sum_bi += out->getBeta (p.x_id);
829 float64_t gi = out->computeGradient (p.x_id, p.y, p.y);
831 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
833 if (it->first != p.y && it->second.isSupportVector (p.x_id))
836 it->second.computeGradient (p.x_id, p.y, it->first);
849 return outputs.size ();
856 "Max iteration (given: %d) must be positive.\n",
865 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
868 res += it->second.getSV (sv);
878 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
880 const LaRankPattern & p = patterns[i];
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);
894 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
896 const LaRankPattern & p = patterns[i];
899 LaRankOutput *out = getOutput (p.y);
902 res += out->getBeta (p.x_id);
907 LaRankOutput *CLaRank::getOutput (int32_t index)
909 outputhash_t::iterator it = outputs.find (index);
910 return it == outputs.end ()? NULL : &it->second;
914 CLaRank::process_return_t CLaRank::process (
const LaRankPattern & pattern, process_type ptype)
916 process_return_t pro_ret = process_return_t (0, 0);
921 std::vector < outputgradient_t > outputgradients(
getNumOutputs ());
922 std::vector < outputgradient_t > outputscores(
getNumOutputs ());
924 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
926 if (ptype != processOptimize
927 || it->second.isSupportVector (pattern.x_id))
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)));
935 outputscores.push_back (outputgradient_t (it->first, -g));
939 std::sort (outputgradients.begin (), outputgradients.end ());
944 std::sort (outputscores.begin (), outputscores.end ());
945 pro_ret.ypred = outputscores[0].output;
950 outputgradient_t ygp;
951 LaRankOutput *outp = NULL;
953 for (p = 0; p < outputgradients.size (); ++p)
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)))
967 if (p == outputgradients.size ())
973 outputgradient_t ygm;
974 LaRankOutput *outm = NULL;
976 for (m = outputgradients.size () - 1; m >= 0; --m)
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))
995 if ((ygp.gradient - ygm.gradient) <
tau)
997 if (ptype == processNew)
998 patterns.insert (pattern);
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))
1007 float64_t beta = outp->getBeta (pattern.x_id);
1008 if (ygp.output == pattern.y)
1019 outp->update (pattern.x_id, lambda, ygp.gradient);
1020 outm->update (pattern.x_id, -lambda, ygm.gradient);
1022 pro_ret.dual_increase = lambda * ((ygp.gradient - ygm.gradient) - lambda * kii);
1029 if (patterns.size ())
1031 for (int32_t n = 0; n < 10; ++n)
1033 process_return_t pro_ret = process (patterns.sample (), processOld);
1034 if (pro_ret.dual_increase)
1035 return pro_ret.dual_increase;
1045 if (patterns.size ())
1047 for (int32_t n = 0; n < 10; ++n)
1049 process_return_t pro_ret =
1050 process (patterns.sample(), processOptimize);
1051 dual_increase += pro_ret.dual_increase;
1054 return dual_increase;
1058 uint32_t CLaRank::cleanup ()
virtual bool init(CFeatures *lhs, CFeatures *rhs)
static void xtruncate(larank_kcache_t *self, int32_t k, int32_t nlen)
static float32_t * larank_kcache_query_row(larank_kcache_t *self, int32_t i, int32_t len)
bool batch_mode
whether to use online learning or batch training
virtual ELabelType get_label_type() const =0
static void larank_kcache_set_maximum_size(larank_kcache_t *self, int64_t entries)
The class Labels models labels, i.e. class assignments of objects.
bool train_machine(CFeatures *data)
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)
multi-class labels 0,1,...
static float64_t log10(float64_t v)
int32_t max_iteration
Max number of iterations before training is stopped.
virtual int32_t get_num_vectors() const =0
static float64_t larank_kcache_query(larank_kcache_t *self, int32_t i, int32_t j)
virtual int32_t add(int32_t x_id, int32_t yi)
virtual int32_t get_num_vec_lhs()
virtual float64_t computeGap()
static void larank_kcache_set_buddy(larank_kcache_t *self, larank_kcache_t *buddy)
static float64_t get_curtime()
static void xextend(larank_kcache_t *self, int32_t k, int32_t nlen)
Multiclass Labels for multi-class classification.
static float64_t xquery(larank_kcache_t *self, int32_t i, int32_t j)
static void larank_kcache_swap_rr(larank_kcache_t *self, int32_t r1, int32_t r2)
void set_bias(float64_t bias)
static void clear_cancel()
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)
static float64_t dot(const bool *v1, const bool *v2, int32_t n)
Compute dot product between v1 and v2 (blas optimized)
static bool cancel_computations()
virtual int32_t get_num_vec_rhs()
#define SG_ABS_PROGRESS(...)
static void larank_kcache_destroy(larank_kcache_t *self)
static void xminsize(larank_kcache_t *self, int32_t n)
all of classes and functions are contained in the shogun namespace
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)
static larank_kcache_t * larank_kcache_create(CKernel *kernelfunc)
The class Features is the base class of all feature objects.
bool create_multiclass_svm(int32_t num_classes)
void(* update)(float *foo, float bar)
virtual uint32_t getNumOutputs() const
static void xpurge(larank_kcache_t *self)
A generic Support Vector Machine Interface.
virtual int32_t predict(int32_t x_id)
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
void set_max_iteration(int32_t max_iter)