Information Technology Reference
In-Depth Information
,(
on
samples of size l. Here the expectation is taken with respect to the product
measure
A
≤
L
y
w
)
≤
B
,
w
∈
Λ
is called the VC entropy of the set of functions
F
(
1
z
,
?
,
z
)
.
l
Theorem 8.2
For uniform two-sided convergence it is necessary and sufficient
that the equality
Λ
H
(
ε
,
l
)
lim
=
0
∀ε>0
(8.9)
l
l
→
∞
be valid. In other words, the ratio of the VC entropy to the number of
observations should decrease to zero with increasing numbers of observations.
Corollary 8.1
Under some conditions of measurability on the set of indicator
functions
L
(
y
,
w
),
w
∈
Λ
, necessary and sufficient condition for uniform two-
Λ
H
(
l
)
lim
=
0
which is a particular case of equality (8.9).
sided convergence is
l
l
→
∞
Theorem 8.3
In order for uniform one-sided convergence of empirical means to
their expectations to hold for the set of totally bounded functions
L y w w
∈
,
it is necessary and sufficient that for any positive δ, η and ε
there exist a set of
functions
( ,
),
*
*
*
*
L
( ,
y w
),
w
∈
Λ
satisfying following
*
*
L
(
y
,
w
)
−
L
(
y
,
w
)
≥
0
∀
y
,
(8.10)
Ð
*
*
(
L
(
y
,
w
)
−
L
(
y
,
w
))
dF
(
y
)
≤
δ
.
*
*
*
*
L
( ,
y w
),
w
∈
Λ
such that the following holds for the ε-entropy of the set
, on
samples of size
l
.
*
Λ
H
(
ε
,
l
)
lim
<
η
.
l
l
→
∞
According to these key theorems, we study learning theory. Moreover, we
describe a sufficient condition for consistency of the ERM principle by using
different methods and functions. On the basis of these functions three milestones
of learning theory are constructed:
(1) We use VC entropy to define the following equation describing a sufficient
condition for consistency of the ERM principle.
