Information Technology Reference
In-Depth Information
and thus
|
(
Π
k
V
)
i
−
(
Π
k
V
)
i
|≤
c.
(9.40)
As this holds for any
i
,wehave
Π
k
V
∞
≤
V
∞
.
Π
k
V
−
V
−
(9.41)
which completes the proof.
Thus, averaging classifiers themselves are compatible with value iteration and
policy iteration. Does this, however, still hold for a set of classifiers that provides
its prediction by (9.21)? Let us first consider the special case when the mixing
functions are constant:
Lemma 9.2.
Let the global model
V
be given by
V
=
k
G
k
Π
k
V
,where
Π
k
is the approximation operator of averaging classifiers, and the
G
k
's are constant
diagonal mixing matrices with non-negative elements such that
k
G
k
=
I
holds.
Then, this model forms a non-expansion with respect to the maximum norm.
Proof.
Themethodtoprooftheabovestatement is similar to the one used to
prove Lemma 9.1: firstly, we show that for any two vectors
V
,
V
such that
V
ΠV
and
Π
(
V
+
b
e
)=(
ΠV
)+
b
e
,where
Π
=
k
G
k
Π
k
. Then, non-expansion is shown
by applying these properties to the maximum absolute difference between two
arbitrary vectors.
ΠV
≤
V
, an arbitrary scalar
b
,and
e
=(1
,...,
1)
T
we have
ΠV
≤
ΠV
follows from observing that for the vector
a
=
V
−
V
with
non-negative elements, all elements of
k
G
k
Π
k
a
are non-negative due to the
non-negativity of the elements of
G
k
,and
Π
k
a
≤
≥
0
, and thus
ΠV
=
k
G
k
Π
k
V
−
ΠV
.
G
k
Π
k
a
≤
(9.42)
k
Also, as
Π
k
(
V
+
b
e
)=(
Π
k
V
)+
b
e
and
k
G
k
(
V
k
+
b
e
)=
b
e
+
k
G
k
V
k
for
any
K
vectors
{
V
k
}
,wehave
Π
(
V
+
b
e
)=
ΠV
+
b
e
.
(9.43)
Let
V
,
V
now be to arbitrary vectors, not bound to
V
≤
V
,andlet
c
=
−
V
∞
=max
i
|
V
i
−
V
i
|
V
be their maximum absolute distance. Thus, for
any
i
,
V
i
V
i
−
c
≤
≤
V
i
+
c.
(9.44)
Given the properties of
Π
it follows that
(
ΠV
)
i
≤
(
ΠV
)
i
−
c
≤
(
ΠV
)
i
+
c,
(9.45)
and therefore
(
ΠV
)
i
|≤
|
(
ΠV
)
i
−
c,
(9.46)
from which follows that
ΠV
∞
≤
V
∞
,
ΠV
−
V
−
(9.47)
which completes the proof.
Search WWH ::
Custom Search