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

dual entirely in terms of α , α ∗ only.

n

1
2

L D ( α ∗ , α )
max

α i )( α j − α j ) K ( x i ,x j )

= − ( α i −

i,j =1

n n

( α i + α i )+ α i ) −ε y i ( α i −

i =1 i =1

subject to

n

α i )=0 y i ( α i −

i =1

α i ,α i 0 ≤ ≤ C

After optimization, the SVM regressor can be written similarly to the classifier
form as

n

α i ) K ( x i , x )+ b f ( x )= ( α i − (3.42)

i =1

The dual variables α i and α i can never be nonzero simultaneously because
the constraint set in Equation 3.41 cannot be fully satisfied for every point.
This provides an opportunity to use one variable to represent the multipliers
in Equation 3.42, but care must be taken when performing the optimiza-
tion (Schlkopf and Smola, 2002).

3.3.3 Training the Support Vector Machine
The SVM problems Equations 3.36 and 3.41 are constrained quadratic
programs in terms of the Lagrangian variables. As such, any optimization
technique suitable for solving these types of problems, for example, projected
gradient descent, projected Newton method, and conjugate gradients can be
used (Fletcher, 1981; Gill et al., 1981). Since data sets can become very large,
problems with computational memory invariably surface due to the storage
requirements for the dense kernel matrix. To deal with this, the decomposition
technique has popularly been applied to solve the SVM by decomposing the
main problem into smaller subproblems, which can be solved with the avail-
able computer memory. The subproblems are characterized by their variables
often referred to as blocks, chunks, or working sets. Decomposition algorithms
proceed by sequentially solving subproblems until all KKT conditions of the
problem have been fulfilled or until some stopping criterion has been met (Lin,
2002). Some of these algorithms are briefly mentioned as follows:

a. General chunking and decomposition algorithm . The general decompo-

sition algorithm operates on part of the problem by taking only a frac-
tion of training points into consideration. The simplest decomposition