Function Spaces and Kernels - The Statistics Notebook

A finite sample tells us the value of a curve at only finitely many locations. It cannot determine an arbitrary function everywhere else. Restrictions on the function space and a penalty are what make estimation possible.

Why interpolation is not enough¶

Suppose a curve $f_0$ interpolates distinct inputs, so that $f_0(x_i)=y_i$ . Let

q(x)=\prod_{i=1}^{n}(x−x_i).

(1)

For any constant $c$ , the curve $f_c(x)=f_0(x)+cq(x)$ gives exactly the same fitted values at the observations. Away from them, changing $c$ can change the curve arbitrarily. Zero training error therefore tells us very little about prediction.

With distinct inputs, a polynomial of degree at most $n−1$ can interpolate all $n$ observations. That is an existence result, not a reason to use such a polynomial as an estimate of a noisy conditional mean.

A norm for functions¶

A Hilbert space $\mathcal H$ is an inner product space that is complete: limits of sequences that should converge remain in the space. Its inner product defines a norm through $\lVert f\rVert_{\mathcal H}^2=\langle f,f\rangle_{\mathcal H}$ .

The evaluation map $L_x(f)=f(x)$ is linear. In a reproducing kernel Hilbert space, this map is also bounded: for each $x$ , there is a finite $C_x$ such that

|f(x)|\leq C_x\lVert f\rVert_{\mathcal H}.

(2)

The Riesz representation theorem then gives a function $K_x=K(\cdot,x)$ satisfying

f(x)=\langle f,K_x\rangle_{\mathcal H}.

(3)

This is the reproducing property. It turns evaluation at a point into an inner product, which allows us to use projection geometry in a space of functions.

A reproducing kernel is symmetric and positive semidefinite. For any chosen inputs, the matrix $K$ with entries $K_{ij}=K(x_i,x_j)$ satisfies $a^\top Ka\geq0$ . The same letter denotes the kernel and its matrix; the arguments distinguish them.

Why the solution uses only n kernel functions¶

Let $\mathcal V$ be the span of $K(\cdot,x_1),\ldots,K(\cdot,x_n)$ . Any $f\in\mathcal H$ decomposes as $f=g+h$ , with $g\in\mathcal V$ and $h$ orthogonal to $\mathcal V$ .

At every observed input,

h(x_i)=\langle h,K(\cdot,x_i)\rangle_{\mathcal H}=0.

(4)

Thus $f$ and $g$ have the same training residuals. Meanwhile,

\lVert f\rVert_{\mathcal H}^2=\lVert g\rVert_{\mathcal H}^2+\lVert h\rVert_{\mathcal H}^2.

(5)

The component $h$ adds a penalty without improving fit. A minimizer of squared error plus a positive norm penalty must therefore have $h=0$ :

\widehat f(x)=\sum_{i=1}^{n}a_iK(x,x_i).

(6)

The original search space may be infinite dimensional, but the solution lies in a span generated by the observations.

Minimum norm interpolation¶

For $g=\sum_i a_iK(\cdot,x_i)$ , its observed values are $Ka$ and its squared norm is $a^\top Ka$ . Exact interpolation requires $Ka=y$ .

The problem is feasible precisely when $y$ belongs to the range of $K$ . If $K$ is invertible, $a=K^{−1}y$ . If it is singular, coefficients need not be unique, but all solutions to $Ka=y$ represent the same minimum norm function. A coefficient difference $v$ in the nullspace has $v^\top Kv=0$ and represents the zero function.

Kernel ridge regression¶

Instead of requiring interpolation, minimize

\sum_i\{y_i−f(x_i)\}^2+\lambda\lVert f\rVert_{\mathcal H}^2,\qquad\lambda>0.

(7)

In kernel coordinates, the objective is $\lVert y−Ka\rVert^2+\lambda a^\top Ka$ . A valid coefficient choice, even when $K$ is singular, is

a=(K+\lambda I)^{−1}y,\qquad\widehat y=K(K+\lambda I)^{−1}y.

(8)

The function minimizer is unique. With a singular kernel matrix, its coefficient representation can still be nonunique. Do not cancel $K$ in the normal equations unless it is invertible.

For the linear kernel $K(x,z)=x^\top z$ , this recovers ridge predictions from a linear feature space. Changing the kernel changes which functions are available and what their norm measures.

A kernel based on curvature¶

The lecture constructs a space on $[0,1]$ with $f(0)=f'(0)=0$ and square integrable second derivative. With the appropriate absolute continuity conditions, use

\langle f,g\rangle=\int_0^1 f''(u)g''(u)\,du.

(9)

The boundary conditions make this a genuine norm: a linear function satisfying both conditions is zero. A reproducing kernel is

K(x,z)=\int_0^1(x−u)_+(z−u)_+\,du,

(10)

where $(v)_+=\max(v,0)$ . Taylor’s integral formula gives

f(x)=\int_0^1 f''(u)(x−u)_+\,du=\langle f,K(\cdot,x)\rangle.

(11)

The practical spline model later allows a free intercept and slope. There, curvature is a seminorm because every linear function has zero curvature. Those unpenalized terms must be retained separately; imposing zero boundary values would change the model.