{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "classification.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# classification \u2014 Python demo\n\nNumerical companion to the entry [classification](https://dictionaryofml.org/terms/classification.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nThe entry's first figure is produced here from data rather than drawn by hand: a training set of data points with known labels and two features, the linear classifier learned from it, and the two decision regions its decision boundary cuts the feature space into. The classifier is built the way the entry describes: a real-valued hypothesis h(x) = w^T x is trained by minimizing the average logistic loss over the training set, and the prediction is obtained by comparing h(x) against the threshold 0.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/classification.py`](https://dictionaryofml.org/terms/classification.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(), \"classification.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nclassification.py \u2014 numerical companion to the glossary entry\n'classification'.\n\nPurpose\n-------\nThe entry's first figure is produced here from data rather than drawn by\nhand: a training set of data points with known labels and two features,\nthe linear classifier learned from it, and the two decision regions its decision\nboundary cuts the feature space into.  The classifier is built the way the\nentry describes: a real-valued hypothesis h(x) = w^T x is trained by\nminimizing the average logistic loss over the training set, and the\nprediction is obtained by comparing h(x) against the threshold 0.\n\nThe two label classes overlap on purpose: data points with nearly the same\nfeature vector can carry different labels, so no classifier reaches zero\nerror and the accuracy on a test set stays below one \u2014 the entry's point\nthat some misclassifications are unavoidable.\n\nSelf-contained (numpy + matplotlib only), fixed seed.\n\nBlocks\n------\n[B-data]      A training set and a test set of data points, two features\n              each and a label from {-1, 1}.  The two classes overlap.\n[B-train]     The real-valued hypothesis h(x) = w^T x, trained by\n              minimizing the average logistic loss over the training set.\n[B-threshold] The two-step construction: the prediction is 1 where\n              h(x) >= 0 and -1 otherwise, so the two decision regions are\n              the half-spaces on either side of the hyperplane w^T x = 0,\n              and the average 0/1 loss equals one minus the accuracy.\n[B-losses]    The 0/1 loss and its two surrogates as functions of the\n              margin y*h(x): the logistic loss is convex and\n              differentiable, the hinge loss is convex with a kink at\n              margin 1, and the hinge loss never falls below the 0/1 loss.\n[B-fig]       The figure data: training set, decision boundary and the\n              shaded decision region of the label 1, written to\n              classification_points.csv, classification_boundary.csv,\n              classification_region.csv and classification.png.\n[B-test]      The learned classifier judged by its accuracy on the test\n              set: clearly above chance, below one because of the overlap.\n\nOutputs\n-------\nclassification_points.csv   : x1, x2, grp for the training set\nclassification_boundary.csv : the decision boundary of the learned classifier\nclassification_region.csv   : the decision region of label 1, as a polygon\nclassification.png          : preview (checking only)\n\"\"\"\n\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nOUT_DIR = Path(__file__).parent\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nreport = []                         # collects (check name, pass/fail) pairs\n\n\ndef check(name, ok):                # records and prints one verification\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")\n\n\nrng = np.random.default_rng(20260911)\nM_TRAIN = 15                        # training data points per label value\nM_TEST = 300                        # test data points in total\nMU = np.array([1.1, 1.4])           # center of the label-1 class; the\n                                    # label -1 class sits at -MU\nSPREAD = 1.1\nBOX = 4.5                           # the plotted part of the feature space"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** A training set and a test set of data points, two features each and a label from {-1, 1}. The two classes overlap."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# A training set and a test set.  Each data point has two features and a\n# label from {-1, 1}; the two classes are overlapping clouds centered at\n# MU and -MU, so nearby feature vectors can carry different labels.\ndef draw(m_per_class):\n    xp = MU + SPREAD * rng.standard_normal((m_per_class, 2))\n    xn = -MU + SPREAD * rng.standard_normal((m_per_class, 2))\n    X = np.vstack([xp, xn])\n    y = np.hstack([np.ones(m_per_class), -np.ones(m_per_class)])\n    return X, y\n\n\nX_tr, y_tr = draw(M_TRAIN)\nX_te, y_te = draw(M_TEST // 2)\n\ncheck(\"[B-data] training set holds 15 data points per label value\",\n      (y_tr == 1).sum() == M_TRAIN and (y_tr == -1).sum() == M_TRAIN)\ncheck(\"[B-data] training set fits the plotted box\",\n      np.abs(X_tr).max() < BOX)\n# Overlap: even the boundary that separates the two class centers best\n# misclassifies part of the test set.\nbest_err = np.mean(np.sign(X_te @ MU) != y_te)\ncheck(\"[B-data] the two classes overlap (no error-free boundary)\",\n      best_err > 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-train]** The real-valued hypothesis h(x) = w^T x, trained by minimizing the average logistic loss over the training set."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# The real-valued hypothesis h(x) = w^T x, trained by minimizing the\n# average logistic loss over the training set (a fixed number of update\n# steps).\ndef avg_logistic_loss(w, X, y):\n    return np.mean(np.log1p(np.exp(-y * (X @ w))))\n\n\nw = np.zeros(2)\nloss_path = [avg_logistic_loss(w, X_tr, y_tr)]\nfor _ in range(3000):\n    p = 1.0 / (1.0 + np.exp(-(X_tr @ w)))          # one update step on the\n    w -= 0.3 * X_tr.T @ (p - (y_tr + 1) / 2) / len(y_tr)   # average loss\n    loss_path.append(avg_logistic_loss(w, X_tr, y_tr))\n\ncheck(\"[B-train] the average logistic loss decreased during training\",\n      loss_path[-1] < loss_path[0])\ncheck(\"[B-train] the learned weights are finite\", np.all(np.isfinite(w)))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-threshold]** The two-step construction: the prediction is 1 where h(x) >= 0 and -1 otherwise, so the two decision regions are the half-spaces on either side of the hyperplane w^T x = 0, and the average 0/1 loss equals one minus the accuracy."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Two-step construction: h(x) quantifies the confidence in the label 1,\n# and the prediction compares it against the threshold 0.\nh_tr = X_tr @ w\nyhat_tr = np.where(h_tr >= 0, 1, -1)\n\ncheck(\"[B-threshold] every prediction lies in the label space {-1, 1}\",\n      set(np.unique(yhat_tr)) <= {-1, 1})\ncheck(\"[B-threshold] the prediction depends only on the side of the \"\n      \"hyperplane w^T x = 0\",\n      np.all((yhat_tr == 1) == (h_tr >= 0)))\nacc_tr = np.mean(yhat_tr == y_tr)\nzeroone_tr = np.mean(yhat_tr != y_tr)\ncheck(\"[B-threshold] average 0/1 loss = 1 - accuracy on the training set\",\n      np.isclose(zeroone_tr, 1.0 - acc_tr))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-losses]** The 0/1 loss and its two surrogates as functions of the margin y*h(x): the logistic loss is convex and differentiable, the hinge loss is convex with a kink at margin 1, and the hinge loss never falls below the 0/1 loss."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# The 0/1 loss and its two surrogates as functions of the margin y*h(x).\nt = np.linspace(-2.0, 3.0, 1001)\nzeroone = np.where(t <= 0, 1.0, 0.0)\nlogistic = np.log1p(np.exp(-t))\nhinge = np.maximum(0.0, 1.0 - t)\n\ncheck(\"[B-losses] the hinge loss never falls below the 0/1 loss\",\n      np.all(hinge >= zeroone - 1e-12))\ncheck(\"[B-losses] the logistic loss is convex and strictly decreasing\",\n      np.all(np.diff(logistic, 2) > -1e-12) and np.all(np.diff(logistic) < 0))\ncheck(\"[B-losses] the hinge loss is convex\",\n      np.all(np.diff(hinge, 2) > -1e-12))\nleft = (hinge[t < 1][-1] - hinge[t < 0.9][-1]) / (t[t < 1][-1] - t[t < 0.9][-1])\nright = (hinge[t < 2][-1] - hinge[t < 1.1][-1]) / (t[t < 2][-1] - t[t < 1.1][-1])\ncheck(\"[B-losses] the hinge loss has a kink at margin 1 \"\n      \"(slope -1 on the left, 0 on the right)\",\n      np.isclose(left, -1.0, atol=1e-6) and np.isclose(right, 0.0, atol=1e-6))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-fig]** The figure data: training set, decision boundary and the shaded decision region of the label 1, written to classification_points.csv, classification_boundary.csv, classification_region.csv and classification.png."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Figure data.  The decision boundary w^T x = 0 is a line through the\n# origin; the decision region of the label 1 is the half-space above it,\n# clipped to the plotted box.\nslope = -w[0] / w[1]\ncheck(\"[B-fig] the boundary leaves the box through its left/right edges\",\n      w[1] > 0 and abs(slope) * BOX < BOX)\n\nbnd = np.array([[-BOX, slope * -BOX], [BOX, slope * BOX]])\nregion = np.array([[-BOX, slope * -BOX], [BOX, slope * BOX],\n                   [BOX, BOX], [-BOX, BOX]])\ncheck(\"[B-fig] the interior corners of the region carry the prediction 1\",\n      np.all(region[2:] @ w > 0))\n\nwith open(OUT_DIR / \"classification_points.csv\", \"w\") as fh:\n    fh.write(\"x1,x2,grp\\n\")\n    for (a, b), lab in zip(X_tr, y_tr):\n        fh.write(f\"{a:.4f},{b:.4f},k{1 if lab > 0 else 0}\\n\")\nwith open(OUT_DIR / \"classification_boundary.csv\", \"w\") as fh:\n    fh.write(\"x1,x2\\n\")\n    for a, b in bnd:\n        fh.write(f\"{a:.4f},{b:.4f}\\n\")\nwith open(OUT_DIR / \"classification_region.csv\", \"w\") as fh:\n    fh.write(\"x1,x2\\n\")\n    for a, b in region:\n        fh.write(f\"{a:.4f},{b:.4f}\\n\")\nprint(f\"  wrote {OUT_DIR / 'classification_points.csv'}\")\nprint(f\"  wrote {OUT_DIR / 'classification_boundary.csv'}\")\nprint(f\"  wrote {OUT_DIR / 'classification_region.csv'}\")\n\nfig, axes = plt.subplots(1, 2, figsize=(9.2, 4.0))\nax = axes[0]\nax.fill(region[:, 0], region[:, 1], color=\"0.92\",\n        label=\"decision region of label 1\")\nax.plot(bnd[:, 0], bnd[:, 1], \"k-\", lw=1.6, label=\"decision boundary\")\npos, neg = y_tr > 0, y_tr < 0\nax.plot(X_tr[neg, 0], X_tr[neg, 1], \"ko\", ms=5, label=\"label -1\")\nax.plot(X_tr[pos, 0], X_tr[pos, 1], \"ks\", mfc=\"none\", ms=6, label=\"label 1\")\nax.set_xlim(-BOX, BOX)\nax.set_ylim(-BOX, BOX)\nax.set_xlabel(\"feature x1\")\nax.set_ylabel(\"feature x2\")\nax.set_title(\"training set and learned decision regions\")\nax.legend(frameon=False, fontsize=8, loc=\"lower left\")\n\nax = axes[1]\nax.plot(t[t <= 0], zeroone[t <= 0], \"k-\", lw=1.6, label=\"0/1 loss\")\nax.plot(t[t > 0], zeroone[t > 0], \"k-\", lw=1.6)\nax.plot(t, logistic, \"k--\", lw=1.4, label=\"logistic loss\")\nax.plot(t, hinge, \"k:\", lw=1.8, label=\"hinge loss\")\nax.set_xlabel(\"margin y h(x)\")\nax.set_ylabel(\"loss\")\nax.set_title(\"0/1 loss and two surrogates\")\nax.legend(frameon=False, fontsize=8)\n\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"classification.png\", dpi=110)\nprint(f\"  wrote {OUT_DIR / 'classification.png'}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-test]** The learned classifier judged by its accuracy on the test set: clearly above chance, below one because of the overlap."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# The learned classifier judged on the test set.\nyhat_te = np.where(X_te @ w >= 0, 1, -1)\nacc_te = np.mean(yhat_te == y_te)\nprint(f\"  accuracy on the test set: {acc_te:.3f}\")\ncheck(\"[B-test] test accuracy is clearly above chance\", acc_te > 0.8)\ncheck(\"[B-test] test accuracy stays below one (the classes overlap)\",\n      acc_te < 1.0)\n\nn_fail = sum(not ok for _, ok in report)\nprint(f\"\\n{len(report) - n_fail}/{len(report)} checks pass.\")\nraise SystemExit(1 if n_fail else 0)"
  }
 ]
}