Exploring Representativeness and Informativeness for Active Learning

Bo Du; Zengmao Wang; Lefei Zhang; Liangpei Zhang; Wei Liu; Jialie Shen; Dacheng Tao

Source-linked AI summary

Exploring Representativeness and Informativeness for Active Learning

Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, Dacheng Tao

arXiv:1904.06685v1Apr 14, 2019cs.LGstat.ML

TL;DR

Active learning needs to select informative samples without labeling large datasets, while existing methods combining informativeness and representativeness can depend on data assumptions. The paper proposes a general two-sample-discrepancy framework using triple similarities and an uncertainty measure, with an RBF-based practical algorithm and modified Best-versus-Second-Best strategy. Experiments on 15 benchmark datasets report performance superior to state-of-the-art active-learning algorithms.

Problem
Existing methods that combine informativeness and representativeness may be susceptible to assumptions and constraints on input data, motivating a more general active-learning approach.
Method
The framework combines informativeness and representativeness through triple similarities derived from two-sample discrepancy, an uncertainty measure, and flexible similarity or uncertainty choices.
Results
The proposed algorithm outperforms state-of-the-art active-learning algorithms on 15 benchmark datasets.
Takeaways & Limitations
The framework provides a systematic way to combine the two criteria, while sensitivity analysis indicates that their relative importance depends on dataset distribution.

Abstract

from arXiv · show

How can we find a general way to choose the most suitable samples for training a classifier? Even with very limited prior information? Active learning, which can be regarded as an iterative optimization procedure, plays a key role to construct a refined training set to improve the classification performance in a variety of applications, such as text analysis, image recognition, social network modeling, etc. Although combining representativeness and informativeness of samples has been proven promising for active sampling, state-of-the-art methods perform well under certain data structures. Then can we find a way to fuse the two active sampling criteria without any assumption on data? This paper proposes a general active learning framework that effectively fuses the two criteria. Inspired by a two-sample discrepancy problem, triple measures are elaborately designed to guarantee that the query samples not only possess the representativeness of the unlabeled data but also reveal the diversity of the labeled data. Any appropriate similarity measure can be employed to construct the triple measures. Meanwhile, an uncertain measure is leveraged to generate the informativeness criterion, which can be carried out in different ways. Rooted in this framework, a practical active learning algorithm is proposed, which exploits a radial basis function together with the estimated probabilities to construct the triple measures and a modified Best-versus-Second-Best strategy to construct the uncertain measure, respectively. Experimental results on benchmark datasets demonstrate that our algorithm consistently achieves superior performance over the state-of-the-art active learning algorithms.

I. INTRODUCTION

Active learning selects unlabeled samples for labeling to improve classification while reducing annotation effort. The paper proposes a general framework that combines informativeness and representativeness without relying on specific data assumptions.

Random selection can introduce redundancy and bias, while methods relying mainly on scarce labeled data may underuse abundant unlabeled information.
Active learning iteratively selects samples for labeling, using informativeness to reduce model uncertainty and representativeness to exploit unlabeled-data structure.
Clustering-based representativeness methods depend on how well their inferred clusters represent the entire dataset.
Existing methods that fuse informativeness and representativeness may depend on assumptions or constraints about the input data.
The proposed framework combines both criteria through a two-sample discrepancy formulation and measures representativeness using three types of similarity.
A practical algorithm uses posterior-probability-based RBF similarities and a modified Best-versus-Second-Best strategy, with experiments on 15 benchmark datasets outperforming state-of-the-art methods.

II. THE PROPOSED FRAMEWORK

The active-learning setup begins with labeled and unlabeled partitions and seeks an unlabeled sample whose addition produces the greatest generalization capability.

A dataset is divided into labeled set L_t and unlabeled set U_t, with n = n_t + u_t at iteration t.
The classifier f_t is trained on L_t, and active learning selects x_s from U_t for labeling.
The selected sample is added to the training set to learn a new classification model with maximum generalization capability.

A. The two-sample discrepancy problem

The two-sample discrepancy problem compares distributions estimated from two samples. The paper adapts this comparison to measure whether an unlabeled sample represents the data distribution relevant to active learning.

The problem tests whether two independently sampled distributions are the same using observations from sets X and Z.
The two-sample statistic compares density estimates from two samples and is adapted to active learning for labeled and unlabeled datasets.
Kernel-based density estimation uses bandwidth parameters and a symmetric multivariate density function to estimate the distributions.
The discrepancy between two distributions can be measured with a minimum distance involving n^-1/2σ^-p/2, where n = n_1 + n_2.
If an unlabeled sample measures the unlabeled distribution and can be moved to the labeled set without changing that distribution, the two sets can become similarly distributed.
The empirical discrepancy converges in probability at rate O((m_jσ^p + n_jσ^p)^(-1/2)), and the resulting theorem is used to measure unlabeled-sample representativeness.

B. The General Active Learning Framework

The framework combines representativeness and informativeness by selecting samples that reflect the unlabeled distribution, diversify the labeled set, and provide useful classifier information.

B. The General Active Learning Framework: The representative component uses three measures to assess similarity within the unlabeled set, between a candidate and labeled data, and between candidate queries.M1 captures unlabeled-set similarity, while M2 and M3 measure distributional relationships involving labeled and unlabeled data.
B. The General Active Learning Framework: M2 favors candidates unlike labeled samples, reducing redundancy and increasing the diversity of selected samples.A smaller M2 value indicates greater difference from labeled samples and lower redundancy.
B. The General Active Learning Framework: M3 encourages a queried sample to retain similarity to the remaining unlabeled samples, supporting representativeness of the unlabeled distribution.Its weighting reflects the relative size of the unlabeled set in the full dataset.
B. The General Active Learning Framework: The informative component assigns each unlabeled sample an uncertainty value based on the current classifier.The uncertainty function can be chosen according to the active learning algorithm.
B. The General Active Learning Framework: The resulting formulation is relaxed from an NP-hard integer program to a convex quadratic program, then rounded by setting the largest α_i to 1.The relaxed problem can be solved efficiently with a QP solver before recovering a single selected sample.

C. The Proposed Active Learning Method

The proposed method instantiates the general framework using estimated class-membership probabilities to construct its active learning measures.

C. The Proposed Active Learning Method: The proposed active learning method relies on probability estimates of class membership for all samples.These estimates provide the basis for the method's practical construction of the framework measures.

1) Computing Representative Part:

The representative component uses a positive-semidefinite RBF kernel over posterior probabilities rather than fixed feature-space distances, adapting similarity to the classifier.

1) Computing Representative Part:: The framework requires a positive-semidefinite similarity matrix to preserve convexity, so the method adopts an RBF kernel.The kernel supplies the similarity structure used in the representative optimization.
1) Computing Representative Part:: Instead of computing RBF similarity directly from feature-space Euclidean distances, the method applies it to posterior probabilities.This choice accommodates changing distributions between labeled and unlabeled sets during active learning.
1) Computing Representative Part:: For each unlabeled sample, the classifier produces a class-probability vector P_i containing one posterior probability per class.The vector length equals the number of classes.
1) Computing Representative Part:: The probability-based similarities populate M1 for pairs of unlabeled samples and support the corresponding M2 and M3 representative measures.M2 and M3 extend the same probability-kernel construction to relationships involving labeled and unlabeled distributions.

2) Computing Uncertainty Part:

The uncertainty component modifies BvSB by combining class-confusion information with proximity to support vectors, then integrates this score into the iterative algorithm.

2) Computing Uncertainty Part:: The method measures informativeness through uncertainty, treating samples whose class membership is difficult for the current classifier to decide as highly uncertain.Its uncertainty strategy modifies the posterior-probability-based BvSB measure.
2) Computing Uncertainty Part:: BvSB compares the two highest estimated class probabilities, with smaller values indicating higher uncertainty.The measure directly estimates classification confusion about class membership.
2) Computing Uncertainty Part:: The modified strategy adds a position measure so selected samples are near both the separating hyperplane and support vectors.This supplements BvSB's tendency to select samples close to the hyperplane.
2) Computing Uncertainty Part:: Figure 1 contrasts samples queried by BvSB with those queried by the proposed uncertain method on a two-class illustration.Triangles and rectangles denote the two classes, while green points denote the unlabeled set.
2) Computing Uncertainty Part:: The algorithm estimates probabilities, constructs M1–M3, computes modified uncertainty, solves the objective by QP, and updates labeled and unlabeled sets iteratively.The procedure continues until the terminating condition is satisfied.
2) Computing Uncertainty Part:: The framework can be generalized to different active learning algorithms by varying its similarity and uncertainty components.This generality follows from the framework's separate representative and uncertainty constructions.

III. EXPERIMENTS

Experiments compare the proposed method with random selection and state-of-the-art active learning methods across benchmark datasets. The proposed method achieves the best overall performance, while competing methods show dataset- or stage-dependent weaknesses.

Experimental setup: Experiments compare random selection and state-of-the-art active learning methods on benchmark datasets using prediction accuracy during the query process.Datasets are randomly split into 60% training and 40% testing data; results average 10 runs per method.
Results: The proposed method yields the best performance among all compared methods.Figure 2 reports learning accuracy over queries, with each curve representing the average of 10 runs.
Results: BMDR performs well early in learning and remains competitive as queries increase, but does not match the proposed method overall.BMDR is described as outperforming other competitors and performing well at the beginning of the learning stage.
Results: Other active learning methods are not consistently superior to RANDOM, whereas the proposed method remains stronger than single-criterion methods throughout the active learning process.The comparison includes methods designed to query informative and representative samples, including BMDR and QUIRE.
Method boundaries: QUIRE requires unlabeled data to satisfy a semi-supervised assumption, limiting its applicability.The paper contrasts this requirement with the proposed approach’s direct measurement of representativeness.

IV. DISCUSSION AND ANALYSIS

The analysis examines how the trade-off between informativeness and representativeness depends on dataset distribution. Different datasets favor different criterion weights, supporting adaptive combination within the proposed framework.

Parameter analysis: The trade-off parameter β controls the balance between informative and representative components in the optimization objective.The experiments evaluate β values from 1, 2, 10, 100, and 1000 on three UCI datasets.
Parameter analysis: Sensitivity to β differs across breast cancer, balance, and semeion handwritten digit datasets.Breast cancer is more sensitive to β than semeion handwritten digit and balance.
Parameter analysis: Smaller β works better on breast cancer, whereas larger β works better on semeion handwritten digit and balance.The paper interprets this pattern as greater usefulness of representativeness for breast cancer and informativeness for the other two datasets.
Discussion: Dataset distribution affects which information is important during active learning, so the framework can support task-specific algorithm design.The framework provides a way to obtain criterion importance during the iterative learning process.

V. CONCLUSION

The paper concludes that its framework systematically combines informativeness and representativeness for active sample selection. A practical implementation using modified BvSB and probability-based RBF measures outperforms state-of-the-art methods on 15 benchmark datasets.

Conclusion: The proposed framework provides a systematic and direct way to measure and combine informativeness and representativeness.It is designed to query samples possessing both criteria.
Conclusion: The practical algorithm uses a modified Best-versus-Second-Best strategy for informativeness and an RBF with estimated probabilities for representativeness.These components instantiate the general framework in an efficient active learning algorithm.
Conclusion: The algorithm outperforms state-of-the-art active learning algorithms on 15 benchmark datasets.The conclusion describes the experimental evidence as extensive.
Future work: Future work will develop additional measures suited to specific data structures or distributions.The stated goal is to produce more practical and specialized active learning algorithms.

Appendix A

Appendix A presents proof steps for Theorem 1 by verifying two conditions and invoking asymptotic results. The supplied passages contain proof transitions but not the complete mathematical statements.

Proof: The proof of Theorem 1 requires checking two conditions.The appendix introduces the proof through a result attributed to reference.
Proof: The proof invokes asymptotic normality, stating that a quantity has distribution N(0, 1).Additional transitions apply Theorem 1 and derive the first condition.
Proof: The final proof steps combine the two verified conditions with results from reference.The cited situations include j1 ≤ k1 and j2 ≤ k2.
Proof: The appendix states that one intermediate result proves the second condition.The displayed mathematical content is not fully preserved in the supplied passage.

Appendix B

The appendix analyzes the two-sample discrepancy statistic under equal bandwidths and local alternatives, deriving its discrimination limit and asymptotic behavior under regularity conditions.

Under the null hypothesis f1 = f2, the two-sample discrepancy problem evaluates Hσ1σ2, with the proof simplifying to Hσ when σ1 = σ2 = σ.The objective is to minimize Hσ1σ2, using estimators of f1 and f2 defined in Theorem 2.
The minimum discriminable distance is ε = n−1/2σ−p/2, provided the estimator-consistency condition is satisfied.
For local alternatives ε = n−1/2σ−p/2a with a ≠ 0, the limiting quantity satisfies α < ¯h(a) < 1 and approaches 1 as |a| grows.
The asymptotic results assume comparable sample sizes, σ → 0, and nσp →∞; under these conditions, the relevant statistics are asymptotically normal with finite nonzero variances.One variance is stated to increase with a, while another does not depend on a.