Solved – Valid result when adding two kernels with negative coefficient

kernel trickmachine learningsvm

If $k_1$ and $k_2$ be a kernel in $ \mathbb{R}^n \times \mathbb{R}^n $. we know $k(x,z)=ak_1(x,z) + bk_2(x,z)$ (kernel addition) is still a valid kernel if $\: a,b \geq 0\,$ ($a,b$ is real numbers, scalar) .

That this is valid can be seen from the fact that the results of the kernel function can be interpreted as inner products in feature space. Adding the inner products together amounts to adding both feature spaces together.

Today I was surprised when I read my notes. My TA said $k(x,z)=ak_1(x,z) + bk_2(x,z)$ ("kernel addition") is not a valid kernel for just option (1).

1) $ a<0,b<0$

2) $a<0,b>0$

3) $a>0,b<0$

How is it possible to still have a valid kernel with $(2),(3)$?

Best Answer

Here's an example where option (3) is valid: let $k_1(x, y) = 2 x^T y$, $k_2(x, y) = x^T y$. Then $k_1 - k_2 = \left( (x, y) \mapsto x^T y \right)$ is a valid kernel. (2) can be achieved in the same way, $-k_2 + k_1$ or equivalently $-\frac12 k_1 + 2 k_2$.

In general, other combinations of kernels according to these options may or may not be positive semidefinite. Finding a valid combination becomes a difficult optimization problem.

(1), though, is by definition negative semidefinite. Only the function $k(x, y) = 0$ is both positive and negative semidefinite.

Related Solutions

Solved – Combination of two SVM Kernels

As Dougal comments, you can just add, average or multiply the values of individual kernels. By way of example, the authors of this paper (1) propose methods for combining kernels in the context of ordinal, categorical and continuous-valued data found in clinical medicine. Their solution involves computing a kernel function for each feature, with the function to be computed depending on the type of data involved: they have an ordinal kernel, a categorical kernel and a continuous-valued kernel. Then they scale each of the function values to the $[0,1]$ interval and average the several kernel matrices to produce their final kernel matrix.

To your specific question about how to combine radial and linear kernels, you should consider what properties you want the kernel function to have. The only constraint on kernel functions is that they must be symmetric, positive semi-definite, but within those very general constraints, you can make manipulations of the radial and linear kernel functions' values to emphasize some attributes of your data, or de-emphasize others.

As for achieving a combination of kernel functions with software, that's a programming problem, rather than a statistical one... But in R, supposing that you want to average two kernel matrices $A$ and $B$ of the same dimension, you can use something like

C <- (A+B)/2

and the result is also a square kernel matrix of the same dimension as $A$ and $B$.

Anneleen Daemen and Bart De Moor, "Development of a Kernel Function for Clinical Data," 31st Annual International Conference of the IEEE (2009)

Solved – Is the Gaussian Kernel still a valid Kernel when taking the negative of the inner function

This reasoning is essentially that of Sycorax's answer, but no need to resort to that theorem:

Consider two distinct points $x$ and $y$. For $\theta<0$, their Gram matrix is $$ \begin{bmatrix} k(x, x) & k(x, y) \\ k(x, y) & k(y, y) \end{bmatrix} = \begin{bmatrix} 1 & \alpha \\ \alpha & 1 \end{bmatrix} $$ where $\alpha = k(x, y) = \exp\left( - \frac{\theta}{2} \lVert x - y \rVert^2 \right) = \exp\left( \tfrac12 \lvert{\theta}\rvert \lVert x - y \rVert^2 \right) > 1$, since the argument to $\exp$ is strictly positive.

The characteristic polynomial of this Gram matrix gives $(\lambda - 1)^2 - \alpha^2 = 0$, so that $\lvert \lambda - 1 \rvert = \alpha$, and the eigenvalues of this matrix are $1 + \alpha$ and $1 - \alpha$. Since $\alpha > 1$, that second eigenvalue is negative, and the kernel is not psd.

Best Answer

Related Solutions

Solved – Combination of two SVM Kernels

Solved – Is the Gaussian Kernel still a valid Kernel when taking the negative of the inner function

Related Question