{
 "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": [
    "# Polynomial Regression & Overfitting\n",
    "\n",
    "Bend a straight line into a curve with polynomial features, and meet the overfitting trap — plus how validation error tells you when to stop.\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/polynomial-regression).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Linear regression draws straight lines, but the world is full of curves:\n",
    "diminishing returns, saturation effects, U-shaped costs. **Polynomial\n",
    "regression** lets the same linear machinery fit curves — and in doing so\n",
    "introduces machine learning's most important dial: **model complexity**. Turn\n",
    "it too low and the model can't learn; turn it too high and it memorizes noise.\n",
    "This lesson is where you learn to feel that trade-off in your hands."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## When a line isn't enough\n",
    "\n",
    "Play with the degree slider below. Watch both curves: at degree 1 the line\n",
    "misses the shape entirely, around degree 3–4 the fit hugs the data's true\n",
    "pattern, and at high degrees the curve contorts itself through every training\n",
    "point while the **test error climbs back up**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "> 🎛️ **Interactive demo** — this section has a hands-on visualization in the web version of this lesson: [open it here](https://ramadnsyh.dev/courses/machine-learning/polynomial-regression)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0004",
   "metadata": {},
   "source": [
    "That U-shaped test-error curve is the single most important picture in this\n",
    "module. Keep it in mind as we rebuild it in code."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "## The trick: manufacture new features\n",
    "\n",
    "Polynomial regression doesn't change the algorithm — it changes the **inputs**.\n",
    "Instead of feeding the model just `x`, we feed it `x`, `x²`, `x³`, … and let\n",
    "plain linear regression find a weight for each:\n",
    "\n",
    "**ŷ = w₁·x + w₂·x² + w₃·x³ + b**\n",
    "\n",
    "scikit-learn's `PolynomialFeatures` manufactures those columns, and a\n",
    "`Pipeline` chains it with `LinearRegression` so the whole thing behaves like\n",
    "one model:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0006",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.preprocessing import PolynomialFeatures\n",
    "from sklearn.pipeline import Pipeline\n",
    "from sklearn.linear_model import LinearRegression\n",
    "\n",
    "# What PolynomialFeatures actually does to a column\n",
    "x_small = np.array([[2.0], [3.0]])\n",
    "poly = PolynomialFeatures(degree=3, include_bias=False)\n",
    "print(\"x -> [x, x^2, x^3]:\")\n",
    "print(poly.fit_transform(x_small))\n",
    "\n",
    "# Fit a curve with the same LinearRegression you already know\n",
    "rng = np.random.default_rng(42)\n",
    "x = np.sort(rng.uniform(-3, 3, 40)).reshape(-1, 1)\n",
    "y = 0.5 * x.ravel()**3 - 2 * x.ravel() + rng.normal(0, 1.5, 40)\n",
    "\n",
    "model = Pipeline([\n",
    "    (\"poly\", PolynomialFeatures(3, include_bias=False)),\n",
    "    (\"lr\", LinearRegression()),\n",
    "])\n",
    "model.fit(x, y)\n",
    "print(f\"\\\\nR2 on training data: {model.score(x, y):.3f}\")\n",
    "print(\"learned weights:\", np.round(model.named_steps[\"lr\"].coef_, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "> **Polynomial regression is still LINEAR regression**\n",
    "> \n",
    "> The model is nonlinear in `x` but **linear in the weights** — it's still a\n",
    "> weighted sum of (transformed) inputs, so the same closed-form solution,\n",
    "> gradient descent, and everything from the previous lesson apply unchanged.\n",
    "> \"Linear model\" refers to the weights, not the shape of the curve."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0008",
   "metadata": {},
   "source": [
    "## Degree is a complexity dial\n",
    "\n",
    "Each extra degree gives the curve one more way to bend. A degree-1 model has\n",
    "two parameters; a degree-15 model has sixteen — enough to wiggle through\n",
    "nearly every training point. More flexibility always **reduces training\n",
    "error**, but past some point it stops modeling the signal and starts modeling\n",
    "the noise. That's **overfitting**, and you can only detect it by checking\n",
    "data the model never saw."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "## Train vs test: rebuilding the U-curve\n",
    "\n",
    "Let's reproduce exactly what the playground showed you, in code. We fit every\n",
    "degree from 1 to 12 and track both errors:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0010",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.preprocessing import PolynomialFeatures\n",
    "from sklearn.pipeline import Pipeline\n",
    "from sklearn.linear_model import LinearRegression\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import mean_squared_error\n",
    "\n",
    "rng = np.random.default_rng(0)\n",
    "x = np.sort(rng.uniform(-3, 3, 60)).reshape(-1, 1)\n",
    "y = np.sin(1.5 * x.ravel()) + 0.5 * x.ravel() + rng.normal(0, 0.35, 60)\n",
    "X_train, X_test, y_train, y_test = train_test_split(x, y, test_size=0.33, random_state=1)\n",
    "\n",
    "degrees = range(1, 13)\n",
    "train_err, test_err = [], []\n",
    "for d in degrees:\n",
    "    model = Pipeline([\n",
    "        (\"poly\", PolynomialFeatures(d, include_bias=False)),\n",
    "        (\"lr\", LinearRegression()),\n",
    "    ]).fit(X_train, y_train)\n",
    "    train_err.append(mean_squared_error(y_train, model.predict(X_train)))\n",
    "    test_err.append(mean_squared_error(y_test, model.predict(X_test)))\n",
    "\n",
    "best = list(degrees)[int(np.argmin(test_err))]\n",
    "plt.figure(figsize=(7, 4))\n",
    "plt.plot(degrees, train_err, \"o-\", label=\"train MSE\")\n",
    "plt.plot(degrees, test_err, \"s-\", label=\"test MSE\")\n",
    "plt.axvline(best, color=\"gray\", ls=\"--\", label=f\"best degree = {best}\")\n",
    "plt.xlabel(\"polynomial degree\")\n",
    "plt.ylabel(\"MSE\")\n",
    "plt.legend()\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "The two curves tell the whole story:\n",
    "\n",
    "- **Training error only goes down.** More degrees can never hurt the fit on\n",
    "  data the model is allowed to see.\n",
    "- **Test error is a U.** It falls while extra flexibility captures real\n",
    "  structure, bottoms out, then rises as the model starts fitting noise.\n",
    "- The **gap** between the curves is your overfitting meter — a small gap at\n",
    "  the U's bottom, a chasm at high degrees."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0012",
   "metadata": {},
   "source": [
    "## Choosing the degree with validation\n",
    "\n",
    "The rule is simple: **pick the degree by performance on held-out data, never\n",
    "on training data** — and among models with similar validation scores, prefer\n",
    "the simplest. In the source course's words: if degree 3 gives the best test\n",
    "score, use degree 3, not the flashier degree 10 that ties it.\n",
    "\n",
    "One refinement: if you compare many degrees against the *same* test set, you\n",
    "slowly overfit to that test set too. The standard fix is **cross-validation** —\n",
    "split the training data into folds, average the score across them, and keep\n",
    "the test set untouched for a final honest estimate:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0013",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from sklearn.model_selection import cross_val_score\n",
    "\n",
    "for d in range(1, 9):\n",
    "    model = Pipeline([\n",
    "        (\"poly\", PolynomialFeatures(d, include_bias=False)),\n",
    "        (\"lr\", LinearRegression()),\n",
    "    ])\n",
    "    scores = cross_val_score(model, X_train, y_train, cv=5)\n",
    "    print(f\"degree {d}:  CV R2 = {scores.mean():.3f} +/- {scores.std():.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "You'll formalize this workflow (and automate it with grid search) later in\n",
    "the course; for now the principle is what matters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0015",
   "metadata": {},
   "source": [
    "> **High-degree polynomials get wild fast**\n",
    "> \n",
    "> Beyond the data's range, a high-degree polynomial shoots off to ±infinity —\n",
    "> extrapolation with degree 9 is fiction. And because `x¹⁰` for x = 3 is\n",
    "> 59,049, feature magnitudes explode, which is one more reason feature scaling\n",
    "> (two lessons ahead) matters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0016",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Find the best degree for a taxi-fare curve\n",
    "\n",
    "Simulate a simplified taxi-fare problem (inspired by this module's original\n",
    "NYC taxi exercise): generate 120 trips with `distance` uniform between 0.5 and\n",
    "10 km, and `fare = 3 + 2.5·distance − 0.12·distance² + noise` (Gaussian,\n",
    "σ = 1). Split 70/30 into train/test. For degrees 1 through 6, fit a\n",
    "`PolynomialFeatures` + `LinearRegression` pipeline and print train and test\n",
    "MSE. Which degree wins on the test set — and does the training error agree\n",
    "with that choice?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0017",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0018",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "from sklearn.preprocessing import PolynomialFeatures\n",
    "from sklearn.pipeline import Pipeline\n",
    "from sklearn.linear_model import LinearRegression\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import mean_squared_error\n",
    "\n",
    "rng = np.random.default_rng(7)\n",
    "distance = rng.uniform(0.5, 10, 120).reshape(-1, 1)\n",
    "fare = 3.0 + 2.5 * distance.ravel() - 0.12 * distance.ravel()**2 + rng.normal(0, 1.0, 120)\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(distance, fare, test_size=0.3, random_state=42)\n",
    "\n",
    "results = []\n",
    "for d in range(1, 7):\n",
    "    model = Pipeline([\n",
    "        (\"poly\", PolynomialFeatures(d, include_bias=False)),\n",
    "        (\"lr\", LinearRegression()),\n",
    "    ]).fit(X_train, y_train)\n",
    "    tr = mean_squared_error(y_train, model.predict(X_train))\n",
    "    te = mean_squared_error(y_test, model.predict(X_test))\n",
    "    results.append((d, tr, te))\n",
    "    print(f\"degree {d}:  train MSE = {tr:.3f}   test MSE = {te:.3f}\")\n",
    "\n",
    "best = min(results, key=lambda r: r[2])\n",
    "print(f\"\\\\nBest degree by test MSE: {best[0]}\")\n",
    "# Degree 2 (the true shape) should win; higher degrees keep lowering\n",
    "# train MSE while test MSE stagnates or worsens.\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0019",
   "metadata": {},
   "source": [
    "You've now seen overfitting with your own eyes — next we give it a proper\n",
    "theory: the bias–variance tradeoff."
   ]
  }
 ]
}