{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "kernelmethod.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# kernel method \u2014 Python demo\n\nNumerical companion to the entry [kernel method](https://dictionaryofml.org/terms/kernelmethod.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nA two-ring binary trainset in R^2 that no linear classifier separates, on which a Gaussian-kernel method learns a perfect nonlinear decision boundary. The method is kernel ridge regression fit to labels y in {-1, +1}, with predictions taken as the sign of the fitted value \u2014 the construction known as regularized least-squares classification (Rifkin, Yeo & Poggio 2003). It is RERM over the RKHS H_k with the squared error loss,\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/kernelmethod.py`](https://dictionaryofml.org/terms/kernelmethod.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(), \"kernelmethod.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"\nkernelmethod.py \u2014 numerical companion to the glossary entry 'kernel method'.\n\nPurpose\n-------\nA two-ring binary trainset in R^2 that no linear classifier separates, on\nwhich a Gaussian-kernel method learns a perfect nonlinear decision boundary.\nThe method is kernel ridge regression fit to labels y in {-1, +1}, with\npredictions taken as the sign of the fitted value \u2014 the construction known\nas regularized least-squares classification (Rifkin, Yeo & Poggio 2003).\nIt is RERM over the RKHS H_k with the squared error loss,\n\n    min_{h in H_k}  (1/m) sum_r (h(x^(r)) - y^(r))^2  +  alpha ||h||_{H_k}^2 ,\n\nwhose representer-theorem solution h_hat = sum_r beta_r k(x^(r), .) has the\nclosed-form expansion coefficients  beta_hat = (K + alpha m I)^{-1} y  with\nGram matrix K_rs = k(x^(r), x^(s)).  Self-contained (numpy/matplotlib only),\nfixed seed.\n\nBlocks\n------\n[B-data]   Two concentric rings (12 points each): class +1 on radius ~1.0,\n           class -1 on radius ~2.5, radial noise 0.1, seed 0.\n[B-linear] Baseline: least-squares linear classifier sign(w^T x + b) fit on\n           the same trainset misclassifies about half the points \u2014 the\n           dataset is far from linearly separable.\n[B-kernel] Gaussian kernel k(x,x') = exp(-||x-x'||^2 / (2 sigma^2)) with\n           sigma = 0.8, alpha = 1e-3: closed-form beta_hat, training\n           accuracy 100%, boundary h_hat = 0 encircles the inner ring.\n[B-opt]    Optimality check: K((K + alpha m I) beta_hat - y) = 0, the\n           first-order optimality condition of the RERM objective in\n           the coefficients, holds at beta_hat.\n[B-norm]   The squared RKHS norm of the learned hypothesis, beta^T K beta.\n[B-bnd]    The decision boundary h_hat = 0, as contour segments drawn\n           onto the preview figure.\n[B-csv]    The two CSVs the entry's pgfplots figure reads.\n[B-preview] Data points and legend added to the preview figure; saved.\n\nOutputs\n-------\nkernelmethod_points.csv   : the 24 data points, columns x1,x2,label,cls\n                            (cls in {pos,neg}) for the entry's pgfplots\n                            scatter.\nkernelmethod_boundary.csv : polyline(s) of the learned decision boundary\n                            h_hat(x) = 0, columns x1,x2; separate contour\n                            segments are delimited by nan,nan rows\n                            (pgfplots: unbounded coords=jump).\nkernelmethod.png          : matplotlib preview of the figure (checking 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}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** Two concentric rings (12 points each): class +1 on radius ~1.0, class -1 on radius ~2.5, radial noise 0.1, seed 0."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "rng = np.random.default_rng(0)\nm_per = 12\nangles = np.linspace(0.0, 2.0 * np.pi, m_per, endpoint=False)\n\nr_in = 1.0 + 0.1 * rng.standard_normal(m_per)\nr_out = 2.5 + 0.1 * rng.standard_normal(m_per)\nX_in = np.c_[r_in * np.cos(angles), r_in * np.sin(angles)]\nX_out = np.c_[r_out * np.cos(angles + np.pi / m_per),\n              r_out * np.sin(angles + np.pi / m_per)]\n\nX = np.vstack([X_in, X_out])                    # (m, 2)\ny = np.r_[np.ones(m_per), -np.ones(m_per)]      # +1 inner, -1 outer\nm = len(y)\n\nprint(\"kernel method demo (kernel ridge regression on +-1 labels, \"\n      \"Gaussian kernel)\")\ncheck(\"[B-data]   two rings, m = 24\", m == 24 and set(y) == {1.0, -1.0})"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-linear]** Baseline: least-squares linear classifier sign(w^T x + b) fit on the same trainset misclassifies about half the points \u2014 the dataset is far from linearly separable."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "A = np.c_[X, np.ones(m)]                        # [x1, x2, 1]\nwb, *_ = np.linalg.lstsq(A, y, rcond=None)\nacc_lin = np.mean(np.sign(A @ wb) == y)\ncheck(\"[B-linear] linear least-squares baseline fails (acc <= 0.7)\",\n      acc_lin <= 0.7)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-kernel]** Gaussian kernel k(x,x') = exp(-||x-x'||^2 / (2 sigma^2)) with sigma = 0.8, alpha = 1e-3: closed-form beta_hat, training accuracy 100%, boundary h_hat = 0 encircles the inner ring."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "SIGMA = 0.8\nALPHA = 1e-3\n\n\ndef gauss_kernel(P, Q):\n    d2 = ((P[:, None, :] - Q[None, :, :]) ** 2).sum(-1)\n    return np.exp(-d2 / (2.0 * SIGMA ** 2))\n\n\nK = gauss_kernel(X, X)\nbeta = np.linalg.solve(K + ALPHA * m * np.eye(m), y)\n\n\ndef h_hat(P):\n    \"\"\"Representer expansion: h_hat(x) = sum_r beta_r k(x^(r), x).\"\"\"\n    return gauss_kernel(P, X) @ beta\n\n\nacc_ker = np.mean(np.sign(h_hat(X)) == y)\ncheck(\"[B-kernel] kernel method separates the trainset (acc = 1.0)\",\n      acc_ker == 1.0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-opt]** Optimality check: K((K + alpha m I) beta_hat - y) = 0, the first-order optimality condition of the RERM objective in the coefficients, holds at beta_hat."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "opt_res = np.linalg.norm(K @ ((K + ALPHA * m * np.eye(m)) @ beta - y))\ncheck(\"[B-opt]    first-order optimality condition holds at beta_hat\",\n      opt_res < 1e-8)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-norm]** The squared RKHS norm of the learned hypothesis, beta^T K beta."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "rkhs_norm2 = float(beta @ K @ beta)\ncheck(\"[B-norm]   RKHS norm ||h_hat||^2 positive and finite\",\n      0.0 < rkhs_norm2 < 1e6)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-bnd]** The decision boundary h_hat = 0, as contour segments drawn onto the preview figure."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# drawn directly onto the preview figure; [B-preview] finishes and saves it\nG = 400\ngx = np.linspace(-3.4, 3.4, G)\ngy = np.linspace(-3.4, 3.4, G)\nGX, GY = np.meshgrid(gx, gy)\nHZ = h_hat(np.c_[GX.ravel(), GY.ravel()]).reshape(G, G)\n\nfig, ax = plt.subplots(figsize=(4.6, 4.6))\ncs = ax.contour(GX, GY, HZ, levels=[0.0], colors=\"k\", linewidths=1.8)\nsegs = [s for s in cs.allsegs[0] if len(s) > 1]\ncheck(\"[B-bnd]    boundary h_hat = 0 found\", len(segs) >= 1)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-csv]** The two CSVs the entry's pgfplots figure reads."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "with open(OUT_DIR / \"kernelmethod_points.csv\", \"w\") as f:\n    f.write(\"x1,x2,label,cls\\n\")\n    for xi, yi in zip(X, y):\n        cls = \"pos\" if yi > 0 else \"neg\"\n        f.write(f\"{xi[0]:.4f},{xi[1]:.4f},{int(yi):+d},{cls}\\n\")\n\nwith open(OUT_DIR / \"kernelmethod_boundary.csv\", \"w\") as f:\n    f.write(\"x1,x2\\n\")\n    for i, s in enumerate(segs):\n        if i:\n            f.write(\"nan,nan\\n\")\n        for p in s[::4]:                        # thin the polyline\n            f.write(f\"{p[0]:.4f},{p[1]:.4f}\\n\")\n        f.write(f\"{s[0][0]:.4f},{s[0][1]:.4f}\\n\")   # close the loop"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-preview]** Data points and legend added to the preview figure; saved."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "ax.scatter(*X[y > 0].T, marker=\"o\", c=\"k\", s=35, label=\"y = +1\")\nax.scatter(*X[y < 0].T, marker=\"s\", facecolors=\"none\", edgecolors=\"k\",\n           s=45, label=\"y = -1\")\nax.set_xlabel(\"x1\"), ax.set_ylabel(\"x2\")\nax.set_aspect(\"equal\")\nax.legend(frameon=False, loc=\"upper right\")\nax.set_title(\"Gaussian-kernel ridge: boundary $\\\\hat{h}(x)=0$\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"kernelmethod.png\", dpi=110)\n\nprint(f\"\\nlinear baseline accuracy: {acc_lin:.2f}\"\n      f\" | kernel method accuracy: {acc_ker:.2f}\"\n      f\" | ||h_hat||^2_Hk = {rkhs_norm2:.2f}\")\nn_ok = sum(ok for _, ok in report)\nprint(f\"{n_ok}/{len(report)} checks pass\")\nprint(f\"wrote {OUT_DIR / 'kernelmethod_points.csv'}, \"\n      f\"{OUT_DIR / 'kernelmethod_boundary.csv'}, {OUT_DIR / 'kernelmethod.png'}\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}