12.2. PERCEPTRONS
471
see what pages it links to. Those pages can safely be assumed to be relevant to
the given topic.
In some applications we can use the stars that people use to rate products
or services on sites like Amazon or Yelp.
For example, we might want to
estimate the number of stars that would be assigned to reviews or tweets about
a product, even if those reviews or tweets do not themselves have star ratings. If
we use star-labeled reviews as a training set, we can deduce the words that are
most commonly associated with positive and negative reviews (called sentiment
analysis). The presence of these words in other reviews can tell us the sentiment
of those reviews.
12.1.5
Exercises for Section 12.1
Exercise 12.1.1: Redo Example 12.2 for the following diﬀerent forms of f(x).
(a) Require f(x) = ax; i.e., a straight line through the origin. Is the line
y = 14
15x that we discussed in the example optimal?
(b) Allow f(x) to be a quadratic, i.e., f(x) = ax2 + bx + c.
12.2
Perceptrons
A perceptron is a linear binary classiﬁer. Its input is a vector x = [x1, x2, . . . , xd]
with real-valued components. Associated with the perceptron is a vector of
weights w = [w1, w2, . . . , wd], also with real-valued components. Each percep-
tron has a threshold θ. The output of the perceptron is +1 if w.x > θ, and
the output is −1 if w.x < θ. The special case where w.x = θ will always be
regarded as “wrong,” in the sense that we shall describe in detail when we get
to Section 12.2.1.
The weight vector w deﬁnes a hyperplane of dimension d −1 – the set of
all points x such that w.x = θ, as suggested in Fig. 12.4. Points on the pos-
itive side of the hyperplane are classiﬁed +1 and those on the negative side
are classiﬁed −1. A perceptron classiﬁer works only for data that is linearly
separable, in the sense that there is some hyperplane that separates all the pos-
itive points from all the negative points. If there are many such hyperplanes,
the perceptron will converge to one of them, and thus will correctly classify all
the training points. If no such hyperplane exists, then the perceptron cannot
converge to any hyperplane.
In the next section, we discuss support-vector
machines, which do not have this limitation; they will converge to some separa-
tor that, although not a perfect classiﬁer, will do as well as possible under the
metric to be described in Section 12.3.
12.2.1
Training a Perceptron with Zero Threshold
To train a perceptron, we examine the training set and try to ﬁnd a weight
vector w and threshold θ such that all the feature vectors with y = +1 (the
