516
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
Ensemble Methods
Decision forests are but one example of an important strategy for making
good decisions. We can use several diﬀerent algorithms to make the same
decision. Then, we combine the opinions of the diﬀerent algorithms in
some way, perhaps by learning the best weights as we suggested in Sec-
tion 12.5.8. In the case of a decision forest, all the contributing algorithms
are of the same type: a decision tree. However, the decision algorithms
can also be of diﬀerent kinds. For example, the winning solution to the
Netﬂix challenge (see Section 9.5) was of this type, where several diﬀer-
ent machine-learning techniques were each applied, and their movie-rating
estimates combined to make a better decision.
they often do much better on test data than any one tree, however many levels
it has. Further, we can design each of the trees in the forest in parallel, so it
can be even faster to design a large collection of shallow trees than to design
one deep tree.
The obvious way to combine the outcomes from all the trees in a decision
forest is to take a majority vote. If there are more than two classes, then we
only expect a plurality of votes for one of the classes, while no class may be the
choice of more than half the trees. However, more complex ways of combining
the trees’ results may yield a more accurate answer than straightforward voting.
We can often “learn” the proper weights to apply to the opinions of each tree.
For example, suppose we have a training set (x1, y1), (x2, y2), . . . , (xn, yn)
and a collection of decision trees T1, T2, . . . , Tk that constitute our decision
forest.
When we apply the decision forest to one of the training examples
(xi, yi), we get a vector of classes ci = [ci1, ci2, . . . , cik], where cij is the outcome
of tree Tj applied to input xi. We know the correct class for the input xi; it is
yi. Thus, we have a new training set (c1, y1), (c2, y2), . . . , (cn, yn), that we can
use to predict the true class from the opinions of all the trees in the forest. For
instance, we could use this training set to train a perceptron or SVM. By doing
so, we place the right weights on the opinion of each of the trees, in order to
combine their opinions optimally.
12.5.9
Exercises for Section 12.5
Exercise 12.5.1: Suppose a training set has examples in four classes, and the
fractions of examples in these classes are 1/2, 1/3, 1/8, and 1/24. What is
the impurity of the root of a decision tree designed for this training set, if the
measure of impurity is (a) Accuracy (b) GINI (c) Entropy?
Exercise 12.5.2: If a dataset consists of examples belonging to n diﬀerent
classes, what is the maximum impurity if the measure of impurity is (a) Accu-
