Input ⟶ prediction + uncertainty.
Gaussian processes (GPs) — gold standard.
— random functions with jointly Gaussian marginals.
Bayesian learning: prior GP + data = posterior GP
Prior GPs are determined by kernels (covariance functions)
— have to be positive semi-definite,
— not all kernels define "good" GPs.
$$
\htmlData{class=fragment fade-out,fragment-index=6}{
\footnotesize
\mathclap{
k_{\nu, \kappa, \sigma^2}(x,x') = \sigma^2 \frac{2^{1-\nu}}{\Gamma(\nu)} \del{\sqrt{2\nu} \frac{\norm{x-x'}}{\kappa}}^\nu K_\nu \del{\sqrt{2\nu} \frac{\norm{x-x'}}{\kappa}}
}
}
\htmlData{class=fragment d-print-none,fragment-index=6}{
\footnotesize
\mathclap{
k_{\kappa, \sigma^2}(x,x') = \sigma^2 \exp\del{-\frac{\norm{x-x'}^2}{2\kappa^2}}
}
}
$$
$\sigma^2$: variance
$\kappa$: length scale
$\nu$: smoothness
$\nu\to\infty$: RBF kernel (Gaussian, Heat, Diffusion)
$\nu = 1/2$
$\nu = 3/2$
$\nu = 5/2$
$\nu = \infty$
Inputs do not lie in $\R^n$:
Can we build Matérn GPs for this application?
Need a GP on some set of graphs.
Distance-based approach:
$ k_{\kappa, \sigma^2}(x,x') \!=\! \sigma^2 \exp \del{\!-\frac{\|x - x'\|^2}{2\kappa^2}} $
$ k_{\kappa, \sigma^2}^{(d)}(x,x') \!=\! \sigma^2 \exp \del{\!-\frac{d(x,x')^2}{2\kappa^2}} $
where $d$ is, e.g., the Hamming distance.
Claim. It is not positive semi-definite.
(this is a very general phenomenon)
Another characterization of $k_{\kappa, \sigma^2}$:
$k_{\kappa, \sigma^2} \propto \sigma^2 \exp(-\frac{\kappa^2}{2} \Delta)$
where $\Delta$ is the Laplacian on $\R^n$.
Define a different notion of geometry.
Claim. It is always positive definite.
(this is a very general phenomenon)
Naïvely, requires working with $$ \htmlData{class=fragment}{ \Delta \in \R^{2^d \x 2^d}, \htmlData{class=fragment}{ \quad d = n(n-1) / 2, \quad n = \text{ number of nodes.} } } $$
In a smart way: $$ \htmlData{class=fragment}{ \begin{aligned} k_{\kappa, \sigma^2}(x, x') = \sigma^2 \tanh(\kappa^2/2)^{d(x, x')} & \htmlData{class=fragment}{ = \sigma^2 \exp\del{-\frac{d(x, x')}{2 \tilde{\kappa}^2}} } \\ & \htmlData{class=fragment}{ \neq \sigma^2 \exp\del{-\frac{d(x, x')^2}{2 \tilde{\kappa}^2}} } \end{aligned} } $$
In a smart way: $$ k_{\nu, \kappa, \sigma^2}(x, x') \propto \sigma^2 \sum_{j=0}^d \del{\frac{2 \nu}{\kappa^2} + 2 j}^{-\nu} G_{j}(d(x, x')), $$ where $G_{j}$ are known orthogonal polynomials (Kravchuk polynomials).
Hardness result: kernels are intractable. However, they can be approximated.
Borovitskiy et al. (AISTATS 2020)
Azangulov et al. (JMLR 2024)
Azangulov et al. (JMLR 2024)
Robert-Nicoud et al. (AISTATS 2024)
Yang et al. (AISTATS 2024)
Bolin et al. (Bernoulli 2024)
Alain et al. (ICML 2024)
Borovitskiy et al. (AISTATS 2023)
Fichera et al. (NeurIPS 2023)
Peach et al. (ICLR 2024)
Li et al. (JMLR 2024)
Rosa et al. (NeurIPS 2023)
Matérn Gaussian processes on meshes (independently proposed)
Example code:
>>> # Define a space (2-dim sphere).
>>> hypersphere = Hypersphere(dim=2)
>>> # Initialize kernel.
>>> kernel = MaternGeometricKernel(hypersphere)
>>> params = kernel.init_params()
>>> # Compute and print out the 3x3 kernel matrix.
>>> xs = np.array([[0., 0., 1.], [0., 1., 0.], [1., 0., 0.]])
>>> print(kernel.K(params, xs))
[[1. 0.356 0.356]
[0.356 1. 0.356]
[0.356 0.356 1. ]]
V. Borovitskiy, I. Azangulov, A. Terenin, P. Mostowsky, M. P. Deisenroth, and N. Durrande. Matérn Gaussian Processes on Graphs. Artificial Intelligence and Statistics, 2021.
A. Feragen, F. Lauze, and S. Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. Computer Vision and Pattern Recognition, 2015.
I. J. Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 1938.
P. Whittle. Stochastic-processes in several dimensions. Bulletin of the International Statistical Institute, 1963.
F. Lindgren, H. Rue, and J. Lindström. An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. Journal of the Royal Statistical Society, Series B: Statistical Methodology, 2011.
V. Borovitskiy, A. Terenin, P. Mostowsky, and M. P. Deisenroth. Matérn Gaussian Processes on Riemannian Manifolds. Advances in Neural Information Processing Systems, 2020.
I. Azangulov, A. Smolensky, A. Terenin, and V. Borovitskiy. Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces I: the compact case. Journal of Machine Learning Research, 2024.
I. Azangulov, A. Smolensky, A. Terenin, and V. Borovitskiy. Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces II: non-compact symmetric spaces, 2024.
D. Robert-Nicoud, A. Krause, and V. Borovitskiy. Intrinsic Gaussian Vector Fields on Manifolds. Artificial Intelligence and Statistics, 2024.
M. Yang, V. Borovitskiy, and E. Isufi. Hodge-Compositional Edge Gaussian Processes. Artificial Intelligence and Statistics, 2024.
D. Bolin, A. B. Simas, and J. Wallin. Gaussian Whittle-Matérn fields on metric graphs. Bernoulli, 2024.
M. Alain, S. Takao, B. Paige, and M. P. Deisenroth. Gaussian Processes on Cellular Complexes. International Conference on Machine Learning, 2024.
V. Borovitskiy, M. R. Karimi, V. R. Somnath, and A. Krause. Isotropic Gaussian Processes on Finite Spaces of Graphs. Artificial Intelligence and Statistics, 2023.
B. Fichera, V. Borovitskiy, A. Krause, and A. Billard. Implicit Manifold Gaussian Process Regression. Advances in Neural Information Processing Systems, 2023.
R. Peach, M. Vinao-Carl, N. Grossman, and M. David. Implicit Gaussian process representation of vector fields over arbitrary latent manifolds. International Conference on Learning Representations, 2024.
D. Li, W. Tang, and S. Banerjee. Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds. Journal of Machine Learning Research, 2023.
P. Rosa, V. Borovitskiy, A. Terenin, and J. Rousseau. Posterior Contraction Rates for Matérn Gaussian Processes on Riemannian Manifolds. Advances in Neural Information Processing Systems, 2023.
N. Jaquier, V. Borovitskiy, A. Smolensky, A. Terenin, T. Asfour, and L. Rozo. Geometry-aware Bayesian Optimization in Robotics using Riemannian Matérn Kernels. Conference on Robot Learning, 2021.
N. Jaquier, L. Rozo, S. Calinon, and M. Bürger. Bayesian optimization meets Riemannian manifolds in robot learning. Conference on Robot Learning, 2020.
S. Coveney, C. Corrado, C. H. Roney, R. D. Wilkinson, J. E. Oakley, F. Lindgren, S. E. Williams, M. D. O'Neill, S. A. Niederer, and R. H. Clayton. Probabilistic interpolation of uncertain local activation times on human atrial manifolds. IEEE Transactions on Biomedical Engineering, 2019.
S. Coveney, C. Corrado, C. H. Roney, D. OHare, S. E. Williams, M. D. O'Neill, S. A. Niederer, R. H. Clayton, J. E. Oakley, and R. D. Wilkinson. Gaussian process manifold interpolation for probabilistic atrial activation maps and uncertain conduction velocity. Philosophical Transactions of the Royal Society A, 2020.