{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "colab": {
   "provenance": []
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cell-0000",
   "metadata": {},
   "source": [
    "# AdaBoost: Learning from Mistakes\n",
    "\n",
    "The original boosting algorithm — sample re-weighting, decision stumps, and why a sequence of barely-better-than-random learners adds up to a strong model.\n",
    "\n",
    "*Part of the free [Machine Learning](https://ramadnsyh.dev/courses/machine-learning) course by [Muhammad Ramadiansyah](https://ramadnsyh.dev). This notebook is generated from the interactive lesson — [read it online](https://ramadnsyh.dev/courses/machine-learning/adaboost).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Bagging trains its members independently and hopes their errors cancel.\n",
    "Boosting is more deliberate: train models **one after another**, and make each\n",
    "new model focus on exactly the samples the previous ones got wrong. AdaBoost\n",
    "(*Adaptive Boosting*, 1997) was the first practical algorithm to pull this\n",
    "off, and its central idea — re-weighting mistakes — is the cleanest way to\n",
    "understand everything that came after it, up to and including XGBoost."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## Boosting: a sequence, not a committee\n",
    "\n",
    "A random forest is a room full of experts voting at the same time. AdaBoost is\n",
    "a relay: the first model does its best, then hands the second model a note\n",
    "saying \"I keep getting *these* samples wrong — you focus on them.\" The second\n",
    "model hands a similar note to the third, and so on. The final prediction is a\n",
    "**weighted vote** of the whole sequence, where models that performed well get\n",
    "a louder voice.\n",
    "\n",
    "Two things had to be invented to make this work:\n",
    "\n",
    "1. **Sample weights** — a number per training sample saying how much the next\n",
    "   learner should care about it. Mistakes get their weight *increased*.\n",
    "2. **Learner weights (α)** — how much each learner's vote counts in the final\n",
    "   ensemble, based on how accurate it was on the weights it faced."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "## Re-weighting, round by round\n",
    "\n",
    "Start with all n samples weighted equally at 1/n. Each round then does:\n",
    "\n",
    "1. Train a weak learner on the current weights.\n",
    "2. Compute its **weighted error** ε (the total weight of the samples it got\n",
    "   wrong).\n",
    "3. Give it a vote weight **α = ½ · ln((1 − ε) / ε)** — near-perfect learners\n",
    "   get big α, coin-flip learners get α ≈ 0.\n",
    "4. Multiply misclassified samples' weights **up** and correct ones **down**,\n",
    "   then renormalize so the weights sum to 1.\n",
    "\n",
    "Let's watch the numbers move for two rounds on ten samples:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0004",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.set_printoptions(precision=3, suppress=True)\n",
    "\n",
    "n = 10\n",
    "w = np.full(n, 1 / n)\n",
    "print(\"round 0 weights:\", w)\n",
    "\n",
    "# --- Round 1: stump misclassifies samples 3, 7, 8 ---\n",
    "miss = np.zeros(n, dtype=bool); miss[[3, 7, 8]] = True\n",
    "eps = w[miss].sum()\n",
    "alpha = 0.5 * np.log((1 - eps) / eps)\n",
    "print(f\"\\\\nround 1: weighted error = {eps:.3f}, learner weight alpha = {alpha:.3f}\")\n",
    "\n",
    "w = w * np.exp(alpha * np.where(miss, 1, -1))   # up-weight misses, down-weight hits\n",
    "w = w / w.sum()\n",
    "print(\"weights after round 1:\", w)\n",
    "print(\"-> samples 3, 7, 8 now carry\", f\"{w[3]:.3f}\", \"each vs\", f\"{w[0]:.3f}\", \"for the rest\")\n",
    "\n",
    "# --- Round 2: new stump fixes 7 and 8 but misses samples 1, 3 ---\n",
    "miss = np.zeros(n, dtype=bool); miss[[1, 3]] = True\n",
    "eps = w[miss].sum()\n",
    "alpha = 0.5 * np.log((1 - eps) / eps)\n",
    "print(f\"\\\\nround 2: weighted error = {eps:.3f}, alpha = {alpha:.3f}\")\n",
    "\n",
    "w = w * np.exp(alpha * np.where(miss, 1, -1))\n",
    "w = w / w.sum()\n",
    "print(\"weights after round 2:\", w)\n",
    "print(\"-> sample 3, wrong twice in a row, now dominates:\", f\"{w[3]:.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "Follow sample 3 through the printout: wrong in round 1, its weight jumps from\n",
    "0.10 to 0.17; wrong *again* in round 2, it climbs to the heaviest sample in\n",
    "the set. By round 3 any learner that wants a low weighted error basically\n",
    "*must* classify sample 3 correctly. That's the \"adaptive\" in Adaptive\n",
    "Boosting — the training distribution itself shifts toward the hard cases."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0006",
   "metadata": {},
   "source": [
    "## Weak learners and decision stumps\n",
    "\n",
    "Boosting's base models are deliberately feeble. The classic choice is a\n",
    "**decision stump**: a depth-1 tree that asks a single question. On its own a\n",
    "stump barely beats a coin flip — but that's all boosting needs. Each round\n",
    "only has to contribute a small correction, and the weighted sum of hundreds of\n",
    "tiny corrections can trace an intricate boundary.\n",
    "\n",
    "Weak learners aren't just sufficient — they're *safer*. A deep tree can fit\n",
    "the re-weighted samples (including noisy ones) almost perfectly in a round or\n",
    "two, which makes the ensemble jump straight to overfitting. Stumps force the\n",
    "progress to be gradual."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "## AdaBoost in scikit-learn\n",
    "\n",
    "`AdaBoostClassifier` uses stumps by default. Its `staged_predict` method lets\n",
    "us score the ensemble after *every* round in one pass — perfect for seeing how\n",
    "accuracy builds up:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0008",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_moons\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.ensemble import AdaBoostClassifier\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "X, y = make_moons(n_samples=500, noise=0.25, random_state=42)\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.3, stratify=y, random_state=42)\n",
    "\n",
    "ada = AdaBoostClassifier(n_estimators=200, learning_rate=0.5, random_state=42)\n",
    "ada.fit(X_train, y_train)\n",
    "\n",
    "train_curve = [accuracy_score(y_train, p) for p in ada.staged_predict(X_train)]\n",
    "test_curve = [accuracy_score(y_test, p) for p in ada.staged_predict(X_test)]\n",
    "\n",
    "plt.plot(train_curve, label=\"train\")\n",
    "plt.plot(test_curve, label=\"test\")\n",
    "plt.xlabel(\"number of stumps\"); plt.ylabel(\"accuracy\"); plt.legend()\n",
    "plt.show()\n",
    "\n",
    "print(f\"1 stump  : test acc = {test_curve[0]:.3f}\")\n",
    "print(f\"200 stumps: test acc = {test_curve[-1]:.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "One stump manages a crude single cut; by a few dozen rounds the ensemble has\n",
    "bent itself around both moons. Notice the shape of the curves: fast gains\n",
    "early, then a long plateau — and if you push far enough on noisy data, the\n",
    "test curve can start drifting back *down* while train keeps climbing. Unlike a\n",
    "random forest, **more boosting rounds is an overfitting axis**, so\n",
    "`n_estimators` needs validation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0010",
   "metadata": {},
   "source": [
    "## The learning rate\n",
    "\n",
    "`learning_rate` scales every learner's contribution before it's added to the\n",
    "ensemble. It trades off against `n_estimators`:\n",
    "\n",
    "- **Small learning rate** (0.1–0.5): each round corrects gently, so you need\n",
    "  more rounds — but the ensemble is smoother and usually generalizes better.\n",
    "- **Learning rate near 1**: aggressive corrections. Fewer rounds needed, but\n",
    "  each round can over-commit to the current mistakes, and later rounds spend\n",
    "  their effort fighting earlier over-corrections.\n",
    "\n",
    "The standard recipe is *shrink the learning rate, grow the round count*, and\n",
    "pick the pair by validation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "> **AdaBoost's Achilles' heel: noisy labels**\n",
    "> \n",
    "> Re-weighting mistakes is a double-edged sword. A mislabeled sample or extreme\n",
    "> outlier is, by definition, a sample every sensible learner gets \"wrong\" — so\n",
    "> AdaBoost doubles down on it round after round until its weight dwarfs\n",
    "> everything else, warping the boundary to chase one bad point. On noisy data,\n",
    "> prefer a lower learning rate, fewer rounds, or a boosting method with a more\n",
    "> forgiving loss (like gradient boosting with a robust loss)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0012",
   "metadata": {},
   "source": [
    "## Where AdaBoost sits in history\n",
    "\n",
    "Freund and Schapire's AdaBoost (1997) was the proof that boosting worked\n",
    "outside of theory, and it earned them the Gödel Prize. A few years later,\n",
    "statisticians showed AdaBoost is a special case of a much more general recipe\n",
    "— **gradient boosting**, which reframes \"focus on the mistakes\" as gradient\n",
    "descent on any differentiable loss (AdaBoost corresponds to the exponential\n",
    "loss). That generalization, hardware-optimized as XGBoost and LightGBM, is\n",
    "what actually ships in production today. AdaBoost remains the best place to\n",
    "*learn* boosting, because you can see the mechanism — the weights — with your\n",
    "own eyes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0013",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Stumps vs deeper base learners\n",
    "\n",
    "On `make_moons` with `noise=0.3`, train two AdaBoost models with 150 rounds:\n",
    "one with the default stumps (`max_depth=1`) and one whose base learner is a\n",
    "`DecisionTreeClassifier` with `max_depth=4`. Plot both test-accuracy curves\n",
    "(via `staged_predict`) on the same axes. Which base learner peaks higher, and\n",
    "which one's test accuracy decays as rounds accumulate?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0014",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0015",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_moons\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.ensemble import AdaBoostClassifier\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "X, y = make_moons(n_samples=500, noise=0.3, random_state=0)\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.3, stratify=y, random_state=0)\n",
    "\n",
    "for depth in [1, 4]:\n",
    "    ada = AdaBoostClassifier(\n",
    "        estimator=DecisionTreeClassifier(max_depth=depth),\n",
    "        n_estimators=150, learning_rate=0.5, random_state=0)\n",
    "    ada.fit(X_train, y_train)\n",
    "    test_curve = [accuracy_score(y_test, p) for p in ada.staged_predict(X_test)]\n",
    "    plt.plot(test_curve, label=f\"base depth {depth}\")\n",
    "    print(f\"depth {depth}: final test acc = {test_curve[-1]:.3f}, best = {max(test_curve):.3f}\")\n",
    "\n",
    "plt.xlabel(\"boosting rounds\"); plt.ylabel(\"test accuracy\"); plt.legend()\n",
    "plt.show()\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0016",
   "metadata": {},
   "source": [
    "Next up: gradient boosting — the reframing of AdaBoost's idea as gradient\n",
    "descent on residuals, and its industrial-strength descendant, XGBoost."
   ]
  }
 ]
}