{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "ridgeregression.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# ridge regression \u2014 Python demo\n\nNumerical companion to the entry [ridge regression](https://dictionaryofml.org/terms/ridgeregression.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nRidge regression learns the parameters w of a linear hypothesis by minimizing the average squared error loss on a trainset plus the penalty term alpha ||w||_2^2; its unique minimizer is w_hat = (X^T X + alpha m I)^{-1} X^T y for ANY feature matrix X. The demo runs the method on the entry's application, predicting the maximum temperature of the next day at Krems an der Donau from the 24 hourly temperatures of a day with fewer training days than features, and verifies the entry's claims: the closed form, the failure of plain linear regression when m < d, the SVD shrinkage view with its bound on the noise amplification, the condition number of the penalized normal equations, and the data augmentation interpretation (Bishop 1995). Self-contained (numpy/matplotlib only), fixed seed; the weather data is downloaded from the GeoSphere Austria archive.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/ridgeregression.py`](https://dictionaryofml.org/terms/ridgeregression.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 ridgeregression.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(), \"ridgeregression.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nridgeregression.py \u2014 numerical companion to the glossary entry\n'ridge regression'.\n\nPurpose\n-------\nRidge regression learns the parameters w of a linear hypothesis by\nminimizing the average squared error loss on a trainset plus the penalty\nterm alpha ||w||_2^2; its unique minimizer is w_hat = (X^T X + alpha m\nI)^{-1} X^T y for ANY feature matrix X.  The demo runs the method on the\nentry's application, predicting the maximum temperature of the next day\nat Krems an der Donau from the 24 hourly temperatures of a day with\nfewer training days than features, and verifies the entry's claims:\nthe closed form, the failure of plain linear regression when m < d, the\nSVD shrinkage view with its bound on the noise amplification, the\ncondition number of the penalized normal equations, and the data\naugmentation interpretation (Bishop 1995).  Self-contained\n(numpy/matplotlib only), fixed seed; the weather data is downloaded from\nthe GeoSphere Austria archive.\n\nBlocks\n------\n[B-fetch]    Hourly air temperature (klima-v2-1h, tl) and daily maximum\n             temperature (klima-v2-1d, tlmax) at Krems an der Donau,\n             GeoSphere station 3805, July and August 2024.  A data point\n             is one day: feature vector x = its 24 hourly temperatures\n             (d = 24), label y = the maximum temperature of the next day.\n             Trainset: July 1 to 20 (m = 20 < d); test set: the 31 days\n             of August.\n[B-closed]   alpha = 1: the closed form zeroes the gradient of the\n             penalized objective, the matrix X^T X + alpha m I is\n             invertible although X^T X has rank 20 < 24, and random\n             perturbations of w_hat increase the objective.  Linear\n             regression (the minimum-norm solution of the underdetermined\n             normal equations, one of infinitely many) reproduces the\n             training labels exactly (training MSE 0) and predicts August\n             with MSE 141; ridge regression has training MSE 5.4 and test\n             MSE 8.3.\n[B-svd]      The singular values of X run from 504 down to 0.21; the\n             hourly temperatures at 13:00 and 14:00 have correlation\n             0.93.  The minimum-norm linear-regression solution is\n             sum_j (v_j^T y / lambda_j) u_j; ridge multiplies each term\n             by lambda_j^2 / (lambda_j^2 + alpha m), which lies strictly\n             between 0 and 1; lambda_j / (lambda_j^2 + alpha m) never\n             exceeds 1 / (2 sqrt(alpha m)) = 0.11, where 1 / lambda_j\n             reaches 4.9; the four directions with lambda_j = 0 get\n             weight 0.  Label noise with variance 0.25 moves the\n             linear-regression weights by 1.9 and the ridge weights by\n             0.2 (Euclidean norm).  The condition number of X^T X +\n             alpha m I is below that of X^T X restricted to its range.\n[B-aug]      Augmentation equivalence (Bishop 1995): the average squared\n             error loss over feature perturbations N(x, alpha I) equals\n             the original loss plus exactly alpha ||w||^2 (Monte Carlo),\n             and linear regression on a large augmented trainset\n             recovers the ridge solution.\n[B-figure]   The entry's figure: the 24 weights of the linear-regression\n             and the ridge-regression hypothesis per hour, and the\n             training and test MSE of ridge regression over a grid of\n             alpha.\n\nOutputs\n-------\nridgeregression_krems.csv   : the data points, columns day,h0,...,h23,\n                              next_tmax.\nridgeregression_weights.csv : columns hour,ls,ridge \u2014 the learned\n                              weights per hour.\nridgeregression_alpha.csv   : columns alpha,train,test \u2014 MSE of ridge\n                              regression over the alpha grid.\nridgeregression.png         : 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\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nfrom pathlib import Path\n\nOUT_DIR = Path(__file__).parent\n\nrng = np.random.default_rng(42)\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")\n\n\ndef ridge(Xm, ym, alpha):\n    \"\"\"w_hat = (X^T X + alpha m I)^{-1} X^T y.\"\"\"\n    mm, dd = Xm.shape\n    return np.linalg.solve(Xm.T @ Xm + alpha * mm * np.eye(dd), Xm.T @ ym)\n\n\ndef f_ridge(Xm, ym, alpha, w):\n    \"\"\"The penalized objective (1/m) ||y - X w||^2 + alpha ||w||^2.\"\"\"\n    return np.mean((ym - Xm @ w) ** 2) + alpha * w @ w\n\n\ndef mse(Xm, ym, w):\n    return float(np.mean((Xm @ w - ym) ** 2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-fetch]** Hourly air temperature (klima-v2-1h, tl) and daily maximum temperature (klima-v2-1d, tlmax) at Krems an der Donau, GeoSphere station 3805, July and August 2024. A data point is one day: feature vector x = its 24 hourly temperatures (d = 24), label y = the maximum temperature of the next day. Trainset: July 1 to 20 (m = 20 < d); test set: the 31 days of August."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "BASE = \"https://dataset.api.hub.geosphere.at/v1/station/historical/\"\n\n\ndef fetch(query):\n    with urllib.request.urlopen(BASE + query, timeout=120) as resp:\n        return json.load(resp)\n\n\nhourly = fetch(\"klima-v2-1h?parameters=tl&station_ids=3805\"\n               \"&start=2024-07-01T00:00&end=2024-08-31T23:00\")\ndaily = fetch(\"klima-v2-1d?parameters=tlmax&station_ids=3805\"\n              \"&start=2024-07-01&end=2024-09-01\")\ntl = hourly[\"features\"][0][\"properties\"][\"parameters\"][\"tl\"][\"data\"]\ntmax = daily[\"features\"][0][\"properties\"][\"parameters\"][\"tlmax\"][\"data\"]\ndays = [stamp[:10] for stamp in daily[\"timestamps\"]]\ncheck(\"[B-fetch] 62 days of 24 hourly temperatures and 63 daily maxima\",\n      len(tl) == 62 * 24 and len(tmax) == 63)\ncheck(\"[B-fetch] no value is missing\",\n      all(t is not None for t in tl) and all(t is not None for t in tmax))\nX_all = np.array(tl, dtype=float).reshape(62, 24)     # one row per day\ny_all = np.array(tmax[1:], dtype=float)               # next day's maximum\nwith open(OUT_DIR / \"ridgeregression_krems.csv\", \"w\") as f:\n    f.write(\"day,\" + \",\".join(f\"h{k}\" for k in range(24)) + \",next_tmax\\n\")\n    for day, row, lab in zip(days, X_all, y_all):\n        f.write(day + \",\" + \",\".join(f\"{v:.1f}\" for v in row) + f\",{lab:.1f}\\n\")\nm, d = 20, 24\nX, y = X_all[:m], y_all[:m]                           # July 1 to 20\nX_test, y_test = X_all[31:62], y_all[31:62]           # August 1 to 31\ncheck(\"[B-fetch] trainset July 1-20 (m = 20 < d = 24), test set August (31 days)\",\n      X.shape == (20, 24) and days[0] == \"2024-07-01\" and days[19] == \"2024-07-20\"\n      and X_test.shape == (31, 24) and days[31] == \"2024-08-01\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-closed]** alpha = 1: the closed form zeroes the gradient of the penalized objective, the matrix X^T X + alpha m I is invertible although X^T X has rank 20 < 24, and random perturbations of w_hat increase the objective. Linear regression (the minimum-norm solution of the underdetermined normal equations, one of infinitely many) reproduces the training labels exactly (training MSE 0) and predicts August with MSE 141; ridge regression has training MSE 5.4 and test MSE 8.3."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "ALPHA = 1.0\nw_hat = ridge(X, y, ALPHA)\ngrad = -(2.0 / m) * X.T @ (y - X @ w_hat) + 2.0 * ALPHA * w_hat\ncheck(\"[B-closed] the closed form satisfies the zero-gradient condition of the penalized objective\",\n      np.allclose(grad, 0.0))\ncheck(\"[B-closed] random perturbations of w_hat increase the objective\",\n      all(f_ridge(X, y, ALPHA, w_hat + 0.1 * rng.normal(size=d))\n          > f_ridge(X, y, ALPHA, w_hat) for _ in range(20)))\nlam_min = np.linalg.eigvalsh(X.T @ X + ALPHA * m * np.eye(d)).min()\ncheck(\"[B-closed] X^T X has rank 20 < 24, and X^T X + alpha m I is invertible \"\n      \"(smallest eigenvalue >= alpha m)\",\n      np.linalg.matrix_rank(X.T @ X) == 20 and lam_min >= ALPHA * m - 1e-9)\nw_ls = np.linalg.pinv(X) @ y                          # minimum-norm solution\nnull_dir = np.linalg.svd(X)[2][-1]                    # a null-space direction\ncheck(\"[B-closed] the normal equations of linear regression are underdetermined: \"\n      \"two different solutions reproduce the training labels\",\n      np.allclose(X @ w_ls, y) and np.allclose(X @ (w_ls + 5.0 * null_dir), y))\nmse_ls_train, mse_ls_test = mse(X, y, w_ls), mse(X_test, y_test, w_ls)\nmse_r_train, mse_r_test = mse(X, y, w_hat), mse(X_test, y_test, w_hat)\ncheck(f\"[B-closed] linear regression: training MSE {mse_ls_train:.1f}, \"\n      f\"test MSE {mse_ls_test:.0f}\",\n      round(mse_ls_train, 1) == 0.0 and round(mse_ls_test) == 141)\ncheck(f\"[B-closed] ridge regression (alpha = 1): training MSE {mse_r_train:.1f}, \"\n      f\"test MSE {mse_r_test:.1f}\",\n      round(mse_r_train, 1) == 5.4 and round(mse_r_test, 1) == 8.3)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-svd]** The singular values of X run from 504 down to 0.21; the hourly temperatures at 13:00 and 14:00 have correlation 0.93. The minimum-norm linear-regression solution is sum_j (v_j^T y / lambda_j) u_j; ridge multiplies each term by lambda_j^2 / (lambda_j^2 + alpha m), which lies strictly between 0 and 1; lambda_j / (lambda_j^2 + alpha m) never exceeds 1 / (2 sqrt(alpha m)) = 0.11, where 1 / lambda_j reaches 4.9; the four directions with lambda_j = 0 get weight 0. Label noise with variance 0.25 moves the linear-regression weights by 1.9 and the ridge weights by 0.2 (Euclidean norm). The condition number of X^T X + alpha m I is below that of X^T X restricted to its range."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "Vf, sv, Ut = np.linalg.svd(X, full_matrices=False)   # X is 20 x 24, rank 20\ncorr_13_14 = float(np.corrcoef(X_all[:, 13], X_all[:, 14])[0, 1])\ncheck(f\"[B-svd] singular values from {sv[0]:.0f} down to {sv[-1]:.2f}; the \"\n      f\"temperatures at 13:00 and 14:00 have correlation {corr_13_14:.2f}\",\n      round(sv[0]) == 504 and round(sv[-1], 2) == 0.21 and round(corr_13_14, 2) == 0.93)\ncoords = Vf.T @ y                                     # (v^(j))^T y\ncheck(\"[B-svd] minimum-norm linear-regression solution = sum_j (v_j^T y / lambda_j) u_j\",\n      np.allclose(Ut.T @ (coords / sv), w_ls))\nfactor = sv ** 2 / (sv ** 2 + ALPHA * m)\ncheck(\"[B-svd] ridge solution = shrinkage factor times each linear-regression term\",\n      np.allclose(Ut.T @ (factor * coords / sv), w_hat))\ncheck(\"[B-svd] shrinkage factors lie strictly between 0 and 1\",\n      np.all((factor > 0.0) & (factor < 1.0)))\nbound = 1.0 / (2.0 * np.sqrt(ALPHA * m))\namp_ridge, amp_ls = (sv / (sv ** 2 + ALPHA * m)).max(), (1.0 / sv).max()\ncheck(f\"[B-svd] lambda / (lambda^2 + alpha m) <= 1 / (2 sqrt(alpha m)) = {bound:.2f}, \"\n      f\"where 1 / lambda reaches {amp_ls:.1f}\",\n      amp_ridge <= bound + 1e-12 and round(bound, 2) == 0.11 and round(amp_ls, 1) == 4.9)\nU_all = np.linalg.svd(X)[2]                           # all 24 right singular vectors\ncheck(\"[B-svd] ridge puts zero weight on the four directions with lambda_j = 0\",\n      np.allclose(U_all[20:] @ w_hat, 0.0))\nnoise = 0.5 * rng.normal(size=m)\nmove_ls = float(np.linalg.norm(np.linalg.pinv(X) @ (y + noise) - w_ls))\nmove_r = float(np.linalg.norm(ridge(X, y + noise, ALPHA) - w_hat))\ncheck(f\"[B-svd] label noise with variance 0.25 moves the linear-regression \"\n      f\"weights by {move_ls:.1f} and the ridge weights by {move_r:.1f}\",\n      round(move_ls, 1) == 1.9 and round(move_r, 1) == 0.2)\ncond_ridge = (sv[0] ** 2 + ALPHA * m) / (sv[-1] ** 2 + ALPHA * m)\ncond_ls = sv[0] ** 2 / sv[-1] ** 2\ncheck(f\"[B-svd] condition number {cond_ridge:.0f} of X^T X + alpha m I is below \"\n      f\"{cond_ls:.0f}, that of X^T X on its range\", cond_ridge < cond_ls)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-aug]** Augmentation equivalence (Bishop 1995): the average squared error loss over feature perturbations N(x, alpha I) equals the original loss plus exactly alpha ||w||^2 (Monte Carlo), and linear regression on a large augmented trainset recovers the ridge solution."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "n_mc = 200_000\nw_probe = rng.normal(size=d)\nr = 0\neps = np.sqrt(ALPHA) * rng.normal(size=(n_mc, d))\nloss_orig = (y[r] - X[r] @ w_probe) ** 2\nloss_pert = np.mean((y[r] - (X[r] + eps) @ w_probe) ** 2)\nexcess = float(ALPHA * w_probe @ w_probe)\nstd_err = np.sqrt(2.0 * excess ** 2 + 4.0 * loss_orig * excess) / np.sqrt(n_mc)\ncheck(\"[B-aug] average loss over perturbed copies = original loss + alpha ||w||^2 \"\n      \"within four standard errors (Monte Carlo)\",\n      abs(loss_pert - loss_orig - excess) < 4.0 * std_err)\nn_fit = 3000\nX_aug = np.repeat(X, n_fit, axis=0) + np.sqrt(ALPHA) * rng.normal(size=(m * n_fit, d))\ny_aug = np.repeat(y, n_fit)                           # labels left unchanged\nw_aug = np.linalg.lstsq(X_aug, y_aug, rcond=None)[0]\ncheck(\"[B-aug] linear regression on the augmented trainset recovers the ridge solution\",\n      np.allclose(w_aug, w_hat, atol=5e-2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-figure]** The entry's figure: the 24 weights of the linear-regression and the ridge-regression hypothesis per hour, and the training and test MSE of ridge regression over a grid of alpha."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "with open(OUT_DIR / \"ridgeregression_weights.csv\", \"w\") as f:\n    f.write(\"hour,ls,ridge\\n\")\n    for k in range(d):\n        f.write(f\"{k},{w_ls[k]:.3f},{w_hat[k]:.3f}\\n\")\nalphas = np.logspace(-3, 2, 26)\ncurve = [(a, mse(X, y, ridge(X, y, a)), mse(X_test, y_test, ridge(X, y, a)))\n         for a in alphas]\nwith open(OUT_DIR / \"ridgeregression_alpha.csv\", \"w\") as f:\n    f.write(\"alpha,train,test\\n\")\n    for a, tr, te in curve:\n        f.write(f\"{a:.5g},{tr:.3f},{te:.3f}\\n\")\nbest = min(curve, key=lambda c: c[2])\ncheck(f\"[B-figure] weights and the alpha grid written; test MSE is smallest at \"\n      f\"alpha = {best[0]:.3g} ({best[2]:.1f})\",\n      len(curve) == 26 and w_ls.max() > 4.0 and abs(w_hat).max() < 0.5)\n\n# ---- preview (checking only)\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))\nhours = np.arange(d)\nax1.plot(hours, w_ls, \"k--o\", lw=1, ms=4, mfc=\"none\", label=\"linear regression\")\nax1.plot(hours, w_hat, \"k-\", lw=1.8, marker=\".\", label=r\"ridge regression, $\\alpha = 1$\")\nax1.axhline(0.0, color=\"0.7\", lw=0.8)\nax1.set_xlabel(\"hour of the day $j$\")\nax1.set_ylabel(\"weight $w_j$\")\nax1.set_title(\"Krems: 24 weights learned from 20 days\")\nax1.legend(frameon=False, fontsize=8)\nax2.loglog(alphas, [c[1] for c in curve], \"k--\", lw=1.2, label=\"training MSE\")\nax2.loglog(alphas, [c[2] for c in curve], \"k-\", lw=1.8, label=\"test MSE (August)\")\nax2.set_xlabel(r\"regularization parameter $\\alpha$\")\nax2.set_ylabel(\"MSE\")\nax2.set_title(\"Ridge regression: error over alpha\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"ridgeregression.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)"
  }
 ]
}