Formulating a Learning Problem

Intuition first

Before an algorithm can learn anything, three decisions have to be made, and they are decisions you make, not the algorithm.

What shapes of answer will I allow? A straight line? Any curve? A decision tree of depth at most five? This is the hypothesis space, and it is a restriction you impose deliberately — allowing every possible function sounds generous but makes learning impossible.

What counts as a bad answer? Being off by 10 on a house price is not the same kind of error as classifying a tumour incorrectly. The loss function encodes how much you care about each type of mistake.

What am I averaging over? You want to do well on future data, but you only have the data in front of you. Everything hinges on that substitution.

Get these three right and the algorithm is almost an afterthought. Get them wrong and no amount of model tuning will rescue the project.

The four ingredients

1. Input and output spaces

$$\mathcal{X} \subseteq \mathbb{R}^d, \qquad \mathcal{Y} = \mathbb{R} \;\text{ or }\; \mathcal{Y} = \{1, \dots, K\}$$

Deciding $\mathcal{X}$ is feature engineering: which measurements exist, in what units, encoded how. Deciding $\mathcal{Y}$ is often where projects go wrong — the same business question can be posed as regression, binary classification, or ranking, and the three lead to different models and different metrics.

2. The data-generating distribution

We assume a fixed but unknown joint distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$, and that our sample is drawn independently from it:

$$S = \{(x_1, y_1), \dots, (x_n, y_n)\} \sim \mathcal{D}^n$$

$\mathcal{D}$ is never observed. It is a modelling fiction that lets us say precisely what "generalise" means.

3. The hypothesis space

$\mathcal{H}$ is the set of functions the learner may return. Examples:

$$\mathcal{H}_{\text{linear}} = \{\, h(x) = w^{\mathsf{T}}x + b \;:\; w \in \mathbb{R}^d,\ b \in \mathbb{R} \,\}$$ $$\mathcal{H}_{\text{poly-}k} = \{\, h(x) = \textstyle\sum_{j=0}^{k} a_j x^j \,\}$$

Choosing $\mathcal{H}$ is choosing an inductive bias — an assumption about what kind of pattern the world contains. Linear models assume additive effects; decision trees assume axis-aligned thresholds; convolutional networks assume translation invariance.

4. The loss function

$L(y, \hat{y}) \geq 0$ measures the cost of predicting $\hat{y}$ when the truth is $y$. Standard choices:

Risk: what we want versus what we can compute

The quantity we actually care about is the true risk — expected loss over the whole distribution:

$$R(h) = \E_{(x,y) \sim \mathcal{D}}\big[\, L(y, h(x)) \,\big]$$

This is uncomputable, because $\mathcal{D}$ is unknown. What we can compute is the empirical risk on our sample:

$$\hat{R}_S(h) = \frac{1}{n} \sum_{i=1}^{n} L\big(y_i, h(x_i)\big)$$

Learning proceeds by minimising the second and hoping it tracks the first:

$$\hat{h} = \argmin_{h \in \mathcal{H}} \hat{R}_S(h)$$

Why empirical risk is a sensible substitute — and where it breaksAdvanced

For any fixed $h$, the empirical risk is an average of $n$ i.i.d. random variables $L(y_i, h(x_i))$, each with mean $R(h)$. So it is unbiased:

$$\E_S\big[\hat{R}_S(h)\big] = \frac{1}{n}\sum_{i=1}^n \E\big[L(y_i, h(x_i))\big] = R(h)$$

and by the law of large numbers $\hat{R}_S(h) \to R(h)$ as $n$ grows. Chebyshev's inequality even quantifies the gap: if the loss has variance $\sigma^2$, then

$$\Prob\big(\lvert \hat{R}_S(h) - R(h) \rvert > \epsilon\big) \leq \frac{\sigma^2}{n\epsilon^2}$$

So far, so reassuring. The catch is the phrase for any fixed $h$.

We do not evaluate a fixed $h$ — we choose $\hat h$ by minimising $\hat{R}_S$ over all of $\mathcal{H}$. That choice depends on $S$, so $\hat{R}_S(\hat h)$ is no longer an unbiased estimate of $R(\hat h)$: the minimisation deliberately seeks out hypotheses that look good on this particular sample, including by exploiting its noise.

Concretely, $\E_S[\hat{R}_S(\hat h)] \leq R(\hat h)$ — empirical risk is optimistically biased, and the bias grows with the richness of $\mathcal{H}$. This single fact is the origin of overfitting, of why a held-out test set is mandatory, and of the entire theory of generalisation bounds.

Parametrising the search

In practice $\mathcal{H}$ is indexed by parameters $\theta$, so optimising over functions becomes optimising over vectors:

$$\hat{\theta} = \argmin_{\theta} \frac{1}{n}\sum_{i=1}^{n} L\big(y_i, h_\theta(x_i)\big)$$

That is what every training loop in this curriculum computes — from the closed-form normal equations of linear regression to weeks of gradient descent on a language model.

Solved problem 1 · Formulating a problem completely

A hospital wants to predict, at admission, whether a patient will be readmitted within 30 days. Available data: 40,000 past admissions with 60 recorded features. Readmission rate is 11%. The hospital can enrol roughly 200 patients per month in an intensive follow-up programme.

Specify $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{H}$, $L$, and the evaluation metric.

Step 1 — output space, and why it is not what it first appears

The obvious choice is $\mathcal{Y} = \{0, 1\}$. But the hospital cannot act on a hard label — it must rank patients to fill 200 slots. So the model should output a probability:

$$h : \mathcal{X} \to [0, 1], \qquad h(x) = \Prob(\text{readmitted} \mid x)$$

Thresholding happens afterwards, as a separate decision driven by capacity.

Step 2 — input space

$\mathcal{X} \subseteq \mathbb{R}^d$ after encoding the 60 raw features: continuous ones standardised, categorical ones one-hot encoded. Critically, every feature must be available at admission — anything recorded during the stay is unavailable at prediction time and would leak.

Step 3 — hypothesis space

Start with regularised logistic regression:

$$\mathcal{H} = \Big\{\, h(x) = \sigma(w^{\mathsf{T}}x + b) \;:\; \lVert w \rVert_2 \leq C \,\Big\}, \qquad \sigma(z) = \frac{1}{1 + e^{-z}}$$

Justification: 40,000 examples with roughly 4,400 positives is not much for a high-capacity model, and clinical settings require coefficients a doctor can inspect. Gradient boosting is the natural next step to compare against.

Step 4 — loss function

Cross-entropy, because we want calibrated probabilities:

$$L(y, \hat{p}) = -\big[\, y \log \hat{p} + (1-y)\log(1-\hat{p}) \,\big]$$

The 0–1 loss is unsuitable: it is not differentiable, and it treats a confident wrong prediction the same as a borderline one.

Step 5 — evaluation metric, driven by the constraint

Accuracy is useless here. Predicting "never readmitted" scores

$$1 - 0.11 = 0.89 = 89\%$$

while helping nobody. Since only 200 patients can be enrolled per month, the operative question is how many of the top 200 ranked patients are genuine readmissions. So the metric is precision at $k = 200$, with recall at that threshold reported alongside to show the fraction of readmissions captured.

Answer

$\mathcal{X} \subseteq \mathbb{R}^d$ from admission-time features only; $\mathcal{Y} = [0,1]$ predicted probability; $\mathcal{H}$ = L2-regularised logistic regression; $L$ = cross-entropy; metric = precision@200 with recall reported. Note that the loss used for fitting and the metric used for judging are deliberately different.

Choosing the hypothesis space is choosing your errors

The left model cannot represent the truth however much data you give it — its error is bias. The right model can represent the truth but is so sensitive to the particular sample that it latches onto noise — its error is variance. Naming and quantifying this split is the next two lessons.

Exercise 1

You are asked to predict delivery time in minutes. A colleague proposes using 0–1 loss on whether the prediction is within 5 minutes. Give one advantage and two disadvantages.

Show solutionHide solution

Advantage: it directly encodes the business requirement. If customers only care whether the estimate was roughly right, a metric that says "within 5 minutes or not" matches reality better than squared error, which penalises a 40-minute miss 320 times more than a 2-minute one.

Disadvantages:

1. Not usable for fitting. The 0–1 loss has zero gradient almost everywhere and is discontinuous at the threshold, so gradient-based optimisation cannot move. You would fit with squared or absolute loss and only evaluate with this.
2. It discards information about magnitude. A prediction off by 6 minutes and one off by 3 hours score identically. A model optimised for this metric has no incentive to avoid catastrophic misses, which are exactly the ones that lose customers.

A reasonable resolution: fit with Huber loss, report both mean absolute error and the within-5-minutes rate.

Exercise 2

Explain why $\mathcal{H}$ containing all possible functions from $\mathcal{X}$ to $\mathcal{Y}$ makes learning impossible, even with a large sample.

Show solutionHide solution

If $\mathcal{H}$ is unrestricted, then for any training sample $S$ there exist hypotheses that fit $S$ perfectly and disagree completely on every point outside $S$. In fact for every unseen $x$ and every candidate label, some hypothesis in $\mathcal{H}$ achieves zero empirical risk while predicting that label.

Empirical risk minimisation therefore cannot distinguish between them — they all score zero — so the training data provides no information about how to behave on new inputs. Learning requires preferring some functions over others before seeing data, and an unrestricted $\mathcal{H}$ expresses no such preference.

This is the informal content of the No Free Lunch theorem, covered later in this module.

---

Next: Empirical Risk Minimisation, which examines the gap between $\hat{R}_S$ and $R$ carefully — the gap that explains everything that goes wrong.