Information Technology Reference
In-Depth Information
−
α
(
,
n
)
or greater, the following inequality holds true:
Theorem 5.
With probability
1
η
n
n
1
B
ln
N
−
ln
η
C
−
V
≤
1
−
−
2
I
B
+
√
n
+
n
n
−
ln
η
.
(41)
−
1
2
I
Theorem 6.
With probability
1
−
α
(
η
,
n
)
or greater, the following inequality holds true:
2
n
n
1
+
1
B
ln
N
+
B
√
n
−
ln
η
−
ln
η
V
−
C
≤
.
(42)
−
2
I
2
I
3
The Relationship for an Infinite Set of Approximating Functions
The simplest case with a finite number of functions in the set has been generalized
by Vapnik [2,19,25] onto
infinite
sets with continuum of elements by introducing sev-
eral notions of the
capacity
of the set of functions:
entropy
,
annealed entropy
,
growth
function
,
Vapnik-Chervonenkis dimension
. We remind them in brief.
First of all, Vapnik defines
N
Ω
(
z
1
,...,
z
I
)
which is the number of all possible
di-
chotmies
that can be achieved on a fixed sample
{
z
1
,...,
z
I
}
using functions from
{
}
ω
∈
Ω
. Then, if we relax the sample the following notions of
capacity
can be
considered:
Q
(
z
,
ω
)
1. expected value of ln
N
Ω
—
Vapnik-Chervonenkis entropy
:
H
Ω
(
I
)=
ln
N
Ω
(
z
1
,...,
z
I
)
z
1
∈
Z
···
z
I
∈
Z
·
p
(
z
1
)
···
p
(
z
I
)
dz
1
···
dz
I
,
2. ln of expected value of
N
Ω
—
annealed entropy
:
H
ann
(
I
)=
ln
N
Ω
(
z
1
,...,
z
I
)
z
1
∈
Z
···
z
I
∈
Z
·
p
(
z
1
)
···
p
(
z
I
)
dz
1
···
dz
I
,
3. ln of supremum of
N
Ω
—
growth function
G
Ω
(
I
)=
ln sup
z
1
,...,
z
I
N
Ω
(
z
1
,...,
z
I
)
.
It has been proved that:
G
Ω
(
I
)=
=
ln 2
I
,
≤
dla
I
h
;
k
=
0
k
,
dla
I
>
h
,
(43)
h
≤
ln
∑
