12.2. PERCEPTRONS
479
example is negative and the dot product is positive, we must adjust the weights.
Since b has 1’s in the third and fourth components, the 1’s in the corresponding
components of w are replaced by 1/2. The last component, corresponding to θ,
must be doubled. These adjustments give the new weight vector [1, 1, 1
2, 1
2, 1, 2]
shown in the third line of Fig. 12.9.
The feature vector c is a positive example, but w.c = −1
2. Thus, we must
double the second and third components of w, because c has 1 in the cor-
responding components, and we must halve the last component of w, which
corresponds to θ. The resulting w = [1, 2, 1, 1
2, 1, 1] is shown in the fourth line
of Fig. 12.9. Next, d is a negative example. Since w.d = 1
2, we must again
adjust weights. We halve the weights in the ﬁrst and fourth components and
double the last component, yielding w = [ 1
2, 2, 1, 1
4, 1, 2]. Now, all positive ex-
amples have a positive dot product with the weight vector, and all negative
examples have a negative dot product, so there are no further changes to the
weights.
The designed perceptron has a threshold of 2. It has weights 2 and 1 for
“viagra” and “nigeria” and smaller weights for “and” and “of.” It also has
weight 1 for “the,” which suggests that “the” is as indicative of spam as “nige-
ria,” something we doubt is true. Nevertheless, this perceptron does classify all
examples correctly.
✷
12.2.5
Multiclass Perceptrons
There are several ways in which the basic idea of the perceptron can be ex-
tended. We shall discuss transformations that enable hyperplanes to serve as
nonlinear boundaries in the next section. Here, we look at how perceptrons can
be used to classify data into many classes.
Suppose we are given a training set with labels in k diﬀerent classes. Start
by training a perceptron for each class; these perceptrons should each have the
same threshold θ. That is, for class i treat a training example (x, i) as a positive
example, and all examples (x, j), where j ̸= i, as a negative example. Suppose
that the weight vector of the perceptron for class i is determined to be wi after
training.
Given a new vector x to classify, we compute wi.x for all i = 1, 2, . . ., k. We
take the class of x to be the value of i for which wi.x is the maximum, provided
that value is at least θ. Otherwise, x is assumed not to belong to any of the k
classes.
For example, suppose we want to classify Web pages into a number of topics,
such as sports, politics, medicine, and so on. We can represent Web pages by a
vector with 1 for each word present in the page and 0 for words not present (of
course we would only visualize the pages that way; we wouldn’t construct the
vectors in reality). Each topic has certain words that tend to indicate that topic.
For instance, sports pages would be full of words like “win,” “goal,” “played,”
and so on. The weight vector for that topic would give higher weights to the
words that characterize that topic.
