Towards Data Valuation via Asymmetric Data Shapley

Xi Zheng, Xiangyu Chang, Ruoxi Jia, Yong Tan

TL;DR

This paper introduces "Asymmetric Data Shapley," a novel framework for valuing data in machine learning that goes beyond traditional methods by accounting for inherent data structures. This new approach offers more nuanced and fair valuations, particularly in complex scenarios like data augmentation, sequential data streams, and data marketplaces, and is supported by efficient algorithms.

What Problem Does This Paper Address?

In the age of data-driven AI, accurately quantifying the value of individual data points is crucial for fair compensation, incentivizing data sharing, and building transparent ML systems. The standard "Data Shapley" value, borrowed from game theory, has been a popular tool for this. However, it relies on a "symmetry axiom" that assumes all data points are interchangeable. This assumption breaks down in real-world scenarios where data has inherent structures, such as redundancy (e.g., augmented data), temporal dependencies (e.g., data streams), or complex ownership in data markets. These structural nuances can lead to misleading or unfair valuations, as demonstrated by scenarios where simply duplicating data grants undue value to a packager over original data creators. This paper aims to address this limitation by developing a more flexible data valuation framework that can capture these structural dependencies.

Methods

The core contribution is the development of Asymmetric Data Shapley. This framework relaxes the symmetry axiom of traditional Data Shapley by introducing a "weight system" that assigns different importance to data points based on their inherent structures. This is achieved through:

  • Ordered Partitions and Weighted Systems: Data points are grouped into "social classes" based on their inherent structures (e.g., original vs. augmented data, data from different time periods). A weight system assigns relative importance to these classes and the order in which they are considered.
  • Asymmetric Shapley Value Formulation: A new mathematical formulation is derived for the asymmetric Shapley value, which accounts for these weights and ordered partitions. This allows for structure-aware valuation.
  • Intra-Class Uniform Weight System (ICU-WS): A specific weight system tailored for ML tasks is proposed, where data points within the same class receive uniform weights.
  • Efficient Algorithms: Two algorithms are developed for computing the asymmetric Shapley value:
  • Monte Carlo Method: An approximation method for general weight systems.
  • KNN Surrogate Method: An efficient, iterative algorithm for computing the value, particularly useful for large datasets and complex models, by using a KNN classifier as a proxy for model performance.

Datasets

The paper evaluates its framework on several standard datasets:

  • Adult: Used for augmented data valuation.
  • MNIST: Used for augmented data valuation and data replication scenarios in data markets.
  • Omniglot: Used for augmented data valuation.
  • Metro Interstate Traffic Volume: Used for sequential data valuation.

The paper does not introduce new benchmark datasets but rather applies its methods to existing ones to demonstrate their practical applicability.

Key Insights and Ideas

  • Symmetry is a Limitation: The "symmetry axiom" of traditional Data Shapley, while mathematically elegant, fails to capture the real-world nuances of data. Redundant or sequentially arriving data points are not truly interchangeable, and ignoring this leads to counterintuitive valuations.
  • Structure Matters: Incorporating inherent data structures (like temporal order or class membership) through ordered partitions and weights leads to more meaningful and fair data valuations.
  • Protecting Copyright: Asymmetric Data Shapley can better protect the "copyright" of original data creators in scenarios where data is replicated or augmented, ensuring they receive value for their foundational contributions, not just the packager.
  • Valuing Incremental Contributions: The framework effectively quantifies the incremental value that new or augmented data brings, which is crucial for understanding the impact of data quality and augmentation strategies.
  • Efficiency is Achievable: Despite the added complexity of considering data structures, the proposed KNN surrogate method provides an efficient way to compute these valuations, making the approach practical.

Key Results

  • Augmented Data Valuation: Asymmetric Data Shapley effectively identifies high- and low-quality augmented data points, showing that removing low-value points leads to performance gains and adding high-value points leads to performance improvements, outperforming traditional Data Shapley baselines.
  • Sequential Data Valuation: The framework accurately quantifies the incremental value of newly arrived data points in a stream, demonstrating that high-value data points contribute more significantly to model performance.
  • Fair Allocation in Data Markets:
    • In data replication scenarios, Asymmetric Data Shapley prevents the data packager from gaining undue value by simply copying data, ensuring creators are compensated for their original data's intrinsic value.
  • In data augmentation scenarios, it allocates value more equitably, reflecting the packager's contribution from meaningful augmentation rather than just replication.
  • In sequential data streams, it ensures earlier contributors maintain their value as new data arrives.

Limitations and Future Work

  • Computational Complexity: While efficient algorithms are proposed, computing asymmetric Shapley values can still be computationally intensive, especially for very large datasets or complex weight systems.
  • General Weight Systems: The proposed efficient algorithms are primarily tailored for Intra-Class Uniform Weight Systems (ICU-WS). Extending these to more general weight systems remains an open challenge.
  • Statistical Properties: The paper suggests further research into examining the statistical properties of asymmetric data Shapley in relation to underlying data distributions.
  • More Complex Scenarios: Exploring the framework in even more complex data market or ML scenarios is a promising direction.

Summary updated

Abstract

As data emerges as a vital driver of technological and economic advancements, a key challenge is accurately quantifying its value in algorithmic decision-making. The Shapley value, a well-established concept from cooperative game theory, has been widely adopted to assess the contribution of individual data sources in supervised machine learning. However, its symmetry axiom assumes all players in the cooperative game are homogeneous, which overlooks the complex structures and dependencies present in real-world datasets. To address this limitation, we extend the traditional data Shapley framework to asymmetric data Shapley, making it flexible enough to incorporate inherent structures within the datasets for structure-aware data valuation. We also introduce an efficient $k$-nearest neighbor-based algorithm for its exact computation. We demonstrate the practical applicability of our framework across various machine learning tasks and data market contexts. The code is available at: https://github.com/xzheng01/Asymmetric-Data-Shapley.
BibTeX
@misc{zheng2024towards,
  author = {Xi Zheng and Xiangyu Chang and Ruoxi Jia and Yong Tan},
  title = {{Towards Data Valuation via Asymmetric Data Shapley}},
  year = {2024},
  eprint = {2411.00388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.00388},
}

Loading related content...

Figure