Timezone: »
Spotlight
Kernels and learning curves for Gaussian process regression on random graphs
Peter Sollich · Matthew J Urry · Camille Coti
We investigate how well Gaussian process regression can learn functions defined on graphs, using large regular random graphs as a paradigmatic example. Randomwalk based kernels are shown to have some surprising properties: within the standard approximation of a locally treelike graph structure, the kernel does not become constant, i.e.neighbouring function values do not become fully correlated, when the lengthscale $\sigma$ of the kernel is made large. Instead the kernel attains a nontrivial limiting form, which we calculate. The fully correlated limit is reached only once loops become relevant, and we estimate where the crossover to this regime occurs. Our main subject are learning curves of Bayes error versus training set size. We show that these are qualitatively well predicted by a simple approximation using only the spectrum of a large tree as input, and generically scale with $n/V$, the number of training examples per vertex. We also explore how this behaviour changes once kernel lengthscales are large enough for loops to become important.
Author Information
Peter Sollich (King's College London)
Matthew J Urry (King's College London)
Camille Coti (INRIA SaclayÎle de France)
Related Events (a corresponding poster, oral, or spotlight)

2009 Poster: Kernels and learning curves for Gaussian process regression on random graphs »
Wed Dec 9th 03:00  07:59 AM Room None
More from the Same Authors

2015 Workshop: Modelling and inference for dynamics on complex interaction networks: joining up machine learning and statistical physics »
Manfred Opper · Yasser Roudi · Peter Sollich 
2012 Poster: Learning curves for multitask Gaussian process regression »
Peter Sollich · Simon R Ashton 
2010 Spotlight: Exact learning curves for Gaussian process regression on large random graphs »
Matthew J Urry · Peter Sollich 
2010 Poster: Exact learning curves for Gaussian process regression on large random graphs »
Matthew J Urry · Peter Sollich