On the Supermodularity of Active Graph-based Semi-supervised Learning with Stieltjes Matrix Regularization
Active graph-based semi-supervised learning (AG-SSL) aims to select a small set of labeled examples and utilize their graph-based relation to other unlabeled examples to aid in machine learning tasks. It is also closely related to the sampling theory in graph signal processing. In this paper, we revisit the original formulation of graph-based SSL and prove the supermodularity of an AG-SSL objective function under a broad class of regularization functions parameterized by Stieltjes matrices. Under this setting, supermodularity yields a novel greedy label sampling algorithm with guaranteed performance relative to the optimal sampling set. Compared to three state-of-the-art graph signal sampling and recovery methods on two real-life community detection datasets, the proposed AG-SSL method attains superior classification accuracy given limited sample budgets.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionGeneral ClassificationSimilar Papers 제목 키워드 기반
Submodularity In Machine Learning and Artificial Intelligence
In this manuscript, we offer a gentle review of submodularity and supermodularity and their properties. We offer a plethora of submodular definitions; a full description of a number of example submodular functions and th…
Abstractive Text SummarizationBIG-bench Machine Learningfeature selectionConsistency-Based Semi-supervised Evidential Active Learning for Diagnostic Radiograph Classification
Deep learning approaches achieve state-of-the-art performance for classifying radiology images, but rely on large labelled datasets that require resource-intensive annotation by specialists. Both semi-supervised learning…
Active LearningDiagnosticimage-classificationImage Classification+2Model-Change Active Learning in Graph-Based Semi-Supervised Learning
Active learning in semi-supervised classification involves introducing additional labels for unlabelled data to improve the accuracy of the underlying classifier. A challenge is to identify which points to label to best …
Active LearningCamouflaged Chinese Spam Content Detection with Semi-supervised Generative Active Learning
We propose a Semi-supervIsed GeNerative Active Learning (SIGNAL) model to address the imbalance, efficiency, and text camouflage problems of Chinese text spam detection task. A {``}self-diversity{''} criterion is propose…
Active LearningChinese Spam DetectionData AugmentationDiversity+1Approximate Supermodularity Bounds for Experimental Design
This work provides performance guarantees for the greedy solution of experimental design problems. In particular, it focuses on A- and E-optimal designs, for which typical guarantees do not apply since the mean-square er…
Experimental Design