Course: Machine Learning

Module 2: Linear Models for Regression and Classification

This module focuses on linear models, which form the backbone of many classical and modern machine learning systems. Despite their apparent simplicity, linear models provide a powerful, interpretable, and computationally efficient framework for regression and classification.

Page 1 – Linear Regression: Problem Formulation and Geometry

1.1 Motivation for Linear Models

Linear models are often the first family of models introduced in machine learning and statistics. They are widely used because they:

Are computationally efficient to train, even on large datasets.
Provide coefficients that are interpretable as feature effects.
Serve as strong baselines for more complex models.
Offer well-understood theoretical properties.

In many real-world settings, a linear approximation to the relationship between predictors and response is sufficient to yield useful and actionable predictions.

1.2 Linear Regression Model

Consider a regression problem with input features x ∈ ℝ^d and target y ∈ ℝ. A linear regression model assumes that the conditional mean of y given x is a linear function:

ŷ = h_w,b(x) = wᵀx + b

where:

w ∈ ℝ^d is the weight vector.
b ∈ ℝ is the bias (intercept) term.
ŷ is the model prediction.

For a dataset of n observations, we collect features into a design matrix X ∈ ℝ^n×d and targets into a vector y ∈ ℝⁿ. The vector of predictions can be written compactly as:

ŷ = Xw + b1

where 1 denotes an n-dimensional vector of ones. In practice, one often augments the feature vector with a constant 1 and absorbs b into the weight vector.

1.3 Least Squares Objective

The most common objective for fitting linear regression models is the ordinary least squares (OLS) criterion. The loss function is defined as:

L(w, b) = (1/2n) Σ_i=1ⁿ (y_i − (wᵀx_i + b))²

The factor 1/2 is included for algebraic convenience when computing gradients. The goal is to find parameters (w, b) that minimise this loss, yielding the best-fitting linear function in the least-squares sense.

1.4 Geometric Interpretation

From a geometric viewpoint, each example contributes a constraint in the d-dimensional feature space. The linear model seeks a hyperplane that best approximates the target values.

If we augment the feature vectors to incorporate the bias term, the OLS solution can be interpreted as projecting the target vector y onto the column space of the design matrix X. The fitted values ŷ lie in this column space, and the residual vector r = y − ŷ is orthogonal to it.

1.5 Closed-Form Solution

When the columns of X are linearly independent and n ≥ d, the OLS solution for w (ignoring the intercept for simplicity) has the closed form:

w* = (XᵀX)⁻¹ Xᵀy

This solution arises by setting the gradient of the loss with respect to w to zero and solving the resulting normal equations.

In large-scale settings or in the presence of many features, explicit inversion is avoided and iterative methods (e.g., gradient descent, conjugate gradients) are preferred.

Page 2 – Regularisation: Ridge, Lasso, and Bias–Variance

2.1 Motivation for Regularisation

While OLS provides an unbiased estimator under idealised assumptions, it can perform poorly in practice when:

The number of features d is large relative to n.
Features are highly correlated (multicollinearity).
We care about generalisation performance rather than in-sample fit.

In such situations, the OLS solution may have high variance, leading to overfitting. Regularisation techniques address this by adding a penalty on the magnitude of the weights, effectively shrinking the coefficients and improving generalisation.

2.2 Ridge Regression (L2 Regularisation)

Ridge regression adds an L2 penalty to the loss function:

L(w, b) = (1/2n) Σ (y_i − (wᵀx_i + b))² + (λ/2) ||w||²₂

where λ ≥ 0 is the regularisation strength.

Key properties:

Penalises large coefficients, making the solution more stable.
Closed-form solution: w* = (XᵀX + λI)⁻¹Xᵀy.
Does not perform feature selection; coefficients are shrunk but rarely exactly zero.

Ridge regression is particularly useful when all predictors are believed to be relevant, but multicollinearity or high dimensionality is an issue.

2.3 Lasso Regression (L1 Regularisation)

Lasso regression uses an L1 penalty:

L(w, b) = (1/2n) Σ (y_i − (wᵀx_i + b))² + λ ||w||₁

where ||w||₁ = Σ |w_j|.

Key properties:

Encourages sparsity in the coefficients (many coefficients become exactly zero).
Performs implicit feature selection.
Does not have a simple closed-form solution; solved via convex optimisation algorithms (e.g., coordinate descent).

Lasso is useful when we suspect only a subset of features are truly informative and wish to obtain a more parsimonious, interpretable model.

2.4 Elastic Net

Elastic Net combines L1 and L2 penalties:

L(w, b) = (1/2n) Σ (y_i − (wᵀx_i + b))² + λ₁ ||w||₁ + (λ₂/2) ||w||²₂

This approach aims to gain the benefits of both ridge and lasso:

Handles correlated features better than lasso alone.
Still encourages sparsity through the L1 component.
Introduces a flexible trade-off between shrinkage and selection.

2.5 Bias–Variance Perspective

Regularisation increases bias but reduces variance. The total expected prediction error can be decomposed as:

Error = Bias² + Variance + Irreducible noise

By penalising model complexity, we accept a small increase in bias in exchange for a potentially large reduction in variance. In many practical settings, this leads to better generalisation performance.

2.6 Choosing the Regularisation Strength

The hyperparameters λ, λ₁, and λ₂ are typically chosen using:

k-fold cross-validation.
Validation set performance.
Information criteria (AIC, BIC) in some statistical workflows.

A practical approach is to search over a grid of values on a logarithmic scale (e.g., 10⁻⁴ to 10²) and select the value that minimises validation error.

Page 3 – Logistic Regression: Linear Models for Classification

3.1 From Regression to Classification

Linear regression is not appropriate for classification problems where the output is a class label (e.g., 0 or 1). We require a model that:

Outputs probabilities in the range [0, 1].
Handles discrete labels in a principled way.

Logistic regression addresses this by applying a sigmoid (logistic) transformation to a linear function of the input.

3.2 Logistic Regression Model

For binary classification with labels y ∈ {0, 1}, logistic regression models the conditional probability:

P(y = 1 | x) = σ(wᵀx + b)

where σ(z) is the logistic sigmoid function:

σ(z) = 1 / (1 + e^−z)

The model output is interpreted as the estimated probability that the instance belongs to the positive class. A typical decision rule is:

Predict ŷ = 1 if P(y = 1 | x) ≥ 0.5, else ŷ = 0

3.3 Loss Function: Cross-Entropy

Rather than mean squared error, logistic regression uses the cross-entropy loss, equivalent to the negative log-likelihood under a Bernoulli model:

L(w, b) = −(1/n) Σ [ y_i log(p_i) + (1 − y_i) log(1 − p_i) ]

where p_i = σ(wᵀx_i + b). This loss is convex in w and b, allowing efficient optimisation via gradient-based methods.

3.4 Regularised Logistic Regression

Similar to linear regression, logistic regression can be regularised using L1 or L2 penalties:

L(w, b) = CrossEntropy(w, b) + λ ||w||²₂  (Ridge-style)
L(w, b) = CrossEntropy(w, b) + λ ||w||₁   (Lasso-style)

Regularisation helps prevent overfitting, especially when the number of features is large or when features are correlated.

3.5 Decision Boundary and Geometry

Logistic regression defines a linear decision boundary in the feature space. Specifically, the set of points where P(y = 1 | x) = 0.5 corresponds to:

wᵀx + b = 0

This is a hyperplane separating the feature space into regions associated with the two classes. Although the decision boundary is linear in the input features, non-linear boundaries can be obtained by applying non-linear feature transformations (e.g., polynomial features, kernels).

3.6 Multiclass Logistic Regression

For multiclass problems with K classes, logistic regression can be extended via:

One-vs-rest (OVR): train K binary classifiers.
Softmax regression (multinomial logistic regression).

In softmax regression, we model:

P(y = k | x) = exp(w_kᵀx + b_k) / Σ_j=1^K exp(w_jᵀx + b_j)

with a corresponding cross-entropy loss over classes. This yields a linear classifier with K sets of weights and biases, one per class.

Page 4 – Feature Engineering and Basis Expansions

4.1 Limitations of Purely Linear Models

A purely linear model assumes that the target variable depends on the input features through a linear combination. Many real-world relationships are inherently non-linear. Despite this, linear models can still be powerful when combined with appropriate feature transformations.

4.2 Feature Engineering

Feature engineering refers to the process of constructing new input features from raw data to better capture the underlying structure. Examples include:

Polynomial features (e.g., x₁², x₁x₂).
Domain-specific transformations (logarithms, ratios, differences).
Temporal features (lags, moving averages, trends).
Interaction terms between variables.

Once transformed, these new features can be fed into a linear model, enabling it to approximate non-linear relationships.

4.3 Basis Functions

Basis expansions generalise feature engineering. Let φ(x) = [φ₁(x), φ₂(x), …, φ_M(x)]ᵀ denote a vector of basis functions applied to the input. The model becomes:

ŷ = wᵀ φ(x)

Examples of basis functions include:

Polynomial basis functions.
Radial basis functions (RBFs).
Splines and piecewise linear functions.

These expansions allow linear models in the transformed space to represent complex, non-linear relationships in the original input space.

4.4 Kernel Trick (Conceptual Introduction)

Explicitly computing basis expansions can be computationally expensive if the number of features or basis functions is large. The kernel trick, used in support vector machines and other kernel methods, allows implicit operation in a high-dimensional feature space without computing the features directly.

Although logistic and linear regression do not typically use kernels in their basic form, the conceptual idea is important: we can retain a linear model in a transformed space where the data become more easily separable.

4.5 Practical Considerations

When constructing new features, we must be cautious about:

Overfitting due to an excessive number of features.
Multicollinearity introduced by correlated transformations.
Scaling and normalisation requirements for gradient-based optimisation.

Regularisation becomes even more critical as we increase the dimensionality of the feature space through basis expansions.

Page 5 – Training Linear Models: Workflow, Evaluation, and Practice

5.1 Data Preparation for Linear Models

Before fitting linear or logistic regression models, it is important to perform appropriate data preprocessing:

Handling missing values via imputation or deletion.
Encoding categorical variables with one-hot (dummy) encoding.
Feature scaling (standardisation or normalisation) to stabilise optimisation.
Outlier handling when extreme values strongly influence the fit.

In particular, regularised models (ridge, lasso) are sensitive to feature scaling; standardising features to zero mean and unit variance is typically recommended.

5.2 Training with Gradient Descent

Although closed-form solutions exist for OLS and ridge regression, many practical implementations use iterative optimisation algorithms such as gradient descent or stochastic gradient descent (SGD), especially when:

n and/or d are very large.
Regularisation or constraints complicate closed-form solutions.
Data are streamed or distributed across machines.

The basic SGD update for a single training example (x_i, y_i) in linear regression is:

w ← w − η ∇_w ℓ(w; x_i, y_i)

where ℓ is the per-example loss and η is the learning rate. Mini-batch variants update parameters using small subsets of data at each iteration, improving stability and computational efficiency.

5.3 Model Selection and Hyperparameter Tuning

Linear models have comparatively few hyperparameters, but regularisation introduces at least one key parameter (λ). A typical model selection procedure comprises:

Split data into training, validation, and test sets.
Train models with different λ values on the training set.
Evaluate each model on the validation set using appropriate metrics.
Select the model with the best validation performance.
Report final performance on the test set.

k-fold cross-validation provides a more robust estimate of performance when data are limited.

5.4 Evaluation Metrics for Regression and Classification

For regression using linear or regularised regression, common metrics include:

Mean Squared Error (MSE) and Root Mean Squared Error (RMSE).
Mean Absolute Error (MAE).
R² (coefficient of determination).

For classification using logistic regression:

Accuracy (for balanced datasets).
Precision, Recall, and F1-score (for imbalanced data).
ROC–AUC and Precision–Recall AUC.
Calibration plots to assess probability estimates.

In high-stakes domains (e.g., healthcare, finance), we often prioritise recall or precision for particular classes rather than overall accuracy.

5.5 Interpretability of Linear Models

One of the primary advantages of linear models is interpretability. Under appropriate scaling, each coefficient w_j can be interpreted as the change in the predicted output associated with a one-unit change in feature x_j, holding other features constant.

For logistic regression, coefficients correspond to log-odds:

log( P(y=1|x) / P(y=0|x) ) = wᵀx + b

Thus, exp(w_j) can be interpreted as the multiplicative change in odds associated with a one-unit increase in feature x_j.

5.6 Summary and Transition to Subsequent Modules

In this module, we have:

Formulated linear regression and its least-squares solution.
Introduced regularisation via ridge, lasso, and elastic net.
Developed logistic regression for binary and multiclass classification.
Discussed feature engineering and basis expansions to address non-linearity.
Outlined practical workflows for training, tuning, and evaluating linear models.

Linear models form a conceptual and practical foundation for many advanced techniques. Subsequent modules can build on this material to explore tree-based models and ensemble learning, and later neural networks and deep learning, which generalise the idea of learning from data using more flexible function classes.