non-linear-transformation

A pre-processing map $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^D$ (often with $D>d$) that turns the inputs into a higher-dimensional feature space. A linear model run on $\varphi (\mathbf{x})$ can produce a non-linear decision boundary in the original space, while keeping its optimisation machinery and convexity properties unchanged.

The Trick

Many classification problems aren’t linearly separable. A single hyperplane in the original input space cannot capture circles, XOR-like patterns, or polynomial boundaries.

The fix is to send each input $\mathbf{x}$ through a non-linear map $\varphi$ — also called a basis expansion or feature transform — and apply a linear model in the resulting space:

$\mathbf{x}\in {\mathbb{R}}^d⟶\varphi (\mathbf{x})\in {\mathbb{R}}^D$

In the new space, the model is still a linear function:

$h(\mathbf{x})={\mathbf{w}}^{\top }\varphi (\mathbf{x})$

But $h$, viewed as a function of the original $\mathbf{x}$, is non-linear. A line in $\varphi$-space can correspond to a curve, a circle, a polynomial, anything determined by $\varphi$.

The key reframing: what looks like a linear model in $\varphi$-space is a highly non-linear model when viewed back in the original input space. The non-linearity is hidden inside the pre-processing step $\varphi$, leaving the model itself — and all its convexity-based optimisation guarantees — perfectly linear.

Toy Example

Data on $\mathbb{R}$: blue points at $x_1\in \{-3,-2,4,5\}$, orange at $x_1\in \{0,1\}$. No linear function $w_0+w_1{x}_1$ can separate them — a line on $\mathbb{R}$ has at most one zero crossing.

Apply $\varphi (x_1)=(1,x_1,x_1^2{)}^{\top }$ and the points become $(1,-3,9),(1,-2,4),(1,0,0),(1,1,1),(1,4,16),(1,5,25)$ in ${\mathbb{R}}^3$.

A linear function $w_0+w_1{x}_1+w_2{x}_1^2$ can now separate them — for example, $w_0=10,w_1=-7,w_2=1$ gives $h(x_1)=x_1^2-7x_1+10=(x_1-2)(x_1-5)$, which is positive outside $[2,5]$ and negative inside. The decision boundary in the original 1-D space is the pair of points $x_1=2$ and $x_1=5$ — a non-linear “boundary” produced by a linear model in lifted space.

Polynomial Basis Expansion

For polynomial decision boundaries of degree $\le p$, include all monomials of total degree up to $p$:

Inputs	Degree	$\varphi (\mathbf{x})$
$x_1$	2	$(1,x_1,x_1^2)$
$x_1,x_2$	2	$(1,x_1,x_2,x_1^2,x_2^2,x_1{x}_2)$
$x_1,x_2$	3	$(1,x_1,x_2,x_1^2,x_2^2,x_1{x}_2,x_1^3,x_2^3,x_1{x}_2^2,x_1^2{x}_2)$

Cross terms like $x_1{x}_2$ are essential for capturing interactions — without them you can only express decision boundaries that are sums of single-variable functions.

The number of monomials of degree $\le p$ in $d$ variables is $\left(\genfrac{}{}{0ex}{}{d+p}{p}\right)$, growing roughly as $d^p$ for fixed $p$. With 100 features and $p=3$, $\varphi (\mathbf{x})$ has more than 170,000 components.

Other Bases

You’re not limited to polynomials. Useful non-polynomial expansions include:

• Exponential / logarithmic: $\varphi (\mathbf{x})=(1,x_1,e^{x_1},\ln (1+|x_1|))$ for data with multiplicative structure.
• Sinusoidal: $\varphi (\mathbf{x})=(1,x_1,\cos (x_1),\sin (x_1))$ for periodic data; the basis of Fourier methods.
• Indicator functions: $\varphi (\mathbf{x})$ has one component per region of input space; “one-hot” features for discrete cuts.
• Radial basis functions: ${\varphi }_i(\mathbf{x})=\exp (-\Vert \mathbf{x}-{\mathbf{c}}_i{\Vert }^2/2{\sigma }^2)$ centred on each training point or a chosen set of centres.

The choice encodes a guess about the shape of the truth. Polynomial expansions are popular because they’re simple and connect cleanly with Taylor approximation intuition: any sufficiently smooth function looks polynomial locally.

Linearity Is Preserved Where It Matters

Think of $\varphi$ as data pre-processing: from the optimisation algorithm’s point of view, the inputs are $\varphi ({\mathbf{x}}^{(i)})$ rather than ${\mathbf{x}}^{(i)}$, and that is the only change. Concretely, for logistic-regression with cross-entropy-loss:

$E(\mathbf{w})=-{\sum }_{i=1}^N\left[y^{(i)}\ln \sigma ({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}^{(i)}))+(1-y^{(i)})\ln (1-\sigma ({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}^{(i)})))\right]$

$\nabla E(\mathbf{w})={\sum }_{i=1}^N(p_1(\varphi ({\mathbf{x}}^{(i)}),\mathbf{w})-y^{(i)})\varphi ({\mathbf{x}}^{(i)})$

The loss is still strictly convex in $\mathbf{w}$. gradient descent and IRLS still find the global optimum. Nothing in the optimiser changes.

ASIDE — "Linear in $\mathbf{w}$" vs "linear in $\mathbf{x}$"

When we call logistic regression a “linear model,” we mean linear in the parameters $\mathbf{w}$, not linear in the inputs. After basis expansion, the model is still linear in $\mathbf{w}$ — only nonlinear in $\mathbf{x}$. This is the property that preserves the convex optimisation. If we had instead made the model non-linear in $\mathbf{w}$ (as in a neural network with multiple weight layers), we would lose convexity entirely.

Caveats

Two costs to weigh against the gained expressiveness:

• Dimensionality: $\varphi (\mathbf{x})$ may have far more components than $\mathbf{x}$, increasing memory, computation, and (especially) sample complexity. The number of training examples needed to fit a model reliably scales with the feature dimension.
• Overfitting: more flexible models can fit training noise. A degree-4 polynomial classifier can perfectly classify any reasonable training set while generalising worse than a linear classifier with a few mistakes. Capacity must be justified by evidence — the central concern of generalisation theory.

The Kernel Trick (Preview)

For algorithms whose optimisation depends on inputs only through inner products — notably SVMs in their dual form — there is a way to use $\varphi$ without ever computing it explicitly. A kernel function $k(\mathbf{x},{\mathbf{x}}^{\prime })=\varphi (\mathbf{x}{)}^{\top }\varphi ({\mathbf{x}}^{\prime })$ can sometimes be evaluated in $O(d)$ time even when $\varphi$ has thousands of components. This makes very high (even infinite) dimensional basis expansions practical. Covered in week 4.

Related

• support-vector-machine — combines basis expansion with maximum-margin classification
• logistic-regression — accepts basis expansion transparently
• generalization — high-dim $\varphi$ raises overfitting risk
• decision boundary — what becomes non-linear in the original space

Active Recall

Why does applying a basis expansion $\varphi$ to logistic regression not break the convexity of the loss?

The cross-entropy loss is convex as a function of $\mathbf{w}$, regardless of what the inputs are. After basis expansion, the loss is $E(\mathbf{w})=-{\sum }_i[y^{(i)}\ln \sigma ({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}^{(i)}))+\dots ]$, which is still convex in $\mathbf{w}$ — the new inputs $\varphi ({\mathbf{x}}^{(i)})$ are constants from the optimiser’s perspective. We’ve changed the inputs, not the function class of the loss in $\mathbf{w}$.

For two input variables $x_1,x_2$, write the basis expansion for polynomial decision boundaries up to degree 2. Why must the cross term $x_1{x}_2$ be included?

$\varphi (\mathbf{x})=(1,x_1,x_2,x_1^2,x_2^2,x_1{x}_2{)}^{\top }$. The cross term captures interactions between features. Without it, the model can only express boundaries that are sums of separate single-variable functions of $x_1$ and $x_2$ — for example, an axis-aligned ellipse $x_1^2+x_2^2=c$, but not a rotated one $(x_1-x_2{)}^2=c$, which expands to include $-2x_1{x}_2$. Generally, no rotation-non-invariant quadratic boundary can be expressed without the cross term.

A degree-4 polynomial basis expansion lets a linear classifier perfectly classify all training data, while a linear classifier without expansion misclassifies a few points. Which is likely to generalise better, and why?

Often the un-expanded linear classifier. Training accuracy is not the goal — generalisation is. The high-degree expansion gives the classifier enough capacity to memorise the training noise, drawing wildly contorted boundaries that fit specific training points but don’t reflect the underlying structure. With limited data, the simpler model whose mistakes are evenly distributed (suggesting irreducible noise rather than systematic structure it’s missing) often generalises better. Capacity must be matched to the evidence in the data — a tension formalised by VC dimension and bias-variance analysis.