12.4. LEARNING FROM NEAREST NEIGHBORS
497
12.3.7
Exercises for Section 12.3
Exercise 12.3.1: Continue the iterations of Fig. 12.20 for three more itera-
tions.
Exercise 12.3.2: The following training set obeys the rule that the positive
examples all have vectors whose components sum to 10 or more, while the sum
is less than 10 for the negative examples.
([3, 4, 5], +1)
([2, 7, 2], +1)
([5, 5, 5], +1)
([1, 2, 3], −1)
([3, 3, 2], −1)
([2, 4, 1], −1)
(a) Which of these six vectors are the support vectors?
! (b) Suggest a vector w and constant b such that the hyperplane deﬁned by
w.x + b = 0 is a good separator for the positive and negative examples.
Make sure that the scale of w is such that all points are outside the margin;
that is, for each training example (x, y), you have y(w.x + b) ≥+1.
! (c) Starting with your answer to part (b), use gradient descent to ﬁnd the
optimum w and b. Note that if you start with a separating hyperplane,
and you scale w properly, then the second term of Equation 12.4 will
always be 0, which simpliﬁes your work considerably.
! Exercise 12.3.3: The following training set obeys the rule that the positive
examples all have vectors whose components have an odd sum, while the sum
is even for the negative examples.
([1, 2], +1)
([3, 4], +1)
([5, 2], +1)
([2, 4], −1)
([3, 1], −1)
([7, 3], −1)
(a) Suggest a starting vector w and constant b that classiﬁes at least three of
the points correctly.
!! (b) Starting with your answer to (a), use gradient descent to ﬁnd the optimum
w and b.
12.4
Learning from Nearest Neighbors
In this section we consider several examples of “learning” where the entire
training set is stored, perhaps preprocessed in some useful way, and then used
to classify future examples or to compute the value of the label that is most
likely associated with the example. The feature vector of each training example
is treated as a data point in some space. When a new point arrives and must
be classiﬁed, we ﬁnd the training example or examples that are closest to the
new point, according to the distance measure for that space. The estimated
label is then computed by combining the closest examples in some way.
