Data Shapley

Data Shapley satisfies the fairness axioms of Shapley values, ensuring no data point is over- or undervalued. It distributes the total model performance gain among all training points based on their marginal contribution across all possible subsets.

• Symmetry: Identically contributing data points receive equal value.
• Null Player: A datum adding zero performance to any subset gets zero value.
• Additivity: Values sum correctly across combined performance metrics.

Points with high Data Shapley values are disproportionately critical for model accuracy. Removing them causes significant performance degradation, while training exclusively on high-value subsets often outperforms training on random subsets of equal size.

• Identifies outliers that harm generalization (negative Shapley values).
• Enables data pruning: discarding low-value points to reduce training cost without accuracy loss.
• Flags mislabeled examples, which typically receive low or negative values.

Exact Data Shapley computation requires evaluating model performance on all 2^N data subsets, which is intractable. Practical implementations use Monte Carlo approximation by randomly sampling permutations of the training set and measuring the marginal gain as each point is added.

• Truncated Monte Carlo: Stops early when marginal gains stabilize.
• Gradient-based methods: Use parameter gradients instead of full retraining for efficiency.
• K-Nearest Neighbors (KNN) Shapley: Applies the framework to KNN classifiers with closed-form computation.

Data Shapley naturally surfaces data quality problems without requiring explicit quality labels. Points with negative Shapley values actively harm model performance and are often mislabeled, noisy, or out-of-distribution.

• A study on the Toxic Comments dataset found that removing the 1% lowest-valued points improved F1 score more than removing 10% randomly.
• Provides a quantitative audit trail for data provenance and quality control in regulated industries.

Data Shapley generalizes and improves upon Leave-One-Out (LOO) importance. While LOO measures the impact of removing a single point from the full dataset, Data Shapley averages the marginal contribution over all possible subset sizes, capturing complex interactions where a point's value depends on the presence of other specific points.

• LOO fails when redundant copies exist; Shapley correctly distributes value among them.
• Shapley accounts for complementary data points that are only valuable together.

Beyond data cleaning, Data Shapley enables data markets where sellers are compensated proportionally to their data's true contribution. It also supports active learning by selecting unlabeled points expected to have high Shapley value.

• Data poisoning defense: Low-value or negative-value points in a contributor's submission signal potential attacks.
• Fair compensation: Platforms can distribute revenue to data providers based on Shapley values.
• Domain adaptation: Identifies which source-domain samples transfer most effectively.

A foundational concept from cooperative game theory that fairly distributes the total payout of a coalition among its players based on their marginal contributions. In machine learning, each feature or data point is treated as a 'player' in a game where the 'payout' is the model's prediction accuracy. The Shapley value is the unique solution that satisfies four axioms: efficiency (contributions sum to the total), symmetry (identical players get identical values), dummy (zero contribution yields zero value), and additivity (values combine across games). Computing exact Shapley values requires evaluating all possible coalitions, making it exponentially expensive for large datasets.

A method that applies Shapley values to quantify global feature importance by measuring the predictive power each feature contributes when included in a model. Unlike SHAP which explains individual predictions, SAGE answers: 'How much does each feature improve overall model performance?' The method accounts for complex feature interactions by evaluating all possible feature subsets and computing the marginal improvement in a chosen loss metric. SAGE is particularly useful for feature selection, model auditing, and comparing the information content of different data sources across an entire dataset.

An adaptation of Shapley values that incorporates a causal model of the data-generating process to assign feature importance based on causal effects rather than mere statistical associations. Standard Shapley values can produce misleading attributions when features are correlated or confounded. Causal Shapley values use a Structural Causal Model (SCM) to distinguish between direct causal effects, indirect effects, and spurious correlations. This is critical in high-stakes domains like healthcare and policy evaluation where understanding true causal drivers—not just predictive associations—is essential.

A robust statistics tool adapted for machine learning to trace a model's prediction back to its training data by estimating the effect of upweighting or removing a specific training point on the loss at a test point. Unlike Data Shapley's game-theoretic approach, influence functions use gradient-based approximations to compute how infinitesimally perturbing a training example changes model parameters and downstream predictions. Key advantages:

• Computationally efficient for large models via Hessian-vector products
• Identifies both helpful and harmful training examples
• Detects mislabeled data and training set artifacts Influence functions provide a complementary, optimization-centric lens on data valuation.

A family of sampling techniques that make Shapley value computation tractable for large datasets by approximating the exact combinatorial formula. Exact Data Shapley requires evaluating model performance on all 2^N subsets of training data, which is infeasible beyond ~20 points. Monte Carlo methods address this:

• Permutation sampling: Randomly order data points and measure each point's marginal contribution as it's added to the growing training set
• Truncated sampling: Stop evaluating coalitions beyond a certain size, exploiting the diminishing marginal returns of large datasets
• Gradient-based approximation: Use gradient information to estimate Shapley values without full retraining These approximations trade theoretical exactness for practical feasibility.