142
5: Mahesh Pal, Pakorn Watanachaturaporn
Thus, the solution of the optimization problem given in (5.23) is obtained
in terms of the Lagrange multipliers Ai. According to the Karush- Kuhn-Tucker
(KKT) optimality condition (Cristianini and Shawe-Taylor 2000), some of the
multipliers will be zero. The multipliers that have the nonzero values are
called the support vectors. It is also noteworthy that the solution w obtained
from (5.21) is unique and independent of the optimizer used. However, the
values of the Lagrange multipliers obtained from different optimizers are not
necessarily unique. This also implies that the support vectors and the number
of support vectors are also not unique and may vary depending upon the
optimizer used.
The results from an optimizer, also called an optimal solution, is a set
A O = (A~, ... ,An that is substituted in (5.21) to get
(5.26)
The intercept b O is determined from
(5.27)
where x~ 1 and x~ 1 are the support vectors of class labels + 1 and -1 respectively.
The following decision rule is then applied to classify the data vector into
two classes + 1 and -1:
f(x) = sign (
L YiA; (Xi· X) + b
O )
•
support vectors
(5.28)
As mentioned before, an SVM is based on SRM whose goal is to minimize
the bound on the VC-dimension and the empirical risk at the same time. In
the linearly separable case, the empirical risk is automatically minimized as
the data belonging to a class are placed on the same side (i. e. no training
error). To control the VC dimension, a nested structure of classifiers each with
a different VC-dimension is created (see Sect. 5.2.2). Based on the fact that an
SVM is constructed by optimizing the Euclidean norm of the weight vector w,
its VC-dimension can best be described by the following theorem (proof given
in Vapnik (1999»,
Theorem 5.1 Let vectors X E X belong to a sphere of radius R. Then the set
of L1-margin separating hyperplanes has the VC dimension h bounded by the
inequality
h ~ min (I ~~ l N) + 1
where r E 1 denotes the ceiling function that round the element E to the nearest
integer greater than or equal to the value E, L1 is the margin of separation, and
N is the dimensionality of the input space.
5: Mahesh Pal, Pakorn Watanachaturaporn
Thus, the solution of the optimization problem given in (5.23) is obtained
in terms of the Lagrange multipliers Ai. According to the Karush- Kuhn-Tucker
(KKT) optimality condition (Cristianini and Shawe-Taylor 2000), some of the
multipliers will be zero. The multipliers that have the nonzero values are
called the support vectors. It is also noteworthy that the solution w obtained
from (5.21) is unique and independent of the optimizer used. However, the
values of the Lagrange multipliers obtained from different optimizers are not
necessarily unique. This also implies that the support vectors and the number
of support vectors are also not unique and may vary depending upon the
optimizer used.
The results from an optimizer, also called an optimal solution, is a set
A O = (A~, ... ,An that is substituted in (5.21) to get
(5.26)
The intercept b O is determined from
(5.27)
where x~ 1 and x~ 1 are the support vectors of class labels + 1 and -1 respectively.
The following decision rule is then applied to classify the data vector into
two classes + 1 and -1:
f(x) = sign (
L YiA; (Xi· X) + b
O )
•
support vectors
(5.28)
As mentioned before, an SVM is based on SRM whose goal is to minimize
the bound on the VC-dimension and the empirical risk at the same time. In
the linearly separable case, the empirical risk is automatically minimized as
the data belonging to a class are placed on the same side (i. e. no training
error). To control the VC dimension, a nested structure of classifiers each with
a different VC-dimension is created (see Sect. 5.2.2). Based on the fact that an
SVM is constructed by optimizing the Euclidean norm of the weight vector w,
its VC-dimension can best be described by the following theorem (proof given
in Vapnik (1999»,
Theorem 5.1 Let vectors X E X belong to a sphere of radius R. Then the set
of L1-margin separating hyperplanes has the VC dimension h bounded by the
inequality
h ~ min (I ~~ l N) + 1
where r E 1 denotes the ceiling function that round the element E to the nearest
integer greater than or equal to the value E, L1 is the margin of separation, and
N is the dimensionality of the input space.