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?


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.

  • $\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 Jan 1 '12 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$ – Dikran Marsupial Jan 1 '12 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 Jan 2 '12 at 13:41
  • $\begingroup$ I think you need to get into eigenfunctions to do that, which I am not that familiar with. $\endgroup$ – Dikran Marsupial Jan 2 '12 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 Apr 21 '15 at 6:50

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.