A loss function $L(z, y)$ is defined as a scalar penalty comparing a raw model score $z$ (or a predicted probability $\hat{y}$) against the target $y$. Smaller is better. Each family of models is characterized by its loss.

| Cross-entropy | $-\left[\,y\log\hat{y}+(1-y)\log(1-\hat{y})\,\right]$ | Neural networks |

*Remark:* $z$ denotes a raw score such as $w^T x$, whereas $\hat{y} \in (0,1)$ denotes a predicted probability, the model's estimate of the label $y$. The cross-entropy row takes a probability $\hat{y}$, not a raw score.


The cost $J(w)$ is defined as the sum of the per-example losses over the whole training set of $m$ examples:

$$\boxed{\,J(w)=\sum_{i=1}^{m} L\!\left(h_w(x^{(i)}),\,y^{(i)}\right)\,}$$

Training a model means choosing $w$ to minimize $J(w)$. The algorithms that carry out this minimization (closed forms, gradient descent) arrive with the model modules. This module asks a different question: what does a low value of $J(w)$ actually prove?

To make everything concrete, take a single input $x$ and fit a polynomial of degree $d$ under the squared loss:

$$\boxed{ h_w(x) = w^T \phi(x) = \sum_{j=0}^{d} w_j\, x^{j}, \qquad \phi(x) = (1, x, x^2, \dots, x^d) }$$

The model stays linear in $w$, so least squares applies unchanged (the closed form is derived in [Linear regression](/en/Machine%20Learning/04%20Linear%20regression)). The degree $d$ is not fitted along with $w$: it is fixed before fitting and decides how flexible the curve is allowed to be. A knob of that kind, chosen rather than learned, is called a hyperparameter, and $d$ is our first one.


The quantity we care about is the generalization error, the expected loss on a fresh draw from the same population:

$$\boxed{ R(h) = \mathbb{E}_{(x, y)}\left[ L\!\left(h(x), y\right) \right] }$$

We cannot observe it, so we estimate it. The tempting estimate is the training error, the average loss on the data used to fit $h$. It is biased downward: the model has already adapted to that particular sample, so it scores itself too kindly.

$$\boxed{ \hat{R}_{\text{train}}(h) = \frac{1}{m}\sum_{i=1}^{m} L\!\left(h(x^{(i)}), y^{(i)}\right) \;\le\; R(h) \ \text{(in expectation)} }$$

Back to the polynomials. The degree-1 fit underfits: it lacks the capacity to represent the trend, so it scores badly on the training points and on new points alike. The degree-9 fit overfits: it has capacity to spare, drives the training error to zero by weaving through the noise, and pays for it on fresh data. It has the lowest training error of the three fits and is also the worst model. The good model sits in between.


This is the bias-variance trade-off. A rigid model is biased: it is systematically off, whichever sample it is trained on. A flexible model has high variance: its fit swings with every resample of the noise. Raising capacity trades bias for variance, and generalization is best where the two balance.

*Remark:* training error is not evidence of quality. Past the sweet spot it is evidence of memorization, and only performance on unseen data can tell the difference.

Choosing the degree is a coarse dial: capacity jumps by whole integers. A finer control keeps a flexible family but makes complexity expensive inside the cost itself, by adding a penalty $\Omega(w)$ scaled by a strength $\lambda \ge 0$:

$$\boxed{\,J_\lambda(w)=\sum_{i=1}^{m} L\!\left(h_w(x^{(i)}),\,y^{(i)}\right) + \lambda\,\Omega(w)\,}$$

The classic choice is the squared norm $\Omega(w) = \lVert w \rVert_2^2$, the ridge penalty. The degree-9 fit only weaves through every point by using huge coefficients that cancel each other between the training points. The penalty makes those coefficients costly, so the minimizer trades a little training error for a much smoother curve. At $\lambda = 0$ the overfitted fit returns, as $\lambda \to \infty$ the curve flattens toward underfitting: $\lambda$ sweeps the same bias-variance dial as the degree, but continuously.

*Remark:* regularization does not decide the right complexity for you, it converts a discrete choice ($d$) into a continuous one ($\lambda$) that is easier to tune. $\lambda$ is a hyperparameter like the degree, chosen by the validation machinery of the next section. Where the penalty comes from (a prior on $w$, via maximum a posteriori) and what the L1 variant adds are the subjects of [Probabilistic formulation](/en/Machine%20Learning/03%20Probabilistic%20formulation) and [Linear regression](/en/Machine%20Learning/04%20Linear%20regression).

Hyperparameters cannot be chosen on the training error, which only rewards more capacity. The fix is to keep data the model never touched during fitting. The standard split has three disjoint roles:

| Set | Used for | Touched |

*Remark:* the test set is sacred. Every time a choice is guided by test performance, the test set quietly becomes part of training and its estimate turns optimistic.

Samples are often small, and a single train/validation split both wastes data and gives a noisy estimate. k-fold cross-validation reuses the data: partition it into $K$ folds, and for each fold train on the other $K-1$ and validate on the held-out fold. The cross-validation error averages the $K$ rounds:

$$\boxed{ \text{CV}_K = \frac{1}{K}\sum_{k=1}^{K} \frac{1}{|F_k|}\sum_{i \in F_k} L\!\left(h^{(-k)}(x^{(i)}), y^{(i)}\right) }$$

where $h^{(-k)}$ is trained on all folds except $F_k$. Taking $K = m$ gives leave-one-out cross-validation. Common choices are $K = 5$ or $K = 10$, trading computation against a lower-variance estimate.


Cross-validation is how we tune. Fit each candidate (a model family, a tree depth, the polynomial degree $d$, or the penalty $\lambda$) and keep the one with the lowest validation or CV error. Only then, once the choice is frozen, do we touch the test set to report a final number.

*Remark:* choosing the winner on the test set inflates the estimate. With enough candidates one will look good by chance alone, the winner's curse, so selection and final evaluation must use different data.

Honest validation is harder than it looks, and real data often breaks the usual assumptions in three ways.

- **Data leakage.** Information about the target leaks into the features. Standardizing with statistics computed on the full sample, or including a variable realized after the outcome, lets the model peek at the answer. Any preprocessing must be fit on the training folds only.

For time series, use a rolling-origin (blocked) scheme so the model is only ever tested on data that comes after its training window. For grouped data, hold out whole units (grouped cross-validation) so no unit appears on both sides.


*Remark:* this is why learning in high dimension leans on structure rather than raw proximity: linear models, regularization pulling toward simple fits, and features or embeddings that compress the inputs. Real data usually concentrates near a much lower-dimensional structure, and that is what makes learning possible at all.

Next: [Probabilistic formulation](/en/Machine%20Learning/03%20Probabilistic%20formulation) · [Course overview](/en/Machine%20Learning)