Published on Wed May 23 2018

Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms

Matthew M. Dunlop, Dejan Slepčev, Andrew M. Stuart, Matthew Thorpe

Scalings in which the graph Laplacian approaches a differential operator are used to develop understanding of a number of semi-supervised learning algorithms. Both optimization and Bayesian approaches are considered.

0
0
0
Abstract

Scalings in which the graph Laplacian approaches a differential operator in the large graph limit are used to develop understanding of a number of algorithms for semi-supervised learning; in particular the extension, to this graph setting, of the probit algorithm, level set and kriging methods, are studied. Both optimization and Bayesian approaches are considered, based around a regularizing quadratic form found from an affine transformation of the Laplacian, raised to a, possibly fractional, exponent. Conditions on the parameters defining this quadratic form are identified under which well-defined limiting continuum analogues of the optimization and Bayesian semi-supervised learning problems may be found, thereby shedding light on the design of algorithms in the large graph setting. The large graph limits of the optimization formulations are tackled through convergence, using the recently introduced metric. The small labelling noise limits of the Bayesian formulations are also identified, and contrasted with pre-existing harmonic function approaches to the problem.

Fri Oct 20 2017
Machine Learning
On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
When consistency holds, carefully designed graph-based Markov chain Monte Carlo algorithms are proved to have a uniform spectral gap. Several numerical experiments corroborate both the statistical consistency and the algorithmic scalability established by the theory.
0
0
0
Sat Jul 25 2020
Machine Learning
Posterior Consistency of Semi-Supervised Regression on Graphs
Graph-based semi-supervised regression (SSR) is the problem of estimating the value of a function on a weighted graph. We present a Bayesian formulation of SSR in which the weighted graph defines aGaussian prior, using a graph Laplacian.
0
0
0
Fri Oct 09 2015
Machine Learning
New Optimisation Methods for Machine Learning
This is a thesis submitted for the degree of Doctor of Philosophy of The Australian National University. In this work we introduce several new optimisation methods for problems in machine learning. Our algorithms broadly fall into two categories: optimisation of finite sums and of graph structured objectives.
0
0
0
Sun Mar 26 2017
Machine Learning
Uncertainty quantification in graph-based classification of high dimensional data
In this paper we introduce, develop algorithms for a variety of Bayesian models for the task of binary classification. The methods are all based around the graph formulation of semi-supervised learning. We show that the probit and level set approaches are natural relaxations of the harmonic function approach introduced
0
0
0
Tue Jan 15 2019
Machine Learning
Algorithms for -based semi-supervised learning on graphs
The graph -Laplacian for has been proposed as a replacement for the standard () $p-Laplace for semi-supervised learning problems with very few labels. We present efficient and scalable algorithms for both the variational and game-theoretic formulations.
0
0
0
Wed Aug 26 2020
Machine Learning
Unlabeled Data Help in Graph-Based Semi-Supervised Learning: A Bayesian Nonparametrics Perspective
In this paper we analyze the graph-based approach to semi-supervised learning. We adopt a Bayesian perspective and demonstrate that the posterior contracts around the truth. Our theory covers both regression and classification.
1
0
0