Fast Approximation of the Shapley Values Based on Order-of-Addition Experimental Designs Article Swipe

MAKE IMPACT

Liuqing Yang , Yongdao Zhou , Haoda Fu , Min‐Qian Liu , Wei Zheng · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2309.08923

Shapley value is originally a concept in econometrics to fairly distribute both gains and costs to players in a coalition game. In the recent decades, its application has been extended to other areas such as marketing, engineering and machine learning. For example, it produces reasonable solutions for problems in sensitivity analysis, local model explanation towards the interpretable machine learning, node importance in social network, attribution models, etc. However, its heavy computational burden has been long recognized but rarely investigated. Specifically, in a $d$-player coalition game, calculating a Shapley value requires the evaluation of $d!$ or $2^d$ marginal contribution values, depending on whether we are taking the permutation or combination formulation of the Shapley value. Hence it becomes infeasible to calculate the Shapley value when $d$ is reasonably large. A common remedy is to take a random sample of the permutations to surrogate for the complete list of permutations. We find an advanced sampling scheme can be designed to yield much more accurate estimation of the Shapley value than the simple random sampling (SRS). Our sampling scheme is based on combinatorial structures in the field of design of experiments (DOE), particularly the order-of-addition experimental designs for the study of how the orderings of components would affect the output. We show that the obtained estimates are unbiased, and can sometimes deterministically recover the original Shapley value. Both theoretical and simulations results show that our DOE-based sampling scheme outperforms SRS in terms of estimation accuracy. Surprisingly, it is also slightly faster than SRS. Lastly, real data analysis is conducted for the C. elegans nervous system and the 9/11 terrorist network.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2309.08923

PDF

https://arxiv.org/pdf/2309.08923

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4386875105

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4386875105

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2309.08923

Digital Object Identifier

Title

Fast Approximation of the Shapley Values Based on Order-of-Addition Experimental Designs

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-09-16

Full publication date if available

Authors

Liuqing Yang, Yongdao Zhou, Haoda Fu, Min‐Qian Liu, Wei Zheng

List of authors in order

Landing page

https://arxiv.org/abs/2309.08923

Publisher landing page

PDF URL

https://arxiv.org/pdf/2309.08923

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2309.08923

Direct OA link when available

Concepts

Shapley value, Permutation (music), Sampling (signal processing), Cooperative game theory, Mathematical optimization, Computer science, Value (mathematics), Order (exchange), Contrast (vision), Sample (material), Scheme (mathematics), Mathematics, Game theory, Mathematical economics, Artificial intelligence, Machine learning, Economics, Computer vision, Mathematical analysis, Chromatography, Acoustics, Filter (signal processing), Finance, Chemistry, Physics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload