PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Batch Active Learning as Sparse Subset Approximation

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

arXiv:1908.02144v4stat.MLcs.LG

TL;DR

High labeling costs and the poor scalability of sequential active learning motivate a Bayesian batch method that approximates the complete-data posterior with a sparse subset. The resulting ACS-FW procedure produces diverse batches and performs effectively across large-scale regression and classification tasks, while supporting closed-form special cases and random-projection generalization.

  • Problem

    High-cost labeling and computationally infeasible sequential active learning limit scalable Bayesian selection, while naive batches produce correlated queries.

  • Method

    ACS-FW recasts batch construction as sparse approximation of the complete-data log posterior and solves a relaxed objective with Frank-Wolfe optimization and posterior-weighted inner products.

  • Results

    ACS-FW significantly outperforms RANDOM and MAXENT during the entire active-learning process in the reported large-scale experiment.

  • Takeaways & Limitations

    The approach enables probabilistic active learning at scale without sacrificing performance relative to competing batch methods.

  • Takeaways & Limitations

    The method’s projection from continuous Frank-Wolfe weights to feasible selections increases approximation error, and alternatives are left for future work.

Abstract

from arXiv · show

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.

1 Introduction

Active learning reduces labeling demands by selecting informative points, but sequential and naive batch strategies struggle with computational cost, weak model updates, and correlated queries. The paper proposes Bayesian batch active learning through sparse posterior approximation, with scalable extensions and empirical benefits on large tasks.

  • 1 Introduction: Active learning selects data points for labeling to make model training more data-efficient when expert annotation is costly.The motivation includes settings such as labeling fish images, where expert access is limited by time and cost.
  • 1 Introduction: Sequential Bayesian active learning is computationally difficult because exact subset selection is NP-hard and greedy methods repeatedly update the model after each query.These procedures include maximum entropy and maximum information gain strategies.
  • 1 Introduction: Batch selection reduces repeated model updates and supports parallel labeling, but naive acquisition functions still produce highly correlated queries.The resulting batches may spend much of the budget on nearby points.
  • 1 Introduction: The proposed method recasts batch construction as a sparse approximation to the full-data log posterior and uses Frank-Wolfe optimization for scalable Bayesian active learning.It also derives closed-form linear-model solutions and uses random projections for arbitrary tractable-likelihood models.

2 Background

Bayesian active learning seeks informative subsets by reducing posterior uncertainty, but exact subset optimization is intractable and sequential greedy updates scale poorly. Naive batch selection also tends to choose redundant points because individual updates barely change the posterior.

  • 2 Background: Bayesian active learning selects points that reduce uncertainty in the model-parameter posterior, ideally minimizing expected posterior entropy under a query budget.The learner chooses a subset from an unlabeled pool and obtains labels from an oracle.
  • 2 Background: Exact batch selection is intractable because it requires considering all subsets of the unlabeled pool, motivating myopic strategies such as MAXENT and BALD.These methods iteratively select individual points until the budget is exhausted.
  • 2 Background: Sequential greedy strategies become computationally infeasible at scale because the model must be retrained after every acquired point.Adding one point can have a negligible effect on the posterior, limiting the value of repeated updates.
  • 2 Background: Naively selecting the highest-scoring batch points yields highly correlated queries because marginal posterior changes lead subsequent selections toward similar regions.This redundancy is illustrated for standard acquisition methods in Figure 1.

3 Bayesian batch active learning as sparse subset approximation

The method constructs batches by approximating the expected complete-data log posterior with a sparse subset in function space. A relaxed Frank-Wolfe optimization selects informative, diverse points using posterior-weighted inner products, with random-projection extensions for tractable-likelihood models.

  • 3 Bayesian batch active learning as sparse subset approximation: The batch objective approximates the expected complete-data log posterior so the selected subset induces a posterior close to that obtained from the full pool.This reframes Bayesian batch construction as sparse subset approximation in function space.
  • 3 Bayesian batch active learning as sparse subset approximation: Inner products define adaptive directionality and account for similarity among selected points, while weighted Fisher and Euclidean choices support analytical or likelihood-based computation.The Euclidean choice enables random-feature projections for arbitrary models with tractable likelihoods.
  • 3 Bayesian batch active learning as sparse subset approximation: ACS-FW relaxes binary and cardinality constraints, then applies Frank-Wolfe optimization to select points aligned with the residual approximation error.Each iteration can add at most one point, and reselection permits at most b nonzero weights.
  • 3 Bayesian batch active learning as sparse subset approximation: The algorithm projects continuous Frank-Wolfe weights back to a feasible binary selection, increasing approximation error and leaving alternative optimization procedures for future work.This projection is an explicit limitation of the presented optimization procedure.

4 Analytic expressions for linear models

The paper derives closed-form weighted Fisher inner products and acquisition expressions for Bayesian linear and probit regression, connecting them to existing active-learning criteria. These results provide interpretable quantities for constructing batches, while the practical algorithm remains ACS-FW.

  • Analytic expressions for linear models: Closed-form weighted Fisher inner products are derived for Bayesian linear and probit regression, enabling analytic batch-acquisition quantities.The paper presents these models as tractable cases for its general batch active-learning framework.
  • Linear regression: For linear regression, αACS shares x_n^TΣ_θx_n with BALD but scales it by x_n^Tx_n instead of applying BALD’s logarithm.The comparison is made through the squared norm of a data point under the weighted Fisher inner product.
  • Linear regression: exp(2αBALD(x_n; D_0)) ∝ αACS(x_n; D_0), making the two criteria equivalent under a greedy maximizer.The proportionality follows from the additional x_n^Tx_n term in αACS.
  • Linear regression: The αACS acquisition function allows more contribution from the current instance than BALD or leverage scores.The paper attributes this interpretation to the x_n^Tx_n term in αACS.
  • Probit regression: For probit regression, the closed-form expressions use the bi-variate Normal cdf and yield an acquisition form involving input magnitude and regularized predictive variance.The paper notes that the full derivation is given for the corresponding closed-form equations.

5 Random projections for non-linear models

Random feature projections address both the model-specific closed-form limitation and the pool-size cost of analytic batch construction. The resulting procedure applies to models with tractable likelihoods and constructs batches in time linear in pool size.

  • Random projections for non-linear models: Random feature projections extend batch construction beyond models with closed-form inner products and make the required computations scalable.The projections approximate the key quantities used during batch construction.
  • Random projections for non-linear models: The projected procedure works for any model with a tractable likelihood and scales linearly in pool size |P|.The exposition assumes a tractable expectation over predicted labels, although sampling can also be used for that expectation.
  • Random projections for non-linear models: Projected inner products are computed as dot products between J-dimensional Euclidean vectors, with the projection providing an unbiased Monte Carlo estimator.The estimator uses J Monte Carlo samples from the posterior.
  • Random projections for non-linear models: O(|P|J) construction time enables the method to scale to pool sets containing hundreds of thousands of examples.This complexity applies because the algorithm only requires inner products of the specified projected forms.

6 Related work

The paper situates its method among uncertainty-based, diversity-based, optimization-based, and probabilistic batch active-learning approaches. It emphasizes scalability, model generality, and reduced reliance on structured feature geometry.

  • Related work: Existing Bayesian active-learning methods select uncertain or high-information points, but principled batch scaling is difficult for complex nonlinear models.Prior deep probabilistic studies cited here used datasets of at most 10 000 points and few model updates.
  • Related work: Non-probabilistic batch methods often trade off diversity and uncertainty, specialize to particular models, or require optimization over many variables.The paper contrasts these approaches with a method intended for any model with a tractable likelihood.
  • Related work: Some probabilistic batch methods jointly optimize acquisitions or greedily impute labels, whereas this approach avoids updating the model after every selected point.The comparison is made primarily within Bayesian optimization literature.
  • Related work: Unlike k-center core-set selection, the proposed method is less reliant on structured feature spaces and only requires evaluating log-likelihood terms.The contrast follows from its Bayesian-coreset-inspired formulation.
  • Related work: Figure 2 compares BALD’s top ten informative points with ACS-FW’s sequentially selected batch on a probit regression task.Rows show BALD on top and ACS-FW below; queried points are black crosses, acquisition values are color-coded, and the current mean decision boundary is black.

7 Experiments and results

Experiments evaluate whether ACS-FW avoids correlated queries, remains competitive with greedy methods, and scales to large datasets and models. Across these settings, it improves data efficiency and classification accuracy while maintaining practical runtime.

  • Experimental design: The experiments target correlated-query avoidance, small-data competitiveness, large-scale scalability, and runtime across regression and classification tasks.Large-scale experiments use random projections with complex models, while smaller regression experiments use derived closed-form solutions.
  • Regression comparisons: ACS-FW achieves much more data-efficient learning as dataset size increases, although greedy methods can remain stronger in small-data regimes.On smaller UCI datasets, ACS-FW is mostly on par with MAXENT and generally better than RANDOM, while MAXENT-SG and MAXENT-I often perform better.
  • Large-scale regression and classification: ACS-FW significantly outperforms RANDOM on large-scale regression and classification tasks, while performing at least as well as competing batch methods on classification.The regression comparison is shown during active learning on year, while classification comparisons use test accuracy across multiple tasks.
  • Classification comparisons: ACS-FW performs at least as well as competitors including K-CENTER, while significantly outperforming RANDOM across the classification experiments.The evaluated classifiers include RANDOM, MAXENT, BALD, K-MEDOIDS, and K-CENTER.
  • Runtime evaluation: ACS-FW batch construction time is negligible relative to per-iteration training time, and its total cumulative runtime is on par with MAXENT.Although ACS-FW uses more active-learning iterations because its batch sizes vary, its cumulative runtime remains comparable.

8 Conclusion and future work

The paper concludes that ACS-FW is a Bayesian batch active-learning method based on sparse subset approximations, with closed-form solutions and random-projection relaxations for large-scale models. The authors identify principled weight use and interactions with alternative approximate inference methods as future directions.

  • Conclusion: ACS-FW combines sparse subset approximations with Frank-Wolfe optimization to construct Bayesian active-learning batches.The algorithm selects points through Frank-Wolfe iterations and updates their weights using closed-form line searches.
  • Conclusion: Closed-form solutions reveal connections between the method, BALD, and leverage scores.These solutions are derived for tractable model cases and provide an interpretable view of the acquisition procedure.
  • Future directions: Random-projection relaxations allow ACS-FW to address large-scale active learning with general nonlinear probabilistic models.Algorithm 2 samples parameters, computes random feature projections, and applies ACS-FW using the projected representations.
  • Future directions: Future work includes principled use of Frank-Wolfe weights and studying interactions with alternative approximate inference procedures.

B Closed-form derivations

The appendix derives closed-form acquisition expressions for Bayesian linear and probit regression, relating ACS to existing BALD-style criteria and simplifying its computation under model-specific approximations.

  • B.1 Linear regression: For Bayesian linear regression, the posterior and predictive posterior are available in closed form under a factorized Gaussian prior.The derivation assumes a unit-variance factorized Gaussian prior, while noting that richer Gaussian priors are straightforward to accommodate.
  • B.1 Linear regression: Closed-form weighted Fisher inner products are derived for Bayesian linear regression and probit regression, with extensions to more powerful models that retain tractability.The appendix presents these derivations as building blocks for neural linear models and other models with closed-form solutions.
  • B.1 Linear regression: αACS uses the squared norm of each point’s contribution as a greedy acquisition function because that norm tracks posterior-reduction magnitude and Bayesian-coreset sensitivity.This connects ACS to both greedy optimization and the sensitivity quantities used in coreset construction.
  • B.1 Linear regression: Dropping the magnitude term xT_nx_n makes αACS proportional to exp(2αBALD(x_n; D_0)), so the two criteria are equivalent under greedy maximization.Figure 5 evaluates this relationship on synthetic linear-regression data.
  • B.2 Logistic regression and probit regression: In the probit model, αACS and the magnitude-adjusted BALD quantity are equivalent up to a constant factor.The relationship follows from the corresponding closed-form acquisition expressions.
  • B.2 Logistic regression and probit regression: For logistic regression, the exact parameter and predictive posteriors are intractable, so the derivation uses a Gaussian posterior approximation and σ(z) ≈ Φ(z).The resulting probit approximation enables tractable expressions involving Normal-distribution identities and Owen’s T function.
  • B.2 Logistic regression and probit regression: The probit-regression derivation obtains closed-form approximations for the weighted Fisher inner product and the squared norm using bi-variate Normal probabilities.The derivation defines ζ_i from the approximate posterior and invokes a bi-variate Normal cumulative density function.

C Experimental details

The experiments use Bayesian final layers with deterministic feature extractors, dataset-specific training protocols, and ten random projections for ACS-FW batch construction.

  • C.1 Regression experiments: Hyperparameters were manually tuned for performance and training stability, although systematic search could improve results and was expected to affect methods comparably.The experiments were run on CPU or GPU hardware depending on the dataset.
  • C.1 Regression experiments: Regression experiments use two-layer fully connected feature extractors, exact Bayesian inference in the final layer, Gaussian weight priors, and an inverse Gamma noise-variance prior.The final-layer posterior is available in closed form, with a Student’s T predictive posterior.
  • C.1 Regression experiments: ACS-FW uses J = 10 random projections for the power, year, and classification experiment settings.The projection count is stated for both regression and classification configurations.
  • C.1 Regression experiments: Regression training normalizes inputs and outputs, runs Adam for 1000 epochs with cosine annealing, and adapts batch size as the labeled set grows.Learning rates are 10^-2 generally and 10^-3 for power and year.
  • C.2 Classification experiments: Classification experiments use a ResNet-18 feature extractor, variational inference in the Bayesian final layer, and 100 predictive samples.The classification setup uses ten projections during ACS-FW batch construction.
  • C.2 Classification experiments: Classification training uses augmentation, jointly trains the full network for 1000 Adam epochs, and uses a fixed batch size of 256.Augmentation includes random crops, horizontal flips, and input normalization.

D Probabilistic methods for active learning

The classification study finds strong performance from probabilistic baselines and reports that variational Bayesian neural linear models outperform Monte Carlo Dropout on several datasets.

  • D Probabilistic methods for active learning: MAXENT and BALD performed strongly in the experiments, despite earlier reports of weaker performance for these probabilistic baselines.This result is described as surprising relative to prior findings.
  • D Probabilistic methods for active learning: The study motivates comparing inference procedures because neural-network posterior inference is generally intractable and approximate inference may affect probabilistic active learning performance.Monte Carlo Dropout is identified as a common approximation used in prior work.
  • D Probabilistic methods for active learning: Variational inference on a Bayesian final layer produced significant gains over Monte Carlo Dropout on the final layer for CIFAR-10, SVHN, and Fashion-MNIST.Figure 6 compares test accuracy across classification tasks over five seeds, with error bars showing two standard errors.
Loading 1908.02144v4…