The mathematics behind Shapley Values

the Sharpie value is considered a fair way to divide the value of a game amongst its players and I promise the formula is not so scary okay maybe at first glance it is quite intimidating but trust me once you get under the hood you'll find it actually has quite an intuitive explanation hi I'm Connor and welcome to Ado today we're going to understand the mathematics behind shapley values to do this we're going to start with a simple two-player game and slowly work our way up to the generalized formula to understand why it's fair we'll also discuss the axioms this formula is derived from if you want to understand how this formula is applied to machine learning then wait until the end of the video I'll explain how you can get access to a python sharp course there's also an article that goes along with this video it might help you if you want to clarify some of the details we discussed here you can find a link to it in the description let's get started suppose you and a friend enter a kaggle contest you end up winning the first prize of ten thousand dollars we call this a coalition value so the value of the Coalition or team of player one and player two is ten thousand dollars now you want to you want to split the money fairly your friend suggests that you simply split it equally so you each get five thousand dollars but you are not happy with this all the model training was done using your GPU you believe you deserve a larger share conveniently your friend owns a time machine you both go back in time and redo the kaggle contest alone please excuse these terrible animations so this time you end up coming second and make 7 500 your friend only comes third and makes five thousand dollars also if none of you played you wouldn't make any prize money these are the Coalition values looking at these it's clear that you deserve more of the prize money you do better by yourself or in other words you you contributed more to the Coalition of two players however it's still not clear how we should divide up the prize money one way to do it is to calculate the expected marginal contribution of each player to do this we start by calculating the marginal contributions of each player these are the increases in prize money due to a player joining a coalition let's start with player one they could join a coalition of only player 2. in this case the Coalition will go from third place to first place and the prize money increases by five thousand dollars player one could also join a coalition of no players and increase the prize money by seven thousand five hundred dollars these are the marginal contributions of player one to calculate the expected marginal contribution we take the weighted average of these values this gives us a value of six thousand two hundred and fifty dollars we can follow a similar process to calculate the expected marginal contribution of player 2. in this case we get a value of 3750 notice how the two values add up to the original prize money of ten thousand dollars in fact these two values are shapley values so in a game the shapley value of a player is the expected marginal contribution of that player which is the weighted average of a player's contribution to all the coalitions that that player could join the Japanese values are considered a fair way to divide the prize money in the previous example we glossed over what a weighted average is to see how we calculate the weights let's look at a three player game we definitely be breaking a few time traveling rules to calculate all the Coalition values there are now eight possible coalitions together all three players win first prize if nobody played you wouldn't win any money there are three coalitions of two players for example a coalition of player one and player 3 would come second and win seven thousand five hundred dollars there will also be three coalitions of one player if player three played alone they would not make any prize money perhaps they should have invested in a better GPU we can use these to calculate the marginal contributions of player one they are now four coalitions that player one could join they could join a coalition of both player 2 and player three they could join a coalition of only player 2 or only player 3 they could also join a coalition of no players finally we take the weighted average this gives us a sharply value of five thousand dollars so where do these weights come from well they are the probabilities that player one makes those respective marginal contributions by Waiting by probabilities we get an expected marginal contribution it is not immediately obvious where these probabilities come from let's start with the first marginal contribution to calculate the probability of this marginal contribution we need to work out the probability that player one makes a marginal contribution to a coalition of player 2 and player 3. to start we need to work out the number of ways a coalition of three players can form this is because the full prize money of ten thousand dollars is only one when all three players work together to do this we assume each member joins the team sequentially with equal chance for example player one could join then player 2 then player 3 or player one could join then player three then player two in total there are three factorial or six ways to form a coalition of three players now all we need to do is count the number of ways player one can join a coalition of player two and three well this can happen in two ways either player two joins then player three then player one or player three joins then player two then player one we can write this as two factorial times one factorial so player one makes this marginal contribution two of the six ways that the Coalition can form this gives us a weight of two over six or one third what about the second marginal contribution well there's only one way for player one to make this contribution which gives the weight of one over six we can work out the remaining values in a similar way we can use similar logic to calculate the weights in general that's if we have a p player game and we want to work out the weight for the marginal contribution of player I to Coalition s let's start with the denominator the number of ways to form a coalition of P players is p factorial s is the coalition we use the absolute value notation to represent the number of players in the Coalition so absolute s factorial is the number of ways the Coalition s can form we also need to consider the number of players that must still join after player I has joined Coalition s we started with P players we subtract the absolute s for the players already in the Coalition and we subtract one because player I has also joined this gives us the weights and what are we finding the weight of well it's the value of the Coalition including player I less the value excluding player I this is the marginal contribution of player I to Coalition s the last thing we need to do is sum over all the possible coalitions that player I can join and that's it that's the shapley value formula this gives a fair value for player I in a p player game breaking down the shapley value you can see that it has an intuitive explanation we are awaiting all the marginal contributions of a player by the probabilities that they make those contributions we then sum over all the possible coalitions that that player can make a marginal contribution to this gives us an expected marginal contribution the question is why is this a fair way to divide value intuitively it may seem like the expected marginal contribution is a fair way we are considering all the possible coalitions that a player can join this means we're considering the player's individual contributions as well as the interactions between players the problem is there could also be other ways to divide value that also seem fair we need to prove that the shape value is a fair way to do this the shappy value is actually derived from four axioms the first is efficiency this means that none of the gains value is left over we saw this with the two-player game where the individual Sharpie values added up to the total prize money of ten thousand dollars the second Axiom is symmetry two players are considered interchangeable if they make the same contributions to all coalitions the two players are interchangeable they must be given an equal share of the game's total value null player if a player makes zero marginal contribution to all coalitions then they get none of the total value the last Axiom is additivity if we combine two games then a player's overall contributions is the sum of the contributions for the two individual games this Axiom makes the assumption that any game played are independent together these axioms can be considered a definition of fairness and the method of dividing value that satisfies them can be considered Fair Lloyd shapley Define these four axioms mathematically and he proved that the shapley value was the only value that satisfied all four of them personally I think it's pretty amazing how we can go from these four simple axioms to such an intuitive formula at this point you may be asking what does all this have to do with machine learning well we can adapt the shapley value formula to explain models we go from dividing value of a gain amongst its players to dividing a model's prediction amongst its features if you want to see how this is done then check out this first video otherwise if you want to jump straight into applying the sharp package then check out the second video you can also get access to my python sharp course for free by signing up to the newsletter in the description this will equip you with the knowledge and skills needed to explain any machine learning model using shap

Channel: A Data Odyssey

Views: 19,436

Keywords:

Id: UJeu29wq7d0

Length: 11min 48sec (708 seconds)

Published: Mon Mar 27 2023