09 Linear Regression

Fundamentals of Regression

Regression is a supervised learning task where the goal is to predict a continuous numerical value (e.g., a credit line amount) based on input features. This differs from classification, which predicts discrete categories (e.g., “good” or “bad” customer).

The Linear Assumption

Linear regression assumes a functional relationship between the predictor variables $(x)$ and the target variable $(y)$. The standard model is expressed as

$$y=f(x,w)+ϵ$$

where $w$ represents the learned weights and $ϵ$ represents the error on noise:

Tip

Even if the relationship between $x$ and $y$ looks curved (non-linear) we still call it “linear regression” as long as the model is linear in its parameters $(w)$.

Ordinary Least Squares (OLS)

The objective of OLS is to find the optimal weights $(w)$ by minimising the Residual Sum of Squares (RSS).

Step-by-Step Derivation

1. Define the Residual $(r_1)$: The error for a single data point.

$$r_i=y_i-\widehat{y_i}=y_i-({\omega }_0+{\omega }_1{x}_i)$$

2. Define the Cost Function $(R(w))$: The sum of all squared residuals.

$$R(w)=\sum _{i=1}^N{r}_i^2=\sum _{i=1}^N(y_i-\widehat{y_i}(x_i,w){)}^2$$

3. Minimise: Take the partial derivatives of $R$ with respect to each weight and set them to zero.

$$\frac{\partial R(w_0,w_1)}{\partial w_0}=0,\frac{\partial R(w_0,w_1)}{\partial w_1}=0$$

4. Solve the System: This leads to a set of linear equations known as the Normal Equations*.

The Matrix Solution

For more complex models, we use the Design Matrix ($\Phi$). The closed-form OLS solution is:

$${\omega }_{OLS}=({\Phi }^T\Phi {)}^{-1}{\Phi }^{T}y$$

The term $({\Phi }^T\Phi {)}^{-1}{\Phi }^T$ is known as the Moore-Penrose pseudo-inverse (${\Phi }^{†}$)

Warning

Directly computing the matrix inversion $({\Phi }^T\Phi {)}^{-1}$ can be numerically unstable or computationally expensive if the matrix is very large. In these cases, Singular Value Decomposition (SVD) is often used.

Basis Functions

To model non-linear patterns, we can transform the input $x$ using a basis function $\varphi (x)$. The model remains linear because the weights $w$ are applied linearly to these transformed features.

Common Basis Functions

• Polynomial: ${\varphi }_j(x)=x^j$ (e.g., $1,x,x^2,x^3$).
• Gaussian (RBF): ${\varphi }_j(x)=\exp \left(-\frac{1}{2{\sigma }^2}(x-{\mu }_j{)}^2\right)$.
• Sigmoidal: $g(\alpha )=\frac{1}{1+e^{-\alpha }}$.
• Hyperbolic Tangent: $h(\alpha )=\tanh (\alpha )$.

Optimisation via Gradient Descent

When the closed-form solution is not feasible, we use Gradient Descent.

The Intuition

Imagine standing on a hill and wanting to reach the bottom. You look at the slope at your current position and take a step in the direction that goes down the fastest.

The Process

1. Initialize weights $w$ randomly.
2. Calculate the in-sample error $E_{in}(w)=\frac{1}{N}\Vert Xw-y{\Vert }^2$.
3. Update weights iteratively by moving in the opposite direction of the gradient.
4. The size of the movement is determined by the step size (learning rate).

Important

Choosing the correct Step Size is critical.

• If the step size is too small, convergence will be slow.
• If the step size is too large, the algorithm may diverge, jumping over the minimum and heading towards infinity.