502
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
12.4.4
Kernel Regression
A way to construct a continuous function that represents the data of a training
set well is to consider all points in the training set, but weight the points
using a kernel function that decays with distance. A popular choice is to use
a normal distribution (or “bell curve”), so the weight of a training point x
when the query is q is e−(x−q)2/σ2. Here σ is the standard deviation of the
distribution (a parameter you select) and the query q is the mean. Roughly,
points within distance σ of q are heavily weighted, and those further away have
little weight. There is an advantage to using a kernel function, such as the
normal distribution, that is continuous and deﬁned for all points in the training
set; doing so assures that the resulting function learned from the data is itself
continuous. (See Exercise 12.4.6 for a discussion of the problem when a simpler
weighting is used.)
Example 12.13 : Let us use the seven training examples of Example 12.12.
To make calculation simpler, we shall not use the normal distribution as the
kernel function, but rather another continuous function of distance, namely
w = 1/(x −q)2. That is, weights decay as the square of the distance. Suppose
the query q is 3.5. The weights w1, w2, . . . w7 of the seven training examples
(xi, yi) = (i, 8/2|i−4|) for i = 1, 2, . . . , 7 are shown in Fig. 12.24.
(1)
xi
1
2
3
4
5
6
7
(2)
yi
1
2
4
8
4
2
1
(3)
wi
4/25
4/9
4
4
4/9
4/25
4/49
(4)
wiyi
4/25
8/9
16
32
16/9
8/25
4/49
Figure 12.24: Weights of points when the query is q = 3.5
Lines (1) and (2) of Fig. 12.24 give the seven training points. The weight
of each when the query is q = 3.5 is given in line (3). For instance, for x1 = 1,
the weight w1 = 1/(1 −3.5)2 = 1/(−2.5)2 = 4/25. Then, line (4) shows each yi
weighted by the weight from line (3). For instance, the column for x2 has value
8/9 because w2y2 = 2 × (4/9).
To compute the label for the query q = 3.5 we sum the weighted values
of the labels in the training set, as given by line (4) of Fig. 12.24; this sum is
51.23. We then divide by the sum of the weights in line (3). This sum is 9.29,
so the ratio is 51.23/9.29 = 5.51. That estimate of the value of the label for
q = 3.5 seems intuitively reasonable, since q lies midway between two points
with labels 4 and 8.
✷
12.4.5
Dealing with High-Dimensional Euclidean Data
We saw in Section 12.4.2 that the two-dimensional case of Euclidean data is
fairly easy. There are several large-scale data structures that have been devel-
