12.6. COMPARISON OF LEARNING METHODS
517
racy (b) GINI (c) Entropy?
! Exercise 12.5.3: An important property of a function f is convexity, meaning
that if x < z < y, then
f(z) > z −x
y −xf(x) + y −z
y −xf(y)
Less formally, the curve of f between x and y lies above the straight line be-
tween the points
x, f(x)

and
y, f(y)

. In the following, assume there are two
classes, and f(x) is the impurity when x is the fraction of examples in the ﬁrst
class.
(a) Prove that the GINI impurity is convex.
(b) Prove that the Entropy measure of impurity is convex.
(c) Give an example to show that the Accuracy measure of impurity is not
always convex. Hint: Note that convexity requires strict inequality; a
straight line is not convex.
Exercise 12.5.4: To see why convexity is important, repeat the calculation of
Fig. 12.27, but using Accuracy as the impurity measure. What goes wrong?
Exercise 12.5.5: Continuing Example 12.19, suppose we have replaced the
node labeled “Continent = NA” by a leaf labeled “Baseball.” Which other
interior nodes do you think can be replaced by leaves without a signiﬁcant
increase to the error rate when the tree is applied to all countries of the world?
12.6
Comparison of Learning Methods
Each of the methods discussed in this chapter and elsewhere has its advantages.
In this closing section, we shall consider:
• Does the method deal with categorical features or only with numerical
features?
• Does the method deal eﬀectively with high-dimensional feature vectors?
• Is the model that the method constructs intuitively understandable?
Perceptrons and Support-Vector Machines: These methods can handle
millions of features, but they only make sense if the features are numerical.
They only are eﬀective if there is a linear separator, or at least a hyperplane
that approximately separates the classes. However, we can separate points by
a nonlinear boundary if we ﬁrst transform the points to make the separator
be linear. The model is expressed by a vector, the normal to the separating
