The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 45
Текст из файла (страница 45)
More generally, the symmlet-pfamily has a support of 2p − 1 consecutive intervals. The wider thesupport, the more time the wavelet has to die to zero, and so it can5.9 Wavelet Smoothing179achieve this more smoothly. Note that the effective support seems tobe much narrower.• The symmlet-p wavelet ψ(x) has p vanishing moments; that is,Zψ(x)xj dx = 0, j = 0, . . . , p − 1.One implication is that any order-p polynomial over the N = 2J timespoints is reproduced exactly in V0 (Exercise 5.18). In this sense V0is equivalent to the null space of the smoothing-spline penalty. TheHaar wavelets have one vanishing moment, and V0 can reproduce anyconstant function.The symmlet-p scaling functions are one of many families of waveletgenerators. The operations are similar to those for the Haar basis:• If√ V0 is spanned by φ(x −Pk), then V1 ⊃ V0 is spanned by φ1,k (x) =2φ(2x−k) and φ(x) = k∈Z h(k)φ1,k (x), for some filter coefficientsh(k).P• W0 is spanned by ψ(x) = k∈Z g(k)φ1,k (x), with filter coefficientsg(k) = (−1)1−k h(1 − k).5.9.2 Adaptive Wavelet FilteringWavelets are particularly useful when the data are measured on a uniformlattice, such as a discretized signal, image, or a time series.
We will focus onthe one-dimensional case, and having N = 2J lattice-points is convenient.Suppose y is the response vector, and W is the N ×N orthonormal waveletbasis matrix evaluated at the N uniformly spaced observations. Then y∗ =WT y is called the wavelet transform of y (and is the full least squaresregression coefficient). A popular method for adaptive wavelet fitting isknown as SURE shrinkage (Stein Unbiased Risk Estimation, Donoho andJohnstone (1994)). We start with the criterionmin ||y − Wθ||22 + 2λ||θ||1 ,θ(5.68)which is the same as the lasso criterion in Chapter 3. Because W is orthonormal, this leads to the simple solution:θ̂j = sign(yj∗ )(|yj∗ | − λ)+ .(5.69)The least squares coefficients are translated toward zero, and truncatedat zero. The fitted function (vector) is then given by the inverse wavelettransform f̂ = Wθ̂.1805.
Basis Expansions and Regularization√A simple choice for λ is λ = σ 2 log N , where σ is an estimate of thestandard deviation of the noise. We can give some motivation for this choice.Since W is an orthonormal transformation, if the elements of y are whitenoise (independent Gaussian variates with mean 0 and variance σ 2 ), thenso are y∗ . Furthermore if random variables Z1 , Z2 , . . . , ZN are white√ noise,the expected maximum of |Z√j |, j = 1, . . . , N is approximately σ 2 log N .Hence all coefficients below σ 2 log N are likely to be noise and are set tozero.The space W could be any basis of orthonormal functions: polynomials,natural splines or cosinusoids. What makes wavelets special is the particularform of basis functions used, which allows for a representation localized intime and in frequency.Let’s look again at the NMR signal of Figure 5.17.
The wavelet transformwas computed using a symmlet−8 basis. Notice that the coefficients do notdescend all the way to V0 , but stop at V4 which has 16 basis functions.As we ascend to each level of detail, the coefficients get smaller, except inlocations where spiky behavior is present. The wavelet coefficients representcharacteristics of the signal localized in time (the basis functions at eachlevel are translations of each other) and localized in frequency. Each dilationincreases the detail by a factor of two, and in this sense corresponds todoubling the frequency in a traditional Fourier representation.
In fact, amore mathematical understanding of wavelets reveals that the wavelets ata particular scale have a Fourier transform that is restricted to a limitedrange or octave of frequencies.The shrinking/truncation in the right panel was achieved using the SUREapproach described in the introduction to this section.
The orthonormalN × N basis matrix W has columns which are the wavelet basis functionsevaluated at the N time points. In particular, in this case there will be 16columns corresponding to the φ4,k (x), and the remainder devoted to theψj,k (x), j = 4, . . . , 11. In practice λ depends on the noise variance, and hasto be estimated from the data (such as the variance of the coefficients atthe highest level).Notice the similarity between the SURE criterion (5.68) on page 179,and the smoothing spline criterion (5.21) on page 156:• Both are hierarchically structured from coarse to fine detail, althoughwavelets are also localized in time within each resolution level.• The splines build in a bias toward smooth functions by imposingdifferential shrinking constants dk .
Early versions of SURE shrinkagetreated all scales equally. The S+wavelets function waveshrink() hasmany options, some of which allow for differential shrinkage.• The spline L2 penalty cause pure shrinkage, while the SURE L1penalty does shrinkage and selection.Exercises181More generally smoothing splines achieve compression of the original signalby imposing smoothness, while wavelets impose sparsity. Figure 5.19 compares a wavelet fit (using SURE shrinkage) to a smoothing spline fit (usingcross-validation) on two examples different in nature. For the NMR data inthe upper panel, the smoothing spline introduces detail everywhere in orderto capture the detail in the isolated spikes; the wavelet fit nicely localizesthe spikes.
In the lower panel, the true function is smooth, and the noise isrelatively high. The wavelet fit has let in some additional and unnecessarywiggles—a price it pays in variance for the additional adaptivity.The wavelet transform is not performed by matrix multiplication as iny∗ = WT y. In fact, using clever pyramidal schemes y∗ can be obtainedin O(N ) computations, which is even faster than the N log(N ) of the fastFourier transform (FFT). While the general construction is beyond thescope of this book, it is easy to see for the Haar basis (Exercise 5.19).Likewise, the inverse wavelet transform Wθ̂ is also O(N ).This has been a very brief glimpse of this vast and growing field. There isa very large mathematical and computational base built on wavelets.
Modern image compression is often performed using two-dimensional waveletrepresentations.Bibliographic NotesSplines and B-splines are discussed in detail in de Boor (1978). Greenand Silverman (1994) and Wahba (1990) give a thorough treatment ofsmoothing splines and thin-plate splines; the latter also covers reproducingkernel Hilbert spaces. See also Girosi et al. (1995) and Evgeniou et al.(2000) for connections between many nonparametric regression techniquesusing RKHS approaches. Modeling functional data, as in Section 5.2.3, iscovered in detail in Ramsay and Silverman (1997).Daubechies (1992) is a classic and mathematical treatment of wavelets.Other useful sources are Chui (1992) and Wickerhauser (1994). Donoho andJohnstone (1994) developed the SURE shrinkage and selection technologyfrom a statistical estimation framework; see also Vidakovic (1999).
Bruceand Gao (1996) is a useful applied introduction, which also describes thewavelet software in S-PLUS.ExercisesEx. 5.1 Show that the truncated power basis functions in (5.3) represent abasis for a cubic spline with the two knots as indicated.5. Basis Expansions and Regularization6018202040splinewavelet020040060080010004NMR Signal•0-4-2n2•••• • •• ••• ••••••• •• • •• •••• •••••••• • • ••••••••••• • •• • • • • •••• •• • • • •• •• •• •••••• • •• • • •• • • • • ••• •• • ••• ••••••••• •• • •• ••••spline••••••wavelet•• •true•••••0.00.20.40.60.81.0Smooth Function (Simulated)FIGURE 5.19.
Wavelet smoothing compared with smoothing splines on twoexamples. Each panel compares the SURE-shrunk wavelet fit to the cross-validatedsmoothing spline fit.Exercises183Ex. 5.2 Suppose that Bi,M (x) is an order-M B-spline defined in the Appendix on page 186 through the sequence (5.77)–(5.78).(a) Show by induction that Bi,M (x) = 0 for x 6∈ [τi , τi+M ]. This shows, forexample, that the support of cubic B-splines is at most 5 knots.(b) Show by induction that Bi,M (x) > 0 for x ∈ (τi , τi+M ). The B-splinesare positive in the interior of their support.PK+M(c) Show by induction that i=1 Bi,M (x) = 1 ∀x ∈ [ξ0 , ξK+1 ].(d) Show that Bi,M is a piecewise polynomial of order M (degree M − 1)on [ξ0 , ξK+1 ], with breaks only at the knots ξ1 , .
. . , ξK .(e) Show that an order-M B-spline basis function is the density functionof a convolution of M uniform random variables.Ex. 5.3 Write a program to reproduce Figure 5.3 on page 145.Ex. 5.4 Consider the truncated power series representation for cubic splineswith K interior knots. Letf (X) =3Xβj X j +j=0KXk=1θk (X − ξk )3+ .(5.70)Prove that the natural boundary conditions for natural cubic splines (Section 5.2.1) imply the following linear constraints on the coefficients:β2 = 0,β3 = 0,PKθ = 0,PKk=1 kξk=1 k θk = 0.(5.71)Hence derive the basis (5.4) and (5.5).Ex.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
