I devised a distance function similar to this form. K(x,y)=(-||x-y||+xy+1)/2

And now I want to prove it is a kernel function.I have read about Mercer's condition and positive semi definiteness, but I still do not know how to prove it?

If it is not a kernel function, can it be kernel function when x and y are 1 or 0?

Any help would be greatly appreciated :)


To answer your first question, the kernel function must be symmetric, i.e.

$K(\mathbf{x}, \mathbf{y}) = K(\mathbf{y}, \mathbf{x})$

and positive semi definite, which we can prove if we can factorise the kernel function in the form of a dot product

$K(\mathbf{x}, \mathbf{y}) = <f(\mathbf{x}),f(\mathbf{y})>$

where $f(x)$ is a vector function. In this case, I suspect your input is scalar, so in this case becomes:

$K(x, y) = <g(x),g(y)>$

where g is a scalar function, meaning we need to determine if there exists a function $g(x)$ which is the square root of

$(-|x-y|+xy+1)/2 = (-\sqrt{(x-y)^2}+xy+1)/2$.

The trickiest part here is showing that $-\sqrt{(x-y)^2}$ can be written as a product of two sets of symmetric terms, one in x and one in y. That might be possible, but it would involve imaginary elements since we have a minus sign at the front of the $-\sqrt{(x-y)^2}$ term.

Instead we can check for positive semi-definiteness by trying to find points that violate this rule, i.e. where the function is decreasing. This is quite easy to do, for example if $y = 0$ and $x = 10$, then $K(x,y) = -9/2$. If $y$ remains equal to 0 then as $x$ increases to 100, we see that $K(x,y)$ decreases to $-99/2$. Therefore the function is not positive semi-definite. You can check this property more rigorously by taking the partial derivatives of the kernel function and show whether or not they are non-negative for all x and y.

To answer your second question, "If it is not a kernel function, can it be kernel function when x and y are 1 or 0?" the answer is no, since you would have to define the function only valid for x = y = 1 = 0, or x = y = 1, (since the above must hold for all values of the input domain due to symmetry requirement) by restricting the domain of the inputs to a single value, and then there is no concept of positive semi-definiteness (no gradient).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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