468
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
preprocessing of the training set enables the computation of f(x) to pro-
ceed eﬃciently. We shall consider an important kind of instance-based
learning, k-nearest-neighbor, in Section 12.4.
For example, 1-nearest-
neighbor classiﬁes data by giving it the same class as that of its nearest
training example. There are k-nearest-neighbor algorithms that are ap-
propriate for any kind of classiﬁcation, although we shall concentrate on
the case where y and the components of x are real numbers.
5. Support-vector machines are an advance over the algorithms traditionally
used to select the weights and threshold. The result is a classiﬁer that
tends to be more accurate on unseen data. We discuss support-vector
machines in Section 12.3.
12.1.4
Machine-Learning Architecture
Machine-learning algorithms can be classiﬁed not only by their general algorith-
mic approach as we discussed in Section 12.1.3. but also by their underlying
architecture – the way data is handled and the way it is used to build the model.
Training, Validating, and Testing
One general issue regarding the handling of data is that there is a good reason to
withhold some of the available data from the training set. The remaining data
is called the test set. In some cases, we withhold two sets of training examples,
a validation set (sometimes called a development set), as well as the test set.
The diﬀerence is that the validation set is used to help design the model, while
the test set is used only to determine how good the model is. The problem
addressed by a validation set is that many machine-learning algorithms tend to
overﬁt the data; they pick up on artifacts that occur in the training set but that
are atypical of the larger population of possible data. By using the validation
set, and seeing how well the classiﬁer works on that, we can tell if the classiﬁer
is overﬁtting the data. If so, we can restrict the machine-learning algorithm in
some way. For instance, if we are constructing a decision tree, we can limit the
number of levels of the tree.
Figure 12.3 illustrates the train-and-test architecture. We assume all the
data is suitable for training (i.e., the class information is attached to the data),
but we separate out a small fraction of the available data as the test set. We
use the remaining data to build a suitable model or classiﬁer. Then we feed
the test data to this model. Since we know the class of each element of the
test data, we can tell how well the model does on the test data. If the error
rate on the test data is not much worse than the error rate of the model on the
training data itself, then we expect there is little, if any, overﬁtting, and the
model can be used. On the other hand, if the classiﬁer performs much worse
on the test data than on the training data, we expect there is overﬁtting and
need to rethink the way we construct the classiﬁer.
