12.4. LEARNING FROM NEAREST NEIGHBORS
503
Problems in the Limit for Example 12.13
Suppose q is exactly equal to one of the training examples x. If we use
the normal distribution as the kernel function, there is no problem with
the weight of x; it is 1. However, with the kernel function discussed in
Example 12.13, the weight of x is 1/(x−q)2 = ∞. Fortunately, this weight
appears in both the numerator and denominator of the expression that
estimates the label of q. It can be shown that in the limit as q approaches
x, the label of x dominates all the other terms in both numerator and
denominator, so the estimated label of q is the same as the label of x.
That makes excellent sense, since q = x in the limit.
oped for ﬁnding near neighbors when the number of dimensions grows, and the
training set is large. We shall not cover these structures here, because the sub-
ject could ﬁll a book by itself, and there are many places available to learn about
these techniques, collectively called multidimensional index structures. See the
bibliographic notes for this chapter for information about such structures as
kd-Trees, R-Trees, and Quad Trees.
Unfortunately, for high-dimensional data, there is little that can be done to
avoid searching a large portion of the data. This fact is another manifestation
of the “curse of dimensionality” from Section 7.1.3. Two ways to deal with the
“curse” are the following:
1. VA Files. Since we must look at a large fraction of the data anyway in
order to ﬁnd the nearest neighbors of a query point, we could avoid a
complex data structure altogether. Accept that we must scan the entire
ﬁle, but do so in a two-stage manner. First, a summary of the ﬁle is
created, using only a small number of bits that approximate the values of
each component of each training vector. For example, if we use only the
high-order (1/4)th of the bits in numerical components, then we can create
a ﬁle that is (1/4)th the size of the full dataset. However, by scanning
this ﬁle we can construct a list of candidates that might be among the k
nearest neighbors of the query q, and this list may be a small fraction of
the entire dataset. We then look up only these candidates in the complete
ﬁle, in order to determine which k are nearest to q.
2. Dimensionality Reduction. We may treat the vectors of the training set
as a matrix, where the rows are the vectors of the training example, and
the columns correspond to the components of these vectors. Apply one of
the dimensionality-reduction techniques of Chapter 11, to compress the
vectors to a small number of dimensions, small enough that the techniques
for multidimensional indexing can be used. Of course, when processing
a query vector q, the same transformation must be applied to q before
