Replica theory for learning curves for Gaussian processes on random graphs

DOI10.1088/1751-8113/45/42/425005zbMATH Open1253.82007arXiv1202.5918OpenAlexW2040573160MaRDI QIDQ4649407

Publication date: 22 November 2012

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Abstract: Statistical physics approaches can be used to derive accurate predictions for the performance of inference methods learning from potentially noisy data, as quantified by the learning curve defined as the average error versus number of training examples. We analyse a challenging problem in the area of non-parametric inference where an effectively infinite number of parameters has to be learned, specifically Gaussian process regression. When the inputs are vertices on a random graph and the outputs noisy function values, we show that replica techniques can be used to obtain exact performance predictions in the limit of large graphs. The covariance of the Gaussian process prior is defined by a random walk kernel, the discrete analogue of squared exponential kernels on continuous spaces. Conventionally this kernel is normalised only globally, so that the prior variance can differ between vertices; as a more principled alternative we consider local normalisation, where the prior variance is uniform.

Full work available at URL: https://arxiv.org/abs/1202.5918

zbMATH Keywords

Gaussian process random graphs random walk replica techniques

Mathematics Subject Classification ID

Gaussian processes (60G15) Bayesian inference (62F15) Random graphs (graph-theoretic aspects) (05C80) Classical equilibrium statistical mechanics (general) (82B05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)