8
$\begingroup$

I'm considering using the following simple function as an SVM kernel. It basically computes the distance between the 2 input vectors (norm):

$K(\vec{x}_1, \vec{x}_2) = \left\| \vec{x}_1- \vec{x}_2 \right\|$, where $\vec{x}_1$ and $\vec{x}_2$ are $N$-dimensional vectors.

I'm not familiar with documentation of such a kernel.

Is it valid? Anyone experienced with such a kernel?

$\endgroup$

1 Answer 1

9
$\begingroup$

No, this kernel doesn't give a positive (semi-) definite Gram matrix, so it is not a valid kernel (the first randomly generated Gram matrix $\matrix{K}$ and vector $\vec{v}$ I tried gave $\vec{v}'\matrix{K}\vec{v} < 0$ so $\matrix{K}$ isn't positive semi-definite. If you infer from that that I am an engineer - you are correct! ;o).

ISTR that Kernel functions need to be "diagonally dominant", i.e. the largest magnitude element in any row or column needs to be the one on the principal diagonal, which won't be true here as the principal diagonal is all zeros (the distance from any point to itself being zero). This is guaranteed for the RBF kernel as taking the negative exponential of the distance can never be greater than 1, which ocurrs when $\vec{x}_1$ and $\vec{x}_2$ are the same. Note however if the kernel is too diagonally dominant then it is likely to lead to over-fitting.

$\endgroup$
5
  • $\begingroup$ Thanks. Where would I find a brief to-the-point list of all conditions that must be satisfied by a function for it to qualify as an SVM kernel? $\endgroup$
    – Bliss
    Commented Jan 1, 2012 at 13:24
  • $\begingroup$ I think positive (semi-) definiteness of the kernel matrix for any sample of data is pretty much it, as then the kernel matric can be interpreted as a covariance matrix computed in some feature space. $\endgroup$ Commented Jan 1, 2012 at 15:21
  • $\begingroup$ Thanks. I'm costumed to referring kernels' function-representation and not matrix representation, i.e. K = f(X1,X2). Could you define the required terms on function level? $\endgroup$
    – Bliss
    Commented Jan 2, 2012 at 13:41
  • $\begingroup$ I think you need to get into eigenfunctions to do that, which I am not that familiar with. $\endgroup$ Commented Jan 2, 2012 at 15:01
  • 2
    $\begingroup$ For posterity, it's worth noting that "diagonally dominant" has a technical meaning which is much more stringent than the version you've said. In any case, there is a formal version of that property: we must have $k(x, y) \le \sqrt{ k(x, x) k(y,y) }$. (This is the Cauchy-Scwarz inequality in the induced feature space of the kernel.) $\endgroup$
    – Danica
    Commented Apr 21, 2015 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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