The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 46
Текст из файла (страница 46)
5.5 Write a program to classify the phoneme data using a quadratic discriminant analysis (Section 4.3). Since there are many correlated features,you should filter them using a smooth basis of natural cubic splines (Section 5.2.3). Decide beforehand on a series of five different choices for thenumber and position of the knots, and use tenfold cross-validation to makethe final selection.
The phoneme data are available from the book websitewww-stat.stanford.edu/ElemStatLearn.Ex. 5.6 Suppose you wish to fit a periodic function, with a known period T .Describe how you could modify the truncated power series basis to achievethis goal.Ex. 5.7 Derivation of smoothing splines (Green and Silverman, 1994). Suppose that N ≥ 2, and that g is the natural cubic spline interpolant to thepairs {xi , zi }N1 , with a < x1 < · · · < xN < b. This is a natural spline1845. Basis Expansions and Regularizationwith a knot at every xi ; being an N -dimensional space of functions, we candetermine the coefficients such that it interpolates the sequence zi exactly.Let g̃ be any other differentiable function on [a, b] that interpolates the Npairs.(a) Let h(x) = g̃(x) − g(x).
Use integration by parts and the fact that g isa natural cubic spline to show thatZbg ′′ (x)h′′ (x)dx=−=0.a(b) Hence show thatZba′′2N−1Xj=1g̃ (t) dt ≥g ′′′ (x+j ){h(xj+1 ) − h(xj )} (5.72)Zb2g ′′ (t) dt,aand that equality can only hold if h is identically zero in [a, b].(c) Consider the penalized least squares problem#"NZ bX′′22f (t) dt .(yi − f (xi )) + λminfi=1aUse (b) to argue that the minimizer must be a cubic spline with knotsat each of the xi .Ex. 5.8 In the appendix to this chapter we show how the smoothing splinecomputations could be more efficiently carried out using a (N + 4) dimensional basis of B-splines.
Describe a slightly simpler scheme using a (N + 2)dimensional B-spline basis defined on the N − 2 interior knots.Ex. 5.9 Derive the Reinsch form Sλ = (I + λK)−1 for the smoothing spline.Ex. 5.10 Derive an expression for Var(fˆλ (x0 )) and bias(fˆλ (x0 )). Using theexample (5.22), create a version of Figure 5.9 where the mean and several(pointwise) quantiles of fˆλ (x) are shown.Ex. 5.11 Prove that for a smoothing spline the null space of K is spannedby functions linear in X.Ex. 5.12 Characterize the solution to the following problem,min RSS(f, λ) =fNXi=1wi {yi − f (xi )}2 + λZ{f ′′ (t)}2 dt,(5.73)where the wi ≥ 0 are observation weights.Characterize the solution to the smoothing spline problem (5.9) whenthe training data have ties in X.Exercises185Ex.
5.13 You have fitted a smoothing spline fˆλ to a sample of N pairs(xi , yi ). Suppose you augment your original sample with the pair x0 , fˆλ (x0 ),and refit; describe the result. Use this to derive the N -fold cross-validationformula (5.26).Ex. 5.14 Derive the constraints on the αj in the thin-plate spline expansion (5.39) to guarantee that the penalty J(f ) is finite. How else could oneensure that the penalty was finite?Ex. 5.15 This exercise derives some of the results quoted in Section 5.8.1.Suppose K(x, y) satisfying the conditions (5.45) and let f (x) ∈ HK . Showthat(a) hK(·, xi ), f iHK = f (xi ).(b) hK(·, xi ), K(·, xj )iHK = K(xi , xj ).PN(c) If g(x) = i=1 αi K(x, xi ), thenJ(g) =NN XXK(xi , xj )αi αj .i=1 j=1Suppose that g̃(x) = g(x) + ρ(x), with ρ(x) ∈ HK , and orthogonal in HKto each of K(x, xi ), i = 1, .
. . , N . Show that(d)NXi=1L(yi , g̃(xi )) + λJ(g̃) ≥NXL(yi , g(xi )) + λJ(g)(5.74)i=1with equality iff ρ(x) = 0.Ex. 5.16 Consider the ridge regression problem (5.53), and assume M ≥ N .Assume you have a kernel K that computes the inner product K(x, y) =PMm=1 hm (x)hm (y).(a) Derive (5.62) on page 171 in the text. How would you compute thematrices V and Dγ , given K? Hence show that (5.63) is equivalentto (5.53).(b) Show thatf̂==Hβ̂K(K + λI)−1 y,(5.75)where H is the N × M matrix of evaluations hm (xi ), and K = HHTthe N × N matrix of inner-products h(xi )T h(xj ).1865.
Basis Expansions and Regularization(c) Show thatfˆ(x)==h(x)T β̂NXK(x, xi )α̂i(5.76)i=1and α̂ = (K + λI)−1 y.(d) How would you modify your solution if M < N ?Ex. 5.17 Show how to convert the discrete eigen-decomposition of K inSection 5.8.2 to estimates of the eigenfunctions of K.Ex.
5.18 The wavelet function ψ(x) of the symmlet-p wavelet basis hasvanishing moments up to order p. Show that this implies that polynomialsof order p are represented exactly in V0 , defined on page 176.Ex. 5.19 Show that the Haar wavelet transform of a signal of length N = 2Jcan be computed in O(N ) computations.Appendix: Computations for SplinesIn this Appendix, we describe the B-spline basis for representing polynomial splines.
We also discuss their use in the computations of smoothingsplines.B-splinesBefore we can get started, we need to augment the knot sequence definedin Section 5.2. Let ξ0 < ξ1 and ξK < ξK+1 be two boundary knots, whichtypically define the domain over which we wish to evaluate our spline.
Wenow define the augmented knot sequence τ such that• τ 1 ≤ τ2 ≤ · · · ≤ τM ≤ ξ 0 ;• τj+M = ξj , j = 1, · · · , K;• ξK+1 ≤ τK+M +1 ≤ τK+M +2 ≤ · · · ≤ τK+2M .The actual values of these additional knots beyond the boundary are arbitrary, and it is customary to make them all the same and equal to ξ0 andξK+1 , respectively.Denote by Bi,m (x) the ith B-spline basis function of order m for theknot-sequence τ , m ≤ M .
They are defined recursively in terms of dividedAppendix: Computations for Splines187differences as follows:1 if τi ≤ x < τi+1Bi,1 (x) =(5.77)0 otherwisefor i = 1, . . . , K + 2M − 1. These are also known as Haar basis functions.x − τiτi+m − xBi,m−1 (x) +Bi+1,m−1 (x)τi+m−1 − τiτi+m − τi+1for i = 1, . . . , K + 2M − m.(5.78)Bi,m (x)=Thus with M = 4, Bi,4 , i = 1, · · · , K + 4 are the K + 4 cubic B-splinebasis functions for the knot sequence ξ. This recursion can be continued and will generate the B-spline basis for any order spline.
Figure 5.20shows the sequence of B-splines up to order four with knots at the points0.0, 0.1, . . . , 1.0. Since we have created some duplicate knots, some carehas to be taken to avoid division by zero. If we adopt the conventionthat Bi,1 = 0 if τi = τi+1 , then by induction Bi,m = 0 if τi = τi+1 =. . . = τi+m . Note also that in the construction above, only the subsetBi,m , i = M − m + 1, . . . , M + K are required for the B-spline basisof order m < M with knots ξ.To fully understand the properties of these functions, and to show thatthey do indeed span the space of cubic splines for the knot sequence, requires additional mathematical machinery, including the properties of divided differences.
Exercise 5.2 explores these issues.The scope of B-splines is in fact bigger than advertised here, and has todo with knot duplication. If we duplicate an interior knot in the construction of the τ sequence above, and then generate the B-spline sequence asbefore, the resulting basis spans the space of piecewise polynomials withone less continuous derivative at the duplicated knot.
In general, if in addition to the repeated boundary knots, we include the interior knot ξj1 ≤ rj ≤ M times, then the lowest-order derivative to be discontinuousat x = ξj will be order M − rj . Thus for cubic splines with no repeats,rj = 1, j = 1, . . . , K, and at each interior knot the third derivatives (4 − 1)are discontinuous. Repeating the jth knot three times leads to a discontinuous 1st derivative; repeating it four times leads to a discontinuous zerothderivative, i.e., the function is discontinuous at x = ξj . This is exactly whathappens at the boundary knots; we repeat the knots M times, so the splinebecomes discontinuous at the boundary knots (i.e., undefined beyond theboundary).The local support of B-splines has important computational implications, especially when the number of knots K is large.
Least squares computations with N observations and K + M variables (basis functions) takeO(N (K + M )2 + (K + M )3 ) flops (floating point operations.) If K is someappreciable fraction of N , this leads to O(N 3 ) algorithms which becomes1885. Basis Expansions and Regularization0.00.40.81.2B-splines of Order 10.00.20.40.60.81.00.81.00.81.00.81.00.00.40.81.2B-splines of Order 20.00.20.40.60.00.40.81.2B-splines of Order 30.00.20.40.60.00.40.81.2B-splines of Order 40.00.20.40.6FIGURE 5.20.
The sequence of B-splines up to order four with ten knots evenlyspaced from 0 to 1. The B-splines have local support; they are nonzero on aninterval spanned by M + 1 knots.Appendix: Computations for Splines189unacceptable for large N . If the N observations are sorted, the N ×(K +M )regression matrix consisting of the K + M B-spline basis functions evaluated at the N points has many zeros, which can be exploited to reduce thecomputational complexity back to O(N ). We take this up further in thenext section.Computations for Smoothing SplinesAlthough natural splines (Section 5.2.1) provide a basis for smoothingsplines, it is computationally more convenient Pto operate in the larger spaceN +4of unconstrained B-splines.
We write f (x) = 1γj Bj (x), where γj arecoefficients and the Bj are the cubic B-spline basis functions. The solutionlooks the same as before,γ̂ = (BT B + λΩB )−1 BT y,(5.79)except now the N × N matrix N is replaced by the N × (N + 4) matrixB, and similarly the (N + 4) × (N + 4) penalty matrix ΩB replaces theN × N dimensional ΩN . Although at face value it seems that there areno boundary derivative constraints, it turns out that the penalty termautomatically imposes them by giving effectively infinite weight to any nonzero derivative beyond the boundary. In practice, γ̂ is restricted to a linearsubspace for which the penalty is always finite.Since the columns of B are the evaluated B-splines, in order from leftto right and evaluated at the sorted values of X, and the cubic B-splineshave local support, B is lower 4-banded. Consequently the matrix M =(BT B + λΩ) is 4-banded and hence its Cholesky decomposition M = LLTcan be computed easily.
One then solves LLT γ = BT y by back-substitutionto give γ and hence the solution fˆ in O(N ) operations.In practice, when N is large, it is unnecessary to use all N interior knots,and any reasonable thinning strategy will save in computations and havenegligible effect on the fit. For example, the smooth.spline function in SPLUS uses an approximately logarithmic strategy: if N < 50 all knots areincluded, but even at N = 5, 000 only 204 knots are used.1905. Basis Expansions and RegularizationThis is page 191Printer: Opaque this6Kernel Smoothing MethodsIn this chapter we describe a class of regression techniques that achieveflexibility in estimating the regression function f (X) over the domain IRpby fitting a different but simple model separately at each query point x0 .This is done by using only those observations close to the target point x0 tofit the simple model, and in such a way that the resulting estimated functionfˆ(X) is smooth in IRp .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
