514
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
list of numbers a1, a2, . . . , an, and we wish to compute xi = Pi
j=1 aj for all
i = 1, 2, . . ., n. It might appear that we need n steps to compute all the xi’s,
and that could be time consuming when n is large; i.e., there is a large training
set. However, there is a divide-and-conquer algorithm to calculate all the x’s
in O(log n) parallel steps, as follows:
BASIS: If n = 1, then x1 = a1. The basis requires one parallel step.
INDUCTION: If n > 1, divide the list of a’s into a left half and a right half,
as evenly as possible. That is, if n is even, the left half is a1, a2, . . . , an/2, and
the right half is an/2+1, an/2+2, . . . , an. If n is odd, then the left half ends with
a⌊n/2⌋and the right half begins with a⌈n/2⌉.
Left−half
Accumulated Sums
Accumulated Sums
Right−half
All Accumulated Sums
n/2
add to each
x
Figure 12.29: Recursive step in parallel computation of accumulated sums
The recursive step is suggested by Fig. 12.29. In parallel, we apply this
algorithm to the left and right halves. Once we have done so, the last accu-
mulated sum of the left half, shown as xn/2, is then added in parallel to each
of the accumulated sums of the right half. As a result, if the ith result in the
right half is Pi
j=n/2+1 aj, we have, by adding xn/2 to it, changed its value to
the correct Pn/2+i
j=1
aj.
Each time we apply the recursive step, we require only one addition, done in
parallel. If n is a power of 2, then each application of the recursive step divides
the size of the lists we need to work on by 2, so the total number of parallel
steps is 1 + log2 n. If n is not a power of 2, the number of times we perform the
recursive step is no greater than what we would need if n were the next higher
power of 2. Thus, 1 + ⌈log2 n⌉parallel steps suﬃces for any n.
12.5.7
Node Pruning
If we design a decision tree using as many levels as needed so that each leaf
is pure, we are likely to have overﬁt to the training data. If we can verify our
design using other examples – either a test set that we have withheld from the
training data or a set of new data – we have the opportunity to simplify the
tree and at the same time limit the overﬁtting.
