Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods

MaRDI QIDQ6320698arXivFDO

Authors Franca Hoffmann, Bamdad Hosseini, Zhi Ren, A. M. Stuart

Publication date 18 June 2019

Published in arXiv

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

arXiv classification

cs.LGcs.NAmath.NAmath.OCstat.ML

Abstract: Graph-based semi-supervised learning is the problem of propagating labels from a small number of labelled data points to a larger set of unlabelled data. This paper is concerned with the consistency of optimization-based techniques for such problems, in the limit where the labels have small noise and the underlying unlabelled data is well clustered. We study graph-based probit for binary classification, and a natural generalization of this method to multi-class classification using one-hot encoding. The resulting objective function to be optimized comprises the sum of a quadratic form defined through a rational function of the graph Laplacian, involving only the unlabelled data, and a fidelity term involving only the labelled data. The consistency analysis sheds light on the choice of the rational function defining the optimization.

This page was built for publication: Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320698)