The Shapley Value of Database Tuples
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Livshits, Ester
Bertossi, Leopoldo
Kimelfeld, Benny
Sebag, Moshe
We investigate the application of the Shapley value to quantifying the contribution of a tuple to a query answer. The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. We study this measure in the context of conjunctive and aggregate queries by defining corresponding coalition games. We provide algorithmic and complexity-theoretic results on the computation of Shapley-based contributions to query answers; and for the hard cases we present approximation algorithms.
 Hello everyone, I'm Esther and I'm going to present our work on the Shapley value of database tuples. This is a joint work with Leopoldo Bautosi, Benny Kimmelfeld and Moshe Szebak. So our main goal in this work is to identify the tuples in the database that best explain why we obtain the certain query results. For example, if we have this database that contains information about the researchers, their publications and number of citations, and the query asking for the total number of citations on papers by researchers in the database, we may want to identify the authors or the institutes that significantly contributed to the total number of citations. And in this work, we propose to use the Shapley value for this task. The Shapley value is a well-known profiteering function from cooperative game theory that was introduced by Lloyd Shapley in 1953. And it has been used in many different areas and fields beyond game theory. For example, for measuring pollution responsibility in environmental management, for influence measurement in social network analysis, for identifying candidate autism genes in medical research, and it has also been used for explanations in machine learning. Now, if you consider the standard machine learning workflow, we have data that is used to extract features that are then used to build a model, and the model is used to obtain predictions on unseen data. Now, researchers in the machine learning community have tried to explain why we obtain the certain prediction, or which features were the most influential ones in making this prediction. And they proposed different measures for this task. And as you can see, the Shapley value is one of them. Here we focus on the first part of this workflow and try to explain which tuples contributed the most to a certain feature value, or more generally to a query result. And again, several measures have been proposed for this task, and I will mention them later, but here we propose to adopt the Shapley value. Now, what is the Shapley value? So we have a game that consists of a set of players and a wealth function that maps each group of players to a number. The question that Shapley tried to answer is how to fairly distribute the total wealth of the game among the players, or equivalently, how to measure the contribution of each player to the total wealth. And Shapley considered functions that satisfy a few good properties that I'm not going to discuss here, but quite remarkably, he established that there is a single function satisfying all of them. And this function is known today as the Shapley value. And the Shapley value is defined using this formula, and I will explain what it means intuitively. Suppose that we want to quantify the contribution of the blue player in this game and continue the following probabilistic game. We select the players one by one, randomly, uniformly, without repetitions. And with each player that we select, we record the change to the total wealth due to the addition of this player in the permutation. For example, we can first select the green player, and the value of the wealth function on this player is two. Then we select the red player, and the value on both players is seven. And we continue until we select the player for which we want to quantify the contribution. As you can see here, the addition of the blue player adds four to the value of the wealth function in this specific permutation. And the Shapley value is just the expected delta, the expected change to the wealth function due to the addition of this player in some random permutation. Now how can the Shapley value be used for explanations? So for explanations in machine learning, the feature values will be the players, and the prediction will be the wealth function. In our case, the tuples in the database will play the role of the players, and the wealth function will be the query result. And this definition is straightforward for queries that map databases to numbers, like Boolean queries or aggregate queries. But it can be easily extended to general queries that return a set of answers or queries with grouping. Then what we will do is we will measure the contribution of tuples to each answer separately. Now if we go back to our example, where we wanted to quantify the contribution of authors to the total number of citations, here the players will be the tuples in the author table, the query that returns the total number of citations will be the wealth function, and we can compute the Shapley value and obtain the following results showing that Alice contributed the most, then Kathy, and so on. Now let's talk about the computational complexity of the Shapley value. So our main result in this work is that the ectomy in data complexity for self-joined free conjunctive queries. We show that if the query is hierarchical, then the Shapley value can be computed in polynomial time. Otherwise, the problem is FP-Sharpy complete. FP-Sharpy is the class of problems that can be solved in polynomial time with an oracle-to-a-problem in Sharpy. And interestingly, this is the exact same classification criterion obtained by Darby and Sotiu for query evaluation over probabilistic databases. Now what is a hierarchical query? So we say that the query is hierarchical if for every two existential variables in the query, either the set of atoms using one of them is contained in the set of atoms using the other one, or these sets of atoms are disjoint. For example, this query is hierarchical because the set of atoms using the variable x contains the sets of atoms using the variables y and z, and the sets for y and z are disjoint. This query, on the other hand, is not hierarchical because the sets of atoms using the variables x and y have a non-empty intersection. They both contain the atom sxy, but none of them contains the other one. Now I'm not going to elaborate on the proof of the positive side of the theorem, but I do want to say a few words about the proof of hardness, and specifically about the proof of hardness for the simplest non-hierarchical query, rxsxydy. To prove hardness here, we construct a reduction from the problem of counting independent sets in a bipartite graph. And this reduction is quite interesting because we use the input to the independent set problem to construct many instances of r problem. In each instance, we add one vertex to the left-hand side of the graph and a few vertices to the right-hand side. So one in the first instance, two in the second instance, three in the third instance, and so on. And we connect all the new vertices on the right-hand side to the new vertex on the left-hand side. Then we put all the vertices on the left-hand side in R, all the vertices on the right-hand side in T, and all the edges in S. And for each instance, we compute the sharply value of the fact corresponding to the new vertex on the left-hand side. Now, from each instance, we obtain an equation over the numbers i as gk, which is the number of independent sets of size k in the original graph G. We show that these equations are independent, so we can actually solve this system and obtain the value i as gk for every k. And finally, the sum of all these values gives us exactly the number of independent sets in the original graph. Now, as I mentioned before, the sharply value is a probabilistic expectation. So using the linearity of expectation, we can easily extend our dichotomy to summations over conjunctive queries and obtain the exact same result. So if we look at this query that we have already seen, it returns the total number of citations, the sharply value can be computed in polynomial time because the underlying conjunctive query is hierarchical. But if we look at this query that is very similar, but it only considers authors from California, then the problem becomes fb-sharpy-complete because this conjunctive query is not hierarchical. In fact, we can extend our hardness results to any numerical function over conjunctive query unless it is constant. So if we want to find the maximal number of citations on papers by researchers from California or the minimal number of citations or the average number, these are all hard problems because the underlying conjunctive query is not hierarchical. Now, let's finish with the more positive picture that we obtained if we allow approximations. So we show that the sharply value has a multiplicative fully polynomial randomized approximation scheme for any conjunctive query with or without self-joins and in fact for any union of conjunctive queries. You can recall that an f-pros is a randomized algorithm that returns an epsilon approximation with probability at least 1-delta and in time polynomial in the size of the input 1 over epsilon and log 1 over delta. This result can again be extended to summations over conjunctive queries. Now to show that, we first obtain an additive approximation by simple Monte Carlo sampling and then we show that the additive approximation is in fact also a multiplicative one due to what we refer to as the gap property which states that the sharply value is never too small. So for every tuple, it is either 0 or at least 1 over some polynomial in the size of the database. Interestingly, when negation is added to the picture, this property no longer holds and we will talk about this in the upcoming course. So to conclude, in this work, we propose to use the sharply value to quantify the contribution of tuples to query results. In a past work, Melio et al introduced the cause of responsibility measure that is based on the minimal number of tuples to remove from the database for the tuple to become counterfactual which means that the result is false without it and true with it. But this measure is designed for Boolean queries and it's not clear if it can be extended to aggregate queries. Salimi et al proposed the causal effect which computes the difference in the expected query result under the assumption that the tuple is present or absent from the database. And we have shown in this work that this measure actually coincides with another well-mone measure from Game Theory called the Bands of Power Index and all of our complexity results can be extended to this measure as well. Now many problems remain open for future work including the complexity for congenital queries with self-joins and extending our understanding of aggregates over conjunctive queries. Thank you very much.
 Hello everyone, I'm Esther and I'm going to present our work on the Shapley value of database  tuples. This is a joint work with Leopoldo Bautosi, Benny Kimmelfeld and Moshe Szebak.  So our main goal in this work is to identify the tuples in the database that best explain  why we obtain the certain query results. For example, if we have this database that  contains information about the researchers, their publications and number of citations,  and the query asking for the total number of citations on papers by researchers in the  database, we may want to identify the authors or the institutes that significantly contributed  to the total number of citations. And in this work, we propose to use the Shapley value  for this task. The Shapley value is a well-known profiteering function from cooperative game  theory that was introduced by Lloyd Shapley in 1953. And it has been used in many different  areas and fields beyond game theory. For example, for measuring pollution responsibility in  environmental management, for influence measurement in social network analysis, for identifying  candidate autism genes in medical research, and it has also been used for explanations  in machine learning. Now, if you consider the standard machine learning workflow, we  have data that is used to extract features that are then used to build a model, and the  model is used to obtain predictions on unseen data. Now, researchers in the machine learning  community have tried to explain why we obtain the certain prediction, or which features  were the most influential ones in making this prediction. And they proposed different measures  for this task. And as you can see, the Shapley value is one of them. Here we focus on the  first part of this workflow and try to explain which tuples contributed the most to a certain  feature value, or more generally to a query result. And again, several measures have been  proposed for this task, and I will mention them later, but here we propose to adopt the  Shapley value. Now, what is the Shapley value? So we have a game that consists of a set of  players and a wealth function that maps each group of players to a number. The question  that Shapley tried to answer is how to fairly distribute the total wealth of the game among  the players, or equivalently, how to measure the contribution of each player to the total  wealth. And Shapley considered functions that satisfy a few good properties that I'm not  going to discuss here, but quite remarkably, he established that there is a single function  satisfying all of them. And this function is known today as the Shapley value. And the  Shapley value is defined using this formula, and I will explain what it means intuitively.  Suppose that we want to quantify the contribution of the blue player in this game and continue  the following probabilistic game. We select the players one by one, randomly, uniformly,  without repetitions. And with each player that we select, we record the change to the  total wealth due to the addition of this player in the permutation. For example, we can first  select the green player, and the value of the wealth function on this player is two.  Then we select the red player, and the value on both players is seven. And we continue  until we select the player for which we want to quantify the contribution. As you can see  here, the addition of the blue player adds four to the value of the wealth function in  this specific permutation. And the Shapley value is just the expected delta, the expected  change to the wealth function due to the addition of this player in some random permutation.  Now how can the Shapley value be used for explanations? So for explanations in machine  learning, the feature values will be the players, and the prediction will be the wealth function.  In our case, the tuples in the database will play the role of the players, and the wealth  function will be the query result. And this definition is straightforward for queries  that map databases to numbers, like Boolean queries or aggregate queries. But it can  be easily extended to general queries that return a set of answers or queries with grouping.  Then what we will do is we will measure the contribution of tuples to each answer separately.  Now if we go back to our example, where we wanted to quantify the contribution of authors  to the total number of citations, here the players will be the tuples in the author table,  the query that returns the total number of citations will be the wealth function, and  we can compute the Shapley value and obtain the following results showing that Alice contributed  the most, then Kathy, and so on. Now let's talk about the computational complexity  of the Shapley value. So our main result in this work is that the  ectomy in data complexity for self-joined free conjunctive queries. We show that if  the query is hierarchical, then the Shapley value can be computed in polynomial time.  Otherwise, the problem is FP-Sharpy complete. FP-Sharpy is the class of problems that can  be solved in polynomial time with an oracle-to-a-problem in Sharpy. And interestingly, this is the  exact same classification criterion obtained by Darby and Sotiu for query evaluation over  probabilistic databases. Now what is a hierarchical query? So we say  that the query is hierarchical if for every two existential variables in the query, either  the set of atoms using one of them is contained in the set of atoms using the other one, or  these sets of atoms are disjoint. For example, this query is hierarchical because  the set of atoms using the variable x contains the sets of atoms using the variables y and  z, and the sets for y and z are disjoint. This query, on the other hand, is not hierarchical  because the sets of atoms using the variables x and y have a non-empty intersection. They  both contain the atom sxy, but none of them contains the other one. Now I'm not going  to elaborate on the proof of the positive side of the theorem, but I do want to say  a few words about the proof of hardness, and specifically about the proof of hardness for  the simplest non-hierarchical query, rxsxydy. To prove hardness here, we construct a reduction  from the problem of counting independent sets in a bipartite graph. And this reduction is  quite interesting because we use the input to the independent set problem to construct  many instances of r problem. In each instance, we add one vertex to the left-hand side of  the graph and a few vertices to the right-hand side. So one in the first instance, two in  the second instance, three in the third instance, and so on. And we connect all the new vertices  on the right-hand side to the new vertex on the left-hand side. Then we put all the vertices  on the left-hand side in R, all the vertices on the right-hand side in T, and all the edges  in S. And for each instance, we compute the sharply value of the fact corresponding to  the new vertex on the left-hand side. Now, from each instance, we obtain an equation  over the numbers i as gk, which is the number of independent sets of size k in the original  graph G. We show that these equations are independent, so we can actually solve this  system and obtain the value i as gk for every k. And finally, the sum of all these values  gives us exactly the number of independent sets in the original graph. Now, as I mentioned  before, the sharply value is a probabilistic expectation. So using the linearity of expectation,  we can easily extend our dichotomy to summations over conjunctive queries and obtain the exact  same result. So if we look at this query that we have already seen, it returns the total  number of citations, the sharply value can be computed in polynomial time because the  underlying conjunctive query is hierarchical. But if we look at this query that is very  similar, but it only considers authors from California, then the problem becomes fb-sharpy-complete  because this conjunctive query is not hierarchical. In fact, we can extend our hardness results  to any numerical function over conjunctive query unless it is constant. So if we want  to find the maximal number of citations on papers by researchers from California or  the minimal number of citations or the average number, these are all hard problems because  the underlying conjunctive query is not hierarchical. Now, let's finish with the more positive  picture that we obtained if we allow approximations. So we show that the sharply value has a multiplicative  fully polynomial randomized approximation scheme for any conjunctive query with or without  self-joins and in fact for any union of conjunctive queries. You can recall that an f-pros is a  randomized algorithm that returns an epsilon approximation with probability at least 1-delta  and in time polynomial in the size of the input 1 over epsilon and log 1 over delta.  This result can again be extended to summations over conjunctive queries. Now to show that,  we first obtain an additive approximation by simple Monte Carlo sampling and then we  show that the additive approximation is in fact also a multiplicative one due to what  we refer to as the gap property which states that the sharply value is never too small.  So for every tuple, it is either 0 or at least 1 over some polynomial in the size of the  database. Interestingly, when negation is added to the picture, this property no longer  holds and we will talk about this in the upcoming course. So to conclude, in this work, we  propose to use the sharply value to quantify the contribution of tuples to query results.  In a past work, Melio et al introduced the cause of responsibility measure that is based  on the minimal number of tuples to remove from the database for the tuple to become  counterfactual which means that the result is false without it and true with it. But  this measure is designed for Boolean queries and it's not clear if it can be extended to  aggregate queries. Salimi et al proposed the causal effect which computes the difference  in the expected query result under the assumption that the tuple is present or absent from the  database. And we have shown in this work that this measure actually coincides with another  well-mone measure from Game Theory called the Bands of Power Index and all of our complexity  results can be extended to this measure as well. Now many problems remain open for future  work including the complexity for congenital queries with self-joins and extending our  understanding of aggregates over conjunctive queries. Thank you very much.
LivshitsBertossiKimelfeldSebag_0_83.png LivshitsBertossiKimelfeldSebag_84_311.png LivshitsBertossiKimelfeldSebag_312_563.png LivshitsBertossiKimelfeldSebag_564_1127.png LivshitsBertossiKimelfeldSebag_1128_1967.png LivshitsBertossiKimelfeldSebag_1968_2603.png LivshitsBertossiKimelfeldSebag_2604_3323.png LivshitsBertossiKimelfeldSebag_3324_4331.png LivshitsBertossiKimelfeldSebag_4332_5195.png LivshitsBertossiKimelfeldSebag_5196_5315.png LivshitsBertossiKimelfeldSebag_5316_5987.png LivshitsBertossiKimelfeldSebag_5988_7091.png LivshitsBertossiKimelfeldSebag_7092_7751.png LivshitsBertossiKimelfeldSebag_7752_10139.png LivshitsBertossiKimelfeldSebag_10140_11807.png LivshitsBertossiKimelfeldSebag_11808_12515.png LivshitsBertossiKimelfeldSebag_12516_13259.png LivshitsBertossiKimelfeldSebag_13260_13631.png LivshitsBertossiKimelfeldSebag_13632_14279.png LivshitsBertossiKimelfeldSebag_14280_16211.png LivshitsBertossiKimelfeldSebag_16212_17927.png LivshitsBertossiKimelfeldSebag_17928_17989.png