{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "overfitting.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# overfitting \u2014 Python demo\n\nNumerical companion to the entry [overfitting](https://dictionaryofml.org/terms/overfitting.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/overfitting.py`](https://dictionaryofml.org/terms/overfitting.py); CC BY 4.0."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"overfitting.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "#!/usr/bin/env python3\n\"\"\"\noverfitting.py \u2014 Training error vs. validation error over polynomial degree.\n\nThis demo generates the data behind the polynomial-degree figure of the\n\"overfitting\" entry. It illustrates overfitting as a growing gap between a\nsmall training error and a large validation error as the model capacity\n(polynomial degree) increases.\n\nSetup\n-----\nThe true relationship between a scalar feature x and a label y is the\nsinusoid  f(x) = sin(2*pi*x)  on x in [0, 1]. Training sets of m = 5,\nm = 10, and m = 20 data points are drawn uniformly on [0, 1] with\nadditive Gaussian label noise,  y = f(x) + eps,  eps ~ N(0, sigma^2),\nsigma = 0.2. A single validation set of 100 data points is drawn from\nthe same distribution and shared by all three training-set sizes, so\ntheir validation errors are comparable.\n\nFor each polynomial degree p = 0, 1, ..., 9 a polynomial hypothesis is\nlearned by empirical risk minimization under the squared-error loss\n(polynomial fit on the Vandermonde matrix). Degree p = 9 has 10 model\nparameters and interpolates the m = 10 training points exactly; for\nm = 5 every degree p >= 4 already interpolates, while for m = 20 no\ndegree in the sweep can.\n\nOutput\n------\nThree CSV files (committed to the repo) are written to pythondemos/:\n  overfitting_errors.csv      degree,trainerr,valerr   (m = 10)\n  overfitting_errors_m5.csv   degree,trainerr,valerr   (m = 5)\n  overfitting_errors_m20.csv  degree,trainerr,valerr   (m = 20)\n    trainerr \u2014 average squared-error loss on the training set\n    valerr   \u2014 average squared-error loss on the validation set\nFor m = 10 the training error decreases monotonically with the degree\nand reaches (numerically) zero at r = 9, while the validation error\npasses through a minimum at moderate degree and then grows by orders of\nmagnitude: the high-degree polynomials overfit the training set. The\ncomparison across training-set sizes shows the validation error growing\nearlier and further for m = 5 and staying much lower for m = 20 \u2014 the\ngeneralization gap shrinks with the number of training data points. The\nTikZ figure shows one panel of training/validation curves per\ntraining-set size and reads the CSVs via pgfplots (log-scaled y-axis),\nso the LaTeX build does not depend on Python. A matplotlib preview with\nthe same three panels is written to pythondemos/overfitting.png.\n\nReproducibility\n---------------\nThe numpy RNG is seeded from 5 (RNG = default_rng(5)); the extra\ntraining sets of size 5 and 20 use their own seeded generators\n(default_rng(500 + m)), so the m = 10 draws \u2014 and with them the\noriginal overfitting_errors.csv \u2014 are bit-identical to the two-CSV-era\noutput, and re-running produces bit-identical CSVs. Run from the repo\nroot:\n\n    python3 pythondemos/overfitting.py\n\nBlocks\n------\n[B-data]    the sinusoid, the training sets of m = 5, 10, 20 noisy data\n            points, and the shared validation set of 100 data points from\n            the same distribution\n[B-sweep]   ERM with the squared-error loss over polynomials of degree\n            0, ..., 9, for each training-set size: training error falls\n            with the degree, validation error passes through a minimum and\n            then grows \u2014 the earlier and the further, the smaller the\n            training set\n[B-three]   the three collinear points of the first figure: ERM over the\n            constants has a unique solution that meets one point of three,\n            ERM over the linear model is unique and interpolating, and over\n            all continuous functions a whole family attains zero training\n            error, so ERM has no unique solution there\n[B-reg]     the three elementary forms of regularization applied to the\n            overfitting degree-9 fit -- pruning the model, a penalty term on\n            the empirical risk, and augmenting the training set -- each\n            lowering the validation error\n[B-output]  the committed CSV and the matplotlib preview\n\"\"\"\nfrom __future__ import annotations\n\nimport warnings\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nOUTDIR = Path(__file__).resolve().parent\nRNG = np.random.default_rng(5)\n\nM_TRAIN = 10\nM_VAL = 100\nSIGMA = 0.2\nMAX_DEGREE = 9\n\n\ndef f_true(x: np.ndarray) -> np.ndarray:\n    return np.sin(2.0 * np.pi * x)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** the sinusoid, the training sets of m = 5, 10, 20 noisy data points, and the shared validation set of 100 data points from the same distribution"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "x_train = RNG.uniform(0.0, 1.0, M_TRAIN)\ny_train = f_true(x_train) + SIGMA * RNG.standard_normal(M_TRAIN)\nx_val = RNG.uniform(0.0, 1.0, M_VAL)\ny_val = f_true(x_val) + SIGMA * RNG.standard_normal(M_VAL)\n\n# Extra training sets of size 5 and 20 from the same distribution, each\n# with its own seeded generator so the m = 10 draws above stay unchanged.\n# All three sizes share the validation set (x_val, y_val).\ntrain_sets = {M_TRAIN: (x_train, y_train)}\nfor m in (5, 20):\n    g = np.random.default_rng(500 + m)\n    x_m = g.uniform(0.0, 1.0, m)\n    y_m = f_true(x_m) + SIGMA * g.standard_normal(m)\n    train_sets[m] = (x_m, y_m)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-sweep]** ERM with the squared-error loss over polynomials of degree 0, ..., 9, for each training-set size: training error falls with the degree, validation error passes through a minimum and then grows \u2014 the earlier and the further, the smaller the training set"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "degrees = np.arange(MAX_DEGREE + 1)\n\n\ndef sweep(x_tr: np.ndarray, y_tr: np.ndarray) -> tuple[np.ndarray, np.ndarray]:\n    \"\"\"ERM with the squared-error loss over polynomials of each degree.\"\"\"\n    tr = np.empty_like(degrees, dtype=float)\n    va = np.empty_like(degrees, dtype=float)\n    for r in degrees:\n        # For degree p >= len(x_tr) there are more model parameters than\n        # data points, so the minimizer is not unique; the fit still\n        # minimizes the training error \u2014 silence the RankWarning.\n        with np.errstate(all=\"ignore\"), warnings.catch_warnings():\n            warnings.simplefilter(\"ignore\")\n            coeffs = np.polynomial.polynomial.polyfit(x_tr, y_tr, int(r))\n        yhat_train = np.polynomial.polynomial.polyval(x_tr, coeffs)\n        yhat_val = np.polynomial.polynomial.polyval(x_val, coeffs)\n        tr[r] = np.mean((y_tr - yhat_train) ** 2)\n        va[r] = np.mean((y_val - yhat_val) ** 2)\n    # Floor the (numerically zero) training error at high degrees so the\n    # log-scaled pgfplots axis stays finite and readable.\n    return np.maximum(tr, 1e-6), va\n\n\nerrors = {m: sweep(*train_sets[m]) for m in sorted(train_sets)}\ntrainerr, valerr = errors[M_TRAIN]\n\nfor m in sorted(errors):\n    tr, va = errors[m]\n    print(f\"[B-sweep] m = {m}: degree  trainerr      valerr\")\n    for r in degrees:\n        print(f\"{r:>24}  {tr[r]:.3e}  {va[r]:.3e}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-three]** the three collinear points of the first figure: ERM over the constants has a unique solution that meets one point of three, ERM over the linear model is unique and interpolating, and over all continuous functions a whole family attains zero training error, so ERM has no unique solution there"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# The first figure of the entry fits three points that lie on a straight line,\n# using three nested hypothesis spaces. Nothing here is drawn by hand: each\n# claim the paragraph makes is checked numerically.\nx3 = np.array([1.0, 2.0, 3.0])\ny3 = np.array([1.0, 2.0, 3.0])\n\n# H1, the constants h(x) = b. ERM over a constant has the average label as its\n# unique solution, and it cannot reach the outer two points.\nb_hat = float(y3.mean())\nerr_const = float(np.mean((y3 - b_hat) ** 2))\nhit_const = int(np.sum(np.isclose(y3, b_hat)))\n\n# H2, the linear model h(x) = w x + b. Three distinct feature values\n# determine the two model parameters, so the solution is unique; the\n# points lie on one line, so it attains zero training error.\nc_lin = np.polynomial.polynomial.polyfit(x3, y3, 1)\nerr_lin = float(np.mean((y3 - np.polynomial.polynomial.polyval(x3, c_lin)) ** 2))\nrank_lin = int(np.linalg.matrix_rank(np.vander(x3, 2, increasing=True)))\n\n# H3, all continuous functions. Every member of the family\n#   h_c(x) = x + c sin(2 pi (x - 1))\n# is continuous and passes through all three points, whatever c is, so ERM has\n# infinitely many solutions there and the training error cannot choose.\ncs = np.array([0.0, 0.25, 0.55, 1.0, -2.0, 7.5])\nerr_family = np.array([np.mean((y3 - (x3 + c * np.sin(2 * np.pi * (x3 - 1)))) ** 2)\n                       for c in cs])\n\nprint(f\"[B-three] H1 constants:   b = {b_hat:.3f}, trainerr = {err_const:.3f}, \"\n      f\"points met = {hit_const} of 3\")\nprint(f\"[B-three] H2 linear:      rank = {rank_lin} of 2 columns (unique), \"\n      f\"trainerr = {err_lin:.2e}\")\ncs_txt = \", \".join(f\"{c:g}\" for c in cs)\nprint(f\"[B-three] H3 continuous:  trainerr for c = {cs_txt}:\")\nprint(f\"[B-three]                 {np.array2string(err_family, precision=2)}\"\n      f\"  -> all zero, so ERM has no unique solution\")\nassert hit_const == 1 and err_const > 0.5      # the constant underfits\nassert rank_lin == 2 and err_lin < 1e-20       # unique, and interpolating\nassert np.all(err_family < 1e-20)              # a continuum of ERM solutions"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-reg]** the three elementary forms of regularization applied to the overfitting degree-9 fit -- pruning the model, a penalty term on the empirical risk, and augmenting the training set -- each lowering the validation error"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# The degree-9 fit above overfits. Each elementary form of regularization is\n# applied to it in turn, and the validation error is reported. Pruning the\n# model and augmenting the training set reuse what is already above; the\n# penalty term is a ridge solve on the same polynomial fit.\ndeg9_val = float(valerr[MAX_DEGREE])\n\n# 1. pruning the model: search degree 3 rather than degree 9\nc_pruned = np.polynomial.polynomial.polyfit(x_train, y_train, 3)\nval_pruned = float(np.mean(\n    (y_val - np.polynomial.polynomial.polyval(x_val, c_pruned)) ** 2))\n\n# 2. a penalty term on the empirical risk: ridge on the degree-9 coefficients\nV_train = np.vander(x_train, MAX_DEGREE + 1, increasing=True)\nV_val = np.vander(x_val, MAX_DEGREE + 1, increasing=True)\nLAMBDA = 1e-3\nw_ridge = np.linalg.solve(\n    V_train.T @ V_train + LAMBDA * np.eye(MAX_DEGREE + 1), V_train.T @ y_train)\nval_ridge = float(np.mean((y_val - V_val @ w_ridge) ** 2))\n\n# 3. augmenting the training set: more data points from the same distribution\nx_aug = np.concatenate([x_train, RNG.uniform(0.0, 1.0, 90)])\ny_aug = f_true(x_aug) + SIGMA * RNG.standard_normal(x_aug.size)\ny_aug[:M_TRAIN] = y_train                      # keep the original labels\nc_aug = np.polynomial.polynomial.polyfit(x_aug, y_aug, MAX_DEGREE)\nval_aug = float(np.mean(\n    (y_val - np.polynomial.polynomial.polyval(x_val, c_aug)) ** 2))\n\nprint(f\"[B-reg]   degree {MAX_DEGREE}, no regularization: valerr = {deg9_val:.3e}\")\nprint(f\"[B-reg]   pruning the model (degree 3):  valerr = {val_pruned:.3e}\")\nprint(f\"[B-reg]   penalty term (ridge, a={LAMBDA:g}):  valerr = {val_ridge:.3e}\")\nprint(f\"[B-reg]   data augmentation (100 pts):   valerr = {val_aug:.3e}\")\nassert val_pruned < deg9_val                   # each form lowers the val error\nassert val_ridge < deg9_val\nassert val_aug < deg9_val"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-output]** the committed CSV and the matplotlib preview \"\"\" from __future__ import annotations import warnings from pathlib import Path import numpy as np import matplotlib matplotlib.use(\"Agg\") import matplotlib.pyplot as plt"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "csv_names = {5: \"overfitting_errors_m5.csv\",\n             10: \"overfitting_errors.csv\",\n             20: \"overfitting_errors_m20.csv\"}\nfor m, name in csv_names.items():\n    tr, va = errors[m]\n    with (OUTDIR / name).open(\"w\") as fh:\n        fh.write(\"degree,trainerr,valerr\\n\")\n        for r in degrees:\n            fh.write(f\"{r},{tr[r]:.6e},{va[r]:.6e}\\n\")\n\n# One panel per training-set size, sharing the y-axis so the panels are\n# comparable. Grayscale-safe: the two curves of a panel differ in line\n# style AND marker shape, not only in color.\nfig, axes = plt.subplots(1, 3, figsize=(8, 3.0), sharey=True)\nfor ax, m in zip(axes, sorted(errors)):\n    tr, va = errors[m]\n    ax.semilogy(degrees, tr, \"o--\", color=\"black\", markersize=4,\n                label=\"training error\")\n    ax.semilogy(degrees, va, \"s-\", color=\"tab:blue\", markersize=4,\n                label=\"validation error\")\n    ax.set_xlabel(\"degree $p$\")\n    ax.set_title(f\"$m = {m}$\", fontsize=10)\naxes[0].set_ylabel(\"average squared-error loss\")\naxes[2].legend(frameon=False, fontsize=8, loc=\"lower left\")\nfig.suptitle(\"Training vs. validation error per training-set size\",\n             fontsize=10)\nfig.tight_layout()\nfig.savefig(OUTDIR / \"overfitting.png\", dpi=110)\nprint(\"[B-output] wrote overfitting_errors{,_m5,_m20}.csv and overfitting.png\")"
  }
 ]
}