Support Vector Machines
l37
where 'sup A' is the supremum of a nonempty set A and is defined as the
smallest scalar x such that x ::: y for all YEA. Uniform convergence is
a necessary and sufficient condition for the consistency of the principle of
empirical risk minimization.
Vapnik and Chervonenkis (1971, 1979) also showed that the necessary and
sufficient condition for consistency amounts to the fitness of the VC-dimension
to the hypothesis space. The VC-dimension (named after its originators Vapnik
and Chervonenkis) is a measure of the capacity of a set of classification functions or the complexity of the hypothesis space. The VC-dimension, generally
denoted by h, is an integer that represents the largest number of data points
that can be separated by a set of functions fa in all possible ways. For example,
for a binary classification problem, the VC-dimension is the maximum number
of points, which can be separated into two classes without error in all possible
2k ways. The proof of consistency of the empirical risk minimization (ERM)
can be found in Vapnik (1995,1998).
The theory of uniform convergence in probability also provides a bound on
the deviation of empirical risk from the expected risk given by
( h 10g('1))
R(a) :::: Remp(a) + (5.4)
where k is the number of training samples, and the confidence term as
( ~ log ('1)) =
k
h (log ¥ + 1) -log ('1/4)
k
(5.5)
The parameter h is the VC-dimension of a set of classifiers, and the bound
in (5.4) holds for any a E 11, and k > h with a probability of at least 1 - ' 1
such that 0 :::: ' 1 :::: 1. From bound in (5.4), a good generalization performance
(i. e. the smallest expected risk R(a)) can be obtained when both the empirical
risk and the ratio between the VC-dimension and the number of training
samples are small. With a fixed number of training samples, the empirical risk
is usually a decreasing function of the VC-dimension while the confidence
term is an increasing function. This means that there exists an optimal value
of the VC-dimension that can give the smallest expected risk. Therefore, to
obtain accurate classification, the choice of an appropriate VC-dimension is
also crucial.
5.2.2
Structural Risk Minimization
For the selection of an appropriate VC-dimension for a given set of functions,
Vapnik (1982) proposed the principle of SRM that is based on the fact that the
minimization of the expected risk is possible by simultaneous minimization of
l37
where 'sup A' is the supremum of a nonempty set A and is defined as the
smallest scalar x such that x ::: y for all YEA. Uniform convergence is
a necessary and sufficient condition for the consistency of the principle of
empirical risk minimization.
Vapnik and Chervonenkis (1971, 1979) also showed that the necessary and
sufficient condition for consistency amounts to the fitness of the VC-dimension
to the hypothesis space. The VC-dimension (named after its originators Vapnik
and Chervonenkis) is a measure of the capacity of a set of classification functions or the complexity of the hypothesis space. The VC-dimension, generally
denoted by h, is an integer that represents the largest number of data points
that can be separated by a set of functions fa in all possible ways. For example,
for a binary classification problem, the VC-dimension is the maximum number
of points, which can be separated into two classes without error in all possible
2k ways. The proof of consistency of the empirical risk minimization (ERM)
can be found in Vapnik (1995,1998).
The theory of uniform convergence in probability also provides a bound on
the deviation of empirical risk from the expected risk given by
( h 10g('1))
R(a) :::: Remp(a) + (5.4)
where k is the number of training samples, and the confidence term as
( ~ log ('1)) =
k
h (log ¥ + 1) -log ('1/4)
k
(5.5)
The parameter h is the VC-dimension of a set of classifiers, and the bound
in (5.4) holds for any a E 11, and k > h with a probability of at least 1 - ' 1
such that 0 :::: ' 1 :::: 1. From bound in (5.4), a good generalization performance
(i. e. the smallest expected risk R(a)) can be obtained when both the empirical
risk and the ratio between the VC-dimension and the number of training
samples are small. With a fixed number of training samples, the empirical risk
is usually a decreasing function of the VC-dimension while the confidence
term is an increasing function. This means that there exists an optimal value
of the VC-dimension that can give the smallest expected risk. Therefore, to
obtain accurate classification, the choice of an appropriate VC-dimension is
also crucial.
5.2.2
Structural Risk Minimization
For the selection of an appropriate VC-dimension for a given set of functions,
Vapnik (1982) proposed the principle of SRM that is based on the fact that the
minimization of the expected risk is possible by simultaneous minimization of