Details

Training Stage

The SVM model is trained using the Boser method [Boser92] reduced to the solution of the quadratic optimization problem

with 0 ≤ α _i ≤ C, i = 1, ... , n, y ^T α = 0,

where e is the vector of ones, C is the upper bound of the coordinates of the vector α, Q is a symmetric matrix of size n x n with Q _ij =y _i y _j K(x _i ,x _j ), and K(x,y) is a kernel function.

Working subset of α updated on each iteration of the algorithm is based on the Working Set Selection (WSS) 3 scheme [Fan05]. The scheme can be optimized using one of these techniques or both:

• Cache.

  The implementation can allocate a predefined amount of memory to store intermediate results of the kernel computation.

• Shrinking.

  The implementation can try to decrease the amount of kernel related computations (see [Joachims99]).

The solution of the problem defines the separating hyperplane and corresponding decision function D(x)= ∑ _k y _k α _k K(x _k ,x) + b where only those x _k that correspond to non-zero α _k appear in the sum, and b is a bias. Each non-zero α _k is called a classification coefficient and the corresponding x _k is called a support vector.

Prediction Stage

Given the SVM classifier and r feature vectors x ₁,…,x _r , the problem is to calculate the signed value of the decision function D(x _i ), i=1, ... , r. The sign of the value defines the class of the feature vector, and the absolute value of the function is a multiple of the distance between the feature vector and separating hyperplane.