Large-Scale Machine Learning - Mining of Massive Datasets - page 429

We can also apply the Winnow Algorithm to the modified data. Winnow requires all fea-
ture vectors to have 0's and 1's, as components. However, we can allow a −1 in the feature
vector component for θ if we treat it in the manner opposite to the way we treat compon-
ents that are 1. That is, if the training example is positive, and we need to increase the other
weights, we instead divide the component for the threshold by 2. And if the training ex-
ample is negative, and we need to decrease the other weights, we multiply the threshold
component by 2.

EXAMPLE 12.6 Let us modify the training set of Fig. 12.6 to incorporate a sixth “word” that
represents the negative − θ of the threshold. The new data is shown in Fig. 12.8 .

Figure 12.8 Training data for spam emails, with a sixth component representing the negative of the threshold

We begin with a weight vector w with six 1's, as shown in the first line of Fig. 12.9 .
When we compute w . a = 3, using the first feature vector a , we are happy because the train-
ing example is positive, and so is the dot product. However, for the second training ex-
ample, we compute w . b = 1. Since the example is negative and the dot product is positive,
we must adjust the weights. Since b has 1's in the third and fourth components, the 1's in
the corresponding components of w are replaced by 1/2. The last component, correspond-
ing to θ , must be doubled. These adjustments give the new weight vector shown in

the third line of Fig. 12.9 .

Figure 12.9 Sequence of updates to w performed by the Winnow Algorithm on the training set of Fig. 12.8

The feature vector c is a positive example, but Thus, we must double the second
and third components of w , because c has 1 in the corresponding components, and we must
halve the last component of w , which corresponds to θ . The resulting is shown in
the fourth line of Fig. 12.9 . Next, d is a negative example. Since w . we must again ad-
just weights. We halve the weights in the first and fourth components and double the last
component, yielding Now, all positive examples have a positive dot product with
the weight vector, and all negative examples have a negative dot product, so there are no
further changes to the weights.