Repository: scikit-learn/scikit-learn
File: benchmarks/bench_plot_polynomial_kernel_approximation.py (Python)

Code before:

An example illustrating the approximation of the feature map
of a Homogeneous Polynomial kernel.

.. currentmodule:: sklearn.kernel_approximation

It shows how to use :class:`PolynomialCountSketch` and :class:`Nystroem` to
approximate the feature map of a polynomial kernel for
classification with an SVM on the digits dataset. Results using a linear
SVM in the original space, a linear SVM using the approximate mappings
and a kernelized SVM are compared.

The first plot shows the classification accuracy of Nystroem [2]_ and
PolynomialCountSketch [1]_ as the output dimension (n_components) grows.
It also shows the accuracy of a linear SVM and a polynomial kernel SVM
on the same data.

The second plot explores the scalability of PolynomialCountSketch
and Nystroem. For a sufficiently large output dimension,
PolynomialCountSketch should be faster as it is O(n(d+klog k))
while Nystroem is O(n(dk+k^2)). In addition, Nystroem requires
a time-consuming training phase, while training is almost immediate
for PolynomialCountSketch, whose training phase boils down to
initializing some random variables (because is data-independent).

References
----------
.. [1] Pham, N., & Pagh, R. (2013, August). Fast and scalable polynomial
       kernels via explicit feature maps. In Proceedings of the 19th ACM
           SIGKDD International Conference on Knowledge Discovery and Data
           Mining (pp. 239-247)
           (https://chbrown.github.io/kdd-2013-usb/kdd/p239.pdf)

.. [2] Charikar, M., Chen, K., & Farach-Colton, M. (2002, July).
       Finding frequent items in data streams. In International Colloquium
           on Automata, Languages, and Programming (pp. 693-703).
           Springer, Berlin, Heidelberg.
           (https://people.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf)

"""

# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause

# Load data manipulation functions
# Will use this for timing results
from time import time

# Some common libraries
import matplotlib.pyplot as plt
import numpy as np

Review comment (suggestion):
There is not a real need to change the reference here because the scripts in the `benchmarks` are not part of the doc.

Code after:

An example illustrating the approximation of the feature map
of an Homogeneous Polynomial kernel.

.. currentmodule:: sklearn.kernel_approximation

It shows how to use :class:`PolynomialCountSketch` and :class:`Nystroem` to
approximate the feature map of a polynomial kernel for
classification with an SVM on the digits dataset. Results using a linear
SVM in the original space, a linear SVM using the approximate mappings
and a kernelized SVM are compared.

The first plot shows the classification accuracy of Nystroem [2] and
PolynomialCountSketch [1] as the output dimension (n_components) grows.
It also shows the accuracy of a linear SVM and a polynomial kernel SVM
on the same data.

The second plot explores the scalability of PolynomialCountSketch
and Nystroem. For a sufficiently large output dimension,
PolynomialCountSketch should be faster as it is O(n(d+klog k))
while Nystroem is O(n(dk+k^2)). In addition, Nystroem requires
a time-consuming training phase, while training is almost immediate
for PolynomialCountSketch, whose training phase boils down to
initializing some random variables (because is data-independent).

[1] Pham, N., & Pagh, R. (2013, August). Fast and scalable polynomial
kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD
international conference on Knowledge discovery and data mining (pp. 239-247)
(https://chbrown.github.io/kdd-2013-usb/kdd/p239.pdf)

[2] Charikar, M., Chen, K., & Farach-Colton, M. (2002, July). Finding frequent
items in data streams. In International Colloquium on Automata, Languages, and
Programming (pp. 693-703). Springer, Berlin, Heidelberg.
(https://people.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf)

"""

# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause

# Load data manipulation functions
# Will use this for timing results
from time import time

# Some common libraries
import matplotlib.pyplot as plt
import numpy as np

from sklearn.datasets import load_digits
from sklearn.kernel_approximation import Nystroem, PolynomialCountSketch
from sklearn.model_selection import train_test_split