{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "highdimregime.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# high-dimensional regime \u2014 Python demo\n\nNumerical companion to the entry [high-dimensional regime](https://dictionaryofml.org/terms/highdimregime.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nNumerical companion to the glossary entry 'highdimregime' (high-dimensional regime). A linear model predicts the maximum daytime temperature of a day at Krems (GeoSphere station 3805) from the maximum daytime temperatures of the previous d days. The training set holds m = 30 days of 2023, the validation set the 366 days of 2024. The feature count d runs from 1 to 60, so it crosses the sample size m. For d < m the hypothesis learned by least squares has a training error of the same order as its validation error. At d = m the feature matrix has rank m, the learned hypothesis interpolates the training set, the training error is zero, and the validation error is three orders of magnitude above the training error at d = 1: the training error has stopped saying anything about the loss on days outside the training set. Two routes restore a usable method on the same features, and the demo recomputes both: a penalty term (ridge regression with a fixed regularization parameter) and dimensionality reduction (least squares on the first five principal directions of the training features).\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/highdimregime.py`](https://dictionaryofml.org/terms/highdimregime.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 highdimregime.py` (B102,B307,B602,B605 are the exec, eval and shell checks of [bandit](https://bandit.readthedocs.io/)) reports nothing: the script runs no shell command and evaluates no generated code."
  },
  {
   "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(), \"highdimregime.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"The high-dimensional regime at Krems an der Donau: thirty training days\nand up to sixty features, with the training error collapsing to zero and the\nvalidation error exploding as the feature count reaches the sample size.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'highdimregime' (high-dimensional\nregime).  A linear model predicts the maximum daytime temperature of a day\nat Krems (GeoSphere station 3805) from the maximum daytime temperatures of\nthe previous d days.  The training set holds m = 30 days of 2023, the\nvalidation set the 366 days of 2024.  The feature count d runs from 1 to\n60, so it crosses the sample size m.  For d < m the hypothesis learned by\nleast squares has a training error of the same order as its validation\nerror.  At d = m the feature matrix has rank m, the learned hypothesis\ninterpolates the training set, the training error is zero, and the\nvalidation error is three orders of magnitude above the training error at\nd = 1: the training error has stopped saying anything about the loss on\ndays outside the training set.  Two routes restore a usable method on the\nsame features, and the demo recomputes both: a penalty term (ridge\nregression with a fixed regularization parameter) and dimensionality\nreduction (least squares on the first five principal directions of the\ntraining features).\n\nSelf-contained (numpy and matplotlib only), fixed seeds; the GeoSphere\ndownload falls back to the committed CSV.\n\nBlocks\n------\n[B-data]     Daily maximum temperature at Krems for 2023 and 2024 (731\n             days, no missing value).\n[B-split]    The m = 30 training days, drawn from the 2023 days that have\n             60 earlier days on record, and the 366 validation days of\n             2024.\n[B-leastsq]  Training and validation error of the least-squares hypothesis\n             for every feature count d = 1, ..., 60.\n[B-interp]   At d = m the rank of the feature matrix is m, the training\n             error is zero, and the minimum-norm solution has a large\n             Euclidean norm.\n[B-restore]  A penalty term and dimensionality reduction keep the\n             validation error below 23 squared degrees at every d.\n\nOutputs\n-------\nhighdimregime_weather.csv  : date, tmax for 2023 and 2024 (committed copy).\nhighdimregime_errors.csv   : d, training error, the same clipped at 1e-3\n                             for a logarithmic axis, validation error of\n                             least squares.\nhighdimregime_restored.csv : d, validation error of least squares, of ridge\n                             regression, and after dimensionality reduction.\nhighdimregime.png          : matplotlib preview (checking only).\n\"\"\"\n\n# /// script\n# requires-python = \">=3.10\"\n# dependencies = [\"matplotlib==3.10.7\", \"numpy==2.3.4\"]\n# ///\n\nimport json\nimport urllib.request\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nOUT_DIR = Path(__file__).parent\n\nDMAX = 60          # largest feature count\nSAMPLESIZE = 30    # m, the number of training days\nREGPARAM = 100.0   # alpha, the regularization parameter of ridge regression\nKEPTDIM = 5        # d', the number of kept principal directions\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** Daily maximum temperature at Krems for 2023 and 2024 (731 days, no missing value)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-data] daily maximum temperature at Krems, 2023 and 2024\")\nURL = (\"https://dataset.api.hub.geosphere.at/v1/station/historical/\"\n       \"klima-v2-1d?parameters=tlmax&station_ids=3805\"\n       \"&start=2023-01-01&end=2024-12-31\")\nCSV = OUT_DIR / \"highdimregime_weather.csv\"\ntry:\n    with urllib.request.urlopen(URL, timeout=120) as resp:\n        payload = json.load(resp)\n    params = payload[\"features\"][0][\"properties\"][\"parameters\"]\n    records = [(stamp[:10], hi)\n               for stamp, hi in zip(payload[\"timestamps\"],\n                                    params[\"tlmax\"][\"data\"])]\n    with open(CSV, \"w\") as fh:\n        fh.write(\"date,tmax\\n\")\n        for day, hi in records:\n            fh.write(f\"{day},{hi}\\n\")\n    print(f\"    downloaded {len(records)} days\")\nexcept OSError as err:\n    print(f\"    download failed ({err}); reading the committed CSV\")\n    rows = CSV.read_text().strip().splitlines()[1:]\n    records = [(d, float(a)) for d, a in (r.split(\",\") for r in rows)]\n\ncheck(\"[B-data] 731 days for 2023 and 2024\", len(records) == 731)\ncheck(\"[B-data] no day is missing its maximum temperature\",\n      all(hi is not None for _, hi in records))\ntmax = np.array([hi for _, hi in records], dtype=float)\nday23 = np.array([d.startswith(\"2023\") for d, _ in records])\ncheck(f\"[B-data] the maxima range from {tmax.min():.1f} to {tmax.max():.1f} \"\n      f\"degrees Celsius\", -20.0 < tmax.min() < tmax.max() < 45.0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-split]** The m = 30 training days, drawn from the 2023 days that have 60 earlier days on record, and the 366 validation days of 2024."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-split] the training days of 2023 and the validation days of 2024\")\ncandidates = np.arange(DMAX, int(day23.sum()))   # 2023 days with 60 lags\nrng = np.random.default_rng(2026)\ntrain_idx = np.sort(rng.choice(candidates, size=SAMPLESIZE, replace=False))\nval_idx = np.arange(int(day23.sum()), len(tmax))\ncheck(f\"[B-split] {len(train_idx)} training days of 2023, the first \"\n      f\"{records[train_idx[0]][0]} and the last {records[train_idx[-1]][0]}\",\n      len(train_idx) == SAMPLESIZE and len(set(train_idx.tolist())) == SAMPLESIZE)\ncheck(f\"[B-split] {len(val_idx)} validation days, the 366 days of 2024\",\n      len(val_idx) == 366 and records[val_idx[0]][0] == \"2024-01-01\")\ncheck(\"[B-split] no day belongs to both sets\",\n      not set(train_idx.tolist()) & set(val_idx.tolist()))\ncheck(f\"[B-split] every training day has {DMAX} earlier days on record\",\n      train_idx.min() >= DMAX)\n\n\ndef features(idx, nr_features):\n    \"\"\"The maxima of the nr_features days before each day in idx.\"\"\"\n    return np.column_stack([tmax[idx - lag]\n                            for lag in range(1, nr_features + 1)])\n\n\ndef mean_sqerr(idx, weights, nr_features):\n    residual = tmax[idx] - features(idx, nr_features) @ weights\n    return float(np.mean(residual ** 2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-leastsq]** Training and validation error of the least-squares hypothesis for every feature count d = 1, ..., 60."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-leastsq] least squares for every feature count d = 1, ..., 60\")\ndims = np.arange(1, DMAX + 1)\ntrainerr = np.empty(DMAX)\nvalerr = np.empty(DMAX)\nsolnorm = np.empty(DMAX)\nranks = np.empty(DMAX, dtype=int)\nfor i, d in enumerate(dims):\n    Xtrain = features(train_idx, d)\n    what = np.linalg.lstsq(Xtrain, tmax[train_idx], rcond=None)[0]\n    trainerr[i] = mean_sqerr(train_idx, what, d)\n    valerr[i] = mean_sqerr(val_idx, what, d)\n    solnorm[i] = float(np.linalg.norm(what))\n    ranks[i] = int(np.linalg.matrix_rank(Xtrain))\n\ncheck(f\"[B-leastsq] d = 1 (yesterday alone): training error \"\n      f\"{trainerr[0]:.2f}, validation error {valerr[0]:.2f} squared degrees\",\n      abs(trainerr[0] - valerr[0]) < 3.0)\ncheck(f\"[B-leastsq] the training error decreases with d, from \"\n      f\"{trainerr[0]:.2f} at d = 1 to {trainerr[SAMPLESIZE - 2]:.2f} at \"\n      f\"d = {SAMPLESIZE - 1}\", np.all(np.diff(trainerr[:SAMPLESIZE]) < 1e-9))\ncheck(f\"[B-leastsq] d = {SAMPLESIZE - 1}: training error \"\n      f\"{trainerr[SAMPLESIZE - 2]:.2f}, validation error \"\n      f\"{valerr[SAMPLESIZE - 2]:.1f} squared degrees\",\n      valerr[SAMPLESIZE - 2] > 20 * trainerr[SAMPLESIZE - 2])\ncheck(f\"[B-leastsq] the validation error is smallest at d = \"\n      f\"{dims[valerr.argmin()]} with {valerr.min():.2f} squared degrees\",\n      dims[valerr.argmin()] < SAMPLESIZE)\ncheck(f\"[B-leastsq] the validation error is largest at d = \"\n      f\"{dims[valerr.argmax()]} with {valerr.max():.0f} squared degrees\",\n      dims[valerr.argmax()] == SAMPLESIZE)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-interp]** At d = m the rank of the feature matrix is m, the training error is zero, and the minimum-norm solution has a large Euclidean norm."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-interp] interpolation of the training set at d = m\")\nat_m = SAMPLESIZE - 1\ncheck(f\"[B-interp] the rank of the feature matrix is min(d, m): \"\n      f\"{ranks[0]} at d = 1, {ranks[at_m]} at d = {SAMPLESIZE}, \"\n      f\"{ranks[-1]} at d = {DMAX}\",\n      np.all(ranks == np.minimum(dims, SAMPLESIZE)))\ncheck(f\"[B-interp] at d = m = {SAMPLESIZE} the training error is \"\n      f\"{trainerr[at_m]:.2e}, zero up to rounding, so the learned \"\n      f\"hypothesis interpolates the training set\", trainerr[at_m] < 1e-20)\ncheck(f\"[B-interp] every d from {SAMPLESIZE} to {DMAX} interpolates the \"\n      f\"training set\", np.all(trainerr[at_m:] < 1e-18))\ncheck(f\"[B-interp] at d = m the validation error is {valerr[at_m]:.0f} \"\n      f\"squared degrees, {valerr[at_m] / valerr[0]:.0f} times the \"\n      f\"validation error {valerr[0]:.2f} at d = 1\",\n      valerr[at_m] > 1000 * valerr[0])\ncheck(f\"[B-interp] the minimum-norm solution grows from \"\n      f\"{solnorm[0]:.2f} at d = 1 to {solnorm[at_m]:.1f} at d = m\",\n      solnorm[at_m] > 10 * solnorm[0])"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-restore]** A penalty term and dimensionality reduction keep the validation error below 23 squared degrees at every d."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-restore] a penalty term and dimensionality reduction\")\nridgeerr = np.empty(DMAX)\npcaerr = np.empty(DMAX)\nfor i, d in enumerate(dims):\n    Xtrain = features(train_idx, d)\n    ytrain = tmax[train_idx]\n    ridge = np.linalg.solve(Xtrain.T @ Xtrain + REGPARAM * np.eye(d),\n                            Xtrain.T @ ytrain)\n    ridgeerr[i] = mean_sqerr(val_idx, ridge, d)\n    kept = min(KEPTDIM, d)\n    basis = np.linalg.svd(Xtrain, full_matrices=False)[2][:kept].T\n    coeff = np.linalg.lstsq(Xtrain @ basis, ytrain, rcond=None)[0]\n    pcaerr[i] = mean_sqerr(val_idx, basis @ coeff, d)\n\ncheck(f\"[B-restore] ridge regression with alpha = {REGPARAM:.0f} keeps the \"\n      f\"validation error between {ridgeerr.min():.1f} and \"\n      f\"{ridgeerr.max():.1f} squared degrees over all 60 feature counts\",\n      ridgeerr.max() < 23.0)\ncheck(f\"[B-restore] least squares on the first {KEPTDIM} principal \"\n      f\"directions keeps it between {pcaerr.min():.1f} and \"\n      f\"{pcaerr.max():.1f}\", pcaerr.max() < 23.0)\ncheck(f\"[B-restore] at d = m both stay near their value at d = 1: ridge \"\n      f\"{ridgeerr[at_m]:.1f} against {ridgeerr[0]:.1f}, reduced \"\n      f\"{pcaerr[at_m]:.1f} against {pcaerr[0]:.1f}\",\n      ridgeerr[at_m] < 3 * ridgeerr[0] and pcaerr[at_m] < 3 * pcaerr[0])\ncheck(f\"[B-restore] at d = m both are below the least-squares validation \"\n      f\"error {valerr[at_m]:.0f} by a factor above 500\",\n      valerr[at_m] / max(ridgeerr[at_m], pcaerr[at_m]) > 500.0)\nXm = features(train_idx, SAMPLESIZE)\nridge_m = np.linalg.solve(Xm.T @ Xm + REGPARAM * np.eye(SAMPLESIZE),\n                          Xm.T @ tmax[train_idx])\nbasis_m = np.linalg.svd(Xm, full_matrices=False)[2][:KEPTDIM].T\ncoeff_m = np.linalg.lstsq(Xm @ basis_m, tmax[train_idx], rcond=None)[0]\ncheck(f\"[B-restore] at d = m neither route interpolates the training set: \"\n      f\"training error {mean_sqerr(train_idx, ridge_m, SAMPLESIZE):.2f} with \"\n      f\"the penalty term and \"\n      f\"{mean_sqerr(train_idx, basis_m @ coeff_m, SAMPLESIZE):.2f} after the \"\n      f\"reduction, against {trainerr[at_m]:.2e} for least squares\",\n      min(mean_sqerr(train_idx, ridge_m, SAMPLESIZE),\n          mean_sqerr(train_idx, basis_m @ coeff_m, SAMPLESIZE)) > 1.0)\n\n\n# ---- CSVs and preview\nFLOOR = 1e-3   # a log axis cannot draw a zero training error\nwith open(OUT_DIR / \"highdimregime_errors.csv\", \"w\") as fh:\n    fh.write(\"d,trainerr,trainplot,valerr\\n\")\n    for i, d in enumerate(dims):\n        fh.write(f\"{d},{trainerr[i]:.6g},{max(trainerr[i], FLOOR):.6g},\"\n                 f\"{valerr[i]:.6g}\\n\")\nwith open(OUT_DIR / \"highdimregime_restored.csv\", \"w\") as fh:\n    fh.write(\"d,leastsquares,ridge,reduced\\n\")\n    for i, d in enumerate(dims):\n        fh.write(f\"{d},{valerr[i]:.6g},{ridgeerr[i]:.6g},{pcaerr[i]:.6g}\\n\")\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))\nax1.semilogy(dims, np.maximum(trainerr, FLOOR), \"k-\", lw=1.1,\n             label=f\"training error (at {FLOOR:g} where it is zero)\")\nax1.semilogy(dims, valerr, \"k--\", lw=1.1, label=\"validation error\")\nax1.axvline(SAMPLESIZE, color=\"black\", ls=\":\", lw=0.9,\n            label=f\"d = m = {SAMPLESIZE}\")\nax1.set_xlabel(\"number d of features\")\nax1.set_ylabel(\"average squared error loss\")\nax1.set_title(\"the gap opens as d reaches m\")\nax1.legend(frameon=False, fontsize=8)\nax2.semilogy(dims, valerr, \"k--\", lw=1.1, label=\"least squares\")\nax2.semilogy(dims, ridgeerr, \"k-\", lw=1.1,\n             label=f\"penalty term, alpha = {REGPARAM:.0f}\")\nax2.semilogy(dims, pcaerr, \"k:\", lw=1.3,\n             label=f\"reduced to {KEPTDIM} directions\")\nax2.set_xlabel(\"number d of features\")\nax2.set_ylabel(\"validation error\")\nax2.set_title(\"two routes keep the method usable\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"highdimregime.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}