Support Vector Machines
135
apart such that a linear separating hyperplane may be found. But, due to very
large dimensionality of the feature space, it is not practical to compute the inner
product of two transformed data vectors (see Sect. 5.3.3). This may, however, be
achieved by using a kernel trick instead of explicitly computing transformations
in the feature space. Kernel trick is played by substituting a kernel function in
place of the inner product of two transformed data vectors. The use of kernel
trick reduces the computational effort by a significant amount.
In this chapter, several theoretical aspects of support vector machines will be
described. In Sect. 5.2, statistical learning theory is briefly reviewed. Section 5.3
describes the construction of SVMs for the binary classification problem for
three different cases: linearly separable case, linearly non-separable case, and
non-linear case. Section 5.4 explains the extension of the binary classification
problem to the multiclass problem. A discussion on various optimization
methods used in the construction ofSVMs is presented in Sect. 5.5. A summary
of the chapter is presented in Sect. 5.6. Though, all the discussion here is
directed towards the classification problem, it is equally applicable for solving
regression problems.
S.2
Statistical Learning Theory
Statistical Learning Theory, developed by Vapnik (1982, 1995, 1998), views
a supervised classification problem as an input-output relationship. In the
case of a two-class (i. e. binary) classification problem, an algorithm learns
from a given set of k training samples, (Xl>yt}, ... , (XbYk), Xi E ]RN, Yi E
{-1, + 1), which are drawn from a fixed but unknown cumulative (probability)
distribution function P{x, y), where X is an N-dimensional observed data vector
and Yi is a class label. ]R is the set of all real numbers. A decision rule or
classification rule is represented by, {Ja{x) : a E 11}, fa : ]RN -+ {-1, +1},
where 11 is the set of parameters used in the decision rule (Osuna et al. 1997).
For example, in a multilayer neural network, 11 is the set of weights of the
network.
The aim of classification is to assign the class label y, based on the training
samples x, and a decision rule fa that provides the smallest possible error over
the independent data samples or the smallest possible expected risk defined as
R{a) = f L (y,fa{X)) dP (x,y) .
(5.1)
The function fa is called the hypothesis. The set {fa (X) : a E 11} is called the
hypothesis space (Osuna et al. 1997), and L{y,fa{x)) is the loss or discrepancy
between the response y of the supervisor or teacher to a given input x and the
response fa (x) provided by the learning machine. In other words, the expected
risk is a measure of the performance of a decision rule that assigns the class label
y to an input data vector x. However, evaluation of the expected risk is difficult,
since the cumulative distribution function P (x,y) is unknown and thus one
135
apart such that a linear separating hyperplane may be found. But, due to very
large dimensionality of the feature space, it is not practical to compute the inner
product of two transformed data vectors (see Sect. 5.3.3). This may, however, be
achieved by using a kernel trick instead of explicitly computing transformations
in the feature space. Kernel trick is played by substituting a kernel function in
place of the inner product of two transformed data vectors. The use of kernel
trick reduces the computational effort by a significant amount.
In this chapter, several theoretical aspects of support vector machines will be
described. In Sect. 5.2, statistical learning theory is briefly reviewed. Section 5.3
describes the construction of SVMs for the binary classification problem for
three different cases: linearly separable case, linearly non-separable case, and
non-linear case. Section 5.4 explains the extension of the binary classification
problem to the multiclass problem. A discussion on various optimization
methods used in the construction ofSVMs is presented in Sect. 5.5. A summary
of the chapter is presented in Sect. 5.6. Though, all the discussion here is
directed towards the classification problem, it is equally applicable for solving
regression problems.
S.2
Statistical Learning Theory
Statistical Learning Theory, developed by Vapnik (1982, 1995, 1998), views
a supervised classification problem as an input-output relationship. In the
case of a two-class (i. e. binary) classification problem, an algorithm learns
from a given set of k training samples, (Xl>yt}, ... , (XbYk), Xi E ]RN, Yi E
{-1, + 1), which are drawn from a fixed but unknown cumulative (probability)
distribution function P{x, y), where X is an N-dimensional observed data vector
and Yi is a class label. ]R is the set of all real numbers. A decision rule or
classification rule is represented by, {Ja{x) : a E 11}, fa : ]RN -+ {-1, +1},
where 11 is the set of parameters used in the decision rule (Osuna et al. 1997).
For example, in a multilayer neural network, 11 is the set of weights of the
network.
The aim of classification is to assign the class label y, based on the training
samples x, and a decision rule fa that provides the smallest possible error over
the independent data samples or the smallest possible expected risk defined as
R{a) = f L (y,fa{X)) dP (x,y) .
(5.1)
The function fa is called the hypothesis. The set {fa (X) : a E 11} is called the
hypothesis space (Osuna et al. 1997), and L{y,fa{x)) is the loss or discrepancy
between the response y of the supervisor or teacher to a given input x and the
response fa (x) provided by the learning machine. In other words, the expected
risk is a measure of the performance of a decision rule that assigns the class label
y to an input data vector x. However, evaluation of the expected risk is difficult,
since the cumulative distribution function P (x,y) is unknown and thus one