24
2 Introduction to Machine Learning
Here d V C is a numerical value of the expressive power (or complexity) of the
model Q J called the VC dimension (Vapnik-Chervonenkis dimension). Roughly
speaking, d V C corresponds to the number of parameters J included in the model. 11
Let us consider the difficulty of generalization using this expression.
First, adjust the parameter J to reduce the empirical error, since it is the first
thing that can be done. It is better to increase the expressive power of the model,
because otherwise it cannot handle various data. As a result, in principle, empirical
errors could be very small by complicating the model.
On the other hand, the value of d V C jumps up in a complex model that makes the
empirical error extremely small. For simplicity, let us say this has become infinite.
Then, under the fixed number of data #, the value of the second term in (2.11)
diverges as
lim
#/d V C →+0
log(#/d V C )
#/d V C
→ ∞ .
(2.14)
Then (2.11) is a meaningless inequality
(Generalization error) ≤ (Experience error) + ∞.
(2.15)
No matter how much the empirical error is reduced in this state, it is not guaranteed
that the generalization error is reduced. 12 Therefore, generalization of learning
cannot be guaranteed without using an appropriate model according to the scale
of the data. When creating a phenomenological model of physics, models that are
too complicated to describe phenomena are not preferable. This argument is called
Occam’s razor. The inequality (2.11) mathematically expresses the principle of
Occam’s razor. 13
11 The exact definition of the VC dimension is as follows. We define the model Q J as
Q J (x, d) = Q J (d|x)P (x) ,
(2.12)
as we will do later. Also, using function f J with parameter J and the Dirac delta function δ, we
write
Q J (d|x) = δ(f J (x) − d).
(2.13)
Suppose further that we are working on the problem of binary classification with d = 0, 1. It means
that f J (x) is working to assign the input x to either 0 or 1. By the way, if there are # data, there are
2 # possible ways of assigning 0/1. If we can vary J fully, then [f J (x[1]), f J (x[2]), . . . , f j (x[#])]
can realize all possible 0/1 distributions, and this model has the ability to completely fit the data
(the capacity is saturated compared to the number of data #). The VC dimension refers to the
maximum value of # where such a situation is realized.
12 Over-training is a situation that falls into this state.
13 A well-known index based on a similar idea is Akaike’s Information Criteria (AIC) [22]:
AI C = −2 log L + 2k ,
(2.16)
2 Introduction to Machine Learning
Here d V C is a numerical value of the expressive power (or complexity) of the
model Q J called the VC dimension (Vapnik-Chervonenkis dimension). Roughly
speaking, d V C corresponds to the number of parameters J included in the model. 11
Let us consider the difficulty of generalization using this expression.
First, adjust the parameter J to reduce the empirical error, since it is the first
thing that can be done. It is better to increase the expressive power of the model,
because otherwise it cannot handle various data. As a result, in principle, empirical
errors could be very small by complicating the model.
On the other hand, the value of d V C jumps up in a complex model that makes the
empirical error extremely small. For simplicity, let us say this has become infinite.
Then, under the fixed number of data #, the value of the second term in (2.11)
diverges as
lim
#/d V C →+0
log(#/d V C )
#/d V C
→ ∞ .
(2.14)
Then (2.11) is a meaningless inequality
(Generalization error) ≤ (Experience error) + ∞.
(2.15)
No matter how much the empirical error is reduced in this state, it is not guaranteed
that the generalization error is reduced. 12 Therefore, generalization of learning
cannot be guaranteed without using an appropriate model according to the scale
of the data. When creating a phenomenological model of physics, models that are
too complicated to describe phenomena are not preferable. This argument is called
Occam’s razor. The inequality (2.11) mathematically expresses the principle of
Occam’s razor. 13
11 The exact definition of the VC dimension is as follows. We define the model Q J as
Q J (x, d) = Q J (d|x)P (x) ,
(2.12)
as we will do later. Also, using function f J with parameter J and the Dirac delta function δ, we
write
Q J (d|x) = δ(f J (x) − d).
(2.13)
Suppose further that we are working on the problem of binary classification with d = 0, 1. It means
that f J (x) is working to assign the input x to either 0 or 1. By the way, if there are # data, there are
2 # possible ways of assigning 0/1. If we can vary J fully, then [f J (x[1]), f J (x[2]), . . . , f j (x[#])]
can realize all possible 0/1 distributions, and this model has the ability to completely fit the data
(the capacity is saturated compared to the number of data #). The VC dimension refers to the
maximum value of # where such a situation is realized.
12 Over-training is a situation that falls into this state.
13 A well-known index based on a similar idea is Akaike’s Information Criteria (AIC) [22]:
AI C = −2 log L + 2k ,
(2.16)