Selective Labeling via Error Bound Minimization

In many practical machine learning problems, the acquisition of labeled data is often expensive and/or time consuming. This motivates us to study a problem as follows: given a label budget, how to select data points to label such that the learning performance is optimized. We propose a selective labeling method by analyzing the generalization error of Laplacian regularized Least Squares (LapRLS). In particular, we derive a deterministic generalization error bound for LapRLS trained on subsampled data, and propose to select a subset of data points to label by minimizing this upper bound. Since the minimization is a combinational problem, we relax it into continuous domain and solve it by projected gradient descent. Experiments on benchmark datasets show that the proposed method outperforms the state-of-the-art methods.

Authors

• Quanquan Gu
• Tong Zhang Nanjing University of Science and Technology
• Jiawei Han University of Illinois Urbana-Champaign
• Chris Ding The School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China

Keywords

No keywords are indexed for this paper.