PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Banzhaf: A Robust Data Valuation Framework for Machine Learning

Jiachen T. Wang, Ruoxi Jia

arXiv:2205.15466v7cs.LGcs.GTstat.ML

TL;DR

The paper addresses inconsistent data-value rankings caused by noisy performance scores from stochastic learning. It formalizes robustness with safety margins, develops an MSR estimator for Banzhaf value, and finds Banzhaf has the strongest robustness among semivalues and performs well empirically.

  • Problem

    Stochastic training makes model performance scores and existing data-value rankings noisy, undermining reliable data valuation for data quality and sharing applications.

  • Method

    The paper introduces safety margin to quantify robustness and develops an efficient Banzhaf-value estimator based on Maximum Sample Reuse.

  • Results

    Banzhaf value achieves the largest safety margin among semivalues and outperforms existing semivalue-based notions on several SGD-based machine-learning tasks.

  • Takeaways & Limitations

    Data Banzhaf is a promising alternative because it combines computational advantage with robust differentiation of data quality under learning stochasticity.

  • Takeaways & Limitations

    The robustness guarantee is worst-case and allows arbitrary or adversarial perturbations, which may be too strong when the noise source is known.

Abstract

from arXiv · show

Data valuation has wide use cases in machine learning, including improving data quality and creating economic incentives for data sharing. This paper studies the robustness of data valuation to noisy model performance scores. Particularly, we find that the inherent randomness of the widely used stochastic gradient descent can cause existing data value notions (e.g., the Shapley value and the Leave-one-out error) to produce inconsistent data value rankings across different runs. To address this challenge, we introduce the concept of safety margin, which measures the robustness of a data value notion. We show that the Banzhaf value, a famous value notion that originated from cooperative game theory literature, achieves the largest safety margin among all semivalues (a class of value notions that satisfy crucial properties entailed by ML applications and include the famous Shapley value and Leave-one-out error). We propose an algorithm to efficiently estimate the Banzhaf value based on the Maximum Sample Reuse (MSR) principle. Our evaluation demonstrates that the Banzhaf value outperforms the existing semivalue-based data value notions on several ML tasks such as learning with weighted samples and noisy label detection. Overall, our study suggests that when the underlying ML algorithm is stochastic, the Banzhaf value is a promising alternative to the other semivalue-based data value schemes given its computational advantage and ability to robustly differentiate data quality.

1 Introduction

Data valuation supports data cleaning, model understanding, and data-sharing incentives, but stochastic training can make existing value rankings inconsistent. The paper formalizes robustness through safety margins, identifies Banzhaf value as the most robust semivalue, and introduces an efficient MSR estimator.

  • Data valuation quantifies data usefulness for cleaning bad data, understanding test-time behavior, and creating incentives for data sharing.
  • SGD makes model performance scores inherently random, causing existing data valuation methods to produce inconsistent rankings across runs.
  • Safety margin measures the largest perturbation in model performance scores that preserves every pairwise data-value ordering.
  • Banzhaf value achieves the largest safety margin among semivalues, exponentially exceeding the safety margins of Shapley value and LOO error.
  • The MSR algorithm estimates Banzhaf value efficiently, providing logarithmic ℓ∞ and nearly linear ℓ2 sample complexity guarantees.
  • Experiments show Banzhaf value outperforms Shapley value, LOO error, and Beta Shapley on bad-data detection and data reweighting with SGD.
  • Data Banzhaf combines the Banzhaf value with its estimator as a promising alternative offering computational advantage and robust data-quality distinction under learning stochasticity.

2 Background: From Leave-One-Out to Shapley to Semivalue

Data valuation assigns scores reflecting training-point contributions through a utility function over dataset subsets. LOO and Shapley are important special cases within the broader semivalue framework, which relaxes Shapley’s efficiency axiom.

  • Data Valuation Problem Set-up: The data valuation problem assigns each training point a score reflecting its contribution to model training through a utility function over dataset subsets.
  • Leave-One-Out: LOO error measures the change in model performance when one data point is excluded from the full training set.
  • Shapley Value: Shapley value evaluates a point using a weighted average of utility changes from adding it to different subsets.
  • Shapley Value: The Shapley value is uniquely characterized by dummy-player, symmetry, linearity, and efficiency axioms.
  • Semivalue: Semivalues satisfy the Shapley axioms except efficiency and express each point’s value as a weighted average of marginal contributions across subsets.
  • Semivalue: The semivalue framework includes both Shapley value and LOO error, leaving open which semivalue should be adopted.

3 Utility Functions Can Be Stochastic

Because stochastic learning makes utility evaluations random, LOO and Shapley rankings can vary substantially across runs. The section motivates robustness measures that avoid the cost of repeatedly estimating expected performance.

  • SGD and other stochastic learning algorithms make dataset utility randomized because training randomness affects the resulting model and its performance.
  • Figure 1 compares LOO, Shapley, and Banzhaf estimates for 20 CIFAR10 images, including 5 mislabeled images, with variance arising only from utility-evaluation stochasticity.
  • For LOO and Shapley, estimate variance from SGD stochasticity substantially exceeds estimate magnitude, producing average Spearman coefficients of ≈0.001 and ≈0.038.
  • Fewer than 10% of data points remain consistently ranked in LOO or Shapley top/bottom-k% sets for any k ≤50%.
  • Redefining utility as expected performance would remove learning stochasticity, but estimating it accurately requires repeated training runs and adds substantial computational cost.

4 Data Banzhaf: a Robust Data Value Notion

This section formalizes robustness in data valuation through safety margin and shows that the Banzhaf value is the most robust semivalue. It also presents an MSR estimator that improves the efficiency of Banzhaf value estimation.

  • Ranking Stability as a Robustness Notion: Safety margin measures the largest perturbation of model performance scores that preserves every distinguishable pairwise data-value ranking.It is defined over utility functions that sufficiently distinguish data-point pairs and is independent of the specific noise distribution induced by stochastic training.
  • Ranking Stability as a Robustness Notion: The Shapley value has a larger safety margin than LOO error, explaining why it is more stable in stochastic data-selection settings.The paper states Safe(τ; wloo) < Safe(τ; wshap) < τ(n −1).
  • Banzhaf Value Achieves the Largest Safety Margin: The Banzhaf value also minimizes the effect of utility noise on data-value magnitudes by achieving the smallest Lipschitz constant.This robustness criterion bounds changes in data values by changes in utility functions.
  • Efficient Banzhaf Value Estimation: The MSR estimator reuses all sampled utility evaluations across data points and saves a factor of n in sample complexity compared with simple Monte Carlo.The estimator provides approximation guarantees, while its efficient sample-reuse construction is unique to the Banzhaf value among the considered semivalue notions.
  • Efficient Banzhaf Value Estimation: The paper derives lower bounds for Banzhaf estimation and evaluates Data Banzhaf against semivalue-based methods on stochastic-optimization tasks.The evaluation includes bad-data detection and data reweighting, while the lower-bound analysis concerns estimators achieving ℓ∞-norm approximation.

5 EVALUATION

The evaluation tests MSR estimation efficiency, ranking robustness under noisy utility scores, and Data Banzhaf’s effectiveness in weighted-sample learning and mislabeled-data detection. Across these settings, Data Banzhaf provides more stable rankings and outperforms comparison methods.

  • Evaluation scope: The evaluation covers MSR sample efficiency, robustness against six semivalue-based notions, and applications to noisy-label detection and weighted-sample learning.The compared notions include Shapley value, LOO error, and four Beta Shapley variants.
  • 5.1 Sample Efficiency: Figure 4 compares MSR and simple Monte Carlo convergence for Banzhaf estimation, and Relative Spearman Index convergence for Banzhaf and Shapley estimators.The Relative Spearman Index measures ranking consistency between adjacent sample sizes.
  • 5.2 Ranking Stability under Noisy Utility Functions: As utility noise decreases with larger k, Data Banzhaf achieves the most stable data-value ranking, with average Spearman index ≈0.856 versus ≈0.038 for Shapley value.Here, k is the number of repeated evaluations used to average U(S).
  • 5.3 Applications of Data Banzhaf: In weighted-sample learning, higher-valued points receive higher sampling probabilities, and Data Banzhaf outperforms other baselines.Each training point’s value is normalized to [0,1] before sampling.
  • 5.3 Applications of Data Banzhaf: For mislabeled-data detection, labels are flipped for 10% of training points, and Data Banzhaf achieves the best overall F1-score across the evaluated methods.A point is marked mislabeled when its value is below the 10th percentile.

6 Limitation and Future Work

The paper positions Data Banzhaf as a robust and computationally efficient alternative within semivalue-based data valuation, while identifying limits of both robustness analysis and existing alternatives. It also situates the method among cooperative-game and machine-learning valuation approaches.

  • 6 Limitation and Future Work: The paper’s robustness guarantee is worst-case and permits arbitrary or adversarial perturbations, which may be stronger than needed when the noise source is known.The authors identify noise-distribution-specific robustness notions as future work.
  • Related Work: Beta Shapley does not account for performance-score perturbations in its construction, whereas this work characterizes Banzhaf as robust to such perturbations.The cited prior experiments used deterministic learning algorithms, while the paper targets stochastic training such as neural-network learning.

B.2.1 Difficulties in Analytical Analysis of U(S)

The appendix analyzes why directly modeling utility noise is difficult even for simple randomized training settings. These analytical obstacles motivate a noise-structure-agnostic robustness definition instead.

  • Randomized utility functions: With SGD, random initialization and mini-batch choices make the trained model and utility U(S) inherently random.The learning algorithm is represented as A(S; r), where r encodes training randomness.
  • Analytical setting: Even in one-dimensional linear regression with Gaussian initialization, the validation mean squared error follows a generalized chi-squared distribution.The model is trained by gradient descent and evaluated on a validation set.
  • Analytical obstacles: The generalized chi-squared distribution has intractable probability density and cumulative density functions, impeding direct robustness analysis.This difficulty appears even under the simplified analytical setting.
  • Analytical obstacles: Designing a noise-specific notion for a dataset of size n requires understanding noise distributions for every subset S ⊆ N, creating exponential computational burden.Numerical approximation would still require modeling performance distributions over exponentially many subsets.
  • Extension to batch SGD: For batch stochastic gradient descent, the parameter distribution becomes intractable to analyze after the first iteration.The first-iteration parameter is a Gaussian mixture, but later distributions are not tractable in the stated analysis.
  • Motivation for noise-structure agnosticism: These difficulties favor defining robustness independently of the specific noise structure, while retaining tractable analysis for semivalues.The paper connects this approach to the τ-distinguishable utility-function framework.

C.1.1 The Safety Margin for the LOO error, the Shapley value, and the Banzhaf value

This section defines safety margin as the utility noise required to reverse a semivalue ranking and compares it across semivalues. The Banzhaf value achieves the largest safety margin, while other semivalues can tie under a less natural weighting pattern.

  • Safety margin: Safety margin measures the minimum utility noise required to reverse the ranking of two data points under a τ-distinguishing utility function.The comparison is made across semivalue weight functions.
  • LOO and Shapley: For any τ > 0, the Leave-one-out error achieves safety margin Safe(τ; wloo) = τ.
  • Banzhaf value: For any τ > 0, the Banzhaf value achieves the largest safety margin among all semivalues, Safe(τ; w) = τ2n/2−1.
  • Approximate semivalues: Exact semivalue computation is NP-hard in general, motivating analysis of noise tolerance when semivalues are approximated from sampled subsets.
  • Interpretation: The Banzhaf value is not uniquely maximally robust, but it is the only reasonable semivalue among ties because alternative tied weights distinguish odd and even cardinalities without a natural explanation.

C.1.2 Sample Complexity of Simple MC and MSR Estimator.

This section analyzes sample complexity for estimating semivalues, emphasizing the Banzhaf value’s Maximum Sample Reuse estimator. MSR has a direct sampling interpretation for Banzhaf, while analogous Shapley estimation is numerically unstable and Banzhaf estimation has a matching lower-bound result.

  • Simple MC estimator: Theorem 4.8 gives an (ε, δ)-approximation guarantee in ℓ2-norm for the Banzhaf value estimator bϕMC.
  • MSR estimator: Theorem 4.9 gives an (ε, δ)-approximation guarantee in ℓ2-norm for the Banzhaf MSR estimator bϕMSR.The estimator samples subsets independently from Unif(2^N).
  • Lower bound: For Banzhaf value estimation, Theorem 4.10 establishes a lower bound on the sample complexity of every algorithm achieving constant-δ ℓ∞-norm approximation.The proof uses Yao’s minimax principle and distinguishes two utility-function instance classes.
  • Why MSR fits Banzhaf: The Banzhaf MSR estimator is uniquely enabled by uniform subset sampling, whose conditional distributions match the two expectations defining Banzhaf value.
  • Numerical instability: The analogous MSR estimator for the Shapley value is numerically unstable for large n because of combinatorial coefficients.
  • Uniqueness: The sampling-distribution constraints imply that Banzhaf is the only known semivalue satisfying the required MSR-compatible weighting conditions.

C.3 Robustness of MSR Estimator

This section studies how noisy utility evaluations affect Banzhaf MSR estimation and compares robustness through Lipschitz constants. The estimator retains its sample-complexity form with an additional noise-dependent approximation error, while Banzhaf minimizes the Lipschitz constant among semivalues.

  • Noisy utility: Under utility noise satisfying ∥U − bU∥2 ≤ γ, the Banzhaf MSR estimator remains an approximation with an additional irreducible error term.The ℓ2 error term is γ√n/2n/2−1, while the ℓ∞ error term is γ/2n/2−1.
  • Lipschitz robustness: A semivalue’s robustness can be measured by its Lipschitz constant, the smallest constant bounding output changes relative to utility-function changes.
  • Optimal robustness: Among all semivalues, Banzhaf achieves the smallest Lipschitz constant L = 1/2n/2−1.
  • Matrix formulation: The semivalue transformation is linear, so its Lipschitz constant equals the operator norm of its semivalue matrix.
  • Optimization: The minimum operator norm is obtained by the Banzhaf weight function w(k) = n/2n−1.

D.1 Experiment Settings for Figure 1 and 2 in the Main Text.

The experiments estimate LOO, Shapley, and Banzhaf values on noisy CIFAR10 data and assess ranking stability across repeated runs. The evaluation controls estimator sample counts and measures consistency of top- and bottom-ranked data points.

  • Figure 1 settings: The experiment uses a size-2000 CIFAR10 dataset with labels randomly flipped for 10% of data points.
  • Figure 1 settings: Shapley and Banzhaf values use their state-of-the-art estimators with 50,000 samples, while LOO uses its exact formula with noisy utility scores.
  • Figure 2 settings: Figure 2 computes five versions of each data-value score and counts the percentage of points consistently ranked in the top or bottom k% across all runs.
  • Evaluation caveat: The reported results also depend on the robustness of each method’s estimator, so the experiments use the best-known estimators to reduce estimation effects.

D.2 Experiment Settings for Sample Efficiency Experiment in Section 5.1

The sample-efficiency experiment uses synthetic and image datasets with specified model architectures and training settings. Dataset sources and preprocessing are summarized for the broader experiments.

  • Synthetic dataset: The synthetic experiment samples 10 points from a bivariate Gaussian and uses logistic regression, whose test accuracy is around 80%.Labels are assigned by the sign of the sum of the two features.
  • MNIST dataset: The MNIST experiment uses 500 data points with LeNet, batch size 32, learning rate 10^-3, and Adam.
  • Dataset preparation: Datasets are summarized in Table 3 and preprocessed by subsampling to balance labels and binarizing multiclass labels where applicable.These procedures apply to Fraud, Creditcard, Vehicle, and OpenML datasets described in the passage.
  • Model settings: For MNIST and FMNIST, LeNet uses batch size 128; CIFAR10 uses a two-layer 256-neuron MLP with ReLU, batch size 128, learning rate 10^-3, and Adam.Other datasets use a two-layer 100-neuron ReLU MLP with learning rate 10^-2 and dataset-specific batch sizes.

D.3.2 Experiment Settings

The rank-stability experiment evaluates semivalue estimators on CPU and CIFAR10 under controlled stochastic-training perturbations. It compares Data Banzhaf with other notions across noise levels using repeated utility estimates.

  • Settings: The experiment uses CPU with 200 data points and CIFAR10 with 500 data points, with perturbations caused by neural-network initialization and SGD mini-batch selection.
  • Perturbation control: Noise magnitude is controlled by k, the number of stochastic training runs used to estimate expected utility for each sampled subset.Larger k reduces noise in the estimated utility, and k = 50 defines the reference data value.
  • Estimation procedure: The procedure samples m subsets, runs each subset k times, averages its performance scores, and estimates each semivalue from those averages.
  • Results: Data Banzhaf achieves better rank stability than all other data value notions on both datasets across a wide range of k values.Stability is measured by the Spearman index against the approximated ground-truth ranking.

D.5 Additional Results for Ranking Stability Experiment on Tiny Datasets

Additional experiments assess ranking stability when exact values are available on tiny datasets and when score perturbations arise from randomized smoothing. Data Banzhaf remains the most stable method in both settings.

  • Tiny-dataset setup: The tiny-dataset experiment computes exact data values on a 10-point synthetic dataset using logistic-regression test accuracy.This removes estimation error from the ranking comparison.
  • Tiny-dataset setup: Figure 7 compares exact-value rankings with rankings computed from Gaussian-noised utility scores using the Spearman index over 20 repetitions.The noise scale σ is varied on the figure’s x-axis.
  • Limitation: Exact-value evaluation is restricted to toy datasets with at most 15 data points because larger datasets make exact ranking computation infeasible.
  • Randomized-smoothing results: The robustness guarantee is agnostic to perturbation structure, so the theory applies beyond perturbations generated by SGD.
  • Randomized-smoothing results: Data Banzhaf again outperforms all other data value notions when perturbations come from gradient descent with randomized smoothing instead of SGD.The comparison uses CPU and CIFAR10 under the same general rank-stability setting.
Loading 2205.15466v7…