Types of machine learning: supervised, unsupervised, semi-supervised and more

Let a computer program be given, together with these three objects:

1. T — a class of tasks the program is to solve (e.g. “decide whether an e-mail is spam”);
2. P — a performance measure: a rule that assigns a number to the program’s results on tasks from T, where a larger number means better performance (e.g. the fraction of e-mails sorted correctly);
3. E — experience: the data or interactions the program receives while learning (e.g. e-mails that someone has already sorted).

The program learns from experience E with respect to the class of tasks T and the performance measure P if and only if its performance on tasks from T, as measured by P, improves with experience E — i.e. a program that has processed more experience from E achieves (on average) a higher value of P on T.

This is a conceptual definition, not a mathematical one: T, P and E still have to be chosen for each concrete task. The formal version for supervised learning is in the next part.

Let 𝒳 be a non-empty set (the input space), 𝒴 a non-empty set (the output space) and p ∈ ℕ, p ≥ 1. A model with parameters θ ∈ ℝ^p is a family of functions

f_θ : 𝒳 → 𝒴,   x ↦ f_θ(x),   θ ∈ ℝ^p,

i.e. every choice of the vector θ determines one function from inputs to outputs.

Let J : ℝ^p → ℝ be an objective function computed from data (the smaller J(θ), the better the model with parameters θ describes the data). Learning (training) is the search for parameters

θ* ∈ argmin_{θ ∈ ℝ^p} J(θ) = {θ ∈ ℝ^p : J(θ) ≤ J(θ′) for all θ′ ∈ ℝ^p}.

If J is differentiable, the search typically uses gradient descent: choose an initial θ₀ ∈ ℝ^p and a learning rate η > 0, and for t = 0, 1, 2, … set

θ_t+1 = θ_t − η ∇J(θ_t),

as long as J keeps decreasing noticeably (or for a fixed number of steps). In general, gradient descent finds only a local minimum, not necessarily an element of the argmin.

Let 𝒳 be the input space, 𝒴 the space of labels (correct answers) and P an unknown probability distribution of pairs (X, Y) on 𝒳 × 𝒴. Further, let

1. n ∈ ℕ, n ≥ 1, and let the training set D = ((x_i, y_i))_i=1ⁿ be a sequence of pairs (x_i, y_i) ∈ 𝒳 × 𝒴 drawn from P independently of each other;
2. {f_θ : 𝒳 → 𝒴 : θ ∈ ℝ^p} be a model (see the definition above);
3. L : 𝒴 × 𝒴 → [0, ∞) be a loss function — L(ŷ, y) is the penalty for the answer ŷ when the correct answer is y.

Supervised learning is the search for parameters that minimise the empirical risk R̂ : ℝ^p → [0, ∞):

R̂(θ) = 1/n ∑_i=1ⁿ L(f_θ(x_i), y_i),   θ* ∈ argmin_{θ ∈ ℝ^p} R̂(θ).

The goal, however, is not the training set — the model should have a small true risk R(θ) = E_{(X, Y) ∼ P}[L(f_θ(X), Y)], i.e. work well on new data from the same distribution (generalisation). We do not know R, so it is estimated by the average loss on a held-out test set that was not used for learning.

Classification is supervised learning in which the label space is a finite set of classes 𝒴 = {1, …, K}, K ∈ ℕ, K ≥ 2. For an input x ∈ 𝒳 the model returns an estimate of the distribution over the classes, i.e. numbers p_θ(k | x) ≥ 0 for k = 1, …, K with ∑_k=1^K p_θ(k | x) = 1.

A common loss is cross-entropy: for x ∈ 𝒳 with label y ∈ 𝒴

L = −∑_k=1^K [y = k] log p_θ(k | x) = −log p_θ(y | x),

where [y = k] is 1 if and only if y = k, and 0 otherwise.

Logistic regression for two classes 𝒴 = {0, 1}: let 𝒳 = ℝ^d, let the parameters be w ∈ ℝ^d and b ∈ ℝ, and let σ : ℝ → (0, 1) be the logistic function

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

The model is p(y = 1 | x) = σ(w^⊤x + b) and p(y = 0 | x) = 1 − σ(w^⊤x + b). It assigns a point x to class 1 if and only if σ(w^⊤x + b) ≥ 0.5, i.e. if and only if w^⊤x + b ≥ 0. The decision boundary is the set

{x ∈ ℝ^d : w^⊤x + b = 0}

— for w ≠ 0 a hyperplane, in the plane (d = 2) a straight line.

The derivative of the average cross-entropy J with respect to the weights comes out surprisingly simple (thanks to σ′ = σ(1 − σ), things cancel):

∂J/∂w = 1/n ∑_i=1ⁿ (p_i − y_i) x_i,   ∂J/∂b = 1/n ∑_i=1ⁿ (p_i − y_i),

where p_i = σ(w^⊤x_i + b).

w, b ← initial values
repeat E epochs:                      # epoch = one pass through all the data
    g_w, g_b ← 0, 0
    for each example (x, y):
        p ← σ(w·x + b)                # estimated probability of class 1
        g_w ← g_w + (p − y)·x         # estimation error times input
        g_b ← g_b + (p − y)
    w ← w − η·g_w / n                 # step against the gradient
    b ← b − η·g_b / n
class(x) = 1 if σ(w·x + b) ≥ 0.5, otherwise 0

Accuracy is the fraction of examples classified correctly: |{i ∈ {1, …, n} : class(x_i) = y_i}|/n.

Start: w = (0.4, 1.2), b = −0.9, learning rate η = 2.5. The first point has coordinates (0.604, 0.673) and class 0:

z = 0.4 · 0.604 + 1.2 · 0.673 − 0.9 = 0.148,   p = σ(0.148) = 1/1 + e^−0.148 = 0.537.

So the model assigns this class-0 point to class 1 with probability 0.537 — a mistake. The loss (y = 0, so only the second term of the cross-entropy formula above remains) is −ln(1 − 0.537) = 0.770 (colours as in the formula above), and its contribution to the gradient (p − y) x = 0.537 · (0.604, 0.673) pulls both weights down.

On the whole data: accuracy at the start 15%, after 5 epochs 95%, from epoch 16 on 100%. The average cross-entropy (natural logarithm) falls from 0.780 to 0.175 after 60 epochs; even once all the points are correct, the model keeps increasing the weights to become more confident.

Regression is supervised learning in which the labels are real numbers: 𝒴 = ℝ. Let (x_i, y_i) ∈ 𝒳 × ℝ, i = 1, …, n, be the training pairs and f : 𝒳 → ℝ a model. A common loss is the mean squared error

MSE(f) = 1/n ∑_i=1ⁿ (f(x_i) − y_i)².

Linear regression with one input: let 𝒳 = ℝ, n ≥ 2, and let x₁, …, x_n not all be equal. The model is f(x) = ax + b with parameters a, b ∈ ℝ. Denote the means x̄ = 1/n ∑_i=1ⁿ x_i and ȳ = 1/n ∑_i=1ⁿ y_i. Then the MSE has a unique minimum (the method of least squares) at

a = ∑_i=1ⁿ (x_i − x̄)(y_i − ȳ)/∑_i=1ⁿ (x_i − x̄)²,   b = ȳ − ax̄.

(The assumption that the x_i are not all equal guarantees a non-zero denominator.)

MSE(a, b) is a quadratic function of two variables, so the minimum is where both partial derivatives are zero:

∂/∂b: 2/n ∑ (ax_i + b − y_i) = 0  ⇒  b = ȳ − ax̄ (the line passes through the centroid of the data),

∂/∂a: 2/n ∑ (ax_i + b − y_i) x_i = 0; substituting b gives the formula for a from the definition above.

For the 24 flats in the chart: a = 0.797, b = 0.083, MSE = 0.0046, so the typical vertical deviation (the dashed segments) is √MSE ≈ 0.068. We generated the data as y = 0.12 + 0.72 x + noise with standard deviation 0.06 — from 24 points the method hit the true slope and noise roughly, not exactly.

Let 𝒳 be the input space, P_X an unknown distribution on 𝒳 and D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, inputs drawn from P_X independently of each other — without labels. Unsupervised learning looks in D for the structure of the distribution P_X. Typical tasks:

1. clustering — a partition of the indices {1, …, n} into k non-empty, pairwise disjoint sets C₁, …, C_k (clusters) such that points in one cluster are similar to each other;
2. dimensionality reduction — for 𝒳 = ℝ^d, a mapping g : ℝ^d → ℝ^m, m < d, that preserves as much information about the data as possible;
3. density estimation — a function p̂ : 𝒳 → [0, ∞) that approximates the density p(x) of the distribution P_X.

What exactly “similar” or “as much information as possible” means is decided only by a concrete method through its objective function — like k-means below.

Let x₁, …, x_n ∈ ℝ^d be points, k ∈ ℕ, 1 ≤ k ≤ n, and let ‖·‖ be the Euclidean norm. For a partition of the points into k pairwise disjoint clusters C₁, …, C_k (each point belongs to exactly one) and centres μ₁, …, μ_k ∈ ℝ^d, the within-cluster sum of squares is

J(C₁, …, C_k, μ₁, …, μ_k) = ∑_j=1^k ∑_{x ∈ Cj} ‖x − μ_j‖².

The k-means problem is to find clusters and centres for which J is minimal.

Lloyd’s algorithm (an approximate solution). Input: points x₁, …, x_n ∈ ℝ^d, the number of clusters k and initial centres μ₁, …, μ_k ∈ ℝ^d. Output: clusters C₁, …, C_k and centres μ₁, …, μ_k. Repeat:

1. assignment: put every point x_i into the cluster C_j with j ∈ argmin_{j′ ∈ {1, …, k}} ‖x_i − μ_j′‖² (the nearest centre);
2. moving the centres: for every j = 1, …, k with C_j ≠ ∅ set μ_j = 1/|C_j| ∑_{x ∈ Cj} x (the mean of the cluster’s points).

Stopping: when no centre changes in step 2. No step increases J and there are finitely many possible partitions, so the algorithm terminates — but in general only in a local minimum of J.

μ₁, …, μ_k ← initial centres
repeat:
    for each point x:                    # step 1: assignment
        c(x) ← argmin_j ‖x − μ_j‖²
    for each j = 1, …, k:                # step 2: moving the centres
        μ_j ← mean of the points with c(x) = j
until the centres stop moving

Why J does not increase. Step 1 changes only the assignment, and every point moves to a closer centre, so its term ‖x − μ_j‖² does not increase. Step 2 changes only the centres, and the mean is the point that minimises the sum of squared distances to a group of points (the derivative of ∑ ‖x − μ‖² with respect to μ is −2 ∑ (x − μ), which is zero exactly for the mean). There are finitely many possible assignments, so the algorithm terminates.

In our chart (66 points), J takes the values 19.330 → 2.937 → 1.048 → 0.655 in the individual iterations — the biggest chunk of the work is done by the very first move of the centres away from the bad start.

Let 𝒳 be the input space, 𝒴 the label space, P an unknown distribution on 𝒳 × 𝒴 and l, u ∈ ℕ, l ≥ 1. We are given

1. a small labelled set D_L = ((x_i, y_i))_i=1^l, (x_i, y_i) ∈ 𝒳 × 𝒴, drawn independently from P;
2. a large unlabelled set D_U = (x_j)_j=l+1^l+u, x_j ∈ 𝒳, drawn independently from the distribution of the inputs X alone (the labels y_j exist, but we do not know them), where u ≫ l.

Semi-supervised learning has the same goal as supervised learning — a model f_θ : 𝒳 → 𝒴 with a small true risk — but uses both D_L and D_U to reach it.

Unlabelled data can help only if the distribution of the inputs says something about the labels. The following assumptions are used (every method rests on at least one of them):

1. smoothness — if two inputs x, x′ ∈ 𝒳 are close to each other in a region with a lot of data, they have (with high probability) the same label;
2. cluster — inputs from one cluster have (with high probability) the same label, so the class boundary runs through places with a low density of data;
3. manifold — the data in 𝒳 = ℝ^d lies close to a surface (a manifold) of dimension m < d, and the distance between points should be measured along this surface, not along a straight line in ℝ^d.

Input: points x₁, …, x_N ∈ ℝ^d, some of which have a label from 𝒴 = {0, 1}, and a number of neighbours k ∈ ℕ (here k = 4). Output: a label for every point that can be reached from the labelled points along the edges of the graph.

1. Build an undirected graph: connect points x_i and x_j (i ≠ j) with an edge if and only if x_j is among the k nearest neighbours of x_i, or x_i is among the k nearest neighbours of x_j (by Euclidean distance).
2. In one round, go through all the unlabelled points; each one that has at least one labelled neighbour gets the label held by the majority of its labelled neighbours (label 0 in case of a tie). Labels assigned in a round take effect only from the next round.
3. Stopping: repeat step 2 while there are unlabelled points and at least one label was added in the last round.

Let D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, be unlabelled data and let g be a fixed (possibly random) rule that automatically, without human work, creates from every input x ∈ 𝒳 a pair

g(x) = (x̃, t),

where x̃ is a part or a corrupted version of the input x and t is what is missing from x̃. Self-supervised learning is supervised learning on the training set (g(x_i))_i=1ⁿ: the model gets x̃ and has to predict t. This artificially created task is called a pretext task.

Next-token prediction — this is how large language models are pre-trained. Let V be a finite vocabulary of tokens and let a text be a sequence x₁, …, x_T ∈ V, T ≥ 1. For each t = 1, …, T the model returns a distribution p_θ(· | x₁, …, x_t−1) on V (for t = 1 without a condition), and the parameters θ are chosen so as to maximise

∑_t=1^T log p_θ(x_t | x₁, …, x_t−1).

Here x̃ = (x₁, …, x_t−1) and the t-th token is the label.

A Markov decision process (the environment) is a five-tuple (S, A, P, R, γ), where

1. S is a non-empty set of states (finite in our case — the cells of a grid);
2. A is a non-empty finite set of actions;
3. P is the transition probability: for every s ∈ S and a ∈ A, P(· | s, a) is a probability distribution on S, i.e. P(s′ | s, a) ≥ 0 and ∑_{s′ ∈ S} P(s′ | s, a) = 1 (P(s′ | s, a) is the probability that action a in state s leads to state s′);
4. R : S × A × S → ℝ is the reward for the transition from s via action a to s′;
5. γ ∈ [0, 1) is the discount factor.

The agent’s policy is a rule π that assigns to every state s ∈ S a distribution π(· | s) on A. The agent starts in state s₀ and for t = 0, 1, 2, … chooses an action a_t according to π(· | s_t), the environment picks the next state s_t+1 according to P(· | s_t, a_t), and the agent receives the reward r_t = R(s_t, a_t, s_t+1). The return is

G = ∑_t=0^∞ γ^t r_t

(in a terminal state the episode ends and all further rewards are 0), and the goal is to find a policy that maximises its expected value E[G].

The action value Q(s, a) is the expected return when the agent performs action a in state s and plays optimally from then on. Q-learning estimates it with a table Q : S × A → ℝ (at the start e.g. all zeros): after every step (s, a, r, s′), with a learning rate α ∈ (0, 1], it performs

Q(s, a) ← Q(s, a) + α [r + γ max_{a′ ∈ A} Q(s′, a′) − Q(s, a)],

where, if s′ is a terminal state, max_a′ Q(s′, a′) = 0 is used.

Let A be a finite non-empty set of actions, Q : S × A → ℝ a table of action values and ε ∈ [0, 1]. For a state s ∈ S, choose a*(s) ∈ argmax_{a ∈ A} Q(s, a) (in case of a tie, any of the best). The ε-greedy policy chooses action a ∈ A in state s with probability

π(a | s) = ε/|A| + (1 − ε) · [a = a*(s)],

where [a = a*(s)] is 1 if and only if a = a*(s), and 0 otherwise. In other words: with probability ε it picks an action at random (uniformly from all of them), otherwise the action with the largest Q(s, a). In our case ε = 0.2.

The first step. At the start the whole table Q is zero. The agent takes a step onto an ordinary cell: r = −1 and max_a′ Q(s′, a′) = 0, so

Q(s, a) ← 0 + 0.5 · [−1 + 0.95 · 0 − 0] = −0.5

(colours as in the Q-learning formula above). A step into the goal is terminal, so the term max_a′ Q(s′, a′) is 0: Q ← 0 + 0.5 · [10 − 0] = 5. On later visits the five moves towards 10 and spreads further back along the path, each time multiplied by 0.95 and reduced by the cost of a step.

The value of the start. The shortest path has 10 steps: nine ordinary ones at −1 and the last one into the goal at +10. The undiscounted return is 9 · (−1) + 10 = 1, the discounted one

G = −(1 + 0.95 + … + 0.95⁸) + 0.95⁹ · 10 = −1 − 0.95⁹/1 − 0.95 + 10 · 0.95⁹ = −7.395 + 6.302 = −1.093.

The learned table has max_a Q(start, a) = −1.093 at the start — Q-learning found the value of the optimal path exactly.

Let J_source, J_target : ℝ^p → ℝ be the objective functions of a source task (usually with a lot of data) and a target task (usually with little data) for a model with the same parameters θ ∈ ℝ^p, and let θ₀ be the parameters learned on the source task, i.e. (approximately) θ₀ ∈ argmin_θ J_source(θ). Transfer learning searches for

θ* ∈ argmin_θ J_target(θ)

by gradient descent that starts at θ₀ (instead of random values). In fine-tuning, often only the parameters with indices from a small set I ⊂ {1, …, p} are changed; the others stay equal to their values in θ₀.

Let D_L be a labelled and D_U an unlabelled set (as in semi-supervised learning), 𝒴 = {1, …, K}, and p_θ(· | x) a model trained on D_L. Active learning repeats these steps:

1. the model itself selects the input x* ∈ D_U it is least sure about — for example the one with the highest entropy: x* ∈ argmax_{x ∈ DU} H(p_θ(· | x));
2. a human (the teacher) supplies its label y*; the pair (x*, y*) moves from D_U to D_L;
3. the model is retrained on D_L;

until the labelling budget runs out.

Let p be a distribution on {1, …, K}, i.e. p(k) ≥ 0 and ∑_k=1^K p(k) = 1. Its entropy (in bits) is

H(p) = −∑_k=1^K p(k) log₂ p(k),   where 0 · log₂ 0 = 0 by convention.

For two classes: an estimate of 50 : 50 has H = −2 · 0.5 · log₂ 0.5 = 1 bit (the most possible), an estimate of 90 : 10 has H = −0.9 log₂ 0.9 − 0.1 log₂ 0.1 ≈ 0.137 + 0.332 = 0.469 bits, an estimate of 99 : 1 only 0.081 bits. The first to be labelled will be an example where the model hesitates 50 : 50.

Let 𝒳 be the input space and 𝒴 the label space.

1. A discriminative model learns the conditional distribution p_θ(y | x) for x ∈ 𝒳, y ∈ 𝒴 directly, or straight away a decision function f_θ : 𝒳 → 𝒴 (and hence a decision boundary). It says nothing about how the inputs x themselves are distributed.
2. A generative model learns the data distribution p_θ(x) on 𝒳, or the joint distribution p_θ(x, y) on 𝒳 × 𝒴, and can sample new data from it. From the joint distribution the conditional one can be computed as well (for finite 𝒴): p_θ(y | x) = p_θ(x, y)/∑_{y′ ∈ 𝒴} p_θ(x, y′).