Diversifying Convex Transductive Experimental Design for Active Learning

Lei Shi, Yi-Dong ShenIJCAI 2016

Abstract

Active learning aims to select the most informative samples for manual labeling to maximize model performance under a limited budget. A popular approach, Convex Transductive Experimental Design (CTED), selects samples that best represent the overall data distribution through reconstruction. However, CTED often selects redundant, highly similar samples, wasting labeling resources. This paper introduces Diversified CTED (DCTED), which incorporates an adaptive diversity regularizer to ensure that selected samples are both informative and unique. Experimental results across five benchmark datasets demonstrate that DCTED significantly outperforms standard CTED and other state-of-the-art methods, particularly on very small labeling budgets.

Introduction

In many machine learning applications, unlabeled data is abundant, but manual labeling is expensive and time-consuming. Active learning addresses this by identifying the most valuable data points for an expert to label. A key challenge is balancing the "informativeness" of individual samples with the "diversity" of the selected set. Traditional reconstruction-based methods like CTED focus on informativeness—selecting samples that can best reconstruct the rest of the dataset. Unfortunately, because similar data points often have similar reconstruction capabilities, CTED tends to select clusters of redundant samples.

Methodology: Diversified CTED (DCTED)

The authors propose a novel framework that explicitly penalizes redundancy during the sample selection process.

1. The Diversity Regularizer

DCTED modifies the standard CTED objective function by adding a diversity regularization term: $\alpha \mathbf{b}^T \mathbf{S} \mathbf{b}$. Here, $\mathbf{b}$ is the selection vector (where higher values indicate a higher priority for labeling), and $\mathbf{S}$ is a similarity matrix. The parameter $\alpha$ controls the trade-off between the reconstruction objective and the diversity constraint.

2. Adaptive Similarity Learning

A core innovation of DCTED is how it defines similarity. Rather than using a fixed similarity matrix based on raw input features, DCTED learns the similarity matrix $\mathbf{S}$ dynamically. It uses the "reconstruction coefficients"—the weights used to represent other data points—as the basis for similarity. This ensures that two samples are considered similar if they play a similar functional role in representing the dataset, rather than just having similar raw features.

3. Optimization

The resulting optimization problem is non-convex. To solve it, the authors derive an alternating minimization algorithm that iteratively updates the reconstruction matrix, the selection vector, and the similarity weights until convergence.

Experimental Results

The researchers evaluated DCTED on five diverse benchmark datasets: USPS and MNIST (digits), NewsGroup and WebKB (text), and ORL (faces).

Performance and Efficiency

DCTED consistently outperformed CTED and other baselines. A notable result was observed on the USPS dataset, where DCTED achieved 78.5% accuracy with only 10 labeled samples. In contrast, the original CTED required 40 samples to reach a lower accuracy of 76%, demonstrating a four-fold improvement in labeling efficiency.

Parameter Sensitivity and Robustness

The parameter $\alpha$ is crucial for balancing informativeness and diversity. The authors found a "sweet spot" for $\alpha$ where performance is maximized. If $\alpha$ is too low, the model reverts to standard CTED behavior; if too high, it may select uninformative outliers simply because they are diverse.

Figure 1: Accuracy (ACC) vs. diversity parameter $\alpha$ for the ORL and USPS datasets. DCTED consistently maintains higher accuracy than the CTED baseline across various $\alpha$ values.
Figure 2: Accuracy (ACC) vs. diversity parameter $\alpha$ for the MNIST and WEBKB datasets. The results highlight the robustness of DCTED and the existence of an optimal diversity trade-off.

Conclusion

Diversified Convex Transductive Experimental Design (DCTED) effectively addresses the redundancy problem in active learning. By incorporating an adaptive diversity regularizer based on functional similarity, DCTED ensures that every labeled sample provides unique information to the model. This approach significantly reduces the human effort required to train high-performing classifiers, making it a practical tool for real-world machine learning tasks.

Summary updated

BibTeX
@inproceedings{shi2016diversifying,
  author = {Lei Shi and Yi-Dong Shen},
  title = {{Diversifying Convex Transductive Experimental Design for Active Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure