12.2. PERCEPTRONS
477
The next two training examples, d and e require no change, since they are
correctly classiﬁed. However, there is a problem with f = [1, 0, 1, 1, 0], since
w.f = 6 > θ, while the associated label for f is −1. Thus, we must divide the
ﬁrst, third, and fourth components of w by 2, since these are the components
where f has 1. The new value of w is [1, 4, 1, 1, 2].
x
y
w.x
OK?
and
viagra
the
of
nigeria
1
1
1
1
1
a
+1
4
no
2
2
1
2
2
b
−1
3
yes
c
+1
3
no
2
4
2
2
2
d
−1
4
yes
e
+1
6
yes
f
−1
6
no
1
4
1
1
2
a
+1
8
yes
b
−1
2
yes
c
+1
5
no
1
8
2
1
2
d
−1
2
yes
e
+1
5
no
2
8
4
1
4
f
−1
7
no
1
8
2
1
2
4
Figure 12.7: Sequence of updates to w performed by the Winnow Algorithm
on the training set of Fig. 12.6
We still have not converged.
It turns out we must consider each of the
training examples a through f again. At the end of this process, the algorithm
has converged to a weight vector w = [1, 8, 2, 1
2, 4], which with threshold θ = 5
correctly classiﬁes all of the training examples in Fig. 12.6.
The details of
the twelve steps to convergence are shown in Fig. 12.7. This ﬁgure gives the
associated label y and the computed dot product of w and the given feature
vector. The last ﬁve columns are the ﬁve components of w after processing
each training example.
✷
12.2.4
Allowing the Threshold to Vary
Suppose now that the choice of threshold 0, as in Section 12.2.1, or threshold d,
as in Section 12.2.3 is not desirable, or that we don’t know the best threshold
to use. At the cost of adding another dimension to the feature vectors, we can
treat θ as one of the components of the weight vector w. That is:
1. Replace the vector of weights w = [w1, w2, . . . , wd] by
w′ = [w1, w2, . . . , wd, θ]
2. Replace every feature vector x = [x1, x2, . . . , xd] by
x′ = [x1, x2, . . . , xd, −1]
