Past exam of the advanced topics in statistical machine learning course of the University of Oxford / 2025 / 3

A transformer block has two principal sublayers: multi-head attention and a positionwise feedforward neural network. Each sublayer has a residual connection and layer normalization. To make the components explicit, let $X\in {\mathbb{R}}^{L\times d_{\mathrm{model}}}$ contain the representations of $L$ sequence positions. For head $h$, learned projections formThe scaled dot-product attention output iswhere the softmax function acts along each row and $B$ is an optional attention mask. For causal self-attention, disallowed future positions receive $-\infty$ before the softmax function, giving zero attention weights. In self-attention, queries, keys, and values all come from the same input sequence. The multi-head attention output concatenates the heads and projects them:A standard post-normalization transformer block can then be writtenHere layer normalization normalizes the feature coordinates of each position separately, within each example, and applies learned scales and shifts. The positionwise feedforward neural network applies the same two affine maps and activation function at every position, for exampleThus attention mixes information between positions, while the feedforward sublayer transforms each position's features. The residual connections support propagation through a deep stack, and dropout is often used during training. Pre-normalization variants move layer normalization before the sublayer. A model's positional encoding supplies order information to the sequence representation or attention mechanism; a decoder in an encoder-decoder model also has a cross-attention sublayer between its self-attention and feedforward neural network sublayers.

A recurrent neural network processes positions through a recurrence such as $h_t=F(h_{t-1},x_t)$. Computing $h_t$ requires $h_{t-1}$, so the standard computation is sequential across sequence positions, although different examples in a batch can be processed in parallel. Information from position $s$ to $t$ must pass through $t-s$ recurrent steps, and backpropagated gradients involve products of that many step Jacobian matrices. This creates vanishing gradients or exploding gradients and can make long-range dependencies difficult to learn. Gating can mitigate these difficulties while retaining the recurrent dependence.

In a transformer block, all queries, keys, and values for an available input sequence can be formed in parallel. The self-attention weights are computed by matrix multiplication, so positions within one layer can be processed together; layers themselves remain sequential. With unrestricted self-attention, one position can directly receive information from any other position in one layer, giving a constant-length route across distant positions rather than one proportional to their separation. With causal self-attention, there is the same direct route to any permitted earlier position.

A transformer model supports parallel training across known sequence positions and short routes for long-range dependencies. Even a causal model can compute all training positions together when the entire training sequence is supplied and the attention mask excludes future positions. However, ordinary autoregressive generation still generates one new token at a time. Full self-attention also constructs $L^2$ pairwise scores, with quadratic time and storage in sequence length for the direct implementation; a standard recurrent neural network has linear sequential work in sequence length at fixed hidden width. Neither architecture guarantees that a useful long-range dependency will actually be learned.

Gaussian process regression supplies a predictive distribution and uncertainty estimates. A Gaussian process regression posterior gives both a posterior mean and a posterior variance, allowing credible intervals for the latent function and a posterior predictive distribution for future noisy observations. The kernel ridge regression estimator by itself specifies a point estimate.

With the same positive-semidefinite kernel and matching regularization, the Gaussian process regression posterior mean equals the kernel ridge regression prediction. Thus the main additional benefit is the explicit probability distribution of predictions, conditional on the chosen Gaussian process model and its hyperparameters, rather than an automatic improvement in point-prediction accuracy.

Condition throughout on the training inputs and $x_{\ast }$. Interpret $\theta$ here as the fixed covariance function and noise hyperparameters. Assume observation errors ${ϵ}_i$ are independent standard normal random variables, independent of the Gaussian process $f$, and writeThe independent-error assumption is the standard Gaussian process regression interpretation of the observation model; the single-observation marginal noise law alone would not specify cross-observation noise correlations. We take ${\sigma }^2>0$ so that $C$ is a positive-definite matrix. More generally the inverse formulas below apply whenever the indicated noisy covariance matrices are invertible.

The Gaussian process prior makes $(f_{\ast },\mathbf{f})$ a Gaussian random vector. Adding the independent Gaussian noise vector to $\mathbf{f}$ preserves a multivariate normal distribution. Its mean is zero, its observation covariance matrix is $C$, and $\mathrm{Cov}(f_{\ast },y_i)=k(x_{\ast },x_i)$ because the noise is independent of $f_{\ast }$. ThereforeA degenerate latent variance is allowed; the displayed multivariate normal distribution then denotes a Gaussian law even if it has no full-dimensional probability density.

The conditional multivariate normal distribution giveswhereFor a direct justification, form $R=f_{\ast }-k_{\ast }^T{C}^{-1}\mathbf{y}$. It is jointly Gaussian with $\mathbf{y}$, has zero mean, and satisfiesThe independence of uncorrelated jointly normal variables therefore makes $R$ independent of $\mathbf{y}$. Conditional on $\mathbf{y}$, only the displayed affine shift remains, proving the result. This is the latent-function posterior variance; a new observation $y_{\ast }=f_{\ast }+\sigma {ϵ}_{\ast }$ with fresh independent noise has predictive variance $v_n(x_{\ast })+{\sigma }^2$.

Use only the first $n-1$ observations to defineThus the full noisy covariance matrix is $C_n=\left(\begin{array}{cc}A& b\\ b^T& c\end{array}\right)$ and the full cross-covariance vector is $(a^T,d{)}^T$. SetThe scalar $s$ is the Schur complement of $A$. Substituting the block inverse into the Gaussian process regression posterior variance givesConsequently,andFor interpretation, after the first $n-1$ observations the remaining covariance between $f_{\ast }$ and $f(x_n)$ is $r=d-b^T{A}^{-1}a$, while the conditional variance of the new noisy observation is $s$. Thus the reduction is the squared remaining covariance divided by the remaining observation variance.

The Schur complement can be writtenbecause the first term is a conditional variance and ${\sigma }^2>0$. Therefore $c_1=s^{-1}>0$ and the squared term is nonnegative, soEquality holds exactly when the remaining conditional covariance $k(x_n,x_{\ast })-b^T{A}^{-1}a$ is zero. In particular, the reduction need not be strict even at a previously unseen input.

Additional observations weakly decrease the posterior variance at every fixed prediction input. Apply part (ii) repeatedly to add observations one at a time. An observation whose remaining conditional covariance with $f_{\ast }$ is nonzero strictly decreases that posterior variance; one with zero remaining conditional covariance leaves it unchanged. Large observation noise reduces the information gained through the denominator $v_{n-1}(x_n)+{\sigma }^2$.

For fixed Gaussian process hyperparameters and a Gaussian likelihood, the posterior variance depends on the observation locations and noise level, but not on the observed numerical outputs. Hence the reduction holds for each possible new output, rather than only on average. The predictive variance of a future noisy observation also decreases by the same amount because its extra independent noise variance is fixed. Refitting the hyperparameters after adding data can change the covariance function; the monotonicity statement compares conditioning under one fixed model.

For $x_n=x_{\ast }$, the notation of part (i) gives $b=a$, $d=k_{\ast \ast }$, and $c=k_{\ast \ast }+{\sigma }^2$. Write $v={\mathrm{Var}}_{n-1}(f_{\ast })=k_{\ast \ast }-a^T{A}^{-1}a$. The remaining covariance is then $v$ and the new observation's remaining variance is $v+{\sigma }^2$. ThusEquivalently,The expression is valid also when $v=0$ and ${\sigma }^2>0$. For $v>0$, a noiseless observation, interpreted as the limit ${\sigma }^2\downarrow 0$, removes all remaining variance at the observed target.

The source's assertion that the target input always gives the greatest reduction needs an additional hypothesis. The reduction formula above does not require that assertion. For a counterexample, use the linear kernel $k(x,x^{\prime })=x{x}^{\prime }$ with ${\sigma }^2=1$ and target $x_{\ast }=1$. With no informative previous observations, $v=1$. This can also be arranged with $n-1=1$ by observing first at $x_1=0$, which has zero covariance with all latent values. Observing at the target gives reduction $1/2$, whereas observing at $x_n=2$ givesIndeed this Gaussian process is $f(x)=xZ$ for a standard normal random variable $Z$, so the measurement at $2$ observes the same unknown coefficient with a larger signal relative to its noise.

One sufficient extra condition is that the existing latent posterior variance be maximal at $x_{\ast }$ among all candidate inputs. To prove it, let $w=v_{n-1}(x)$ and $r=\mathrm{Cov}(f(x),f_{\ast }\mid {\mathbf{y}}_{1:n-1},\theta )$. The Cauchy-Schwarz inequality gives $r^2\le vw$. If $w\le v$, thenbecause $w\mapsto w/(w+{\sigma }^2)$ is increasing. Thus target sampling is optimal under this extra condition, but it is not implied by the paper's arbitrary-covariance function assumptions.