{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Scalable learning with polynomial kernel approximation\n\n.. currentmodule:: sklearn.kernel_approximation\n\nThis example illustrates the use of :class:`PolynomialCountSketch` to\nefficiently generate polynomial kernel feature-space approximations.\nThis is used to train linear classifiers that approximate the accuracy\nof kernelized ones.\n\nWe use the Covtype dataset [2], trying to reproduce the experiments on the\noriginal paper of Tensor Sketch [1], i.e. the algorithm implemented by\n:class:`PolynomialCountSketch`.\n\nFirst, we compute the accuracy of a linear classifier on the original\nfeatures. Then, we train linear classifiers on different numbers of\nfeatures (`n_components`) generated by :class:`PolynomialCountSketch`,\napproximating the accuracy of a kernelized classifier in a scalable manner.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Preparing the data\n\nLoad the Covtype dataset, which contains 581,012 samples\nwith 54 features each, distributed among 6 classes. The goal of this dataset\nis to predict forest cover type from cartographic variables only\n(no remotely sensed data). After loading, we transform it into a binary\nclassification problem to match the version of the dataset in the\nLIBSVM webpage [2], which was the one used in [1].\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.datasets import fetch_covtype\n\nX, y = fetch_covtype(return_X_y=True)\n\ny[y != 2] = 0\ny[y == 2] = 1  # We will try to separate class 2 from the other 6 classes."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Partitioning the data\n\nHere we select 5,000 samples for training and 10,000 for testing.\nTo actually reproduce the results in the original Tensor Sketch paper,\nselect 100,000 for training.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.model_selection import train_test_split\n\nX_train, X_test, y_train, y_test = train_test_split(\n    X, y, train_size=5_000, test_size=10_000, random_state=42\n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Feature normalization\n\nNow scale features to the range [0, 1] to match the format of the dataset in\nthe LIBSVM webpage, and then normalize to unit length as done in the\noriginal Tensor Sketch paper [1].\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.pipeline import make_pipeline\nfrom sklearn.preprocessing import MinMaxScaler, Normalizer\n\nmm = make_pipeline(MinMaxScaler(), Normalizer())\nX_train = mm.fit_transform(X_train)\nX_test = mm.transform(X_test)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Establishing a baseline model\n\nAs a baseline, train a linear SVM on the original features and print the\naccuracy. We also measure and store accuracies and training times to\nplot them later.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import time\n\nfrom sklearn.svm import LinearSVC\n\nresults = {}\n\nlsvm = LinearSVC()\nstart = time.time()\nlsvm.fit(X_train, y_train)\nlsvm_time = time.time() - start\nlsvm_score = 100 * lsvm.score(X_test, y_test)\n\nresults[\"LSVM\"] = {\"time\": lsvm_time, \"score\": lsvm_score}\nprint(f\"Linear SVM score on raw features: {lsvm_score:.2f}%\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Establishing the kernel approximation model\n\nThen we train linear SVMs on the features generated by\n:class:`PolynomialCountSketch` with different values for `n_components`,\nshowing that these kernel feature approximations improve the accuracy\nof linear classification. In typical application scenarios, `n_components`\nshould be larger than the number of features in the input representation\nin order to achieve an improvement with respect to linear classification.\nAs a rule of thumb, the optimum of evaluation score / run time cost is\ntypically achieved at around `n_components` = 10 * `n_features`, though this\nmight depend on the specific dataset being handled. Note that, since the\noriginal samples have 54 features, the explicit feature map of the\npolynomial kernel of degree four would have approximately 8.5 million\nfeatures (precisely, 54^4). Thanks to :class:`PolynomialCountSketch`, we can\ncondense most of the discriminative information of that feature space into a\nmuch more compact representation. While we run the experiment only a single time\n(`n_runs` = 1) in this example, in practice one should repeat the experiment several\ntimes to compensate for the stochastic nature of :class:`PolynomialCountSketch`.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.kernel_approximation import PolynomialCountSketch\n\nn_runs = 1\nN_COMPONENTS = [250, 500, 1000, 2000]\n\nfor n_components in N_COMPONENTS:\n    ps_lsvm_time = 0\n    ps_lsvm_score = 0\n    for _ in range(n_runs):\n        pipeline = make_pipeline(\n            PolynomialCountSketch(n_components=n_components, degree=4),\n            LinearSVC(),\n        )\n\n        start = time.time()\n        pipeline.fit(X_train, y_train)\n        ps_lsvm_time += time.time() - start\n        ps_lsvm_score += 100 * pipeline.score(X_test, y_test)\n\n    ps_lsvm_time /= n_runs\n    ps_lsvm_score /= n_runs\n\n    results[f\"LSVM + PS({n_components})\"] = {\n        \"time\": ps_lsvm_time,\n        \"score\": ps_lsvm_score,\n    }\n    print(\n        f\"Linear SVM score on {n_components} PolynomialCountSketch \"\n        + f\"features: {ps_lsvm_score:.2f}%\"\n    )"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Establishing the kernelized SVM model\n\nTrain a kernelized SVM to see how well :class:`PolynomialCountSketch`\nis approximating the performance of the kernel. This, of course, may take\nsome time, as the SVC class has a relatively poor scalability. This is the\nreason why kernel approximators are so useful:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.svm import SVC\n\nksvm = SVC(C=500.0, kernel=\"poly\", degree=4, coef0=0, gamma=1.0)\n\nstart = time.time()\nksvm.fit(X_train, y_train)\nksvm_time = time.time() - start\nksvm_score = 100 * ksvm.score(X_test, y_test)\n\nresults[\"KSVM\"] = {\"time\": ksvm_time, \"score\": ksvm_score}\nprint(f\"Kernel-SVM score on raw features: {ksvm_score:.2f}%\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Comparing the results\n\nFinally, plot the results of the different methods against their training\ntimes. As we can see, the kernelized SVM achieves a higher accuracy,\nbut its training time is much larger and, most importantly, will grow\nmuch faster if the number of training samples increases.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\n\nfig, ax = plt.subplots(figsize=(7, 7))\nax.scatter(\n    [\n        results[\"LSVM\"][\"time\"],\n    ],\n    [\n        results[\"LSVM\"][\"score\"],\n    ],\n    label=\"Linear SVM\",\n    c=\"green\",\n    marker=\"^\",\n)\n\nax.scatter(\n    [\n        results[\"LSVM + PS(250)\"][\"time\"],\n    ],\n    [\n        results[\"LSVM + PS(250)\"][\"score\"],\n    ],\n    label=\"Linear SVM + PolynomialCountSketch\",\n    c=\"blue\",\n)\n\nfor n_components in N_COMPONENTS:\n    ax.scatter(\n        [\n            results[f\"LSVM + PS({n_components})\"][\"time\"],\n        ],\n        [\n            results[f\"LSVM + PS({n_components})\"][\"score\"],\n        ],\n        c=\"blue\",\n    )\n    ax.annotate(\n        f\"n_comp.={n_components}\",\n        (\n            results[f\"LSVM + PS({n_components})\"][\"time\"],\n            results[f\"LSVM + PS({n_components})\"][\"score\"],\n        ),\n        xytext=(-30, 10),\n        textcoords=\"offset pixels\",\n    )\n\nax.scatter(\n    [\n        results[\"KSVM\"][\"time\"],\n    ],\n    [\n        results[\"KSVM\"][\"score\"],\n    ],\n    label=\"Kernel SVM\",\n    c=\"red\",\n    marker=\"x\",\n)\n\nax.set_xlabel(\"Training time (s)\")\nax.set_ylabel(\"Accuracy (%)\")\nax.legend()\nplt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### References\n\n[1] Pham, Ninh and Rasmus Pagh. \"Fast and scalable polynomial kernels via\nexplicit feature maps.\" KDD '13 (2013).\nhttps://doi.org/10.1145/2487575.2487591\n\n[2] LIBSVM binary datasets repository\nhttps://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html\n\n"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.9.21"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}