PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms

Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J. Spanos, Dawn Song

arXiv:1908.08619v4cs.LGstat.ML

TL;DR

The paper asks how to value individual data contributions when ML models are trained on large datasets, where exact Shapley-value computation is generally expensive. It develops efficient algorithms specialized to KNN utilities, obtaining exact quasi-linear computation and sublinear approximation, while extending valuation to several contributor and analyst settings.

  • Problem

    Shapley-value data valuation is appealing for fairly attributing gains among contributors, but baseline computation is prohibitive for large KNN training datasets.

  • Method

    The paper exploits KNN utility structure for exact Shapley-value computation and uses locality-sensitive hashing and Monte Carlo methods for approximation and extensions.

  • Results

    For unweighted KNN classifiers and regressors, exact Shapley values can be computed in quasi-linear time, while LSH provides sublinear approximation under suitable ε and K conditions.

  • Takeaways & Limitations

    Task-specific Shapley valuation can be made practical for KNN models and extended to multiple data-contributor and computation-contributor settings.

  • Takeaways & Limitations

    Exact KNN Shapley-value computation remains expensive for large and high-dimensional datasets, and LSH approximation is confined to classification.

Abstract

from arXiv · show

Given a data set $\mathcal{D}$ containing millions of data points and a data consumer who is willing to pay for \$$X$ to train a machine learning (ML) model over $\mathcal{D}$, how should we distribute this \$$X$ to each data point to reflect its "value"? In this paper, we define the "relative value of data" via the Shapley value, as it uniquely possesses properties with appealing real-world interpretations, such as fairness, rationality and decentralizability. For general, bounded utility functions, the Shapley value is known to be challenging to compute: to get Shapley values for all $N$ data points, it requires $O(2^N)$ model evaluations for exact computation and $O(N\log N)$ for $(ε, δ)$-approximation. In this paper, we focus on one popular family of ML models relying on $K$-nearest neighbors ($K$NN). The most surprising result is that for unweighted $K$NN classifiers and regressors, the Shapley value of all $N$ data points can be computed, exactly, in $O(N\log N)$ time -- an exponential improvement on computational complexity! Moreover, for $(ε, δ)$-approximation, we are able to develop an algorithm based on Locality Sensitive Hashing (LSH) with only sublinear complexity $O(N^{h(ε,K)}\log N)$ when $ε$ is not too small and $K$ is not too large. We empirically evaluate our algorithms on up to $10$ million data points and even our exact algorithm is up to three orders of magnitude faster than the baseline approximation algorithm. The LSH-based approximation algorithm can accelerate the value calculation process even further. We then extend our algorithms to other scenarios such as (1) weighed $K$NN classifiers, (2) different data points are clustered by different data curators, and (3) there are data analysts providing computation who also requires proper valuation.

1. Introduction

The paper develops efficient Shapley-value algorithms for task-specific data valuation in KNN models, motivated by data marketplaces involving multiple contributors. Its key results exploit KNN structure for exact computation and use LSH for sublinear approximation.

  • Motivation: Data valuation is framed as fairly distributing buyer payments among sellers contributing training instances to an ML model.The setting is motivated by data marketplaces and applications such as crowdsourced ML and clinical data markets.
  • C1.1 Exact Computation: O(N log N) time computes exact Shapley values for all N data points in unweighted KNN classifiers.The algorithm exploits the piecewise utility difference property of KNN utilities, improving exponentially over the stated baseline.
  • C1.2 Sublinear Approximation: O(N^{h(ε,K)} log N) computation provides an (ε, δ)-approximation through Locality Sensitive Hashing when ε is not too small and K is not too large.The approximation reduces to approximate max{K, 1/ε}-nearest-neighbor queries.
  • Limitation of LSH: LSH handles mild error requirements but can be less efficient than exact calculation for stringent errors, and its approximation extension remains confined to classification.The limitation is tied to h(ε,K) increasing with max{1/ε,K}.
  • Contribution 2: Extensions: The paper extends its exact algorithms beyond unweighted KNN classification to unweighted regressors, weighted KNN classifiers, multiple data points per curator, and analyst valuation.The contribution list explicitly includes weighted KNN classifiers and settings where analysts provide computation.

C2.2 Weighted KNN

The paper organizes extensions of KNN data valuation across model, task, contributor, and analyst dimensions. In less efficient cases such as weighted KNN and multiple-data-per-curator settings, improved approximation methods remain necessary.

  • C2.2 Weighted KNN: Weighted KNN is one axis in the paper’s classification of data valuation problems.The framework distinguishes weighted from unweighted KNN models alongside regression versus classification and single versus multiple data points per contributor.
  • C2.2 Weighted KNN: Some weighted KNN and multiple-data-per-curator settings have exact algorithms that are improved exponentially but remain less practical.The paper turns to Monte Carlo approximation for these less efficient cases.
  • Approximation for Extensions: O(N/ε^2 log^2 K) computation is required by the improved Monte Carlo method for the less efficient extension settings.The stated improvement over the state-of-the-art is O(N log^2 N / log^2 K).

2. Preliminaries

The paper frames data valuation as allocating a buyer’s payment among training instances according to their contributions to ML utility. It adopts the Shapley value because it provides fairness, group rationality, additivity, transparency, and decentralizability, while addressing its computational cost through Monte Carlo baselines.

  • Data marketplace: Data marketplaces connect sellers providing labeled training instances with buyers who pay according to the utility of resulting ML models.The buyer aggregates training data from sellers and produces a model for predicting labels on unseen features.
  • Shapley-value valuation: The Shapley value measures each training point’s importance to learning a performant ML model by averaging marginal contributions over all player orderings.Players are training instances, and the coalition utility is the performance of a model trained on the selected instances.
  • Shapley-value valuation: The Shapley value is adopted because it uniquely satisfies group rationality, fairness, and additivity, supporting full-yield distribution, impartial valuation, transparency, and decentralizability.Additivity permits decomposing utilities and computing value shares separately.
  • Computational challenge: Exact Shapley-value computation requires O(2^N) utility evaluations, making valuation impractical for large training sets.Utility evaluation can itself require retraining an ML model on each subset.
  • Computational challenge: The baseline Monte Carlo estimator samples random permutations and averages marginal contributions to estimate each Shapley value.For bounded utility differences, Hoeffding’s inequality gives a permutation-sample requirement for (ε, δ)-approximation.
  • Computational challenge: O(N^2 log^2 N) complexity arises for the baseline KNN classifier because each utility evaluation sorts a training subset, making the approach prohibitive at scale.The baseline performs O(N log N) utility evaluations, and each KNN utility evaluation costs O(|S| log |S|).

3. Valuing Data for KNN Classifiers

For KNN classifiers, the paper exploits locality and piecewise marginal-contribution structure to compute exact Shapley values efficiently. It also develops an LSH-based approximation that retrieves only a limited number of neighbors when the error tolerance is not too stringent.

  • Overview: The paper presents quasi-linear exact Shapley-value computation and a sublinear LSH-based approximation for KNN classifiers.The exact method targets unweighted KNN classifiers, while the approximation focuses on classification tasks.
  • Utility and exact computation: The KNN utility can be defined as the average likelihood of predicting the correct label using the nearest neighbors in a selected training subset.The nearest-neighbor indices determine the labels contributing to the classifier’s testing accuracy.
  • Utility and exact computation: Theorem 1 gives a recursive formula for each training point’s Shapley value, enabled by a piecewise relationship between neighboring points’ utility gains and Shapley-value differences.The proof analyzes how adding neighboring points changes the KNN set and utility.
  • Utility and exact computation: O(N log N Ntest) computes exact Shapley values for N training points and Ntest test points by sorting one length-N array per test point.For multiple test points, additivity makes the overall value the average of the single-test-point values.
  • LSH-based approximation: max{K, ⌈1/ε⌉} nearest neighbors suffice for an (ε, 0)-approximation while preserving the original value ranking among those neighbors.This truncation avoids processing the full training set for each query.
  • LSH-based approximation: For ε not too small such that CK* > 1, LSH provides sublinear-time approximation by estimating values from retrieved nearest neighbors and neglecting sufficiently small remaining values.CK measures the relative contrast between a random training-point distance and the Kth-neighbor distance; smaller contrast makes retrieval harder.

4. Extensions

The paper extends efficient Shapley-value computation beyond standard unweighted KNN classification to regression, weighted KNN, multiple data instances per seller, and analyst valuation. These extensions preserve efficient exact computation in some settings but require polynomial-time algorithms or approximation in others.

  • Unweighted KNN Regression: Unweighted KNN regression admits an iterative extension of the exact Shapley-value algorithm.
  • Weighted KNN: Weighted KNN Shapley values can be computed exactly in O(NK) time, because only NK distinctive nearest-neighbor combinations affect utility values.The paper attributes this complexity to the bounded number of utility-relevant nearest-neighbor combinations.
  • Multiple Data Per Contributor: When each seller provides multiple data instances, seller Shapley values require O(MK) computation for unweighted and weighted classifiers and regressors.For K = 1, the complexity reduces to O(M log M) because utility depends only on each seller’s nearest point.
  • Valuing Computation: The paper models computation providers through a composite game containing M sellers and one analyst, allocating value to both parties.The composite game extends the data-only valuation framework to include the analyst’s computation contribution.
  • General Proof Technique: A piecewise utility-difference property reduces Shapley-value comparison to a counting problem when the utility difference has efficiently evaluable groups.For the examined KNN utilities, the property holds with settings including T = 1, N − 1, and a polynomial expression in K.

5. Improved MC Approximation

The paper improves Monte Carlo Shapley-value approximation for KNN by exploiting lower variance and locality, then implements the method with incremental nearest-neighbor updates. The resulting permutation requirement is largely stable with training-set size, while the method’s efficiency depends on the error regime and K.

  • Sample Complexity: Bennett’s inequality improves on Hoeffding’s bound by using KNN’s smaller utility-difference variance rather than only its range.For KNN, adding a training instance often leaves utility unchanged for many subsets, reducing variance.
  • Sample Complexity: For unweighted KNN classification, the utility-difference range parameter is r = 1 in the Bennett-based bound.
  • Algorithm: The improved Monte Carlo approach estimates all training-point Shapley values from measurements over randomly sampled permutations.
  • Sample Complexity: The required permutation count remains approximately unchanged as N grows because more unknown values offset decreasing Shapley-value variance.The paper explains that larger datasets require more estimates but also contain a larger proportion of points with insignificant contributions.
  • Algorithm: The improved Monte Carlo algorithm incrementally maintains the K nearest neighbors with a max-heap, costing O(N log K) per permutation.Heap insertion costs O(log K), enabling incremental updates during each permutation.

6. Experiments

The experiments evaluate exact, LSH-based, and Monte Carlo Shapley-value methods across datasets and valuation settings. The exact method is highly competitive for unweighted KNN, while LSH helps under moderate approximation requirements and extensions require improved Monte Carlo methods.

  • Experimental setup: The evaluation uses benchmark datasets including dog-fish, MNIST, CIFAR-10, ImageNet, and Yahoo Flickr Creative Commons 100M.The datasets range from hundreds of examples to approximately 100 million photos, with deep feature representations used for several image datasets.
  • Unweighted KNN classifier: The exact algorithm reproduces the Shapley values estimated by Monte Carlo while providing exact results.On MNIST, Monte Carlo estimates converge to the exact algorithm’s values for randomly selected training and test points.
  • Unweighted KNN classifier: The exact algorithm is faster than baseline Monte Carlo by several orders of magnitude, while LSH increasingly outperforms it as training size grows.The LSH advantage is attributed to avoiding sorting large arrays and improving approximate-neighbor search as relative contrast increases.
  • Unweighted KNN classifier: 3×-5× speed-up is achieved by LSH over the exact algorithm for K = 1 across CIFAR-10, ImageNet, and Yahoo10m.The benchmark averages runtime over 100 randomly selected test points per dataset.
  • Unweighted KNN classifier: For LSH, the relative contrast at K*=100 is deep (1.57) > gist (1.48) > dog-fish (1.17), and the required search parameters vary across datasets.The experiments use ϵ = 0.01 and K = 2 for this comparison.
  • Evaluation of other extensions: The LSH approximation is preferable for moderate error and relatively small K, whereas exact computation is recommended otherwise; extensions can require polynomial-time or Monte Carlo computation.For weighted KNN, exact computation has O(NK) complexity, and the improved Bennett-based Monte Carlo method is more than 2× faster than baseline above one million training points.

7. Discussion

The discussion connects KNN Shapley values to monetary rewards, proxy valuation for other classifiers, and task-specific data valuation, while noting transparency and model-bias concerns.

  • From the KNN SV to Monetary Reward: An affine revenue function maps each contributor’s KNN Shapley value to a proportional monetary reward.The mapping assumes R(S) = aν(S) + b, yielding s(R, i) = as(ν, i) + b.
  • SV as a proxy for other classifiers: KNN Shapley values for Iris data are correlated with those from logistic regression, suggesting a possible proxy for other classifiers.The paper cautions that KNN values do not distinguish neighboring points sharing the same label.
  • SV as a proxy for other classifiers: Deep-network Shapley surrogates can be obtained by training KNN on deep features and labels after calibrating K to mimic the original network’s performance.The resulting KNN is then used with the paper’s valuation techniques.
  • Implications of Task-Specific Data Valuation: Task-specific Shapley values accommodate changes in a data point’s utility across applications and can assign low values to data crafted to degrade model performance.The paper also raises concern that valuations may inherit biases from the models used to compute them.
  • Implications of Task-Specific Data Valuation: Blockchain-based data markets are presented as a way to support transparency and trust for the valuation framework.The authors describe implementing the framework in a blockchain-based data market.

8. Related Work

Related work covers query and model pricing, revenue sharing, data-importance methods, and the computational difficulty of Shapley-value estimation.

  • Data and Query Pricing: Existing data marketplaces commonly use simplistic fixed or subscription-based pricing for whole datasets, dataset parts, or access quotas.Examples include Azure Data Marketplace subscriptions and Xignite pricing by data type, size, and query frequency.
  • Data and Query Pricing: Query-based pricing derives prices for purchased queries from explicit prices over a few views while requiring arbitrage-freeness and discount-freeness.This literature focuses on fine-grained relational queries over datasets.
  • Revenue Allocation: Few prior works address allocating revenues among data owners, whereas this paper studies nearest-neighbor revenue allocation using Shapley-value fairness.The cited prior work considered fair revenue sharing for relational queries with multiple sellers.
  • Training-Data Importance: Influence functions and SVM data-removal rules rank training-data importance but do not provide the Shapley value’s stated properties.Influence functions target smooth parametric models and approximate performance changes after removing points.
  • Shapley-Value Computation: General Shapley-value computation can be #P-complete, while sampling-based approximation for bounded utilities requires O(N log N) samples for a desired error.The literature also exploits special utility-function properties to obtain more efficient approximations.

9. Conclusion

The conclusion presents practical Shapley-value data valuation for KNN models through quasi-linear exact algorithms, sublinear approximations, extensions, and large-scale evaluation.

  • Conclusion: The paper calculates KNN data values exactly in quasi-linear time and approximately in sublinear time.This addresses the exponential computational complexity that has limited practical use of Shapley-value data valuation.
  • Conclusion: The algorithms extend to KNN regression, multiple data points owned by one contributor, and simultaneous valuation of data and analytics contributions.The conclusion also identifies future work on other ML algorithms and integration into a clinical data market.

Appendix A. Additional Experiments

Additional experiments compare exact and LSH-based methods for unweighted KNN Shapley-value computation on datasets with up to ten million points.

  • Runtime Comparison: 3×-5× speed-up is achieved by the LSH-based method compared with the exact algorithm.The evaluation averages runtime over 100 test points per dataset using K = 2 and K = 5.
  • Runtime Comparison: The runtime experiment measures average computation time for exact and LSH-based approximation algorithms on a single test point with ϵ, δ = 0.1.Results are reported for K = 2 and K = 5.

Appendix C. Proof of Theorem 2

The appendix develops recursive and efficient Shapley-value calculations for KNN extensions, including regression, weighted KNN, multiple data points per curator, and composite data-and-computation games.

  • Unweighted KNN regression: Theorem 6 computes each training point’s Shapley value recursively for the unweighted KNN regression utility.The utility is defined using negative mean squared error.
  • Unweighted KNN regression: Adjacent regression points have equal Shapley values when their labels match; otherwise, their difference depends on label difference, distance rank, and prediction-error contribution.The difference is larger for larger label differences, smaller distances, and larger induced prediction errors.
  • Weighted KNN: Weighted KNN Shapley values can be computed exactly in O(NK) time by focusing only on subsets whose utility may change when a training instance is added.This is less efficient than the O(N log N) unweighted case but avoids exponential enumeration.
  • Multiple data per contributor: For seller-level valuation, the method represents possible top-K neighborhoods formed by sellers and computes each seller’s Shapley value in O(MK).At most K sellers can contribute the top K instances for a test point.
  • Composite game: The composite game assigns Shapley values to both training points and computation contributors for unweighted and weighted KNN classification and regression.The corresponding procedures retain the computational complexity of the data-only game.

E.4.1. Unweighted KNN classification.

This section analyzes Shapley-value approximation and related KNN valuation formulas, including bounds on individual values, permutation-based error analysis, and LSH search probabilities.

  • Unweighted KNN classification: The piecewise utility-difference structure reduces Shapley-value computation to a counting problem that can be evaluated in O(NT).The parameter T controls the number of piecewise cases or terms used in the computation.
  • Unweighted KNN classification: For unweighted KNN classification, adjacent points’ utility difference is determined by whether their labels match the test label.With differing labels, the Shapley difference is scaled by 1/K.
  • Approximation analysis: Permutation-based Monte Carlo error analysis uses Bennett’s inequality and a union bound to control the maximum estimation error across all data points.The sample count is selected so that the probability of any point exceeding ε error is at most δ.
Loading 1908.08619v4…