Support Vector Machines
143
This theorem shows that the VC-dimension of the set of hyperplanes is equal
to N + 1. However, it can be less than N + 1 if the margin of separation is large.
In case of an SVM, a SRM nested structure of hypothesis space can be
described in terms of the separating hyperplanes as Ale A2 c ... C An C ...
with
(5.29)
where q is a constant. The nested structure may be reformulated in terms of
the bound on the VC-dimension as
(5.30)
where ak is a constant.
After a nested structure is created, the expected risk is then minimized by
minimizing the empirical risk and the confidence term simultaneously. The
empirical risk is automatically minimized by setting it to zero from the requirement that data belonging to the same class are placed on the same side
without error. Since the empirical risk of every hypothesis space is set to zero,
the expected risk depends on the confidence term alone. However, the confidence term depends on the VC-dimension and the number of training samples.
Let the number of training samples be a constant value, then the confidence
term relies on the VC-dimension only. The smallest value of VC-dimension
is determined from the largest value of the margin (from Theorem 5.1). The
margin is equal to 2/llw112 (i. e. the smallest value of the vector w also produces
the smallest value of VC-dimension). Therefore, the classifier that produces
the smallest expected risk is identified as the one that minimizes the vector w.
This clearly shows that the construction of an SVM completely complies with
the principle of SRM.
5.3.2
Linearly Non-Separable Case
It is true that the linearly separable case is an ideal case to understand the
concept of support vector machines. All data are assumed to be separable
into two classes with a linear separating hyperplane. However, in practice,
this assumption is rarely met due to noise or mixture of classes during the
selection of training data. In other words, it is not possible in practice to
create a linear separating hyperplane to separate classes of interest without
any misclassification error for a given training data set (see Fig. 5.2). Thus, the
classes are not linearly separable. This problem can be tackled by using a soft
margin classifier introduced by Bennett and Mangasarian (l992) and Cortes
and Vapnik (l995). Soft margin classification relaxes the requirement that every
data point belonging to the same class must be located on the same side of
a linear separating hyperplane. It introduces slack variables 5i ::: 0, i = 1, ... , I,
to take into account the noise or error in the dataset due to misclassification.
143
This theorem shows that the VC-dimension of the set of hyperplanes is equal
to N + 1. However, it can be less than N + 1 if the margin of separation is large.
In case of an SVM, a SRM nested structure of hypothesis space can be
described in terms of the separating hyperplanes as Ale A2 c ... C An C ...
with
(5.29)
where q is a constant. The nested structure may be reformulated in terms of
the bound on the VC-dimension as
(5.30)
where ak is a constant.
After a nested structure is created, the expected risk is then minimized by
minimizing the empirical risk and the confidence term simultaneously. The
empirical risk is automatically minimized by setting it to zero from the requirement that data belonging to the same class are placed on the same side
without error. Since the empirical risk of every hypothesis space is set to zero,
the expected risk depends on the confidence term alone. However, the confidence term depends on the VC-dimension and the number of training samples.
Let the number of training samples be a constant value, then the confidence
term relies on the VC-dimension only. The smallest value of VC-dimension
is determined from the largest value of the margin (from Theorem 5.1). The
margin is equal to 2/llw112 (i. e. the smallest value of the vector w also produces
the smallest value of VC-dimension). Therefore, the classifier that produces
the smallest expected risk is identified as the one that minimizes the vector w.
This clearly shows that the construction of an SVM completely complies with
the principle of SRM.
5.3.2
Linearly Non-Separable Case
It is true that the linearly separable case is an ideal case to understand the
concept of support vector machines. All data are assumed to be separable
into two classes with a linear separating hyperplane. However, in practice,
this assumption is rarely met due to noise or mixture of classes during the
selection of training data. In other words, it is not possible in practice to
create a linear separating hyperplane to separate classes of interest without
any misclassification error for a given training data set (see Fig. 5.2). Thus, the
classes are not linearly separable. This problem can be tackled by using a soft
margin classifier introduced by Bennett and Mangasarian (l992) and Cortes
and Vapnik (l995). Soft margin classification relaxes the requirement that every
data point belonging to the same class must be located on the same side of
a linear separating hyperplane. It introduces slack variables 5i ::: 0, i = 1, ... , I,
to take into account the noise or error in the dataset due to misclassification.