520
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
descent), or the result of using a small subset of the training examples
(minibatch gradient descent).
✦Nearest-Neighbor Learning: In this approach to machine learning, the
entire training set is used as the model. For each (“query”) point to be
classiﬁed, we search for its k nearest neighbors in the training set. The
classiﬁcation of the query point is some function of the labels of these k
neighbors. The simplest case is when k = 1, in which case we can take
the label of the query point to be the label of the nearest neighbor.
✦Regression: A common case of nearest-neighbor learning, called regres-
sion, occurs when the there is only one feature vector, and it, as well as
the label, are real numbers; i.e., the data deﬁnes a real-valued function of
one variable. To estimate the label, i.e., the value of the function, for an
unlabeled data point, we can perform some computation involving the k
nearest neighbors. Examples include averaging the neighbors or taking a
weighted average, where the weight of a neighbor is some decreasing func-
tion of its distance from the point whose label we are trying to determine.
✦Decision Trees: This learning method constructs a tree where each inte-
rior node holds a test about the input and sends us to one of its children
depending on the outcome of the test. Each leaf gives a decision about
the class to which the input belongs.
✦Impurity Measures: To help design a decision tree, we need a measure
of how pure, i.e., close to a single class, is the set of training examples
that reach a particular node of the decision tree. Possible measures of
impurity include Accuracy (fraction of training examples with the wrong
class), GINI (1 minus the squares of the fractions of examples in each of
the classes), and Entropy (sum of the fractions of training examples in
each class times the logarithm of the inverse of that fraction).
✦Designing a Decision-Tree Node: We must consider each possible feature
to use for the test at a node, and we must break the set of training exam-
ples that reach the node in a way that minimizes the average impurity of
its children. For a numerical feature, we can order the traning examples
by the value of that feature and use a test that breaks this list in a way
that minimizes average impurity. For a categorical feature we order the
values of that feature by the fraction of training examples with that value
that belong to one particular class, and break the list to minimize average
impurity.
12.8
References for Chapter 12
The perceptron was introduced in [14]. [8] introduces the idea of maximizing the
margin around the separating hyperplane. A well-known book on the subject
is [12].
