Computational Intelligence Techniques - Computational Intelligence in Biomedical Engineering - page 106

the kth iteration and write the violator list as the vector E ( k ) ↓ , where
∀

k> 0

E ( k ) ↓ = { y i v i | y 1 v 1 ≥ y 2 v 2 ≥ ··· ≥ y z v z , ∀ i =1 ,...,z }

The working set α p is of size q where q is some even number so that
∀ p> 0, we choose the first q/ 2 elements from E ( k ) ↓ and the last q/ 2

elements, that is,

first q/ 2 elements from E ↓ , last q/ 2 elements from E ↓ }
(3.51)

α p = { α |

This method is a generalization of Platt's method because q variables
can now be chosen. Given the ordered error list, the top q/ 2 variables
had the largest positive error whereas the bottom q/ 2 variables had
the largest negative error. Use of the steepest search direction method
implies that gradient descent on q variables could be employed at once,
rather than being restricted to just two as in Platt's method. The selec-
tion heuristic employed by SVM light , however, was still based on maxi-
mal violators as SMO and the step for b was calculated independently.
The algorithm flowchart for SVM light is shown in Figure 3.19.
To further decrease the SVM light runtime, Joachims further intro-
duced a heuristic, which he called shrinking. Note that in Figure 3.19,
after a selected working set was updated, the gradients of all points
were then updated. As convergence was approached, Joachims observed
that generally only a subset of multipliers remained to be determined.

Start
SVM problem with
N examples, set q
to be working set
size

Success

Update q
examples
using
Zoutendijk
line search

Compute
the training
errors of
violators

Y Select q/2 most

positive errors and q/2
most negative errors

#KKT>0?

N

Optimization
complete

Examine the next set
of errors

Failed

FIGURE 3.19
Flowchart for selecting working sets in the SVM light algorithm.