Comment

Trevor Hastie, Ji Zhu

Description

Statistical Science2006, Vol. 21, No. 3, 352–357DOI: 10.1214/088342306000000466Main article DOI: 10.1214/088342306000000493© Institute of Mathematical Statistics, 2006CommentTrevorHastieandJiZhuWe congratulate the authors for a well written and reproducing kernel Hilbert space H (RKHS) gener-Kthoughtful survey of some of the literature in this area. ated by K(·,·) (see Burges, 1998; Evgeniou, Pontil andThey are mainly concerned with the geometry and the Poggio, 2000; and Wahba, 1999, for details).computational learning aspects of the support vector Suppose the positive definite kernel K(·,·) has amachine (SVM). We will therefore complement their (possibly finite) eigenexpansion,review by discussing from the statistical function esti-∞ mation perspective. In particular, we will elaborate on K(x,x ) = δ φ (x)φ (x ),j j jthe following points: j=1where δ ≥ δ ≥ ··· ≥ 0 are the eigenvalues and• Kernel regularization is essentially a generalized 1 2ridge penalty in a certain feature space. φ (x)’s are the corresponding eigenfunctions. Ele-j• In practice, the effective dimension of the data ker- ments of H have an expansion in terms of theseKnel matrix is not always equal to n, even when the eigenfunctionsimplicit dimension of the feature space is infinite;∞hence, the training data are not always perfectly sep- (2) f(x) = β φ (x),j jarable. j=1• Appropriate regularization plays an important role inwith the constraint thatthe success of the SVM ...

Informations

• Publié par: Erni
• Nombre de lectures: 24
• Langue: English

Extrait

Statistical Science 2006, Vol. 21, No. 3, 352–357 DOI:10.1214/088342306000000466 Main article DOI:10.1214/088342306000000493 ©Institute of Mathematical Statistics, 2006 Comment Trevor Hastie and Ji Zhu

We congratulate the authors for a well written andreproducing kernel Hilbert spaceH K (RKHS) gener thoughtful survey of some of the literature in this area. ated byK(∙,∙)(see Burges,1998; Evgeniou, Pontil and They are mainly concerned with the geometry and the Poggio,2000; and Wahba,1999, for details). computational learning aspects of the support vector Suppose the positive definite kernelK(∙,∙)has a machine (SVM). We will therefore complement their (possibly finite) eigenexpansion, review by discussing from the statistical function esti ∞    mation perspective. In particular, we will elaborate on K(x,x)=δ j φ j (x)φ j (x), the following points: j=1 • where Kernel regularization is essentially a generalized δ 1 ≥δ 2 ≥ ∙∙ ∙≥0 are the eigenvalues and ridge penalty in a certain feature space. φ j (x)’s are the corresponding eigenfunctions. Ele • ments of In practice, the effective dimension of the data ker H K have an expansion in terms of these nel matrix is not always equal ton eigenfunctions , even when the implicit dimension of the feature space is infinite; ∞  hence, the training data are not always perfectly sep (2)f (x)=β j φ j (x), arable. j=1 •Appropriate regularization plays an important role in with the constraint that the success of the SVM. ∞  •The SVM is not fundamentally different from many 2 2 def ∞, f =β j /δ j < H K statistical tools that our statisticians are familiar j=1 with, for example, penalized logistic regression. wheref H is the norm induced byK(∙,∙). K We acknowledge that many of the comments are based Then we can rewrite (1) as on our earlier paper Hastie, Rosset, Tibshirani and   n∞ ∞ 2   β Zhu (2004). j (3) min y i , β 0 +β j φ j (x i )+λ , β 0 ,β δ j i=1j=1j=1 KERNEL REGULARIZATION AND THE 2 GENERALIZED RIDGE PENALTY and we can see that the regularization termfin H K (1) can be interpreted as a generalized ridge penalty,   Given a positive definite kernelK(x,x), wherex,x where eigenfunctions with small eigenvalues in the ex belong to a certain domainX, we consider the general pansion (2) get penalized more and vice versa. function estimation problem Formulation (3) seems to be an infinite dimensional n    λ optimization problem, but according to the representer 2 1)x) ( min y i , β 0 +f (x i )+ f ( H K . theorem (Kimeldorf and Wahba,1971; Wahba1990), β ,f 0 2 i=1 the solution is finite dimensional and has the form Here(∙,∙)is a convex loss function that describes the n  “closeness” between the observed data and the fitted f (x)=α i K(x,x i ).  model, andfis an element in the span of{K(∙,x), i=1  x∈X}. More precisely,f∈H K is a function in the Using the reproducing property ofH K , that is, K(∙,x i ), K(∙,x i ) =K(x i ,x i ), (3) also reduces to a   Trevor Hastie is Professor, Department of Statistics, finitedimensional criterion, Stanford University, Stanford, California 94305, USA T (4) minL(y, β 0 +Kα)+λαKα. (e-mail:[e-mail]). Ji Zhu is Assistant β 0 ,α Professor, Department of Statistics, University of Michigan, Ann Arbor, Michigan 48109, USA (e-mail: Here we use vector notation,Kis then×ndata ker  [e-mail]). nel matrix with elements equal toK(x i ,x i ), i, i=  352

COMMENT 353  n 1, . . . , n, andL(y, β 0 +Kα)=(y i , β 0 +f (x i )). i=1 We reparametrize (4) using the eigendecomposition of T K=UDU, whereDis diagonal andUis orthogonal. T LetKα=Uβ, whereβ=DUα. Then (4) becomes T−1 (5) minL(y, β 0 +Uβ)+λβDβ. β 0 ,β Now the columns ofUare unitnorm basis functions that span the column space ofK; and again, we see that those members that correspond to small eigenval ues (the elements of the diagonal matrixD) get heavily penalized and vice versa. In the machine learning community, people tend to view the kernel as providing an implicit map ofx fromXto a certain highdimensional feature space, andK(∙,∙)computes inner products in this (possibly infinitedimensional) feature space. Specifically, the features are    I T F G . 1.Eigenvalues(on the log scale)of the data kernel ma- h j (x)=δ j φ j (x)orh(x)=h 1 (x), h 2 (x), . . ., trixK. and we have EFFECTIVE DIMENSION OF THE DATA   K(x,x)= h(x),h(x).  KERNEL MATRIX 1/2 Furthermore, letθ j =β j / δ j andH=UD. Then (3) and (5 As we have seen in the previous section, the kernel ) become   n∞ ∞ K(∙,∙)mapsxfrom its original input space to some   2 ( highdimensionalfeature spaceh(x). In the case of 6) min y i , θ j h j (x)+λ θ j β ,θ 0 i=1j=1j=1 classification, it is sometimes argued that the implicit feature space can be infinitedimensional (e.g., via the and radial basis kernel), which suggests that perfect sepa T (7) minL(y, β 0 +Hθ)+λθ θ, ration of the training data is always possible. However, β 0 ,θ this is not always true in practice. respectively. This shows kernel regularization as an ex To illustrate the point, we consider a twoclass classi act ridge penalty in the feature space, but unlike (3) fication example. The data were generated from a pair and (5), it hides the fact that eigenfunctions are dif of mixture Gaussian densities, described in detail by ferentially penalized according to their corresponding Hastie, Tibshirani and Friedman (2001). The radial ker eigenvalues.  2 nel functionK(x,x )=exp(−γx−x)was used. To illustrate the point, we consider a simple example. Four different values ofγ(0.1,0.5,1 and 5) were tried. The datax i ’s are onedimensional and were generated For each of the values ofγ, the SVM was fitted for a from the standard Gaussian distribution (n=50). The  2 sequence of values ofλ, ranging from the most regu radial kernel function)K(x, x=exp(−γx−x) larized model to the least regularized model. was used, withγ=1. Figure1shows the eigenval We were at first surprised to discover that not all ues of the kernel matrixK. The left panel of Figure2 these sequences achieved zero training errors on the shows the first 16 eigenvectors ofK(columns ofU) and the right panel shows the corresponding features 200 training data points, at their least regularized fit. (columns ofH The minimal training errors and the corresponding val ). As we can see from the left panel of Figure2 ues for , eigenvectors with large eigenvalues (hence γare summarized in Table1. The second row get penalized less) tend to be smooth, while eigenvec of the table shows the effective rank of the data kernel tors with small eigenvalues (hence get penalized more) matrixK(which we defined to be the number of eigen 2 −12 tend to be wiggly; therefore,fis also always in values greater than 10). This 200×200 matrix has H K  terpreted as a roughness measure of the functionf. We elementsK(x i ,x i ), i, i=1, . . . ,200. In this example,  can also see from the right panel of Figure2that many a full rankKis required to achieve perfect separation. of the features are “norm challenged,” that is, they are Similar observations have also appeared in Williams squashed down dramatically by their eigenvalues.and Seeger (2000) and Bach and Jordan (2002).

354

T. HASTIE AND J. ZHU

F IG . 2.The left panel shows the eigenvectors of the data kernel matrixKand the right panel shows the corresponding features(eigenvectors scaled by the corresponding eigenvalues).

T ABLE 1 Results for the mixture simulation example

γ05 1.5 0.1 Training errors0 1221 33 Effective rank200 177 14376

This emphasizes again the fact that not all features in the feature map implied byK(∙,∙)are of equal stature (see the right panel in Figure2); many of them are

shrunken way down to zero. The regularization in (3) and (5) penalizes unitnorm eigenvectors by the in verse of their eigenvalues, which effectively annihi lates some, depending onγ. Smallγimplies wide, flat kernels and a suppression of wiggly, rough func tions. Figure3shows the eigenvalues ofKfor the four values ofγ. The larger eigenvalues correspond in this case to smoother eigenfunctions, the smaller ones to rougher. The rougher eigenfunctions get penalized ex ponentially more than the smoother ones. Hence, for smaller values ofγ, the effective dimension of the fea ture space is truncated.

F IG . 3.The eigenvalues(on the log scale)for the data kernel matricesKthat correspond to the four values ofγ.

COMMENT 355 THE NEED FOR CAREFUL REGULARIZATION Figure4shows the test error as a function ofλfor the mixture data example. Here we see a dramatic range in The SVM has been very successful for the classifi the correct choice ofλ. Whenγ=5, the most regu cation problem and gained a lot of attention in the ma larized model is called for. On the other hand, when chine learning community in the past ten years. Many γ=0.1, we would want to choose among the least papers have been published to explain why it performs regularized models. Depending on the value ofγ, the so well. Most of this literature concentrates on the con cept of margin. Various misclassification error bounds optimalλcan occur at either end of the spectrum or have been derived based on the margin (Vapnik,1995 in between, emphasizing the need for care; anywhere Bartlett and ShaweTaylor,1999 ful selection. ; ShaweTaylor and Cristianini,1999). However, our view is a little different from that based CONNECTION WITH OTHER STATISTICAL TOOLS on the concept of margin. Several researchers have noted the relationship between the SVM and regular Last, we would like to comment on the connection ized function estimation in RKHS (Evgeniou, Pon between the SVM and some statistical tools that statis til and Poggio,2000; Wahba,1999). The regularized ticians are familiar with. function estimation problem contains two parts: a loss As we have seen in previous sections, what is spe function and a penalty term [e.g., (1)]. The SVM uses cial with the SVM is not the regularization term, but the socalled hinge loss function (see Figure5). The is rather the loss function, that is, the hinge loss. Lin margin maximizing property of the SVM derives from (2002) pointed out that the hinge loss is Bayes con the hinge loss function. Hence margin maximization sistent, that is, the population minimizer of the loss is by nature a nonregularized objective, and solving function agrees with the Bayes rule in terms of clas it in highdimensional space is likely to lead to over sification. This is important in explaining the success fitting and bad prediction performance. This has been of the SVM, because it implies that the SVM is trying observed in practice by many researchers, in particular to implement the Bayes rule. Breiman (1999) and Marron and Todd (2002). On the other hand, notice that the hinge loss and the Theloss+penaltyformulation emphasizes the role binomial deviance have very similar shapes (see Fig of regularization. In many situations we have sufficient ure5): both increase linearly asyfgets very small features (e.g., gene expression arrays) to guarantee sep (negative), and both encourageyandfto have the aration. We may nevertheless avoid the maximum mar gin separator (λ↓0) in favor of a more regularized so same sign. Hence it is reasonable to conjecture that by lution. replacingthe hinge loss of the SVM with the binomial

F IG . 4.Test error curves for the mixture example,using four different values for the radial kernel parameterγ.Large values ofλcorrespond to heavy regularization,small values ofλto light regularization.Depending on the value ofγ,the optimalλcan occur at either end of the spectrum or anywhere in between,emphasizing the need for careful selection.

356

T. HASTIE AND J. ZHU

F IG . 5.Comparing the hinge loss and the binomial deviance,y∈ {−1,1}.

deviance, which is also Bayes consistent, we should be able to get a fitted model that performs similarly to the SVM. In fact, in Zhu and Hastie (2005), we show that under certain conditions, the classification bound ary of the resulting penalized logistic regression (using the binomial deviance) and that of the SVM coincide. Penalized logistic regression has been studied by many statisticians (see Green and Silverman,1994; Wahba, Gu, Wang and Chappell,1995; and Lin et al.,2000, for details). We understand why it can work well. The same reasoning could be applied to the SVM. Penalized logistic regression is not the only model that performs similarly to the SVM; replacing the hinge loss with any sensible loss function will give a sim ilar result, for example, the exponential loss func tion of boosting (Freund and Schapire,1997) and the squared error loss (Zhang and Oles,2001; Bühlmann and Yu,2003). These loss functions are all Bayes con sistent. The binomial deviance and the exponential loss are marginmaximizing loss functions, but the squared error loss is not. The distance weighted discrimination (Marron and Todd,2002) is designed specifically for notmaximizing the margin and works well with high dimensional data, which in a way also justifies that margin maximization is not the key to the success of the SVM.

ACKNOWLEDGMENTS Hastie is partially supported by NSF Grant DMS05 05676. Zhu is partially supported by NSF Grant DMS 0505432.

REFERENCES B ACH , F. and J ORDAN , M. (2002). Kernel independent component analysis.J. Mach. Learn. Res.31–48.MR1966051 B ARTLETT , P. and S HAWE T AYLOR , J. (1999). Generalization performance of support vector machines and other pattern clas sifiers. InAdvances in Kernel Methods—Support Vector Learn- ing(B. Schölkopf, C. J. C. Burges and A. J. Smola, eds.) 43–54. MIT Press, Cambridge, MA. B REIMAN , L. (1999). Prediction games and arcing algorithms. Neural Computation111493–1517. B ÜHLMANN , P. and Y U , B. (2003). Boosting with theLloss: 2 Regression and classification.J. Amer. Statist. Assoc.98324– 340.MR1995709 B URGES , C. J. C. (1998). A tutorial on support vector machines for pattern recognition.Data Min. Knowl. Discov.2121–167. E VGENIOU , T., P ONTIL , M. and P OGGIO , T. (2000). Regulariza tion networks and support vector machines.Adv. Comput. Math. 131–50.MR1759187 F REUND , Y. and S CHAPIRE , R. (1997). A decision theoretic gen eralization of online learning and an application to boosting. J. Comput. System Sci.55119–139.MR1473055 G REEN , P. and S ILVERMAN , B. (1994).Nonparametric Regres- sion and Generalized Linear Models:A Roughness Penalty Ap- proach. Chapman and Hall, London.MR1270012 H ASTIE , T., R OSSET , S., T IBSHIRANI , R. and Z HU , J. (2004). The entire regularization path for the support vector machine.J. Mach. Learn. Res.51391–1415.

COMMENT

H ASTIE , T., T IBSHIRANI , R. and F RIEDMAN , J. (2001).The Ele- ments of Statistical Learning. Springer, New York.MR1851606 K IMELDORF , G. and W AHBA , G. (1971). Some results on Tcheby cheffian spline functions.J. Math. Anal. Appl.3382–95. MR0290013 L IN , X., W AHBA , G., X IANG , D., G AO , F., K LEIN , R. and K LEIN , B. (2000). Smoothing spline ANOVA models for large data sets with Bernoulli observations and the randomized GACV.Ann. Statist.281570–1600.MR1835032 L IN , Y. (2002). Support vector machines and the Bayes rule in clas sification.Data Min. Knowl. Discov.6259–275.MR1917926 M ARRON , J. and T ODD , M. (2002). Distance weighted discrimi nation. Technical report, School Operations Res. and Industrial Engineering, Cornell Univ. S HAWE T AYLOR , J. and C RISTIANINI , N. (1999). Margin distri bution bounds on generalization. InComputational Learning Theory. Lecture Notes in Artificial Intelligence1572263–273. Springer, Berlin. V APNIK , V. (1995).The Nature of Statistical Learning Theory. Springer, New York.MR1367965 W AHBA , G. (1990).Spline Models for Observational Data. SIAM, Philadelphia.MR1045442

357

W AHBA , G. (1999). Support vector machines, reproducing ker nel Hilbert space and randomized GACV. InAdvances in Ker- nel Methods—Support Vector Learning(B. Schölkopf, C. J. C. Burges and A. J. Smola, eds.) 69–88. MIT Press, Cambridge, MA. W AHBA , G., G U , C., W ANG , Y. and C HAPPELL , R. (1995). Soft classification, a.k.a. risk estimation, via penalized log likelihood and smoothing spline analysis of variance. InThe Mathematics of Generalization(D. Wolpert, ed.) 329–360. Addison–Wesley, Reading, MA. W ILLIAMS , C. and S EEGER , M. (2000). The effect of the input density distribution on kernelbased classifiers. InProc. Seven- teenth International Conference on Machine Learning1159– 1166. Morgan Kaufmann, San Francisco. Z HANG , T. and O LES , F. (2001). Text categorization based on reg ularized linear classification methods.Information Retrieval4 5–31. Z HU , J. and H ASTIE , T. (2005). Kernel logistic regression and the import vector machine.J. Comput. Graph. Statist.14185–205. MR2137897