Impala Documentation

void Solver_NU::do_shrinking ( ) [private, virtual]

Reimplemented from Solver.

Definition at line 968 of file svm.cpp.

References Solver::active_size, Solver::eps, Solver::G, INF, Solver::is_lower_bound(), Solver::is_upper_bound(), Solver::l, max, Solver::reconstruct_gradient(), Solver::swap_index(), Solver::unshrinked, and Solver::y.

00969 {
00970         double Gmax1 = -INF;    // max { -grad(f)_i * d | y_i = +1, d = +1 }
00971         double Gmax2 = -INF;    // max { -grad(f)_i * d | y_i = +1, d = -1 }
00972         double Gmax3 = -INF;    // max { -grad(f)_i * d | y_i = -1, d = +1 }
00973         double Gmax4 = -INF;    // max { -grad(f)_i * d | y_i = -1, d = -1 }
00974 
00975         int k;
00976         for(k=0;k<active_size;k++)
00977         {
00978                 if(!is_upper_bound(k))
00979                 {
00980                         if(y[k]==+1)
00981                         {
00982                                 if(-G[k] > Gmax1) Gmax1 = -G[k];
00983                         }
00984                         else    if(-G[k] > Gmax3) Gmax3 = -G[k];
00985                 }
00986                 if(!is_lower_bound(k))
00987                 {
00988                         if(y[k]==+1)
00989                         {       
00990                                 if(G[k] > Gmax2) Gmax2 = G[k];
00991                         }
00992                         else    if(G[k] > Gmax4) Gmax4 = G[k];
00993                 }
00994         }
00995 
00996         double Gm1 = -Gmax2;
00997         double Gm2 = -Gmax1;
00998         double Gm3 = -Gmax4;
00999         double Gm4 = -Gmax3;
01000 
01001         for(k=0;k<active_size;k++)
01002         {
01003                 if(is_lower_bound(k))
01004                 {
01005                         if(y[k]==+1)
01006                         {
01007                                 if(-G[k] >= Gm1) continue;
01008                         }
01009                         else    if(-G[k] >= Gm3) continue;
01010                 }
01011                 else if(is_upper_bound(k))
01012                 {
01013                         if(y[k]==+1)
01014                         {
01015                                 if(G[k] >= Gm2) continue;
01016                         }
01017                         else    if(G[k] >= Gm4) continue;
01018                 }
01019                 else continue;
01020 
01021                 --active_size;
01022                 swap_index(k,active_size);
01023                 --k;    // look at the newcomer
01024         }
01025 
01026         // unshrink, check all variables again before final iterations
01027 
01028         if(unshrinked || std::max(-(Gm1+Gm2),-(Gm3+Gm4)) > eps*10) return;
01029         
01030         unshrinked = true;
01031         reconstruct_gradient();
01032 
01033         for(k=l-1;k>=active_size;k--)
01034         {
01035                 if(is_lower_bound(k))
01036                 {
01037                         if(y[k]==+1)
01038                         {
01039                                 if(-G[k] < Gm1) continue;
01040                         }
01041                         else    if(-G[k] < Gm3) continue;
01042                 }
01043                 else if(is_upper_bound(k))
01044                 {
01045                         if(y[k]==+1)
01046                         {
01047                                 if(G[k] < Gm2) continue;
01048                         }
01049                         else    if(G[k] < Gm4) continue;
01050                 }
01051                 else continue;
01052 
01053                 swap_index(k,active_size);
01054                 active_size++;
01055                 ++k;    // look at the newcomer
01056         }
01057 }

Here is the call graph for this function: