12.3. SUPPORT-VECTOR MACHINES
495
get ∂f/∂v = 1 +
1
10
0 + (−2) + 0 + 0 + 0 + 0

= 0.8. Finally, for b we get
∂f/∂b = −2 + 1
10
0 + (−1) + 0 + 0 + 0 + 0

= −2.1.
We can now compute the new w and b that appear on line (2) of Fig. 12.20.
Since we chose η = 0.2, the new value of u is 0 −1
5(−0.2) = −0.04, the new
value of v is 1 −1
5(0.8) = 0.84, and the new value of b is −2 −1
5(−2.1) = −1.58.
To compute the derivatives shown in line (2) of Fig. 12.20 we must ﬁrst check
the conditions of Fig. 12.19. While the outcomes of the ﬁrst three conditions
have not changed, the last three are no longer satisﬁed.
For example, the
fourth condition is u + v + b ≤−1, but 0.04 + 0.84 + (−1.58) = −0.7, which is
not less than −1. Thus, the pattern of bad points becomes oxoxxx. We now
have more nonzero terms in the expressions for the derivatives. For example
∂f/∂u = 0.04 + 1
10
0 + (−2) + 0 + 1 + 2 + 3

= 0.44.
The values of w and b in line (3) are computed from the derivatives of
line (2) in the same way as they were computed in line (2). The new values
do not change the pattern of bad points; it is still oxoxxx. However, when we
repeat the process for line (4), we ﬁnd that all six conditions are unsatisﬁed.
For instance, the ﬁrst condition, u + 4v + b ≥+1 is not satisﬁed, because
(−0.118 + 4 × 0.502 + (−1.083) = 0.807, which is less than 1. In eﬀect, the
ﬁrst point has become too close to the separating hyperplane, even though it is
properly classiﬁed.
We can see that in line (5) of Fig. 12.20, the problems with the ﬁrst and
third points are corrected, and we go back to pattern oxoxxx of bad points.
However, at line (6), the points have again become too close to the separating
hyperplane, so we revert to the xxxxxx pattern of bad points. You are invited
to continue the sequence of updates to w and b for several more iterations.
One might wonder why the gradient-descent process seems to be converging
on a solution where at least some of the points are inside the margin, when
there is an obvious hyperplane (horizontal, at height 1.5) with a margin of 1/2,
that separates the positive and negative points. The reason is that when we
picked C = 0.1 we were saying that we really don’t care too much whether
there are points inside the margins, or even if points are misclassiﬁed. We were
saying also that what was important was a large margin (which corresponds to
a small ∥w∥), even if some points violated that same margin.
✷
12.3.5
Stochastic Gradient Descent
The gradient-descent algorithm described in Section 12.3.4 is often called batch
gradient descent, because at each round, all the training examples are consid-
ered as a “batch.” While it is eﬀective on small datasets, it can be too time-
consuming to execute on a large dataset, where we must visit every training
example, often many times before convergence.
An alternative, called stochastic gradient descent, considers one training ex-
ample, or a few training examples at a time and adjusts the current estimate of
the error function (w in the SVM example) in the direction indicated by only
the small set of training examples considered. Additional rounds are possible,
