00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 #include <vector>
00050 #include <algorithm>
00051
00052 #include "lib/io.h"
00053 #include "lib/Signal.h"
00054 #include "lib/Time.h"
00055 #include "lib/Mathematics.h"
00056 #include "classifier/svm/LaRank.h"
00057 #include "kernel/Kernel.h"
00058
00059 using namespace shogun;
00060
00061 namespace shogun
00062 {
00063 static void * xmalloc (int32_t n)
00064 {
00065 void *p = malloc (n);
00066 if (!p)
00067 SG_SERROR ("Function malloc() has returned zero\n");
00068 return p;
00069 }
00070
00071 static void * xrealloc (void *ptr, int32_t n)
00072 {
00073 if (!ptr)
00074 ptr = malloc (n);
00075 else
00076 ptr = realloc (ptr, n);
00077 if (!ptr)
00078 SG_SERROR ("Function realloc has returned zero\n");
00079 return ptr;
00080 }
00081
00082 static larank_kcache_t* larank_kcache_create (CKernel* kernelfunc)
00083 {
00084 larank_kcache_t *self;
00085 self = (larank_kcache_t *) xmalloc (sizeof (larank_kcache_t));
00086 memset (self, 0, sizeof (larank_kcache_t));
00087 self->l = 0;
00088 self->maxrowlen = 0;
00089 self->func = kernelfunc;
00090 self->prevbuddy = self;
00091 self->nextbuddy = self;
00092 self->cursize = sizeof (larank_kcache_t);
00093 self->maxsize = 256 * 1024 * 1024;
00094 self->qprev = (int32_t *) xmalloc (sizeof (int32_t));
00095 self->qnext = (int32_t *) xmalloc (sizeof (int32_t));
00096 self->rnext = self->qnext + 1;
00097 self->rprev = self->qprev + 1;
00098 self->rprev[-1] = -1;
00099 self->rnext[-1] = -1;
00100 return self;
00101 }
00102
00103 static void xtruncate (larank_kcache_t * self, int32_t k, int32_t nlen)
00104 {
00105 int32_t olen = self->rsize[k];
00106 if (nlen < olen)
00107 {
00108 float32_t *ndata;
00109 float32_t *odata = self->rdata[k];
00110 if (nlen > 0)
00111 {
00112 ndata = (float32_t *) xmalloc (nlen * sizeof (float32_t));
00113 memcpy (ndata, odata, nlen * sizeof (float32_t));
00114 }
00115 else
00116 {
00117 ndata = 0;
00118 self->rnext[self->rprev[k]] = self->rnext[k];
00119 self->rprev[self->rnext[k]] = self->rprev[k];
00120 self->rnext[k] = self->rprev[k] = k;
00121 }
00122 free (odata);
00123 self->rdata[k] = ndata;
00124 self->rsize[k] = nlen;
00125 self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
00126 }
00127 }
00128
00129 static void xpurge (larank_kcache_t * self)
00130 {
00131 if (self->cursize > self->maxsize)
00132 {
00133 int32_t k = self->rprev[-1];
00134 while (self->cursize > self->maxsize && k != self->rnext[-1])
00135 {
00136 int32_t pk = self->rprev[k];
00137 xtruncate (self, k, 0);
00138 k = pk;
00139 }
00140 }
00141 }
00142
00143 static void larank_kcache_set_maximum_size (larank_kcache_t * self, int64_t entries)
00144 {
00145 ASSERT (self);
00146 ASSERT (entries > 0);
00147 self->maxsize = entries;
00148 xpurge (self);
00149 }
00150
00151 static void larank_kcache_destroy (larank_kcache_t * self)
00152 {
00153 if (self)
00154 {
00155 int32_t i;
00156 larank_kcache_t *nb = self->nextbuddy;
00157 larank_kcache_t *pb = self->prevbuddy;
00158 pb->nextbuddy = nb;
00159 nb->prevbuddy = pb;
00160
00161 if (self->i2r)
00162 free (self->i2r);
00163 if (self->r2i)
00164 free (self->r2i);
00165 if (self->rdata)
00166 for (i = 0; i < self->l; i++)
00167 if (self->rdata[i])
00168 free (self->rdata[i]);
00169 if (self->rdata)
00170 free (self->rdata);
00171 if (self->rsize)
00172 free (self->rsize);
00173 if (self->rdiag)
00174 free (self->rdiag);
00175 if (self->qnext)
00176 free (self->qnext);
00177 if (self->qprev)
00178 free (self->qprev);
00179 memset (self, 0, sizeof (larank_kcache_t));
00180 free (self);
00181 }
00182 }
00183
00184 static void xminsize (larank_kcache_t * self, int32_t n)
00185 {
00186 int32_t ol = self->l;
00187 if (n > ol)
00188 {
00189 int32_t i;
00190 int32_t nl = CMath::max (256, ol);
00191 while (nl < n)
00192 nl = nl + nl;
00193 self->i2r = (int32_t *) xrealloc (self->i2r, nl * sizeof (int32_t));
00194 self->r2i = (int32_t *) xrealloc (self->r2i, nl * sizeof (int32_t));
00195 self->rsize = (int32_t *) xrealloc (self->rsize, nl * sizeof (int32_t));
00196 self->qnext = (int32_t *) xrealloc (self->qnext, (1 + nl) * sizeof (int32_t));
00197 self->qprev = (int32_t *) xrealloc (self->qprev, (1 + nl) * sizeof (int32_t));
00198 self->rdiag = (float32_t *) xrealloc (self->rdiag, nl * sizeof (float32_t));
00199 self->rdata = (float32_t **) xrealloc (self->rdata, nl * sizeof (float32_t *));
00200 self->rnext = self->qnext + 1;
00201 self->rprev = self->qprev + 1;
00202 for (i = ol; i < nl; i++)
00203 {
00204 self->i2r[i] = i;
00205 self->r2i[i] = i;
00206 self->rsize[i] = -1;
00207 self->rnext[i] = i;
00208 self->rprev[i] = i;
00209 self->rdata[i] = 0;
00210 }
00211 self->l = nl;
00212 }
00213 }
00214
00215 static int32_t* larank_kcache_r2i (larank_kcache_t * self, int32_t n)
00216 {
00217 xminsize (self, n);
00218 return self->r2i;
00219 }
00220
00221 static void xextend (larank_kcache_t * self, int32_t k, int32_t nlen)
00222 {
00223 int32_t olen = self->rsize[k];
00224 if (nlen > olen)
00225 {
00226 float32_t *ndata = (float32_t *) xmalloc (nlen * sizeof (float32_t));
00227 if (olen > 0)
00228 {
00229 float32_t *odata = self->rdata[k];
00230 memcpy (ndata, odata, olen * sizeof (float32_t));
00231 free (odata);
00232 }
00233 self->rdata[k] = ndata;
00234 self->rsize[k] = nlen;
00235 self->cursize += (int64_t) (nlen - olen) * sizeof (float32_t);
00236 self->maxrowlen = CMath::max (self->maxrowlen, nlen);
00237 }
00238 }
00239
00240 static void xswap (larank_kcache_t * self, int32_t i1, int32_t i2, int32_t r1, int32_t r2)
00241 {
00242
00243 if (r1 < self->maxrowlen || r2 < self->maxrowlen)
00244 {
00245 int32_t mrl = 0;
00246 int32_t k = self->rnext[-1];
00247 while (k >= 0)
00248 {
00249 int32_t nk = self->rnext[k];
00250 int32_t n = self->rsize[k];
00251 int32_t rr = self->i2r[k];
00252 float32_t *d = self->rdata[k];
00253 if (r1 < n)
00254 {
00255 if (r2 < n)
00256 {
00257 float32_t t1 = d[r1];
00258 float32_t t2 = d[r2];
00259 d[r1] = t2;
00260 d[r2] = t1;
00261 }
00262 else if (rr == r2)
00263 {
00264 d[r1] = self->rdiag[k];
00265 }
00266 else
00267 {
00268 int32_t arsize = self->rsize[i2];
00269 if (rr < arsize && rr != r1)
00270 d[r1] = self->rdata[i2][rr];
00271 else
00272 xtruncate (self, k, r1);
00273 }
00274 }
00275 else if (r2 < n)
00276 {
00277 if (rr == r1)
00278 {
00279 d[r2] = self->rdiag[k];
00280 }
00281 else
00282 {
00283 int32_t arsize = self->rsize[i1];
00284 if (rr < arsize && rr != r2)
00285 d[r2] = self->rdata[i1][rr];
00286 else
00287 xtruncate (self, k, r2);
00288 }
00289 }
00290 mrl = CMath::max (mrl, self->rsize[k]);
00291 k = nk;
00292 }
00293 self->maxrowlen = mrl;
00294 }
00295
00296 self->r2i[r1] = i2;
00297 self->r2i[r2] = i1;
00298 self->i2r[i1] = r2;
00299 self->i2r[i2] = r1;
00300 }
00301
00302 static void larank_kcache_swap_rr (larank_kcache_t * self, int32_t r1, int32_t r2)
00303 {
00304 xminsize (self, 1 + CMath::max(r1, r2));
00305 xswap (self, self->r2i[r1], self->r2i[r2], r1, r2);
00306 }
00307
00308 static void larank_kcache_swap_ri (larank_kcache_t * self, int32_t r1, int32_t i2)
00309 {
00310 xminsize (self, 1 + CMath::max (r1, i2));
00311 xswap (self, self->r2i[r1], i2, r1, self->i2r[i2]);
00312 }
00313
00314 static float64_t xquery (larank_kcache_t * self, int32_t i, int32_t j)
00315 {
00316
00317 larank_kcache_t *cache = self->nextbuddy;
00318 do
00319 {
00320 int32_t l = cache->l;
00321 if (i < l && j < l)
00322 {
00323 int32_t s = cache->rsize[i];
00324 int32_t p = cache->i2r[j];
00325 if (p < s)
00326 return cache->rdata[i][p];
00327 if (i == j && s >= 0)
00328 return cache->rdiag[i];
00329 p = cache->i2r[i];
00330 s = cache->rsize[j];
00331 if (p < s)
00332 return cache->rdata[j][p];
00333 }
00334 cache = cache->nextbuddy;
00335 }
00336 while (cache != self);
00337
00338 return self->func->kernel(i, j);
00339 }
00340
00341
00342 static float64_t larank_kcache_query (larank_kcache_t * self, int32_t i, int32_t j)
00343 {
00344 ASSERT (self);
00345 ASSERT (i >= 0);
00346 ASSERT (j >= 0);
00347 return xquery (self, i, j);
00348 }
00349
00350
00351 static void larank_kcache_set_buddy (larank_kcache_t * self, larank_kcache_t * buddy)
00352 {
00353 larank_kcache_t *p = self;
00354 larank_kcache_t *selflast = self->prevbuddy;
00355 larank_kcache_t *buddylast = buddy->prevbuddy;
00356
00357 ASSERT (self->func == buddy->func);
00358
00359 do
00360 {
00361 if (p == buddy)
00362 return;
00363 p = p->nextbuddy;
00364 }
00365 while (p != self);
00366
00367 selflast->nextbuddy = buddy;
00368 buddy->prevbuddy = selflast;
00369 buddylast->nextbuddy = self;
00370 self->prevbuddy = buddylast;
00371 }
00372
00373
00374 static float32_t* larank_kcache_query_row (larank_kcache_t * self, int32_t i, int32_t len)
00375 {
00376 ASSERT (i >= 0);
00377 if (i < self->l && len <= self->rsize[i])
00378 {
00379 self->rnext[self->rprev[i]] = self->rnext[i];
00380 self->rprev[self->rnext[i]] = self->rprev[i];
00381 }
00382 else
00383 {
00384 int32_t olen, p;
00385 float32_t *d;
00386 if (i >= self->l || len >= self->l)
00387 xminsize (self, CMath::max (1 + i, len));
00388 olen = self->rsize[i];
00389 if (olen < len)
00390 {
00391 if (olen < 0)
00392 {
00393 self->rdiag[i] = self->func->kernel(i, i);
00394 olen = self->rsize[i] = 0;
00395 }
00396 xextend (self, i, len);
00397 d = self->rdata[i];
00398 self->rsize[i] = olen;
00399 for (p = olen; p < len; p++)
00400 d[p] = larank_kcache_query (self, self->r2i[p], i);
00401 self->rsize[i] = len;
00402 }
00403 self->rnext[self->rprev[i]] = self->rnext[i];
00404 self->rprev[self->rnext[i]] = self->rprev[i];
00405 xpurge (self);
00406 }
00407 self->rprev[i] = -1;
00408 self->rnext[i] = self->rnext[-1];
00409 self->rnext[self->rprev[i]] = i;
00410 self->rprev[self->rnext[i]] = i;
00411 return self->rdata[i];
00412 }
00413
00414 }
00415
00416
00417
00418 void LaRankOutput::initialize (CKernel* kfunc, int64_t cache)
00419 {
00420 kernel = larank_kcache_create (kfunc);
00421 larank_kcache_set_maximum_size (kernel, cache * 1024 * 1024);
00422 beta = new float32_t[1];
00423 g = new float32_t[1];
00424 *beta=0;
00425 *g=0;
00426 l = 0;
00427 }
00428
00429
00430 void LaRankOutput::destroy ()
00431 {
00432 larank_kcache_destroy (kernel);
00433 kernel=NULL;
00434 delete[] beta;
00435 delete[] g;
00436 beta=NULL;
00437 g=NULL;
00438 }
00439
00440
00441 float64_t LaRankOutput::computeScore (int32_t x_id)
00442 {
00443 if (l == 0)
00444 return 0;
00445 else
00446 {
00447 float32_t *row = larank_kcache_query_row (kernel, x_id, l);
00448 return CMath::dot (beta, row, l);
00449 }
00450 }
00451
00452
00453 float64_t LaRankOutput::computeGradient (int32_t xi_id, int32_t yi, int32_t ythis)
00454 {
00455 return (yi == ythis ? 1 : 0) - computeScore (xi_id);
00456 }
00457
00458
00459 void LaRankOutput::update (int32_t x_id, float64_t lambda, float64_t gp)
00460 {
00461 int32_t *r2i = larank_kcache_r2i (kernel, l);
00462 int64_t xr = l + 1;
00463 for (int32_t r = 0; r < l; r++)
00464 if (r2i[r] == x_id)
00465 {
00466 xr = r;
00467 break;
00468 }
00469
00470
00471 if (xr < l)
00472 {
00473 beta[xr]+=lambda;
00474 }
00475 else
00476 {
00477 larank_kcache_swap_ri (kernel, l, x_id);
00478 CMath::resize(g, l, l+1);
00479 CMath::resize(beta, l, l+1);
00480 g[l]=gp;
00481 beta[l]=lambda;
00482 l++;
00483 }
00484
00485
00486 float32_t *row = larank_kcache_query_row (kernel, x_id, l);
00487 for (int32_t r = 0; r < l; r++)
00488 {
00489 float64_t oldg = g[r];
00490 g[r]=oldg - lambda * row[r];
00491 }
00492 }
00493
00494
00495
00496 void LaRankOutput::set_kernel_buddy (larank_kcache_t * bud)
00497 {
00498 larank_kcache_set_buddy (bud, kernel);
00499 }
00500
00501
00502 int32_t LaRankOutput::cleanup ()
00503 {
00504 int32_t count = 0;
00505 std::vector < int32_t >idx;
00506 for (int32_t x = 0; x < l; x++)
00507 {
00508 if ((beta[x] < FLT_EPSILON) && (beta[x] > -FLT_EPSILON))
00509 {
00510 idx.push_back (x);
00511 count++;
00512 }
00513 }
00514 int32_t new_l = l - count;
00515 for (int32_t xx = 0; xx < count; xx++)
00516 {
00517 int32_t i = idx[xx] - xx;
00518 for (int32_t r = i; r < (l - 1); r++)
00519 {
00520 larank_kcache_swap_rr (kernel, r, int64_t(r) + 1);
00521 beta[r]=beta[r + 1];
00522 g[r]=g[r + 1];
00523 }
00524 }
00525 CMath::resize(beta, l, new_l+1);
00526 CMath::resize(g, l, new_l+1);
00527 beta[new_l]=0;
00528 g[new_l]=0;
00529 l = new_l;
00530 return count;
00531 }
00532
00533
00534
00535 float64_t LaRankOutput::getW2 ()
00536 {
00537 float64_t sum = 0;
00538 int32_t *r2i = larank_kcache_r2i (kernel, l + 1);
00539 for (int32_t r = 0; r < l; r++)
00540 {
00541 float32_t *row_r = larank_kcache_query_row (kernel, r2i[r], l);
00542 sum += beta[r] * CMath::dot (beta, row_r, l);
00543 }
00544 return sum;
00545 }
00546
00547 float64_t LaRankOutput::getKii (int32_t x_id)
00548 {
00549 return larank_kcache_query (kernel, x_id, x_id);
00550 }
00551
00552
00553 float64_t LaRankOutput::getBeta (int32_t x_id)
00554 {
00555 int32_t *r2i = larank_kcache_r2i (kernel, l);
00556 int32_t xr = -1;
00557 for (int32_t r = 0; r < l; r++)
00558 if (r2i[r] == x_id)
00559 {
00560 xr = r;
00561 break;
00562 }
00563 return (xr < 0 ? 0 : beta[xr]);
00564 }
00565
00566
00567 float64_t LaRankOutput::getGradient (int32_t x_id)
00568 {
00569 int32_t *r2i = larank_kcache_r2i (kernel, l);
00570 int32_t xr = -1;
00571 for (int32_t r = 0; r < l; r++)
00572 if (r2i[r] == x_id)
00573 {
00574 xr = r;
00575 break;
00576 }
00577 return (xr < 0 ? 0 : g[xr]);
00578 }
00579 bool LaRankOutput::isSupportVector (int32_t x_id) const
00580 {
00581 int32_t *r2i = larank_kcache_r2i (kernel, l);
00582 int32_t xr = -1;
00583 for (int32_t r = 0; r < l; r++)
00584 if (r2i[r] == x_id)
00585 {
00586 xr = r;
00587 break;
00588 }
00589 return (xr >= 0);
00590 }
00591
00592
00593 int32_t LaRankOutput::getSV (float32_t* &sv) const
00594 {
00595 sv=new float32_t[l];
00596 int32_t *r2i = larank_kcache_r2i (kernel, l);
00597 for (int32_t r = 0; r < l; r++)
00598 sv[r]=r2i[r];
00599 return l;
00600 }
00601
00602 CLaRank::CLaRank (): CMultiClassSVM(ONE_VS_REST),
00603 nb_seen_examples (0), nb_removed (0),
00604 n_pro (0), n_rep (0), n_opt (0),
00605 w_pro (1), w_rep (1), w_opt (1), y0 (0), dual (0),
00606 batch_mode(true), step(0)
00607 {
00608 }
00609
00610 CLaRank::CLaRank (float64_t C, CKernel* k, CLabels* lab):
00611 CMultiClassSVM(ONE_VS_REST, C, k, lab),
00612 nb_seen_examples (0), nb_removed (0),
00613 n_pro (0), n_rep (0), n_opt (0),
00614 w_pro (1), w_rep (1), w_opt (1), y0 (0), dual (0),
00615 batch_mode(true), step(0)
00616 {
00617 }
00618
00619 CLaRank::~CLaRank ()
00620 {
00621 destroy();
00622 }
00623
00624 bool CLaRank::train(CFeatures* data)
00625 {
00626 tau = 0.0001;
00627
00628 ASSERT(kernel);
00629 ASSERT(labels && labels->get_num_labels());
00630
00631 CSignal::clear_cancel();
00632
00633 if (data)
00634 {
00635 if (data->get_num_vectors() != labels->get_num_labels())
00636 {
00637 SG_ERROR("Numbert of vectors (%d) does not match number of labels (%d)\n",
00638 data->get_num_vectors(), labels->get_num_labels());
00639 }
00640 kernel->init(data, data);
00641 }
00642
00643 ASSERT(kernel->get_num_vec_lhs() && kernel->get_num_vec_rhs());
00644
00645 nb_train=labels->get_num_labels();
00646 cache = kernel->get_cache_size();
00647
00648 int32_t n_it = 1;
00649 float64_t gap = DBL_MAX;
00650
00651 SG_INFO("Training on %d examples\n", nb_train);
00652 while (gap > C1 && (!CSignal::cancel_computations()))
00653 {
00654 float64_t tr_err = 0;
00655 int32_t ind = step;
00656 for (int32_t i = 0; i < nb_train; i++)
00657 {
00658 int32_t y=labels->get_label(i);
00659 if (add (i, y) != y)
00660 tr_err++;
00661
00662 if (ind && i / ind)
00663 {
00664 SG_DEBUG("Done: %d %% Train error (online): %f%%\n",
00665 (int32_t) (((float64_t) i) / nb_train * 100), (tr_err / ((float64_t) i + 1)) * 100);
00666 ind += step;
00667 }
00668 }
00669
00670 SG_DEBUG("End of iteration %d\n", n_it++);
00671 SG_DEBUG("Train error (online): %f%%\n", (tr_err / nb_train) * 100);
00672 gap = computeGap ();
00673 SG_ABS_PROGRESS(gap, -CMath::log10(gap), -CMath::log10(DBL_MAX), -CMath::log10(C1), 6);
00674
00675 if (!batch_mode)
00676 gap = 0;
00677 }
00678 SG_DONE();
00679
00680 int32_t num_classes = outputs.size();
00681 create_multiclass_svm(num_classes);
00682 SG_DEBUG("%d classes\n", num_classes);
00683
00684
00685 int32_t i=0;
00686 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
00687 {
00688 const LaRankOutput* o=&(it->second);
00689
00690 larank_kcache_t* k=o->getKernel();
00691 int32_t l=o->get_l();
00692 float32_t* beta=o->getBetas();
00693 int32_t *r2i = larank_kcache_r2i (k, l);
00694
00695 ASSERT(l>0);
00696 SG_DEBUG("svm[%d] has %d sv, b=%f\n", i, l, 0.0);
00697
00698 CSVM* svm=new CSVM(l);
00699
00700 for (int32_t j=0; j<l; j++)
00701 {
00702 svm->set_alpha(j, beta[j]);
00703 svm->set_support_vector(j, r2i[j]);
00704 }
00705
00706 svm->set_bias(0);
00707 set_svm(i, svm);
00708 i++;
00709 }
00710 destroy();
00711
00712 return true;
00713 }
00714
00715
00716 int32_t CLaRank::add (int32_t x_id, int32_t yi)
00717 {
00718 ++nb_seen_examples;
00719
00720 if (!getOutput (yi))
00721 {
00722 outputs.insert (std::make_pair (yi, LaRankOutput ()));
00723 LaRankOutput *cur = getOutput (yi);
00724 cur->initialize (kernel, cache);
00725 if (outputs.size () == 1)
00726 y0 = outputs.begin ()->first;
00727
00728 if (outputs.size () > 1)
00729 {
00730 LaRankOutput *out0 = getOutput (y0);
00731 cur->set_kernel_buddy (out0->getKernel ());
00732 }
00733 }
00734
00735 LaRankPattern tpattern (x_id, yi);
00736 LaRankPattern & pattern = (patterns.isPattern (x_id)) ? patterns.getPattern (x_id) : tpattern;
00737
00738
00739 float64_t time1 = CTime::get_curtime();
00740 process_return_t pro_ret = process (pattern, processNew);
00741 float64_t dual_increase = pro_ret.dual_increase;
00742 float64_t duration = (CTime::get_curtime() - time1);
00743 float64_t coeff = dual_increase / (0.00001 + duration);
00744 dual += dual_increase;
00745 n_pro++;
00746 w_pro = 0.05 * coeff + (1 - 0.05) * w_pro;
00747
00748
00749
00750 for (;;)
00751 {
00752 float64_t w_sum = w_pro + w_rep + w_opt;
00753 float64_t prop_min = w_sum / 20;
00754 if (w_pro < prop_min)
00755 w_pro = prop_min;
00756 if (w_rep < prop_min)
00757 w_rep = prop_min;
00758 if (w_opt < prop_min)
00759 w_opt = prop_min;
00760 w_sum = w_pro + w_rep + w_opt;
00761 float64_t r = CMath::random(0.0, w_sum);
00762 if (r <= w_pro)
00763 {
00764 break;
00765 }
00766 else if ((r > w_pro) && (r <= w_pro + w_rep))
00767 {
00768 float64_t ltime1 = CTime::get_curtime ();
00769 float64_t ldual_increase = reprocess ();
00770 float64_t lduration = (CTime::get_curtime () - ltime1);
00771 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
00772 dual += ldual_increase;
00773 n_rep++;
00774 w_rep = 0.05 * lcoeff + (1 - 0.05) * w_rep;
00775 }
00776 else
00777 {
00778 float64_t ltime1 = CTime::get_curtime ();
00779 float64_t ldual_increase = optimize ();
00780 float64_t lduration = (CTime::get_curtime () - ltime1);
00781 float64_t lcoeff = ldual_increase / (0.00001 + lduration);
00782 dual += ldual_increase;
00783 n_opt++;
00784 w_opt = 0.05 * lcoeff + (1 - 0.05) * w_opt;
00785 }
00786 }
00787 if (nb_seen_examples % 100 == 0)
00788 nb_removed += cleanup ();
00789 return pro_ret.ypred;
00790 }
00791
00792
00793 int32_t CLaRank::predict (int32_t x_id)
00794 {
00795 int32_t res = -1;
00796 float64_t score_max = -DBL_MAX;
00797 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
00798 {
00799 float64_t score = it->second.computeScore (x_id);
00800 if (score > score_max)
00801 {
00802 score_max = score;
00803 res = it->first;
00804 }
00805 }
00806 return res;
00807 }
00808
00809 void CLaRank::destroy ()
00810 {
00811 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end ();++it)
00812 it->second.destroy ();
00813 }
00814
00815
00816
00817 float64_t CLaRank::computeGap ()
00818 {
00819 float64_t sum_sl = 0;
00820 float64_t sum_bi = 0;
00821 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
00822 {
00823 const LaRankPattern & p = patterns[i];
00824 if (!p.exists ())
00825 continue;
00826 LaRankOutput *out = getOutput (p.y);
00827 if (!out)
00828 continue;
00829 sum_bi += out->getBeta (p.x_id);
00830 float64_t gi = out->computeGradient (p.x_id, p.y, p.y);
00831 float64_t gmin = DBL_MAX;
00832 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
00833 {
00834 if (it->first != p.y && it->second.isSupportVector (p.x_id))
00835 {
00836 float64_t g =
00837 it->second.computeGradient (p.x_id, p.y, it->first);
00838 if (g < gmin)
00839 gmin = g;
00840 }
00841 }
00842 sum_sl += CMath::max (0.0, gi - gmin);
00843 }
00844 return CMath::max (0.0, computeW2 () + C1 * sum_sl - sum_bi);
00845 }
00846
00847
00848 uint32_t CLaRank::getNumOutputs () const
00849 {
00850 return outputs.size ();
00851 }
00852
00853
00854 int32_t CLaRank::getNSV ()
00855 {
00856 int32_t res = 0;
00857 for (outputhash_t::const_iterator it = outputs.begin (); it != outputs.end (); ++it)
00858 {
00859 float32_t* sv=NULL;
00860 res += it->second.getSV (sv);
00861 delete[] sv;
00862 }
00863 return res;
00864 }
00865
00866
00867 float64_t CLaRank::computeW2 ()
00868 {
00869 float64_t res = 0;
00870 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
00871 {
00872 const LaRankPattern & p = patterns[i];
00873 if (!p.exists ())
00874 continue;
00875 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
00876 if (it->second.getBeta (p.x_id))
00877 res += it->second.getBeta (p.x_id) * it->second.computeScore (p.x_id);
00878 }
00879 return res;
00880 }
00881
00882
00883 float64_t CLaRank::getDual ()
00884 {
00885 float64_t res = 0;
00886 for (uint32_t i = 0; i < patterns.maxcount (); ++i)
00887 {
00888 const LaRankPattern & p = patterns[i];
00889 if (!p.exists ())
00890 continue;
00891 LaRankOutput *out = getOutput (p.y);
00892 if (!out)
00893 continue;
00894 res += out->getBeta (p.x_id);
00895 }
00896 return res - computeW2 () / 2;
00897 }
00898
00899 LaRankOutput *CLaRank::getOutput (int32_t index)
00900 {
00901 outputhash_t::iterator it = outputs.find (index);
00902 return it == outputs.end ()? NULL : &it->second;
00903 }
00904
00905
00906 CLaRank::process_return_t CLaRank::process (const LaRankPattern & pattern, process_type ptype)
00907 {
00908 process_return_t pro_ret = process_return_t (0, 0);
00909
00910
00911
00912
00913 std::vector < outputgradient_t > outputgradients;
00914
00915 outputgradients.reserve (getNumOutputs ());
00916
00917 std::vector < outputgradient_t > outputscores;
00918 outputscores.reserve (getNumOutputs ());
00919
00920 for (outputhash_t::iterator it = outputs.begin (); it != outputs.end (); ++it)
00921 {
00922 if (ptype != processOptimize
00923 || it->second.isSupportVector (pattern.x_id))
00924 {
00925 float64_t g =
00926 it->second.computeGradient (pattern.x_id, pattern.y, it->first);
00927 outputgradients.push_back (outputgradient_t (it->first, g));
00928 if (it->first == pattern.y)
00929 outputscores.push_back (outputgradient_t (it->first, (1 - g)));
00930 else
00931 outputscores.push_back (outputgradient_t (it->first, -g));
00932 }
00933 }
00934
00935 std::sort (outputgradients.begin (), outputgradients.end ());
00936
00937
00938
00939
00940 std::sort (outputscores.begin (), outputscores.end ());
00941 pro_ret.ypred = outputscores[0].output;
00942
00943
00944
00945
00946 outputgradient_t ygp;
00947 LaRankOutput *outp = NULL;
00948 uint32_t p;
00949 for (p = 0; p < outputgradients.size (); ++p)
00950 {
00951 outputgradient_t & current = outputgradients[p];
00952 LaRankOutput *output = getOutput (current.output);
00953 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
00954 bool goodclass = current.output == pattern.y;
00955 if ((!support && goodclass) ||
00956 (support && output->getBeta (pattern.x_id) < (goodclass ? C1 : 0)))
00957 {
00958 ygp = current;
00959 outp = output;
00960 break;
00961 }
00962 }
00963 if (p == outputgradients.size ())
00964 return pro_ret;
00965
00966
00967
00968
00969 outputgradient_t ygm;
00970 LaRankOutput *outm = NULL;
00971 int32_t m;
00972 for (m = outputgradients.size () - 1; m >= 0; --m)
00973 {
00974 outputgradient_t & current = outputgradients[m];
00975 LaRankOutput *output = getOutput (current.output);
00976 bool support = ptype == processOptimize || output->isSupportVector (pattern.x_id);
00977 bool goodclass = current.output == pattern.y;
00978 if (!goodclass || (support && output->getBeta (pattern.x_id) > 0))
00979 {
00980 ygm = current;
00981 outm = output;
00982 break;
00983 }
00984 }
00985 if (m < 0)
00986 return pro_ret;
00987
00988
00989
00990
00991 if ((ygp.gradient - ygm.gradient) < tau)
00992 return pro_ret;
00993 if (ptype == processNew)
00994 patterns.insert (pattern);
00995
00996
00997
00998
00999 float64_t kii = outp->getKii (pattern.x_id);
01000 float64_t lambda = (ygp.gradient - ygm.gradient) / (2 * kii);
01001 if (ptype == processOptimize || outp->isSupportVector (pattern.x_id))
01002 {
01003 float64_t beta = outp->getBeta (pattern.x_id);
01004 if (ygp.output == pattern.y)
01005 lambda = CMath::min (lambda, C1 - beta);
01006 else
01007 lambda = CMath::min (lambda, fabs (beta));
01008 }
01009 else
01010 lambda = CMath::min (lambda, C1);
01011
01012
01013
01014
01015 outp->update (pattern.x_id, lambda, ygp.gradient);
01016 outm->update (pattern.x_id, -lambda, ygm.gradient);
01017
01018 pro_ret.dual_increase = lambda * ((ygp.gradient - ygm.gradient) - lambda * kii);
01019 return pro_ret;
01020 }
01021
01022
01023 float64_t CLaRank::reprocess ()
01024 {
01025 if (patterns.size ())
01026 {
01027 for (int32_t n = 0; n < 10; ++n)
01028 {
01029 process_return_t pro_ret = process (patterns.sample (), processOld);
01030 if (pro_ret.dual_increase)
01031 return pro_ret.dual_increase;
01032 }
01033 }
01034 return 0;
01035 }
01036
01037
01038 float64_t CLaRank::optimize ()
01039 {
01040 float64_t dual_increase = 0;
01041 if (patterns.size ())
01042 {
01043 for (int32_t n = 0; n < 10; ++n)
01044 {
01045 process_return_t pro_ret =
01046 process (patterns.sample(), processOptimize);
01047 dual_increase += pro_ret.dual_increase;
01048 }
01049 }
01050 return dual_increase;
01051 }
01052
01053
01054 uint32_t CLaRank::cleanup ()
01055 {
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072 return 0;
01073 }