{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "erm.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# empirical risk minimization (ERM) \u2014 Python demo\n\nNumerical companion to the entry [empirical risk minimization (ERM)](https://dictionaryofml.org/terms/erm.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nOne block per paragraph of the entry (marked [P...]): each block verifies numerically what the corresponding statement asserts. Self-contained (numpy/matplotlib only), fixed seed.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/erm.py`](https://dictionaryofml.org/terms/erm.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(), \"erm.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nerm.py \u2014 numerical companion to the glossary entry\n'empirical risk minimization (ERM)'.\n\nOne block per paragraph of the entry (marked [P...]): each block verifies\nnumerically what the corresponding statement asserts. Self-contained\n(numpy/matplotlib only), fixed seed.\n\nBlocks\n------\n[P-risk]       The risk of a hypothesis is the expected loss under the\n               data-generating distribution; the ideal choice minimizes\n               the risk (verified on a grid of hypotheses against a\n               large Monte Carlo sample).\n[P-surrogate]  The distribution is unknown; ERM minimizes the\n               sample-average surrogate. As the trainset grows, the\n               risk of the ERM hypothesis approaches the minimal risk\n               (consistency of the surrogate).\n[P-map]        ERM is a map A: trainset -> learned hypothesis. For\n               the linear model with squared error loss the map has a closed\n               form, its output attains the minimal empirical risk, and\n               calling it on different trainsets yields different\n               learned hypotheses.\n[P-fixedpoint] In practice A is computed by an iterative optimization\n               method that is a fixed-point iteration: the GD update\n               operator T has the ERM solution as its fixed point\n               (T(w-hat) = w-hat), and iterating T converges to it.\n\nOutputs\n-------\nerm.png : preview figure (checking only).\n\nData generated by pythondemos/erm.py.\n\"\"\"\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\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\n# data-generating distribution: y = 2 x + 1 + noise, x ~ U(0, 10)\nW_TRUE = np.array([2.0, 1.0])\ndef draw(m):\n    x = rng.uniform(0, 10, m)\n    y = W_TRUE[0] * x + W_TRUE[1] + 0.5 * rng.normal(size=m)\n    return x, y\n\ndef risk(w, mc=200000):                            # expected squared loss\n    x, y = draw(mc)\n    return np.mean((y - w[0] * x - w[1]) ** 2)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-risk]** The risk of a hypothesis is the expected loss under the data-generating distribution; the ideal choice minimizes the risk (verified on a grid of hypotheses against a large Monte Carlo sample)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-risk] risk = expected loss; the ideal hypothesis minimizes it\")\ncands = [np.array([a, b]) for a in (1.5, 2.0, 2.5) for b in (0.0, 1.0)]\nrisks = [risk(w) for w in cands]\nbest = cands[int(np.argmin(risks))]\ncheck(\"the risk-minimizing candidate is the true hypothesis (2, 1)\",\n      np.array_equal(best, W_TRUE))\ncheck(\"its risk equals the noise floor 0.25 (irreducible)\",\n      abs(min(risks) - 0.25) < 0.01)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-surrogate]** The distribution is unknown; ERM minimizes the sample-average surrogate. As the trainset grows, the risk of the ERM hypothesis approaches the minimal risk (consistency of the surrogate)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-surrogate] ERM minimizes the sample-average surrogate\")\ndef erm_fit(m):\n    x, y = draw(m)\n    return np.polyfit(x, y, 1)\nexcess = [np.mean([risk(erm_fit(m)) - 0.25 for _ in range(20)])\n          for m in (5, 50, 500)]\nprint(f\"    excess risk of ERM at m = 5, 50, 500: \"\n      f\"{excess[0]:.4f}, {excess[1]:.4f}, {excess[2]:.5f}\")\ncheck(\"the ERM hypothesis approaches the minimal risk as m grows\",\n      excess[0] > excess[1] > excess[2] > 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-map]** ERM is a map A: trainset -> learned hypothesis. For the linear model with squared error loss the map has a closed form, its output attains the minimal empirical risk, and calling it on different trainsets yields different learned hypotheses."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-map] ERM is a map from trainsets to hypotheses\")\nx1, y1 = draw(30)\nx2, y2 = draw(30)\nA = lambda x, y: np.polyfit(x, y, 1)\nw1, w2 = A(x1, y1), A(x2, y2)\nemp = lambda w, x, y: np.mean((y - w[0] * x - w[1]) ** 2)\ncheck(\"A(D) attains the minimal empirical risk on D (vs perturbations)\",\n      all(emp(w1 + d, x1, y1) > emp(w1, x1, y1)\n          for d in ([0.05, 0], [-0.05, 0], [0, 0.2], [0, -0.2])))\ncheck(\"different trainsets yield different learned hypotheses\",\n      not np.allclose(w1, w2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-fixedpoint]** In practice A is computed by an iterative optimization method that is a fixed-point iteration: the GD update operator T has the ERM solution as its fixed point (T(w-hat) = w-hat), and iterating T converges to it."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-fixedpoint] the optimizer is a fixed-point iteration\")\nX = np.c_[x1, np.ones(30)]\nw_hat = np.linalg.solve(X.T @ X, X.T @ y1)         # ERM solution\nL = 2 * np.linalg.eigvalsh(X.T @ X / 30).max()\nT = lambda w: w - (1 / L) * (2 / 30) * X.T @ (X @ w - y1)   # GD operator\ncheck(\"the ERM solution is a fixed point: T(w-hat) = w-hat\",\n      np.allclose(T(w_hat), w_hat, atol=1e-10))\nw = np.zeros(2)\nfor _ in range(60000):     # ill-conditioned (x vs intercept): slow rate\n    w = T(w)\ncheck(\"iterating T converges to the ERM solution\",\n      np.linalg.norm(w - w_hat) < 1e-5)\n\n# ------------------------------------------------------------ preview\nfig, ax = plt.subplots(figsize=(4.8, 3.2))\nax.loglog([5, 50, 500], excess, \"o-\")\nax.set_xlabel(\"trainset size m\"); ax.set_ylabel(\"excess risk of ERM\")\nax.set_title(\"[P-surrogate] ERM approaches the minimal risk\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"erm.png\", dpi=110)\nprint(f\"\\n{sum(ok for _, ok in report)}/{len(report)} checks passed\")\nassert all(ok for _, ok in report)"
  }
 ]
}