Machine Learning
Topic 2 · ML foundations · ⏱ about 2 h

What is Machine Learning?

Learning patterns from data instead of hand-writing rules.

Show:
In this topic
Beginner

The big idea

In ordinary programming, a person writes down the rules and the computer follows them. To build a spam filter that way, you might write "if the email contains the word lottery and comes from an unknown sender, mark it as spam". The trouble is that real problems have far too many subtle patterns to write down by hand, and the patterns keep changing.

Traditional programmingrules+dataanswersMachine learningdata+answersrules = modelpredictnew cases
In ordinary programming people write the rules; in machine learning the rules are learned from examples with known answers.

Machine learning turns this around. Instead of writing the rules, we give the computer a large number of examples together with the correct answers (thousands of emails, each already labelled spam or not spam) and let it work out the rules for itself. The rules it discovers are stored in a model, which we can then apply to new emails it has never seen.

Traditional programming:rules+data  →  answers \text{Traditional programming:}\quad \text{rules} + \text{data} \;\rightarrow\; \text{answers}
Machine learning:data+answers  →  rules (a model) \text{Machine learning:}\quad \text{data} + \text{answers} \;\rightarrow\; \text{rules (a model)}

Tom Mitchell gave a definition in 1997 that is still widely quoted. A program is said to learn from experience EE, with respect to some task TT and performance measure PP, if its performance at TT, as measured by PP, improves with experience EE. The definition is useful because it forces you to state three things clearly. For the spam filter, the task TT is to label incoming emails as spam or not spam; the experience EE is the collection of labelled emails it is trained on; and the performance measure PP is the percentage of emails it labels correctly. If the filter gets more accurate as it sees more labelled emails, it is learning.

It is worth noticing what this definition does not say. It does not require the computer to understand anything in a human sense, and it does not require any particular algorithm. Everything in this course, from a straight-line fit to a large neural network, fits Mitchell's definition: each is a different way of turning experience into improved performance on a task.

Beginner

Three main types of learning

Machine learning problems are usually grouped into three families, depending on what kind of information is available while the model learns.

Supervisedlabelled examplesUnsupervisedfind structure, no labelsReinforcementlearn from rewardsagentenvironmentactionstate, reward
The three main types of machine learning.

In supervised learning, every training example comes with the correct answer, called its label. The model's job is to learn the relationship between inputs and labels well enough to predict the label of new inputs. If the label is a number, such as the price of a house, the problem is called regression. If the label is a category, such as "spam" or "not spam", or which digit appears in an image, the problem is called classification. Most of the algorithms in this course (linear and logistic regression, k-nearest neighbours, decision trees, support vector machines and most neural networks) are supervised.

In unsupervised learning, the examples have no labels at all, and the goal is to discover structure in the data by itself. A retailer might group its customers into segments with similar buying habits, without knowing in advance what those segments are; that is clustering. Or we might want to compress data with hundreds of features into a handful of informative ones; that is dimensionality reduction, and PCA is the classic method.

In reinforcement learning, there are no fixed examples at all. Instead, an agent takes actions in an environment and receives rewards or penalties, and it must learn which actions lead to the most reward over time. This is how computers have learned to play games such as Go at superhuman level, and it is also used in robotics.

A fourth idea, self-supervised learning, sits between the first two. The data have no human-provided labels, but we create labels automatically from the data itself. For example, we can hide the next word of a sentence and train the model to predict it; the "label" is simply the word that really came next. Because no human labelling is needed, this can be done on enormous amounts of text, and it is how large language models are pre-trained.

Interactive: this part runs in your browser.

Interactive. The same kind of picture viewed as each type of learning. Click through the four.
TypeWhat you haveGoalExample
Supervisedinputs with labelspredict labels for new inputshouse prices, spam detection
Unsupervisedinputs without labelsfind structurecustomer segments, PCA
Reinforcementan environment and rewardslearn good actionsgame-playing agents
Beginner

Key vocabulary

A handful of words come up in every machine learning discussion, so it is worth fixing their meanings now.

A feature is one input variable that describes an example, such as the floor area of a house. Features are usually written xx, and an example with several features is a vector x=[x1,x2,… ]x = [x_1, x_2, \dots]. The label or target, written yy, is the quantity we want to predict, such as the price of the house.

A model is a function that maps features to a prediction, y^=f(x)\hat y = f(x). Its behaviour is controlled by parameters, also called weights, which are the numbers the learning algorithm adjusts. In the straight line y^=wx+b\hat y = wx + b, the slope ww and intercept bb are the parameters. Hyperparameters are different: they are settings that you choose before training begins and that the algorithm does not learn by itself, such as the learning rate of gradient descent, the maximum depth of a decision tree, or the number of neighbours in k-NN. Choosing good hyperparameters is a large part of practical machine learning.

A loss function measures how wrong the model's predictions are on the training data, for example the average squared difference between predictions and true values. Training means searching for the parameter values that make the loss as small as possible.

Because a model can always do well on data it has already memorised, we judge it on data it has not seen. We therefore split the available data into a training set, used to learn the parameters; a validation set, used to compare models and choose hyperparameters; and a test set, kept locked away until the very end and used once to report an honest estimate of performance.

All of this serves a single goal, generalisation: performing well on new data drawn from the same source as the training data. A model that does brilliantly on its training data but poorly on new data has learned the noise rather than the pattern, and it is of little practical use.

Intermediate · Maths

Learning as empirical risk minimisation

📐 Maths you'll need: m-notation · m-prob
💡 The idea in plain words

We can't test a model on every possible future example, only on the examples we have. So we pick the model that does best on our data (minimise the training error) and hope it also does well on new data (the true error). The whole of ML theory is about when that hope is justified.

🔤 Symbols in this section
P(x,y)P(x,y)the unknown process that generates data
H\mathcal Hhypothesis class: the set of models we allow
ℓ(y^,y)\ell(\hat y, y)loss for one prediction
R(f)R(f)true risk: expected loss on new data
R^n(f)\hat R_n(f)empirical risk: average loss on our n training examples
E\mathbb Eexpectation (average over the distribution)

This section gives the precise mathematical framework behind "learning from data". The framework is simple, but once you see it, you will recognise it inside almost every algorithm in the course.

We imagine that the data are generated by some process in the world, described by an unknown probability distribution P(x,y)P(x, y) over inputs and labels. Each training example (xi,yi)(x_i, y_i) is drawn independently from this distribution. We also choose a hypothesis class H\mathcal H, the set of models we are willing to consider (for example, all straight lines), and a loss function ℓ(y^,y)\ell(\hat y, y) that says how bad it is to predict y^\hat y when the truth is yy.

What we really want is a model with small error on future data. This is called the true risk (or expected loss):

R(f)=E(x,y)∼P[ℓ(f(x),y)]. R(f) = \mathbb E_{(x,y)\sim P}\big[\ell(f(x), y)\big].

The symbol E\mathbb E means "the average over all possible examples, weighted by how likely they are". The difficulty is that we can't compute this, because we don't know PP. What we can compute is the average loss on the training examples we actually have, called the empirical risk:

R^n(f)=1n∑i=1nℓ(f(xi),yi). \hat R_n(f) = \frac{1}{n}\sum_{i=1}^{n} \ell(f(x_i), y_i).

The natural strategy is to use the empirical risk as a stand-in for the true risk and choose the model that minimises it. This strategy is called empirical risk minimisation (ERM), and it is written f^=arg⁡min⁡f∈HR^n(f)\hat f = \arg\min_{f\in\mathcal H}\hat R_n(f). In practice we usually add a penalty λ Ω(f)\lambda\,\Omega(f) that discourages overly complicated models; this is regularisation, and it has its own topic later.

Seen through this lens, most of the algorithms in the course differ only in three choices: which hypothesis class they use, which loss they minimise, and which optimisation method they use to do the minimising.

ModelHypothesis classLossOptimiser
Linear regressionw⊤x+bw^\top x + b(y−y^)2(y-\hat y)^2closed form or gradient descent
Logistic regressionσ(w⊤x+b)\sigma(w^\top x + b)cross-entropygradient descent or Newton
Support vector machinew⊤ϕ(x)+bw^\top \phi(x) + bhinge max⁡(0,1−yy^)\max(0, 1 - y\hat y)quadratic programming
Neural networkcompositions of layersany differentiable lossstochastic gradient descent / Adam

The difference between the true risk and the empirical risk of the chosen model, R(f^)−R^n(f^)R(\hat f) - \hat R_n(\hat f), is called the generalisation gap. A model that overfits is one where this gap is large: it looks excellent on the training data and disappoints on new data. Much of the rest of the course is about understanding and controlling this gap.

Key takeaway. Almost every ML algorithm = choose a family of models + a loss + an optimiser, then minimise the average training loss (often plus a penalty).
Advanced

The probabilistic view: MLE, MAP and generalisation bounds

📐 Maths you'll need: m-stats · m-prob
💡 The idea in plain words

Two big ideas. (1) Loss functions aren't arbitrary: if you assume a probability model for your labels, "make the observed data as likely as possible" automatically gives you squared error or cross-entropy, and adding a prior belief gives you regularisation. (2) A model that fits training data well will also do well on new data if you have enough data relative to how flexible the model is.

🔤 Symbols in this section
θ\thetamodel parameters
p(y∣x,θ)p(y\mid x,\theta)probability of label y given input x under parameters θ
θ^MLE\hat\theta_{\text{MLE}}maximum likelihood estimate
θ^MAP\hat\theta_{\text{MAP}}maximum a posteriori estimate (likelihood × prior)
δ\deltaallowed failure probability in a bound
∣H∣|\mathcal H|number of models in the class

The previous section treated the loss function as something we simply choose. This section shows that the most common losses actually follow from a probabilistic model of the data, and then explains why minimising training loss can be expected to work on new data at all.

Suppose our model defines the probability of a label given an input and parameters θ\theta, written p(y∣x,θ)p(y\mid x,\theta). A natural way to choose θ\theta is to make the observed labels as probable as possible. This is maximum likelihood estimation. Because the examples are independent, the probability of all the labels is a product, and taking logarithms turns it into a sum:

θ^MLE=arg⁡max⁡θ∏ip(yi∣xi,θ)=arg⁡min⁡θ  −∑ilog⁡p(yi∣xi,θ). \hat\theta_{\text{MLE}} = \arg\max_\theta \prod_{i} p(y_i \mid x_i, \theta) = \arg\min_\theta \; -\sum_i \log p(y_i\mid x_i,\theta).

The quantity being minimised on the right is the negative log-likelihood, and it plays the role of the loss function. Two choices of probability model give the two most common losses. If we assume the label equals the model's prediction plus Gaussian noise, y=fθ(x)+εy = f_\theta(x) + \varepsilon with ε∼N(0,σ2)\varepsilon\sim\mathcal N(0,\sigma^2), then −log⁡p-\log p equals 12σ2(y−fθ(x))2\frac{1}{2\sigma^2}(y - f_\theta(x))^2 plus a constant, so maximum likelihood is exactly least squares. If instead the label is a yes/no outcome whose probability is p=σ(fθ(x))p = \sigma(f_\theta(x)), then −log⁡p-\log p is exactly the cross-entropy loss −[ylog⁡p+(1−y)log⁡(1−p)]-[y\log p + (1-y)\log(1-p)]. (The likelihood topic works through both derivations step by step.)

We can also include prior beliefs about the parameters, which gives maximum a posteriori (MAP) estimation: θ^MAP=arg⁡min⁡θ [−∑ilog⁡p(yi∣xi,θ)−log⁡p(θ)]\hat\theta_{\text{MAP}} = \arg\min_\theta\,\big[-\sum_i\log p(y_i\mid x_i,\theta) - \log p(\theta)\big]. If our prior belief is that the weights are probably small, expressed as a Gaussian prior θ∼N(0,τ2I)\theta\sim\mathcal N(0,\tau^2 I), then −log⁡p(θ)-\log p(\theta) contributes the term 12τ2∥θ∥2\frac{1}{2\tau^2}\lVert\theta\rVert^2. That is precisely L2 regularisation. So regularisation is not an arbitrary trick: it is what you get when you combine the data with a sensible prior belief.

Now the second question: why should a model that does well on training data do well on new data? Consider the simplest case, a finite hypothesis class H\mathcal H and a loss between 0 and 1. For any single fixed model, the training error is an average of independent random quantities, and a result called Hoeffding's inequality says that such an average is unlikely to stray far from its expected value, the true error. Because we pick the best model from H\mathcal H, we need this to hold for all models at once, which we can guarantee by adding up the failure probabilities (the "union bound"). The result is that, with probability at least 1−δ1 - \delta, every model in the class satisfies

R(f)  ≤  R^n(f)+ln⁡∣H∣+ln⁡(1/δ)2n. R(f) \;\le\; \hat R_n(f) + \sqrt{\frac{\ln|\mathcal H| + \ln(1/\delta)}{2n}} .

Read this as: true error ≤ training error + a gap term. The gap shrinks like 1/n1/\sqrt n as you collect more data, and it grows (slowly, through the logarithm) with the number of models you were choosing between. In other words, a more flexible model class needs more data to generalise reliably. For infinite classes, such as all straight lines, ln⁡∣H∣\ln|\mathcal H| is replaced by more refined measures of flexibility such as the VC dimension, but the message is the same.

Finally, the No Free Lunch theorem states that, averaged over all conceivable problems, no learning algorithm is better than any other. Every algorithm works well only because it makes assumptions that suit the problems we actually meet, such as "similar inputs have similar outputs" or "the relationship is roughly linear". These built-in assumptions are called the algorithm's inductive bias, and choosing a model is really choosing which assumptions to make.

Key takeaway. MSE = Gaussian likelihood, cross-entropy = Bernoulli likelihood, L2 penalty = Gaussian prior; and the generalisation gap shrinks like 1/√n but grows with model capacity.
Code

Code: the standard scikit-learn workflow

Every supervised project follows the same skeleton: split → build a pipeline → fit → evaluate. This runs as-is with scikit-learn.

Python · scikit-learn
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import classification_report

# 1. Data: 569 tumours, 30 numeric features, label 0 = malignant, 1 = benign
X, y = load_breast_cancer(return_X_y=True)

# 2. Hold out a test set (stratified keeps the class ratio)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42)

# 3. Pipeline: preprocessing + model are fitted together on TRAIN only
model = make_pipeline(StandardScaler(), LogisticRegression(C=1.0, max_iter=1000))
model.fit(X_train, y_train)

# 4. Evaluate on data the model has never seen
print("train accuracy:", model.score(X_train, y_train))
print("test accuracy: ", model.score(X_test, y_test))
print(classification_report(y_test, model.predict(X_test)))
Open in playground ↗
Check yourself

Quiz

1. Predicting tomorrow's temperature in °C is…

2. Grouping customers with no labels is…

3. Which of these is a hyperparameter?

4. Least-squares regression is the maximum-likelihood estimate when the noise is…

5. A Gaussian prior on the weights in MAP estimation is equivalent to…

6. In the finite-class generalisation bound, the gap shrinks with n like…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready