Impala Documentation

int Solver::select_working_set	(	int &	i,
		int &	j
	)			`[protected, virtual]`

Reimplemented in Solver_NU.

Definition at line 702 of file svm.cpp.

References active_size, eps, G, INF, is_lower_bound(), is_upper_bound(), and y.

Referenced by do_shrinking(), and Solve().

00703 {
00704         // return i,j which maximize -grad(f)^T d , under constraint
00705         // if alpha_i == C, d != +1
00706         // if alpha_i == 0, d != -1
00707 
00708         double Gmax1 = -INF;            // max { -grad(f)_i * d | y_i*d = +1 }
00709         int Gmax1_idx = -1;
00710 
00711         double Gmax2 = -INF;            // max { -grad(f)_i * d | y_i*d = -1 }
00712         int Gmax2_idx = -1;
00713 
00714         for(int i=0;i<active_size;i++)
00715         {
00716                 if(y[i]==+1)    // y = +1
00717                 {
00718                         if(!is_upper_bound(i))  // d = +1
00719                         {
00720                                 if(-G[i] > Gmax1)
00721                                 {
00722                                         Gmax1 = -G[i];
00723                                         Gmax1_idx = i;
00724                                 }
00725                         }
00726                         if(!is_lower_bound(i))  // d = -1
00727                         {
00728                                 if(G[i] > Gmax2)
00729                                 {
00730                                         Gmax2 = G[i];
00731                                         Gmax2_idx = i;
00732                                 }
00733                         }
00734                 }
00735                 else            // y = -1
00736                 {
00737                         if(!is_upper_bound(i))  // d = +1
00738                         {
00739                                 if(-G[i] > Gmax2)
00740                                 {
00741                                         Gmax2 = -G[i];
00742                                         Gmax2_idx = i;
00743                                 }
00744                         }
00745                         if(!is_lower_bound(i))  // d = -1
00746                         {
00747                                 if(G[i] > Gmax1)
00748                                 {
00749                                         Gmax1 = G[i];
00750                                         Gmax1_idx = i;
00751                                 }
00752                         }
00753                 }
00754         }
00755 
00756         if(Gmax1+Gmax2 < eps)
00757                 return 1;
00758 
00759         out_i = Gmax1_idx;
00760         out_j = Gmax2_idx;
00761         return 0;
00762 }

Here is the call graph for this function: