12.3. SUPPORT-VECTOR MACHINES
489
Let w = [u, v]. Our goal is to minimize
√
u2 + v2 subject to the constraints
we derive from the four training examples. For the ﬁrst, where x1 = [1, 2] and
y1 = +1, the constraint is (+1)(u + 2v + b) = u + 2v + b ≥1. For the second,
where x2 = [2, 1] and y2 = −1, the constraint is (−1)(2u + v + b) ≥1, or
2u + v + b ≤−1. The last two points are analogously handled, and the four
constraints we derive are:
u + 2v + b ≥1
2u + v + b ≤−1
3u + 4v + b ≥1
4u + 3v + b ≤−1
We shall cover in detail the subject of how one optimizes under constraints;
the subject is broad and many packages are available for you to use.
Sec-
tion 12.3.4 discusses one method – gradient descent – in connection with a
more general application of SVM, where there is no separating hyperplane. An
illustration of how this method works will appear in Example 12.9.
In this simple example, the solution is easy to see: b = 0 and w = [u, v] =
[−1, +1]. It happens that all four constraints are satisﬁed exactly; i.e., each
of the four points is a support vector. That case is unusual, since when the
data is two-dimensional, we expect only three support vectors. However, the
fact that the positive and negative examples lie on parallel lines allows all four
constraints to be satisﬁed exactly.
✷
12.3.3
Finding Optimal Approximate Separators
We shall now consider ﬁnding an optimal hyperplane in the more general case,
where no matter which hyperplane we choose, there will be some points on the
wrong side, and perhaps some points that are on the correct side, but too close
to the separating hyperplane itself, so the margin requirement is not met. A
typical situation is shown in Fig. 12.16. We see two points that are misclassiﬁed;
they are on the wrong side of the separating hyperplane w.x + b = 0. We also
see two points that, while they are classiﬁed correctly, are too close to the
separating hyperplane. We shall call all these points bad points.
Each bad point incurs a penalty when we evaluate a possible hyperplane.
The amount of the penalty, in units to be determined as part of the optimization
process, is shown by the arrow leading to the bad point from the hyperplane
on the wrong side of which the bad point lies. That is, the arrows measure the
distance from the hyperplane w.x + b = 1 or w.x + b = −1. The former is
the baseline for training examples that are supposed to be above the separating
hyperplane (because the label y is +1), and the latter is the baseline for points
that are supposed to be below (because y = −1).
We have many options regarding the exact formula that we wish to mini-
mize. Intuitively, we want ∥w∥to be as small as possible, as we discussed in
Section 12.3.2. But we also want the penalties associated with the bad points
to be as small as possible. The most common form of a tradeoﬀis expressed
by a formula that involves the term ∥w∥2/2 and another term that involves a
constant times the sum of the penalties.
