478
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
Then, for the new training set and weight vector, we can treat the threshold
as 0 and use the algorithm of Section 12.2.1. The justiﬁcation is that w′.x′ > 0
is equivalent to Pd
i=1 wixi+θ×−1 = w.x−θ > 0, which in turn is equivalent to
w.x > θ. The latter is the condition for a positive response from a perceptron
with threshold θ.
We can also apply the Winnow Algorithm to the modiﬁed data. Winnow
requires all feature vectors to have 0’s and 1’s, as components. However, we can
allow a −1 in the feature vector component for θ if we treat it in the manner
opposite to the way we treat components that are 1. That is, if the training
example is positive, and we need to increase the other weights, we instead divide
the component for the threshold by 2. And if the training example is negative,
and we need to decrease the other weights we multiply the threshold component
by 2.
and
viagra
the
of
nigeria
θ
y
a
1
1
0
1
1
−1
+1
b
0
0
1
1
0
−1
−1
c
0
1
1
0
0
−1
+1
d
1
0
0
1
0
−1
−1
e
1
0
1
0
1
−1
+1
f
1
0
1
1
0
−1
−1
Figure 12.8: Training data for spam emails, with a sixth component representing
the negative of the threshold
Example 12.6 : Let us modify the training set of Fig. 12.6 to incorporate a
sixth “word” that represents the negative −θ of the threshold. The new data
is shown in Fig. 12.8.
x
y
w.x
OK?
and
viagra
the
of
nigeria
θ
1
1
1
1
1
1
a
+1
3
yes
b
−1
1
no
1
1
1
2
1
2
1
2
c
+1
−1
2
no
1
2
1
1
2
1
1
d
−1
1
2
no
1
2
2
1
1
4
1
2
Figure 12.9: Sequence of updates to w performed by the Winnow Algorithm
on the training set of Fig. 12.8
We begin with a weight vector w with six 1’s, as shown in the ﬁrst line
of Fig. 12.9. When we compute w.a = 3, using the ﬁrst feature vector a, we
are happy because the training example is positive, and so is the dot product.
However, for the second training example, we compute w.b = 1. Since the
