2
$\begingroup$

Is there an absolute need to use a PSD kernel for Gaussian processes (and maybe SVMs?)

For example, If I used a Minkowski distance with 0 < p < 1, the function would is not convex, and thus I would assume that the matrix K would not be positive semi definite.

In Gaussian Process regression, we would need to invert the covariance matrix to do inference. What would it mean to have negative eigenvalues in terms of this inference?

Is there any corrections that can be done so I can use a Minkowski distance function 0 < p < 1?

$\endgroup$
9
$\begingroup$

Say that $X \sim \mathcal{GP}(m(\cdot), k(\cdot, \cdot))$.

If $k$ is not a PSD kernel, then there is some set of $n$ points $\{ t_i \}_{i=1}^n$ and corresponding weights $\alpha_i \in \mathbb R$ such that $$\sum_{i=1}^n \sum_{j=1}^n \alpha_i k(t_i, t_j) \alpha_j < 0.$$

Now, consider the joint distribution of $\big(X(t_i) \big)$. By the GP assumption, $$\operatorname{Cov}(X(t_i), X(t_j)) = k(t_i, t_j).$$ But then $$ \operatorname{Var}\left( \sum_{i=1}^n \alpha_i X(t_i) \right) = \sum_{i=1}^n \sum_{j=1}^n \alpha_i \operatorname{Cov}(X(t_i), X(t_j)) \alpha_j < 0 ,$$ which is nonsensical. So a GP with a non-PSD kernel isn't a valid random process. How much that matters to your application depends on what you're doing with it, but the probabilistic foundations are definitely shot.

If you're just running an SVM or doing ridge regression (formally equivalent to GP regression), then the Hilbert space foundations are also definitely shot, but it's possible to define what you're doing in terms of a Krein space. There was a bit of work in the mid-to-late-aughts on this, but I think it was mostly abandoned because the theoretical motivation wasn't super satisfying and neither were the empirical results; I can dig out some of these papers if you want.

Another option is to "patch" your kernel to the closest (in some sense) PSD kernel on the particular points you consider. The following paper studied that; I have also used these techniques, but wouldn't generally recommend them if you can avoid it, because it adds a lot of headaches.

Chen, Garcia, Gupta, Rahimi, and Cazzanti. Similarity-based Classification: Concepts and Algorithms. JMLR 2009 (pdf).

$\endgroup$
  • $\begingroup$ +1. Agreed; in short, negative variances are irrelevant mathematically and impossible realistically. $\endgroup$ – usεr11852 says Reinstate Monic Mar 19 '18 at 20:08
  • $\begingroup$ Great post Dougal. The techniques described in the paper are also useful. Could you shed some light on what you mean by the alpha values? Where did that come from? Also, I am looking to find the appropriate distance measures to use for my project, is there perhaps a place you can point me to, to explore the different distance functions? $\endgroup$ – user3542930 Mar 19 '18 at 20:26
  • $\begingroup$ @user3542930 That's just one way to demonstrate how it breaks; there being some such set of $\alpha$s is equivalent to there being a negative eigenvalue in the kernel matrix for those $n$ points, and it's the simplest way to show that an indefinite covariance matrix leads you to nonsense. $\endgroup$ – Dougal Mar 19 '18 at 20:44
  • $\begingroup$ cs.toronto.edu/~duvenaud/cookbook is a reasonable place to start for thinking about what kernel function to use. These days, if you have a reasonable amount of data, you should probably be specifying some general form for the kernel and then optimizing the particular value of the parameters; good software like GPflow / GPy makes this easy. $\endgroup$ – Dougal Mar 19 '18 at 20:45

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.