12.3. SUPPORT-VECTOR MACHINES
487
on the points of Fig. 11.1, where it turns out that all four points are support
vectors, even though two-dimensional data normally has three.
A tentative statement of our goal is:
• Given a training set (x1, y1), (x2, y2), . . . , (xn, yn), maximize γ (by varying
w and b) subject to the constraint that for all i = 1, 2, . . ., n,
yi(w.xi + b) ≥γ
Notice that yi, which must be +1 or −1, determines which side of the hyperplane
the point xi must be on, so the ≥relationship to γ is always correct. However, it
may be easier to express this condition as two cases: if y = +1, then w.x+b ≥γ,
and if y = −1, then w.x + b ≤−γ.
Unfortunately, this formulation doesn’t really work properly. The problem
is that by increasing w and b, we can always allow a larger value of γ. For
example, suppose that w and b satisfy the constraint above. If we replace w
by 2w and b by 2b, we observe that for all i, yi
(2w).xi + 2b

≥2γ. Thus, 2w
and 2b is always a better choice that w and b, so there is no best choice and no
maximum γ.
12.3.2
Normalizing the Hyperplane
The solution to the problem that we described intuitively above is to normalize
the weight vector w. That is, the unit of measure perpendicular to the sepa-
rating hyperplane is the unit vector w/∥w∥. Recall that ∥w∥is the Frobenius
norm, or the square root of the sum of the squares of the components of w. We
shall require that w be such that the parallel hyperplanes that just touch the
support vectors are described by the equations w.x+b = +1 and w.x+b = −1,
as suggested by Fig. 12.15. We shall refer to the hyperplanes deﬁned by these
two equations as the upper and lower hyperplanes, respectively.
It looks like we have set γ = 1. But since we are using w as the unit vector,
the margin γ is the number of “units,” that is, steps in the direction w needed
to go between the separating hyperplane and the parallel hyperplanes. Our goal
becomes to maximize γ, which is now the multiple of the unit vector w/∥w∥
between the separating hyperplane and the upper and lower hyperplanes.
Our ﬁrst step is to demonstrate that maximizing γ is the same as minimizing
∥w∥. Consider one of the support vectors, say x2 shown in Fig. 12.15. Let x1 be
the projection of x2 onto the upper hyperplane, also as suggested by Fig. 12.15.
Note that x1 need not be a support vector or even a point of the training set.
The distance from x2 to x1 in units of w/∥w∥is 2γ. That is,
x1 = x2 + 2γ w
∥w∥
(12.1)
Since x1 is on the hyperplane deﬁned by w.x + b = +1, we know that
w.x1 + b = 1. If we substitute for x1 using Equation 12.1, we get
w.

x2 + 2γ w
∥w∥

+ b = 1
