SubGradientSVM.cpp

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 2007-2009 Soeren Sonnenburg
00008  * Written (W) 2007-2008 Vojtech Franc
00009  * Copyright (C) 2007-2009 Fraunhofer Institute FIRST and Max-Planck-Society
00010  */
00011 
00012 #include <shogun/lib/config.h>
00013 #include <shogun/mathematics/Math.h>
00014 #include <shogun/lib/Signal.h>
00015 #include <shogun/lib/Time.h>
00016 #include <shogun/machine/LinearMachine.h>
00017 #include <shogun/classifier/svm/SubGradientSVM.h>
00018 #include <shogun/classifier/svm/QPBSVMLib.h>
00019 #include <shogun/features/DotFeatures.h>
00020 #include <shogun/features/Labels.h>
00021 
00022 #undef DEBUG_SUBGRADIENTSVM
00023 
00024 using namespace shogun;
00025 
00026 CSubGradientSVM::CSubGradientSVM()
00027 : CLinearMachine(), C1(1), C2(1), epsilon(1e-5), qpsize(42),
00028     qpsize_max(2000), use_bias(false), delta_active(0), delta_bound(0)
00029 {
00030 }
00031 
00032 CSubGradientSVM::CSubGradientSVM(
00033     float64_t C, CDotFeatures* traindat, CLabels* trainlab)
00034 : CLinearMachine(), C1(C), C2(C), epsilon(1e-5), qpsize(42),
00035     qpsize_max(2000), use_bias(false), delta_active(0), delta_bound(0)
00036 {
00037     set_features(traindat);
00038     set_labels(trainlab);
00039 }
00040 
00041 
00042 CSubGradientSVM::~CSubGradientSVM()
00043 {
00044 }
00045 
00046 /*
00047 int32_t CSubGradientSVM::find_active(int32_t num_feat, int32_t num_vec, int32_t& num_active, int32_t& num_bound)
00048 {
00049     int32_t delta_active=0;
00050     num_active=0;
00051     num_bound=0;
00052 
00053     for (int32_t i=0; i<num_vec; i++)
00054     {
00055         active[i]=0;
00056 
00057         //within margin/wrong side
00058         if (proj[i] < 1-work_epsilon)
00059         {
00060             idx_active[num_active++]=i;
00061             active[i]=1;
00062         }
00063 
00064         //on margin
00065         if (CMath::abs(proj[i]-1) <= work_epsilon)
00066         {
00067             idx_bound[num_bound++]=i;
00068             active[i]=2;
00069         }
00070 
00071         if (active[i]!=old_active[i])
00072             delta_active++;
00073     }
00074 
00075     return delta_active;
00076 }
00077 */
00078 
00079 int32_t CSubGradientSVM::find_active(
00080     int32_t num_feat, int32_t num_vec, int32_t& num_active, int32_t& num_bound)
00081 {
00082     delta_bound=0;
00083     delta_active=0;
00084     num_active=0;
00085     num_bound=0;
00086 
00087     for (int32_t i=0; i<num_vec; i++)
00088     {
00089         active[i]=0;
00090 
00091         //within margin/wrong side
00092         if (proj[i] < 1-autoselected_epsilon)
00093         {
00094             idx_active[num_active++]=i;
00095             active[i]=1;
00096         }
00097 
00098         //on margin
00099         if (CMath::abs(proj[i]-1) <= autoselected_epsilon)
00100         {
00101             idx_bound[num_bound++]=i;
00102             active[i]=2;
00103         }
00104 
00105         if (active[i]!=old_active[i])
00106             delta_active++;
00107 
00108         if (active[i]==2 && old_active[i]==2)
00109             delta_bound++;
00110     }
00111 
00112 
00113     if (delta_active==0 && work_epsilon<=epsilon) //we converged
00114         return 0;
00115     else if (delta_active==0) //lets decrease work_epsilon
00116     {
00117         work_epsilon=CMath::min(work_epsilon/2, autoselected_epsilon);
00118         work_epsilon=CMath::max(work_epsilon, epsilon);
00119         num_bound=qpsize;
00120     }
00121 
00122     delta_bound=0;
00123     delta_active=0;
00124     num_active=0;
00125     num_bound=0;
00126 
00127     for (int32_t i=0; i<num_vec; i++)
00128     {
00129         tmp_proj[i]=CMath::abs(proj[i]-1);
00130         tmp_proj_idx[i]=i;
00131     }
00132 
00133     CMath::qsort_index(tmp_proj, tmp_proj_idx, num_vec);
00134 
00135     autoselected_epsilon=tmp_proj[CMath::min(qpsize,num_vec-1)];
00136 
00137 #ifdef DEBUG_SUBGRADIENTSVM
00138     //SG_PRINT("autoseleps: %15.15f\n", autoselected_epsilon);
00139 #endif
00140 
00141     if (autoselected_epsilon>work_epsilon)
00142         autoselected_epsilon=work_epsilon;
00143 
00144     if (autoselected_epsilon<epsilon)
00145     {
00146         autoselected_epsilon=epsilon;
00147 
00148         int32_t i=0;
00149         while (i < num_vec && tmp_proj[i] <= autoselected_epsilon)
00150             i++;
00151 
00152         //SG_PRINT("lower bound on epsilon requires %d variables in qp\n", i);
00153 
00154         if (i>=qpsize_max && autoselected_epsilon>epsilon) //qpsize limit
00155         {
00156             SG_INFO("qpsize limit (%d) reached\n", qpsize_max);
00157             int32_t num_in_qp=i;
00158             while (--i>=0 && num_in_qp>=qpsize_max)
00159             {
00160                 if (tmp_proj[i] < autoselected_epsilon)
00161                 {
00162                     autoselected_epsilon=tmp_proj[i];
00163                     num_in_qp--;
00164                 }
00165             }
00166 
00167             //SG_PRINT("new qpsize will be %d, autoeps:%15.15f\n", num_in_qp, autoselected_epsilon);
00168         }
00169     }
00170 
00171     for (int32_t i=0; i<num_vec; i++)
00172     {
00173         active[i]=0;
00174 
00175         //within margin/wrong side
00176         if (proj[i] < 1-autoselected_epsilon)
00177         {
00178             idx_active[num_active++]=i;
00179             active[i]=1;
00180         }
00181 
00182         //on margin
00183         if (CMath::abs(proj[i]-1) <= autoselected_epsilon)
00184         {
00185             idx_bound[num_bound++]=i;
00186             active[i]=2;
00187         }
00188 
00189         if (active[i]!=old_active[i])
00190             delta_active++;
00191 
00192         if (active[i]==2 && old_active[i]==2)
00193             delta_bound++;
00194     }
00195 
00196     //SG_PRINT("delta_bound: %d of %d (%02.2f)\n", delta_bound, num_bound, 100.0*delta_bound/num_bound);
00197     return delta_active;
00198 }
00199 
00200 
00201 void CSubGradientSVM::update_active(int32_t num_feat, int32_t num_vec)
00202 {
00203     for (int32_t i=0; i<num_vec; i++)
00204     {
00205         if (active[i]==1 && old_active[i]!=1)
00206         {
00207             features->add_to_dense_vec(C1*get_label(i), i, sum_CXy_active, num_feat);
00208             if (use_bias)
00209                 sum_Cy_active+=C1*get_label(i);
00210         }
00211         else if (old_active[i]==1 && active[i]!=1)
00212         {
00213             features->add_to_dense_vec(-C1*get_label(i), i, sum_CXy_active, num_feat);
00214             if (use_bias)
00215                 sum_Cy_active-=C1*get_label(i);
00216         }
00217     }
00218 
00219     CMath::swap(active,old_active);
00220 }
00221 
00222 float64_t CSubGradientSVM::line_search(int32_t num_feat, int32_t num_vec)
00223 {
00224     float64_t sum_B = 0;
00225     float64_t A_zero = 0.5*CMath::dot(grad_w, grad_w, num_feat);
00226     float64_t B_zero = -CMath::dot(w, grad_w, num_feat);
00227 
00228     int32_t num_hinge=0;
00229 
00230     for (int32_t i=0; i<num_vec; i++)
00231     {
00232         float64_t p=get_label(i)*(features->dense_dot(i, grad_w, num_feat)+grad_b);
00233         grad_proj[i]=p;
00234         if (p!=0)
00235         {
00236             hinge_point[num_hinge]=(proj[i]-1)/p;
00237             hinge_idx[num_hinge]=i;
00238             num_hinge++;
00239 
00240             if (p<0)
00241                 sum_B+=p;
00242         }
00243     }
00244     sum_B*=C1;
00245 
00246     CMath::qsort_index(hinge_point, hinge_idx, num_hinge);
00247 
00248 
00249     float64_t alpha = hinge_point[0];
00250     float64_t grad_val = 2*A_zero*alpha + B_zero + sum_B;
00251 
00252     //CMath::display_vector(grad_w, num_feat, "grad_w");
00253     //CMath::display_vector(grad_proj, num_vec, "grad_proj");
00254     //CMath::display_vector(hinge_point, num_vec, "hinge_point");
00255     //SG_PRINT("A_zero=%f\n", A_zero);
00256     //SG_PRINT("B_zero=%f\n", B_zero);
00257     //SG_PRINT("sum_B=%f\n", sum_B);
00258     //SG_PRINT("alpha=%f\n", alpha);
00259     //SG_PRINT("grad_val=%f\n", grad_val);
00260 
00261     float64_t old_grad_val = grad_val;
00262     float64_t old_alpha = alpha;
00263 
00264     for (int32_t i=1; i < num_hinge && grad_val < 0; i++)
00265     {
00266         alpha = hinge_point[i];
00267         grad_val = 2*A_zero*alpha + B_zero + sum_B;
00268 
00269         if (grad_val > 0)
00270         {
00271             ASSERT(old_grad_val-grad_val != 0);
00272             float64_t gamma = -grad_val/(old_grad_val-grad_val);
00273             alpha = old_alpha*gamma + (1-gamma)*alpha;
00274         }
00275         else
00276         {
00277             old_grad_val = grad_val;
00278             old_alpha = alpha;
00279 
00280             sum_B = sum_B + CMath::abs(C1*grad_proj[hinge_idx[i]]);
00281             grad_val = 2*A_zero*alpha + B_zero + sum_B;
00282         }
00283     }
00284 
00285     return alpha;
00286 }
00287 
00288 float64_t CSubGradientSVM::compute_min_subgradient(
00289     int32_t num_feat, int32_t num_vec, int32_t num_active, int32_t num_bound)
00290 {
00291     float64_t dir_deriv=0;
00292 
00293     if (num_bound > 0)
00294     {
00295 
00296         CTime t2;
00297         CMath::add(v, 1.0, w, -1.0, sum_CXy_active, num_feat);
00298 
00299         if (num_bound>=qpsize_max && num_it_noimprovement!=10) // if qp gets to large, lets just choose a random beta
00300         {
00301             //SG_PRINT("qpsize too large  (%d>=%d) choosing random subgradient/beta\n", num_bound, qpsize_max);
00302             for (int32_t i=0; i<num_bound; i++)
00303                 beta[i]=CMath::random(0.0,1.0);
00304         }
00305         else
00306         {
00307             memset(beta, 0, sizeof(float64_t)*num_bound);
00308 
00309             float64_t bias_const=0;
00310 
00311             if (use_bias)
00312                 bias_const=1;
00313 
00314             for (int32_t i=0; i<num_bound; i++)
00315             {
00316                 for (int32_t j=i; j<num_bound; j++)
00317                 {
00318                     Z[i*num_bound+j]= 2.0*C1*C1*get_label(idx_bound[i])*get_label(idx_bound[j])* 
00319                         (features->dot(idx_bound[i], features, idx_bound[j]) + bias_const);
00320 
00321                     Z[j*num_bound+i]=Z[i*num_bound+j];
00322 
00323                 }
00324 
00325                 Zv[i]=-2.0*C1*get_label(idx_bound[i])* 
00326                     (features->dense_dot(idx_bound[i], v, num_feat)-sum_Cy_active);
00327             }
00328 
00329             //CMath::display_matrix(Z, num_bound, num_bound, "Z");
00330             //CMath::display_vector(Zv, num_bound, "Zv");
00331             t2.stop();
00332 #ifdef DEBUG_SUBGRADIENTSVM
00333             t2.time_diff_sec(true);
00334 #endif
00335 
00336             CTime t;
00337             CQPBSVMLib solver(Z,num_bound, Zv,num_bound, 1.0);
00338             //solver.set_solver(QPB_SOLVER_GRADDESC);
00339             //solver.set_solver(QPB_SOLVER_GS);
00340 #ifdef USE_CPLEX
00341             solver.set_solver(QPB_SOLVER_CPLEX);
00342 #else
00343             solver.set_solver(QPB_SOLVER_SCAS);
00344 #endif
00345 
00346             solver.solve_qp(beta, num_bound);
00347 
00348             t.stop();
00349 #ifdef DEBUG_SUBGRADIENTSVM
00350             tim+=t.time_diff_sec(true);
00351 #else
00352             tim+=t.time_diff_sec(false);
00353 #endif
00354 
00355             //CMath::display_vector(beta, num_bound, "beta gs");
00356             //solver.set_solver(QPB_SOLVER_CPLEX);
00357             //solver.solve_qp(beta, num_bound);
00358             //CMath::display_vector(beta, num_bound, "beta cplex");
00359 
00360             //CMath::display_vector(grad_w, num_feat, "grad_w");
00361             //SG_PRINT("grad_b:%f\n", grad_b);
00362         }
00363 
00364         CMath::add(grad_w, 1.0, w, -1.0, sum_CXy_active, num_feat);
00365         grad_b = -sum_Cy_active;
00366 
00367         for (int32_t i=0; i<num_bound; i++)
00368         {
00369             features->add_to_dense_vec(-C1*beta[i]*get_label(idx_bound[i]), idx_bound[i], grad_w, num_feat);
00370             if (use_bias)
00371                 grad_b -=  C1 * get_label(idx_bound[i])*beta[i];
00372         }
00373 
00374         dir_deriv = CMath::dot(grad_w, v, num_feat) - grad_b*sum_Cy_active;
00375         for (int32_t i=0; i<num_bound; i++)
00376         {
00377             float64_t val= C1*get_label(idx_bound[i])*(features->dense_dot(idx_bound[i], grad_w, num_feat)+grad_b);
00378             dir_deriv += CMath::max(0.0, val);
00379         }
00380     }
00381     else
00382     {
00383         CMath::add(grad_w, 1.0, w, -1.0, sum_CXy_active, num_feat);
00384         grad_b = -sum_Cy_active;
00385 
00386         dir_deriv = CMath::dot(grad_w, grad_w, num_feat)+ grad_b*grad_b;
00387     }
00388 
00389     return dir_deriv;
00390 }
00391 
00392 float64_t CSubGradientSVM::compute_objective(int32_t num_feat, int32_t num_vec)
00393 {
00394     float64_t result= 0.5 * CMath::dot(w,w, num_feat);
00395     
00396     for (int32_t i=0; i<num_vec; i++)
00397     {
00398         if (proj[i]<1.0)
00399             result += C1 * (1.0-proj[i]);
00400     }
00401 
00402     return result;
00403 }
00404 
00405 void CSubGradientSVM::compute_projection(int32_t num_feat, int32_t num_vec)
00406 {
00407     for (int32_t i=0; i<num_vec; i++)
00408         proj[i]=get_label(i)*(features->dense_dot(i, w, num_feat)+bias);
00409 }
00410 
00411 void CSubGradientSVM::update_projection(float64_t alpha, int32_t num_vec)
00412 {
00413     CMath::vec1_plus_scalar_times_vec2(proj,-alpha, grad_proj, num_vec);
00414 }
00415 
00416 void CSubGradientSVM::init(int32_t num_vec, int32_t num_feat)
00417 {
00418     // alloc normal and bias inited with 0
00419     SG_FREE(w);
00420     w=SG_MALLOC(float64_t, num_feat);
00421     w_dim=num_feat;
00422     memset(w,0,sizeof(float64_t)*num_feat);
00423     //CMath::random_vector(w, num_feat, -1.0, 1.0);
00424     bias=0;
00425     num_it_noimprovement=0;
00426     grad_b=0;
00427     qpsize_limit=5000;
00428 
00429     grad_w=SG_MALLOC(float64_t, num_feat);
00430     memset(grad_w,0,sizeof(float64_t)*num_feat);
00431 
00432     sum_CXy_active=SG_MALLOC(float64_t, num_feat);
00433     memset(sum_CXy_active,0,sizeof(float64_t)*num_feat);
00434 
00435     v=SG_MALLOC(float64_t, num_feat);
00436     memset(v,0,sizeof(float64_t)*num_feat);
00437 
00438     old_v=SG_MALLOC(float64_t, num_feat);
00439     memset(old_v,0,sizeof(float64_t)*num_feat);
00440 
00441     sum_Cy_active=0;
00442 
00443     proj= SG_MALLOC(float64_t, num_vec);
00444     memset(proj,0,sizeof(float64_t)*num_vec);
00445 
00446     tmp_proj=SG_MALLOC(float64_t, num_vec);
00447     memset(proj,0,sizeof(float64_t)*num_vec);
00448 
00449     tmp_proj_idx= SG_MALLOC(int32_t, num_vec);
00450     memset(tmp_proj_idx,0,sizeof(int32_t)*num_vec);
00451 
00452     grad_proj= SG_MALLOC(float64_t, num_vec);
00453     memset(grad_proj,0,sizeof(float64_t)*num_vec);
00454 
00455     hinge_point= SG_MALLOC(float64_t, num_vec);
00456     memset(hinge_point,0,sizeof(float64_t)*num_vec);
00457 
00458     hinge_idx= SG_MALLOC(int32_t, num_vec);
00459     memset(hinge_idx,0,sizeof(int32_t)*num_vec);
00460 
00461     active=SG_MALLOC(uint8_t, num_vec);
00462     memset(active,0,sizeof(uint8_t)*num_vec);
00463 
00464     old_active=SG_MALLOC(uint8_t, num_vec);
00465     memset(old_active,0,sizeof(uint8_t)*num_vec);
00466 
00467     idx_bound=SG_MALLOC(int32_t, num_vec);
00468     memset(idx_bound,0,sizeof(int32_t)*num_vec);
00469 
00470     idx_active=SG_MALLOC(int32_t, num_vec);
00471     memset(idx_active,0,sizeof(int32_t)*num_vec);
00472 
00473     Z=SG_MALLOC(float64_t, qpsize_limit*qpsize_limit);
00474     memset(Z,0,sizeof(float64_t)*qpsize_limit*qpsize_limit);
00475 
00476     Zv=SG_MALLOC(float64_t, qpsize_limit);
00477     memset(Zv,0,sizeof(float64_t)*qpsize_limit);
00478 
00479     beta=SG_MALLOC(float64_t, qpsize_limit);
00480     memset(beta,0,sizeof(float64_t)*qpsize_limit);
00481 
00482     old_Z=SG_MALLOC(float64_t, qpsize_limit*qpsize_limit);
00483     memset(old_Z,0,sizeof(float64_t)*qpsize_limit*qpsize_limit);
00484 
00485     old_Zv=SG_MALLOC(float64_t, qpsize_limit);
00486     memset(old_Zv,0,sizeof(float64_t)*qpsize_limit);
00487 
00488     old_beta=SG_MALLOC(float64_t, qpsize_limit);
00489     memset(old_beta,0,sizeof(float64_t)*qpsize_limit);
00490 
00491 }
00492 
00493 void CSubGradientSVM::cleanup()
00494 {
00495     SG_FREE(hinge_idx);
00496     SG_FREE(hinge_point);
00497     SG_FREE(grad_proj);
00498     SG_FREE(proj);
00499     SG_FREE(tmp_proj);
00500     SG_FREE(tmp_proj_idx);
00501     SG_FREE(active);
00502     SG_FREE(old_active);
00503     SG_FREE(idx_bound);
00504     SG_FREE(idx_active);
00505     SG_FREE(sum_CXy_active);
00506     SG_FREE(grad_w);
00507     SG_FREE(v);
00508     SG_FREE(Z);
00509     SG_FREE(Zv);
00510     SG_FREE(beta);
00511     SG_FREE(old_v);
00512     SG_FREE(old_Z);
00513     SG_FREE(old_Zv);
00514     SG_FREE(old_beta);
00515 
00516     hinge_idx=NULL;
00517     proj=NULL;
00518     active=NULL;
00519     old_active=NULL;
00520     idx_bound=NULL;
00521     idx_active=NULL;
00522     sum_CXy_active=NULL;
00523     grad_w=NULL;
00524     v=NULL;
00525     Z=NULL;
00526     Zv=NULL;
00527     beta=NULL;
00528 }
00529 
00530 bool CSubGradientSVM::train_machine(CFeatures* data)
00531 {
00532     tim=0;
00533     SG_INFO("C=%f epsilon=%f\n", C1, epsilon);
00534     ASSERT(labels);
00535 
00536     if (data)
00537     {
00538         if (!data->has_property(FP_DOT))
00539             SG_ERROR("Specified features are not of type CDotFeatures\n");
00540         set_features((CDotFeatures*) data);
00541     }
00542     ASSERT(get_features());
00543 
00544     int32_t num_iterations=0;
00545     int32_t num_train_labels=labels->get_num_labels();
00546     int32_t num_feat=features->get_dim_feature_space();
00547     int32_t num_vec=features->get_num_vectors();
00548 
00549     ASSERT(num_vec==num_train_labels);
00550 
00551     init(num_vec, num_feat);
00552 
00553     int32_t num_active=0;
00554     int32_t num_bound=0;
00555     float64_t alpha=0;
00556     float64_t dir_deriv=0;
00557     float64_t obj=0;
00558     delta_active=num_vec;
00559     last_it_noimprovement=-1;
00560 
00561     work_epsilon=0.99;
00562     autoselected_epsilon=work_epsilon;
00563 
00564     compute_projection(num_feat, num_vec);
00565 
00566     CTime time;
00567 #ifdef DEBUG_SUBGRADIENTSVM
00568     float64_t loop_time=0;
00569 #endif
00570     while (!(CSignal::cancel_computations()))
00571     {
00572         CTime t;
00573         delta_active=find_active(num_feat, num_vec, num_active, num_bound);
00574 
00575         update_active(num_feat, num_vec);
00576 
00577 #ifdef DEBUG_SUBGRADIENTSVM
00578         SG_PRINT("==================================================\niteration: %d ", num_iterations);
00579         obj=compute_objective(num_feat, num_vec);
00580         SG_PRINT("objective:%.10f alpha: %.10f dir_deriv: %f num_bound: %d num_active: %d work_eps: %10.10f eps: %10.10f auto_eps: %10.10f time:%f\n",
00581                 obj, alpha, dir_deriv, num_bound, num_active, work_epsilon, epsilon, autoselected_epsilon, loop_time);
00582 #else
00583       SG_ABS_PROGRESS(work_epsilon, -CMath::log10(work_epsilon), -CMath::log10(0.99999999), -CMath::log10(epsilon), 6);
00584 #endif
00585         //CMath::display_vector(w, w_dim, "w");
00586         //SG_PRINT("bias: %f\n", bias);
00587         //CMath::display_vector(proj, num_vec, "proj");
00588         //CMath::display_vector(idx_active, num_active, "idx_active");
00589         //SG_PRINT("num_active: %d\n", num_active);
00590         //CMath::display_vector(idx_bound, num_bound, "idx_bound");
00591         //SG_PRINT("num_bound: %d\n", num_bound);
00592         //CMath::display_vector(sum_CXy_active, num_feat, "sum_CXy_active");
00593         //SG_PRINT("sum_Cy_active: %f\n", sum_Cy_active);
00594         //CMath::display_vector(grad_w, num_feat, "grad_w");
00595         //SG_PRINT("grad_b:%f\n", grad_b);
00596         
00597         dir_deriv=compute_min_subgradient(num_feat, num_vec, num_active, num_bound);
00598 
00599         alpha=line_search(num_feat, num_vec);
00600 
00601         if (num_it_noimprovement==10 || num_bound<qpsize_max)
00602         {
00603             float64_t norm_grad=CMath::dot(grad_w, grad_w, num_feat) +
00604                 grad_b*grad_b;
00605 
00606 #ifdef DEBUG_SUBGRADIENTSVM
00607             SG_PRINT("CHECKING OPTIMALITY CONDITIONS: "
00608                     "work_epsilon: %10.10f delta_active:%d alpha: %10.10f norm_grad: %10.10f a*norm_grad:%10.16f\n",
00609                     work_epsilon, delta_active, alpha, norm_grad, CMath::abs(alpha*norm_grad));
00610 #else
00611             SG_ABS_PROGRESS(work_epsilon, -CMath::log10(work_epsilon), -CMath::log10(0.99999999), -CMath::log10(epsilon), 6);
00612 #endif
00613 
00614             if (work_epsilon<=epsilon && delta_active==0 && CMath::abs(alpha*norm_grad)<1e-6)
00615                 break;
00616             else
00617                 num_it_noimprovement=0;
00618         }
00619 
00620         if ((dir_deriv<0 || alpha==0) && (work_epsilon<=epsilon && delta_active==0))
00621         {
00622             if (last_it_noimprovement==num_iterations-1)
00623             {
00624                 SG_PRINT("no improvement...\n");
00625                 num_it_noimprovement++;
00626             }
00627             else
00628                 num_it_noimprovement=0;
00629 
00630             last_it_noimprovement=num_iterations;
00631         }
00632 
00633         CMath::vec1_plus_scalar_times_vec2(w, -alpha, grad_w, num_feat);
00634         bias-=alpha*grad_b;
00635 
00636         update_projection(alpha, num_vec);
00637         //compute_projection(num_feat, num_vec);
00638         //CMath::display_vector(w, w_dim, "w");
00639         //SG_PRINT("bias: %f\n", bias);
00640         //CMath::display_vector(proj, num_vec, "proj");
00641 
00642         t.stop();
00643 #ifdef DEBUG_SUBGRADIENTSVM
00644         loop_time=t.time_diff_sec();
00645 #endif
00646         num_iterations++;
00647 
00648         if (get_max_train_time()>0 && time.cur_time_diff()>get_max_train_time())
00649             break;
00650     }
00651     SG_DONE();
00652 
00653     SG_INFO("converged after %d iterations\n", num_iterations);
00654 
00655     obj=compute_objective(num_feat, num_vec);
00656     SG_INFO("objective: %f alpha: %f dir_deriv: %f num_bound: %d num_active: %d\n",
00657             obj, alpha, dir_deriv, num_bound, num_active);
00658 
00659 #ifdef DEBUG_SUBGRADIENTSVM
00660     CMath::display_vector(w, w_dim, "w");
00661     SG_PRINT("bias: %f\n", bias);
00662 #endif
00663     SG_INFO("solver time:%f s\n", tim);
00664 
00665     cleanup();
00666 
00667     return true;
00668 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation