EUVIMEDEUVIMED entdecken
Crossref

Efficient Sampling Approaches to Shapley Value Approximation

Jiayao Zhang, Qiheng Sun, Jinfei Liu, Li Xiong, Jian Pei, Kui Ren

Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-24

DOI: 10.1145/3588728 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Jiayao Zhang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 45-mal zitiert (Crossref) und nennt 43 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Shapley value provides a unique way to fairly assess each player's contribution in a coalition and has enjoyed many applications. However, the exact computation of Shapley value is #P-hard due to the combinatoric nature of Shapley value. Many existing applications of Shapley value are based on Monte-Carlo approximation, which requires a large number of samples and the assessment of utility on many coalitions to reach high quality approximation, and thus is still far from being efficient. Can we achieve an efficient approximation of Shapley value by smartly obtaining samples? In this paper, we treat the sampling approach to Shapley value approximation as a stratified sampling problem. Our main technical contributions are a novel stratification design and two sample allocation methods based on Neyman allocation and empirical Bernstein bound, respectively. Experimental results on several real data sets and synthetic data sets demonstrate the effectiveness and efficiency of our novel stratification design and sampling approaches.

Zitieren

APA

Zhang, J., Sun, Q., Liu, J., Xiong, L., Pei, J., & Ren, K. (2023). Efficient Sampling Approaches to Shapley Value Approximation. Proceedings of the ACM on Management of Data, 1(1), 1-24. https://doi.org/10.1145/3588728

Vancouver

Zhang J, Sun Q, Liu J, Xiong L, Pei J, Ren K. Efficient Sampling Approaches to Shapley Value Approximation. Proceedings of the ACM on Management of Data. 2023;1(1):1-24. doi:10.1145/3588728

BibTeX
@article{Zhang2023,
  author = {Zhang, Jiayao and Sun, Qiheng and Liu, Jinfei and Xiong, Li and Pei, Jian and Ren, Kui},
  title = {Efficient Sampling Approaches to Shapley Value Approximation},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2023},
  volume = {1},
  number = {1},
  pages = {1--24},
  doi = {10.1145/3588728}
}
Kostenlos starten →