The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 95
Текст из файла (страница 95)
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 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.. .. .. .. .. ..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....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... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...o.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..oC = 0.01FIGURE 12.2. The linear support vector boundary for the mixture data example with two overlapping classes, for two different values of C. The broken linesindicate the margins, where f (x) = ±1. The support points (αi > 0) are all thepoints on the wrong side of their margin. The black solid dots are those supportpoints falling exactly on the margin (ξi = 0, αi > 0). In the upper panel 62% ofthe observations are support points, while in the lower panel 85% are.
The brokenpurple curve in the background is the Bayes decision boundary.12.3 Support Vector Machines and Kernels42312.3 Support Vector Machines and KernelsThe support vector classifier described so far finds linear boundaries in theinput feature space. As with other linear methods, we can make the procedure more flexible by enlarging the feature space using basis expansionssuch as polynomials or splines (Chapter 5). Generally linear boundariesin the enlarged space achieve better training-class separation, and translate to nonlinear boundaries in the original space. Once the basis functionshm (x), m = 1, . .
. , M are selected, the procedure is the same as before. Wefit the SV classifier using input features h(xi ) = (h1 (xi ), h2 (xi ), . . . , hM (xi )),i = 1, . . . , N , and produce the (nonlinear) function fˆ(x) = h(x)T β̂ + βˆ0 .The classifier is Ĝ(x) = sign(fˆ(x)) as before.The support vector machine classifier is an extension of this idea, wherethe dimension of the enlarged space is allowed to get very large, infinitein some cases. It might seem that the computations would become prohibitive. It would also seem that with sufficient basis functions, the datawould be separable, and overfitting would occur. We first show how theSVM technology deals with these issues.
We then see that in fact the SVMclassifier is solving a function-fitting problem using a particular criterionand form of regularization, and is part of a much bigger class of problemsthat includes the smoothing splines of Chapter 5. The reader may wishto consult Section 5.8, which provides background material and overlapssomewhat with the next two sections.12.3.1 Computing the SVM for ClassificationWe can represent the optimization problem (12.9) and its solution in aspecial way that only involves the input features via inner products. We dothis directly for the transformed feature vectors h(xi ). We then see that forparticular choices of h, these inner products can be computed very cheaply.The Lagrange dual function (12.13) has the formLD =NXi=1Nαi −N1XXαi αi′ yi yi′ hh(xi ), h(xi′ )i.2 i=1 ′(12.19)i =1From (12.10) we see that the solution function f (x) can be writtenf (x)==h(x)T β + β0NXi=1αi yi hh(x), h(xi )i + β0 .(12.20)As before, given αi , β0 can be determined by solving yi f (xi ) = 1 in (12.20)for any (or all) xi for which 0 < αi < C.42412.
Flexible DiscriminantsSo both (12.19) and (12.20) involve h(x) only through inner products. Infact, we need not specify the transformation h(x) at all, but require onlyknowledge of the kernel functionK(x, x′ ) = hh(x), h(x′ )i(12.21)that computes inner products in the transformed space. K should be asymmetric positive (semi-) definite function; see Section 5.8.1.Three popular choices for K in the SVM literature aredth-Degree polynomial: K(x, x′ ) = (1 + hx, x′ i)d ,Radial basis: K(x, x′ ) = exp(−γkx − x′ k2 ),Neural network: K(x, x′ ) = tanh(κ1 hx, x′ i + κ2 ).(12.22)Consider for example a feature space with two inputs X1 and X2 , and apolynomial kernel of degree 2.
ThenK(X, X ′ ) = (1 + hX, X ′ i)2= (1 + X1 X1′ + X2 X2′ )2= 1 + 2X1 X1′ + 2X2 X2′ + (X1 X1′ )2 + (X2 X2′ )2 + 2X1 X1′ X2 X2′ .(12.23)√if we choose h1 (X) = 1, √h2 (X) = 2X1 , h3 (X) =√ Then M = 6, and2X2 , h4 (X) = X12 , h5 (X) = X22 , and h6 (X) = 2X1 X2 , then K(X, X ′ ) =hh(X), h(X ′ )i. From (12.20) we see that the solution can be writtenfˆ(x) =NXα̂i yi K(x, xi ) + β̂0 .(12.24)i=1The role of the parameter C is clearer in an enlarged feature space,since perfect separation is often achievable there. A large value of C willdiscourage any positive ξi , and lead to an overfit wiggly boundary in theoriginal feature space; a small value of C will encourage a small value ofkβk, which in turn causes f (x) and hence the boundary to be smoother.Figure 12.3 show two nonlinear support vector machines applied to themixture example of Chapter 2.
The regularization parameter was chosenin both cases to achieve good test error. The radial basis kernel producesa boundary quite similar to the Bayes optimal boundary for this example;compare Figure 2.5.In the early literature on support vectors, there were claims that thekernel property of the support vector machine is unique to it and allowsone to finesse the curse of dimensionality. Neither of these claims is true,and we go into both of these issues in the next three subsections.12.3 Support Vector Machines and Kernels425SVM - Degree-4 Polynomial in Feature Space..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .. .. .. .. .. .. .. ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
