492
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
12.3.4
SVM Solutions by Gradient Descent
A common approach to solving Equation 12.4 is to use quadratic programming.
For large-scale data, another approach, gradient descent has an advantage. We
can allow the data to reside on disk, rather than keeping it all in memory, which
is normally required for quadratic solvers. To implement gradient descent, we
compute the derivative of the equation with respect to b and each component
wj of the vector w. Since we want to minimize f(w, b), we move b and the
components wj in the direction opposite to the direction of the gradient. The
amount we move each component is proportional to the derivative with respect
to that component.
Our ﬁrst step is to use the trick of Section 12.2.4 to make b part of the
weight vector w. Notice that b is really the negative of a threshold on the dot
product w.x, so we can append a (d + 1)st component b to w and append an
extra component with value +1 to every feature vector in the training set (not
−1 as we did in Section 12.2.4).
We must choose a constant η to be the fraction of the gradient that we move
w in each round. That is, we assign
wj := wj −η ∂f
∂wj
for all j = 1, 2, . . . , d + 1.
The derivative
∂f
∂wj of the ﬁrst term in Equation 12.4, 1
2
Pd
j=1 w2
i , is easy;
it is wj. However, the second term involves the hinge function, so it is harder
to express. We shall use an if-then expression to describe these derivatives, as
in Equation 12.5. That is:
∂f
∂wj
= wj + C
n
X
i=1

if yi(
d
X
j=1
wjxij + b) ≥1 then 0 else −yixij

(12.6)
Note that this formula gives us a partial derivative with respect to each compo-
nent of w, including wd+1, which is b, as well as to the weights w1, w2, . . . , wd.
We continue to use b instead of the equivalent wd+1 in the if-then condition to
remind us of the form in which the desired hyperplane is described.
To execute the gradient-descent algorithm on a training set, we pick:
1. Values for the parameters C and η.
2. Initial values for w, including the (d + 1)st component b.
Then, we repeatedly:
(a) Compute the partial derivatives of f(w, b) with respect to the wj’s.
(b) Adjust the values of w by subtracting η ∂f
∂wj from each wj.
