Mikaël Monet, Inria Lille.
25 February 2022, 10:30-11:30.
ENS, S16.
Shapley Values for Relational Databases and Machine Learning
The Shapley value is a game-theoretic function that can be used to distribute the wealth of a team in a cooperative game. This function has strong theoretical justifications has been applied across various fields such as economics, law, environmental science, and network analysis. The talk will consits of two parts:
– In the first part, I will explain how the framework of Shapley values can be used in the context of relational databases query evaluation, where it can be used to measure the contribution of inputs facts of a database to output of a query. I will in particular present a proof that the Shapley value can be computed in polynomial time for a query Q whenever the probabilistic query evaluation problem for Q can. I will also present an approach to compute the Shapley value based on provenance and knowledge compilation. This part of the talk present results of a joint publication with Daniel Deutch, Nave Frost and Benny Kimelfeld, available at https://arxiv.org/abs/2112.08874.
– In the second part of the talk I will present how the Shapley value is used in machine learning, embodied in the notion of “SHAP-score”, and we will show that this score can be computed in PTIME over deterministic and decomposable Boolean circuits — a formalism from knowledge compilation –, thus generalizing a recent result about decision trees. This part of the talk present results of a preprint with Marcelo Arenas, Pablo Barceló and Leopoldo Bertossi, available at https://arxiv.org/abs/2104.08015.
