Kernel nonparametric regression

One of the methods for nonparametric regression is using kernels. My question is what are the conditions on the kernels functions in this method? In other words how can I decide if a given function can be used as a kernel?

Thanks

1 Answer

Notion of a kernel has a strict mathematical definition (from here):

Definition. $k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ is a kernel if

1. $k$ is symmetric: $k(x,y) =k(y,x)$.
2. $k$ is positive semi-definite, i.e., $\forall x_1,x_2,...,x_n \in \mathcal{X}$, the ”Gram Matrix” $K$ defined by $K_{ij}=k(x_i,x_j)$ is positive semi-definite. (A matrix $M \in \mathbb{R}^{n \times n}$ is positive semi-definite if $\forall a \in \mathbb{R}^n, a'Ma\ge0$.)

Intuition behind a kernel is that it implicitly maps its input to some space (possibly infinite-dimensional), and then computes an inner product in that space:

$$k(x, y) = \phi(x)^T \phi(y)$$

Then $K$ is effectively a Gram matrix, so you have to check if it's symmetric and positive-definite. This is not something you can test on a computer, you'll have to prove it mathematically.

Mercer's theorem says that a kernel can be represented as $$k(s, t) = \sum_{j=1}^\infty \lambda_j e_j(t) e_j(s)$$ for some non-negative $\lambda$. From this form it easily follows that $K$ is positive semi-definite. So if you can represent your function in a form of RHS of the above equation, your function is a kernel.

You can also show a function is a kernel if you decompose it into a combination of known-to-be kernels:

• Sum of two kernels is a kernel
• A kernel multiplied by a positive number is a kernel