2
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$ Jul 8, 2010 at 14:31
  • $\begingroup$ 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. $\endgroup$
    – mrehayden
    Jul 8, 2010 at 17:10
  • $\begingroup$ 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. $\endgroup$
    – mrehayden
    Jul 8, 2010 at 17:19
  • $\begingroup$ 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. $\endgroup$ Aug 26, 2010 at 9:38

3 Answers 3

2
$\begingroup$

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 [not exactly: see comments] 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

$\endgroup$
4
  • 1
    $\begingroup$ However, not everybody in ML lacks rigor: For example, please see: isa.uni-stuttgart.de/Steinwart/Publikationen/… $\endgroup$
    – Suvrit
    Oct 21, 2010 at 10:09
  • $\begingroup$ Of course. My remark was not meant to be offensive. H $\endgroup$
    – Hagen
    Oct 21, 2010 at 11:26
  • $\begingroup$ I just wanted to point out ;-) I fully agree with the last sentence of your personal remark / opinion though. $\endgroup$
    – Suvrit
    Oct 23, 2010 at 11:58
  • 2
    $\begingroup$ Note for others: as pointed out implicitly at mathoverflow.net/questions/328532/… it is not true that $K_X$ is a ring, but rather it is a "ring-without-negatives" or a rig $\endgroup$
    – Yemon Choi
    Apr 20, 2019 at 14:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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