Linear tree shap
Authors: Peng Yu
Albert Bifet
Jesse Read
Chao Xu
Venue: NeurIPS 2022 Accept (2022)

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.  

Linear TreeShap
Peng Yu 12,5
Chao Xul- Albert Bifet Jesse Read
University Electronic Science and Technology of China LTCI. Télécom Paris, IP Paris LIX, Ecole Polytechnique. IP Paris
4 Al Institute, University of Waikato 5 Shopify ppng yu, albert. bifet biffet@@teeecompaaat @@telecom-paris.fr cxu@uestc. edu. cn readeeereeepplyyyeeeiiiueee
Abstract
Decision trees are well-known due to their ease of interpretability. To improve accuracy, we need grow deep trees or ensembles trees. These are hard 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 linear weighting to features independent of the tree structure. The rise in popularity mainly due to TreeShap, which solves a general exponential com- plexity 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.
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-bas bbssed local explanation model LIME[9], game-theer theerettetetiaall based Shapley value[10], etc. Shapley value gained particular interest due to both local and globally consistent and efficient implementation: TreeShap[S]. With the broad adoption of Shapley value, the industry has been seeking much more efficient implementation. Various methods like GPUTreeShapp6 and FastTreeShapl 12] were proposed to speed up TreeShap. GPUTreeShap primarily focuses on utilizing GPU perform efficient parallelization. And Fast improves the efficiency of TreeShap by utilizing caching. All of them are empirical approaches lacking mathematical foundation and are thus making them hard to understand.
We solve the exact Shapley value computing problem based on polynomial arithmetic. By utiliz- ing the properties of polynomials, our proposed algorithm Linear TreeShap can compute the exact Shapley value 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 Table 1, since all current algorithms for ensemble of trees are applying the same algorithm to each tree individually.
*Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Let S be the number of samples to be explained, N the number of features, T. 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 OL)). Also, D < L.
temperature
wo00.
w:0.5
15
0.5 rain(D)
cloudy
Algorithm
Time Complexity
Space Complexity
wo:044
400
Original
no
yes
TreeSHAP [5]
O(SLD²)
O + NN
Fast TreeSHAP vl [12]
wind speed
0.7 min (A)
O(SLD²)
O(D² + N)
w0 0.7
te:
Fast
90
0.3
TreeSHAP v2 [12)
O + SLD)
O(T2P)
Linear
0.4 rain (C)
0.6
TreeSHAP
O(SLD)
O(D² N)
Table 1: Comparison of both computational and space
Figure An example decision
complexity
tree Ty shows chances of rain
Methodology
2.1 Notation & Backkround
Elementary symmetry polynomials are widely used in our paper. [R[x] denotes the set of polynomials with coefficient in R. R[æ]a are polynomials of degree no larger than d. We use @ for polynomial multiplication. For two polynomials a and b, [ is the quotient of the polynomial division a/b.
For two vectors x, y E Rd. (ar y) is the inner product of and y. We abuse the notation, so when polynomial appears in the inner product, we take it to mean the coefficient vector of the polynomial. Namely, p, q are both polynomials
the same degree, then (p, q) is the inner product of their coefficient vectors. We use for matrix multiplication.
We refer to x X C IR' 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] the value of feature i of instance æ.
instance and f X IR as the fitted tree model in a supervised
We have to start with some common terminologies because our algorithm is closely involved with trees. A rooted tree T (V, E) is directed tree where each edge is oriented away from the root r E V. For each node v, P. is the root to e path, i.e. the set of edges from the root to u. L(v) is the set of leaves reachable from L(T) non-leaf node has two children. an edge e goes from u to c, then u and u are the tail and head of e, respectively. We write hee) for the head of e.
L(r) is the set of leaves of T. T is full binary tree if every
A tree is weighted, if there is an edge weight we for each edge e. It a labeled tree if each edge also has label le. For labeled tree T, let E, be all the edges of the tree with label i. Similarly, define Pr. = P. n E, the set of edges in the root to o path that has label i. The last edge of any subset of path is the edge furthest away from the root.
For our purpose, a decision tree is weighted labeled rooted full binary tree. There is correspond- ing decision tree for the fitted tree model Ty. 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 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 contains weight w. that the conditional probability based associated splitting criteria during training.

---

When predicting a given instance, 3; decision tree model f sends the instance to of its leaves according to splitting criteria. We draw an example decision tree in Fig 1. Each leaf node is laheled 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 fs(x) X R.S S M to denote the prediction of instance a of the fitted tree model using only the features in active set S, and treat the rest of features of instance as missing. Using this representation, the default prediction f() is shorthand for (z).
The Shapley value of a decision tree model f is the function ((f X R, Ssu(st (z) - fs(x).
(L.
Σ
M
SEMYE
[S]
The Shapley value o(f. (x) quantifies the marginal contribution of feature in the tree model when predicting instance r. The problem of computing the Shapley values is the following algorith- mie problem.
The Tree Shapley Value Problem
Input: A decision tree y for function f X R over m features, and x E X. Output: The vector (ø(f. ())x). (ff, (z))
Meanwhile, decision nodes cannot split instances with missing feature values. A common con- vention is to use conditional expectation. When decision node encounters missing value, 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: wt, Wy- Here Wi + w, = 1 and 0 < wi < 1. similar approach is also used in both Treeshap(5), and C4.5 [7] 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 example instance =(tepperature: 20, cloudy: no, wind speed: 6) with tree in Fig I to show the full process of Shapley value computing. By following the decision nodes of Ty, the prediction f(x) is leaf' C: 0.4 chance of raining. Now we compute the importance/Shapley value feature (temperature: 18) among x for getting prediction 0.4 chance raining.
The importance/Shapley value of feature (temperature: 18) is
(f, temperature) (z)
(f /leemprraturee, cloudy, wind speed) (I) f(cloudy, wind speed] (I))
+ (f /temperrature wind speed} (x) - [(wind speed] (x) + /temperature, cloudy (x) -f f(ctoudy] (x))
+ ( ttepeerature y. (I) - fo(x)))
To elaborate more, term f(clondy, wind speed) (I) with =(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 D 0.5 C' as prediction.
On the other hand, decision tree ff can be linearized into decision rules [8]. decision rule can be seen decision tree with only a single path. A decision rule R" X + IR for leaf v can be constructed via starting from root node, following all the conditions along the path to the leaf u. We use F(R) to represent the set of all features specified in decision rule R, namely, F(R)- = Pi * 0}.
The linearization of the decision tree f to decision rules is the relation f(x) = EvELTT (x). Example tree in Fig can be linearized into 4 rules:
1. R::: if (temperature 19) and (is cloudy) then predict 0.7 chance of rain else predict chance of rain
3

---

2. RB: if (temperature 19) and (is not cloudy) and (wind speed 8) then predict 0.6 chance of rain else predict chance of rain
3. RC: (temperature 19) and (is not cloudy) and (wind speed - 8) then predict 0.4 chance of rain else predict 0 chance of rain
4. RP: if (temperature < 19) then predict 0.5 chance of rain else predict 0 chance of rain
For decision rule R, we also introduce prediction with active set S, Rs X + R. When features 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 V with empty input:
= -
=V
II We
PEP.
Where is the conditional probability/proportio of instances, when splitting by decision node at the source of edge e, the proportion of instances belong to the current edge. V is the prediction of the leaf node that defines that decision rule.
We say n. R),, if ar is satisfied by every splitting criteria concerning feature i in decision rule R. For given instance x and leaf v, we use a new variable (t.v to denote the marginal prediction of R when adding feature to active set S.
1 x E (R") 1i.0 (x) = IeEEP.. ie
& 7
The empty product equals 1, hence if Pi,. = 0. (x) = 1. We omit the super/subseript if there no ambiguity the leaf node. So, with i S, we can write:
Rayuss(r)
(4)
Since 0 is subset of any set S, can get Rs(x)) via products of weights:
Rs(x) Rg II (z(2)
(5)
JES
With Rs, Is can also be linearized into the sum of rule predictions:
fs(ø) Σ
R²((x).
(6)
VEL(T,)
2.2 Some special luucction and their properties
Definition 2.1. Define the reciprocal binomial polynomial to be Ba(x) En (9 "r,
Definition 2.2. The function va R[r]a > IR is defined as
(A, Ba)
vb((A)
d+1
We write (p)) = va(p) where d is the degree of p.
The function &ha has two nice properties: additive for same degree polynomial and "scale" invariant when multiplying binomial coefficient.
Proposition 2.1. Let p, E [[[x) and l E N.
Additivity: va(p) + valg) = va(p + q).
Scale Invariant (pp O (1 ))* vp(p).

---

2.3
Summary polynomials and their relation to Shapley value
Consider we have a function f represented by a decision tree Tç. We want to explain a particular sample 2; therefore in the later sections, abuse the notation and let g mean g(ø) whenever X + IR, e.g Kr = (z). 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 tree the sum of the Shapley value of decision rules.
o(Si))
E i(R,
(8)
VEL(Ty)
Now, for each decision rule, we define summary polynomial.
Definition 2.3. For decision tree y and instance For decision rule associated with leaf in Ty, the summary polynomial G. is defined as
Gv( Rij
II
(9j,v v)
JEF(R)
Next, study the relationship between the summary polynomial and the Shapley value of corre- sponding decision rule.
Lemma 2.2. Let e be a leaf in fT, then
GO (i,0 + y
6(R", ((1, 1)
Proof. Since everything involved in the proof is related to the leaf we drop from the su- per/subscripts for simplicity. First, we simplify the Shapley value of rule R into:
Φ RR
1
Σ
(m-1) Rough) Rs Ro(g: 1)
Σ SCM)()
4 JES
II
(10)
SCA(
When feature does not appear in R. 9: returns O, thus Shapley value feature from rule R Let [F(R) = d, the number features in R. The Shapley value of R further reduces to:
S
((R,) = Rola: - 1) Σ
Σ
II %
(11)
k=0
SCF(RMM
We observe that R4 Σ S|= SCF(BM Ils 9j is precisely the coefficient of y in
We obtain the weighted of all subsets' decision rule prediction using the inner product:
| Σ
d (d-1)
G
R
Σ 1/
II
( 9:
Ba-1)
(12)
[S]
+
SCP(R)E
SCF(R)
Shapley value for R has a compact form shown in Eq.
$ Rolg - 1)
Σ
II 41
d
dd
SCF(RM
JES
(g: 1)
+ Ba-1)
(13)
d
G
(q: - 1)
qi + y
5

---

2.4 Computations
Even though we have simplified the Shapley value of decision rule in compact form using poly- nomials, it is still not friendly in computational complexity. In particular, the values fi, are flat aggregated statistics and do not necessarily share terms in-hetween different rules. This makes 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 with feature i, use et to denote its closest ancestor edge that shares the same feature. In cases such edge does not exist, et L. We also use a E Ta to represent the x[1] is satisfied by all splitting criteria feature associated with all edges in P.,..
I Ie we x E Th(c) 0
Pe =
(14)
x & Th(c)
We also define additionally that P1 1.
is the last edge in P.,e then Pe = qt This is the key to avoid qr, completely, and instead switch to Pe. Our analysis will make sure that any pe that does not correspond 4s,x for any v and i gets cancelled out.
We show relation between the Shapley value of a decision rule and the newly defined 's's.
Consider operation @di.d2
[R[x] (r) d2
R [xx] max((ii The subscript is omitted when
d1, d2 is implicit.
G + G2 = G + G o +)
(15)
We extend the summary polynomial to all nodes in the tree. Let Gu = D G". Denote de as the degree of Ga, where h(e)) u. Proposition 2.3. Let be leaf in Ty. and dy be the degree of Gy then
Go @ (y 
1ydo-du
) -(Pett (pat
1) (1 Go ② 1) 11++
1):
((H, = Σ
(pe 1)
21 Pe
Pet
eEPr
Proof. Let e" be the last edge of P..-- We note few facts. Pe- ni, y + dú,0 divides Gu, and the sum is a telescoping sum. Put them together.
(pe 1)pb (L
G. ① (y + 1)da-do
1) (pet - 1) (1
Gp ② (y fy++ 1) dd
!)
Σ eEP,
y U Pe
3 + Pat
Par
Gn ④ (y 1)d
=(pe- 1)pb
1 + Pet
G ④ (y + 1)da- -d
1)
=(qi.v 1)
y + qú.0
G
-(piv 1)
(y 1)da--d
y + Aiv
G
-(a.v
1)
y + Qi.v
=O(R", i)
The following theorem establishes the relation between Shapley values, the summary polynomials at each node, and pe for each edge Theorem 2.4 (Main).
(Ghite) Pe
Gh(e)
1) (Pot 1)b (1 Gh(te @ ( 01++1)4.
))
@(fii) Σ (pe 1)
y PPt

---

Proof. Based linearity of Shapley Value, ((,,)) = EVELIT, @ ,i).
For each rule R", we can scale their summary polynomial G, to the degree of Ghee)- Based on Proposition 2.3,
[Gv (y (8+ 1)daadaa 1) 1) (G.00(+t)))
(1 Gv (G
1 1)
((.1)= E E(e (pc-1)y VEL(Ty)EEP...
Pe
y ++ Pet
Observe that for any (e, pair, have E E, and L(h(e)) if and only if u E L(Ty) and e E Pi.. Hence, can order the summation by summing through the edges.
(f - Σ E (pe-1)ed (1
(y 1)de du -) -1)-
( о (y + 1)(( 1 -de) 1)
y P
V Pet
Pet
EEE, NEI(((())
Observe that at each edge all summary polynomial G is scaled to the same degree de, According Proposition 2.1, we can add the summary polynomials before evaluate using (.). Now, focus on the first part of the sum.
Gy 2 (y + 1)de-d
Go O (y + 1)d.-d. d.
E Σ eEÈ; VEL(H(e)
((pr 1)y((
1) Σ (p. 1)16
E(p,
Σ vEI(h(e))
y + Pe
y + Pe
EveL(h(e))
Go (y 1dde-
Σ eEE,
(pe 1)4((
V Pe
(pe - 1)2((1 DVEL(M(E) Go
Σ EEE,
y + Pe
Σ (pe 1) (
Gh(())
y + Pe
RE
Using the exact same proof, we can also obtain
Σ Σ (Pet-1)w (1
G. O (y + 1) d. (dd, -de)
1)
(1
Ghite O (y 1))tt -ddtt-d
Σ
(Par (1)p
y + Pe
y 4 Per
EEE, vEL(h(e)
.EE,
2.5 Linear TreeSHAP and complexity analysis
By Theorem 2.4, we can obtain an algorithm in two phases. Efficiently compute the summary polynomial on each node(Alge Allgorithm 2) and then evaluates for @(f, 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 Φ(f, (): after running Algorithm 4.
To analyze the rumning time, ations 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).
each node is visited a constant number of times. The oper-
need the coefficients of the polynomials. So can improve the running time by storing the summary polynomials in a better-suited form, the multipoint interpolation form. Namely, evaluate the polynomials G on set of predefined unique points Y (yo, Vı, ... yDD RD+1, and store G(Y) = (G(yo)...., G(yd)) instead. In this form, addition, product and divi- sion takes O(D) time [2]. The evaluation function (G) also takes O(D) time but needs more explanation.
However,
Denote V(Y) C D++ as the Vandermonde matrix of Y, where U. V(Y) 1/f the jth power of y:-
7

---

COMPUTESUMAAR v, C): if node is leaf:
Glul 4 C- Ry
else:
if v not the root:
<- edge with as head
C C (y
if +1:
Ct (+
1, f children of COMPUTESUIMAARTOONNNNNIAAL COMPUTSSUNMANYPOONNOMIIL...... G'ul <- G|]] G[r]
return Glul
Algorithm Obtain the summary polynomial each node.
AGGREGATESHAPLEYGGR G): if has children:
I. f- children of AGGREGATESSHAPLEY(ZI..
ACCREGATESSHAAPEYY(RTY.
if is not the root: edge with head + feature of edge e
S[i] S + (z) 1)v{
G
ytp.(=)
G1 (tp,-(m)
S[i] S (p)) 1)
Algorithm 3: Obtain the Shapley value vector.
Lemma 2.5. Let p.q R[z]d. and its coefficients A and B, respectively, then have
(p.q) (A, P(Y
Proof. Polynomial evaluation can consider as inner product of coefficient and Vandermonde ma- trix of input Y. Namely p(Y) = A- AYY. Therefore (p(Y), V(Y)))())) B) (A-V(Y)) -(Y) B)
(A, V(Y) - = (A, B) completes the proof.
order to compute the inner products (G, Ba) in O(D) time, we have to precompute Na V(Y)--Ca, where C. is the coefficient of Ba, for all S < D. This can be done simply in O(D) time each d, so total of O(D2) 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(L)).
Other than the summary polynomials, the algorithm uses constant space to store information on nodes and edges. Each summary polynomial takes O(D) space store. Therefore the algorithm takes (LL)) 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 O(D²).
Remark Even though Y can be arbitrarily chosen based on the maximum depth of the tree D, it shown that Chebyshev points are near-optimal numerical stability [11), In our Linear TreeShap implementation, we used the Chebyshev points of the second kind.

---

LINEARTREESHAPIC. T;):
G an array indexed by the nodes MAI.BUUUMMMAYYLLLOIIIAASSSSS (T))
S < an array indexed by the features
AGGREGATESHAPLEYYC.. (od
return $
Algorithm 4: The entire LINEARTREESHAP algorithm.
dataset adult
dataset conductor
6
5
speed up
4
method
linear_tree sarr__ree_shhee _ee__shapp__
3
fast tree shap_v
fast tree _ere_reee_______________________
2
tree free_shap
5
10
15
10 depth
15
depth
Figure 5: Speed up comparison
Datasets adult [4]
Instances
Attributes
Task
Classes
48,842
64
Classification
conductor [3]
21,263
81
Regression
Table 2: Datasets
3 Experiments
We experiment 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 18. And to align the performance 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 the same test 5 times get both average speeds up and the error bar. And for fair comparison purposes, all methods are limited to using single core.
different
Linear TreeShap is the fastest among all setups. And due to heavy memory usage, Fast TreeShap V2 falls back to VI 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 conclude that the Linear TreeShap is more efficient than all satte-o--hhe-a Shapley value computing methods in both theory and practice.
References
[1] Ronald Newbold Bracewell and Ronald N Bracewell. The Fourier transform and its applica- tions, volume 31999. McGraw-hill New York, 1986.
[2] Henri Cohen. A course in computational algebraic number theory, volume 8. Springer-Verre Berlin, 1993.
[3] Kam Hamidieh. A data-driven statistical model for predicting the critical temperature superconductor. Computational Materials Science, 154:346-354, 2018.

---

[4] Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Pro- ceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD'96, 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 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 interpretabil- ity, 2020.
[7] 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 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 Shapley. A value for n-person games. 2(28):307-31,, 1953.
Contributions to the Theory of Games,
[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.08847, 2021.
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(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. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "yG61pcTtXhu", "reviewer": "Reviewer_RR9B", "summary": "The paper introduces \"Linear TreeSHAP\", a novel method to compute exact Shapley-Value for decision trees. The method leverages observations from the well-known and used TreeSHAP method, and utilizes properties of polynomials to reduce the complexity of TreeSHAP from $O(LSD^2)$ to $O(LSD)$, when $D$ is the max depth of the tree. Linear TreeSHAP is empirically compared to TreeSHAP and its more efficient variant FastTreeSHAP, and shows significant improvement in run time for deep decision trees.", "questions": "I would like to hear the authors' opinions on two possible limitations of the method:\n1.  $\\textbf{the effect of unused features}$ - consider the tree described in figure 1, and assume that there is another feature provided to the model - \"season\". Also, assume that we fit a tree with a low depth and that the fitted tree does not contain the season feature at all. When evaluating $E(f(x)| x_{(season, couldy)})$, the method will assume 0.5 prob. of temperature to be above 19, and 0.5 prob. to be below 19. However, it is very likely that $P(temperature < 19| season) \\neq P(temperature < 19)$, so even though the model does not explicitly use season, the conditional probability-based feature elimination process that estimates  $\\phi(\\{season, cloudy\\})$ should be effected from the knowledge that the season feature provides.\n\n2.  $\\textbf{weights balancing}$ - When training decision tree classifiers in practice, it is very common to balance the weights between the different classes. When doing so, the weights are no longer representing the conditional distribution of the samples in the train data and therefore using these weights to evaluate $f(x_s)$ might be inaccurate. I wonder if there is another interpretation of the results yielded in this scenario and if there is a way to use the training data distribution to overcome this issue. \n\nDespite the fact that both limitations also apply to the original TreeSHAP, I believe that highlighting them in the paper will allow further research, and prevent misuse of the method.", "limitations": "It would be helpful if the authors will mention some limitations of their work, especially about how to interpret the output of their method. For example, it is important to mention that this method only explains the tree, and should be used carefully when trying to infer causality or conclusions on the structure of the data.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nShapley Value based feature importance methods are widely used both in academia and in the industry. Since computing the exact Shapley Value is hard computationally-wise, introducing methods that can efficiently calculate the exact values are of high importance. This paper introduces such a solution for decision trees, which are commonly used models, especially in scenarios where explainability is required. The algorithm is based on a grounded theory that guarantees linear run time for any tree and showed both theoretically and empirically to outperform existing methods.\n\nI also think that the authors did a good job of explaining the background and simplifying the intuition behind the algorithm.\n\nWeaknesses:\n\n* I think that the paper is worth publishing as is, but since its main potenital impact is to practically allow computation of Shapley Value on trees, providing more information about its limitations and assumptions might help practitioners to use it more wisely (I provide some examples in the questions section).\n* In the experiments, It seems like Linear TreeSHAP showed to significantlly outperform FastTrreeSHAP only in cases where FastTrreeSHAP V2 falls back to FastTreeSHAP V1 due to memory limitations. In my opinion, it is important to show at which point Linear TreeSHAP outperforms FastTrreeSHAP V2 where there are no memory limitations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "oO3zrH5x17", "reviewer": "Reviewer_nHUS", "summary": "- The authors proposed a novel algorithm that improves the computational complexity of TreeShap with the same amount of memory. \n- TreeShap has been a popular algorithm for understanding ensemble of decision trees. The proposed algorithm will have some applications for large-scale data. \n", "questions": "- Will the authors release the code and add it to the official TreeShap github?", "limitations": "The area is relatively narrow. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The correctness of the algorithm is rigorously verified. \n- The improvement in computation is significant. \nWeaknesses:\n- The algorithm is a specific refinement to an algorithm in a relatively narrow area. But this is not a reason for rejection. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "hbVQ7FQcVaH", "reviewer": "Reviewer_yep3", "summary": "This work considers the problem of calculating Shapley values for tree-based models. Without a clever algorithm, calculating Shapley values has exponential running time, but TreeSHAP introduced a procedure for making the running time polynomial. The approach presented here, Linear TreeSHAP, aims to design a procedure that is even more efficient (without compromising on memory). \n\nThe approach is quite technical, but if the authors' results are correct, then Linear TreeSHAP achieves exact Shapley value calculation with better time complexity in theory (by a factor of $D$, the maximum tree depth) and a noticeable speedup in practice (which grows larger with deeper trees). The tools used here are interesting, and to my knowledge novel in this subfield.", "questions": "Several questions about the presentation and experiments are included above.", "limitations": "There are no negative societal impacts for this work.\n\nThe authors give a detailed description of their algorithm's run-time and memory complexity, describing the most expensive computations. The only additional material that might highlight limitations would be an expansion of the experiments section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- The authors present a new procedure for calculating Shapley values for tree-based models. They provide results showing that their algorithm is exact (it involves no statistical estimation) and efficient (the time complexity analysis yields a linear rather than quadratic dependence on the tree depth). The speedup is reflected in practice\n- The authors make use of interesting technical tools (summary polynomials) to design their approach\n\n### Weaknesses\n\nThe presentation was difficult to follow. This is perhaps inevitable for a technical approach like this, but there were a couple places where it could be improved:\n- $m$ and $N$ are both used to denote the number of features\n- The process of linearizing a tree could be described specifically around lines 91-94, as it's quite simple - i.e., there's a single decision node with a split based on all edges in $P_v$, with the prediction being either the original node prediction or zero\n- \"Marginal prediction\" is a confusing name for $q_{i, v}(x)$. That name sounds like \"marginal contribution\" from the game theory context, but to get the marginal contribution we actually need $R_S(x)(q_{i, v}(x) - 1)$, so the multiplier itself is not the marginal contribution\n- In equation 6, this isn't a completely obvious result so it may be helpful to include something like \"according to this definition of $R_S$, we have the following equivalence with the previously defined $f_S$\"\n- I attempted to verify the math up until a certain point, and I found equation 11 somewhat difficult to derive from equation 10. I don't think this result is described in the main text or appendix, could it be added?\n\nSome other notes on presenting the approach:\n- What's the motivation for the name \"linear TreeSHAP,\" is it the reduced dependence on $D$ in the complexity analysis? \n- In the introduction, would it be possible to give more intuition for how the approach works instead of \"we solve the exact Shapley value computing problem based on polynomial arithmetic\" ? I'm not sure how I would refine this, but it's a pretty vague description of what's presented in later sections\n- Could the authors add some discussion about how their approach differs, in its derivation and the techniques involved (rather than just the run-time), from TreeSHAP and FastTreeSHAP? For readers who aren't familiar with the details of those algorithms, even a high-level discussion would be helpful\n\nAbout the experiments: \n- The results are quite positive. Would it be possible to show how the different algorithms improve when parallelizing across multiple cores? \n- Would it be possible to add a couple more datasets, for example those shown in the FastTreeSHAP work?\n- Because the math is difficult to verify, it would be very helpful to show experimentally that the three algorithms (TreeSHAP, FastTreeSHAP, Linear TreeSHAP) yield identical results\n\nNits: \n- On line 5, \"provides a linear weighting\" is an unusual description for SHAP. In what sense is it linear? The attributions are perhaps *additive*, in that they sum to the prediction (minus the base rate prediction) and are derived from a weighted least squares problem\n- On lines 22-23: these criticisms of prior work don't make sense. How are either GPUTreeSHAP or FastTreeSHAP lacking mathematical foundation? GPUTreeSHAP is based on the original TreeSHAP algorithm, and FastTreeSHAP is mathematically justified as well. How are they \"empirical\" approaches? That sounds like it means heuristics that aren't necessarily correct or well understood, which isn't true here. And how are they harder to understand than Linear TreeSHAP? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QHW_bhgkEQ9", "reviewer": "Reviewer_sVJC", "summary": "The authors present a new exact method to compute Shapley values for decision trees that can be computed in O(SLD) where S is the number of samples, L is the number of leaves and D is the maximum depth of the tree. This compares to previous exact methods operating in O(SLD^2). The authors provide both the mathematical proof for their method as well as empirical comparisons to previous algorithm to compute Shapley values.", "questions": "I have no further questions or suggestions for this work.", "limitations": "There are no obvious negative societal effects of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and motivated and provides a clear improvement over previously available methods to compute Shapley values for decision trees. Decision trees are an important non-linear prediction tool and Shapley values integral in analyzing their fit and selecting variables. Hence, I believe this paper makes a significant and original contribution to the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AyIf5rs6eK", "reviewer": "Reviewer_1DKp", "summary": "This paper proposes an efficient implementation of an algorithm to compute of Shapley values from decision trees. This implementation is based on polynomial arithmetic. With respect to existing algorithm it reduces the dependency of computational complexity on tree depth from D^2 to D, while it remains exact.\n", "questions": "I would suggest the authors to rewrite their introduction, to improve the experimental part and add a conclusion.\n", "limitations": "I don't see any negative societal impacts to the work (since it aims at improving model interpretabilaty). There is no discussion of the limitation of the approach. Given the nature of the contribution, a strict improvement of some existing work, it's not really a problem though.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Reducing the computing times of exact TreeShap is a very nice result given the desirable theoretical properties of this metric and its popularity. So, I think the contribution of the paper is important. The derivation of the algorithm, based on polynomial arithmetic, is very clever and looks sound to me (although I didn't check every steps of the proofs and I'm also not an expert of polynomial arithmetic). In the end, the final algorithm remains rather simple to implement.\n\nThe presentation in the paper could be improved however. The introduction is very minimal and seems to have been rushed. Section 1.1 presents the computational complexity of all compared methods without any discussion. I think that Linear TreeShap should be better contrasted with respect to previous results. The paper should incorporate a more detailed presentation of related works.\n\nIn contrast, I find the description of the proposed algorithm rather clear and accurate, despite a few typos (see below). The pseudo-code is also clear. I think however that some proofs could have been moved to the supplement to gain space for more discussion in the introduction and experimental section.\n\nThe experiments are very minimal and a bit rushed again. I understand that the computational complexity of the proposed algorithm is strictly better than all other proposals, without any sacrifice in terms of exactitude and space complexity. But still, I would have been interested by an assessment of the impact of more parameters on performance, in addition to tree depth. For example, I see that Fast TreeShap v2 carries out some pre-computations to improve computing times when several explanations are computed. How does this method compare against Linear TreeShap when the number of samples to be explained increases? Reporting actual computing times would have been interesting as well.\n\nSome details are also missing: the size of the test set used on both datasets, how the trees have been constructed (are they single trees, forests, boosted ensembles?). \n\nMinor comments: \n- I have no better name to suggest but I'm not fond of the name of the method, \"linear TreeShap\". Note that strictly the dependence is not linear with respect to tree complexity or depth, because it depends on the product LD.\n- It should be mentioned in the paper that the proof of proposition 2.1 is in the appendix.\n- Some typos:\n     - Line 50: \"tail and head e\" => of e.\n     - Line 88: \"equalivant\"\n     - Line 94: Use $R^v$ instead of $R$?\n     - Eq (2): \"v\" is used both to denote a leaf and its value. Maybe a different notations should be used.\n     - Line 159: \"last edge of in $P_{i,v}$\".\n     - Line 160: \"any $p_e$ does not\" => \"any $p_e$ that does not\".\n     - Line 204: \"to to\".\n     - There are many problems in the references (authors list in [2], name of proceedings is cut in [4], no journal in [7], [9] is a reference to a review of Quinlan's book, not to Quinlan's book).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept