474
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
Pragmatics of Training on Emails
When we represent emails or other large documents as training examples,
we would not really want to construct the vector of 0’s and 1’s with a
component for every word that appears even once in the collection of
emails. Doing so would typically give us sparse vectors with millions of
components. Rather, create a table in which all the words appearing in the
emails are assigned integers 1, 2, . . ., indicating their component. When we
process an email in the training set, make a list of the components in which
the vector has 1; i.e., use the standard sparse representation for the vector.
If we eliminate stop words from the representation, or even eliminate words
with a low TF.IDF score, then we make the vectors representing emails
signiﬁcantly sparser and thus compress the data even more.
Only the
vector w needs to have all its components listed, since it will not be sparse
after a small number of training examples have been processed.
y for b is −1, b is misclassiﬁed. We thus assign
w := w + (1/2)(−1)b = [1
2, 1
2, 0, 1
2, 1
2] −[0, 0, 1
2, 1
2, 0] = [1
2, 1
2, −1
2, 0, 1
2]
Training example c is next. We compute
w.c = [1
2, 1
2, −1
2, 0, 1
2].[0, 1, 1, 0, 0] = 0
Since the associated y for c is +1, c is also misclassiﬁed. We thus assign
w := w + (1/2)(+1)c = [1
2, 1
2, −1
2, 0, 1
2] + [0, 1
2, 1
2, 0, 0] = [1
2, 1, 0, 0, 1
2]
Training example d is next to be considered:
w.d = [1
2, 1, 0, 0, 1
2].[1, 0, 0, 1, 0] = 1
Since the associated y for d is −1, d is misclassiﬁed as well. We thus assign
w := w + (1/2)(−1)d = [1
2, 1, 0, 0, 1
2] −[1
2, 0, 0, 1
2, 0] = [0, 1, 0, −1
2, 1
2]
For training example e we compute w.e = [0, 1, 0, −1
2, 1
2].[1, 0, 1, 0, 1] = 1
2.
Since the associated y for e is +1, e is classiﬁed correctly, and no change to w
is made. Similarly, for f we compute
w.f = [0, 1, 0, −1
2, 1
2].[1, 0, 1, 1, 0] = −1
2
