109
Online Learning
for t =1,2,...
receive question x
t
∈X
predict p
t
∈ D
receive true answer y
t
∈Y
suffer loss l(p
t
,y
t
)
The specific case of yes/no answers and predictions, namely D =
Y = {0,1}, is called online classification. In this case it is natural to
use the 0–1 loss function: l(p
t
,y
t
)=|p
t
− y
t
|. That is, l(p
t
,y
t
) indicates
if p
t
= y
t
(the prediction is correct) or p
t
= y
t
(the prediction is wrong).
For example, consider the problem of predicting whether it is going
to rain tomorrow. On day t, the question x
t
can be encoded as a vector
of meteorological measurements. Based on these measurements, the
learner should predict if it’s going to rain tomorrow. In the following
day, the learner knows the correct answer.
We can also allow the learner to output a prediction in [0,1], which
can be interpreted as the probability of raining tomorrow. This is an
example of an application in which D = Y. We can still use the loss
function l(p
t
,y
t
)=|p
t
− y
t
|, which can now be interpreted as the prob-
ability to err if predicting that it’s going to rain with probability p
t
.
The learner’s ultimate goal is to minimize the cumulative loss suf-
fered along its run, which translates to making few prediction mistakes
in the classification case. The learner tries to deduce information from
previous rounds so as to improve its predictions on present and future
questions. Clearly, learning is hopeless if there is no correlation between
past and present rounds. Classic statistical theory of sequential predic-
tion therefore enforces strong assumptions on the statistical properties
of the input sequence (e.g., that it is sampled i.i.d. according to some
unknown distribution).
In this review we survey methods which make no statistical assump-
tions regarding the origin of the sequence of examples. The sequence is
allowed to be deterministic, stochastic, or even adversarially adaptive
to the learner’s own behavior (as in the case of spam email filtering).
Naturally, an adversary can make the cumulative loss to our online
weblqdai2015-10-31这是很好的书，谢谢
