The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 74
Текст из файла (страница 74)
The EM algorithm, however, can take a long time to converge,and so sizable HME models are considered costly to fit.Bibliographic NotesThe most comprehensive source for generalized additive models is the textof that name by Hastie and Tibshirani (1990). Different applications ofthis work in medical problems are discussed in Hastie et al. (1989) andHastie and Herman (1990), and the software implementation in Splus isdescribed in Chambers and Hastie (1991). Green and Silverman (1994)discuss penalization and spline models in a variety of settings. Efron andTibshirani (1991) give an exposition of modern developments in statistics(including generalized additive models), for a nonmathematical audience.Classification and regression trees date back at least as far as Morgan andSonquist (1963). We have followed the modern approaches of Breiman etal.
(1984) and Quinlan (1993). The PRIM method is due to Friedmanand Fisher (1999), while MARS is introduced in Friedman (1991), with anadditive precursor in Friedman and Silverman (1989). Hierarchical mixturesof experts were proposed in Jordan and Jacobs (1994); see also Jacobs etal. (1991).Exercises335ExercisesEx.
9.1 Show that a smoothing spline fit of yi to xi preserves the linearpart of the fit. In other words, if yi = ŷi + ri , where ŷi represents thelinear regression fits, and S is the smoothing matrix, then Sy = ŷ + Sr.Show that the same is true for local linear regression (Section 6.1.1). Henceargue that the adjustment step in the second line of (2) in Algorithm 9.1is unnecessary.Ex. 9.2 Let A be a known k × k matrix, b be a known k-vector, and zbe an unknown k-vector. A Gauss–Seidel algorithm for solving the linearsystem of equations Az = b works by successively solving for element zj inthe jth equation, fixing all other zj ’s at their current guesses.
This processis repeated for j = 1, 2, . . . , k, 1, 2, . . . , k, . . . , until convergence (Golub andVan Loan, 1983).(a) Consider an additive model with N observations and p terms, withthe jth term to be fit by a linear smoother Sj . Consider the followingsystem of equations: I S1 S1 · · · S1f1S1 y S 2 I S 2 · · · S 2 f2 S 2 y (9.33) ...... . ... .. = .. . ....... SpSpSp···IfpSp yHere each fj is an N -vector of evaluations of the jth function atthe data points, and y is an N -vector of the response values. Showthat backfitting is a blockwise Gauss–Seidel algorithm for solving thissystem of equations.(b) Let S1 and S2 be symmetric smoothing operators (matrices) witheigenvalues in [0, 1). Consider a backfitting algorithm with responsevector y and smoothers S1 , S2 .
Show that with any starting values,the algorithm converges and give a formula for the final iterates.Ex. 9.3 Backfitting equations. Consider a backfitting procedure with orthogonal projections, and let D be the overall regression matrix whose columnsspan V = Lcol (S1 ) ⊕ Lcol (S2 ) ⊕ · · · ⊕ Lcol (Sp ), where Lcol (S) denotes thecolumn space of a matrix S. Show that the estimating equations I S1 S1 · · · S1f1S1 y S 2 I S 2 · · · S 2 f2 S 2 y ...... . ... .. = ..
....... SpSpSp···IfpSp yare equivalent to the least squares normal equations DT Dβ = DT y whereβ is the vector of coefficients.3369. Additive Models, Trees, and Related MethodsEx. 9.4 Suppose the same smoother S is used to estimate both terms in atwo-term additive model (i.e., both variables are identical).
Assume that Sis symmetric with eigenvalues in [0, 1). Show that the backfitting residualconverges to (I + S)−1 (I − S)y, and that the residual sum of squares converges upward. Can the residual sum of squares converge upward in lessstructured situations? How does this fit compare to the fit with a singleterm fit by S? [Hint: Use the eigen-decomposition of S to help with thiscomparison.]Ex. 9.5 Degrees of freedom of a tree.
Given data yi with mean f (xi ) andvariance σ 2 , and aPfitting operation y → ŷ, let’s define the degrees offreedom of a fit by i cov(yi , ŷi )/σ 2 .Consider a fit ŷ estimated by a regression tree, fit to a set of predictorsX1 , X2 , . . . , Xp .(a) In terms of the number of terminal nodes m, give a rough formula forthe degrees of freedom of the fit.(b) Generate 100 observations with predictors X1 , X2 , . . . , X10 as independent standard Gaussian variates and fix these values.(c) Generate response values also as standard Gaussian (σ 2 = 1), independent of the predictors.
Fit regression trees to the data of fixed size 1,5and 10 terminal nodes and hence estimate the degrees of freedom ofeach fit. [Do ten simulations of the response and average the results,to get a good estimate of degrees of freedom.](d) Compare your estimates of degrees of freedom in (a) and (c) anddiscuss.(e) If the regression tree fit were a linear operation, we could write ŷ = Syfor some matrix S. Then the degrees of freedom would be tr(S).Suggest a way to compute an approximate S matrix for a regressiontree, compute it and compare the resulting degrees of freedom tothose in (a) and (c).Ex.
9.6 Consider the ozone data of Figure 6.9.(a) Fit an additive model to the cube root of ozone concentration. as afunction of temperature, wind speed, and radiation. Compare yourresults to those obtained via the trellis display in Figure 6.9.(b) Fit trees, MARS, and PRIM to the same data, and compare the resultsto those found in (a) and in Figure 6.9.This is page 337Printer: Opaque this10Boosting and Additive Trees10.1 Boosting MethodsBoosting is one of the most powerful learning ideas introduced in the lasttwenty years.
It was originally designed for classification problems, but aswill be seen in this chapter, it can profitably be extended to regressionas well. The motivation for boosting was a procedure that combines theoutputs of many “weak” classifiers to produce a powerful “committee.”From this perspective boosting bears a resemblance to bagging and othercommittee-based approaches (Section 8.8). However we shall see that theconnection is at best superficial and that boosting is fundamentally different.We begin by describing the most popular boosting algorithm due toFreund and Schapire (1997) called “AdaBoost.M1.” Consider a two-classproblem, with the output variable coded as Y ∈ {−1, 1}. Given a vector ofpredictor variables X, a classifier G(X) produces a prediction taking oneof the two values {−1, 1}.
The error rate on the training sample isN1 Xerr =I(yi 6= G(xi )),N i=1and the expected error rate on future predictions is EXY I(Y 6= G(X)).A weak classifier is one whose error rate is only slightly better thanrandom guessing. The purpose of boosting is to sequentially apply theweak classification algorithm to repeatedly modified versions of the data,thereby producing a sequence of weak classifiers Gm (x), m = 1, 2, . .
. , M .33810. Boosting and Additive TreesFinal ClassifierhPiMG(x) = signm=1 αm Gm (x)Weighted SampleGM (x)Weighted SampleG3 (x)Weighted SampleG2 (x)Training SampleG1 (x)FIGURE 10.1. Schematic of AdaBoost. Classifiers are trained on weighted versions of the dataset, and then combined to produce a final prediction.The predictions from all of them are then combined through a weightedmajority vote to produce the final prediction:!MXG(x) = signαm Gm (x) .(10.1)m=1Here α1 , α2 , .
. . , αM are computed by the boosting algorithm, and weightthe contribution of each respective Gm (x). Their effect is to give higherinfluence to the more accurate classifiers in the sequence. Figure 10.1 showsa schematic of the AdaBoost procedure.The data modifications at each boosting step consist of applying weightsw1 , w2 , . . . , wN to each of the training observations (xi , yi ), i = 1, 2, .
. . , N .Initially all of the weights are set to wi = 1/N , so that the first step simplytrains the classifier on the data in the usual manner. For each successiveiteration m = 2, 3, . . . , M the observation weights are individually modified and the classification algorithm is reapplied to the weighted observations. At step m, those observations that were misclassified by the classifierGm−1 (x) induced at the previous step have their weights increased, whereasthe weights are decreased for those that were classified correctly. Thus asiterations proceed, observations that are difficult to classify correctly receive ever-increasing influence. Each successive classifier is thereby forced10.1 Boosting Methods339Algorithm 10.1 AdaBoost.M1.1. Initialize the observation weights wi = 1/N, i = 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
