PaperlayerView exact revision on arXiv

Source-linked AI summary

Batch Active Learning Using Determinantal Point Processes

Erdem Bıyık, Kenneth Wang, Nima Anari, Dorsa Sadigh

arXiv:1906.07975v1cs.LGstat.ML

TL;DR

Batch active learning must select informative samples without wasting a batch on items that share information, while earlier methods used ad hoc ways to combine informativeness and diversity. This paper uses DPPs to build diverse batches and develops algorithms to approximate the DPP mode. The authors report competitive performance against state-of-the-art methods and describe a computational bottleneck when datasets are large.

  • Problem

    Batch active learning must avoid redundant selections because samples in a batch can share information, while prior methods combined informativeness and diversity ad hoc.

    Source: §1 · p. 2

  • Method

    The paper uses DPPs to balance informativeness and diversity in batch selection and develops algorithms for approximating the mode of a DPP.

    Source: §1 · p. 2

  • Results

    The authors report that their DPP-based approach is competitive with state-of-the-art methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The proposed framework is presented as general, with demonstrations on classification and preference-based reward learning.

    Source: §6 · pp. 8–9

    Sampling remains a computational bottleneck when N is large, despite acceleration from MCMC and rank-one updates.

    Source: §6 · p. 8

Abstract

from arXiv · show

Data collection and labeling is one of the main challenges in employing machine learning algorithms in a variety of real-world applications with limited data. While active learning methods attempt to tackle this issue by labeling only the data samples that give high information, they generally suffer from large computational costs and are impractical in settings where data can be collected in parallel. Batch active learning methods attempt to overcome this computational burden by querying batches of samples at a time. To avoid redundancy between samples, previous works rely on some ad hoc combination of sample quality and diversity. In this paper, we present a new principled batch active learning method using Determinantal Point Processes, a repulsive point process that enables generating diverse batches of samples. We develop tractable algorithms to approximate the mode of a DPP distribution, and provide theoretical guarantees on the degree of approximation. We further demonstrate that an iterative greedy method for DPP maximization, which has lower computational costs but worse theoretical guarantees, still gives competitive results for batch active learning. Our experiments show the value of our methods on several datasets against state-of-the-art baselines.

1 Introduction

Labeling data can be costly, and single-sample active learning makes parallel labeling impractical while batch selection risks redundancy. The paper uses DPPs to balance informativeness and diversity, develops mode-approximation algorithms, and reports competitive results.

1 Introduction

  • Human labeling can be time-consuming and costly in applications that require interaction with people or physical systems.The paper focuses on reducing labeling effort through active learning with a human kept in the learning loop.Source: §1 · p. 1
  • Single-sample active learning requires retraining at every iteration, making parallel labeling inapplicable and adding computational cost.A single selected sample may also have little impact on modern learning models.Source: §1 · p. 2
  • Batch selection is difficult because individually informative samples can share information, while exact batch generation requires exhaustive search.The paper formulates the classification task as labeling K samples in batches of size k to train a high-accuracy classifier.Source: §1 · p. 2
  • DPPs provide a principled way to balance informativeness and diversity in batches, replacing earlier ad hoc combinations of those quantities.The framework uses uncertainty and exploration DPPs to produce batches that are separately and jointly diverse and informative.Source: §1 · p. 2, Figure 1 · p. 2
  • The paper introduces a maximum coordinate rounding algorithm with the best possible approximation ratio without conditional expectations, and evaluates its methods on classification tasks.It also reports preference-based reward-learning results in the Appendix.Source: §1 · p. 2

2 Background

The background defines DPPs as distributions over subsets whose kernel captures item similarities and whose determinant favors repulsive, diverse selections. The paper uses fixed-size k-DPPs and score- and feature-weighted kernels for batch selection.

2 Background

  • A point process is a probability measure over finite subsets of a ground set, and an L-ensemble DPP specifies one through a positive semidefinite kernel matrix.The probability of selecting subset A is proportional to the determinant of its corresponding submatrix L_A.Source: §2 · pp. 2–3
  • The determinant-based distribution favors less similar selections, reflecting DPP repulsiveness and negative correlation.The paper uses k-DPPs to guarantee batch size k; sampled subsets are more diverse than uniform samples except in trivial cases.Source: §2 · p. 3
  • Exact k-DPP sampling has complexity O(N^ω + Nk^3), so the paper instead uses MCMC to approximate sampling.MCMC starts from a likelihood-maximizing set and then removes and inserts one sample per step.Source: §2 · p. 3
  • The batch-learning kernel weights similarity features by nonnegative item scores that represent how informative each sample is.Increasing γ for fixed α gives more importance to scores during sampling.Source: §2 · p. 3

3 Approximating the Mode of a DPP

The section compares greedy and convex-relaxation approaches to DPP mode approximation, then presents maximum coordinate rounding with an e^k approximation guarantee. The new method avoids conditional expectations, while mode computation remains costly for large datasets.

3 Approximating the Mode of a DPP

  • The greedy algorithm guarantees a k^O(k)-approximation, while convex relaxation achieves an e^k-approximation but has super-linear dependence on N.Mode finding is NP-hard, and approximation beyond a factor of 2^ck is hard under a cardinality constraint of size k, for some c > 0.Source: §3 · p. 4
  • The convex-relaxation approach replaces integer variables with nonnegative reals and maximizes the concave log generating polynomial under a sum-to-k constraint.A sampled set has expected determinant within an e^k factor of the mode, but the probability of obtaining such an approximation can be exponentially small, motivating conditional expectations.Source: §3 · p. 4
  • Computing g and its gradient scales super-linearly in N, limiting the method’s practicality when N is large.Both quantities are needed for solving the relaxation and running conditional expectations.Source: §3 · p. 4

3.1 Maximum Coordinate Rounding

  • Maximum coordinate rounding finds an e^k-approximation to the DPP mode without the method of conditional expectations.It selects the largest relaxed coordinate, then recursively adds k − 1 elements using the conditioned DPP.Source: §3.1 · p. 4
  • The paper reports that maximum coordinate rounding empirically outperforms the greedy algorithm in the Appendix.The proof bounds the loss by at most a factor of e at each recursive step.Source: §3.1 · p. 4

4 Methods for Batch Active Learning

Batch selection addresses the retraining burden of single-sample active learning, but uncertainty-based batches can miss decision boundaries or contain redundant samples. The proposed Active DPP methods combine uncertainty and dissimilarity in a DPP to select informative, diverse batches.

4 Methods for Batch Active Learning

  • Uniform sampling can select redundant samples and unevenly emphasize parts of the data space; ϵ-greedy can likewise choose correlated samples because it selects by uncertainty alone.The paper illustrates that ϵ-greedy with ϵ = 0 misses an important portion of the decision boundary.Source: §4 · pp. 5–6
  • Passive DPP uses q_i = 1 to select a more homogeneous, less redundant sample set, while Passive DPP-Mode uses an approximate mode instead of random DPP sampling.Passive DPP may not improve performance, though it can mitigate redundancy; the mode variant changes how the batch is selected.Source: §4 · p. 5
  • Uncertainty sampling requires retraining for each queried sample and can miss distant decision boundaries, while batch methods reduce computation and ϵ-greedy adds exploration.The ϵ-greedy variant selects the most uncertain (1 − ϵ)k samples and uniformly samples ϵk more, but uncertainty-only selections can be correlated and redundant.Source: §4 · pp. 5–6

4.1 Active DPP-based Methods

  • Active DPP incorporates sample dissimilarity and uncertainty into a DPP distribution to promote diverse, informative batches.Uncertainty scores set q_i, while γ controls their weight; sampling enforces both properties with appropriate tuning of α and γ.Source: §4.1 · p. 6
  • The method constructs dissimilarity using sample features or distances, with a Gaussian kernel available when a suitable distance metric exists.The kernel parameter σ is a hyperparameter.Source: §4.1 · p. 6
  • Conditioning the DPP on previously selected samples supports batch selection across iterations while addressing redundancy between batches and encouraging exploration of unexplored regions.The method samples additional exploitation or exploration points from the conditioned DPP.Source: §4.1 · p. 6

5 Experiments & Results

The experiments evaluate batch active learning on synthetic and real classification datasets, as well as preference-based reward learning. Active Greedy-DPP is among the best methods on most real classification datasets, while Active DPP-Mode significantly outperforms competitors on nearly all reported robotics tasks.

5 Experiments & Results

  • On four robotics reward-learning tasks, Active DPP-Mode significantly outperformed all four competitors except for one insignificant comparison.The reward-learning experiments are presented in the Appendix.Source: §5 · p. 6

5.1 Implementation Details

  • The main classification experiments used a greedy mode-approximation algorithm because it was considerably faster, although maximum coordinate rounding could yield higher overall performance.Classification used K = 150, batch size k = 15, and a cold start with no initial labels.Source: §5 · p. 6, §5.1 · p. 7

5.2 Classification on a Synthetic Dataset

  • On the synthetic dataset, Active DPP significantly outperformed the other methods (p<0.005), while Active DPP-Mode achieved similar accuracy with lower computation time.Passive DPP also significantly outperformed uniform sampling (p<0.005), and ϵ-Greedy was significantly outperformed by Passive DPP and its greedy variant (p < 0.005). Figure 3 reports accuracies over 100 runs.Source: §5.2 · p. 7, Figure 3 · p. 7
  • On the synthetic task, Passive DPP homogeneously covered the sample space, while Active DPP selected near-boundary samples that were less tightly clustered than ϵ-Greedy selections.The synthetic dataset had two classes and 1,000 samples, with a separate 1,000-sample test set.Source: §5.2 · p. 7

5.3 Classification on Real Datasets

  • The real-data experiments included compressed MNIST and Fashion-MNIST, plus four OpenML datasets; the MNIST datasets used 5-dimensional autoencoder representations.The MNIST and Fashion-MNIST training subsets each contained 5,000 samples, and their test sets contained 10,000 samples.Source: §5.3 · p. 7
  • Active DPP-Mode performed significantly better than the real-dataset baselines, with Figure 4 showing accuracies and marking significant differences.Parenthesized tuples in the figure indicate insignificant differences.Source: §5.3 · p. 8, Figure 4 · p. 8
  • Active Greedy-DPP was among the best methods with statistical significance on 4 of 6 real datasets and gave competitive accuracy on the other two; no algorithm was superior on every dataset.Each method was run 100 times using feed-forward neural networks with sigmoid nonlinearities.Source: §5.3 · p. 8

5.1 Implementation Details

  • The authors note that Active DPP-based methods may improve further by tuning ϵ using heuristics or expertise about the dataset.The classification uncertainty estimates used the entropy of mean class probabilities from an ensemble of 10 neural networks.Source: §5.1 · p. 6, §5.3 · p. 8

6 Discussion

The paper demonstrates its batch-mode method on synthetic and real-world classification tasks while describing broader applications and a computational-cost limitation. The authors also identify several directions for future DPP research.

6 Discussion

  • The method is demonstrated on synthetic and several real-world classification tasks, while the framework is also described for Gaussian Process fitting and reward learning.The authors characterize the framework as more general than these classification use cases.Source: §6 · p. 8
  • Sampling remains a computational bottleneck when N is large, despite acceleration from MCMC sampling and rank-one updates.The authors suggest dual DPP representations with carefully designed similarity features and/or random projections as possible ways to address this cost.Source: §6 · p. 8
  • The authors consider extending DPPs to regression, generative models, and diversity-based learning, including text summarization and video understanding.They note generative models may be useful when data generation is costly, such as in medical imaging.Source: §6 · pp. 8–9
  • The conclusion presents DPP-based batch active learning as applicable to domains where data labeling is costly, while demonstrating use cases with classification tasks.The authors suggest DPPs may also be useful in other machine-learning problems because they naturally provide diversity.Source: §6 · p. 9

Proof of the Approximation Ratio

The proof establishes the rounding algorithm’s ek approximation ratio by induction, bounding the loss at each selection step and relating the argument to a conditioned DPP.

Proof of the Approximation Ratio

  • The rounding algorithm achieves an approximation ratio of ek.The proof proceeds by induction on k, with each selected element losing at most a factor of e.Source: Proof of the Approximation Ratio · p. 12
  • The proof uses first-order optimality and complementary slackness to characterize the optimizer’s coordinates.It also invokes k-homogeneity of g and an inequality relating its gradient to the optimizer.Source: Proof of the Approximation Ratio · p. 12
  • Because ∂ig is the generating polynomial of the DPP conditioned on i ∈ A, the proof bounds its maximum by comparing it with a rescaled optimizer.The comparison seeks a value at least 1/e of the amount under consideration.Source: Proof of the Approximation Ratio · p. 12

Stochastic Mirror Descent Algorithm

The algorithm uses stochastic mirror descent to optimize a convex relaxation of the k-DPP generating polynomial. DPP samples provide stochastic updates, while an entropy-based geometry addresses instability in a direct update.

Stochastic Mirror Descent Algorithm

  • The algorithm optimizes log g(v1, . . . , vN) over nonnegative coordinates whose sum is k, where g is the generating polynomial associated with a k-DPP.The proposed method repeats an iterative procedure for this convex program.Source: Stochastic Mirror Descent Algorithm · p. 12
  • Each iteration samples A according to a DPP, updates u with η1_A, then projects back to the feasible set using the geometry induced by φ.The projection rescales u to satisfy the coordinate-sum constraint.Source: Stochastic Mirror Descent Algorithm · pp. 12–13
  • MCMC sampling can implement the DPP draw in O(N · k^2 log k) time with careful implementations of recent methods.The step size η can be adjusted.Source: Stochastic Mirror Descent Algorithm · p. 13
  • A direct stochastic gradient using diag(v)^−1 1_A was numerically unstable when v had small entries, motivating stochastic mirror descent.The authors use φ(v1, . . . , vN) = Σ_i v_i log v_i, whose Hessian is diag(v)^−1; step 3 projects according to the resulting Bregman divergence.Source: Stochastic Mirror Descent Algorithm · p. 13

Choice of Stochastic Gradient Vector

The stochastic gradient vector can be replaced by another random vector with the same expectation. The authors construct one from MCMC transitions and report lower variance than the indicator vector in practice.

Choice of Stochastic Gradient Vector

  • The authors construct X from MCMC transition probabilities, and report that this choice has less variance than 1_A in practice.The replacement is valid when its expectation is preserved; the described construction uses a mixed chain with A drawn from its stationary distribution.Source: Choice of Stochastic Gradient Vector · p. 13

Empirical Comparison with Greedy Algorithm

The maximum coordinate rounding algorithm compares favorably with greedy DPP-mode maximization. In preference-based reward learning, Active DPP-Mode outperformed the comparison methods across four environments, with one exception.

Empirical Comparison with Greedy Algorithm

7.2 Preference-based Reward Learning

  • The reward-learning method scores queries by expected volume removal and uses Euclidean distance between query features to measure diversity.A query’s features are the differences between the trajectory features in its pairwise comparison.Source: §7.2 · p. 14
  • Under [4]’s Theorem 3.1 assumptions, Active DPP-Mode removes at least 1−δ as much volume as the best adaptive strategy after k ln(1/δ) times as many queries.Source: §7.2 · p. 14
  • After 30 queries, Active DPP-Mode significantly outperformed all comparison methods in every environment (p < 0.05), except successive elimination in LDS, where results were comparable.Source: §7.2 · p. 15

Hyperparameter Tuning

The tuning procedure uses fake labels to select DPP hyperparameters without spending the labeling budget. The appendix reports parameter choices and tuning behavior for synthetic and real classification data, reward learning, and the computation infrastructure.

Hyperparameter Tuning

  • σ is set to the expected distance between two nearest neighbors among k uniform samples; α and γ are tuned on fake labels, while ϵ stays at 1/3 because true-label boundary dispersion is unknown.For real datasets, fake labels assign each sample to its nearest randomly chosen class centroid, repeated until every class has at least 2N/3C samples; mode variants eliminate α.Source: Hyperparameter Tuning · pp. 15–16

Classification on Synthetic Dataset

Classification on Real Datasets

  • For original-dataset experiments, tuning-set γ values giving the highest average accuracies were 5 for Compressed MNIST, 3 for Compressed Fashion-MNIST and Morphological, 1 for Segment and WRN, and 2 for Blood.The algorithm was somewhat robust to different γ values in the given interval; each γ value was experimented with 100 times.Source: Classification on Real Datasets · p. 17

Preference-based Reward Learning

7.4 Computation Infrastructure

  • Experiments used two Ubuntu machines: a 40-CPU, 125GB-RAM Ubuntu 16.04 host and a 32-CPU, 32GB-RAM Ubuntu 18.04.2 host.Source: §7.4 · p. 17
Loading 1906.07975v1…