The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 24
Текст из файла (страница 24)
. . , M,(3.73)where cm is the mth canonical correlation coefficient. Note that as the ratioof the number of input variables to sample size p/N gets small, the shrinkage factors approach 1. Breiman and Friedman (1997) proposed modifiedversions of Λ based on training data and cross-validation, but the generalform is the same. Here the fitted response has the formŶc+w = HYSc+w ,(3.74)863. Linear Methods for Regressionwhere Sc+w = UΛU−1 is the response shrinkage operator.Breiman and Friedman (1997) also suggested shrinking in both the Yspace and X space.
This leads to hybrid shrinkage models of the formŶridge,c+w = Aλ YSc+w ,(3.75)where Aλ = X(XT X + λI)−1 XT is the ridge regression shrinkage operator,as in (3.46) on page 66. Their paper and the discussions thereof containmany more details.3.8 More on the Lasso and Related PathAlgorithmsSince the publication of the LAR algorithm (Efron et al., 2004) there hasbeen a lot of activity in developing algorithms for fitting regularizationpaths for a variety of different problems.
In addition, L1 regularization hastaken on a life of its own, leading to the development of the field compressedsensing in the signal-processing literature. (Donoho, 2006a; Candes, 2006).In this section we discuss some related proposals and other path algorithms,starting off with a precursor to the LAR algorithm.3.8.1 Incremental Forward Stagewise RegressionHere we present another LAR-like algorithm, this time focused on forwardstagewise regression. Interestingly, efforts to understand a flexible nonlinearregression procedure (boosting) led to a new algorithm for linear models(LAR). In reading the first edition of this book and the forward stagewiseAlgorithm 3.4 Incremental Forward Stagewise Regression—FSǫ .1. Start with the residual r equal to y and β1 , β2 , . .
. , βp = 0. All thepredictors are standardized to have mean zero and unit norm.2. Find the predictor xj most correlated with r3. Update βj ← βj + δj , where δj = ǫ · sign[hxj , ri] and ǫ > 0 is a smallstep size, and set r ← r − δj xj .4. Repeat steps 2 and 3 many times, until the residuals are uncorrelatedwith all the predictors.Algorithm 16.1 of Chapter 164 , our colleague Brad Efron realized that with4 Inthe first edition, this was Algorithm 10.4 in Chapter 10.3.8 More on the Lasso and Related Path AlgorithmsFSǫFS00.0gleason0.4svilweightpgg45lbph0.2Coefficients0.2svilweightpgg45lbph0.00.40.6lcavol0.6lcavolCoefficients87gleasonage−0.2−0.2agelcp050100150Iteration200lcp0.00.51.01.52.0L1 Arc-length of CoefficientsFIGURE 3.19.
Coefficient profiles for the prostate data. The left panel showsincremental forward stagewise regression with step size ǫ = 0.01. The right panelshows the infinitesimal version FS0 obtained letting ǫ → 0. This profile was fit bythe modification 3.2b to the LAR Algorithm 3.2. In this example the FS0 profilesare monotone, and hence identical to those of lasso and LAR.linear models, one could explicitly construct the piecewise-linear lasso pathsof Figure 3.10.
This led him to propose the LAR procedure of Section 3.4.4,as well as the incremental version of forward-stagewise regression presentedhere.Consider the linear-regression version of the forward-stagewise boostingalgorithm 16.1 proposed in Section 16.1 (page 608). It generates a coefficientprofile by repeatedly updating (by a small amount ǫ) the coefficient of thevariable most correlated with the current residuals. Algorithm 3.4 givesthe details. Figure 3.19 (left panel) shows the progress of the algorithm onthe prostate data with step size ǫ = 0.01. If δj = hxj , ri (the least-squarescoefficient of the residual on jth predictor), then this is exactly the usualforward stagewise procedure (FS) outlined in Section 3.3.3.Here we are mainly interested in small values of ǫ. Letting ǫ → 0 givesthe right panel of Figure 3.19, which in this case is identical to the lassopath in Figure 3.10.
We call this limiting procedure infinitesimal forwardstagewise regression or FS0 . This procedure plays an important role innon-linear, adaptive methods like boosting (Chapters 10 and 16) and is theversion of incremental forward stagewise regression that is most amenableto theoretical analysis. Bühlmann and Hothorn (2007) refer to the sameprocedure as “L2boost”, because of its connections to boosting.883.
Linear Methods for RegressionEfron originally thought that the LAR Algorithm 3.2 was an implementation of FS0 , allowing each tied predictor a chance to update their coefficients in a balanced way, while remaining tied in correlation. However, hethen realized that the LAR least-squares fit amongst the tied predictorscan result in coefficients moving in the opposite direction to their correlation, which cannot happen in Algorithm 3.4. The following modification ofthe LAR algorithm implements FS0 :Algorithm 3.2b Least Angle Regression: FS0 Modification.4.
Find the new direction by solving the constrained least squares problemmin ||r − XA b||22 subject to bj sj ≥ 0, j ∈ A,bwhere sj is the sign of hxj , ri.The modification amounts to a non-negative least squares fit, keeping thesigns of the coefficients the same as those of the correlations. One can showthat this achieves the optimal balancing of infinitesimal “update turns”for the variables tied for maximal correlation (Hastie et al., 2007). Likelasso, the entire FS0 path can be computed very efficiently via the LARalgorithm.As a consequence of these results, if the LAR profiles are monotone nonincreasing or non-decreasing, as they are in Figure 3.19, then all threemethods—LAR, lasso, and FS0 —give identical profiles.
If the profiles arenot monotone but do not cross the zero axis, then LAR and lasso areidentical.Since FS0 is different from the lasso, it is natural to ask if it optimizesa criterion. The answer is more complex than for lasso; the FS0 coefficientprofile is the solution to a differential equation. While the lasso makes optimal progress in terms of reducing the residual sum-of-squares per unitincrease in L1 -norm of the coefficient vector β, FS0 is optimal per unitincrease in L1 arc-length traveled along the coefficient path. Hence its coefficient path is discouraged from changing directions too often.FS0 is more constrained than lasso, and in fact can be viewed as a monotone version of the lasso; see Figure 16.3 on page 614 for a dramatic example.
FS0 may be useful in p ≫ N situations, where its coefficient profilesare much smoother and hence have less variance than those of lasso. Moredetails on FS0 are given in Section 16.2.3 and Hastie et al. (2007). Figure 3.16 includes FS0 where its performance is very similar to that of thelasso.3.8 More on the Lasso and Related Path Algorithms893.8.2 Piecewise-Linear Path AlgorithmsThe least angle regression procedure exploits the piecewise linear nature ofthe lasso solution paths.
It has led to similar “path algorithms” for otherregularized problems. Suppose we solveβ̂(λ) = argminβ [R(β) + λJ(β)] ,withR(β) =NXL(yi , β0 +i=1pXxij βj ),(3.76)(3.77)j=1where both the loss function L and the penalty function J are convex.Then the following are sufficient conditions for the solution path β̂(λ) tobe piecewise linear (Rosset and Zhu, 2007):1. R is quadratic or piecewise-quadratic as a function of β, and2. J is piecewise linear in β.This also implies (in principle) that the solution path can be efficientlycomputed. Examples include squared- and absolute-error loss, “Huberized”losses, and the L1 , L∞ penalties on β. Another example is the “hinge loss”function used in the support vector machine.
There the loss is piecewiselinear, and the penalty is quadratic. Interestingly, this leads to a piecewiselinear path algorithm in the dual space; more details are given in Section 12.3.5.3.8.3 The Dantzig SelectorCandes and Tao (2007) proposed the following criterion:minβ ||β||1 subject to ||XT (y − Xβ)||∞ ≤ s.(3.78)They call the solution the Dantzig selector (DS). It can be written equivalently asminβ ||XT (y − Xβ)||∞ subject to ||β||1 ≤ t.(3.79)Here || · ||∞ denotes the L∞ norm, the maximum absolute value of thecomponents of the vector. In this form it resembles the lasso, replacingsquared error loss by the maximum absolute value of its gradient. Notethat as t gets large, both procedures yield the least squares solution ifN < p. If p ≥ N , they both yield the least squares solution with minimumL1 norm.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
