Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 45 / 4

For a binary hypothesis class $\mathcal{H}=\{x\mapsto f(x,\alpha )\}$, a set of $m$ distinct points is shattered if every one of its $2^m$ binary labelings is realized by some member of $\mathcal{H}$. The VC dimension iswith value infinity if arbitrarily large finite sets are shattered. For real-valued scores, apply this definition to the associated binary decision functions, for example their signs. The word “some” matters: shattering every set of that size is not required.

As an example, take the interval classifiers on the real line, $f_{a,b}(x)=1_{\{a\le x\le b\}}$. Two ordered points $x_1<x_2$ can receive labels $00$, $10$, $01$ or $11$ by choosing an interval away from both, around the first, around the second, or containing both. Hence the class shatters two points. No three ordered points can be shattered, since any interval containing the first and third also contains the middle, making labeling $101$ impossible. Thus the VC dimension of interval indicators isThis describes combinatorial classification capacity, rather than merely counting written parameters; the definition applies equally to nonlinear or infinite-parameter classes.

Condition on the training covariates, and let $m_i=\mathbb{E}{Y}_i$. The fresh response $Y_i^N$ has the same marginal distribution as $Y_i$ and is independent of the complete training response vector, hence independent of ${\hat{Y}}_i=\hat{f}(x_i)$. Assume the relevant second moments are finite. Expanding the squared errors givesThe first expectation averages over both training and new responses; the second averages over training responses only. Subtracting cancels both second-moment terms, leavingAveraging over the design points proves the covariance formula for prediction optimism:No linear fitting rule or Gaussian noise assumption is needed. The difference arises because a training response and its fitted value are dependent, whereas a fresh response and the fitted value are independent. Ordinary fitting often makes those covariances positive and the training error too favorable, explaining the name prediction optimism.

For example, if $\hat{Y}=HY$ is a fixed linear smoother and $\mathrm{Cov}(Y)={\sigma }^{2}I$, then $\mathrm{Cov}(Y_i,{\hat{Y}}_i)={\sigma }^2{H}_{ii}$. ThusThis links the optimism correction to effective degrees of freedom. For a data-selected fitting operator, its realized trace alone does not generally give the covariance penalty, since selecting the model uses the responses too.

An orthonormal multiresolution analysis is a sequence of closed subspaces $V_j\subset L^2(\mathbb{R})$ satisfying $V_j\subset V_{j+1}$, $\overline{{\bigcup }_j{V}_j}=L^2(\mathbb{R})$, ${\bigcap }_j{V}_j=\{0\}$, and $f\in V_j$ iff $f(2\cdot )\in V_{j+1}$. A scaling function $\varphi$ has integer translates forming an orthonormal basis of $V_0$, and its scaled translates ${\varphi }_{j,k}(x)=2^{j/2}\varphi (2^{j}x-k)$ span $V_j$. Thus $V_j$ contains information at resolution about $2^{-j}$.

The detail space $W_j=V_{j+1}\cap V_j^{\perp }$ is generated by the corresponding wavelet functions ${\psi }_{j,k}(x)=2^{j/2}\psi (2^{j}x-k)$. The orthogonal splitting $V_{j+1}=V_j\oplus W_j$ iterates toAccordingly a square-integrable signal has a coarse-and-detail wavelet series,and its wavelet projection onto $V_J$ keeps the coarse coefficients and details below level $J$. Increasing $J$ adds finer-scale oscillations and localized features. On the real line there are infinitely many translates at each level; for a bounded observation interval, with an appropriate interval or periodic construction, the relevant approximation dimension satisfies $d_J\asymp 2^J$. For the Haar wavelet on a unit interval this is exactly $2^J$, corresponding to a separate mean on each dyadic subinterval.

This hierarchy gives a concrete meaning to wavelet approximation complexity. Coarse resolution uses few coefficients and can miss sharp features; fine resolution uses more coefficients and can fit noise. By orthogonality, projection bias is the energy of the omitted details,For an orthonormal sequence model with independent coefficient noise of variance ${\sigma }^2/n$, estimating the $d_J$ retained coefficients without shrinkage givesThe first term decreases with resolution while the second increases, making the bias-variance tradeoff explicit. Equivalently, a fixed orthogonal regression projection of rank $d_J$ has effective degrees of freedom $d_J$ and prediction optimism $2{\sigma }^2{d}_J/n$ under independent equal-variance errors.

Wavelets also permit local rather than only global complexity control. Thresholding small estimated detail coefficients, for example by soft thresholding, retains strong local structure while suppressing fine-scale noise elsewhere. A sparse retained coefficient set can represent localized features much more economically than keeping every coefficient through a high level. Its locations and scales matter as well as its count. If that set is selected using the same noisy responses, however, selection adds adaptivity: its raw coefficient count is not automatically its covariance-based degrees of freedom. Resolution or threshold tuning should therefore account for prediction error, using an appropriate risk estimate or cross-validation, rather than only decreasing training error.