The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 11
Текст из файла (страница 11)
. . . . . . . . . . . . . . . . .. ..o.. o...........................o .... .... .... .... .... .... .... .... .... .... .... .... .... o.... .... .... .... .... ....o.... .... .... .... ....oo.... .... .... .... .... .... .... ....oo.. ....o.... o..... ..... ..... ..... ..... ..... .....
..... ..... ..... ..... ..... .....o..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. ..o.. .. o. . .. .. .. ... o.. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. o.. .. o.. .. .. .. .. .. .. .. .. ...
... o..o.. .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. o. .. .. .. .. .. .. .. .. o. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. o........o.. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. .. .... ..
.. .. .. .. ... o. . . .. .. .. .. .. ...o. . .o. .. ..o.. o. . . . . .. .. .. ..o. .. .. .. ... ... ... ... ... ... ... ...o. . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. ... ... ...o..o.. .. .. .. .. ... ... ... ... o.. ..o.. ... ... ... ... ...o.. ..
.. .. ...o.. .. .. .. .. .. .. o. .. .. .. .. .. .. ... . . . ... ... ... o. . . . . . .ooo. .. .. .. .. .. .. .. .. .. .. ..o.o. ..o.o. .. .. .. .. .. .. .. .. .. .. .. .. o. .. o. .. .. .. .. .. .. .. .. ... ... ... ...o. . . . . .o.. . . .. .. .. .. .. .. .. ... o.......oo.. .. .. .. .. .. .. .. .. .. .. .. .. ..
o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. ..o.. .. .. .. .. ..o.. .. .. o. .. .. .. .. .. .. ....o.. .. ... ... ... ... ... ... ... ... ... ... o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. o..o.. o.. o.. .. .. o.. .. ..o.. .. .. .. .. .. .. .. o..
.. .. .. .. .. ..o.. .. .. .. o.. .. .. .. .. .. .. .. ... ... ... ... ... ... ... .....o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. o.. .. .. .. .. .. .. .. .. .. .. .. .. ..oo...o... ... ... ... ... ... o... ... ... ... ... ... ... ... ... ... ... ... ...o... ... ... ... ... ...o...o... ... ...o... ...o.. .. .. .. .. ..o.. .. ..
..o.. .. .. .. .. .. ..o............... .. .. .. .. .. .. .. .. .. .. .. .. .. ..o. . .. .. .. .. .. .. .. .. .. .. .. .. .. o.. .. o. . . . . . .. .. .. .. .. .. .. .. .. .. .. ... ...o... ... ... ... ... ... ... ... ... ... ..... .. .. ..
.. .. .. .. .. .. .. .. .. .. .. ... ...o... ... ... ... ... ... ... o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. o.. o.. .. o.. .. ... ... o... ... ... ... ... ... ... o.. .. .. .. .. .. ..o... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...o............o................o.. .. .. .. .. .. ..o.. .. ..
.. o.. .. o. . . . . . .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. o. . . .oo.. o....oo.... .... .... .... .... .... .... o. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. ..
.. .. .. .. .. o.. .. .. .. .. ... ... ... ... ... o... ... ... ... ... ... ... ... ... ... ... o... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. o. .. ... ... ... ... o. .o..o.. .. .. ..o.. .. .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... ...
... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. .. o.. o..o.. ..o.. .. ... ... ... ... ... o. . . . . .. .. .. .. .. .. .. .. .. ..o................o..o.. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...o... ... ... ... o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .... .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ... ...o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. o.. .. .. o.. o... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o. . . .o. . . o. . . . .. .. .. .. o. . . . . . . .o.................... .. .. .. .. .. .. .. .. .. .. .. o. . . . . .o. . . .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. .. .. ..o.. .. .. .. .. .. o..o.. .. .. .. .. o.. .. .. ..oo .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... o.. o.. o.. .. .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ... ... ... ... o.. .. .. .. ..o....................... ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. o. . . .o. .o. . . .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. ..o.. .. ... ... ... ... ... ... ... ... ... o. . . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ... ... o. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ...oo.. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... o.................. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... ... ...
... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ................................................................oFIGURE 2.5. The optimal Bayes decision boundary for the simulation exampleof Figures 2.1, 2.2 and 2.3. Since the generating density is known for each class,this boundary can be calculated exactly (Exercise 2.2).and again it suffices to minimize EPE pointwise:Ĝ(x) = argming∈GKXk=1L(Gk , g)Pr(Gk |X = x).(2.21)With the 0–1 loss function this simplifies toĜ(x) = argming∈G [1 − Pr(g|X = x)](2.22)Ĝ(x) = Gk if Pr(Gk |X = x) = max Pr(g|X = x).(2.23)or simplyg∈GThis reasonable solution is known as the Bayes classifier, and says thatwe classify to the most probable class, using the conditional (discrete) distribution Pr(G|X).
Figure 2.5 shows the Bayes-optimal decision boundaryfor our simulation example. The error rate of the Bayes classifier is calledthe Bayes rate.222. Overview of Supervised LearningAgain we see that the k-nearest neighbor classifier directly approximatesthis solution—a majority vote in a nearest neighborhood amounts to exactly this, except that conditional probability at a point is relaxed to conditional probability within a neighborhood of a point, and probabilities areestimated by training-sample proportions.Suppose for a two-class problem we had taken the dummy-variable approach and coded G via a binary Y , followed by squared error loss estimation.
Then fˆ(X) = E(Y |X) = Pr(G = G1 |X) if G1 corresponded to Y = 1.Likewise for a K-class problem, E(Yk |X) = Pr(G = Gk |X). This showsthat our dummy-variable regression procedure, followed by classification tothe largest fitted value, is another way of representing the Bayes classifier.Although this theory is exact, in practice problems can occur, dependingon the regression model used. For example, when linear regression is used,fˆ(X) need not be positive, and we might be suspicious about using it asan estimate of a probability. We will discuss a variety of approaches tomodeling Pr(G|X) in Chapter 4.2.5 Local Methods in High DimensionsWe have examined two learning techniques for prediction so far: the stablebut biased linear model and the less stable but apparently less biased classof k-nearest-neighbor estimates.
It would seem that with a reasonably largeset of training data, we could always approximate the theoretically optimalconditional expectation by k-nearest-neighbor averaging, since we shouldbe able to find a fairly large neighborhood of observations close to any xand average them. This approach and our intuition breaks down in highdimensions, and the phenomenon is commonly referred to as the curseof dimensionality (Bellman, 1961). There are many manifestations of thisproblem, and we will examine a few here.Consider the nearest-neighbor procedure for inputs uniformly distributedin a p-dimensional unit hypercube, as in Figure 2.6.
Suppose we send out ahypercubical neighborhood about a target point to capture a fraction r ofthe observations. Since this corresponds to a fraction r of the unit volume,the expected edge length will be ep (r) = r1/p . In ten dimensions e10 (0.01) =0.63 and e10 (0.1) = 0.80, while the entire range for each input is only 1.0.So to capture 1% or 10% of the data to form a local average, we must cover63% or 80% of the range of each input variable. Such neighborhoods are nolonger “local.” Reducing r dramatically does not help much either, sincethe fewer observations we average, the higher is the variance of our fit.Another consequence of the sparse sampling in high dimensions is thatall sample points are close to an edge of the sample. Consider N data pointsuniformly distributed in a p-dimensional unit ball centered at the origin.Suppose we consider a nearest-neighbor estimate at the origin.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
