Towards Data Valuation via Asymmetric Data Shapley

• URL: http://arxiv.org/abs/2411.00388v2
• Date: Wed, 20 Nov 2024 06:27:46 GMT
• Title: Towards Data Valuation via Asymmetric Data Shapley
• Authors: Xi Zheng, Xiangyu Chang, Ruoxi Jia, Yong Tan,
• Abstract summary: We extend the traditional data Shapley framework to asymmetric data Shapley. We 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.
• Score: 17.521840311921274
• License:
• 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.

Related papers

• EcoVal: An Efficient Data Valuation Framework for Machine Learning [11.685518953430554]
  Existing Shapley value based frameworks for data valuation in machine learning are computationally expensive. We introduce an efficient data valuation framework EcoVal, to estimate the value of data for machine learning models in a fast and practical manner.
  arXiv  Detail & Related papers  (2024-02-14T16:21:47Z)
• Surprisal Driven $k$-NN for Robust and Interpretable Nonparametric Learning [1.4293924404819704]
  We shed new light on the traditional nearest neighbors algorithm from the perspective of information theory. We propose a robust and interpretable framework for tasks such as classification, regression, density estimation, and anomaly detection using a single model. Our work showcases the architecture's versatility by achieving state-of-the-art results in classification and anomaly detection.
  arXiv  Detail & Related papers  (2023-11-17T00:35:38Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• On Responsible Machine Learning Datasets with Fairness, Privacy, and Regulatory Norms [56.119374302685934]
  There have been severe concerns over the trustworthiness of AI technologies. Machine and deep learning algorithms depend heavily on the data used during their development. We propose a framework to evaluate the datasets through a responsible rubric.
  arXiv  Detail & Related papers  (2023-10-24T14:01:53Z)
• Delegating Data Collection in Decentralized Machine Learning [67.0537668772372]
  Motivated by the emergence of decentralized machine learning (ML) ecosystems, we study the delegation of data collection. We design optimal and near-optimal contracts that deal with two fundamental information asymmetries. We show that a principal can cope with such asymmetry via simple linear contracts that achieve 1-1/e fraction of the optimal utility.
  arXiv  Detail & Related papers  (2023-09-04T22:16:35Z)
• DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation [23.646508094051768]
  We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain. The Shapley value is a natural tool to perform dataset valuation due to its formal axiomatic justification. We propose a novel approximation, referred to as discrete uniform Shapley, which is expressed as an expectation under a discrete uniform distribution.
  arXiv  Detail & Related papers  (2023-06-03T10:22:50Z)
• Detection and Evaluation of Clusters within Sequential Data [58.720142291102135]
  Clustering algorithms for Block Markov Chains possess theoretical optimality guarantees. In particular, our sequential data is derived from human DNA, written text, animal movement data and financial markets. It is found that the Block Markov Chain model assumption can indeed produce meaningful insights in exploratory data analyses.
  arXiv  Detail & Related papers  (2022-10-04T15:22:39Z)
• Data-Centric AI Requires Rethinking Data Notion [12.595006823256687]
  This work proposes unifying principles offered by categorical and cochain notions of data. In the categorical notion, data is viewed as a mathematical structure that we act upon via morphisms to preserve this structure. As for cochain notion, data can be viewed as a function defined in a discrete domain of interest and acted upon via operators.
  arXiv  Detail & Related papers  (2021-10-06T04:00:38Z)
• Representative & Fair Synthetic Data [68.8204255655161]
  We present a framework to incorporate fairness constraints into the self-supervised learning process. We generate a representative as well as fair version of the UCI Adult census data set. We consider representative & fair synthetic data a promising future building block to teach algorithms not on historic worlds, but rather on the worlds that we strive to live in.
  arXiv  Detail & Related papers  (2021-04-07T09:19:46Z)
• Efficient computation and analysis of distributional Shapley values [15.322542729755998]
  We derive the first analytic expressions for DShapley for the canonical problems of linear regression, binary classification, and non-parametric density estimation. Our formulas are directly interpretable and provide quantitative insights into how the value varies for different types of data.
  arXiv  Detail & Related papers  (2020-07-02T19:51:54Z)
• Towards Efficient Data Valuation Based on the Shapley Value [65.4167993220998]
  We study the problem of data valuation by utilizing the Shapley value. The Shapley value defines a unique payoff scheme that satisfies many desiderata for the notion of data value. We propose a repertoire of efficient algorithms for approximating the Shapley value.
  arXiv  Detail & Related papers  (2019-02-27T00:22:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.