ED Mathématiques et Informatique
On Shapley-Based Responsibility Measures for Explaining Query Answers in the Database and Ontology Settings
by Pierre LAFOURCADE (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
The defense will take place at 14h00 - Amphitéâtre 050 351, cours de la Libération, Bât A30, 33400 Talence
in front of the jury composed of
- Meghyn BIENVENU - Directrice de recherche - Université de Bordeaux - Directeur de these
- Benny KIMELFELD - Professor - Technion - Rapporteur
- Carsten LUTZ - Professeur des universités - Universität Leipzig - Rapporteur
- Diego FIGUEIRA - Directeur de recherche - Université de Bordeaux - CoDirecteur de these
- Antoine AMARILLI - Chercheur avancé - Inria Lille - Examinateur
- Marie-Laure MUGNIER - Professeure des universités - Université de Montpellier - Examinateur
The Shapley value is a wealth distribution scheme that was defined in the 1950s as the unique scheme satisfying a set of desirable axioms. In recent years, it has found use in databases as a means of defining responsibility measures that quantify the contributions of database facts to obtaining a given query answer. These and similar applications of the Shapley value to other settings typically display two major drawbacks, the first conceptual and the second practical: (1) the Shapley axioms themselves are invoked as justification, but these properties ---deemed desirable in economics--- are not necessarily meaningful in every context, and in fact the resulting measures sometimes display unexpected properties; (2) the existing Shapley-based measures are often intractable, with many very simple queries over which they are #P-hard to compute, even in data complexity. The present thesis extends the aforementioned measures to ontology-mediated queries, and addresses these two issues of existing Shapley-based responsibility measures, both in the original database and new ontology settings. For the former issue, we revisit the question of what constitutes a reasonable responsibility measure for query answers and identify properties inspired by the Shapley axioms that are truly meaningful and desirable in our context of interest. For the latter, we design new Shapley-based measures that satisfy said desirable properties, while enjoying more favourable computational complexities. We achieve this by changing the definition of the "wealth function" that is fed to the Shapley value, as a representation of the query answer we wish to explain. Aside from these conceptual contributions, we thoroughly investigate the computational complexity of all studied measures. Our complexity analysis primarily focuses on various variants of conjunctive queries, possibly extended with unions and negations, as well as ontologies that are expressed in lightweight description logics from the DL-Lite and EL families. We finally leverage the conceptual insights developed in our study of responsibility measures for queries to shine a new light on other applications of the Shapley value, most importantly the SHAP score, which is widely used to explain machine learning classifiers.