8
$\begingroup$

In support vector machines (SVMs) and other Kernel based methods, like Gaussian processes, the Kernel replaces the inner product of two feature vectors $k(x_n,x_m)=x_n^Tx_m$. The Gaussian kernel

$$k(x_n,x_m) = \exp(- \frac{\theta}{2} \lVert x_n-x_m\rVert^2)$$ is a valid kernel function when $\theta \ge 0$. $\theta$ then plays the role of the inverse variance (precision).

My question is, is this function still a valid kernel function for SVMs and Gaussian processes when $\theta<0$?

$\endgroup$
  • 1
    $\begingroup$ one of the criteria of "valid" probably involves that it integrates to something finite, so no, it's not: en.wikipedia.org/wiki/… $\endgroup$ – Taylor Oct 26 '16 at 20:34
  • $\begingroup$ @Taylor I thought the only criterion is that the kenel matrix be semi-positive definite. $\endgroup$ – tomka Oct 26 '16 at 20:46
  • $\begingroup$ @tomka Thanks for your question, but what exactly is your definition of kernel here? Is it that for every set of vectors $\{x_1,...x_n\}$, the matrix $K:=[k(x_i,x_j)]$ is positive semi-definite? If it's indeed your definition of kernel, then why does Theorem 2.5.3 of the note mentioned by Dougal, math.iit.edu/~fass/603_ch2.pdf, not prove immediately that with negative $\theta, k$ in your definition won't be a Gaussian kernel? $\endgroup$ – Mathmath Jan 20 at 21:40
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Dougal I just found a similar discussion on mathematics SE which seems to suggest (as acceped answer) the opposite of what you claim. I cannot fully follow their argument. Can you check? math.stackexchange.com/questions/248976/… $\endgroup$ – tomka Oct 27 '16 at 12:55
  • 1
    $\begingroup$ @tomka That question is about $\exp(- \alpha \lVert x - y \rVert )$ for $\alpha > 0$; it doesn't conflict with this answer. $\endgroup$ – djs Oct 27 '16 at 12:59
  • $\begingroup$ @Dougal but doesn't the logic of monotonicity in the answer apply also if $\alpha<0$ $\endgroup$ – tomka Oct 27 '16 at 13:03
  • 1
    $\begingroup$ @tomka "Completely monotone" doesn't just mean "monotone everywhere" or something like that; it's defined e.g. in Definition 2.5.1 of the linked book chapter. One of the requirements is that $\varphi'(r) \le 0$, which holds for $f(r) = \exp\left( - \alpha r \right)$ when $\alpha \ge 0$ but not for $\alpha < 0$. $\endgroup$ – djs Oct 27 '16 at 13:08
  • 1
    $\begingroup$ @Mathmath Yes. But we’re not trying to prove that a kernel is psd; we’re showing that it’s not by exhibiting a specific $\{x_1, x_2\}$ for which the kernel matrix is not psd; hence the kernel function is not psd. $\endgroup$ – djs Jan 21 at 4:09
3
$\begingroup$

This is an extended comment, please don't judge me too harshly.

Mercer's theorem characterizes the positive semidefinite (PSD) kernel which is of interest to OP. Mercer provides two conditions for a valid kernel:

  1. The function is symmetric: $f(x,y)=f(y,x)$.
  2. The resulting kernel matrix $K_{n\times n}$ is PSD for all valid inputs, which implies that its eigenvalues are all nonnegative. (Kernels may be restricted to only consider specific intervals or sets, so it's feasible to define a kernel that is PSD for just some input values.)

Let's approach the problem by cases.

Note that $\theta=0$ results in a matrix of 1s. It has rank 1, and has the eigenvalue 1 once and the remaining $n-1$ of its eigenvalues are 0. Hence, it is PSD.

For $\theta>0$, the farther apart two points are, the smaller the similarity between them. Unless two points are identical, the off-diagonal elements of $K$ are less than 1, and the diagonal elements are 1.

We can use the same reasoning to show that for $\theta<0$, $K$ is not diagonally dominant; that is, non-idential elements will have larger entries on the off-diagonal than the diagonal (because $f(x,y;\theta<0)$ is convex with a minimum at 1). I think that we could get clever with the Girshgorin circle theorem to show that in this case, the matrix is indefinite, but I've tried and am stuck. I'll keep thinking about it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! This is a sophisticated approach - I am not familiar with the two theorems. I made a different attempt in an own answer below after some more thinking and litertature study. Please check. $\endgroup$ – tomka Oct 26 '16 at 22:40
  • 1
    $\begingroup$ Note that "diagonally dominant" means that the diagonal entry is larger than the sum of the off-diagonal elements in its row, not merely that the diagonal is the largest entry. RBF kernel matrices are not necessarily diagonally dominant, so the theorem you pointed to doesn't actually suffice in the $\theta > 0$ case. (That said, Girshgorin circle theorem is neat and I hadn't seen it before, so thanks for bringing it up!) $\endgroup$ – djs Oct 26 '16 at 23:54
  • $\begingroup$ @Dougal Merp. Corrected. This is what I get for writing CV answers when in a hurry. $\endgroup$ – Sycorax Oct 27 '16 at 0:01
1
$\begingroup$

After some more thinking I will make an attempt to answer my own question. From Bishop's Pattern Recognition and Machine Learning, p. 296, I take rules for building new Kernels from valid Kernels. Let $k_1$ be a valid Kernel then

$$ k(x_n,x_m) = f(x) k_1(x_n,x_m) f(x^T) $$ $$ k(x_n,x_m) = \exp(k_1(x_n,x_m)) $$

are again valid Kernels. Now we have

$$\frac{\theta}{2} \lVert x_n-x_m \rVert^2 = \frac{\theta}{2} x_n^T x_n + \frac{\theta}{2} x_m^T x_m - \theta x_n^T x_m$$

So

$$\exp (-\frac{\theta}{2} \lVert x_n-x_m \rVert^2)= \exp (-\frac{\theta}{2} x_n^T x_n) \exp (\theta x_n^T x_m) \exp (-\frac{\theta}{2} x_m^T x_m)$$

Hence by the second rule from above and since we know $x_n^T x_m$ is a valid kernel, $\exp (\theta x_n^T x_m) $ is a valid kernel if $\theta>0$, but it is not if $\theta<0$. By the first rule then $\exp (-\frac{\theta}{2} \lVert x_n-x_m \rVert^2)$ is a valid kernel if $\theta>0$ but not if $\theta<0$. I am not sure about this though. Comments welcome.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is a valid way to prove that it is a kernel for $\theta > 0$, but doesn't prove that it isn't for $\theta < 0$, as far as I can tell. $\endgroup$ – djs Oct 26 '16 at 23:42
  • $\begingroup$ @Dougal Do I understand correctly that you say it is not a valid proof because it may still hold that $\exp(-k_1)$ also gives a valid Kernel? What if I knew this is not the case, so that the inner function has to be positive? $\endgroup$ – tomka Oct 27 '16 at 8:28
  • $\begingroup$ The property from Bishop is that ($k$ is a pd kernel) => ($\exp(k)$ is a pd kernel). It doesn't show the converse, which you would need to prove (and which I'm not confident is true). $\endgroup$ – djs Oct 27 '16 at 11:25
  • $\begingroup$ Whoops, yes, fixed. (And I should know....) $\endgroup$ – djs Oct 27 '16 at 11:28
  • $\begingroup$ @Dougal. Ok then I understand you correctly. However, it is possible that the list given in Bishop is exclusive. If that is true, then it is a proof because the converse is not part of that list. $\endgroup$ – tomka Oct 27 '16 at 11:30

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.