Number of eigenfunctions for kernel

Question

While studying machine learning, I've read the following statement:

The kernel $K(x,y)=(x\cdot y+1)^d$ , for $x, y \in \mathbb{R}^p$, has $M={p+d \choose d}$ eigenfunctions that span the space of polynomials in $\mathbb{R}^p$ of total degree $d$.

I do not understand how does the $M={p+d \choose d}$ come from? What does exactly the degree $d$ mean here?

Answer 1

The polynomial kernel $K(x,y) = (x \cdot y + 1)^d$ is easily represented in terms of monomials. The degree $d$ is the maximum degree of the polynomial computed by the kernel and therefore also the maximum degree of any contained monomial.

The problem of determining the number of monomials of degree exactly $d$ in $p$ input variables is the same as the problem of finding the number of combinations to draw $d$ elements from a bin with $p$ different elements. The number of such $d$-combinations is

$$\left(\!\!{d \choose p}\!\!\right) = {d + p - 1 \choose d} = {d + p - 1 \choose p - 1}.$$

However, we need to consider all monomials of degree $k = 0, \ldots, d$. Using $\sum_{j=k}^{n}{j \choose k} = {n+1 \choose k+1}$ we get

$$ \sum_{k=0}^{d}{p - 1 + k \choose p - 1} = \sum_{k=(p-1)}^{(p-1)+d}{k \choose p - 1} = {p + d \choose p} = {p + d \choose d}.$$

Addendum: This formula also nicely showcases the power of kernel functions: Just consider the case where $p = 256$ and $d = 2$. The kernel calculates the scalar product of two vectors (representing the scalar in front of each monomial base function) in a space with dimension ${d + p \choose d} = {256 + 2 \choose 2} = 33153$. An explicit scalar product computation thus involves 33153 multiplications and additions, while the kernel needs $p + d - 1 = 257$ multiplications and $p = 256$ additions.

Answer 2

Take a simple example, if $x,z \in \mathbb{R}^2$, and $d=2$, then,

$$ (\left< x , z \right> + 1)^2 = (x_1z_1 + x_2z_2 + 1)^2 $$ $$ = x_1^2z_1^2 + x_2^2z_2^2 + 2x_1z_1x_2z_2 +x_1z_1 + x_2z_2 + 1$$ $$ = \left< (x_1^2, x_2^2, \sqrt{2}x_1x_2, x_1, x_2, 1), (z_1^2, z_2^2, \sqrt{2}z_1z_2, z_1, z_2, 1) \right> $$ $$ = \left< \phi(\bf{x}), \phi(\bf{z}) \right> $$

where $\phi(\cdot)$ is the feature map, which we can see has 6 eigenfunctions. In this case $p=2$ and $d=2$, so there should be $\left( \begin{array}{c} 4 \\ 2 \end{array} \right) = 6$ eigenfunctions, as predicted. This is trivial but laborious to show for higher dimensions or higher polynomial degree orders.