{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "boosting.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# boosting \u2014 Python demo\n\nNumerical companion to the entry [boosting](https://dictionaryofml.org/terms/boosting.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nRuns boosting with the squared error loss on a task with one feature and a real-valued label and checks the entry's claims numerically: each base learner is fit to the residuals, which are the negative gradient of the training error with respect to the current predictions, so each iteration lowers the training error; with enough iterations the training error becomes arbitrarily small while the validation error eventually rises, so the number of iterations is a hyperparameter chosen by early stopping; and accumulating base learners (boosting) differs from averaging them (bagging). Self-contained (numpy and matplotlib only), fixed seed.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/boosting.py`](https://dictionaryofml.org/terms/boosting.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(), \"boosting.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nboosting.py \u2014 numerical companion to the glossary entry 'boosting'.\n\nPurpose\n-------\nRuns boosting with the squared error loss on a task with one feature\nand a real-valued label and checks the entry's claims numerically: each base learner is fit\nto the residuals, which are the negative gradient of the training error\nwith respect to the current predictions, so each iteration lowers the\ntraining error; with enough iterations the training error becomes\narbitrarily small while the validation error eventually rises, so the\nnumber of iterations is a hyperparameter chosen by early stopping; and\naccumulating base learners (boosting) differs from averaging them\n(bagging).  Self-contained (numpy and matplotlib only), fixed seed.\n\nSetup\n-----\nTraining pairs: m = 30 pairs (x, y) with feature x in [0, 1] and label\ny = sin(2 pi x) + 0.5 x + noise; a validation set of 30 further pairs\nof the same kind.  Base learners: decision trees of depth one\n(one split of the feature range, one constant prediction on each side).\nLearning rate eta = 0.5, up to T = 300 iterations, initialization\nh^(0) = mean label of the training pairs.\n\nBlocks\n------\n[B-gradstep] The base learner of iteration t is fit to the residuals\n             y - h^(t-1)(x), i.e. to the negative gradient of the training\n             error with respect to the predictions; adding it with\n             learning rate eta lowers the training error in every\n             iteration.\n[B-overfit]  The training error falls below 0.02 by T = 300, while the\n             validation error reaches its minimum at an earlier iteration\n             and is at least 0.03 larger at T = 300 than at that minimum:\n             early stopping picks the number of iterations.\n[B-bagging]  Averaging 300 base learners, each trained on a random draw\n             with replacement from the training pairs (bagging), leaves the\n             training error more than five times that of accumulating\n             them (boosting).\n\nOutputs\n-------\nboosting_errors.csv : t, trainerr, valerr of boosting, and the training\n                      error of bagging with t base learners.\nboosting_fit.csv    : x grid with the label function, the boosted\n                      hypothesis after early stopping and after T = 300.\nboosting.png        : matplotlib preview of the two panels (checking\n                      only).\n\"\"\"\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\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")\n\n\nrng = np.random.default_rng(0)\n\nm = 30\nx_tr = np.sort(rng.uniform(0.0, 1.0, m))\nx_va = np.sort(rng.uniform(0.0, 1.0, m))\n\n\ndef truth(xs):\n    return np.sin(2.0 * np.pi * xs) + 0.5 * xs\n\n\ny_tr = truth(x_tr) + 0.3 * rng.standard_normal(m)\ny_va = truth(x_va) + 0.3 * rng.standard_normal(m)\n\n\ndef fit_stump(xs, target):\n    \"\"\"Depth-one decision tree: the split and the two constants that\n    minimize the squared error of the fit to `target`.\"\"\"\n    order = np.argsort(xs); xs_s, t_s = xs[order], target[order]\n    best = (np.inf, None, None, None)\n    for i in range(1, len(xs_s)):\n        left, right = t_s[:i].mean(), t_s[i:].mean()\n        err = ((t_s[:i] - left) ** 2).sum() + ((t_s[i:] - right) ** 2).sum()\n        if err < best[0]:\n            best = (err, 0.5 * (xs_s[i - 1] + xs_s[i]), left, right)\n    _, split, left, right = best\n    return lambda q: np.where(q < split, left, right)\n\n\ndef trainerr(pred, y):\n    return float(np.mean((y - pred) ** 2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-gradstep]** The base learner of iteration t is fit to the residuals y - h^(t-1)(x), i.e. to the negative gradient of the training error with respect to the predictions; adding it with learning rate eta lowers the training error in every iteration."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "eta, T = 0.5, 300\nh_tr = np.full(m, y_tr.mean()); h_va = np.full(m, y_tr.mean())\nlearners = []\nerr_tr, err_va = [trainerr(h_tr, y_tr)], [trainerr(h_va, y_va)]\nmonotone = True\nfor t in range(1, T + 1):\n    residual = y_tr - h_tr                 # negative gradient (up to 2/m)\n    g = fit_stump(x_tr, residual)\n    learners.append(g)\n    h_tr = h_tr + eta * g(x_tr); h_va = h_va + eta * g(x_va)\n    err_tr.append(trainerr(h_tr, y_tr)); err_va.append(trainerr(h_va, y_va))\n    monotone &= err_tr[-1] < err_tr[-2]\ngrad_check = np.allclose(residual, -0.5 * m * (-(2.0 / m) * residual))\ncheck(f\"[B-gradstep] residuals are the negative gradient of the training \"\n      f\"error (up to the factor 2/m), and all {T} iterations lower it: \"\n      f\"{err_tr[0]:.3f} -> {err_tr[-1]:.4f}\", monotone and grad_check)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-overfit]** The training error falls below 0.02 by T = 300, while the validation error reaches its minimum at an earlier iteration and is at least 0.03 larger at T = 300 than at that minimum: early stopping picks the number of iterations."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "t_best = int(np.argmin(err_va))\ncheck(f\"[B-overfit]  training error {err_tr[-1]:.4f} at T={T}; validation \"\n      f\"error minimal at t={t_best} ({err_va[t_best]:.3f}), larger at T=\"\n      f\"{T} ({err_va[-1]:.3f})\",\n      err_tr[-1] < 0.02 and t_best < T and err_va[-1] > err_va[t_best] + 0.03)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-bagging]** Averaging 300 base learners, each trained on a random draw with replacement from the training pairs (bagging), leaves the training error more than five times that of accumulating them (boosting)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "bag_err = []\nbag_sum = np.zeros(m)\nfor b in range(1, T + 1):\n    idx = rng.integers(0, m, m)\n    g = fit_stump(x_tr[idx], y_tr[idx])\n    bag_sum += g(x_tr)\n    bag_err.append(trainerr(bag_sum / b, y_tr))\ncheck(f\"[B-bagging]  training error of {T} averaged base learners \"\n      f\"{bag_err[-1]:.3f} vs {err_tr[-1]:.4f} for {T} accumulated ones\",\n      bag_err[-1] > 5 * err_tr[-1])\n\n# ---------------------------------------------------------------- CSV\nwith open(OUT_DIR / \"boosting_errors.csv\", \"w\") as fh:\n    fh.write(\"t,trainerr,valerr,bagging_trainerr\\n\")\n    for t in range(T + 1):\n        be = bag_err[t - 1] if t > 0 else trainerr(np.full(m, y_tr.mean()), y_tr)\n        fh.write(f\"{t},{err_tr[t]:.4f},{err_va[t]:.4f},{be:.4f}\\n\")\nxg = np.linspace(0.0, 1.0, 201)\n\n\ndef boosted(xs, n):\n    out = np.full(len(xs), y_tr.mean())\n    for g in learners[:n]:\n        out = out + eta * g(xs)\n    return out\n\n\nwith open(OUT_DIR / \"boosting_fit.csv\", \"w\") as fh:\n    fh.write(\"x,truth,h_early,h_final\\n\")\n    for a, b, c, d in zip(xg, truth(xg), boosted(xg, t_best), boosted(xg, T)):\n        fh.write(f\"{a:.4f},{b:.4f},{c:.4f},{d:.4f}\\n\")\n\n# -------------------------------------------------------------- preview\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 3.9))\nts = np.arange(T + 1)\nax1.plot(ts, err_tr, \"k-\", lw=1.3, label=\"training error (boosting)\")\nax1.plot(ts, err_va, \"k--\", lw=1.3, label=\"validation error (boosting)\")\nax1.plot(ts, [err_tr[0]] + bag_err, \"k:\", lw=1.5, label=\"training error (bagging)\")\nax1.axvline(t_best, color=\"0.5\", lw=0.8, ls=\"-.\", label=f\"early stopping, t={t_best}\")\nax1.set_xlabel(\"iteration $t$\"); ax1.set_ylabel(\"average squared error\")\nax1.set_title(\"accumulated vs averaged base learners\")\nax1.legend(frameon=False, fontsize=8)\nax2.plot(x_tr, y_tr, \"ko\", ms=3, label=\"training pairs\")\nax2.plot(xg, truth(xg), \"k-\", lw=1.0, label=\"label function\")\nax2.plot(xg, boosted(xg, t_best), \"k--\", lw=1.3, label=f\"boosted hypothesis, t={t_best}\")\nax2.plot(xg, boosted(xg, T), \"k:\", lw=1.3, label=f\"boosted hypothesis, t={T}\")\nax2.set_xlabel(\"feature $x$\"); ax2.set_ylabel(\"label $y$\")\nax2.set_title(\"boosting overfits when run too long\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"boosting.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nprint(f\"wrote {OUT_DIR / 'boosting_errors.csv'}, {OUT_DIR / 'boosting_fit.csv'}, \"\n      f\"{OUT_DIR / 'boosting.png'}\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}