CaltechAUTHORS
  A Caltech Library Service

Consistency of Semi-Supervised Learning Algorithms on Graphs: Probit and One-Hot Methods

Hoffmann, Franca and Hosseini, Bamdad and Ren, Zhi and Stuart, Andrew M. (2020) Consistency of Semi-Supervised Learning Algorithms on Graphs: Probit and One-Hot Methods. Journal of Machine Learning Research, 21 . pp. 1-55. ISSN 1533-7928. https://resolver.caltech.edu/CaltechAUTHORS:20190722-075729960

[img] PDF - Published Version
Creative Commons Attribution.

1223Kb
[img] PDF (9 March 2020) - Submitted Version
See Usage Policy.

1461Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190722-075729960

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://www.jmlr.org/papers/v21/15-900.htmlPublisherArticle
https://arxiv.org/abs/1906.07658arXivDiscussion Paper
ORCID:
AuthorORCID
Hoffmann, Franca0000-0002-1182-5521
Ren, Zhi0000-0001-9812-0251
Additional Information:© 2020 Franca Hoffmann, Bamdad Hosseini, Zhi Ren and Andrew M. Stuart. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/19-500.html. Submitted 6/19; Revised 3/20; Published 7/20. The authors are grateful to Nicolás García-Trillos, Mark Girolami and Omiros Papaspiliopoulos for helpful discussions about the probit methodology and spectral clustering. FH is partially supported by Caltech's von Kármán postdoctoral instructorship. BH is supported in part by an NSERC PDF fellowship. AMS is grateful to AFOSR (grant FA9550-17-1-0185) and NSF (grant DMS 18189770) for financial support.
Funders:
Funding AgencyGrant Number
CaltechUNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-17-1-0185
NSFDMS-18189770
Subject Keywords:Semi-supervised learning, classification, consistency, graph Laplacian, probit, spectral analysis
Classification Code:AMS subject classifications: 62H30, 68T10, 68Q87, 91C20
Record Number:CaltechAUTHORS:20190722-075729960
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190722-075729960
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97303
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:22 Jul 2019 16:33
Last Modified:05 Nov 2020 19:18

Repository Staff Only: item control page