12.1. THE MACHINE-LEARNING MODEL
467
dictionary, because these words tend not to tell us much about the subject mat-
ter of the document. Similarly, we might also restrict the dictionary to words
with high TF.IDF scores (see Section 1.3.1) so the words considered would tend
to reﬂect the topic or substance of the document.
The training set consists of pairs, where the vector x represents the presence
or absence of each dictionary word in document. The label y could be +1 or
−1, with +1 representing that the document (an email, e.g.) is spam. Our goal
would be to train a classiﬁer to examine future emails and decide whether or not
they are spam. We shall illustrate this use of machine learning in Example 12.4.
Alternatively, y could be chosen from some ﬁnite set of topics, e.g., “sports,”
“politics,” and so on. Again, x could represent a document, perhaps a Web
page. The goal would be to create a classiﬁer for Web pages that assigned a
topic to each.
✷
12.1.3
Approaches to Machine Learning
There are many forms of ML algorithms, and we shall not cover them all here.
Here are the major classes of such algorithms, each of which is distinguished by
the form by which the function f is represented.
1. Decision trees were discussed brieﬂy in Section 9.2.7 and will be covered
more extensively in Section 12.5. The form of f is a tree, and each node of
the tree has a function of x that determines to which child or children the
search must proceed. Decision trees are suitable for binary and multiclass
classiﬁcation, especially when the dimension of the feature vector is not
too large (large numbers of features can lead to overﬁtting).
2. Perceptrons are threshold functions applied to the components of the vec-
tor x = [x1, x2, . . . , xn]. A weight wi is associated with the ith component,
for each i = 1, 2, . . ., n, and there is a threshold θ. The output is +1 if
n
X
i=1
wixi > θ
and the output is −1 if that sum is less than θ. A perceptron is suitable
for binary classiﬁcation, even when the number of features is very large,
e.g., the presence or absence of words in a document. Perceptrons are the
topic of Section 12.2.
3. Neural nets are acyclic networks of perceptrons, with the outputs of some
perceptrons used as inputs to others. These are suitable for binary or
multiclass classiﬁcation, since there can be several perceptrons used as
output, with one or more indicating each class.
4. Instance-based learning uses the entire training set to represent the func-
tion f. The calculation of the label y associated with a new feature vector
x can involve examination of the entire training set, although usually some
