The Polynomial Kernel - MathOverflow

The Polynomial Kernel

2010-07-08T12:16:50Z

I Have seen two versions of the Polynomial Kernel during my time learning Kernel Methods for things such as regression analysis.

1) $\kappa_d(x,y) = (x \cdot y)^d$

2) $\kappa_d(x,y) = (x \cdot y + 1)^d$source

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).

Is this correct?

What Mathematics must I know to perform a rigorous proof of there being such a Kernel?

Answer by sphinx8193 for The Polynomial Kernel

2010-07-28T20:07:31Z

A polynomial kernel with degree d consists of all monomials (x.y) of degree up to 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 linear kernel raised to the power d which won't give the property required by the polynomial kernel of degree d as I mentioned earlier.

Answer by Hagen for The Polynomial Kernel

2010-10-07T07:33:00Z

The precise definition of a kernel function on a set $X$ is this:

The function $K:X\times X\rightarrow\mathbb{R}$ is a kernel function if it has the following two properties:

$K(x,y)=K(y,x)$.
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.

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.

The ring $K_X$ has much more structure: one can look at limits of kernel functions, power series, orderings etc.

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.

Hagen

Answer by S. Sra for The Polynomial Kernel

2010-10-07T08:07:43Z

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):

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.

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).

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.

I hope my quickly sketched out answer is clear enough; if not, I can try to add more details for you.