Machine Learning & Signals Learning

4 Model Characterization

4.1 Uni-variate Polynomial Model

The \(L\)-degree uni-variate polynomial regression model is

\begin{equation} \begin{aligned} \hat {y} = f_\bw (x) &= w_0 + w_1x + w_2x^2 + \cdots + w_Lx^L\\ &=\sum _{j=0}^{L} w_jx^j \end {aligned} \end{equation}

This problem is linear by the change of variables, \(z_{j} = x^j,\; j=0,\ldots ,L\),

\begin{equation} \hat {y} =\sum _{j=0}^{L} w_jz_{j} \end{equation}

The corresponding prediction for the dataset \(\left \{x_k,y_k\right \}_{k=1}^M\) can be easily written by using the matrix notation (also termed Vandermonde matrix),

\begin{equation} \renewcommand {\arraystretch }{1.3} \bX = \begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^L\\ 1 & x_2 & x_2^2 & \cdots & x_2^L\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_M & x_M^2 & \cdots & x_M^L\\ \end {bmatrix} \end{equation}

The weights vector values are straightforward by (3.5),

\begin{equation*} \bw _{opt} = \left (\bX ^T\bX \right )^{-1}\bX ^T\by \end{equation*}

Hyper-parameter: A hyper-parameter is a parameter that defines the model structure or the learning process, and is set before training rather than learned from the data. In contrast to the model parameters \(\bw \), which are optimized during training, hyper-parameters are chosen by the designer (further discussed in Sec. 7.1.2).

The value of \(L\) in the polynomial model is an example of a hyper-parameter, as it determines the model complexity.

4.2 Generalization

Let’s assume that the dataset \((\bX ,\by )\) are \(M\) samples drawn from some (unknown) joint probability distribution, \(\mathcal {D}\). The theoretical model performance is given by some average model metric (not loss) over all (theoretically) possible points from \(\mathcal {D}\),¹

\begin{equation} \label {eq-generalization-metric} \bar {J}_{theory} = \lim \limits _{M\rightarrow \infty }\frac {1}{M}\sum _{k=1}^MJ(y_k,\hat {y}_k) \end{equation}

Generalization: The difference between:

• • Performance metric over dataset that is used to train the model, \(\bar {J}_M\).

• • Theoretical performance metric \(\bar {J}_{theory}\) from (4.4).

Better generalization means smaller difference between model performance and theoretical performance.

The problem is that the distribution \(\mathcal {D}\) is unknown in most of the practical applications. Moreover, in practice, the value of \(M\) is (very) limited and \(\bar {J}_M\) can significantly differ from \(\bar {J}_{theory}\).

The generalization gap has two main sources:

• • Data-related: limited dataset size \(M\), sampling bias, noise in the data, and non-representative samples from \(\mathcal {D}\).

• • Model-related: model complexity mismatch (underfitting or overfitting), inappropriate model assumptions, and insufficient regularization.

In the following, methods to reduce both data-related and model-related gaps such that \(\bar {J}_M\approx \bar {J}_{theory}\) will be discussed.

The generalization concept is illustrated in Fig. 4.1.

Table 4.1 summarizes the methods discussed in this chapter and their influence on the generalization gap. Each method primarily addresses either data-related or model-related sources of the gap.

4.3 Bias-Variance Trade-Off

4.3.1 Bias and Variance

Noise deterministic function model The general model beneath the dataset model is

\begin{equation} y_i = h(\bx _i) + \epsilon _i, \end{equation}

where \(h(\bx )\) is some unknown function and \(\epsilon \) is some random noise with unknown distribution, zero-mean (\(\bar {\epsilon }=0\)) and variance of \(\sigma ^2\) \((\Var [\epsilon ]=\sigma ^2)\).

A model predicts outputs via \(\hat {y}_i = f_\bw (\bx _i)\) with error \(e_i = \hat {y}_i-y_i\).

Bias The bias of the model is the expected difference between predictions and the true function,

\begin{equation} \mathrm {Bias}[\hat {y}] = \E [\hat {y}] - \E [y] = \E [f_\bw (\bx )] - h(\bx ) \end{equation}

where the expectation is taken over all possible training samples.

For a specific dataset, the empirical bias can be estimated as:

Variance The variance of the model measures the variability of predictions across different training sets,

\begin{equation} \Var [\hat {y}] = \mathbb {E}\!\left [\left (\hat {y} - \E [\hat {y}]\right )^2\right ] \end{equation}

The bias and variance are illustrated conceptually in Fig. 4.2.

The Explicit Bias-Variance Trade-off Formula The core of model evaluation relates to understanding the total expected prediction error (MSE). For a new unseen point \(\bx \), the expected error is explicitly given by the sum of three fundamental components:

\begin{equation} \label {eq-bias-variance-basics} \E [(y - \hat {y})^2] = \left (\mathrm {Bias}[\hat {y}]\right )^2 + \Var [\hat {y}] + \sigma ^2 \end{equation}

where:

• • Squared Bias \(\left (\mathrm {Bias}[\hat {y}]\right )^2\): Error introduced by approximating a real-world problem with a simplified model.

• • Variance \(\Var [\hat {y}]\): Error introduced by the model’s sensitivity to small fluctuations or noise in the training set.

• • Irreducible Noise \(\sigma ^2\): The inherent variance of the data itself that no model can capture.

The total prediction error consists of these three components (formally derived in Sec. 4.8). The inherent bias-variance trade-off is presented in Fig. 4.3. Underfitting is characterized by low variance and high bias, whereas overfitting is characterized by high variance and low bias. The best generalized model performance balances this inherent bias-variance trade-off to minimize the overall expected error. However, note that some poorly chosen models can simultaneously exhibit both high bias and high variance.

Figure 4.5 shows the squared bias, variance, and their sum (plus irreducible noise \(\sigma ^2\)) as a function of polynomial degree. The empirical MSE (green crosses) closely matches the theoretical decomposition (black diamonds), confirming (4.9). As the model complexity increases, bias decreases while variance increases, producing the characteristic U-shaped total error curve.

4.3.2 Overfitting and underfitting

The effect of model complexity is illustrated with polynomial regression (Sec. 4.1) in Fig. 4.6. A degree-1 polynomial (top left) underfits and it cannot capture the cubic shape (see Fig. 4.4) of the data. A degree-3 model (top right) matches the true data-generating order and generalizes well to test points. Degree-6 and degree-10 models (bottom row) overfit, failing on unseen test data (blue). The annotated weight \(w_i\) in each panel shows that the largest coefficient magnitude grows with the polynomial degree, a mark of overfitting.

To evaluate a model, the available dataset is split into a training subset (used to fit the model) and a test subset (used to evaluate it on unseen data). The formal splitting procedures are discussed in Sec. 4.4. The relationship between model complexity and performance on these two subsets reveals two failure modes.

Overfitting is when the model is too complex, i.e. have too many parameters.

• • Too many parameters relative to the number of observations. Theoretically, we expect at least an order of magnitude more observations than parameters.

• • Follow the training data very closely.

• • Fail to generalize well to unseen data.

Underfitting happens when a model is too simple.

• • Unable to capture the underlying pattern of the data and hence misses the trends in the data.

• • Performs poorly on the training data and fail to generalize.

Overfitting and underfitting are complementary and balancing between them is key to building robust machine learning models that perform well on new, unseen data, i.e. generalize well. This principle is illustrated in Fig. 4.7

4.4 Cross-validation

The cross-validation methods are illustrated in Fig. 4.8.

Big dataset \(\left (10^4\lesssim M\right )\): train/validation/test

First step is to resample the dataset into the random order. Then, split it into three distinctive datasets:

• • Training dataset (50-80%): used for learning of model parameters, e.g. weights \(\bw \).

• • Validation dataset (10-25%): used for assessment of model hyper-parameters influence.

• • Test dataset (10-25%): performance assessment that is supposed to be sufficiently close to \(\bar {J}_{theory}\).

Hyper-parameter selection proceeds as follows:

• 1. For each candidate hyper-parameter value (e.g., polynomial degree \(L\), regularization \(\lambda \)), train the model on the training set and evaluate the metric on the validation set.

• 2. Select the hyper-parameter value that yields the best validation metric.

• 3. Retrain the model on the combined training and validation sets using the selected hyper-parameter, and report the final performance on the held-out test set.

Medium datasets \(\left (10^2\lesssim M\lesssim 10^4\right )\): Nested k-fold Cross-Validation

The first step is to resample the dataset into a random order. After randomizing, we apply a nested loop procedure to separate two main objectives: hyper-parameter selection and performance assessment. Conflating these objectives into a single loop leads to optimistic performance estimates because the test data would indirectly influence model selection.

Nested cross-validation separates these objectives into two loops (Fig. 4.8):

• • Outer loop (\(k_{\text {out}}\) folds for Performance Assessment): The available dataset is divided into \(k_{\text {out}}\) subsets (folds) of approximately equal size. In each of the \(k_{\text {out}}\) iterations, one fold (red in Fig. 4.8) is held out as the test set for unbiased performance evaluation. The remaining \(k_{\text {out}}-1\) folds form the outer training set.

• • Inner loop (\(k_{\text {in}}\) folds for Hyper-parameter Tuning): Within each outer training set, a further \(k_{\text {in}}\)-fold split creates validation folds (yellow in Fig. 4.8). For each candidate hyper-parameter value (e.g., polynomial degree \(L\), regularization parameter \(\lambda \)), the model is trained on the inner training folds (blue) and evaluated on the inner validation fold. The hyper-parameter value that maximizes the average inner validation metric is selected.

After the inner loop selects the best hyper-parameter, the model is retrained on the entire outer training set using that hyper-parameter, and its performance is evaluated on the outer test fold. The final performance estimate is the average over the \(k_{\text {out}}\) outer test metrics:

\begin{equation} \bar {J} = \frac {1}{k_{\text {out}}} \sum _{i=1}^{k_{\text {out}}} J_i \end{equation}

Usually, \(k_{\text {out}}\) defaults to 5 or 10.

When hyper-parameter optimization is not required the inner loop is completely omitted. The procedure simply collapses into a standard, single-loop \(k\)-fold cross-validation. The model is trained on the \(k_{\text {out}}-1\) training folds and evaluated directly on the held-out test fold. This process is repeated \(k_{\text {out}}\) times, and the performance is averaged.

Grouped Cross-Validation When data is collected from distinct domains or groups (e.g., multiple patients, different sensors, separate locations), standard random splitting can place samples from the same group in both training and test folds. This allows the model to learn domain-specific signatures rather than generalizable patterns. Grouped cross-validation ensures that all samples from a given group are assigned to the same fold, providing a realistic estimate of performance on unseen domains. Further CV splitting strategies are discussed in Sec. 11.1.1.

Very small datasets \(\left (M\lesssim 10^2\right )\): Leave-One-Out Cross-Validation (LOOCV)

Uses \(k\)-fold with \(k=M\), which means that each fold will contain only one data point.

4.5 Normalization and Standardization

Values in different columns in \(\bX \) (feature columns \(\btx _j\)) may be different by orders of magnitudes, i.e. \(\norm {\btx _i}\gg \norm {\btx _j}\). This results in:

• • Some columns have significantly higher influence on \(\hat {\by }\).

• • Numerical instabilities.

Standardization (z-score normalization)

\begin{equation} \label {eq-zscore} \bz = \frac {\bx -\bar {\bx }}{s_\bx }, \end{equation}

such that \(\bar \bz = 0, s_\bz = 1\).

Implementation steps:²

• 1. On train dataset, evaluate \(\bar {\bx }\) and \(\sigma _\bx \).

• 2. Apply normalization on train dataset, using \(\bar {\bx }\) and \(\sigma _\bx \).

• 3. Apply normalization on test dataset, using same \(\bar {\bx }\) and \(\sigma _\bx \) (no recalculation).

When normalization is applied to \(\by \), the output of the model is transformed back, \(\hat {\by } = \hat {\by }_{std}\sigma _\by + \bar {\by }\).

Normalization

Mapping all values of a feature to be in the range \([0,1]\) by the transformation³

\begin{equation} x_{norm} = \frac {x-x_{min}}{x_{max}-x_{min}} \end{equation}

Implementation steps for normalization are similar to standardization.

Pros:

• • Improves convergence speed of gradient-based optimization.

• • Prevents features with large magnitudes from dominating distance-based models.

• • Standardization of both \(\bX \) and \(\by \) results in \(w_0=0\) and removes the requirement for \(\bOne \) column in \(\bX \).

Cons:

• • Min-max normalization is sensitive to outliers.

• • Scaling parameters must be computed on the training set and applied consistently to the test set.

4.6 Dataset Size

By the law of large numbers, the sample average \(\bar {J}_M = \frac {1}{M}\sum _{k=1}^M J(y_k,\hat {y}_k)\) converges to the theoretical performance (4.4), so the generalization gap \(\bar {J}_M - \bar {J}_{theory}\) shrinks as the number of samples \(M\) grows. However, the benefit of additional data depends on whether the model is overfitting or underfitting, as summarized in Table 4.2 and illustrated in Fig. 4.9.

4.7 Regularization

Regularization: Penalty to the loss function

\begin{equation} \loss _{\mathrm {new}} = \loss + \lambda g(\bw ) \end{equation}

where \(\lambda \) is termed regularization parameter.

\(L_2\)-regularization: Special case of

\begin{equation} g(\bw ) = \dfrac {1}{2M}\left \| \bw \right \|^2 =\frac {1}{2M}\sum _{i=1}^N w_i^2 \end{equation}

where vector of weights \(\bw \) does not include \(w_0\) weight. Moreover, when normalization is used, no \(w_0\) weight is needed. Two special cases are:

• • \(\lambda \rightarrow 0\) gets the original loss function (overfitting).

• • \(\lambda \rightarrow \infty \) makes loss function independent on \(\bw \) (underfitting).

Polynomial regression example The resulting coefficients \(w_i\) will be significantly higher for higher \(i\) (Fig. 4.6). Reducing them results in smooth \(\hat {y}\) prediction. The illustration of \(\lambda \) influence is presented in Fig. 4.10.

The corresponding underfitting-overfitting \(\lambda \)-related trade-off is presented in Fig. 4.11.

4.7.1 Ridge Regression

Ridge regression: \(L_2\)-regularized linear regression.

\begin{equation} \begin{aligned} \mathcal {L}(\bw ) &= \frac {1}{2M}\left \| \by - \bX \bw \right \|^2 + \frac {\lambda }{2M}\underbrace {\left \| \bw \right \|^2}_{\sum _{i=1}^{N}w_i^2}\\ &= \frac {1}{2M}\left (\by - \bX \bw \right )^T \left (\by - \bX \bw \right ) + \frac {\lambda }{2M}\bw ^T\bw \end {aligned} \end{equation}

Derivative

\begin{equation} \nabla \mathcal {L}(\bw ) =\frac {1}{M}\left (-\bX ^T\left (\by - \bX \bw \right ) + \lambda \bw \right )= 0 \end{equation}

Solution

\begin{align*} &-\bX ^T\left (\by - \bX \bw \right ) + \lambda \bw = -\bX ^T \by + \bX ^T\bX \bw + \lambda \bw = 0\\ &\bX ^T \by = \bX ^T\bX \bw + \lambda \bw \end{align*} Finally, the regularized weights are given by

\begin{equation} \label {eq-rigde-regression-w} \bw = \left (\lambda \mathbf {I} + \bX ^T\bX \right )^{-1}\bX ^T \by \end{equation}

Can be viewed as special case of linear regression, of the form

\begin{align} \tilde {y} &= \tilde {\bX }\bw \nonumber \\ \begin{bmatrix} \by \\ 0 \\ \vdots \\ 0 \end {bmatrix} &= \begin{bmatrix} - & \bX & - \\ \sqrt {\lambda } & & 0 \\ & \ddots & \\ 0 & & \sqrt {\lambda } \end {bmatrix} \begin{bmatrix} w_1\\ \vdots \\ w_N \end {bmatrix} +w_0 \end{align}

Slope interpretation Higher value of \(\lambda \) reduces (mostly) the highest slopes (weights \(w_i\)) \(\Rightarrow \) the dependency on the parameters with these weights is reduced.

Eigenvalues interpretation This calculation limits the smallest eigenvalues to \(>\frac {1}{\lambda }\) and thus improve the numerical stability.

Bias-Variance Trade-off The bias-variance trade-off for ridge regression is illustrated in Fig. 4.12.

GD Solution

Tailored GD (Sec. 3.4) solution is

\begin{equation} \label {eq-gd-lr-ls} \begin{aligned} \bw _{n+1} &= \bw _{n} - \alpha \nabla \mathcal {L}(\bw )\\ &=\bw _{n} - \frac {\alpha }{M}\left [\bX ^T\left (\bX \bw _n - \by \right ) +\lambda \bw _n\right ]\\ &=\bw _{n}\left (1-\frac {\alpha }{M}\lambda \right ) - \frac {\alpha }{M}\bX ^T\left (\bX \bw _n - \by \right ) \end {aligned} \end{equation}

The \(\alpha \) value is typically chosen such that

\begin{equation} 0.99\gtrsim \left (1-\dfrac {\alpha }{M}\lambda \right )\gtrsim 0.95 \end{equation}

4.8 Bias-Variance Decomposition (*)

The expected prediction error (MSE), taken over all possible training sets and noise realizations, decomposes into three irreducible components:

\begin{equation} \E [(\hat {y}-y)^2] =\left (\E [\hat {y}] - h(\bx )\right )^2 + \Var [\hat {y}] + \sigma ^2 \end{equation}

where \(\left (\mathrm {Bias}[\hat {y}]\right )^2=\left (\E [\hat {y}] - h(\bx )\right )^2\).

Empirical estimate For a specific dataset of \(M\) samples, the MSE can be similarly decomposed:

\begin{equation} \MSE = \frac {1}{M}\sum _{i=1}^M (\hat {y}_i - y_i)^2 = \text {bias}^2_{\text {emp}} + \text {variance}_{\text {emp}} + \text {noise}_{\text {emp}} \end{equation}

where

\begin{align} {\text {bias}^2_{\text {emp}}} &=\left (\bar {\hat {y}} - \bar {h}\right )^2,\qquad \bar {\hat {y}} = \frac {1}{M}\sum _{i=1}^M \hat {y}_i, \quad \bar {h} = \frac {1}{M}\sum _{i=1}^M h(\bx _i)\\ \text {variance}_{\text {emp}} &= \frac {1}{M}\sum _{i=1}^M (\hat {y}_i - \bar {\hat {y}})^2\\ \text {noise}_{\text {emp}} &=\frac {1}{M}\sum _{i=1}^M \epsilon _i^2 \end{align}

4.9 Summary

• • Overfitting and underfitting are two extremes of model complexity: overfitting follows training data too closely, underfitting fails to capture the underlying pattern.

• • Bias-variance trade-off provides the theoretical framework explaining why overfitting (high variance, low bias) and underfitting (high bias, low variance) occur.

• • Cross-validation mitigates data-related issues by evaluating model performance across different data splits, and guides model-related decisions such as hyper-parameter selection.

• • Hyper-parameter tuning (e.g., polynomial degree \(L\), regularization \(\lambda \)) adjusts model complexity to balance underfitting and overfitting.

• • Normalization and standardization are data pre-processing steps that reduce the influence of feature scale imbalance and improve numerical stability.

• • Increasing dataset size directly reduces the data-related gap by making \(\bar {J}_M\) closer to \(\bar {J}_{theory}\), and reduce overfitting in complex models.

• • Regularization constrains model complexity via the penalty parameter \(\lambda \), controlling the bias-variance trade-off from the model side.