Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
You're question is not clear. What do you mean by "such a Kernel" ? do you want a symetric positive definite kernel ? what are $x$ and $y$ ? vectors ? real? The sentence "a proof of a polynomial kernel function" should also be clarified... I am sure you will get an answer to your question rapidely, if you can clarify it ! good luck robin –  robin girard Jul 8 '10 at 14:31
    
My understanding of a Kernel is: An inner product between two real vectors both projected into a higher dimensional feature space, which can instead be performed implicitly in a lower dimensional space. The "kernel function" here is a function that performs this implicit calculation. This probably doesn't describe everything that it is to be a Kernel, although I am still interested in that topic, my primary interest is a solid proof, which may indeed involve that topic. –  mrehayden Jul 8 '10 at 17:10
    
This is the identity that I think defines a kernel. $\kappa(x,y) = <\Phi(x),\Phi(y)>$ $\Phi(\cdot)$ is a function that projects the vectors into a feature space. $\kappa(\cdot,\cdot)$ is the associated kernel function. –  mrehayden Jul 8 '10 at 17:19
    
If you expand both sides of your defining identity with the definition (2) and the feature space of polynomials, the identity holds. So (2) defines a kernel on the feature space of polynomials of degree $\leq d$. This is a rigorous proof, you could find it in a textbook or a paper as it is. And, as you suggested, you can derive (2) from (1) (which defines the kernel over the feature space of homogeneous degree-$d$ polynomials) by adding a dummy variable 1. The underlying operation on polynomials is sometimes known as homogenization/dehomogenization. –  Federico Poloni Aug 26 '10 at 9:38
add comment

3 Answers

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:

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

share|improve this answer
    
However, not everybody in ML lacks rigor: For example, please see: isa.uni-stuttgart.de/Steinwart/Publikationen/… –  Suvrit Oct 21 '10 at 10:09
    
Of course. My remark was not meant to be offensive. H –  Hagen Oct 21 '10 at 11:26
    
I just wanted to point out ;-) I fully agree with the last sentence of your personal remark / opinion though. –  Suvrit Oct 23 '10 at 11:58
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.