472
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
w
w.x = θ
Figure 12.4: A perceptron divides a space by a hyperplane into two half-spaces
positive examples) are on the positive side of the hyperplane and all those with
y = −1 (the negative examples) are on the negative side. It may or may not be
possible to do so, since there is no guarantee that any hyperplane separates all
the positive and negative examples in the training set.
We begin by assuming the threshold is 0; the simple augmentation needed
to handle an unknown threshold is discussed in Section 12.2.4. The follow-
ing method will converge to some hyperplane that separates the positive and
negative examples, provided one exists.
1. Initialize the weight vector w to all 0’s.
2. Pick a learning-rate parameter η, which is a small, positive real number.
The choice of η aﬀects the convergence of the perceptron. If η is too small,
then convergence is slow; if it is too big, then the decision boundary will
“dance around” and again will converge slowly, if at all.
3. Consider each training example t = (x, y) in turn.
(a) Let y′ = w.x.
(b) If y′ and y have the same sign, then do nothing; t is properly classi-
ﬁed.
(c) However, if y′ and y have diﬀerent signs, or y′ = 0, replace w by
w + ηyx. That is, adjust w slightly in the direction of x.
The two-dimensional case of this transformation on w is suggested in Fig.
12.5. Notice how moving w in the direction of x moves the hyperplane that is
perpendicular to w in such a direction that it makes it more likely that x will
be on the correct side of the hyperplane, although it does not guarantee that x
will then be correctly classiﬁed.
