470
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
2. Adapt to changes in the population of training examples as time goes on.
For instance, Google trains its spam-email classiﬁer this way, adapting
the classiﬁer for spam as new kinds of spam email are sent by spammers
and indicated to be spam by the recipients.
An enhancement of on-line learning, suitable in some cases, is active learn-
ing. Here, the classiﬁer may receive some training examples, but it primarily
receives unclassiﬁed data, which it must classify. If the classiﬁer is unsure of
the classiﬁcation (e.g., the newly arrived example is very close to the bound-
ary), then the classiﬁer can ask for ground truth at some signiﬁcant cost. For
instance, it could send the example to Mechanical Turk and gather opinions of
real people. In this way, examples near the boundary become training examples
and can be used to modify the classiﬁer.
Feature Selection
Sometimes, the hardest part of designing a good model or classiﬁer is ﬁguring
out what features to use as input to the learning algorithm. Let us reconsider
Example 12.3, where we suggested that we could classify emails as spam or not
spam by looking at the words contained in the email. In fact, we explore in
detail such a classiﬁer in Example 12.4. As discussed in Example 12.3, it may
make sense to focus on certain words and not others; e.g., we should eliminate
stop words.
But we should also ask whether there is other information available that
would help us make a better decision about spam. For example, spam is often
generated by particular hosts, either those belonging to the spammers, or hosts
that have been coopted into a “botnet” for the purpose of generating spam.
Thus, including the originating host or originating email address into the feature
vector describing an email might enable us to design a better classiﬁer and lower
the error rate.
Creating a Training Set
It is reasonable to ask where the label information that turns data into a train-
ing set comes from. The obvious method is to create the labels by hand, having
an expert look at each feature vector and classify it properly. Recently, crowd-
sourcing techniques have been used to label data. For example, in many appli-
cations it is possible to use Mechanical Turk to label data. Since the “Turkers”
are not necessarily reliable, it is wise to use a system that allows the question
to be asked of several diﬀerent people, until a clear majority is in favor of one
label.
One often can ﬁnd data on the Web that is implicitly labeled. For example,
the Open Directory (DMOZ) has millions of pages labeled by topic. That data,
used as a training set, can enable one to classify other pages or documents
according to their topic, based on the frequency of word occurrence. Another
approach to classifying by topic is to look at the Wikipedia page for a topic and
