The Importance of Parameters in Ranking Functions

The SHAP score [23] is an instantiation of the Shapley value that, in turn, is used to attribute a share to each player in a cooperative game, where each coalition (set of players) gains some utility [31]. The Shapley value, named after its inventor, is unique up to some axioms of rationality (e.g., the sum of shares adds up to the utility of the entire set) [31, 28] and, besides applications in a plethora of domains, has been used for explanations in data-centric fields such as Machine Learning [23, 11, 29], IR [9, 19], and databases [21, 6, 10]. The SHAP score was originally proposed for the purpose of explaining machine-learned models, and particularly attributing responsibility for the outcome of the model to the feature values of a particular instance [23, 20].

Specifically, SHAP is the Shapley value in the cooperative game where the feature values are the players, and the utility of a coalition $C$ is the expected effect (model’s output) of the instance where the feature values of $C$ are used and the rest chosen randomly. In the framework of Grohe et al. [18], the parameter values play the same role that feature values play in the application of SHAP to machine-learning explanations [23, 20] and that feature values play in the application of SHAP to value-based explanations of ranking [26, 9]. Moreover, the Shapley value has recently been used in function-based explanations [19].

Connecting to this work, consider a particular parameterized ranking function, along with a particular choice of values for its parameters. These define a ranking over the given a set of records. To apply the SHAP score, two additional components need to be determined. The first is a distribution from which parameter choices are assumed to be drawn. The second is an effect function that determines how different the ranking obtained from a specific (random) choice of parameters is from the base ranking with the original choice of parameters. The effect function captures different interpretations of what Heuss et al. [19] refer to as “listwise feature attribution.” Similarly to the study of Grohe et al. [18], we restrict the discussion to simple distributions of parameters, namely finite and probabilistically independent parameters (i.e., “fully factorized” distributions [36]).

From the computational perspective, the SHAP score entails an expectation (w.r.t. a random choice of players) over an expectation (over the random parameter choices). Nevertheless, it was shown by Grohe et al. [18] that the SHAP score can also be viewed as a single expectation over an efficiently samplable space; therefore, the SHAP score of a parameter can be computed in polynomial time via sampling if we settle for a randomized additive approximation (FPRAS), under the mild assumption that the effect function is computable in polynomial time. This technique allows additive approximations also for more general classes of probability distributions, including fully factorized continuous distributions that allow efficient sampling. Moreover, if we make a data complexity assumption of a fixed number of parameters, then the SHAP score can be computed in polynomial time via an explicit enumeration of the probability space. We investigate the ability to compute the SHAP score exactly (and deterministically), for a given (non-fixed) number of parameters, in polynomial time. Van den Broeck et al. [36] have established that there are polynomial-time reductions in both directions between the computation of the SHAP score and the computation of the expected effect, which is arguably a simpler notion. Hence, following their result, we focus mainly on the expected effect throughout the paper.

Our study considers a variety of basic ranking functions and effect functions. For ranking, we consider the score functions of $\mathrm{𝖲𝗎𝗆}$, $\mathrm{𝖬𝗂𝗇}$, and $\mathrm{𝖬𝖺𝗑}$, and the lexicographic ordering (descending or ascending). In all of these functions, the parameters are coefficients (weights) over the record attributes. We view the dataset simply as a matrix (where every row corresponds to a record), and the parameters as per-column multiplicative weights. For the effects, we consider three types: global measures determine an effect over the entire ranking, top-$k$ measures determine the impact on the set of top-$k$ answers, and local measures determine the impact on a single record. The global measures we consider are standard distances between permutations [27, 5], and specifically Kendall’s tau, maximum displacement, and Hamming distances between the random ranking (due to the random choice of parameters) and the base ranking. The top-$k$ measures include the symmetric difference between the top-$k$ sets (for the base and random rankings) and the binary indicator of whether there is any difference between the top-$k$ sets. The local measures include the change in the record’s position and the change in its status of membership in the set of top-$k$ answers. A detailed example is presented at the end of Section 3.

We begin with algorithms for a simpler task: given two records $r_1$ and $r_2$, compute the probability (for randomly chosen parameters) that $r_1$ precedes $r_2$ in the ranking. This problem is tractable for all the ranking functions we consider, while for $\mathrm{𝖲𝗎𝗆}$ we make the necessary assumption that the numbers are in unary representation (as the problem is FP^#P-hard¹¹1Recall that FP^#P is the class of functions computable in polynomial time using an oracle to some function in #P. A function $F$ is FP^#P-hard if there is a polynomial-time Turing reduction from every function in FP^#P to $F$. Such a problem is at least as hard as every problem in the polynomial hierarchy [34]. for the binary representation). Our results (summarized in Table 1) show that, in general, this pairwise case suffices for the tractability of some of the effect functions, namely Kendall’s tau and the position and top-$k$ membership of a row for small $k$; for the rest, we prove hardness results. We also consider the case where the number of records is bounded, thus, we have a small number of competitors. There, we prove that all problems become tractable, again with the exception of $\mathrm{𝖲𝗎𝗆}$ with binary numeric representation.

Finally, we consider another variation of a function-based explanation for ranking, now parameter-free. The goal is to compute the contribution of whole columns (attributes) to the ranking. More precisely, we consider the Shapley value of the cooperative game where the players are the columns, and the utility of a set of columns is the effect of the ranking obtained by considering only the columns in the set, while ignoring the rest. This task has been presented by Heuss et al. [19] where they refer to the action of ignoring a column as “masking the feature vector,” yet with no complexity analysis. We show that this problem reduces in polynomial time to the problem in the focus of this paper, namely computing the SHAP score of parameter choices. Hence, our algorithms for the SHAP score of parameters can be used for the Shapley value of columns. Moreover, we show that the hard cases of computing the SHAP scores are hard already for the Shapley value of columns.

We begin with preliminary definitions in the next section. In Section 3, we describe the formal framework and computational problems that we study, namely the SHAP score of parameters, the expected effect, and the Shapley value of columns. We give algorithms for the expectation in Section 4 and establish lower bounds in Section 5. Finally, we discuss extensions to the Shapley value of columns in Section 6, and conclude in Section 7. For space limitations, some of the proofs are given in the archive version of this paper [33].

For a natural number $n$, we denote by $[n]$ the set $\{1,\mathrm{\dots },n\}$, and by ${𝒮}_n$ the set of permutations over $[n]$ (i.e., bijective functions $\pi :[n]\to [n]$). By ${\pi }_{\mathrm{𝗂𝖽}}$ we denote the identity permutation defined by ${\pi }_{\mathrm{𝗂𝖽}}(i)=i$ for all $i\in [n]$. By $𝒮$ we denote the set of all permutations, that is, $𝒮≔{\cup }_n{𝒮}_n$. We denote by ${ℳ}^{n\times m}$ the set of all $n\times m$ matrices, over the rational numbers, with $n$ rows and $m$ columns, and by $ℳ$ the set of all matrices of all dimensions (i.e., $ℳ≔{\cup }_{n,m}{ℳ}^{n\times m}$). If $𝐌\in {ℳ}^{n\times m}$ and $C\subseteq \{1,\mathrm{\dots },m\}$ represents a set of columns, then we denote by ${𝐌|}_C$ the $n\times |C|$ matrix obtained from $𝐌$ by removing all columns except those in $C$. In other words, ${𝐌|}_C$ is the projection of $𝐌$ on $C$ under bag semantics. We may refer to a row of a matrix as a tuple. We denote such a row (and every numeric vector) $𝐯$ in boldface and its $j$th entry with $𝐯[j]$.

Computation-wise, we assume every number is represented as a pair $(a,b)$, standing for the rational number $a/b$, where $a$ and $b$ are integers in a binary representation. When we refer to a unary representation, we mean an integer $a$ encoded as a string of length $a$.

By a ranking function we refer to a function $r:ℳ\to 𝒮$ that maps every matrix $𝐌\in {ℳ}^{n\times m}$ to a permutation in ${𝒮}_n$; hence, $r$ ranks the rows of its input matrix $𝐌$. Specifically, we will focus on several ranking functions $r$:

• $\mathrm{■}$

  Ranking by decreasing/increasing score of a row $(a_1,\mathrm{\dots },a_m)$, with the score being the sum of the $a_j$, denoted $\mathrm{𝖲𝗎𝗆}$, the maximum among the $a_j$, denoted $\mathrm{𝖬𝖺𝗑}$, or the minimum among the $a_j$, denoted $\mathrm{𝖬𝗂𝗇}$. For each scoring function $s$, we denote by $r_s^{\mathrm{𝖽𝗌𝖼}}$ and $r_s^{\mathrm{𝖺𝗌𝖼}}$ the rankings by decreasing and increasing $s$, respectively. For example, we have , meaning that the $i$th row ${𝐭}_i$ precedes the $j$th row ${𝐭}_j$, whenever $s({𝐭}_i)>s({𝐭}_j)$.

• $\mathrm{■}$

  Ranking by the lexicographic ordering (left to right) over the rows, denoted $r_{\mathrm{𝖫𝖾𝗑}}$.

In our analysis, the direction of the ranking with respect to the score (increasing/decreasing) is important for ranking by $\mathrm{𝖬𝗂𝗇}$ and $\mathrm{𝖬𝖺𝗑}$, as shown in Table 1. This direction is not important for ranking by $\mathrm{𝖲𝗎𝗆}$ since we can switch between the directions by multiplying the entries by a negative number (or subtracting each value from the maximum value in the matrix); hence, we simply write $r_{\mathrm{𝖲𝗎𝗆}}$ as standing for $r_{\mathrm{𝖲𝗎𝗆}}^{\mathrm{𝖺𝗌𝖼}}$ (since $r_{\mathrm{𝖲𝗎𝗆}}^{\mathrm{𝖽𝗌𝖼}}$ is equivalent). In the lexicographic order, we assume for the same reason that the order of each column is ascending (i.e., lower numbers precede higher numbers). Also for the same, we will not consider ranking by $\mathrm{𝖬𝗂𝗇}$ explicitly since it is the same as ranking by $\mathrm{𝖬𝖺𝗑}$ of the negated matrix in reversed direction.

For the framework to be well-defined, we need to handle tie-breaking. For that, we will use the ordering by the row indices; that is, if the rows $i$ and $i^{\prime }$ are tied by the ordering and , then we give precedence to the $i$th row.

A cooperative game is a pair $(P,\nu )$ where $P$ is a finite set of players and $\nu :2^P\to ℝ$ is a utility function that associates with every coalition $C\subseteq P$ a value $\nu (C)$, so that $\nu (\mathrm{\varnothing })=0$. The Shapley value of a player $p\in P$ is defined by the following formula [28, 31].

Intuitively, we consider the situation where we select players iteratively without replacement, starting with the empty set; the Shapley value of a player $p\in P$ is the mean increase in utility when adding $p$.

Let $f:D^m\to ℝ$ be an $m$-ary function over some domain $D$. Let $\mathrm{\Pi }$ be a discrete distribution over $D^m$, and let $𝐰=(w_1,\mathrm{\dots },w_m)$ be a tuple from $\mathrm{\Pi }$ with a nonzero probability. For $j=1,\mathrm{\dots },m$, the SHAP score of $j$ with respect to (w.r.t.) $𝐰$, denoted $\text{Shap}(j,f,𝐰)$, is the value $\mathrm{Shapley}(j,\nu )$ for the cooperative game $(P,\nu )$ defined as follows [23].

• $\mathrm{■}$

  $P≔\{1,\mathrm{\dots },m\}$;

• $\mathrm{■}$

  $\nu (C)≔{𝔼}_{𝐮\sim \mathrm{\Pi }}\left[f(𝐮)\mid u_{\mathrm{\ell }}=w_{\mathrm{\ell }}\text{ for all }\mathrm{\ell }\in C\right]$.

That is, the utility of a subset $C$ of parameters is the expectation of $f$ over the distribution $\mathrm{\Pi }$, conditioned on every parameter in $C$ having its specific value from $𝐰$.

We are given a matrix $𝐌$ and a ranking function $r$ with original order ${\pi }_0≔r(𝐌)$. As a result of applying the ranking function with different weights on the columns (or only on a subset of columns), we get a different permutation $\pi$. We will focus on three classes of effect functions:

• $\mathrm{■}$

  Global perspective: How far is $\pi$ from the original permutation? We can use several notions of distance between permutations. We give here three conventional ones, where the first two were used for ranking explanation in the RankSHAP work [9].

  • –

    Kendall’s tau: determines the number of pairwise disagreements (swaps) between $\pi$ and the original order. This effect function has the range $[\frac{n(n-1)}{2}]$.

  • –

    Maximum Displacement (MD) distance: $e_{\mathrm{𝗆𝖽}}(\pi )≔{\max }_{1\le i\le n}|\pi (i)-{\pi }_0(i)|$ is the maximum difference of an item’s position between the two permutations. This difference is a number in $[n-1]$.

  • –

    Hamming distance: $e_{\mathrm{𝖧𝖺𝗆}}(\pi )≔{\sum }_{1\le i\le n}{\mathrm{𝟙}}_{\pi (i)\ne {\pi }_0(i)}$ determines the number of positions where the tuple is different between the original and permuted orders. It can attain values in $[n]$.

• $\mathrm{■}$

  Top-$k$ perspective: What is the impact on the set of top-$k$ answers? For that, let $T=\{{\pi }^{-1}(1),\mathrm{\dots },{\pi }^{-1}(k)\}$ and $T_0=\{{\pi }_0^{-1}(1),\mathrm{\dots },{\pi }_0^{-1}(k)\}$ we will consider two functions.

  • –

    Top-$k$ difference: $e_{\mathrm{\Delta }}^k(\pi )≔|T\cup T_0|-|T\cap T_0|$ is the size of the symmetric difference between the sets of top-$k$ elements.

  • –

    Top-$k$ any-change: $e_{\mathrm{𝖺𝗇𝗒}}^k(\pi )≔{\mathrm{𝟙}}_{T\ne T_0}$ determines whether there is any change in the top-$k$ elements.

• $\mathrm{■}$

  Local perspective: What is the impact on a specific row $i$? We will consider two functions:

  • –

    Position: $e_{\mathrm{𝗉𝗈𝗌}}(i,\pi )≔\pi (i)-{\pi }_0(i)$ is the change of position of the $i$th row and is in the range $\{-n+1,\mathrm{\dots },n-1\}$.

  • –

    Top-$k$ membership: $e_{\mathrm{𝗍𝗈𝗉}}^k(i,\pi )≔{\mathrm{𝟙}}_{\pi (i)\le k}-{\mathrm{𝟙}}_{{\pi }_0(i)\le k}$ determines how the $i$th row changes its membership in the top-$k$ tuples. Its range is either $\{-1,0\}$ or $\{0,1\}$.

In the analysis we conduct in the remainder of this paper, we focus on four effects: Kendall’s tau, MD, position, and top-$k$ membership. The complexity results for the Hamming distance are the same as those of MD. The complexity results for the impacts of the top-$k$ perspective are the same as the top-$k$ membership. Details are in the archive version [33].

Next, we assume that the columns of the input matrix $𝐌$ are weighted, and the goal is to compute the SHAP score of a given weight. To make it precise, we assume that our data is a pair $(𝐌,𝐰)$, where $𝐌\in {ℳ}^{n\times m}$ and $𝐰=(w_1,\mathrm{\dots },w_m)\in {\mathbb{Q}}^m$ is a sequence of column weights. The pair $(𝐌,𝐰)$ represents the pair $𝐌\circ 𝐰$, which is the matrix ${𝐌}^{\prime }$ obtained by multiplying the $j$th column by $w_i$ for $i=1,\mathrm{\dots },m$; that is, we apply element-wise multiplication by $𝐰$ to each row of $𝐌$, or, in other words, ${𝐌}^{\prime }=\mathrm{𝖽𝗂𝖺𝗀}(𝐰)\cdot 𝐌$ where $\mathrm{𝖽𝗂𝖺𝗀}(𝐰)$ is the diagonal matrix whose diagonal elements are given by $𝐰$.

We will also assume that, in addition to $𝐌$ and $𝐰$, we are given a finite probability distribution $\mathrm{\Pi }$ over ${\mathbb{Q}}^m$. We restrict our complexity study to column-wise independent distributions (i.e., fully factorized distributions [36]), hence, $\mathrm{\Pi }$ is represented by finite distributions ${\mathrm{\Pi }}_1,\mathrm{\dots },{\mathrm{\Pi }}_m$ over $\mathbb{Q}$ for each weight parameter, each distribution given as a list of value-probability-pairs; the total number of such pairs is denoted by $|\mathrm{\Pi }|$.

Let $r$ be a ranking function and $e$ an effect function. Given the pair $(𝐌,𝐰)$ and a column number $j$, our goal is to compute $\text{Shap}(j,f,𝐰)$, where $f(𝐮)≔-e(r(𝐌\circ 𝐮))$, that is, the inverse of the effect on the ranking of replacing the weights of $𝐰$ with those of $𝐮$. We denote this value by $\text{Shap}⟨r,e⟩(j,𝐌,𝐰,\mathrm{\Pi })$. The reason for the inverse (using minus) is that the closer we are to the original ranking order ${\pi }_0$ (i.e., the less effect), the higher we deem the contribution to the the actual ${\pi }_0$ in place.

In this and the other problems we consider, when the effect function $e$ is local, the input also includes the row number $i$ of the effect. In addition, when $e$ is the top-$k$ membership, then the input also includes $k$ (unless we explicitly state that $k$ is assumed to be fixed).

It has been established by Van den Broeck et al. [36] that, for finite and probabilistically independent parameters, calculating the SHAP score is computationally equivalent to calculating the expected value of $f$, which is arguably simpler to handle.

Hence, we will also study the following problem.

Let $r$ be a ranking function and $e$ an effect function. Given a matrix $𝐌\in {ℳ}^{n\times m}$ and a column number $j\in \{1,\mathrm{\dots },m\}$, the Shapley value of the $j$th column is defined as $\mathrm{Shapley}(i,\nu )$ for the game $(P,\nu )$ defined as follows:

• $\mathrm{■}$

  $P≔\{1,\mathrm{\dots },m\}$.

• $\mathrm{■}$

  $\nu (C)≔-e(r({𝐌|}_C))$, that is, the inverse of the effect on the ranking we obtain by applying $r$ to only the columns of $C$ (with the same rationale for inverse as SHAP).²²2The ranking function $r$ applied to the empty set of columns always yields the matrix order ${\pi }_{\mathrm{𝗂𝖽}}$ since all tuples of ${𝐌|}_{\mathrm{\varnothing }}$ are identical. In particular, this definition does not depend on the value of the scoring function on the empty set.

We denote this value by $\mathrm{Shapley}⟨r,e⟩(j,𝐌)$.

Before moving to exact algorithms, we want to emphasize that each of the three problems $\mathrm{𝖤𝖷𝖯}⟨r,e⟩$, $\mathrm{𝖲𝖧𝖠𝖯}⟨r,e⟩$, and $\mathrm{𝖲𝗁𝖺𝗉𝗅𝖾𝗒}⟨r,e⟩$ can be efficiently additively approximated whenever $r$ and $e$ can be computed in polynomial time and the range of $e$ is polynomial in the number of rows. This is the case for all ranking and effect functions introduced in this section. As we will show in Section 5.2, this is not always the case for multiplicative approximations. The additive approximation can be done via basic Monte-Carlo-sampling since all three problems can be expressed as the expectation of a random variable over a probability space that allows efficient sampling: $\mathrm{\Pi }$ for $\mathrm{𝖤𝖷𝖯}⟨r,e⟩$, ${𝒮}_m$ for $\mathrm{𝖲𝗁𝖺𝗉𝗅𝖾𝗒}⟨r,e⟩$, and $\mathrm{\Pi }\times {𝒮}_m$ for $\mathrm{𝖲𝖧𝖠𝖯}⟨r,e⟩$. We can use this insight for efficient additive approximations also in the case of not necessarily independent discrete parameter distributions under very mild assumptions (see [18]) or independent continuous parameter distributions that can be sampled efficiently.³³3For continuous distributions, the definition of the SHAP score via conditional representations is not well-defined since the set we condition on has measure $0$. In the case of independent distributions, we can derive a compatible definition via disintegration, that is, fixing the parameters in $C$ to their reference values and choosing the others at random. This simple idea was further improved to allow for faster additive approximations (e.g. [7]). Hence, our framework could be applied in practice, even in cases where we show that exact computation is hard.

Before we start our complexity analysis, let us first look at a small example that demonstrates the framework in detail. Consider the following matrix $𝐌$:

Assume that we rank the row by $\mathrm{𝖲𝗎𝗆}$ in descending order with a scoring parameter $𝐮\in \{1,2\}\times \{1,2\}$. We want to measure the impact of choosing the weight vector $𝐰=(1,1)$ among the possible choices for $𝐮$ (where we assume a uniform distribution).

To measure this, we first determine the rankings for each $𝐮$: For $𝐮=𝐰=(1,1)$, the scores are $(46,43,40,39)$, so we obtain the ranking $(1,2,3,4)$. In the same way, we obtain $(4,1,2,3)$ for $𝐮=(1,2)$, $(3,2,1,4)$ for $𝐮=(2,1)$, and again $(1,2,3,4)$ for $𝐮=(2,2)$.

Now, we need to choose an effect function $e$ that measures the distance between two rankings. We will look at the Kendall’s tau distance $e_{𝗄\tau }$ and the position of the fourth row $e_{\mathrm{𝗉𝗈𝗌}}(4,\pi )$. We observe that $d_{𝗄\tau }((1,2,3,4),(4,1,2,3))=d_{𝗄\tau }((1,2,3,4),(3,2,1,4))=3$ and that the row $4$ is in the last position of all the rankings except for $(4,1,2,3)$ where it is first.

For the SHAP score calculation, the valuation of a set of columns $C$ is the expected value of the negated effect function when we fix the parameter value for the columns in $C$ to the value of $𝐰$ and choose the rest at random. For example, for $C=\{2\}$, we obtain for $e=e_{𝗄\tau }$

and for $e=e_{\mathrm{𝗉𝗈𝗌}}(4,\pi )$, we obtain ${\nu }_{\mathrm{𝗉𝗈𝗌}(4)}(\{2\})=-\frac{(4-4)+(4-4)}{2}=0$. Calculating the valuation $\nu$ of every $C\subseteq \{1,2\}$ gives the following. For $e=e_{𝗄\tau }$, we obtain $\text{Shap}(1)=\frac{1}{2}\left({\nu }_{𝗄\tau }(\{1,2\})-{\nu }_{𝗄\tau }(\{2\})\right)+\frac{1}{2}\left({\nu }_{𝗄\tau }(\{2\})-{\nu }_{𝗄\tau }(\mathrm{\varnothing })\right)=\frac{1}{2}\left(0-(-\frac{3}{2})\right)+\frac{1}{2}\left(-\frac{3}{2}-(-\frac{3}{2})\right)=\frac{3}{4}$ and $\text{Shap}(2)=\frac{3}{4}$ as well, so both parameter choices have the same impact w.r.t. global changes in the ranking measured by $d_{𝗄\tau }$. This reflects the symmetry in the 4th column of table above. In contrast, for $e=e_{\mathrm{𝗉𝗈𝗌}}(4,\pi )$, we obtain $\text{Shap}(1)=\frac{3}{8}$ and $\text{Shap}(2)=-\frac{9}{8}$. This matches our intuition that fixing the second weight to $1$ is bad for the ranking of row $4$, since the only good weighting vector for row $4$ is $𝐮=(1,2)$.

In the remainder of the paper, we study the complexity of exactly solving the computational problems we defined in this section.