12.2. PERCEPTRONS
483
Figure 12.13: Perceptrons converge as soon as the separating hyperplane reaches
the region between classes
parallelism by computing dot products in parallel. However, as we discussed in
connection with Example 12.4, high-dimensional vectors are likely to be sparse
and can be represented more succinctly than would be expected from their
length.
In order to get signiﬁcant parallelism, we have to modify the perceptron
algorithm slightly, so that many training examples (a “batch”) are used with the
same estimated weight vector w. This algorithm modiﬁcation changes slightly
what the algorithm does, when compared with the sequential implementation
where we change w after every misclassiﬁed training example. However, if the
learning rate is small, as it normally is, then reusing a single w for many training
examples makes little diﬀerence in the resulting value of w after the batch of
training examples are considered. As an example, let us formulate the parallel
algorithm as a MapReduce job.
The Map Function: Each Map task is given a chunk of training examples,
and each Map task knows the current weight vector w. The Map task computes
w.x for each feature vector x = [x1, x2, . . . , xk] in its chunk and compares that
dot product with the label y, which is +1 or −1, associated with x. If the signs
agree, no key-value pairs are produced for this training example. However, if
the signs disagree, then for each nonzero component xi of x the key-value pair
(i, ηyxi) is produced; here, η is the learning-rate constant used to train this
perceptron.
Notice that ηyxi is the increment we would like to add to the
current ith component of w, and if xi = 0, then there is no need to produce
a key-value pair. In the interests of parallelism, we defer that change until we
can accumulate many changes in the Reduce phase.
The Reduce Function: For each key i, the Reduce task that handles key i
adds all the associated increments and then adds that sum to the ith component
