UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A Multilinear Sampling Algorithm to Estimate Shapley Values

Okhrati, R; Lipani, A; (2021) A Multilinear Sampling Algorithm to Estimate Shapley Values. In: Proceedings of the 25th International Conference on Pattern Recognition (ICPR). IEEE Green open access

[thumbnail of A_Multilinear_Sampling_Algorithm.pdf]
Preview
Text
A_Multilinear_Sampling_Algorithm.pdf - Accepted Version

Download (1MB) | Preview

Abstract

Shapley values are great analytical tools in game theory to measure the importance of a player in a game. Due to their axiomatic and desirable properties such as efficiency, they have become popular for feature importance analysis in data science and machine learning. However, the time complexity to compute Shapley values based on the original formula is exponential, and as the number of features increases, this becomes infeasible. Castro et al. [1] developed a sampling algorithm, to estimate Shapley values. In this work, we propose a new sampling method based on a multilinear extension technique as applied in game theory. The aim is to provide a more efficient (sampling) method for estimating Shapley values. Our method is applicable to any machine learning model, in particular for either multiclass classifications or regression problems. We apply the method to estimate Shapley values for multilayer perceptrons (MLPs) and through experimentation on two datasets, we demonstrate that our method provides more accurate estimations of the Shapley values by reducing the variance of the sampling statistics.

Type: Proceedings paper
Title: A Multilinear Sampling Algorithm to Estimate Shapley Values
Event: 25th International Conference on Pattern Recognition (ICPR)
Open access status: An open access version is available from UCL Discovery
DOI: 10.1109/ICPR48806.2021.9412511
Publisher version: https://doi.org/10.1109/ICPR48806.2021.9412511
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Civil, Environ and Geomatic Eng
URI: https://discovery.ucl.ac.uk/id/eprint/10113161
Downloads since deposit
47Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item