INTERPRETING MACHINE LEARNING MODEL USING SHAP ALGORITHM
The basics behind SHAP(SHapley Additive exPlanations) to explain the output of any machine learning model
SHAP (Shapley additive explanations) is a a unified framework for interpreting predictions of complex machine learning models. SHAP is based on shapley values, a game theory concept. So, before understanding SHAP algorithm lets learn about some game theory concepts.
Game theory is the analysis of actions of individual players in a game that affects the outcome of the game. The word ‘game’ is not particularly about computer games. A game can be interactive situations where two or more individuals called players take decisions that determines a final outcome.
Game theory has a wide range of applications, including psychology, evolutionary biology, war, politics, economics, and business.
Game theory definition : Any time we have a situation with two or more players that involve known payouts or quantifiable consequences, we can use game theory to help determine the most likely outcomes.
commonly used terms in game theory :
- Game : A situation where there is outcome due to people interaction.
- Players:An action taker or decision maker in game. They have their own attitude and preferences. ex: People, government, Company etc.
- Actions: What players can do?.
- Payoffs : Payout players receives by producing a particular outcome.
There are mainly two forms of game representation in game theory .
1,Normal Form(matrix form) Normal forms is representing game in form of matrix. It includes players , their actions and also all the payoffs. link .
2, Extensive form : Players move sequentially and represented as a tree. It also keeps track of each player decisions and actions before making a action. link
Normal Form game :
Players : N={1,…n},( n is number of players)
Action set : A a=(a1,…,an) ,
utility function or payoff function(function gives each player payoff ) : u=(u1, …, un)
Representing a game in Normal form : “row” is player1 and column is player2. Rows corresponding ti actions of player1 (a1). and Column correspond to actions of player2 (a2). Cells in inside represents the payoff values for each player by the order of (player1,player2)
Prisoners dilemma .
Prisoners dilemma is a well known example in game theory. Consider the example of two criminals arrested for a crime. Prosecutors have no hard evidence to convict them. However, to gain a confession, officials remove the prisoners from their solitary cells and question each one in separate chambers. Neither prisoner has the means to communicate with each other. Officials present four deals, often displayed as a 2 x 2 box.
- If both confess, they will each receive a three-year prison sentence.
- If Prisoner 1 confesses, but Prisoner 2 does not, Prisoner 2 will get five years.
- If Prisoner 2 confesses, but Prisoner 1 does not, Prisoner 1 will get five years
- If neither confesses, each will serve one year in prison.
The most favorable strategy is to not confess. However, neither is aware of the other’s strategy and without certainty that one will not confess, both will likely confess and receive a three-year prison sentence. The Nash equilibrium suggests that in a prisoner’s dilemma, both players will make the move that is best for them individually but worse for them collectively.
There are many types of game theories. Cooperative and non-cooperative game theories are the most common .
Cooperative game deals with group of players rather than individual players. The groups of players work together and they get payoff as a single value the single payoff value can redistribute among group members call it as a transferable utility . link.
Non-cooperative game is a game with competition between individual players, as opposed to cooperative games, and in which alliances can only operate if self-enforcing . link.
This is an overview of the game theory .
As we seen in the cooperative game, Payoff can be redistribute among the players . There is question how we divide the payoff for each players inside the group ?
In order to be fair ? In order to be stable?
In order to be fair we can consider three axioms below ..
1, Let i and j are two players in group.if i and j are interchangeable then contribution of both i and j in group will be same. It is called symmetry axiom . For any v, if i and j are interchangeable then ψi(N,v) = ψj (N,v)
2, ‘i’ is a dummy player if the amount that ‘i’ contributes to any coalition is exactly the amount that i is able to achieve alone. It is called dummy player axiom.For any v, if i is a dummy player then ψi(N,v) = v({i}).
3, The additivity axiom states that if we re-model the setting as a single game in which each coalition S achieves a payoff of v1(S) + v2(S), the agents’ payments in each coalition should be the sum of the payments they would have achieved for that coalition under the two separate games. It is called additivity axiom. For any two v1 and v2, we have for any player i that ψi(N,v1 + v2) = ψi(N,v1) + ψi(N,v2), where the game (N,v1 + v2) is defined by (v1 + v2)(S) = v1(S) + v2(S) for every coalition S.
Shapley value
The Shapley value is one way to distribute the total gains to the players, assuming that they all collaborate. Shapley value helps to determine a payoff for all of the players when each player might have contributed more or less than the others.
Given a coalitional game (N,v), there is a unique payoff division x(v) = φ(N,v) that divides the full payoff of the grand coalition and that satisfies the Symmetry, Dummy player and Additivity axioms.
Payoff division φ(N,v) is called the Shapley value.
Lets, understand each values :
N : Total players in a game
S : subset of N . (different groups of players that can form from N without the player i )
V : Value function of S that gives us the total payoff as a single value .
“average marginal contribution” of agent i, averaging over all the different sequences according to which the grand coalition could be built up from the empty coalition.
[v(S ∪ {i}) − v(S)] : Contribution of i, Comparing S and (S ∪ {i})
|S|! : different ways the set S could have been formed prior to agent i’s addition.
(|N| − |S| − 1)! : Different ways the remaining agents could be added afterward.
∑ S⊆N\{i}: sum over all possible sets S
|N|! : Sum over all possible sets S and obtain an average by dividing by number of possible orderings of all the agents. reference
Example : Lets take two partners Sharing there profit .
SHAPLEY VALUES IN MACHINE LEARNING:
We got intuition behind Shapley values in game theory. When it comes to the machine learning model the “game” here is the task we are assigning(classification, regression..), “Players” are the features values of the model, and output using the features is its “final payoff”. Then we calculate the average marginal contribution of a feature 𝒙 towards a model score using the Shapley value formula.
In 2017, Scott M. Lundberg and Su-In Lee introduced SHAP which has some methods to explain individual predictions.
SHAP (Shapley Additive exPlanations) is unified framework for interpreting a machine learning model. Shap assigns a value for each feature according to the importance of the feature.
Additive Feature Attribution Methods
Additive feature attribution methods have an explanation model that is a linear function of binary variables, the method which matches these models attribute an effect to each feature, and summing the effects of all feature attribution approximates the output f(x).
lets discuss some Additive feature attribution methods,
1,The LIME method interprets individual model predictions based on locally approximating the model around a given prediction. link
2,DeepLIFT was recently proposed as a recursive prediction explanation method for deep learning . link
3,The layer-wise relevance propagation method interprets the predictions of deep networks. link
4,Classic Shapley Value Estimation link
A surprising attribute of the class of additive feature attribution methods is the presence of a single unique solution in this class with three desirable properties (described below).
Property 1 (Local accuracy) : When approximating the original model (f) for a specific input x, local accuracy requires the explanation model to at least match the output of f for the simplified input x 0 (which corresponds to the original input x).
Property 2 (Missingness) : If the simplified inputs represent feature presence, then missingness requires features missing in the original input to have no impact.
Property 3 (Consistency): states that if a model changes so that some simplified input’s contribution increases or stays the same regardless of the other inputs, that input’s attribution should not decrease.
Definition 1: Additive feature attribution methods have an explanation model that is a linear function of binary variables:
Methods with explanation models matching Definition 1 attribute an effect φi to each feature, and summing the effects of all feature attributions approximates the output f(x) of the original model.
Theorem 1: Only one possible explanation model g follows Definition 1 and satisfies Properties 1, 2, and 3:
Theorem 1 follows from combined cooperative game theory results, where the values φi are known as Shapley values. Under Properties 1–3, for a given simplified input mapping hx, Theorem 1 shows that there is only one possible additive feature attribution method. This result implies that methods not based on Shapley values violate local accuracy and/or consistency
The following section proposes a unified approach that improves previous methods, preventing them from unintentionally violating Properties 1 and 3.
Kernel SHAP (Linear LIME + Shapley values)
we know the Shapley values are the only possible solution that satisfies Properties 1–3 — local accuracy, missingness and consistency. A natural question to pose is whether the solution to Linear LIME recovers these values. The answer depends on the choice of loss function L, weighting kernel πx0 and regularization term Ω. we can recover the shapley values by avoiding heuristically choosing the parameters in linear LIME explanation model. link
Deep SHAP (DeepLIFT + Shapley values)
DeepLIFT is an additive feature attribution method that satisfies local accuracy and missingness, we know that Shapley values represent the only attribution values that satisfy consistency. This motivates our adapting DeepLIFT to become a compositional approximation of SHAP values, leading to Deep SHAP.
The paper proposes many other ways such as TreeSHAP, Max SHAP, Linear SHAP etc. You can refer to the paper for more.
Ref :
1, https://arxiv.org/abs/1705.07874
2,https://christophm.github.io/interpretable-ml-book/shap.html
3,https://en.wikipedia.org/wiki/Shapley_value
4, Game theory coursera
5,https://www.cs.ubc.ca/~kevinlb/teaching/cs532l%20-%202007-8/lectures/lect23.pdf
Thank you
