
68 Knowledge Discovery from Data Streams
bound (Chernoff, 1952):
ε
c
=
r
3 × ¯µ
n
ln(2/δ),
where δ is a user-defined confidence level. In the case of bounded loss functions,
like the 0-1 loss, the Hoeffding bound (Hoeffding, 1963) can be used:
ε
h
=
s
R
2n
ln
2
δ
,
where R is the range of the random variable. Both bounds use the sum of inde-
pendent random variables and give a relative or absolute approximation of the
deviation of X from its expectation. They are independent of the distribution
of the random variable.
5.3.2.1 Error Estimators Using a Single Algorithm and a Single
Dataset
Prequential evaluation provides a learning curve that monitors the evo-
lution of learning ...