Bayesian Batch Active Learning as Sparse Subset Approximation

Robert Pinsler, Jonathan Gordon, Eric T. Nalisnick, José Miguel Hernández-Lobato

TL;DR

This paper re-imagines batch active learning as a "sparse subset approximation" problem, using techniques from Bayesian coresets to select diverse, informative data points. By approximating the model's full-data posterior with a small batch, the authors create a scalable algorithm that avoids the redundant, highly-correlated queries common in traditional active learning.

What Problem Does This Paper Address?

In supervised learning, labeling data is often the most expensive part of the machine learning pipeline. Active Learning (AL) aims to reduce these costs by intelligently selecting only the most "informative" points for an expert to label.

However, standard AL has two major flaws in the era of Deep Learning:

  1. Sequential Bottlenecks: Most methods pick one point, re-train the model, and repeat. For massive models like ResNets, re-training thousands of times is computationally impossible.
  2. The "Redundancy" Trap: To save time, researchers often pick a "batch" of the top-$b$ most uncertain points. Unfortunately, these points are often right next to each other in the data space. If you ask an expert to label 100 nearly identical images, you’ve wasted 99% of your budget.
Comparison of batch selection methods in latent space. Standard methods like MaxEnt and BALD suffer from the redundancy trap, selecting highly correlated points, whereas the proposed ACS-FW method selects a diverse batch.

The core challenge is to pick a batch that is both informative (high uncertainty) and diverse (covering different parts of the data manifold) without needing to re-train the model after every single point.

Methods

The authors propose Active Bayesian CoreSets with Frank-Wolfe (ACS-FW). Their core insight is to treat batch selection as a geometry problem in a Hilbert space.

  • The Objective: Instead of just looking for "high entropy," they try to find a subset of unlabeled points whose combined influence on the model parameters best approximates the influence of the entire unlabeled pool. Mathematically, they minimize the distance between the "expected complete data log-posterior" and a weighted sum of the points in their batch.
  • Frank-Wolfe Optimization: To solve this normally hard combinatorial problem, they use the Frank-Wolfe algorithm. This is an iterative optimizer that greedily picks the next "best" point to reduce the approximation error. Crucially, once a point is picked, the "residual error" changes, naturally pushing the algorithm to pick a point in a different "direction" (i.e., a diverse point).
  • Scaling with Projections: For simple models (linear/probit), they provide elegant closed-form solutions. For complex neural networks, they use Random Projections of the log-likelihoods. This allows the method to scale linearly with the size of the data pool, making it feasible for datasets with hundreds of thousands of examples.

Key Insights and Ideas

  • Diversity is a Mathematical Consequence: In many AL papers, "diversity" is added as a heuristic or a secondary penalty. Here, diversity emerges naturally from the goal of approximating the full-data posterior. If you pick two identical points, the second point doesn't help you approximate the "full" dataset any better than the first one did.
  • The "Rotating" Acquisition Function: The paper shows that while standard acquisition functions (like BALD) stay static during batch construction, the ACS-FW "acquisition surface" rotates after each selection. This provides an intuitive visual explanation for why it spreads points out across the data space.
Evolution of selected points over time. While BALD repeatedly samples from the same high-uncertainty region, ACS-FW's acquisition surface effectively rotates, forcing the selection of diverse points across the decision boundary.
  • Bridge to Coresets: The paper successfully bridges the gap between Active Learning (selecting data to label) and Bayesian Coresets (compressing already labeled data for faster inference).

Key Results

The authors evaluated their approach on a variety of standard benchmarks, including UCI regression datasets, the massive Year Prediction MSD dataset (over 515,000 points), and classification tasks like CIFAR-10 and SVHN.

  • Superior Scaling: On the massive Year Prediction dataset, ACS-FW significantly outperformed random selection and standard greedy MaxEnt, achieving much lower error with fewer labels.
  • Better than Heuristics: In classification tasks, ACS-FW consistently outperformed or matched state-of-the-art non-probabilistic batch methods like K-Center, proving that Bayesian reasoning can be both principled and high-performing at scale.
  • Efficiency: The time taken to construct a batch was found to be negligible compared to the time required to train the underlying neural network, making it a practical choice for real-world engineering pipelines.

Limitations and Future Work

  • Weight Projection: The Frank-Wolfe algorithm produces continuous weights (e.g., "include this point 0.5 times"). Since AL requires a binary choice (label or don't label), the authors simply pick all points with a weight > 0. They acknowledge that a more principled way to handle this "projection" back to binary choices could improve results.
  • Dependence on Posterior Quality: The method relies on having a good estimate of the model's uncertainty (the posterior). If the underlying Bayesian approximation (like Variational Inference) is poor, the batch selection will likely suffer.
  • Exploration of Other Inner Products: The authors focused on Fisher and Euclidean inner products; they suggest that exploring other kernels or distance metrics in the function space could be a fruitful direction for future research.

Summary updated

Abstract

Leveraging the wealth of unlabeled data produced in recent years provides great potential for improving supervised models. When the cost of acquiring labels is high, probabilistic active learning methods can be used to greedily select the most informative data points to be labeled. However, for many large-scale problems standard greedy procedures become computationally infeasible and suffer from negligible model change. In this paper, we introduce a novel Bayesian batch active learning approach that mitigates these issues. Our approach is motivated by approximating the complete data posterior of the model parameters. While naive batch construction methods result in correlated queries, our algorithm produces diverse batches that enable efficient active learning at scale. We derive interpretable closed-form solutions akin to existing active learning procedures for linear models, and generalize to arbitrary models using random projections. We demonstrate the benefits of our approach on several large-scale regression and classification tasks.
BibTeX
@inproceedings{pinsler2019bayesian,
  author = {Robert Pinsler and Jonathan Gordon and Eric T. Nalisnick and José Miguel Hernández-Lobato},
  title = {{Bayesian Batch Active Learning as Sparse Subset Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=sFSbpAmBsX},
}
Figure