Solved – Prove (or disprove) that this function is a kernel

kernel trickproofsvm

I devised a distance function similar to this form

$d(x,y) = \sum_{i = 1}^{n-1} b(x_i, y_i,x_{i+1}, y_{i+1}) $

with

$b(x_i, y_i,x_{i+1}, y_{i+1}) = 0 \mbox{ if } x_i \leq 0 \vee y_i \leq 0 \vee x_{i+1} \leq 0 \vee y_{i+1} \leq 0$
$b(x_i, y_i,x_{i+1}, y_{i+1}) = \alpha \cdot \frac{x_{i+1}}{y_{i+1}} + (x_i – y_i)^2 \mbox{ else } $
where $\alpha$ is a real number > 0.

And now I want to prove (or disprove) that $e^{-d(x,y)}$ is a kernel which I for example could use in SVMs.

I have read about Mercer's condition, positive semi definiteness and about constructing kernels from existing kernels, but I can't transfer it to this kind of function. Especially, how do I deal with the if-cases in my definition of b?

Any help would be greatly appreciated 🙂

Best Answer

if clauses introduce some nonlinearity, but that's okay. The proposed kernel function does not yield a symmetric kernel matrix and as such definitely not a positive definite kernel and is therefore invalid.

Proof:

$ \begin{align} d(x,y)&\neq d(y,x) \\ \sum_{i = 1}^{n-1} b(x_i, y_i,x_{i+1}, y_{i+1}) &\neq \sum_{i = 1}^{n-1} b(y_i, x_i,y_{i+1}, x_{i+1}) \\ \sum_{i = 1}^{n-1} \alpha \cdot \frac{x_{i+1}}{y_{i+1}} + (x_i - y_i)^2 & \neq \sum_{i = 1}^{n-1} \alpha \cdot \frac{y_{i+1}}{x_{i+1}} + (y_i - x_i)^2 \\ \end{align}$

So no, this is not a valid kernel function. Exponentiating will not salvage it.

You could fix this by making $b$ symmetric, for example:

$b(x_i, y_i,x_{i+1}, y_{i+1})= \alpha \cdot \big( \frac{x_{i+1}}{y_{i+1}} + \frac{y_{i+1}}{x_{i+1}} \big) + (x_i - y_i)^2$

Related Question