154
5: Mahesh Pal, Pakorn Watanachaturaporn
This algorithm can process large datasets without large memory requirements.
Hsu and Lin (2002) found that these algorithms work quite well and the results
are similar to any standard QP optimization method. Further, Mangasarian
and Musicant (2000a) proposed the use of mathematical programming to solve
the optimization problem. An 'active set' strategy is used to generate a fast
algorithm that consists of solving a finite number of linear equations of the
order of the dimensionality of the original input space at each step. This method
consists of maximizing the margin between two separating hyperplanes with
respect to both wand b and using a squared 2-norm of slack variables in place
of the I-norm defined in (5.30). Thus, the active set optimization algorithm
requires no specialized quadratic or linear programming software, but a linear
solver to solve an N + 1 by N + 1 matrix, where N is the dimensionality of the
input data space.
Mangasarian and Musicant (2000b) also proposed the Lagrangian SVM
(LSVM) that reformulates the constrained optimization problem as an unconstrained optimization problem. The problem is solved through an optimizer
based on the system oflinear equalities. Ferris and Munson (2000a, 2000b) proposed interior point and semi-smooth support vector machines. The interior
point SVM uses proximal point modification to the underlying algorithm, the
Sherman-Morrison-Woodbury formula, and the Schur complement to solve
a linear system. In the semi-smooth support vector machine, Ferris and Munson reformulated the optimality conditions as a semi-smooth system using
the Fischer-Burmeister function, applied as a damped Newton method, and
exploited the Sherman-Morrison-Woodbury formula to efficiently solve the
problem. Both methods can solve linear classification problems proficiently.
These optimization methods are just some examples and are still being pursued in ongoing research. Some of the methods will also be investigated in
Chap. 10.
5.6
Summary
In this chapter, we have introduced the basic concepts of support vector machines (SVMs) for classification problems. SVMs originate from the structural
risk minimization concept of statistical learning theory. The basic mathematical background of SVM was discussed by formulating a binary classification
problem. All the three cases - linearly separable and linearly non-separable
cases, and the nonlinear case - were considered. In the nonlinear case, data
are required to be mapped to a higher dimensional feature space through
a kernel function suitably incorporated in the objective function. The binary
classification problem was then extended to multiclass classification and the
associated methods were briefly discussed. A discussion on various optimization methods was also provided. This methodology will be employed for the
classification of a set of multi- and hyperspectral data in Chap. 10.
5: Mahesh Pal, Pakorn Watanachaturaporn
This algorithm can process large datasets without large memory requirements.
Hsu and Lin (2002) found that these algorithms work quite well and the results
are similar to any standard QP optimization method. Further, Mangasarian
and Musicant (2000a) proposed the use of mathematical programming to solve
the optimization problem. An 'active set' strategy is used to generate a fast
algorithm that consists of solving a finite number of linear equations of the
order of the dimensionality of the original input space at each step. This method
consists of maximizing the margin between two separating hyperplanes with
respect to both wand b and using a squared 2-norm of slack variables in place
of the I-norm defined in (5.30). Thus, the active set optimization algorithm
requires no specialized quadratic or linear programming software, but a linear
solver to solve an N + 1 by N + 1 matrix, where N is the dimensionality of the
input data space.
Mangasarian and Musicant (2000b) also proposed the Lagrangian SVM
(LSVM) that reformulates the constrained optimization problem as an unconstrained optimization problem. The problem is solved through an optimizer
based on the system oflinear equalities. Ferris and Munson (2000a, 2000b) proposed interior point and semi-smooth support vector machines. The interior
point SVM uses proximal point modification to the underlying algorithm, the
Sherman-Morrison-Woodbury formula, and the Schur complement to solve
a linear system. In the semi-smooth support vector machine, Ferris and Munson reformulated the optimality conditions as a semi-smooth system using
the Fischer-Burmeister function, applied as a damped Newton method, and
exploited the Sherman-Morrison-Woodbury formula to efficiently solve the
problem. Both methods can solve linear classification problems proficiently.
These optimization methods are just some examples and are still being pursued in ongoing research. Some of the methods will also be investigated in
Chap. 10.
5.6
Summary
In this chapter, we have introduced the basic concepts of support vector machines (SVMs) for classification problems. SVMs originate from the structural
risk minimization concept of statistical learning theory. The basic mathematical background of SVM was discussed by formulating a binary classification
problem. All the three cases - linearly separable and linearly non-separable
cases, and the nonlinear case - were considered. In the nonlinear case, data
are required to be mapped to a higher dimensional feature space through
a kernel function suitably incorporated in the objective function. The binary
classification problem was then extended to multiclass classification and the
associated methods were briefly discussed. A discussion on various optimization methods was also provided. This methodology will be employed for the
classification of a set of multi- and hyperspectral data in Chap. 10.