REVIEW 9 cited by
Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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 $(\epsilon, \delta)$-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 $(\epsilon, \delta)$-approximation, we are able to develop an algorithm based on Locality Sensitive Hashing (LSH) with only sublinear complexity $O(N^{h(\epsilon,K)}\log N)$ when $\epsilon$ 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.
Forward citations
Cited by 9 Pith papers
-
An Asymptotic Analysis of the Shapley Value for Dataset Valuation
Under smooth RKHS embedding utilities, a fixed owner's Shapley value is O(1/I)-close in L1 to an explicit leading term of scale (log I)/I driven by a first-order population signal.
-
Understanding Data Influence with Differential Approximation
This paper introduces Diff-In, an influence estimator that accumulates second-order approximations of influence differences across training steps and shows strong accuracy in data cleaning, deletion, and coreset selec...
-
Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation
In-distribution validation noise directionally compresses KNN-Shapley values of training samples toward zero via neighborhood reshuffling, and a boundary-aware rescaling can partially restore baseline statistics.
-
CompLeak: Deep Learning Model Compression Exacerbates Privacy Leakage
Compression of deep learning models can increase privacy leakage when multiple compressed versions are available to an attacker, and combining their outputs makes membership inference attacks much stronger.
-
KAIROS: Scalable Model-Agnostic Data Valuation
KAIROS derives a closed-form Maximum Mean Discrepancy influence score that approximates leave-one-out data rankings and detects noise, mislabels, and backdoors without retraining.
-
A case for data valuation transparency via DValCards
Data valuation is unstable across imputation methods and can penalize minority groups; the paper proposes DValCards to document and constrain such valuation use.
-
Semivalue-based data valuation is arbitrary and gameable
Semivalue-based data valuations are shown to be highly sensitive to plausible utility-function choices and are gameable under the paper's weak definition of gameability.
-
In-Run Data Shapley for Adam Optimizer
An 'Adam-aware' approximation for In-Run Data Shapley is proposed, but its central theorem is not proven and the fidelity test uses a proxy that is not the true Shapley value.
-
On the Usage of Gaussian Process for Efficient Data Valuation
A Gaussian Process integrated-variance utility, updated via Schur complements, computes Shapley data values with less retraining, but the method is numerically unstable in practice.
Discussion (0). Sign in to comment.