# Linear TreeShap

Peng Yu1,2,4 Chao Xu1 Albert Bifet2 Jesse Read3
1 University of Electronic Science and Technology of China
2 Télécom ParisTech 3 Ecole polytechnique 4 Shopify
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Decision trees are well-known due to their ease of interpretability. To
improve accuracy, we need to grow deep trees or ensembles of trees. These are
hard to interpret, offsetting their original benefits. Shapley values have
recently become a popular way to explain the predictions of tree-based machine
learning models. It provides a linear weighting to features independent of the
tree structure. The rise in popularity is mainly due to TreeShap, which solves
a general exponential complexity problem in polynomial time. Following
extensive adoption in the industry, more efficient algorithms are required.
This paper presents a more efficient and straightforward algorithm: Linear
TreeShap. Like TreeShap, Linear TreeShap is exact and requires the same amount
of memory.

##  1 Introduction

Machine learning in the industry has played more and more critical roles. For
both business and fairness purposes, the need for explainability has been
increasing dramatically. As one of the most popular machine learning models,
the tree-based model attracted much attention. Several methods were developed
to improve the interpretability of complex tree models, such as sampling-based
local explanation model LIME[9], game-theoretical based Shapley value[10],
etc. Shapley value gained particular interest due to both local and globally
consistent and efficient implementation: TreeShap[5]. With the broad adoption
of Shapley value, the industry has been seeking a much more efficient
implementation. Various methods like GPUTreeShap[6] and FastTreeShap[12] were
proposed to speed up TreeShap. GPUTreeShap primarily focuses on utilizing GPU
to perform efficient parallelization. And FastTreeShap improves the efficiency
of TreeShap by utilizing caching. All of them are empirical approaches lacking
a mathematical foundation and are thus making them hard to understand.

We solve the exact Shapley value computing problem based on polynomial
arithmetic. By utilizing the properties of polynomials, our proposed algorithm
Linear TreeShap can compute the exact Shapley value in linear time. And there
is no compromise in memory utilization.

###  1.1 Contrast with previous result

We compare the running time of our algorithm with previous results for a
single tree in Table 1, since all current algorithms for ensemble of trees are
applying the same algorithm to each tree individually.

Let $S$ be the number of samples to be explained, $N$ the number of features,
$L$ the number of leaves in the tree, and $D$ is the maximum depth of the
tree. For simplicity, we assume every feature is used in the tree, and
therefore $N=O(L)$. Also, $D\leq L$.

Algorithm | Time Complexity | Space Complexity
---|---|---
Original TreeSHAP [5] | $O(SLD^{2})$ | $O(D^{2}+N)$
Fast TreeSHAP v1 [12] | $O(SLD^{2})$ | $O(D^{2}+N)$
Fast TreeSHAP v2 [12] | $O(L2^{D}D+SLD)$ | $O(L2^{D})$
Linear TreeSHAP | $O(SLD)$ | $O(D^{2}+N)$

Table 1: Comparison of both computational and space complexity

pttemperaturept0.5 rain(D)$\leq$ 19pt$w$:0.5ptcloudyptwind speedpt0.4 rain
(C)$w$: 0.7$\leq 8$pt0.6 rain (B)$w$: 0.3$>8$$w$:0.4nopt0.7 rain
(A)pt$w$:0.6yes$w$:0.5$>19$

Figure 1: An example decision tree $T_{f}$ shows chances of rain

##  2 Methodology

###  2.1 Notation & Background

Elementary symmetry polynomials are widely used in our paper. $\mathbb{R}[x]$
denotes the set of polynomials with coefficient in $\mathbb{R}$.
$\mathbb{R}[x]_{d}$ are polynomials of degree no larger than $d$. We use
$\odot$ for polynomial multiplication. For two polynomials $a$ and $b$,
$\left\lfloor\frac{a}{b}\right\rfloor$ is the quotient of the polynomial
division $a/b$.

For two vectors $x,y\in\mathbb{R}^{d}$, $\langle x,y\rangle$ is the inner
product of $x$ and $y$. We abuse the notation, so when a polynomial appears in
the inner product, we take it to mean the coefficient vector of the
polynomial. Namely, if $p,q$ are both polynomials of the same degree, then
$\langle p,q\rangle$ is the inner product of their coefficient vectors. We use
$\cdot$ for matrix multiplication.

We refer to $x\in X\subset\mathbb{R}^{m}$ as an instance and
$f:X\to\mathbb{R}$ as the fitted tree model in a supervised learning task.
Here, $m$ denotes the number of all features, $M$ is the set of all features,
and $|.|$ is the cardinality operation, namely $|M|=m$. We denote $x[i]$ as
the value of feature $i$ of instance $x$.

We have to start with some common terminologies because our algorithm is
closely involved with trees. A rooted tree $T=(V,E)$ is a directed tree where
each edge is oriented away from the root $r\in V$. For each node $v$, $P_{v}$
is the root to $v$ path, i.e. the set of edges from the root to $v$. $L(v)$ is
the set of leaves reachable from $v$. $L(T)=L(r)$ is the set of leaves of $T$.
$T$ is a full binary tree if every non-leaf node has two children. If an edge
$e$ goes from $u$ to $v$, then $u$ and $v$ are the tail and head of $e$,
respectively. We write $h(e)$ for the head of $e$.

A tree is weighted, if there is an edge weight $w_{e}$ for each edge $e$. It
is a labeled tree if each edge also has a label $\ell_{e}$. For a labeled tree
$T$, let $E_{i}$ be all the edges of the tree with label $i$. Similarly,
define $P_{i,v}=P_{v}\cap E_{i}$, the set of edges in the root to $v$ path
that has label $i$. The last edge of any subset of a path is the edge furthest
away from the root.

For our purpose, a decision tree is a weighted labeled rooted full binary
tree. There is a corresponding decision tree for the fitted tree model
$T_{f}$. The internal nodes of the tree are called the decision nodes, and the
leaves are called the end nodes. Every decision node has a label of feature
$i$, and every end node contains a prediction $v$. The label of each edge is
the feature of the head node of the edge. We will call the label on the edge
of the feature. Every edge $e$ contains weight $w_{e}$ that is the conditional
probability based on associated splitting criteria during training.

When predicting a given instance, $x$, decision tree model $f$ sends the
instance to one of its leaves according to splitting criteria. We draw an
example decision tree in Fig 1. Each leaf node is labeled with id and
prediction value. Every decision node is labeled with the feature. We also
associate each edge with conditional probability $w$ and splitting criteria of
features in the parenting node.

To represent the marginal effect, we use $f_{S}(x):X\to\mathbb{R},S\subseteq
M$ to denote the prediction of instance $x$ of the fitted tree model using
only the features in _active set_ $S$, and treat the rest of features of
instance $x$ as missing. Using this representation, the default prediction
$f(x)$ is a shorthand for $f_{M}(x)$.

The _Shapley value_ of a decision tree model $f$ is the function
$\phi(f,i):X\to\mathbb{R}$,

$\begin{split}\phi(f,i)(x)=\frac{1}{|M|}\sum_{S\subseteq
M\setminus\\{i\\}}\frac{1}{\binom{|M|-1}{|S|}}f_{S\cup\\{i\\}}(x)-f_{S}(x).\end{split}$
(1)

The Shapley value $\phi(f,i)(x)$ quantifies the marginal contribution of
feature $i$ in the tree model $f$ when predicting instance $x$. The problem of
computing the Shapley values is the following algorithmic problem.

The Tree Shapley Value Problem
Input: A decision tree $T_{f}$ for function $f:X\to\mathbb{R}$ over $m$
features, and $x\in X$. Output: The vector
$(\phi(f,1)(x),\ldots,\phi(f,m)(x))$.

Meanwhile, decision nodes cannot split instances with missing feature values.
A common convention is to use conditional expectation. When a decision node
encounters a missing value, it redirects the instance to both children and
returns the weighted sum of both children’s predictions. The weights differ
between decision nodes and are empirical instance proportions during training:
$w_{l},w_{r}$. Here $w_{l}+w_{r}=1$ and $0<w_{l}<1$. A similar approach is
also used in both Treeshap[5], and C4.5 [7] to deal with missing values. Any
instance would result in a single leaf when there is no missing feature. In
contrast, an instance might reach multiple different leaves with a missing
feature.

Here, we use an example instance $x=$(temperature: 20, cloudy: no, wind speed:
6) with tree $f$ in Fig 1 to show the full process of Shapley value computing.
By following the decision nodes of $T_{f}$, the prediction $f(x)$ is leaf $C$:
0.4 chance of raining. Now we compute the importance/Shapley value of feature
(temperature: 18) among $x$ for getting prediction of 0.4 chance of raining.

The importance/Shapley value of feature (temperature: 18) is

$\begin{split}&\phi(f,\textbf{temperature})(x)=\frac{1}{3}(\frac{1}{\binom{2}{2}}(f_{\\{\textbf{temperature,
cloudy, wind speed}\\}}(x)-f_{\\{\textbf{cloudy, wind speed}\\}}(x))\\\
&+\frac{1}{\binom{2}{1}}(f_{\\{\textbf{temperature, wind
speed}\\}}(x)-f_{\\{\textbf{wind speed}\\}}(x)+f_{\\{\textbf{temperature,
cloudy}\\}}(x)-f_{\\{\textbf{cloudy}\\}}(x))\\\
&+\frac{1}{\binom{2}{0}}(f_{\\{\textbf{temperature}\\}}(x)-f_{\emptyset}(x)))\end{split}$

To elaborate more, a term $f_{\\{\textbf{cloudy, wind speed}\\}}(x)$ with
$x=$(temperature: 20, cloudy: no, wind speed: 6) is equivalent to $f($cloudy:
no, wind speed: 6$)$. When traversal first decision node: temperature, value
to current feature is considered as unspecified. We sum over children leaves
with empirical weights and get $0.5\cdot D+0.5\cdot C$ as prediction.

On the other hand, decision tree $f$ can be linearized into decision rules
[8]. A decision rule can be seen as a decision tree with only a single path. A
decision rule $R^{v}:X\to\mathbb{R}$ for a leaf $v$ can be constructed via
starting from root node, following all the conditions along the path to the
leaf $v$. We use $F(R)$ to represent the set of all features specified in
decision rule $R$, namely, $F(R)=\\{i|P_{i,v}\neq\emptyset\\}$.

The linearization of the decision tree $f$ to decision rules is the relation
$f(x)=\sum_{v\in L(T_{f})}R^{v}(x)$. Example tree in Fig 1 can be linearized
into 4 rules:

  1. 1.

$R^{A}$: if (temperature $>$ 19) and (is cloudy) then predict 0.7 chance of
rain else predict 0 chance of rain

  2. 2.

$R^{B}$: if (temperature $>$ 19) and (is not cloudy) and (wind speed $>$ 8)
then predict 0.6 chance of rain else predict 0 chance of rain

  3. 3.

$R^{C}$: if (temperature $>$ 19) and (is not cloudy) and (wind speed $\leq$ 8)
then predict 0.4 chance of rain else predict 0 chance of rain

  4. 4.

$R^{D}$: if (temperature $\leq$ 19) then predict 0.5 chance of rain else
predict 0 chance of rain

For a decision rule $R$, we also introduce _prediction with active set_ $S$,
$R_{S}:X\to\mathbb{R}$. When features are missing, leaf value further weighted
by their conditional probability is provided as the prediction. Here we
introduce the definition recursively. First, we define the prediction of rule
$R$ associated with leaf value $\mathcal{V}$ with empty input:

$\begin{split}R_{\emptyset}^{v}=R_{\emptyset}^{v}(x)=\mathcal{V}\prod_{e\in
P_{v}}w_{e}\end{split}$ (2)

Where $w_{e}$ is the conditional probability/proportion of instances, when
splitting by decision node at the source of edge $e$, the proportion of
instances belong to the current edge. $\mathcal{V}$ is the prediction of the
leaf node $v$ that defines that decision rule.

We say $x\in\pi_{i}(R)$, if $x[i]$ is satisfied by every splitting criteria
concerning feature $i$ in decision rule $R$. For a given instance $x$ and leaf
$v$, we use a new variable $q_{i,v}(x)$ to denote the marginal prediction of
$R^{v}$ when adding feature $i$ to active set $S$.

$\begin{split}q_{i,v}(x):=\begin{cases}\prod_{e\in P_{i,v}}\frac{1}{w_{e}}&x\
\in\pi_{i}(R^{v})\\\ 0&x\ \notin\ \pi_{i}(R^{v})\end{cases}\end{split}$ (3)

The empty product equals $1$, hence if $P_{i,v}=\emptyset$, $q_{i,v}(x)=1$. We
omit the super/subscript $v$ if there is no ambiguity on the leaf node. So,
with $i\notin S$, we can write:

$R_{\\{i\\}\cup S}(x)=q_{i}(x)R_{S}(x)$ (4)

Since $\emptyset$ is a subset of any set $S$, we can get $R_{S}(x)$ via
products of weights:

$R_{S}(x)=R_{\emptyset}\prod_{j\in S}q_{j}(x)$ (5)

With $R_{S}$, $f_{S}$ can also be linearized into the sum of rule predictions:

$f_{S}(x)=\sum_{v\in L(T_{f})}R_{S}^{v}(x).$ (6)

###  2.2 Some special functions and their properties

######  Definition 2.1.

Define the reciprocal binomial polynomial to be
$B_{d}(x)=\sum_{i=0}^{d}{\binom{d}{i}}^{-1}x^{i}$.

######  Definition 2.2.

The function $\psi_{d}:\mathbb{R}[x]_{d}\to\mathbb{R}$ is defined as

$\psi_{d}(A):=\frac{\langle A,B_{d}\rangle}{d+1}.$ (7)

We write $\psi(p)=\psi_{d}(p)$ where $d$ is the degree of $p$.

The function $\psi_{d}$ has two nice properties: additive for same degree
polynomial and ”scale” invariant when multiplying binomial coefficient.

######  Proposition 2.1.

Let $p,q\in\mathbb{R}[x]_{d}$, and $k\in\mathbb{N}$.

  * •

Additivity: $\psi_{d}(p)+\psi_{d}(q)=\psi_{d}(p+q)$.

  * •

Scale Invariant: $\psi(p\odot(1+y)^{k})=\psi(p)$.

###  2.3 Summary polynomials and their relation to Shapley value

Consider we have a function $f$ represented by a decision tree $T_{f}$. We
want to explain a particular sample $x$, therefore in the later sections, we
abuse the notation and let $g$ to mean $g(x)$ whenever $g:X\to\mathbb{R}$, e.g
$q_{i,v}=q_{i,v}(x)$. In order to not confuse the readers, the polynomials we
are constructing always have the formal variable $y$.

Since tree prediction can be linearized into decision rules, and the Shapley
value also has Linearity property, we decompose the Shapley value of a tree as
the sum of the Shapley value of decision rules.

$\begin{split}\phi(f,i)=\sum_{v\in L(T_{f})}\phi(R^{v},i)\end{split}$ (8)

Now, for each decision rule, we define a summary polynomial.

######  Definition 2.3.

For a decision tree $T_{f}$ and an instance $x$. For a decision rule
associated with leaf $v$ in $T_{f}$, the _summary polynomial_ $G_{v}$ is
defined as

$G_{v}(y)=R^{v}_{\emptyset}\prod_{j\in F(R^{v})}(q_{j,v}+y)$ (9)

Next, we study the relationship between the summary polynomial and the Shapley
value of corresponding decision rule.

######  Lemma 2.2.

Let $v$ be a leaf in $T_{f}$, then

$\phi(R^{v},i)=(q_{i,v}-1)\psi\left(\frac{G_{v}}{q_{i,v}+y}\right).$

###### Proof.

Since everything involved in the proof is related to the leaf $v$, we drop $v$
from the super/subscripts for simplicity. First, we simplify the Shapley value
of rule $R$ into:

$\begin{split}\phi(R,i)=\frac{1}{m}\sum_{S\subset
M\setminus\\{i\\}}\frac{1}{\binom{m-1}{|S|}}R_{S\cup\\{i\\}}-R_{S}=\frac{R_{\emptyset}(q_{i}-1)}{m}\sum_{S\subset
M\setminus\\{i\\}}\frac{1}{\binom{m-1}{|S|}}\prod_{j\in S}q_{j}\end{split}$
(10)

When feature $i$ does not appear in $R$, $q_{i}-1$ returns 0, thus Shapley
value on feature $i$ from rule $R$ is 0. Let $|F(R)|=d$, the number of
features in $R$. The Shapley value of $R$ further reduces to:

$\begin{split}\phi(R,i)=\frac{R_{\emptyset}(q_{i}-1)}{d}\sum_{k=0}^{d-1}\frac{1}{\binom{d-1}{k}}\sum_{S\subset
F(R)\setminus\\{i\\}}^{|S|=k}\prod_{j\in S}q_{j}\end{split}$ (11)

We observe that $R_{\emptyset}\sum_{S\subset
F(R)\setminus\\{i\\}}^{|S|=k}\prod_{j\in S}q_{j}$ is precisely the coefficient
of $y^{k}$ in $\frac{G}{q_{i}+y}$.

We obtain the weighted sum of all subsets’ decision rule prediction using the
inner product:

$R_{\emptyset}\sum_{S\subset
F(R)\setminus\\{i\\}}{1}/{\binom{d-1}{|S|}}\sum_{S\subset
F(R)\setminus\\{i\\}}^{|S|=k}\prod_{j\in
S}q_{j}=\langle\frac{G}{q_{i}+y},B_{d-1}\rangle$ (12)

Shapley value for $R$ has a compact form as shown in Eq.13.

$\displaystyle\phi(R,i)$
$\displaystyle=\frac{R_{\emptyset}(q_{i}-1)}{d}\sum_{S\subset
F(R)\setminus\\{i\\}}\frac{1}{\binom{d-1}{|S|}}\prod_{j\in S}q_{j}$ (13)
$\displaystyle=\frac{(q_{i}-1)}{d}\langle\frac{G}{q_{i}+y},B_{d-1}\rangle$
$\displaystyle=(q_{i}-1)\psi\left(\frac{G}{q_{i}+y}\right)$

∎

###  2.4 Computations

Even though we have simplified the Shapley value of a decision rule in a
compact form using polynomials, it is still not friendly in computational
complexity. In particular, the values $q_{i,v}$ are flat aggregated statistics
and do not necessarily share terms in-between different rules. This makes it
difficult to share intermediate results across different rules. To benefit
from the fact that decision rules overlap, we develop an edge-based polynomial
representation.

For every edge $e$ with feature $i$, we use $e^{\uparrow}$ to denote its
closest ancestor edge that shares the same feature. In cases such edge does
not exist, $e^{\uparrow}=\bot$. We also use $x\in\pi_{u}$ to represent the
$x[i]$ is satisfied by all splitting criteria on feature $i$ associated with
all edges in $P_{i,u}$.

$\begin{split}p_{e}:=\begin{cases}\prod_{e^{\prime}\in
P_{i,h(e)}}\frac{1}{w_{e^{\prime}}}&x\ \in\pi_{h(e)}\\\ 0&x\ \notin\
\pi_{h(e)}\end{cases}\end{split}$ (14)

We also define additionally that $p_{\bot}=1$.

If $e$ is the last edge in $P_{i,v}$ then $p_{e}=q_{i,v}$. This is the key to
avoid $q_{i,v}$ completely, and instead switch to $p_{e}$. Our analysis will
make sure that any $p_{e}$ that does not correspond to $q_{i,v}$ for any $v$
and $i$ gets cancelled out.

We show a relation between the Shapley value of a decision rule and the newly
defined $p_{e}$’s.

Consider an operation
$\oplus_{d_{1},d_{2}}:\mathbb{R}[x]_{d_{1}}\times\mathbb{R}[x]_{d_{2}}\to\mathbb{R}[x]_{\max(d_{1},d_{2})}$.
The subscript is omitted when $d_{1},d_{2}$ is implicit.

$G^{1}\oplus G^{2}:=G^{1}+G^{2}\odot(1+y)^{d_{1}-d_{2}},$ (15)

We extend the summary polynomial to all nodes in the tree. Let
$G_{u}=\bigoplus_{v\in L(u)}G^{v}$. Denote $d_{e}$ as the degree of $G_{u}$,
where $h(e)=u$.

######  Proposition 2.3.

Let $v$ be a leaf in $T_{f}$, and $d_{v}$ be the degree of $G_{v}$ then

$\phi(R^{v},i)=\sum_{e\in
P_{i,v}}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\right\rfloor\right)-(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e^{\uparrow}}-d_{v}}}{y+p_{e^{\uparrow}}}\right\rfloor\right).$

###### Proof.

Let $e^{*}$ be the last edge of $P_{i,v}$. We note a few facts.
$p_{e^{*}}=q_{i,v}$, $y+q_{i,v}$ divides $G_{v}$, and the sum is a telescoping
sum. Put them together.

$\displaystyle\sum_{e\in
P_{i,v}}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\right\rfloor\right)-(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e^{\uparrow}}-d_{v}}}{y+p_{e^{\uparrow}}}\right\rfloor\right)$
$\displaystyle=$
$\displaystyle(p_{e^{*}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e^{*}}-d_{v}}}{y+p_{e^{*}}}\right\rfloor\right)$
$\displaystyle=$
$\displaystyle(q_{i,v}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e^{*}}-d_{v}}}{y+q_{i,v}}\right\rfloor\right)$
$\displaystyle=$
$\displaystyle(q_{i,v}-1)\psi\left(\frac{G_{v}}{y+q_{i,v}}\odot(y+1)^{d_{e^{*}}-d_{v}}\right)$
$\displaystyle=$
$\displaystyle(q_{i,v}-1)\psi\left(\frac{G_{v}}{y+q_{i,v}}\right)$
$\displaystyle=$ $\displaystyle\phi(R^{v},i)$

∎

The following theorem establishes the relation between Shapley values, the
summary polynomials at each node, and $p_{e}$ for each edge $e$.

######  Theorem 2.4 (Main).

$\phi(f,i)=\sum_{e\in
E_{i}}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{h(e)}}{y+p_{e}}\right\rfloor\right)-(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{h(e)}\odot(y+1)^{d_{e^{\uparrow}}-d_{e}}}{y+p_{e^{\uparrow}}}\right\rfloor\right)$

###### Proof.

Based on linearity of Shapley Value, $\phi(f,i)=\sum_{v\in
L(T_{f})}\phi(R^{v},i)$.

For each rule $R^{v}$, we can scale their summary polynomial $G_{v}$ to the
degree of $G_{h(e)}$. Based on Proposition 2.3,

$\phi(f,i)=\sum_{v\in L(T_{f})}\sum_{e\in
P_{i,v}}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\right\rfloor\right)-(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{(d_{e}-d_{v})+(d_{e^{\uparrow}}-d_{e})}}{y+p_{e^{\uparrow}}}\right\rfloor\right)$

Observe that for any $(e,v)$ pair, we have $e\in E_{i}$ and $v\in L(h(e))$ if
and only if $v\in L(T_{f})$ and $e\in P_{i,v}$. Hence, can order the summation
by summing through the edges.

$\phi(f,i)=\sum_{e\in E_{i}}\sum_{v\in
L(h(e))}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\right\rfloor\right)-(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{(d_{e}-d_{v})+(d_{e^{\uparrow}}-d_{e})}}{y+p_{e^{\uparrow}}}\right\rfloor\right)$

Observe that at each edge $e$, all summary polynomial $G$ is scaled to the
same degree $d_{e}$. According to Proposition 2.1, we can add the summary
polynomials before evaluate using $\psi(.)$. Now, focus on the first part of
the sum.

$\displaystyle\sum_{e\in E_{i}}\sum_{v\in
L(h(e))}((p_{e}-1)\psi(\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\rfloor)$
$\displaystyle=\sum_{e\in E_{i}}(p_{e}-1)\psi\left(\sum_{v\in
L(h(e))}\left\lfloor\frac{G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\right\rfloor\right)$
$\displaystyle=\sum_{e\in E_{i}}(p_{e}-1)\psi(\lfloor\frac{\sum_{v\in
L(h(e))}G_{v}\odot(y+1)^{d_{e}-d_{v}}}{y+p_{e}}\rfloor)$
$\displaystyle=\sum_{e\in E_{i}}(p_{e}-1)\psi(\lfloor\frac{\bigoplus_{v\in
L(h(e))}G_{v}}{y+p_{e}}\rfloor)$ $\displaystyle=\sum_{e\in
E_{i}}(p_{e}-1)\psi\left(\left\lfloor\frac{G_{h(e)}}{y+p_{e}}\right\rfloor\right)$

Using the exact same proof, we can also obtain

$\sum_{e\in E_{i}}\sum_{v\in
L(h(e))}(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{v}\odot(y+1)^{(d_{e}-d_{v})+(d_{e^{\uparrow}}-d_{e})}}{y+p_{e^{\uparrow}}}\right\rfloor\right)=\sum_{e\in
E_{i}}(p_{e^{\uparrow}}-1)\psi\left(\left\lfloor\frac{G_{h(e)}\odot(y+1)^{d_{e^{\uparrow}}-d_{e}}}{y+p_{e^{\uparrow}}}\right\rfloor\right)$

∎

###  2.5 Linear TreeSHAP and complexity analysis

|  ComputeSummaryPolynomials$(x,v,C)$:
---
if node $v$ is leaf:
$G[v]\leftarrow C\cdot R^{v}_{\emptyset}$
else:
if $v$ is not the root:
$e\leftarrow$ edge with $v$ as head
$C\leftarrow C\odot(y+p_{e}(x))$
if $e^{\uparrow}\neq\bot$:
$C\leftarrow\frac{C}{y+p_{e^{\uparrow}}(x)}$
$l,r\leftarrow$ children of $v$
ComputeSummaryPolynomials$(x,l,C)$
ComputeSummaryPolynomials$(x,r,C)$
$G[v]\leftarrow G[l]\oplus G[r]$
return $G[v]$
Algorithm 2: Obtain the summary polynomial for each node. |  |  AggregateShapley$(x,v,G)$:
---|---
if $v$ has children:
$l,r\leftarrow$ children of $v$
AggregateShapley$(x,l,G)$
AggregateShapley$(x,r,G)$
if $v$ is not the root:
$e$ edge with $v$ as head
$i\leftarrow$ feature of edge $e$
$S[i]\leftarrow
S[i]+(p_{e}(x)-1)\psi(\left\lfloor\frac{G[v]}{y+p_{e}(x)}\right\rfloor)$
$S[i]\leftarrow
S[i]-(p_{e^{\uparrow}}(x)-1)\psi(\left\lfloor\frac{G[v]\odot(y+1)^{d_{e^{\uparrow}}-d_{e}}}{y+p_{e^{\uparrow}}(x)}\right\rfloor)$
Algorithm 3: Obtain the Shapley value vector. |  |  LinearTreeSHAP$(x,T_{f})$:
---|---
$G\leftarrow$ an array indexed by the nodes
ComputeSummaryPolynomials$(x,root(T_{f}),1)$
$S\leftarrow$ an array indexed by the features
AggregateShapley$(x,root(T_{f}),G)$
return $S$
Algorithm 4: The entire LinearTreeSHAP algorithm.

By Theorem 2.4, we can obtain an algorithm in two phases. Efficiently compute
the summary polynomial on each node(Algorithm 2) and then evaluates for
$\phi(f,i)$ directly(Algorithm 3). Both parts of the algorithm are
straightforward, basically computing directly through definition and tree
traversal. The final values of $S[i]$ is the desired value $\phi(f,i)(x)$
after running Algorithm 4.

To analyze the running time, one can see each node is visited a constant
number of times. The operations are polynomial addition, multiplication,
division, inner product, or constant-time operations. In general, all those
polynomial operations takes $O(D\log D)$ time for degree $D$ polynomial [1].
This shows the total running time is $O(LD\log D)$.

However, we never need the coefficients of the polynomials. So we can improve
the running time by storing the summary polynomials in a better-suited form,
the multipoint interpolation form. Namely, we evaluate the polynomials $G$ on
a set of predefined unique points
$Y=(y_{0},y_{1},y_{2},\cdots,y_{D})\in\mathbb{R}^{D+1}$, and store
$G(Y)=(G(y_{0}),\ldots,G(y_{D}))$ instead. In this form, addition, product and
division takes $O(D)$ time [2]. The evaluation function $\psi(G)$ also takes
$O(D)$ time but needs more explanation.

Denote $\mathcal{V}(Y)\subset\mathbb{R}^{D+1\times D+1}$ as the Vandermonde
matrix of $Y$, where $v_{i,j}\in\mathcal{V}(Y)=y_{i}^{j}$ is the $j$th power
of $y_{i}$.

######  Lemma 2.5.

Let $p,q\in R[x]_{d}$, and its coefficients $A$ and $B$, respectively, then we
have

$\langle p,q\rangle=\langle A,B\rangle=\langle
p(Y),\mathcal{V}(Y)^{-1}B\rangle.$

###### Proof.

Polynomial evaluation can be consider as inner product of coefficient and
Vandermonde matrix of input $Y$. Namely $p(Y)=A\cdot\mathcal{V}(Y)$. Therefore
$\langle p(Y),\mathcal{V}(Y)^{-1}B\rangle=\langle
A\cdot\mathcal{V}(Y),\mathcal{V}(Y)^{-1}B\rangle=\langle
A,\mathcal{V}(Y)\cdot\mathcal{V}(Y)^{-1}B\rangle=\langle A,B\rangle$ completes
the proof. ∎

In order to compute the inner products $\langle G,B_{d}\rangle$ in $O(D)$
time, we have to precompute $N_{d}=\mathcal{V}(Y)^{-1}C_{d}$, where $C_{d}$ is
the coefficient of $B_{d}$, for all $0\leq d\leq D$. This can be done simply
in $O(D)$ time for each $d$, so a total of $O(D^{2})$ time.

By storing the polynomial in interpolation form, all our polynomial operations
on each node take $O(D)$ time. Therefore the total running time is $O(LD)$.

Other than the summary polynomials, the algorithm uses constant space to store
information on nodes and edges. Each summary polynomial takes $O(D)$ space to
store. Therefore the algorithm takes $O(LD)$ space. Nevertheless, we can save
space by realizing the algorithms only need a single top-down and a single
bottom-up step. By joining two steps into one, the algorithm consumes the
summary polynomials on the spot. Hence the total space usage will be bounded
by $O(D)$ times the stack size, bounded by $D$, the depth of the tree. The
final total space usage is improved to $O(D^{2})$.

#### Remark

Even though $Y$ can be arbitrarily chosen based on the maximum depth of the
tree $D$, it is shown that Chebyshev points are near-optimal in numerical
stability [11]. In our Linear TreeShap implementation, we used the Chebyshev
points of the second kind.

##  3 Experiments

Figure 5: Speed up comparison Datasets | # Instances | # Attributes | Task | Classes
---|---|---|---|---
adult [4] | 48,842 | 64 | Classification | 2
conductor [3] | 21,263 | 81 | Regression | -
Table 2: Datasets

We run an experiment on both regression dataset adult and classification
dataset conductor(summary in Table 2) to compare both our method and two
popular algorithms, TreeShap and Fast TreeShap. We explain Trees with depths
ranging from 2 to 18. And to align the performance across different depths of
trees, we plot the ratio between the time of Tree Shap and the time of all
methods in Figure 5. We run every algorithm on the same test set 5 times to
get both average speeds up and the error bar. And for fair comparison
purposes, all methods are limited to using a single core.

Linear TreeShap is the fastest among all setups. And due to heavy memory
usage, Fast TreeShap V2 falls back to V1 when tree depth reaches 18 for the
dataset conductor. Since the degree of the polynomial is bounded both by the
depth of the tree also the number of unique features per decision rule, with
deeper depth, dataset Conductor has much more speed up gains thanks to a
higher number of features. We can conclude that the Linear TreeShap is more
efficient than all state-of-the-art Shapley value computing methods in both
theory and practice.

## References

  * [1] Ronald Newbold Bracewell and Ronald N Bracewell.  The Fourier transform and its applications, volume 31999.  McGraw-hill New York, 1986.
  * [2] Henri Cohen.  A course in computational algebraic number theory, volume 8.  Springer-Verlag Berlin, 1993.
  * [3] Kam Hamidieh.  A data-driven statistical model for predicting the critical temperature of a superconductor.  Computational Materials Science, 154:346–354, 2018.
  * [4] Ron Kohavi.  Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.  In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD’96, page 202–207. AAAI Press, 1996\.
  * [5] Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee.  From local explanations to global understanding with explainable ai for trees.  Nature machine intelligence, 2(1):56–67, 2020.
  * [6] Rory Mitchell, Eibe Frank, and Geoffrey Holmes.  Gputreeshap: Fast parallel tree interpretability, 2020.
  * [7] J Ross Quinlan.  C4. 5: programs for machine learning.  Elsevier, 2014.
  * [8] J.R. Quinlan.  Simplifying decision trees.  International Journal of Man-Machine Studies, 27(3):221–234, 1987\.
  * [9] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  ” why should i trust you?” explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144, 2016.
  * [10] Lloyd S Shapley.  A value for n-person games.  Contributions to the Theory of Games, 2(28):307–317, 1953.
  * [11] Sven Weisbrich, Georgios Malissiovas, and Frank Neitzel.  On the fast approximation of point clouds using chebyshev polynomials.  Journal of Applied Geodesy, 15(4):305–317, 2021.
  * [12] Jilei Yang.  Fast treeshap: Accelerating shap value computation for trees.  arXiv preprint arXiv:2109.09847, 2021.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [Yes]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]