484
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
Perceptrons on Streaming Data
While we have viewed the training set as stored data, available for repeated
use on any number of passes, perceptrons can also be used in a stream
setting. That is, we may suppose there is an inﬁnite sequence of training
examples, but that each may be used only once. Detecting email spam is
a good example of a training stream. Users report spam emails and also
report emails that were classiﬁed as spam but are not. Each email, as it
arrives, is treated as a training example, and modiﬁes the current weight
vector, presumably by a very small amount.
If the training set is a stream, we never really converge, and in fact
the data points may well not be linearly separable. However, at all times,
we have an approximation to the best possible separator. Moreover, if the
examples in the stream evolve over time, as would be the case for email
spam, then we have an approximation that values recent examples more
than examples from the distant past, much like the exponentially decaying
windows technique from Section 4.7.
of w.
Probably, these changes will not be enough to train the perceptron. If any
changes to w occur, then we need to start a new MapReduce job that does the
same thing, perhaps with diﬀerent chunks from the training set. However, even
if the entire training set was used on the ﬁrst round, it can be used again, since
its eﬀect on w will be diﬀerent if w has changed.
12.2.9
Exercises for Section 12.2
Exercise 12.2.1: Modify the training set of Fig. 12.6 so that example b also
includes the word “nigeria” (yet remains a negative example – perhaps someone
telling about their trip to Nigeria). Find a weight vector that separates the
positive and negative examples, using:
(a) The basic training method of Section 12.2.1.
(b) The Winnow method of Section 12.2.3.
(c) The basic method with a variable threshold, as suggested in Section 12.2.4.
(d) The Winnow method with a variable threshold, as suggested in Section
12.2.4.
! Exercise 12.2.2: For the following training set:
([1, 2], +1)
([2, 1], +1)
([2, 3], −1)
([3, 2], −1)
