Editing Support vector machine (section)

== Nonlinear kernels ==
[[File:Kernel_Machine.svg|thumb|Kernel machine]]
The original maximum-margin hyperplane algorithm proposed by Vapnik in 1963 constructed a [[linear classifier]]. However, in 1992, [[Bernhard Boser]], [[Isabelle Guyon]] and [[Vladimir Vapnik]] suggested a way to create nonlinear classifiers by applying the [[kernel trick]] (originally proposed by Aizerman et al.<ref>{{cite journal |last1=Aizerman |first1=Mark A. |last2=Braverman |first2=Emmanuel M. |last3=Rozonoer |first3=Lev I. |name-list-style=amp |year=1964 |title=Theoretical foundations of the potential function method in pattern recognition learning |journal=Automation and Remote Control |volume=25 |pages=821–837 }}</ref>) to maximum-margin hyperplanes.<ref name="ReferenceA" /> The kernel trick, where [[dot product]]s are replaced by kernels, is easily derived in the dual representation of the SVM problem. This allows the algorithm to fit the maximum-margin hyperplane in a transformed [[feature space]]. The transformation may be nonlinear and the transformed space high-dimensional; although the classifier is a hyperplane in the transformed feature space, it may be nonlinear in the original input space.

It is noteworthy that working in a higher-dimensional feature space increases the [[generalization error]] of support vector machines, although given enough samples the algorithm still performs well.<ref>{{cite conference |last1=Jin |first1=Chi |last2=Wang |first2=Liwei |title=Dimensionality dependent PAC-Bayes margin bound |conference=Advances in Neural Information Processing Systems |year=2012 |url=http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound |url-status=live |archive-url=https://web.archive.org/web/20150402185336/http://papers.nips.cc/paper/4500-dimensionality-dependent-pac-bayes-margin-bound |archive-date=2015-04-02 |citeseerx=10.1.1.420.3487  }}</ref>

Some common kernels include:
* [[Homogeneous polynomial|Polynomial (homogeneous)]]: <math>k(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j)^d</math>. Particularly, when <math>d = 1</math>, this becomes the linear kernel.
* [[Polynomial kernel|Polynomial]] (inhomogeneous): <math>k(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + r)^d</math>.
* Gaussian [[Radial basis function kernel|radial basis function]]: <math>k(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\gamma \left\|\mathbf{x}_i - \mathbf{x}_j\right\|^2\right)</math> for <math>\gamma > 0</math>. Sometimes parametrized using <math>\gamma = 1/(2\sigma^2)</math>.
* [[Sigmoid function]] ([[Hyperbolic tangent]]): <math>k(\mathbf{x_i}, \mathbf{x_j}) = \tanh(\kappa \mathbf{x}_i \cdot \mathbf{x}_j + c)</math> for some (not every) <math>\kappa > 0 </math> and <math>c < 0</math>.

The kernel is related to the transform <math>\varphi(\mathbf{x}_i)</math> by the equation <math>k(\mathbf{x}_i, \mathbf{x}_j) = \varphi(\mathbf{x}_i) \cdot \varphi(\mathbf{x}_j)</math>. The value {{math|'''w'''}} is also in the transformed space, with <math display="inline">\mathbf{w} = \sum_i \alpha_i y_i \varphi(\mathbf{x}_i)</math>. Dot products with {{math|'''w'''}} for classification can again be computed by the kernel trick, i.e. <math display="inline"> \mathbf{w} \cdot \varphi(\mathbf{x}) = \sum_i \alpha_i y_i k(\mathbf{x}_i, \mathbf{x})</math>.