12.3. SUPPORT-VECTOR MACHINES
485
A Key Trick to Obtain Parallelism
The method we used in Section 12.2.8 to turn an inherently serial process
into a parallel one appears frequently when dealing with large datasets. In
the serial version of the algorithm, there is a state that changes at every
step. In this case, the state is the weight vector w. As long as changes to
the state tend to be small at every step, we can ﬁx the state and calculate,
in parallel, the changes to this exact state that would be caused by each
of the serial steps. After the parallel step, combine the changes to make a
new state, and repeat the parallel step until convergence.
describe all the vectors w and thresholds θ such that the hyperplane (really a
line) deﬁned by w.x −θ = 0 separates the points correctly.
! Exercise 12.2.3: Suppose the following four examples constitute a training
set:
([1, 2], −1)
([2, 3], +1)
([2, 1], +1)
([3, 2], −1)
(a) What happens when you attempt to train a perceptron to classify these
points using 0 as the threshold?
!! (b) Is it possible to change the threshold and obtain a perceptron that cor-
rectly classiﬁes these points?
(c) Suggest a transformation using quadratic polynomials that will transform
these points so they become linearly separable.
12.3
Support-Vector Machines
We can view a support-vector machine, or SVM, as an improvement on the
perceptron that is designed to address the problems mentioned in Section 12.2.7.
An SVM selects one particular hyperplane that not only separates the points in
the two classes, but does so in a way that maximizes the margin – the distance
between the hyperplane and the closest points of the training set.
In this section, we begin with a discussion of SVM’s for training points
that are separable, and we show how to maximize the margin in such a case.
We then consider a more complex problem, where the points are not linearly
separable. In that case, our goal is diﬀerent. We need to ﬁnd a hyperplane
that does the best it can in separating the two classes. But “best” is a tricky
notion. We shall develop a loss function that penalizes misclassiﬁed points, but
also one that penalizes to a lesser extent points that are correctly classiﬁed but
are too close to the separating hyperplane. This matter will be taken up in
Section 12.3.3.
