Information Technology Reference
In-Depth Information
Figure 8.2. A structure on the set of functions is determined by the nested subsets of
functions.
(Picture from Vapnik , 1995).
Let the set S of functions L(z,w) be provided with a structure consisting of nested
subsets of functions
S
=
{ ( ,
L z w
),
w
∈
Λ
}
, such that (See Figure 8.2)
k
k
S
⊂
S
⊂
?
⊂
S
(8.17)
1
2
n
where the elements of the structure satisfy the following two properties:
(1) The VC dimension hk of each set
S
k
of functions is finite. Therefore,
h
2
≤
,…,
≤
h
n
, … .
(2) Any element
1
≤
h
S
k
of the structure contains either a set of totally bounded
functions,0
≤
B
k
; α
∈Λ
k
or a set of functions satisfy the following
inequality for some pair (
L
(
z,w
)
≤
p
,
τ
k
).
1
Ð
(
L
p
(
z
,
w
)
dF
(
z
))
p
sup
≤
τ
p
>2
(8.18)
k
Ð
L
(
z
,
w
)
dF
(
z
)
∈
w
k
We call this structure an admissible structure.
For a given set of observations
z
1
,…,z
l
the SRM principle chooses the function
L
S
k
for which the guaranteed
risk (determined by the right-hand side of inequality (8.15) or by the right-hand
side of inequality (8.16) depending on the circumstances) is minimal.
The SRM principle defines a trade-off between the quality of the
approximation of the given data and the complexity of the approximating
function. As the subset index n increases, the minima of the empirical risks
decrease. However, the term responsible for the confidence interval increases.
(
z,w
kl
) minimizing the empirical risk in the subset
