Axiomatic attribution for multilinear functions

By Yi Sun, Mukund Sundararajan. 2011

31 citations recorded by the source corpus.

We study the attribution problem. That is, given a real-valued characteristic function f of n variables and initial and final values r and s for its independent variables, our objective is to divide the responsibility for the change f(s) - f(r) in the characteristic function among each of its independent variables. We call these assigned responsibilities attributions, and we would like the attributions to form a complete partition of the total change. When r=0, the attribution problem coincides with a standard cost sharing model from the social choice literature (cf. Moulin [2]), where the characteristic function is the cost function, the independent variables are the demands of the agents, and the attributions are cost shares for the agents. We follow the cost sharing literature in identifying good attribution methods axiomatically (for a classical example, see Friedman and Moulin [1]). We consider: Additivity -- attributions are additive in the characteristic function, Dummy -- if the characteristic function does not depend on a variable, then its attribution is zero, and Affine Scale Invariance -- attributions are invariant under simultaneous affine transformation of the characteristic function and the variables. First, we show that when the characteristic function is the sum of a multilinear function and an additively separable one, every attribution method satisfying these axioms is a random order method. Intuitively, a multilinear function is determined by its values on the vertices of a hypercube, so its attributions should depend on these values alone, leading to the space of random order methods. The proof proceeds by using this idea to count dimensions. Second, in our main result, we show that there is a unique attribution method satisfying these axioms and Anonymity (which requires attributions to be invariant under relabeling of the variables) if and only if the characteristic function is the sum of a multilinear function and an additively separable one. The main technical tool is the use of Stokes' Theorem to compare attribution methods. The resulting method coincides with the classical Aumann-Shapley and Shapley-Shubik methods, and thus we term it the Aumann-Shapley-Shubik method. When the characteristic function is multilinear, our result prescribes this method for use; to this end, we provide a computationally efficient implementation. Together, our results single out the class of multilinear characteristic functions as a particularly nice one for attribution problems. We give several examples of natural attribution problems where such functions arise, including pay-per-click advertising, website traffic analysis, portfolio analysis, and performance analysis of sports teams.

Subfields: Economics and Econometrics, General Decision Sciences, Safety Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In General Decision Sciences

In Safety Research

Citations in the corpus

Improved protein structure refinement guided by deep learning based accuracy estimation (2020, background): “We are aware that more sophisticated feature attribution methods for deep networks exist (30); however, these methods attribute importance scores to features per output per sample.”
Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation (2019, methodology): “This axiom, also called anonymity (Sun & Sundararajan, 2011), is arguably a desirable property for any attribution method: if two variables play the exact same role in the DNN, they should receive the same attribution.”
End-to-end lung cancer screening with three-dimensional deep learning on low-dose chest computed tomography (2019, methodology): “Further analysis of the model’s results included examining attri-bution regions computed with integrated gradients 35 , using three radiologists with an average of 23 years’ clinical experience (range 10–38 years).”
Gradients of Counterfactuals (2016, methodology): “We note that these path integrals of gradients have been used to perform attribution in the context of small non-linear polynomials (Sun & Sundararajan (2011)), and also within the cost-sharing literature in economics where function at hand is a cost function that models the cost of a project as a…”
The many Shapley values for model explanation (2019, methodology): “model a feature’s absence using its value in the baseline. We call this the Baseline Shapley (BShap) approach. We denote BShap attribution by bs i(x;x0;f). Variants of this approach have been used by [18, 2, 10]. 2.4 Random Baseline Shapley (RBShap) This approach is a variant of BShap that takes thr”