The Polynomial Kernel - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:53:37Z http://mathoverflow.net/feeds/question/31030 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31030/the-polynomial-kernel The Polynomial Kernel mrehayden 2010-07-08T12:16:50Z 2010-11-18T10:22:14Z <p>I Have seen two versions of the Polynomial Kernel during my time learning Kernel Methods for things such as regression analysis.</p> <p>1) $\kappa_d(x,y) = (x \cdot y)^d$</p> <p>2) $\kappa_d(x,y) = (x \cdot y + 1)^d$<a href="http://mi.eng.cam.ac.uk/~kkc21/thesis_main/node32.html" rel="nofollow">source</a></p> <p>Without knowing deeply the mathematics behind these things, I attempted a proof of a polynomial kernel function that produces the kernel with all other lower-order polynomial terms (I set $x_i \rightarrow (x_i,1)$) and came out with 2).</p> <p>Is this correct?</p> <p>What Mathematics must I know to perform a rigorous proof of there being such a Kernel?</p> http://mathoverflow.net/questions/31030/the-polynomial-kernel/33705#33705 Answer by sphinx8193 for The Polynomial Kernel sphinx8193 2010-07-28T20:07:31Z 2010-07-28T20:07:31Z <p>A polynomial kernel with degree d consists of all monomials (x.y) of degree <em>up to</em> d (not just d). This is only true for the second definition above ((x.y + 1)^d), as its expansion would suggest. On the other hand, the first definition ((x.y)^d) simply means a <em>linear</em> kernel raised to the power d which won't give the property required by the polynomial kernel of degree d as I mentioned earlier.</p> http://mathoverflow.net/questions/31030/the-polynomial-kernel/41374#41374 Answer by Hagen for The Polynomial Kernel Hagen 2010-10-07T07:33:00Z 2010-10-07T07:33:00Z <p>The precise definition of a kernel function on a set $X$ is this:</p> <p>The function $K:X\times X\rightarrow\mathbb{R}$ is a kernel function if it has the following two properties:</p> <ol> <li>$K(x,y)=K(y,x)$.</li> <li>For all $(x_1,...,x_r )\in X^r$ the matrix $(K(x_i,x_j))_{i,j\in{1,...,r}}$ is positiv semi-definite.</li> </ol> <p>Using basic linear algebra one can prove: the set $K_X$ of all kernel functions on $X$ is a commutative ring with identity taking pointwise addition and multiplication as ring operations. Moreover the product of a kernel function with a non-negative real is a kernel function. In particular it follows that for a polynomial $p(X)$ with non-negative coefficients and every kernel function $K$ on $X$ the function $p(K)$ is a kernel function on $X$. Applying this to the scalar product, which is a kernel function on $\mathbb{R}^n$, one can see that the "polynomial kernel" actually is a kernel function.</p> <p>The ring $K_X$ has much more structure: one can look at limits of kernel functions, power series, orderings etc. </p> <p>Personal remark / opinion: according to my experience the people in the maschine learning community tend to ignore the rigorous theory in favor of a more computational / pragmatic point of view. One can learn the theory of kernels much better from publications in functional analysis for example, where kernels are arising in the theory of functional Hilbert spaces. </p> <p>Hagen</p> http://mathoverflow.net/questions/31030/the-polynomial-kernel/41379#41379 Answer by S. Sra for The Polynomial Kernel S. Sra 2010-10-07T08:07:43Z 2010-10-07T08:07:43Z <p>Here is a quick proof (which essentially expands F. Poloni's comment above it seems) of why $k(x,y) = (\langle x, y \rangle + c)^d$ is a kernel function (assuming for now $x, y \in R^k$, $c \ge 0$, and $d$ a positive integer):</p> <p>To prove that $k(x,y)$ is a kernel-function, all you have to do (as H. Knaf pointed out, things can be made rigorous) is to prove that for an arbitrary set of $n$ vectors, $x_1,...,x_n$, the associated matrix $K_{ij} = k(x_i,x_j)$ is positive-definite. </p> <p>Now, for the easy case $c=0$ above, just recall the fact that the Hadamard product of two positive definite matrices is again positive-definite. Take $d$ Hadamard products of the positive-definite matrix $\langle x_i,x_j \rangle$ (a Gram matrix, hence posdef).</p> <p>The case $c > 0$ is also simple, and one essentially uses one more fact there: the sum of two positive-definite matrices is again positive-definite.</p> <p>I hope my quickly sketched out answer is clear enough; if not, I can try to add more details for you.</p>