{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "hypospace.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# hypothesis space \u2014 Python demo\n\nNumerical companion to the entry [hypothesis space](https://dictionaryofml.org/terms/hypospace.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/hypospace.py`](https://dictionaryofml.org/terms/hypospace.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(), \"hypospace.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nhypospace.py \u2014 numerical companion to the glossary entry\n'hypothesis space'.\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-def]      The hypothesis space is the committed set of candidate maps,\n             a subset of Y^X: for |X| = 4, |Y| = 2 the full map space has\n             16 elements, the threshold subset only 5.\n[P-examples] Canonical hypothesis spaces: the linear model (linear maps\n             R^d -> R closed under evaluation) and the set of maps\n             realizable by a fixed ANN architecture as its parameters\n             vary (different parameters, different maps; same\n             architecture).\n[P-design]   The choice of H trades computation against the number of\n             data points: with m = 15 points, raising the polynomial\n             degree (larger H) drives the error on the trainset down but\n             the error on fresh data points up \u2014 the overfitting limit on\n             the usable size of H.\n[P-size]     The size of H anticipates generalization BEFORE training:\n             the maximal generalization gap over H grows with the\n             cardinality |H| (finite classes of random threshold maps).\n[P-algos]    The same H serves different algorithms: ERM on a fixed\n             training set, online learning over a stream, and Bayesian inference (a\n             posterior over a finite H) all operate on one linear\n             hypothesis space; ERM and online learning agree in the limit,\n             the posterior concentrates on the same hypothesis.\n\nOutputs\n-------\nhypospace.png : preview figure (checking only).\n\nData generated by pythondemos/hypospace.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\nfrom itertools import product\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}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-def]** The hypothesis space is the committed set of candidate maps, a subset of Y^X: for |X| = 4, |Y| = 2 the full map space has 16 elements, the threshold subset only 5."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-def] H is a subset of Y^X\")\nX_space, Y_space = [0, 1, 2, 3], [0, 1]\nall_maps = set(product(Y_space, repeat=4))\nH_thresh = {tuple(int(x >= t) for x in X_space) for t in range(5)}\ncheck(\"|Y^X| = 16\", len(all_maps) == 16)\ncheck(\"H (threshold maps) is a strict subset of Y^X\",\n      H_thresh < all_maps)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-examples]** Canonical hypothesis spaces: the linear model (linear maps R^d -> R closed under evaluation) and the set of maps realizable by a fixed ANN architecture as its parameters vary (different parameters, different maps; same architecture)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-examples] linear model and fixed-architecture ANN as H\")\nw1, w2 = rng.normal(size=3), rng.normal(size=3)\nx = rng.normal(size=3)\ncheck(\"linear model: every parameter vector w defines the map x -> w^T x\",\n      np.isclose(w1 @ x, np.sum(w1 * x)))\nrelu = lambda a: np.maximum(a, 0)\nann = lambda W, v, xx: v @ relu(W @ xx)           # fixed 3-8-1 architecture\nW_a, v_a = rng.normal(size=(8, 3)), rng.normal(size=8)\nW_b, v_b = rng.normal(size=(8, 3)), rng.normal(size=8)\ncheck(\"fixed ANN architecture: different parameters realize different maps\",\n      not np.isclose(ann(W_a, v_a, x), ann(W_b, v_b, x)))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-design]** The choice of H trades computation against the number of data points: with m = 15 points, raising the polynomial degree (larger H) drives the error on the trainset down but the error on fresh data points up \u2014 the overfitting limit on the usable size of H."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-design] larger H overfits a small trainset\")\nm = 15\nxd = np.sort(rng.uniform(-1, 1, m))\nyd = np.sin(2.5 * xd) + 0.15 * rng.normal(size=m)\nxv = rng.uniform(-1, 1, 200)\nyv = np.sin(2.5 * xv) + 0.15 * rng.normal(size=200)\ntr_err, va_err = [], []\nfor deg in (1, 3, 12):\n    c = np.polyfit(xd, yd, deg)\n    tr_err.append(np.mean((yd - np.polyval(c, xd)) ** 2))\n    va_err.append(np.mean((yv - np.polyval(c, xv)) ** 2))\nprint(f\"    train err deg 1,3,12: {tr_err[0]:.3f}, {tr_err[1]:.3f}, \"\n      f\"{tr_err[2]:.4f} | val err: {va_err[0]:.3f}, {va_err[1]:.3f}, \"\n      f\"{va_err[2]:.1f}\")\ncheck(\"the error on the trainset decreases with the size of H\",\n      tr_err[0] > tr_err[1] > tr_err[2])\ncheck(\"the error on fresh data points blows up for the largest H (overfitting)\",\n      va_err[2] > 5 * va_err[1])"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-size]** The size of H anticipates generalization BEFORE training: the maximal generalization gap over H grows with the cardinality |H| (finite classes of random threshold maps)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-size] the size of H bounds the gap before training\")\nmg = 60\nxg_tr, xg_va = rng.uniform(0, 1, mg), rng.uniform(0, 1, 1000)\nyg_tr = (xg_tr > 0.5).astype(float)\nyg_va = (xg_va > 0.5).astype(float)\ndef max_gap(n_hypos):\n    ts = rng.uniform(0, 1, n_hypos)               # random threshold class\n    gaps = [abs(np.mean((xg_tr > t) != yg_tr)\n                - np.mean((xg_va > t) != yg_va)) for t in ts]\n    return max(gaps)\ngaps = [np.mean([max_gap(n) for _ in range(30)]) for n in (2, 16, 256)]\nprint(f\"    max train-val gap for |H| = 2, 16, 256: \"\n      f\"{gaps[0]:.3f}, {gaps[1]:.3f}, {gaps[2]:.3f}\")\ncheck(\"the maximal gap over H grows with |H|\", gaps[0] < gaps[1] < gaps[2])"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[P-algos]** The same H serves different algorithms: ERM on a fixed training set, online learning over a stream, and Bayesian inference (a posterior over a finite H) all operate on one linear hypothesis space; ERM and online learning agree in the limit, the posterior concentrates on the same hypothesis."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[P-algos] one H, three algorithms\")\nmt = 200\nXa = rng.normal(size=(mt, 2))\nw_true = np.array([1.0, -0.5])\nya = Xa @ w_true + 0.1 * rng.normal(size=mt)\nw_erm = np.linalg.lstsq(Xa, ya, rcond=None)[0]    # ERM on a fixed training set\nw_og = np.zeros(2)                                # online learning on the stream\nfor t in range(mt):\n    w_og += 0.05 * (ya[t] - w_og @ Xa[t]) * Xa[t]\nH_fin = [w_true, np.array([0.0, 0.0]), np.array([-1.0, 0.5]),\n         np.array([1.0, 0.5])]                    # finite H for Bayes\nlog_post = np.array([-np.sum((ya - Xa @ w) ** 2) / (2 * 0.1**2)\n                     for w in H_fin])\npost = np.exp(log_post - log_post.max())\npost /= post.sum()\ncheck(\"ERM on a fixed trainset and online learning agree on the same H \"\n      \"(|w| close)\",\n      np.linalg.norm(w_erm - w_og) < 0.1)\ncheck(\"Bayesian inference returns a distribution over H that \"\n      \"concentrates on the best hypothesis\",\n      post[0] > 0.99)\n\n# ------------------------------------------------------------ preview\nfig, ax = plt.subplots(1, 2, figsize=(8.6, 3.0))\nxx = np.linspace(-1, 1, 300)\nax[0].plot(xd, yd, \"ko\", ms=4)\nfor deg, st in ((1, \"--\"), (3, \"-\"), (12, \":\")):\n    ax[0].plot(xx, np.polyval(np.polyfit(xd, yd, deg), xx), st,\n               label=f\"deg {deg}\")\nax[0].set_ylim(-2, 2); ax[0].legend(frameon=False)\nax[0].set_xlabel(\"feature $x$\"); ax[0].set_ylabel(\"label $y$\")\nax[0].set_title(\"[P-design] size of H vs overfitting\")\nax[1].semilogx([2, 16, 256], gaps, \"o-\")\nax[1].set_xlabel(\"|H|\"); ax[1].set_ylabel(\"max generalization gap\")\nax[1].set_title(\"[P-size]\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"hypospace.png\", dpi=110)\nprint(f\"\\n{sum(ok for _, ok in report)}/{len(report)} checks passed\")\nassert all(ok for _, ok in report)"
  }
 ]
}