Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 45 (Introduction to Data Mining)

Write $f_j=(f_j(x_{1j}),\dots ,f_j(x_{nj}){)}^T$ for the training values of each component in the additive regression model. Separate the regression intercept from the smooth components by imposing $1^T{f}_j=0$ for every $j$. Without these constraints, adding a constant to a component and subtracting it from the intercept gives exactly the same mean function. A population alternative is $\mathbb{E}{f}_j(X_j)=0$ when those expectations exist. Additional identifiability of additive regression components requirements exclude redundant component directions, as discussed below.

The backfitting algorithm proceeds as follows:

Because every component remains centered, the least-squares update of the intercept remains $\overline{y}$ throughout. The essential update isFor penalized least-squares smoothers these updates are coordinate descent on the additive fitting objective. For a completely arbitrary smoother, convergence is an additional property to establish, not a consequence of merely specifying the iteration. Centering removes the constant ambiguity but does not by itself remove concurvity.

There are two distinct identifiability issues. Without centering, constants can move between the regression intercept and the additive components. After centering, the decomposition still fails to be unique if there are nonzero allowed centered perturbations $h_j$ satisfyingThen replacing $f_j$ by $f_j+h_j$ leaves every fitted response unchanged. This nonlinear analogue of multicollinearity is concurvity. For example, if two predictor columns are identical, a centered function $h$ can be added to the effect of the first and subtracted from the effect of the second. Conceptually, the data observe their combined effect but cannot tell which predictor deserves the credit. A unique fitted sum can therefore coexist with nonunique individual effects. Smoothness penalties can distinguish some such decompositions, so a representation ambiguity is not automatically an ambiguity of every penalized estimator.

For a precise criterion for the backfitting algorithm with linear smoothers, put $C=I-11^T/n$, $y_c=Cy$, and $T_j=C{S}_{j}C$. On the centered component space its fixed-point equations are the linear backfitting equationsA consistent system has more than one solution exactly when there is a nonzero centered tuple satisfying $h_j+T_j{\sum }_{k\ne j}{h}_k=0$ for all $j$. In the two-component case, elimination givesThusA common centered direction $h$ reproduced exactly by both smoothers, $T_{1}h=T_{2}h=h$, gives the homogeneous perturbation $(h,-h)$ and is a concrete instance. For example, two identical predictor columns with smoothers that reproduce the same centered linear trend have this property. Approximate concurvity yields an eigenvalue near one, causing poor conditioning and slow or unstable component estimation, but it does not constitute exact nonuniqueness. Failure of an iteration to converge is also distinct from the existence of multiple fixed points.

To isolate the bias-variance tradeoff of the smoothing step, fix the three neighbor locations and write $Y_{(k)}=m_k+{ϵ}_{(k)}$, with independent zero-mean errors of common variance ${\sigma }^2$. At a target $x$, the local estimate isThe bias and variance of a three-neighbour weighted smoother areConsequently the variance is minimized by equal weights, $w=1/3$, when it equals ${\sigma }^2/3$. It decreases as $w$ increases from zero to $1/3$, and increases thereafter toward ${\sigma }^2$ as $w\to 1$. In particular, variance is not increasing over the entire interval $0<w<1$.

Giving more weight to the closest location reduces the influence of more distant responses and often reduces smoothing bias. If the closest location is the target itself, $m_1=m(x)$, put $\Delta =(m_2+m_3)/2-m(x)$. Then the squared bias is $(1-w{)}^2{\Delta }^2$, andThus a locally flat signal favors equal averaging, while stronger local smoothing bias favors greater nearest-point weight. At a general target the bias is affine in $w$, and its absolute value need not decrease: farther neighbors can cancel one another's approximation errors. Even without that cancellation, a smoothness-based worst-case bias bound decreases with $w$ because the first neighbor is closest. The exact tradeoff is therefore lower variance near balanced weights versus potentially lower bias near the closest-point fit. These formulas describe the elementary smoother; fitted partial residuals, centering and repeated backfitting can introduce dependence, so the variance of the final additive fit requires its full fitting operator rather than this single-step calculation.

For an $n\times p$ design matrix, distinguish the coefficient vector from the fitted-response vector. The ridge regression objective and its solution areThe gradient is $2(X^{T}X+\lambda I_p)\beta -2X^{T}Y$. For $\lambda >0$, $X^{T}X+\lambda I_p$ is a positive-definite matrix, so this is the unique minimizer even if $X$ is rank deficient. The expression with an additional leading $X$ is instead the $n$-vector of fitted values,This distinction corrects the dimensional mismatch in the printed coefficient-estimator notation.

The quadratic penalty discourages large coefficients, exchanging some bias for lower variance. If $X=UD{V}^T$ is a reduced singular value decomposition, with positive singular values $d_k$, thenThe principal-component shrinkage by ridge regression therefore shrinks directions with small $d_k^2$ most strongly. These are precisely the poorly determined directions created by multicollinearity, where ordinary least-squares coefficients can have large variance or fail to be uniquely determined. A positive penalty stabilizes their inversion and sets coefficients in the null space to zero. It does not make the predictors independent or provide a universal risk improvement for every signal. Because the penalty depends on coefficient units, predictors are ordinarily standardized before choosing $\lambda$ by cross-validation. An unpenalized intercept in ridge regression is handled separately by centering; the displayed objective either has no intercept or applies the penalty to every component included in $\beta$.

Use the Gaussian sampling model $Y\mid \beta \sim N(X\beta ,{\sigma }^2{I}_n)$ with known ${\sigma }^2>0$, and the independent prior $\beta \sim N(0,{\tau }^2{I}_p)$ with ${\tau }^2>0$. A Gaussian prior alone is not enough to imply the ridge result without this likelihood assumption. The posterior distribution is proportional toMaximizing it is equivalent to minimizing the ridge objective with $\lambda ={\sigma }^2/{\tau }^2$. More explicitly, complete the square. The posterior precision, covariance matrix and mean areConsequently the Gaussian posterior representation of ridge regression isA tighter prior, smaller ${\tau }^2$, implies stronger shrinkage; larger observation-noise variance at fixed prior scale also increases the penalty. The posterior covariance is $V$, not the frequentist sampling covariance of the ridge estimator, which is ${\sigma }^2(X^{T}X+\lambda I{)}^{-1}{X}^{T}X(X^{T}X+\lambda I{)}^{-1}$. If an intercept is to remain unpenalized, give only the slopes this proper Gaussian prior and center the design and responses.

The ridge regression penalty is quadratic, whereas the Lasso uses an absolute-value penalty. To make the constants explicit, compareBoth trade goodness of fit against coefficient size, and both require sensible predictor scaling and tuning. Ridge continuously shrinks coefficient directions and generally retains all variables. The Lasso's nonsmooth penalty can set coefficients exactly to zero, so it performs variable selection as well as shrinkage. When $X^{T}X=I$, let $z=X^{T}Y$. The distinction is especially transparent:The second formula is soft thresholding. For general designs, the Karush-Kuhn-Tucker conditions for the Lasso give $X_j^T(Y-X\hat{\beta })=t\mathrm{sign}({\hat{\beta }}_j)$ for a nonzero coefficient and $|X_j^T(Y-X\hat{\beta })|\le t$ for a zero coefficient. The latter interval permits exact zeros; the ridge equation instead is $X^T(Y-X\hat{\beta })=\lambda \hat{\beta }$.

Ridge is especially useful for stable prediction when many predictors carry small effects or are highly correlated. Its strictly convex penalty gives unique coefficients for $\lambda >0$ even in a rank-deficient design. It shares an effect among identical predictor columns: for a fixed coefficient sum the minimum quadratic penalty splits that sum equally. The Lasso can give a simpler sparse model when many effects are absent, but selection among strongly correlated predictors can be unstable. With identical columns, any same-sign split of a selected coefficient sum has the same absolute-value penalty and the same fitted values, so the coefficient vector need not be unique. This is a possible design degeneracy, not a claim that every Lasso fit is nonunique.

The penalties also encode different prior shapes: the Gaussian prior yields ridge, while independent double-exponential priors yield a Lasso posterior mode under Gaussian noise. A Lasso mode is not generally its posterior mean. Practically, sparse interpretability favors the Lasso, while stable distributed effects can favor ridge; prediction performance should be checked with cross-validation, and neither method universally dominates the other.

Use labels $y_i\in \{-1,1\}$ and base predictions $G_m(x)\in \{-1,1\}$. The binary AdaBoost algorithm starts with observation weights $D_1(i)=1/n$ and score $F_0(x)=0$. For rounds $m=1,\dots ,M$:

The final classifier isResolve a zero-score tie by a fixed convention. A classifier with error above $1/2$ may be sign-reversed if the base class permits it; otherwise it fails the weak-learning requirement and should be replaced. Error $1/2$ gives zero weight and no improvement. Error zero gives the limiting perfect-classifier step with infinite coefficient, so terminate with that classifier rather than computing the undefined finite update. Misclassified observations are multiplied by $e^{{\alpha }_m}$ and correctly classified observations by $e^{-{\alpha }_m}$, increasing the relative weight of errors for the next round. The procedure is sequential, and its number of rounds is a tuning parameter.

The exponential classification risk for the training sample is $\mathcal{L}(F)={\sum }_i{e}^{-y_{i}F(x_i)}$. At the start of round $m$, defineThus the observation weights arise directly from each point's current exponential loss. For a candidate base classifier $G$ and coefficient $\alpha$,where $ϵ$ is its error under $D_m$. For a fixed $\alpha >0$ the bracket is increasing in $ϵ$, so the appropriate base fit minimizes weighted classification error. With $G$ fixed, differentiation givesThe second derivative is positive, hence the exponential-loss derivation of AdaBoost yieldsThe normalizer is $Z_m=(1-{ϵ}_m)e^{-{\alpha }_m}+{ϵ}_m{e}^{{\alpha }_m}=2\sqrt{{ϵ}_m(1-{ϵ}_m)}$. Consequently the next normalized weights again satisfy $D_{m+1}(i)\propto e^{-y_i{F}_m(x_i)}$, proving the update by induction from uniform initial weights. The factor by which an error gains weight relative to a correct observation is $e^{2{\alpha }_m}=(1-{ϵ}_m)/{ϵ}_m$.

This calculation also explains why repeated weak fits can improve training performance. Since the initial mean exponential loss is one, its value after $M$ rounds is ${\prod }_m{Z}_m$. A misclassified point has $y_i{F}_M(x_i)\le 0$ and hence exponential loss at least one, giving the AdaBoost training error boundThe last inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. This is a training guarantee under positive edges, not a guarantee that further rounds always improve prediction on new observations.

A random forest constructs an ensemble of classification and regression trees. For each tree, draw a bootstrap sample of the training observations. Grow the tree by recursive partitioning; at each node, draw a fresh random subset of predictor coordinates and choose the best split only among those coordinates, using a criterion such as Gini impurity. Trees are ordinarily grown deeply with a chosen minimum terminal-node size and without the pruning used to select a single small tree. Repeat for many independently randomized trees. For binary classification, predict by majority vote; for regression, average the tree predictions. The out-of-bag error predicts each observation using only trees whose bootstrap samples omitted it, furnishing an internal assessment of prediction error.

The strategies differ in how they form a useful ensemble. The forest uses resampling and random predictor subsets to decorrelate trees; averaging then reduces the variability of individual tree predictions. For illustration, if equally weighted predictions have common variance $v$ and pairwise correlation $\rho$, the variance of their average is $v[\rho +(1-\rho )/M]$, showing why low inter-tree correlation matters. This identity describes a regression-prediction calculation; it is not an exact classification-error formula.

AdaBoost instead fits sequentially, with each round responding to errors of the accumulated score. It uses nonuniform observation weights and nonuniform final classifier weights derived from exponential loss; a forest's bootstrap sampling is ordinarily uniform and its final votes are ordinarily equal. Forest trees can be built in parallel once the data and tuning parameters are fixed, whereas each boosting stage depends on previous stages. Random forests commonly use deep trees; AdaBoost often uses shallow trees or stumps as weak learners, although its base class is not restricted to them. Reweighting persistent errors can make boosting sensitive to mislabeled points and outliers, while randomization and averaging often make a forest less sensitive; neither statement is a universal robustness theorem. Both methods require attention to ensemble size and tree complexity, and neither guarantees a better classifier for every dataset.

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.