496
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
using other sets of training examples; these can be selected randomly or accord-
ing to some ﬁxed strategy. Note that it is normal that some members of the
training set are never used in a stochastic gradient descent algorithm.
Example 12.10 : Recall the UV-decomposition algorithm discussed in Sec-
tion 9.4.3. This algorithm was described as an example of batch gradient de-
scent. We can regard each of the nonblank entries in the matrix M we are
trying to approximate by the product UV as a training example, and the error
function is the root-mean-square error between the product of the current ma-
trices U and V and the matrix M, considering only those elements where M is
nonblank.
However, if M has a very large number of nonblank entries, as would be the
case if M represented, say, purchases of items by Amazon customers or movies
that Netﬂix customers had rated, then it is not practical to make repeated
passes over the entire set of nonblank entries of M when adjusting the entries
in U and V . A stochastic gradient descent implementation would look at a
single nonblank entry of M and compute the change to each element of U and
V that would make the product UV agree with that element of M. We would
not make that change to the elements of U and V completely, but rather choose
some learning rate η less than 1 and change each element of U and V by the
fraction η of the amount that would be necessary to make UV equal M in the
chosen entry.
✷
There is a compromise between batch and stochastic gradient descent called
minibatch gradient descent. In the minibatch version, we partition the entire
training set into “minibatches,” of some chosen size, e.g., 1000 training exam-
ples.
We work on one minibatch at a time, computing changes to w using
Equation 12.4, but summing only over the selected training examples.
12.3.6
Parallel Implementation of SVM
The ﬁrst observation is that stochastic gradient descent is inherently serial,
since the state of the system – the vector w and the constant b – changes with
every training example considered. On the other hand, batch gradient descent
is most easily parallelized, since it uses each training example starting from the
same state, and only combines the eﬀects of these training examples at the end
of a round.
Thus, we can parallelize SVM using gradient descent in a manner analogous
to what we suggested for perceptrons in Section 12.2.8. You can start with the
current w and b and divide the training examples into minibatches, creating one
task for each minibatch. The tasks each apply Equation 12.4 to their minibatch,
and the changes to the state, w and b, are summed after one parallel round.
The new state is computed by summing all the changes, and the process can
repeat with the new state distributed to all the tasks.
