Attention Flows are Shapley Value Explanations (2021)

Abstract: Shapley Values, a solution to the credit assignment problem in cooperative game theory, are a popular type of explanation in machine learning, having been used to explain the importance of features, embeddings, and even neurons. In NLP, however, leave-one-out and attention-based explanations still predominate. Can we draw a connection between these different methods? We formally prove that — save for the degenerate case — attention weights and leave-one-out values cannot be Shapley Values. Attention flow is a post-processed variant of attention weights obtained by running the max-flow algorithm on the attention graph. Perhaps surprisingly, we prove that attention flows are indeed Shapley Values, at least at the layerwise level. Given the many desirable theoretical qualities of Shapley Values — which has driven their adoption among the ML community — we argue that NLP practitioners should, when possible, adopt attention flow explanations alongside more traditional ones.

## introduction the approaches to model interpretability taken by the ml and nlp communities overlap in some areas and diverge in others. notably, in machine learning, model prediction has sometimes been framed as a cooperative effort between the potential subjects of an explanation (e.g., input tokens) @xcite . but how should we allocate the credit for a prediction, given that some subjects contribute more than others (e.g., the sentiment words in sentiment classification)? the shapley value is a solution to this problem that uniquely satisfies several criteria for equitable allocation @xcite . however, while shapley value explanations have been widely adopted by the ml community -to analyze the importance of features, neurons, and even training data @xcite ) -they have had far less traction in nlp, where leave-one-out and attentionbased explanations still predominate. what is the connection between these different paradigms? when, if ever, are attention weights and leave-one-out values effectively shapley values? the adoption of shapley values -which have their origins in game theory @xcite -by the ml community can be ascribed to their many desirable theoretical qualities. for example, consider a token whose masking out does not impact the model prediction in any way, regardless of how many other tokens in the sentence are also masked out. in game theory, such a token would be called a null player, whose shapley value is guaranteed to be zero @xcite . if we could provably identify the conditions under which attention weights and leave-one-out values are shapley values, we could extend such theoretical guarantees to them as well. in this work, we first prove that -save for the degenerate case -attention weights and leaveone-out values cannot be shapley values. more formally, there is no set of players (i.e., possible subjects of an explanation, such as tokens) and payoff (i.e., function defining prediction quality) such that the values induced by attention or leave-oneout also satisfy the definition of a shapley value. we then turn to attention flow, a post-processed variant of attention weights obtained by running the max-flow algorithm on the attention graph (abnar and zuidema, 2020). we prove that when the players all come from the same layer (e.g., tokens in the input layer), there exists a payoff function such that attention flows are shapley values. this means that under certain conditions, we can extend the theoretical guarantees associated with the shapley value to attention flow as well. as we show, these guarantees are axioms of faithful interpretation, and having them can increase confidence in interpretations of black-box nlp models. for this reason, we argue that whenever possible, nlp practitioners should use attention flow-based explanations alongside more traditional ones, such as gradients @xcite . we conclude by discussing some of the limitations in calculating shapley values for any arbitrary player set and payoff function in nlp. ## model interpretation as a game the shapley value @xcite was proposed as a solution to a classic problem in game theory: when a group of players work together to achieve a payoff, how can we fairly allocate the payoff to each player, given that some contribute more than others? the players here are the potential subjects of the explanation (e.g., input tokens); the payoff is some quality of the model prediction (e.g., correctness). we contextualize the game theoretic terms with respect to model interpretability below. definition 2.1. a player is a possible subject of the explanation (e.g., character, token, embedding, neuron). @xmath0, ..., n} is the set of all players. definition 2.2. a coalition is a subset of players s ⊆ n that work together. there are 2 n possible coalitions. the other players n \ s are left out by being replaced with a non-subject that cannot affect the outcome (e.g., a zeroed-out embedding or a dropped-out neuron). definition 2.3. the payoff reflects some quality of the model prediction -e.g., correctness, confidence, entropy -made using a given coalition. it is defined by a payoff function v : 2 @xmath1, where v(∅) = 0. the value φ i (v) of a player i is the share of the payoff allocated to it. in other words, it is the importance accorded to subject i of an explanation. definition 2.4. a game is defined by (n, v), a player set n and payoff function v. it is a transferable utility game (tu-game), where the payoff can be distributed among the players as desired. in the game of model interpretation, the subjects of the explanation are framed as players working cooperatively to make the best possible prediction. ## attention flows what if we restricted the players to those from the same layer of a model? the remaining players still affect the prediction but can't have any of the payoff allocated to them. in this case, attention weights still cannot be shapley values. however, attention weights can be post-processed. abnar and zuidema (2020) proposed treating the self-attention graph as a flow network -where the attention weights are capacities -and then applying a max-flow algorithm @xcite to this network to calculate the maximum flow on each edge. we prove (by construction) that these attention flows are shapley values when the players are restricted to those from the same layer and the payoff is the total flow, as visualized in figure 1 . proposition 2. consider a tu-game (n, v), where @xmath2, ..., n} players are all from the same layer. let f denote the flow obtained by running a maxflow algorithm on the graph defined by the selfattention matrix, where the capacities are the attention weights. let v(s) = |f (s)|, the value of the flow when only permitting flow through players in the coalition s ⊆ n . then for each player i, its total outflow |f o (i)| is its shapley value. proof. blocking the flow through a player @xmath3, since the attention flow is only calculated once -with the entire graph -and not for each possible subgraph. since the players are all disjoint and have no connections, blocking the flow through one player does not affect the outflow of any of the other players. this would not be the case, for example, if the players were in different layers, in which case changes in flow upstream would cause changes in flow downstream. then for any coalition s ⊆ n and player @xmath4, v(s ∪ {i}) = v(s) + |f o (i)|. we can rewrite the total outflow for player i as figure 1 : the attention flow network for three tokens across three layers, with player nodes (red) and non-player nodes (blue). the payoff v(n ) is the total flow through the network. φ i (v) is the total outgoing flow of player i. note that if we remove player i, then the total flow will decrease by φ i (v), but the outgoing flow of the other two players (red) will stay the same. in other words, the contribution of player i to the total flow v(n ) is always φ i (v); therefore, φ i (v) is its shapley value. this construction is possible because the players are all in the same layer and therefore parallel; if one depended on another, then its outgoing flow could not be its shapley value. attention rollout abnar and zuidema (2020) also proposed another post-processed variant of attention called attention rollout, in which the attention weight matrices from each layer are multiplied with those before it to get aggregated attention values. attention roll-out values cannot be shapley values, however; this can be shown with a trivial extension of the proof to proposition 1. ## leave-one-out erasure describes a class of interpretability methods that aim to understand the importance of a representation, token, or neuron by erasing it and recording the resulting effect on model prediction @xcite @xcite . although the shapley value technically falls under this class, most erasure-based methods only remove one entitythe one whose importance they want to estimate -and this only takes two forward passes, compared to o(2 n ) passes for the shapley value. since only one entity is erased, this simpler group of erasurebased methods is called leave-one-out (jain and wallace, 2019; abnar and zuidema, 2020). we show in this section that leave-one-out values are not shapley values, except in the degenerate case. proposition 3. if ∃ @xmath5, then there is no tu-game (n, v) for which leave-one-out values are shapley values. proof. let the leave-one-out value of player i be denoted by loo i (v). let r denote any permutation of n where p r [:i] = n \ {i}. by definition, by our assumption, the first term is non-zero, so there is no equivalence with loo i (v). in practice, this assumption is almost always satisfied. note that leave-one-out tells us very little about player importance for discrete payoff functions. for example, if the payoff were the correctness (i.e., 1 if correct and 0 otherwise), then the importance of a player would be binary: it would either be critically important to prediction or totally irrelevant. this provides an incomplete picture -while there is enough redundancy in bert-based models to tolerate some missing embeddings, this does not mean those embeddings are of no importance @xcite @xcite . for example, if two representations played a critical and identical role in a predictionbut only one was necessary -then leave-one-out would assign each a value of zero, despite both being important. in contrast, the shapley value of both players would be non-zero and identical. ## applications because shapley values have many useful applications, attentions flows -and any other score that meets the criteria for a shapley value -have many useful applications as well: however, what if we wanted to understand the role of entire groups of tokens rather than individual ones? for most interpretability methods, there is no canonical way to aggregate scores across multiple units -we cannot necessarily add the raw attention scores of two tokens, since the usefulness of one may depend on the other. if we used a method that provided shapley values, we could easily redefine a "player" to be a group of tokens, such that all tokens in the same player group would simultaneously be included or excluded from a coalition. ## limitations and future work because shapley values -and by extension, attention flows -have many theoretical guarantees that are axioms of faithful interpretation, we encourage nlp practitioners to provide attention flow-based explanations alongside more traditional ones. this is not without limitations, however. as proven in proposition 2, this equivalence only holds for a specific payoff function -the total flow through a layer -which is reflective of model confidence but not of the prediction correctness. but why do we need attention flows at all if, in theory, shapley values can be calculated for any arbitrary player set and payoff function? while this is true in theory, because of the combinatorial calculation (1), it is computationally intractable in most cases. while it is possible to take a monte carlo estimate (2), in practice the bounds can be quite loose @xcite . finding tu-games for which the shapley value can be calculated exactly in polynomial time -as with attention flow --is an important line of future work. these explanations may come with trade-offs: for example, shap is a kind of shapley value that assumes contributions are linear (i.e., a coalition can't be greater than the sum of its parts), which makes it much faster to calculate but restricts the set of possible payoff functions @xcite . still, such methods will be critical to providing explanations that are both fast and faithful.