Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning

DOI10.1137/22M1531981arXiv2210.15786OpenAlexW4389486627MaRDI QIDQ6151664FDOQ6151664

Authors: Kevin C. Miller, Jeff Calder 

Publication date: 12 February 2024

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: We show that uncertainty sampling is sufficient to achieve exploration versus exploitation in graph-based active learning, as long as the measure of uncertainty properly aligns with the underlying model and the model properly reflects uncertainty in unexplored regions. In particular, we use a recently developed algorithm, Poisson ReWeighted Laplace Learning (PWLL) for the classifier and we introduce an acquisition function designed to measure uncertainty in this graph-based classifier that identifies unexplored regions of the data. We introduce a diagonal perturbation in PWLL which produces exponential localization of solutions, and controls the exploration versus exploitation tradeoff in active learning. We use the well-posed continuum limit of PWLL to rigorously analyze our method, and present experimental results on a number of graph-based image classification problems.

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

Recommendations

• Graph-Based Active Learning Based on Label Propagation
• Active exploration for large graphs
• Evidence-based uncertainty sampling for active learning
• A Scalable Algorithm for Graph-Based Active Learning
• Toward optimal probabilistic active learning using a Bayesian approach

zbMATH Keywords

partial differential equationscontinuum limitactive learninggraph Laplacianuncertainty sampling

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Extremal problems in graph theory (05C35) PDEs in connection with statistics (35Q62)

Cites Work

• Diffusion maps
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• Learning Theory
• Semi-supervised learning on Riemannian manifolds
• Agnostic active learning
• Support vector machine active learning with applications to text classification
• Margin Based Active Learning
• Graph Laplacians and their convergence on random neighborhood graphs
• Theory of Disagreement-Based Active Learning
• Active learning
• Learning Theory
• Two faces of active learning
• Analysis of \(p\)-Laplacian regularization in semisupervised learning
• Weighted nonlocal Laplacian on interpolation from sparse data
• Large data and zero noise limits of graph-based semi-supervised learning algorithms
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Minimax analysis of active learning
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
• Properly-weighted graph Laplacian for semi-supervised learning
• The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
• Diffuse interface models on graphs for classification of high dimensional data
• An Introduction to Variational Autoencoders
• Cautious active clustering
• Graph-based optimization approaches for machine learning, uncertainty quantification and networks
• Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
• Rates of convergence for Laplacian semi-supervised learning with low labeling rates

This page was built for publication: Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning

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