34 #include <shogun/lib/external/pr_loqo.h>
49 using namespace shogun;
51 #ifndef DOXYGEN_SHOULD_SKIP_THIS
52 struct S_THREAD_PARAM_REACTIVATE_LINADD
63 struct S_THREAD_PARAM_SVMLIGHT
68 int32_t * active2dnum ;
73 struct S_THREAD_PARAM_REACTIVATE_VANILLA
80 int32_t* changed2dnum;
81 int32_t* inactive2dnum;
87 struct S_THREAD_PARAM_KERNEL
95 #endif // DOXYGEN_SHOULD_SKIP_THIS
99 S_THREAD_PARAM_SVMLIGHT* params = (S_THREAD_PARAM_SVMLIGHT*) p;
103 for (jj=params->start;(jj<params->end) && (j=params->active2dnum[jj])>=0;jj++)
104 params->lin[j]+=params->kernel->compute_optimized(params->docs[j]);
111 S_THREAD_PARAM_KERNEL* params = (S_THREAD_PARAM_KERNEL*) p;
114 for (jj=params->start;jj<params->end;jj++)
115 params->Kval[jj]=params->svmlight->compute_kernel(params->KI[jj], params->KJ[jj]) ;
147 model=SG_MALLOC(MODEL, 1);
161 SG_FREE(
model->supvec);
162 SG_FREE(
model->alpha);
163 SG_FREE(
model->index);
206 SG_ERROR(
"SVM_light can not proceed without kernel!\n")
212 SG_ERROR(
"%s::train_machine(): Number of training vectors (%d) does"
213 " not match number of labels (%d)\n",
get_name(),
220 SG_ERROR(
"SVM_light can not proceed without initialized kernel!\n")
268 for (int32_t i=0; i<
model->sv_num-1; i++)
297 int32_t *inconsistent, i;
298 int32_t misclassified,upsupvecnum;
301 int32_t trainpos=0, trainneg=0 ;
304 int32_t totdoc=lab.
vlen;
308 int32_t* docs=SG_MALLOC(int32_t, totdoc);
320 for (i=0; i<totdoc; i++)
325 TIMING timing_profile;
326 SHRINK_STATE shrink_state;
328 timing_profile.time_kernel=0;
329 timing_profile.time_opti=0;
330 timing_profile.time_shrink=0;
331 timing_profile.time_update=0;
332 timing_profile.time_model=0;
333 timing_profile.time_check=0;
334 timing_profile.time_select=0;
344 inconsistent = SG_MALLOC(int32_t, totdoc);
347 a_fullset = SG_MALLOC(
float64_t, totdoc);
348 xi_fullset = SG_MALLOC(
float64_t, totdoc);
360 SG_FREE(
model->supvec);
361 SG_FREE(
model->alpha);
362 SG_FREE(
model->index);
363 model->supvec = SG_MALLOC(int32_t, totdoc+2);
365 model->index = SG_MALLOC(int32_t, totdoc+2);
367 model->at_upper_bound=0;
371 model->totdoc=totdoc;
377 model->loo_recall=-1;
378 model->loo_precision=-1;
381 model->xa_precision=-1;
383 for (i=0;i<totdoc;i++) {
395 else if(label[i] < 0) {
410 SG_INFO(
"Computing starting state...")
415 for (i=0; i<totdoc; i++)
421 int32_t* index = SG_MALLOC(int32_t, totdoc);
422 int32_t* index2dnum = SG_MALLOC(int32_t, totdoc+11);
424 for (i=0;i<totdoc;i++) {
426 alpha[i]=fabs(alpha[i]);
427 if(alpha[i]<0) alpha[i]=0;
441 for (i=0;i<totdoc;i++)
442 if((alpha[i]>0) && (alpha[i]<
learn_parm->svm_cost[i])
446 for (i=0;i<totdoc;i++)
456 for (i=0;i<totdoc;i++)
457 if((alpha[i]>0) && (alpha[i]<
learn_parm->svm_cost[i])
461 for (i=0;i<totdoc;i++)
471 index2dnum,index2dnum);
472 for (i=0;i<totdoc;i++) {
484 SG_DEBUG(
"%d totdoc %d pos %d neg\n", totdoc, trainpos, trainneg)
489 &shrink_state,inconsistent,a,lin,
491 &maxdiff,(int32_t)-1,
499 SG_DEBUG(
"(%ld iterations)", iterations)
503 for (i=0;(i<totdoc);i++) {
508 SG_INFO(
"Optimization finished (%ld misclassified, maxdiff=%.8f).\n",
509 misclassified,maxdiff);
513 SG_WARNING(
"maximum violation (%f) exceeds svm_epsilon (%f) due to numerical difficulties\n", maxdiff,
epsilon)
516 for (i=1;i<
model->sv_num;i++)
518 if(fabs(
model->alpha[i]) >=
523 SG_INFO(
"Number of SV: %d (including %d at upper bound)\n",
524 model->sv_num-1,upsupvecnum);
529 SG_FREE(inconsistent);
541 SHRINK_STATE *shrink_state,
542 int32_t *inconsistent,
544 TIMING *timing_profile,
float64_t *maxdiff,
545 int32_t heldout, int32_t retrain)
564 int32_t *chosen,*key,i,j,jj,*last_suboptimal_at,noshrink;
565 int32_t inconsistentnum,choosenum,already_chosen=0,iteration;
566 int32_t misclassified,supvecnum=0,*active2dnum,inactivenum;
567 int32_t *working2dnum,*selexam;
571 int32_t t0=0,t1=0,t2=0,t3=0,t4=0,t5=0,t6=0;
575 int32_t bestmaxdiffiter,terminate;
576 bool reactivated=
false;
591 chosen = SG_MALLOC(int32_t, totdoc);
592 last_suboptimal_at =SG_MALLOC(int32_t, totdoc);
593 key =SG_MALLOC(int32_t, totdoc+11);
595 selexam =SG_MALLOC(int32_t, totdoc);
598 working2dnum =SG_MALLOC(int32_t, totdoc+11);
599 active2dnum =SG_MALLOC(int32_t, totdoc+11);
610 if(!retrain) retrain=1;
613 bestmaxdiff=999999999;
620 for (i=0;i<totdoc;i++) {
623 last_suboptimal_at[i]=1;
627 activenum=
compute_index(shrink_state->active,totdoc,active2dnum);
628 inactivenum=totdoc-activenum;
648 SG_DEBUG(
"\nSelecting working set... ")
655 for (jj=0;(j=working2dnum[jj])>=0;jj++) {
673 for (jj=0;(j=working2dnum[jj])>=0;jj++) {
677 for (i=0;i<totdoc;i++) {
678 if((inconsistent[i] || (heldout==i)) && (a[i] != 0.0)) {
686 for (i=0;i<totdoc;i++) {
689 for (i=0;(i<totdoc) && (fabs(eq) >
learn_parm->epsilon_a);i++) {
690 if((eq*label[i] > 0) && (a[i] > 0)) {
693 if((eq*label[i]) > a[i]) {
716 label,a,lin,c,totdoc,
719 inconsistent,active2dnum,
720 working2dnum,selcrit,selexam,1,
722 choosenum+=already_chosen;
725 label,a,lin,c,totdoc,
728 inconsistent,active2dnum,
729 working2dnum,selcrit,selexam,0,key,
736 label,a,lin,c,totdoc,
739 inconsistent,active2dnum,
740 working2dnum,selcrit,selexam,key,
746 SG_INFO(
" %ld vectors chosen\n",choosenum)
774 optimize_svm(docs,label,inconsistent,0.0,chosen,active2dnum,
775 totdoc,working2dnum,choosenum,a,lin,c,
776 aicache,&qp,&epsilon_crit_org);
788 for (jj=0;(i=working2dnum[jj])>=0;jj++) {
793 maxdiff,epsilon_crit_org,&misclassified,
794 inconsistent,active2dnum,last_suboptimal_at,
799 timing_profile->time_select+=t1-t0;
800 timing_profile->time_kernel+=t2-t1;
801 timing_profile->time_opti+=t3-t2;
802 timing_profile->time_update+=t4-t3;
803 timing_profile->time_model+=t5-t4;
804 timing_profile->time_check+=t6-t5;
808 if((*maxdiff) < bestmaxdiff) {
809 bestmaxdiff=(*maxdiff);
810 bestmaxdiffiter=iteration;
812 if(iteration > (bestmaxdiffiter+
learn_parm->maxiter)) {
816 SG_WARNING(
"Relaxing KT-Conditions due to slow progress! Terminating!\n")
817 SG_DEBUG(
"(iteration :%d, bestmaxdiffiter: %d, lean_param->maxiter: %d)\n", iteration, bestmaxdiffiter,
learn_parm->maxiter )
822 if ((!
callback) && (!retrain) && (inactivenum>0) &&
826 SG_DEBUG(
"reactivating inactive examples\n")
829 iteration,inconsistent,
833 SG_DEBUG(
"done reactivating inactive examples (maxdiff:%8f eps_crit:%8f orig_eps:%8f)\n", *maxdiff,
learn_parm->epsilon_crit, epsilon_crit_org)
835 activenum=
compute_index(shrink_state->active,totdoc,active2dnum);
836 inactivenum=totdoc-activenum;
838 bestmaxdiff=(*maxdiff);
839 bestmaxdiffiter=iteration;
846 SG_INFO(
"restarting optimization as we are - due to shrinking - deviating too much (maxdiff(%f) > eps(%f))\n", *maxdiff,
learn_parm->epsilon_crit)
853 SG_DEBUG(
"Number of inactive variables = %ld\n", inactivenum)
857 if((!retrain) && (
learn_parm->epsilon_crit>(*maxdiff)))
859 if((!retrain) && (
learn_parm->epsilon_crit>epsilon_crit_org)) {
868 SG_INFO(
" => (%ld SV (incl. %ld SV at u-bound), max violation=%.5f)\n",
869 supvecnum,
model->at_upper_bound,(*maxdiff));
875 if (((iteration % 10) == 0) && (!noshrink) && !
callback)
877 activenum=
shrink_problem(shrink_state,active2dnum,last_suboptimal_at,iteration,totdoc,
879 CMath::max((int32_t)(totdoc/500),(int32_t) 100)),
880 a,inconsistent, c, lin, label);
882 inactivenum=totdoc-activenum;
889 shrink_state->active);
893 if (bestmaxdiff>worstmaxdiff)
894 worstmaxdiff=bestmaxdiff;
906 SG_DEBUG(
"inactive:%d\n", inactivenum)
908 if (inactivenum && !reactivated && !
callback)
910 SG_DEBUG(
"reactivating inactive examples\n")
912 iteration,inconsistent,
915 SG_DEBUG(
"done reactivating inactive examples\n")
917 activenum=
compute_index(shrink_state->active,totdoc,active2dnum);
918 inactivenum=totdoc-activenum;
920 bestmaxdiff=(*maxdiff);
921 bestmaxdiffiter=iteration;
929 SG_FREE(last_suboptimal_at);
935 SG_FREE(working2dnum);
936 SG_FREE(active2dnum);
941 SG_FREE(qp.opt_xinit);
959 for (int32_t i=0;i<totdoc;i++)
960 criterion=criterion+(eps[i]-(
float64_t)label[i]*c[i])*a[i]+0.5*a[i]*label[i]*lin[i];
976 for (i=0;index[i] != -1;i++);
982 int32_t *binfeature, int32_t range, int32_t *index)
985 register int32_t i,ii;
988 for (i=0;i<range;i++) {
1002 int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
1003 float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t totdoc,
1017 exclude_from_eq_const,eq_target,chosen,
1018 active2dnum,working2dnum,a,lin,c,
1019 varnum,totdoc,aicache,qp);
1034 for (i=0;i<varnum;i++)
1035 a[working2dnum[i]]=a_v[i];
1039 int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
1040 float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t *key,
1047 chosen, active2dnum, key, a, lin, c,
1048 varnum, totdoc, aicache, qp) ;
1053 register int32_t ki,kj,i,j;
1057 qp->opt_ce0[0]=-eq_target;
1058 for (j=1;j<
model->sv_num;j++) {
1059 if((!chosen[
model->supvec[j]])
1060 && (!exclude_from_eq_const[(
model->supvec[j])])) {
1061 qp->opt_ce0[0]+=
model->alpha[j];
1070 for (i=0;i<varnum;i++) {
1071 qp->opt_g0[i]=lin[key[i]];
1075 int32_t *KI=SG_MALLOC(int32_t, varnum*varnum);
1076 int32_t *KJ=SG_MALLOC(int32_t, varnum*varnum);
1079 for (i=0;i<varnum;i++) {
1084 for (j=i+1;j<varnum;j++)
1092 ASSERT(Knum<=varnum*(varnum+1)/2)
1100 params[t].svmlight =
this;
1101 params[t].start = t*step;
1102 params[t].end = (t+1)*step;
1105 params[t].Kval=Kval ;
1112 pthread_join(threads[t], NULL);
1118 for (i=0;i<varnum;i++) {
1122 qp->opt_ce[i]=label[ki];
1126 kernel_temp=Kval[Knum] ;
1129 qp->opt_g0[i]-=(kernel_temp*a[ki]*(
float64_t)label[ki]);
1131 qp->opt_g[varnum*i+i]=kernel_temp;
1133 for (j=i+1;j<varnum;j++) {
1135 kernel_temp=Kval[Knum] ;
1138 qp->opt_g0[i]-=(kernel_temp*a[kj]*(
float64_t)label[kj]);
1139 qp->opt_g0[j]-=(kernel_temp*a[ki]*(
float64_t)label[ki]);
1142 qp->opt_g[varnum*j+i]=qp->opt_g[varnum*i+j];
1156 for (i=0;i<varnum;i++) {
1158 qp->opt_xinit[i]=a[key[i]];
1171 int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
1172 float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t *key,
1176 register int32_t ki,kj,i,j;
1180 qp->opt_ce0[0]=-eq_target;
1181 for (j=1;j<
model->sv_num;j++) {
1182 if((!chosen[
model->supvec[j]])
1183 && (!exclude_from_eq_const[(
model->supvec[j])])) {
1184 qp->opt_ce0[0]+=
model->alpha[j];
1193 for (i=0;i<varnum;i++) {
1194 qp->opt_g0[i]=lin[key[i]];
1197 for (i=0;i<varnum;i++) {
1201 qp->opt_ce[i]=label[ki];
1207 qp->opt_g0[i]-=(kernel_temp*a[ki]*(
float64_t)label[ki]);
1209 qp->opt_g[varnum*i+i]=kernel_temp;
1211 for (j=i+1;j<varnum;j++) {
1216 qp->opt_g0[i]-=(kernel_temp*a[kj]*(
float64_t)label[kj]);
1217 qp->opt_g0[j]-=(kernel_temp*a[ki]*(
float64_t)label[ki]);
1220 qp->opt_g[varnum*j+i]=qp->opt_g[varnum*i+j];
1230 for (i=0;i<varnum;i++) {
1232 qp->opt_xinit[i]=a[key[i]];
1249 int32_t i,ii,pos,b_calculated=0,first_low,first_high;
1261 for (ii=0;(i=working2dnum[ii])>=0;ii++) {
1262 if((a_old[i]>0) && (a[i]==0)) {
1263 pos=
model->index[i];
1270 else if((a_old[i]==0) && (a[i]>0)) {
1276 else if(a_old[i]==a[i]) {
1283 if((a_old[i]>=ex_c) && (a[i]<ex_c)) {
1284 (
model->at_upper_bound)--;
1286 else if((a_old[i]<ex_c) && (a[i]>=ex_c)) {
1287 (
model->at_upper_bound)++;
1291 && (a[i]>
learn_parm->epsilon_a) && (a[i]<ex_c)) {
1302 && (
model->sv_num-1 ==
model->at_upper_bound)) {
1307 for (ii=0;(i=active2dnum[ii])>=0;ii++) {
1312 if((b_temp>b_low) || (first_low)) {
1319 if((b_temp<b_high) || (first_high)) {
1328 if((b_temp>b_low) || (first_low)) {
1335 if((b_temp<b_high) || (first_high)) {
1345 else if(first_low) {
1349 model->b=-(b_high+b_low)/2.0;
1357 return(
model->sv_num-1);
1363 int32_t *inconsistent, int32_t *active2dnum, int32_t *last_suboptimal_at,
1367 int32_t i,ii,retrain;
1377 for (ii=0;(i=active2dnum[ii])>=0;ii++) {
1378 if((!inconsistent[i]) && label[i]) {
1386 if((a[i]>
learn_parm->epsilon_a) && (dist > target)) {
1387 if((dist-target)>(*maxdiff))
1388 (*maxdiff)=dist-target;
1390 else if((a[i]<ex_c) && (dist < target)) {
1391 if((target-dist)>(*maxdiff))
1392 (*maxdiff)=target-dist;
1401 last_suboptimal_at[i]=iteration;
1404 && (dist < (target+
learn_parm->epsilon_shrink))) {
1405 last_suboptimal_at[i]=iteration;
1407 else if((a[i]>=ex_c)
1408 && (dist > (target-
learn_parm->epsilon_shrink))) {
1409 last_suboptimal_at[i]=iteration;
1415 if((!retrain) && ((*maxdiff) >
learn_parm->epsilon_crit)) {
1422 int32_t* docs, int32_t* label, int32_t *active2dnum,
float64_t *a,
1430 register int32_t i=0,ii=0,j=0,jj=0;
1437 a_old, working2dnum, totdoc, lin, aicache);
1443 int32_t num_working=0;
1444 for (ii=0;(i=working2dnum[ii])>=0;ii++) {
1445 if(a[i] != a_old[i]) {
1455 for (jj=0;(j=active2dnum[jj])>=0;jj++) {
1462 int32_t num_elem = 0 ;
1463 for (jj=0;(j=active2dnum[jj])>=0;jj++) num_elem++ ;
1469 int32_t end = step ;
1473 params[t].kernel =
kernel ;
1474 params[t].lin = lin ;
1475 params[t].docs = docs ;
1476 params[t].active2dnum=active2dnum ;
1477 params[t].start = start ;
1478 params[t].end = end ;
1489 pthread_join(threads[t], &ret) ;
1503 a, a_old, working2dnum, totdoc, lin, aicache);
1506 for (jj=0;(i=working2dnum[jj])>=0;jj++) {
1507 if(a[i] != a_old[i]) {
1509 for (ii=0;(j=active2dnum[ii])>=0;ii++)
1510 lin[j]+=(a[i]-a_old[i])*aicache[j]*(
float64_t)label[i];
1519 int32_t* docs, int32_t* label, int32_t *active2dnum,
float64_t *a,
1525 int32_t num_weights = -1;
1528 ASSERT(num_weights==num_kernels)
1535 int32_t n = 0, i, j ;
1542 if(a[i] != a_old[i])
1546 W[j*num_kernels+n]+=(a[i]-a_old[i])*aicache[j]*(
float64_t)label[i];
1560 for (int32_t i=0; i<num_kernels; i++)
1562 w_backup[i] = old_beta[i] ;
1565 for (int32_t n=0; n<num_kernels; n++)
1570 for (int32_t i=0;i<num;i++)
1572 if(a[i] != a_old[i])
1574 for (int32_t j=0;j<num;j++)
1593 int32_t* docs, int32_t* label, int32_t *active2dnum,
float64_t *a,
1602 int32_t num_weights = -1;
1605 ASSERT(num_weights==num_kernels)
1611 for (int32_t i=0; i<num_kernels; i++)
1613 w_backup[i] = old_beta[i] ;
1621 for (int32_t ii=0, i=0;(i=working2dnum[ii])>=0;ii++) {
1622 if(a[i] != a_old[i]) {
1630 for (int32_t i=0; i<num; i++)
1642 params[t].kernel =
kernel;
1644 params[t].start = t*step;
1645 params[t].end = (t+1)*step;
1653 pthread_join(threads[t], NULL);
1668 S_THREAD_PARAM_SVMLIGHT* params = (S_THREAD_PARAM_SVMLIGHT*) p;
1670 int32_t num_kernels=params->kernel->get_num_subkernels();
1673 for (int32_t i=params->start; i<params->end; i++)
1674 params->kernel->compute_by_subkernel(i,&(params->W[i*num_kernels]));
1687 int nk = (int) num_kernels;
1688 double* alphay = SG_MALLOC(
double, num);
1690 for (int32_t i=0; i<num; i++)
1692 alphay[i]=a[i]*label[i];
1696 for (int32_t i=0; i<num_kernels; i++)
1699 cblas_dgemv(CblasColMajor, CblasNoTrans, num_kernels, (
int) num, 0.5, (
double*)
W,
1700 num_kernels, alphay, 1, 1.0, (
double*) sumw, 1);
1704 for (int32_t i=0; i<num; i++)
1707 for (int32_t d=0; d<num_kernels; d++)
1710 for (int32_t i=0; i<num; i++)
1711 sumw[d] += a[i]*(0.5*label[i]*
W[i*num_kernels+d]);
1723 cblas_dgemv(CblasColMajor, CblasTrans, nk, (
int) num, 1.0, (
double*)
W,
1724 nk, (
double*) new_beta, 1, 0.0, (
double*) lin, 1);
1726 for (int32_t i=0; i<num; i++)
1728 for (int32_t d=0; d<num_kernels; d++)
1730 for (int32_t i=0; i<num; i++)
1731 lin[i] += new_beta[d]*
W[i*num_kernels+d] ;
1742 int32_t qp_size, int32_t *inconsistent, int32_t *active2dnum,
1743 int32_t *working2dnum,
float64_t *selcrit, int32_t *select,
1744 int32_t cache_only, int32_t *key, int32_t *chosen)
1750 int32_t choosenum,i,j,k,activedoc,inum,valid;
1753 for (inum=0;working2dnum[inum]>=0;inum++);
1756 for (i=0;(j=active2dnum[i])>=0;i++) {
1768 && (!((a[j]<=(0+
learn_parm->epsilon_a)) && (s<0)))
1773 && (!inconsistent[j]))
1780 select_top_n(selcrit,activedoc,select,(int32_t)(qp_size/2));
1781 for (k=0;(choosenum<(qp_size/2)) && (k<(qp_size/2)) && (k<activedoc);k++) {
1784 working2dnum[inum+choosenum]=i;
1793 for (i=0;(j=active2dnum[i])>=0;i++) {
1805 && (!((a[j]<=(0+
learn_parm->epsilon_a)) && (s<0)))
1810 && (!inconsistent[j]))
1818 select_top_n(selcrit,activedoc,select,(int32_t)(qp_size/2));
1819 for (k=0;(choosenum<qp_size) && (k<(qp_size/2)) && (k<activedoc);k++) {
1822 working2dnum[inum+choosenum]=i;
1828 working2dnum[inum+choosenum]=-1;
1834 int32_t qp_size, int32_t *inconsistent, int32_t *active2dnum,
1835 int32_t *working2dnum,
float64_t *selcrit, int32_t *select, int32_t *key,
1836 int32_t *chosen, int32_t iteration)
1842 int32_t choosenum,i,j,k,activedoc,inum;
1845 for (inum=0;working2dnum[inum]>=0;inum++);
1848 for (i=0;(j=active2dnum[i])>=0;i++) {
1850 if((!((a[j]<=(0+
learn_parm->epsilon_a)) && (s<0)))
1853 && (!inconsistent[j])
1856 selcrit[activedoc]=(j+iteration) % totdoc;
1861 select_top_n(selcrit,activedoc,select,(int32_t)(qp_size/2));
1862 for (k=0;(choosenum<(qp_size/2)) && (k<(qp_size/2)) && (k<activedoc);k++) {
1865 working2dnum[inum+choosenum]=i;
1873 for (i=0;(j=active2dnum[i])>=0;i++) {
1875 if((!((a[j]<=(0+
learn_parm->epsilon_a)) && (s<0)))
1878 && (!inconsistent[j])
1881 selcrit[activedoc]=(j+iteration) % totdoc;
1886 select_top_n(selcrit,activedoc,select,(int32_t)(qp_size/2));
1887 for (k=0;(choosenum<qp_size) && (k<(qp_size/2)) && (k<activedoc);k++) {
1890 working2dnum[inum+choosenum]=i;
1896 working2dnum[inum+choosenum]=-1;
1903 float64_t *selcrit, int32_t range, int32_t* select, int32_t n)
1905 register int32_t i,j;
1907 for (i=0;(i<n) && (i<range);i++) {
1908 for (j=i;j>=0;j--) {
1909 if((j>0) && (selcrit[select[j-1]]<selcrit[i])){
1910 select[j]=select[j-1];
1919 for (i=n;i<range;i++) {
1920 if(selcrit[i]>selcrit[select[n-1]]) {
1921 for (j=n-1;j>=0;j--) {
1922 if((j>0) && (selcrit[select[j-1]]<selcrit[i])) {
1923 select[j]=select[j-1];
1939 SHRINK_STATE *shrink_state, int32_t totdoc, int32_t maxhistory)
1943 shrink_state->deactnum=0;
1944 shrink_state->active = SG_MALLOC(int32_t, totdoc);
1945 shrink_state->inactive_since = SG_MALLOC(int32_t, totdoc);
1946 shrink_state->a_history = SG_MALLOC(
float64_t*, maxhistory);
1947 shrink_state->maxhistory=maxhistory;
1948 shrink_state->last_lin = SG_MALLOC(
float64_t, totdoc);
1949 shrink_state->last_a = SG_MALLOC(
float64_t, totdoc);
1951 for (i=0;i<totdoc;i++) {
1952 shrink_state->active[i]=1;
1953 shrink_state->inactive_since[i]=0;
1954 shrink_state->last_a[i]=0;
1955 shrink_state->last_lin[i]=0;
1961 SG_FREE(shrink_state->active);
1962 SG_FREE(shrink_state->inactive_since);
1963 if(shrink_state->deactnum > 0)
1964 SG_FREE((shrink_state->a_history[shrink_state->deactnum-1]));
1965 SG_FREE((shrink_state->a_history));
1966 SG_FREE((shrink_state->last_a));
1967 SG_FREE((shrink_state->last_lin));
1971 SHRINK_STATE *shrink_state, int32_t *active2dnum,
1972 int32_t *last_suboptimal_at, int32_t iteration, int32_t totdoc,
1978 int32_t i,ii,change,activenum,lastiter;
1983 for (ii=0;active2dnum[ii]>=0;ii++) {
1986 lastiter=last_suboptimal_at[i];
1988 if(((iteration-lastiter) >
learn_parm->svm_iter_to_shrink)
1989 || (inconsistent[i])) {
1993 if((change>=minshrink)
1994 && (shrink_state->deactnum<shrink_state->maxhistory)) {
2004 shrink_state->a_history[shrink_state->deactnum]=a_old;
2005 for (i=0;i<totdoc;i++) {
2009 for (ii=0;active2dnum[ii]>=0;ii++) {
2011 lastiter=last_suboptimal_at[i];
2012 if(((iteration-lastiter) >
learn_parm->svm_iter_to_shrink)
2013 || (inconsistent[i])) {
2014 shrink_state->active[i]=0;
2015 shrink_state->inactive_since[i]=shrink_state->deactnum;
2018 activenum=
compute_index(shrink_state->active,totdoc,active2dnum);
2019 shrink_state->deactnum++;
2021 shrink_state->deactnum=0;
2025 SG_DEBUG(
"Number of inactive variables = %ld\n", totdoc-activenum)
2033 S_THREAD_PARAM_REACTIVATE_LINADD* params = (S_THREAD_PARAM_REACTIVATE_LINADD*) p;
2038 int32_t* active = params->active;
2039 int32_t* docs = params->docs;
2040 int32_t start = params->start;
2041 int32_t end = params->end;
2043 for (int32_t i=start;i<end;i++)
2056 S_THREAD_PARAM_REACTIVATE_VANILLA* params = (S_THREAD_PARAM_REACTIVATE_VANILLA*) p;
2063 ASSERT(params->changed2dnum)
2064 ASSERT(params->inactive2dnum)
2072 int32_t* changed2dnum = params->changed2dnum;
2073 int32_t* inactive2dnum = params->inactive2dnum;
2074 int32_t* label = params->label;
2075 int32_t start = params->start;
2076 int32_t end = params->end;
2078 for (int32_t ii=start;ii<end;ii++)
2080 int32_t i=changed2dnum[ii];
2085 for (int32_t jj=0;(j=inactive2dnum[jj])>=0;jj++)
2086 lin[j]+=(a[i]-a_old[i])*aicache[j]*(
float64_t)label[i];
2093 float64_t *c, int32_t totdoc, int32_t iteration, int32_t *inconsistent,
2099 register int32_t i,j,ii,jj,t,*changed2dnum,*inactive2dnum;
2100 int32_t *changed,*inactive;
2105 a_old=shrink_state->last_a;
2109 SG_DEBUG(
" clear normal - linadd\n")
2112 int32_t num_modified=0;
2113 for (i=0;i<totdoc;i++) {
2114 if(a[i] != a_old[i]) {
2125 if (num_threads < 2)
2127 S_THREAD_PARAM_REACTIVATE_LINADD params;
2130 params.last_lin=shrink_state->last_lin;
2132 params.active=shrink_state->active;
2140 pthread_t* threads = SG_MALLOC(pthread_t, num_threads-1);
2141 S_THREAD_PARAM_REACTIVATE_LINADD* params = SG_MALLOC(S_THREAD_PARAM_REACTIVATE_LINADD, num_threads);
2142 int32_t step= totdoc/num_threads;
2144 for (t=0; t<num_threads-1; t++)
2148 params[t].last_lin=shrink_state->last_lin;
2149 params[t].docs=docs;
2150 params[t].active=shrink_state->active;
2151 params[t].start = t*step;
2152 params[t].end = (t+1)*step;
2158 params[t].last_lin=shrink_state->last_lin;
2159 params[t].docs=docs;
2160 params[t].active=shrink_state->active;
2161 params[t].start = t*step;
2162 params[t].end = totdoc;
2165 for (t=0; t<num_threads-1; t++)
2166 pthread_join(threads[t], NULL);
2178 int32_t *idx = SG_MALLOC(int32_t, totdoc);
2179 int32_t num_suppvec=0 ;
2181 for (i=0; i<totdoc; i++)
2183 if(a[i] != a_old[i])
2185 alphas[num_suppvec] = (a[i]-a_old[i])*(
float64_t)label[i];
2186 idx[num_suppvec] = i ;
2194 int32_t num_inactive=0;
2195 int32_t* inactive_idx=SG_MALLOC(int32_t, totdoc);
2198 for (i=0;i<totdoc;i++)
2200 if(!shrink_state->active[i])
2202 inactive_idx[j++] = i;
2210 memset(dest, 0,
sizeof(
float64_t)*num_inactive);
2215 for (i=0;i<totdoc;i++) {
2216 if(!shrink_state->active[i]) {
2217 lin[i] = shrink_state->last_lin[i] + dest[j++] ;
2219 shrink_state->last_lin[i]=lin[i];
2226 for (i=0;i<totdoc;i++)
2227 shrink_state->last_lin[i]=lin[i];
2229 SG_FREE(inactive_idx);
2239 changed=SG_MALLOC(int32_t, totdoc);
2240 changed2dnum=SG_MALLOC(int32_t, totdoc+11);
2241 inactive=SG_MALLOC(int32_t, totdoc);
2242 inactive2dnum=SG_MALLOC(int32_t, totdoc+11);
2243 for (t=shrink_state->deactnum-1;(t>=0) && shrink_state->a_history[t];t--)
2248 a_old=shrink_state->a_history[t];
2249 for (i=0;i<totdoc;i++) {
2250 inactive[i]=((!shrink_state->active[i])
2251 && (shrink_state->inactive_since[i] == t));
2252 changed[i]= (a[i] != a_old[i]);
2259 int32_t num_threads=1;
2262 if (num_threads < 2)
2264 for (ii=0;(i=changed2dnum[ii])>=0;ii++) {
2266 for (jj=0;(j=inactive2dnum[jj])>=0;jj++)
2267 lin[j]+=(a[i]-a_old[i])*aicache[j]*(
float64_t)label[i];
2274 int32_t num_changed=0;
2275 for (ii=0;changed2dnum[ii]>=0;ii++)
2280 pthread_t* threads= SG_MALLOC(pthread_t, num_threads-1);
2281 S_THREAD_PARAM_REACTIVATE_VANILLA* params = SG_MALLOC(S_THREAD_PARAM_REACTIVATE_VANILLA, num_threads);
2282 int32_t step= num_changed/num_threads;
2286 memset(tmp_lin, 0,
sizeof(
float64_t)*((
size_t) totdoc)*num_threads);
2288 memset(tmp_aicache, 0,
sizeof(
float64_t)*((
size_t) totdoc)*num_threads);
2291 for (thr=0; thr<num_threads-1; thr++)
2293 params[thr].kernel=
kernel;
2294 params[thr].lin=&tmp_lin[thr*totdoc];
2295 params[thr].aicache=&tmp_aicache[thr*totdoc];
2297 params[thr].a_old=a_old;
2298 params[thr].changed2dnum=changed2dnum;
2299 params[thr].inactive2dnum=inactive2dnum;
2300 params[thr].label=label;
2301 params[thr].start = thr*step;
2302 params[thr].end = (thr+1)*step;
2306 params[thr].kernel=
kernel;
2307 params[thr].lin=&tmp_lin[thr*totdoc];
2308 params[thr].aicache=&tmp_aicache[thr*totdoc];
2310 params[thr].a_old=a_old;
2311 params[thr].changed2dnum=changed2dnum;
2312 params[thr].inactive2dnum=inactive2dnum;
2313 params[thr].label=label;
2314 params[thr].start = thr*step;
2315 params[thr].end = num_changed;
2318 for (jj=0;(j=inactive2dnum[jj])>=0;jj++)
2319 lin[j]+=tmp_lin[totdoc*thr+j];
2321 for (thr=0; thr<num_threads-1; thr++)
2323 pthread_join(threads[thr], NULL);
2326 for (jj=0;(j=inactive2dnum[jj])>=0;jj++)
2327 lin[j]+=tmp_lin[totdoc*thr+j];
2331 SG_FREE(tmp_aicache);
2339 SG_FREE(changed2dnum);
2341 SG_FREE(inactive2dnum);
2345 for (i=0;i<totdoc;i++) {
2346 shrink_state->inactive_since[i]=shrink_state->deactnum-1;
2347 if(!inconsistent[i]) {
2351 if((a[i]>
learn_parm->epsilon_a) && (dist > target)) {
2352 if((dist-target)>(*maxdiff))
2353 (*maxdiff)=dist-target;
2355 else if((a[i]<ex_c) && (dist < target)) {
2356 if((target-dist)>(*maxdiff))
2357 (*maxdiff)=target-dist;
2361 shrink_state->active[i]=1;
2364 shrink_state->active[i]=1;
2366 else if((a[i]>=ex_c)
2367 && (dist > (target-
learn_parm->epsilon_shrink))) {
2368 shrink_state->active[i]=1;
2371 shrink_state->active[i]=1;
2377 for (i=0;i<totdoc;i++) {
2378 (shrink_state->a_history[shrink_state->deactnum-1])[i]=a[i];
2380 for (t=shrink_state->deactnum-2;(t>=0) && shrink_state->a_history[t];t--) {
2381 SG_FREE(shrink_state->a_history[t]);
2382 shrink_state->a_history[t]=0;
2392 int32_t& svm_maxqpsize)
2394 register int32_t i, j, result;
2395 float64_t margin, obj_before, obj_after;
2405 for(i=0;i<qp->opt_n;i++) {
2406 obj_before+=(qp->opt_g0[i]*qp->opt_xinit[i]);
2407 obj_before+=(0.5*qp->opt_xinit[i]*qp->opt_xinit[i]*qp->opt_g[i*qp->opt_n+i]);
2409 obj_before+=(qp->opt_xinit[j]*qp->opt_xinit[i]*qp->opt_g[j*qp->opt_n+i]);
2413 result=STILL_RUNNING;
2414 qp->opt_ce0[0]*=(-1.0);
2418 (margin<=0.9999999) && (result!=OPTIMAL_SOLUTION);) {
2423 result=pr_loqo((int32_t)qp->opt_n,(int32_t)qp->opt_m,
2434 SG_SDEBUG(
"Restarting PR_LOQO with more conservative parameters.\n")
2439 margin=(margin+1.0)/2.0;
2442 SG_SDEBUG(
"Reducing precision of PR_LOQO.\n")
2445 else if(result!=OPTIMAL_SOLUTION) {
2450 SG_SDEBUG(
"Reducing precision of PR_LOQO due to (%ld).\n",result)
2463 for(i=0;i<qp->opt_n;i++) {
2465 dist+=(qp->opt_g0[i]+1.0);
2467 dist+=(
primal[j]*qp->opt_g[j*qp->opt_n+i]);
2469 for(j=i;j<qp->opt_n;j++) {
2470 dist+=(
primal[j]*qp->opt_g[i*qp->opt_n+j]);
2473 if((
primal[i]<(qp->opt_up[i]-epsilon_loqo)) && (dist < (1.0-(*epsilon_crit)))) {
2474 epsilon_loqo=(qp->opt_up[i]-
primal[i])*2.0;
2476 else if((
primal[i]>(0+epsilon_loqo)) && (dist > (1.0+(*epsilon_crit)))) {
2477 epsilon_loqo=
primal[i]*2.0;
2481 for(i=0;i<qp->opt_n;i++) {
2482 if(
primal[i]<=(0+epsilon_loqo)) {
2485 else if(
primal[i]>=(qp->opt_up[i]-epsilon_loqo)) {
2491 for(i=0;i<qp->opt_n;i++) {
2492 obj_after+=(qp->opt_g0[i]*
primal[i]);
2493 obj_after+=(0.5*
primal[i]*
primal[i]*qp->opt_g[i*qp->opt_n+i]);
2495 obj_after+=(
primal[j]*
primal[i]*qp->opt_g[j*qp->opt_n+i]);
2502 for(i=0;i<qp->opt_n;i++) {
2503 primal[i]=qp->opt_xinit[i];
2506 if(svm_maxqpsize>2) {
2511 if(obj_after >= obj_before) {
2515 SG_SDEBUG(
"Increasing Precision of PR_LOQO.\n")
2521 (*epsilon_crit)*=10.0;
2523 SG_SINFO(
"Relaxing epsilon on KT-Conditions.\n")
2528 if(result!=OPTIMAL_SOLUTION) {
2529 SG_SERROR(
"PR_LOQO did not converge.\n")
2530 return(qp->opt_xinit);
2538 #endif //USE_SVMLIGHT