Scalable Interpretability via Polynomials
Authors: Abhimanyu Dubey
Filip Radenovic
Dhruv Mahajan
Venue: NeurIPS 2022 Accept (2022)
Keywords: interpretability
explainability
trustworthy AI
polynomials
generalized additive models
interpretable machine learning

Abstract: Generalized Additive Models (GAMs) have quickly become the leading choice for interpretable machine learning. However, unlike uninterpretable methods such as DNNs, they lack expressive power and easy scalability, and are hence not a feasible alternative for real-world tasks. We present a new class of GAMs that use tensor rank decompositions of polynomials to learn powerful, {\em inherently-interpretable} models. Our approach, titled Scalable Polynomial Additive Models (SPAM) is effortlessly scalable and models {\em all} higher-order feature interactions without a combinatorial parameter explosion. SPAM outperforms all current interpretable approaches, and matches DNN/XGBoost performance on a series of real-world benchmarks with up to hundreds of thousands of features. We demonstrate by human subject evaluations that SPAMs are demonstrably more interpretable in practice, and are hence an effortless replacement for DNNs for creating interpretable and high-performance systems suitable for large-scale machine learning.
Source code is available at \href{https://github.com/facebookresearch/nbm-spam}{\ttfamily github.com/facebookresearch/nbm-spam}. 

Scalable Interpretability via Polynomials
Abhimanyu Dubey
Filip Radenovic
Dhruv Mahajan Meta Al dhruvm@fb com
Meta Al dubeya@fb.com
Meta AI
fil filipradenovicófb.com
Abstract
Generalized Additive Models (GAMs) have quickly become the leading choice for interpretable machine learning. However, unlike uninterpretable methods such DNNs, they lack expressive power and casy scalability, and are hence not feasible alternative for real-world tasks. We present a new class of GAMs that use tensor rank decompositions of polynomials to learn powerful, tiiterennty-interrettaeed models. Our approach, titled Scalable Polynomial Additive Models (SPAM) is effortlessly scalable and models all higher-ordee order feature interactions without a combinatorial parameter explosion. SPAM outperforms all current interpretable approaches, and matches DNN/XGBoost performance on series of real-world benchmarks with up hundreds of thousands of features. We demonstrate by human subject evaluations that SPAMs are demonstrably more interpretable in prac- tice, and are hence effortless replacement for DNNs for creating interpretable and high- geshh-erffrmance systems suitable for large-scale machine learning. Source www.chh/nnbmmeeeeeeeeeeeee apam.
code is available github. cacmuu..comeeee www.///oooooc/eeeeeeeeeo
1 Introduction
Interpretable machine learning systems suffer from tradeoff between approximation and inter- pretability: nigh-performing models used in practice have millions of parameters and are highly non-linear, making them difficult to interpret. Post-hoc explainability attempts remove this trade- off by explaining black-box predictions with interpretable instance-specific approximations (e.g.. LIME [Ribeiro et al., 2016), SHAP [Lundberg and Lee. 2017)), however, they are notoriously unsta- ble [Ghorbani et al., 2019a, Lakkaraju and Bastani, 2020], expensive to compute [Slack et al., 2021], and in many cases, inaccurate [Lipton, 2018]. It is therefore desirable to learn models that instead intereenll-interpretaabe (glass-bone box). i.c., do not require post-hoc interpretability. but provide better performance than timerennly-interpretaabb classical approaches such linear or logistic regression.
This has led to a flurry of research interest Generalized Additive Models [Hastie and Tibshirani, 2017], i.e., methods that non-linearly transform each input feature separately. e.g., tree-based GAM and GA [Lou et al., 2013], or NAMs [Agarwal et al., 2021]. While these are an improvement over linear methods, due to their highly complex training procedures, they are not simple drop- in replacement for black-box methods. Furthermore, it is not straightforward to model feature interactions in these models: the combinatorial explosion in higher-order interactions makes this infeasible without computationally expensive feature selection [Lou et al., 2013, Chang et al., 2021].
Contrary to these approaches, we revisit an entirely different solution: polynomials. It is folklore in machine learning that since polynomials are universal approximators [Stone, 1948, Weierstrass, 1885), hypothetically. modeling all possible feature interactions will suffice in creating powerful learners and eliminate the need for intricate non-linear transformations of data. Furthermore, polynomials can also provide rubric for interpretability: lower-degree polynomials, that have interactions between few features are interpretable but likely less accurate, whereas polynomials higher degree have larger predictive power at the cost of interpretability. Thus, not only are polynomial models capable of capturing all possible interactions between features, they also give practitioners the ability to select suitable model (order of interactions, i.c., degree) based precisely on their requirement in the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

interpretabiliity performance tradeoff. However, such an approach has till date remained elusive, as learning interpretable feature interactions efficiently and at scale remains an open problem.
In this paper, we introduce a highly scalable approach to modeling feature interactions for inherently interpretable classifiers based on rank decomposed polynomials. Our contributions are:
1. First, we present an algorithm titled Scalable Polynomial Additive Models (SPAM) to learn pnherrenty-interppetabbe classifiers that can learn all possible feature interactions by leveraging low-rank tensor decompositions of polynomials [Nie, 2017b]. To the best of our knowledge, SPAM is the among the first Generalized Additive Models with feature interactions scalable to 100K features. SPAM can be trained end-to-end with SGD (backpropagatton) and GPU acceleration, but has orders of magnitude fewer parameters than comparable interpretable models. 2. We demonstrate that under a coarse regularity assumption (Assumption 1), SPAM converges to the optimal polynomial as the number of samples n + co. Furthermore, we establish novel non-asymptotic excess risk bounds that match classic bounds for linear or full-rank polynomials. 3. SPAM outperforms all current interpretable baselines on several machine learning tasks. To the best of our knowledge, our experimental benchmark considers problems of size (number of samples, and dimensionality) orders of magnitude larger than prior work, and we show that our simple approach scales easily to all problems, whereas prior approaches fail. Moreover, we demonstrate that the need for modeling feature interactions is as important as non-linear feature transformations: on most real woll-w tabular datasets, pairwise interactions suffice to match DNN performance, We conduct detailed human subject evaluation to corroborate our performance with practical interpretability. We demonstrate that SPAM explanations are more faithful compared to post- hoc methods, making them a drop-in in replacement for black-box methods such as DNNs for interpretable machine learning on tabular and concept-bottlencck [Koh et al., 2020] problems.
2
Related Work
Here we survey the literature most relevant to our work, i.e., interpretable ML with feature interactions, and polynomials for machine learning. Please see Appendix Section B for detailed survey.
Transparent and Interpretable Machine Learning. Early work has focused on greedy or ensemble approaches to modeling interactions [Friedman, 2001, Friedman and Popescu, 2008] that enumerate pairwise interactions and learn additive interaction effects. Such approaches often pick spurious interactions when data is sparse [Lou et al., 2013] and are impossible to scale to modern-sized datasets due to enumeration of individual combinations. As an improvement, Lou et al. [2013] proposed GA 2 that uses statistical test to select only "true" interactions. However GA G fails to scale to large datasets as requires constant re-training of the model and ad-hoc operations such as discretization of features which may require tuning for datasets with a large dimensionality. Other generalized additive models require expensive training of millions of decision trees, kernel machines or splines [Hastie and Tibshirani, 2017], making them unattractive compared to blxck-box models.
An alternate approach is is learn interpretable neural network transformations. Neural Additive Models (NAMs, Agarwal et al. [2021]) learn a DNN per feature. TabNet [Ank and Pfister, 2021] and NIT [Tsang et al., 2018] alternatively modify NN architectures to increase their interpretability. NODE-GAM [Chang et al., 2021] improves NAMs with oblivious decision trees for better perfor- mance while maintaining interpretabilityy Our approach is notably distinct from these prior works: we do not require iterative re-training; we can learn all pairwise interactions regardless of dimensionality; we can train SPAM via backpropagation; and we scale effortlessly to very large-scale datasets.
Learning Polynomials. The idea of decomposing polynomials was of interest prior to the deep learning era. Specifically, the work of Ivakhnenko [1971], Oh et al. [2003], Shin and Ghosh [1991] study learning neural networks with polynomial interactions, also known as ridge polynomial networks (RPNs). However, RPNs are typically not interpretable: they learn interactions of a very high order, and include non- lonelr transformation. Similar rank decompositions have been studied in the context of matrix completion [Recht, 2011], and are also subject of interest in tensor decompositions [Nie, 2017a, Brachat et al., 2010], where, contrary to our work, the objective is to decompose existing tensors rather than directly learn decompositions from gradient descent. Recently, Chrysos et al. [2019, 2020] use tensor decompositions to learn higher-order polynomial relationships in intermediate layers of generative models. However, their work uses recursive formulation and learns high-degree polynomials directly from uninterpretable input data (c.g., images), and hence is non-interpretable.
2

---

Scalable Polynomial Additive Models
Setup and Notation. Matrices are represented by uppercase boldface letters, e.g., X and vectors by boldface lowercase, i.e., Z. We assume that the covariates lie within the set X' C Rd. and the labels lie within the finite set V. Data (æ, v) E X' x y are drawn following some unknown (but fixed) distribution B. We assume we are provided with n i.i.d. samples {( 21) 9:) as the training set.
Motivation. Generalized Additive Models [Hastie and Tibshirani. 2017] are an excellent design choice for interpretable models, they learn transformations of individual features, allowing us to model exactly the contribution of any feature. A typical GAM is as follows.
Intepretabiliey
f(x)
Σ f((ms)) order (unary)
fy)() + ..... fI...((:)) order d
J> order (pairwise)
Performance
Where fi, etc., possibly non-linear transformations. It is evident [Lou et al., 2013] that as the order of interaction increases, e.g. beyond pairwise interactions, these models are no longer interpretable, albeit some benefit performance. While some approaches (e.g., Agarwal al. [2021], Chang et al. [2021]) learn Sa via neural networks, we want to learn the simplest GAMs, i.e., polynomials. Specifically, want to learn a polynomial P(xr), of order (degree) k S d of the form:
d
d
d
P(x) = b+
Σ
W
(2) Wi
IiTj +
Σ
II
Here, the weights (( fwo 1.1.1s capture the l-ary interactions between subsets of I features. For small values of d and k. one potentially enumerate all possible interactions and learn a linear model of (dd)) dimensionality, however this approach quickly becomes infeasible for large d and k. Furthermore, the large number of parameters in P(ar) make regularization essential for performance, and the computation of each interaction can be expensive. Alternatively, observe that any polynomial that models k-ary ary interactions can be written as follows, for weights {
1/ N1=1
P(x) (1) @1 æ + (2)) O2 x + +.. (kk) O x x b.
Here, the weights ( E Rdd are written as tensor of order and the operation Tr refers to
repeated inner product along dimensions, e.g., W E Rdd x: T Wwx W O2 x (W @ x) O æ where @ denotes the inner product. More generally, any symmetric order 7 tensor admits equivalent polynomial representation having only degree-l terms. Now, this representation is still plagued with the earlier curse of dimensionality for arbitrary weight tensors WF and we will now demonstrate how circumvent this issue by exploiting rank decompositions.
3.1 Learning Low-Rank Decompositions of Polynomials
The primary insight of our approach is to observe that any symmetric tensor (!)) of order / also admits an additional rank decomposition [Nie, 2017a, Brachat et al., 2010] (ø) being the outer product):
W Σ Ar Su wu.....
I limes
Where {u,Y= are the (possibly orthonormal) d dimensional basis vectors, Z, denotes the rank of the tensor, and the scalars {A Ag E R denote the singular values. Our objective is to directly learn the rank decomposition of order I tensor, and therefore learn the required polyno- mial function. This gives us total of O(rd) learnable parameters per tensor, down from a previous dependence of O(d'). This low-rank formulation additionally enables us compute the polynomial more efficiently. Specifically, for a degree k polynomial with ranks r {1, 72, r2, rk), we have:
T3
P(x) = b xx) + E Azi (uzi. x)²
+
Aae (Ugi x²
ARi (uts z)
Where (us) ) { denote the corresponding bases and eigenvalues W The above term now be easily computed via simple inner product, and has time as well as space complexity
3

---

of (dd[rll)) instead of the earlier O(d*), Here, I|rl/a simply represents the sum of ranks of all the k tensors. Note that low-rank decompositions do not enjoy a free lunch: the rank of each weight tensor can, in the worst case, be polynomial in d. However, it is reasonable to assume that correlations in the data X' will ensure that a small r will suffice for real-world problems (see, e.g., Assumption 1).
Optimization. For notational simplicity, let us parameterize any order k polynomial by the weight set 0 = {b, u1, {22s. U2: Ni {AEs, Uks Y==1 E (R((++1) where from now onwards r = ||||] = 1+ + F3 ... + nk denotes the cumulative rank across all the tensors. We write the polynomial parametrized by 0 as P(:; 0), and the learning problem for any loss E is:
select θ_ arg min o.
((P(x;; 0), ys) + 8 R(0).
(2)
Here, O denotes the feasible set for O. and R(-) denotes an appropriate regularization term scaled by 3 O. We can show that the above problem is well-behaved for certain data distributions X.
Proposition If the regularization R and loss function é: y x y + [0, 1] are convex, À >> 0 and X' R4 then the optimization problem in Equation 2 is convex in 0 for O RT(
Proposition 1 suggests that if the training data is positive (achieved by renormalization), typical loss functions (e.g., cross-entropy or mean squared error) and R such as Lp norms are well-suited for optimization. To ensure convergence, one can use proximal SGD with a small learning rate [Nitanda, 2014]. In practice, we find that unconstrained SGD also provides comparable performance.
3.2 Improving Polynomials for Learning
Geometric rescaling. Learning higher-order interactions is tricky as the order of interactions increases: the product of two features is an order of magnitude different from the original, and consequently, higher-order products are progressively disproportionate. To mitigate this, we rescale features such that (a) the scale is preserved across terms, and (b) the variance in interactions is captured. We replace the input x with क = sign(x)
1/t for an interaction of order Specifically, |xx
r's
rk
P(x)= (u1, x)
Agc (uzi, 2²)²
Asi (U3,,
Aua (usi. .zg)* + b. (3)
We denote this model as SPAM-LINEAR. We argue that this rescaling for unit-bounded features ensures higher interpretability as well as better learning (since all features are of similar variance). Note that for order 1, _. = x. For h 2 2, consider a pairwise interaction between two features Tz 0.5 and zj 0.6. Naively multiplying the two will give feature value of x;æ; 0.3 (smaller than both x; and æ,)) whereas an intuitive value of the feature would be vTzzj = 0.54, i.e., the geometric mean. Regarding the reduced variance, observe that unconstrained, the variance V(rjay)) V V(x:) V(z,) and V( (xpry) ((VT,)V(VV)) S VVx;)) - V(x,). If the features have small variance, e.g., V(z,)= = V(r,) 10-2 and are uncorrelated, then the first case would provide a much smaller variance for the interaction, whereas the rescaling would preserve variance.
Shared bases for multi-class problems. When we are learning a multi-class classifier, it is observed that learning a unique polynomial for each class creates a large model (with O(2drC) weights) when the number of classes C is large, which leads to overfitting and issues with regularization. Instead, we propose sharing bases (u) across classes for all higher order terms, and learning class- specific singular values (A) for all higher order terms (> 2) per class. For any input æ, P(æ; 0) SOFTMAX (a:
C) where, for any class c E (1,..,C),
12
Pk
Pa 0) b. + (uf, .x)
Xg, (u2i, )² + Σ
Aa. (UL3, T3)
Nr. (uk mx)
The terms in green denote weights unique to each class, and terms in red denote weights shared across classes. This reduces the model size to O(dd + r)C + rd) from (rdC)). We set l as the cross-entropy of the softmax of (Po(. 0) both these operations preserve convexity.
Exploring nonlinear input transformations Motivated by non-linean GAMs (e.g.. GA [Lou et al., 2013] and NAM [Agarwal et al., 2021]), we modify our low-rank decomposed algorithm by replacing क; for each I with feature-wise nin-liie.s..ies. We learn a non-lineat SPAM P(: 0) as,
P(z: 0) = b + (u1, Fz)))) +
Aas (uzi, F2(x))² + + Σ
Aps (usi (

---

Here, the function (z = Ifa (z1), fi. [ra( is a Neural Additive Model (NAM) [Agar- wal et al., 2021]. We denote this model as SPA.M-NEUAAL For more details on the NAM we use. please refer to the Appendix Section C. Note that the resulting model is still interpretable, as the interaction between features I; and Jyj e.g., will be given by (Et=) X2x (2nl)))))))))) (2)(
instead of the previous (EX=1 A2a (aeeuuuku)))) "2kz) v2
for typical SPAM.
Dropout for bases via A. To capture non-overlapping feature correlations, we introduce a basis dropout by setting the contribution from any particular basis to zero at random via the singular values x. Specifically,, observe that the contribution of any basis-singular value pair (u, X) at order is A X(u, x)". We apply dropout to to ensure that the network learns robust basis directions.
3.3
Approximation and Learning-Theonn Theoretic Guarantees
We present some -heoorec guarantees for SPAM. Proofs are deferred Appendix Section A. Proposition 2. Let f be continuous real-valued function over compact set X. For any threshold e > 0, there exists a low-rank polynomial P X + IR such that supzex [f(z) - P(x) <
functioo
The above result demonstrates that asymptotically, decomposed polynomials universal function approximators. Next, we present an assumption on the data-generating distribution as well as a novel excess risk bound that characterizes learning with polynomials more precisely moo-asymptotic).
Assumption 1 (Exponential Spectral Decay of Polynomial Approximators). Let Pk denote the family of all polynomials of degree at most k, and let P., denote the optimal polynomial in Pk. iee. P..k- arg minpep, BB(a.))-33 [e(P(a)), y)]. We assume that Vk, P.,k admits decomposition as described in Equation such that, for all 1 S S. k, there exist absolute constants C₁ < 1 and
C2 (1) such that \xtll= S C1 expp (-C2 (7) for each j 2 1 and l [1, k.)
This condition is essentially bounding the "smoothness" of the nearest polynomial approximator of f. i.e., implying that only a few degrees of freedom suffice to approximate f accurately. Assumption 1 provides a soft threshold for singular value decay. One can also replace the exponential with slower "polynomial" decay with similar results, and we discuss this in the Appendix Section A. We can now present our error bound for L22 regularized models (see Appendix for Iı-regularized models).
Theorem 1. Let E be 1-Lipschitz, 8 E (0, 1]. the generalization error for the optimal degree-k polynomial P.,k be E(P. k) and the generalization error for the empirical risk minimizer SPAM
Pr.ko ie., Pe.e- arg minp Ei= ((P(as)) y1) with ranks = [1, "l,,2,...,,,. be E(Pr.)). Then, if B satissies Assumption with constants C1 O2 and 7, we have for iz-regularized ERM, where |uuill2 S Bu,2 Vi E [ E [ri),, and | S Bx where X = {{>ig { )= least 1 - 8,
with probability at
E(Prk)) - E(P,,)) S 2Bx,
h (uwD
Vn
V=+++
d
G. C2
k (Esp(-ri))
+ 5
log (4/8)
The above result demonstrates an expected scaling of the generalization error, matching the bounds obtained for L1 (see Appendix Section A) and Le-regularized linear classifiers [Wainwright, 2019]. We that the rank r = ||r|/ has an O(r) dependence on the Rademacher complexity. This highlights a trade-off between optimization and generalization: a larger r' gives a lower approximation error (smaller second term), but larger model complexity (larger first term). Observe, however, that even when Q2oog d)?) for some p 2 1, the approximation error (second term) diminishes as of ((77 ). This suggests that in practice, one only needs a cumulative rank (poly)logaiithmic in The above result also provides a non-asymptotic variant of Proposition 2; as n, r - xc, E(Pr,) E(P,,))+
Offline Experiments
Here we evaluate SPAM against a set of benchmark algorithms on both classification and regression problems. The baseline approaches consider are (see Appendix Section C for precise details):
Deep Neural Networks (DNN): These are standard multi-layer fully fully-connected neural networks included to demonstrate an upper-bound on performance. These are explained via the perturbation- based LIME [Ribeiro et al., 2016] and SHAP [Lundberg and Lee, 2017] methods Section 5. Linear / Logistic Regression: These serve as our baseline interpretable models. We learn both L
and Le regularrze models unary and pairwise features (4) features) with minibatch SGD,
5

---

Table 1: Evaluation of SPAM on benchmarks against prior work. (t): higher is better, (Q): lower is
better, **: variance across trials is < 0.001. : variance across trials is < 0.005. Boldface red denotes the best black-box model, boldface green denotes the best interpretable model, boldface denotes where SPAM Order 3 is best. Runs averaged over 10 random trials with optimal hyperparameters.
Regression Binary
Multi-Class Classification
Obj. Det.
Model
RMSE ())
AUROC (t)
Accuracy (t)
mAP (1)
CH
FICO
CovType
News
CUB
iNat
CO114
Interpretable Baselines
Linear (Order 1)
0.73541
0.7909"
0.7254
0.8238
0.7451
0.3932 0.1917
Linear (Order 2)
0.7293
0.7910
0.7601 **
0.7617
0.4292 0.2190
EBMs (Order 1)
0.5586*
0.7985
0.7392
EB Ms (Order 2)
Ms
0,4919*
0.7998**
NAM
0.5721*
0.7993
0.7359
0.7632
0.4194 0.2056
Uninterpretable Black Box Baselines
XGBoost
0.4428"
0.7925
0.8860 0.7677 0.7186
DNN
0.5014
0.7936"
0.9694 0.8494" 0.7684"
0.4584"
0.2376"
Our Interpretable Models
SPAM (Linear, Order 2)
0.6474
0.7940"
0.7732 0.8472"
0.7786"
0,4605
0.2361
SPAM
(Neural, Order 2)
0.4914"
0.8011
0.7770"
0.7762
0.4689
SPAM
(Linear, Order 3)
0.6410"
0.7945
0.8066"" 0.8520'
0.7741 TM
0.4684 0.2368
SPAM
(Neural, Order 3)
0.4865*
0.8024"
0.8857**
0.7753"
0.4722"
Table 2: Tabular Datasets
Name
California Housing (CH)
FICO
Cover Type (CovType))
Newsgroups
Source
Pace and Barry [1997]
FICO [2018]
Blackard and Dean [1999] Lang [1995]
Instances
20,640
10,459
581,012
18,828
Features
8
23
54
146,016
Classes
2
7
20
Feature Type
Numeric
Mixed
Mixed
TF-IDF
Gradient Boosted Trees (XGBoost): We use the library xgboost. This baseline is mainly to compare accuracy, the number of trees required are typically large and are hence uninterpretable. Explainable Boosting Machines (EBMs) [Lou et al., 2013]: EBMs use millions of shallow bagged trees operating on each feature at a time. Note that this approach is not scalable to datasets with many features or multi-class problems. We report scores on the datasets where we successfully trained EBMs without sophisticated engincering, using the interpretml library [Nori et al., 2019]. Neural Additive Models (NAMs) [Agarwal et al., 2021]: These models are neural network extensions of prior EBMs. Note that this method also does not scale to some datasets.
Training Setup. SPAM is implemented by learning LerLua-rgl variants by minibatch SGD implemented in PyTorch. For regression tasks, we measure the root mean squared error (RMSE). For binary classification, we report the area under the ROC (AUROC), for multi-class classification, we report the top-1 accuracy (Acc @ 1), and finally, for object detection, we report mean Average Precision (mAP). We tune hyperparameters via random sampling approach over a grid. Note that for all experiments, both NAM and SPAM-NEURAL have identical MLP structures to ensure identical approximation power. For definitions of metrics and hyperparameter ranges, see Appendix Section C.
4.1 Measuring Benchmark Performance
We select tasks to explore a variety of settings from regression multi-class classification, and also explore different dataset scales, from a few hundred samples and tens of features to 100K-scale datasets (both in the number of samples and data dimensionalityy, while ensuring that the features are interpretable. Our datasets are summarized in Table 2. Please see Appendix Section C.1 for details. For all datasets with defined train-val-test split, use fixed random sample of 70% of the data for training, 10% for validation and 20% for testing. For the 20 Newsgroups dataset, we split the pre-defined training split 7:1 for training and validation, respectively.
In an effort to scale interpretable approaches beyond tabular datasets, we consider benchmark problems using the "Independent Concept Bottleneck" framework of Koh et al. [2020] for image

---

0.50
[A1] Acc. vs Order, INat
0.50
(81) Acc. vs Ranks, INat
(C) Acc. Sparsity, CU8-200
Accuracy
0.77
0.45
0.45
SPAMa-Linea
SPAM JOrder 21
0.40
SPAM Neura
SPAM (rrder
Accuracy
0.76
2
0.40
500
750
1000
1250
1500
Accuracy
0.9
(A2) vs Order, Cov Tye
Accuracy
0.86
(B2) Acc. vs Ranks, Newsgroups
0.75
SPAM--Lneer
SPAM 1Order
0.7
SPAM Neura
SPAM (rrder 3)
10a
0.04 Fraction of Painwise Interactions
0.08
Degree
Cumulative Rank
Figure 1: Ablation of Accuracy with: (A1, A2) Degree k; (B1, B2) Rank r; (C) L1 Sparsity.
classification and object detection. We use a convolutional neural network (CNN) backbone ResNet- 50 [He et al., 2016] that is trained to predict interpretable concepts (c.g., parts of object) from images. After training the backbone, we extract predicted concepts for all inputs, and learn an interpretable classifier head from these concepts. In experiments, the backbone remains identical for all comparisons, and we only compare the head classifiers (see Appendix Section C.3 for more details). We select three datasets for evaluation in the concept bottleneck setting:
1. AAltech-UCSD Birds (CUB-200) [Wah et al., 2011]: This fine-grained visual categorization dataset where one has to classify between 200 species of birds. The interpretable concepts are 278 binary bird attributes, e.g., the shape of the beak, the color of the wings, etc. The dataset has 5,994 training and 5,794 validation images. See Appendix Section C.3.1 for more details.
2. INaturalist "Birds" [Van Horn et al., 2018 1, 2021]: iNaturalist can be thought of as a larger version of the previous dataset. We only select the "Birds" super-categor, of samples, which has 414,000 training and 14,860 validation instances across 1,486 classes. Since the iNaturalist dataset does not contain dense part and attribute annotations, we use the predicted concepts from the CUB-200 backbone model extracted on all samples.
3. Common Objects Dataset (CO114, Proprietary): Here we consider, for the first time, a concept bottleneck model for object detection. We construct a dataset involving common household objects (e.g., bed, saucer, tables, etc.) with their bounding box annotations. For each bounding box, we collect 2,618 interpretable annotations (e-g., parts, color, etc.). The dataset has 2,645,488 training and 58,525 validation samples across 1 115 classes with 2,618 interpretable concepts. We report the mean Average Precision (mAP) metric. For more details please refer to Appendix Section C.3.2.
Our results are summarized in Table 1. There are four main takeaways from the results. First, observe that both 3PAM-LINEA. and --EURALLLL comfortably outperform their prior interpretable counterparts on all datasets (e.g.. Order 2 SPAM-LINEAM outperforms all linear methods even the full rank pairwise model), and SPAM- comfortably outperforms all non-linear baselines. Next, observe that in all datasets but CoverType, second degree interactions suffice to match or even outperform DNN performance. We will discuss CoverType in detail the next paragraph. Thirdly, observe that SPAM models are as scalable as the black-box approaches, whereas prior work (e.g.. NAM and EBMs) are not. the case of NAM, we were unable scale due to the sheer number of parameters required to model large datasets, c.g., Newsgroups (>900M parameters), and for EBMs, the training time and memory requirement increased dramatically for large datasets. Furthermore, MB do not even support multi-class problems. Finally, observe that for many problems, we do not require non-linear feature transformations once we model feature interactions: e.g., iNat and CUB.
Cover' Type Dataset. XGBoost and DNNs perform substantially better on CoverType compared to linear or neural SPAM. On analysis, we found that existing SPAM models underfit on CoverType, and hence we increased the total parameters for PAM-NNURAL via subnets, identical to NAMs [Agarwal et al., 2021], where each feature is mapped to non-linear features (as opposed to originally). With = 8 subnets, the performance of S-BURN AT. (order 3) improves to 0.9405. In comparison,
NAMs with 8 subnets provides a lower accuracy of 0.51..
4.2 Ablation Studies
Rank and Degree of Interactions. By Proposition 2, it is natural to expect the approximation quality to increase with the degree k and rank r, i.c., introduce more higher-order interactions
7

---

Table 3: Throughput benchmarking (higher is faster).
CH
FICO
Cov Type
News
Method
hroughput (images second)
NAM [Agarwal al., 2021]
x 10
1.2 x 10
10'
NAM (Order 2)
1.1 x 10
6 x 10
3 X 10a
LincarSPAM (Order 2)
6.1 x 10'
6.7 10'
6.1 10"
10"
NeuralSPAM (Order 2)
1.7 x 10
7.9 x 10
1.1 x 10
LinearSPAM (Order 3)
3.2 x 10
3.7 10?
3.9 10"
1.8 10
NeuralSPAM (Order 3)
1.1 X 10
5.3 x 10
2.6 X 10
MLP
1.3 x 10
1.3 10
1.3 10"
2.2 102
between features. We ablate the degree on the tabular benchmark CoverType and concept bottleneck benchmark iNaturalist (Birds), summarized in Figure 1A. We observe, expected, that increasing the degree l leads to moderate improvements beyond k 2 3, but with diminishing returns. Similarly, examine the effect of the cumulative rank performance (Birds) datasets (Figure IB); we observe that performance is sufficiently insensitive to r, and plateaus after while. We imagine that as r increases, model complexity will dominate and performance will likely begin to decrease, matching the full-rank performance at r = O(d2) for pairwise models.
the Newsgroups and iNaturalist
Sparsity in Higher-Order Relationships. A requirement for interpretability is to ensure that the learned models can be explained with few interpretable concepts. Since the number of higher-order combinations increases with k we examine sparsity to limit the number of active feature assignments. We penalize the objective in Equation 2 with a regularization term that inhibits dense feature selection. IfU { > denotes all the basis vectors in matrix form, we add the penalty R(0) _ ||U]| This ensures that every basis u only captures limited interactions between features, and hence the overall complexity of the model is limited. We examine accuracy non-zero pairwise interactions for a degree 2, rank 800 SPAM on CUB-200 in Figure IC, and find that only 6% of the possible interactions suffice to obtain competitive performance.
function of the fraction of
Examining Assumption 1 (Spectral Decay). The spectral decay assumption presented in Assump- tion I crucial to obtain reasonable generalization bounds (Theorem 1). To test this assumption, we examine the spectra of SPAM-LINEAR (Order 2) model for all 200 of CUB-200 classes. These are depicted Figure 2A. Furthermore, we an exponential model on the decay itself, and obtain (in line with Assumption y 3, C₁ 0.54 and C2 0.006, all in accordance with the assumption.
4.3
Additional Experiments
4.3.1
Comparisons on Common Benchmarks
In addition to the 7 datasets considered earlier, evaluate on 9 further benchmark datasets commonly used in the interpretability literature. We evaluate on the MIMIC2, Credit and COMPAS datasets as presented in Agarwal al. [2021], and the Click, Epsilon, Higgs, Microsoft, Yahoo and Year datasets from Chang et al. [2021]. The result this is summarized Table 4. We observe that SPAM models competitive with prior work, and outperforming prior work on number of tasks (the best interpretable model is in bold).
4.3.2 Runtime Evaluation
We provide comparison of SPAM runtimes on 4 different datasets to establish their scalability. We consider the Californi Housing (CH, Pace and Barry [1997], features), FICO HELOC (FICO, FICO [2018], 23 features), CoverType (CovType, Blackard and Dean [1999], 54 features) and 20 News- groups (News, Lang [1995], 146,016 features), and evaluate the throughput of the optimal Linear and Neural SPAM models against Neural Additive Models (NAM, Agarwal et al. [2021]) and MLPs. Table 3 describes the throughput, where we observe that Linear SPAM is more efficient than MLPs, and NeuralSPAM is orders of magnitude faster than NAM, which does not scale to higher orders.

---

Table 4: Comparison against state-of of------rtttttttt interpretable neural networks on additional benchmarks.
MIMIC2 Credit
COMPAS
Click Epsilon
Higgs
Microsoft
Yahoo
Year
Method
(AUC) (AUC)
(AUC)
(ERR) (ERR) (ERR)
(MSE)
(MSE) (MSE)
NAM [Agarwal et al., 2021J
0.8539
0.9766
0.7368
0.3447 0.1079 0.2972
0.5824
0.6093
85,25
NODE-GAM [Chang et al., 2021]
0.8320
0,9810
0.7420
0.3342 0. 0.2970
0.5821
0.6101 85.09
LinearSPAM (Order 2)
0.8514
0,9836
0.7426
0.3791
0.1011 0.2881
0,5710
0.5923
81.30
NeuralSPAM (Order 2)
0.8664
0.9850
0.7411
0.3348
0.1020 0.2750
0.5671
0.5869
79.99
XGBoost
0.8430
0,9780
0.7440
0.3334
0,1112 0.2328
0.5544
0.5420
78.53
Table 5: Feature importances for interpretable models used in human subject evaulations.
Model
Importances for input æ = (21, Ld)
Linear / post-hoc Linear
ux v;, E (1,..., d]
SPAM (Linear, Order 2) uu Zx, i E (l...., d} and (2 A
xj,ij.. (d]
5 Human Subject Evaluations
Experiment Methodology. We now evaluate how well explanations from SPAM fare in practical setting with non-interpretable benchmarks such as black-box models equipped with post-hoc explanations. Our objective is to mimic a practical setting, where the model user must decide between fully-interpretable model vs. black-box classifier with post-hoc explainability. Our experiment design is Prediction Task [Hoffman et al., 2018, 8, Muramatsu and Pratt, 2001], where the objective for the users is to guess what the model predicted given an explanation. The motivation of such a design is to ascertain both the faithfulness and interpretability of the model explanations.
Computing Explanations. We first compute the feature importances for any class c, as the contribu- tion of any specific feature in the logit for class e (for binary classification or regression, there is only one class). For the Logisite Regression model, we simply use the contribution of each feature the prediction. For SPAM-Liner (Order 2), we still use each feature's 's contribution, but features now can be unary (z4)) or pairwise (I; and 2z). ). As black-box post-hoe baselines, we consider DNNs with LIME [Ribeiro et al., 2016] and KemeiSHAP [Lundberg and Lee, 2017] to generate post-hoc linear explanations. See Table for the formulation of importance for the models we use experiments.
Experiment Design We conduct a separate experiment for each model M with explanations of length E by selecting E most important features. Each such experiment runs in two phases training and lesting. In the training phase, participants are shown 8 images of birds and their corresponding explanations to develop their mental model. Four of these images have been pre- dicted as class A by the model, and the remaining are predicted as class B. They then move on to the testing phase, where they are successively shown the explanations for 5 unseen im- ages (which the model could have predicted as either A or B), and the users must answer "given the explanation, which class (of A or B) did the model predict?". If they desire, the users can move back to the training phase at any time to revise model explanations. We do not show the corresponding images in the test phase, as we want the user feedback to rely solely on the faithfulness of explanations. We measure the mean user accuracy on predicting model decisions. For more details on the interface, please see Appendix Section D.1. For each experiment, we follow an independent- subjects design, and gathered a total of 150 participants per experiment. Each task (corresponding to one eeplalexpllnnation pair) lasted 3 minutes. The participants were compensated with $0.75 USD ($1 5/hour), and all experiments were run on Amazon Mechanical Turk (AMT, Buhrmester et al. (2016]) with a total cost of $3000. To remove poorly performing participants, we only select those that get the first decision correct, and compute the mean user accuracy using the remaining 4 images.
Study #1: Comparing Black-Box and Transparent Explanations. We compare different inter- pretable models with a fixed explanation length of E = 7. Our objective is to assess the interpretability of pairwise interactions compared to black-box and linear explanations, and to re-am re-answer whether was even necessary to have -eleriinterreeeable models compared to black-box models with post-hoc explanations. We used samples from the 5 pairs of classes, that is A and B), from CUB-200 dataset (see Section D.1 for images). The results from this experiment are summarized in Figure 2B. Observe that with SPAM, the mean user accuracy (mUA) is substantially higher (0.71) compared to both linear (0.67) and post-hoc LIME (0.65). We would like to remark that even for E = 7, SPAM has an
9

---

(A) Spectral Decay
(B) Comparing Interpretable Approaches
(C) Varying Explanation Length
0.8
Exponential Fit
0.8
LIME-SK
SPAM-Linear
0.6
mean User Accuracy
Accuracy
0.0
0.7
0.7
0.8
0.2
0.0
100
150
200
Linear
LIME
SHAP
SPAM
0.4
10
Longth Explanation
Figure 2: (A) Spectral Decay on CUB-200; Human Subject Evaluation results for (B) Comparing Black-box and glass-box explanations, and (C) LIME vs. SPAM with different explanation lengths.
average of 3.1 pairwise terms in each explanation, and therefore the higher-order terms are substantial. A one-sided t-test [Freund and Simon, 1967] provides significance (p-value) of 2.29 x 10-4 and test statistic of 3.52 for the SPAM mUA being higher than LIME, and correspondingly for Linear, we get significance (p-velue) of 0.03801 and test statistic of 1.666. Hence SPAM's improvements in interpretability are statistically significant over both linear and post-hoc approaches.
Study #2: Varying Explanation Length. One argue that the increased interpretability of polynomial approaches due to the fact that each higher-order "term" involves multiple features (c.g.. pairwise involves two features), and hence the increased mean user accuracy (mUA) is due to the larger number of features shown (either individually or as pairs). We examine this hypothesis by varying the explanation length E for both SPAM-Linear (Order 2) and LIME, which consequently increases the number of terms seen for both approaches. We observe in Figure 2C that regardless of explanation method, mUA is maximum E and introducing more terms decreases interpretability.
6 Discussion and Conclusion
We presented a simple and scalable approach for modeling higher-order interactions in interpretable machine learning. Our approach alleviates several of the concerns with existing algorithms and focuses on presenting a viable alternative for practical, large-scale machine learning systems. In addition to offline experimental guarantees, we demonstrate by an extensive user study that these models are indeed more interpretable in practice, and therefore can readily substitute post-hoc interpretability without any loss in performance. Moreover, to the best of our knowledge, our work provides the first incremental analysis of interpretability and performance: we show how progressively increasing the model complexity (with higher order interactions) brings better performance while compromising interpretability in practice, and the "sweet spot" appears to rest at pairwise interactions.
We have several follow-up directions. First, given that our model provides precise guarantees feasible starting point to understanding tradeoffs between privacy and explainability from rigorous perspective. Next, one can consider utilizing SPAM to understand failure modes and spurious correlations directly. Furthermore, SPAM-esque decompositions can also be useful in other domains beyond interpretability. c.g., language and vision, where modeling higher-order interactions is challenging due to the curse of dimensionality.
on generalization,
References
R. Agarwal, L. Meinick, N. Frosst, X. Zhang, B. Lengerich, R. Caruana, and G. E. Hinton. Neural additive models: Interpretable machine learning with neural nets. Advances in Neural Information Processing Systems, 34, 2021.
S. O. Arık and T. Pfister. Tabnet: Attentive interpretable tabular learning. In AAAI, volume 35, pages 6679-6687, 2021.
A. Asuncion and D. Newman. Uci machine learning repository, 2007.
S. Bach, A. Binder, G. Montavon, F. Klauschen, K.-R. Müller, and W. Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10 (7):00100140, 2015.
10

---

P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-433 2002.
B. Bercu, B. Delyon, and E. Rio. Concentration inequalities for sums and martingales. Springer, 2015.
J. A. Blackard and D. J. Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):33--511 1999.
J. Brachat, P. Comon, B. Mourrain, and E. Tsigaridas. Symmetric tensor decomposition. Linear Algebra and its Applications, 433(11-11):1851-18777) 2010.
M. Buhrmester, T. Kwang, and S. D. Gosling. Amazon's mechanical turk: A new source of inexpensive, yet high-quality data? 2016.
D. V. Carvalho, E. M. Pereira, and J. S. Cardoso. Machine learning interpretability; survey on methods and metrics. Electronics, 8(8):832, 2019.
S. Chakraborty, R. Tomsett, R. Raghavendra, D. Harbore, M. Alzantot, F. Cerutti, M. Srivastava, A. Preece. S. Julier, R. M. Rao, al. Interpretability of deep learning models: A survey of results. In 2017 IEEE smartworld, ubiquitous intelligence & computing, advanced & trusted computed, scalable computing communications, cloud & big data computing, Internet of people and smart city innovation
pages 1-6. IEEF, 2017.
C.-H. Chang, R. Caruana, and A. Goldenberg. Node-gam Neural generalized additive model for interpretable deep learning. arXiv preprint arXiv:2 106,0/613, 2021.
C. Chen, O. Li, D. Tao, A. Barnett, C. Rudin, and K. Su. This looks like that: deep learning for interpretable image recognition. Advances in neural information processing systems, 32, 2019.
G. Chrysos, S. Moschoglou, Y. Panagakis, and S. Zafeiriou. Polygan: High-order polynomial generators. arXiv preprint /9Xiv:/908.0657/ 2019.
G. G. Chrysos, S. Moschoglou, G. Bouritsas, Y. Panagakis, J. Deng, and Zafeiriou. P-nets: Deep polynomial neural networks. In Proceedings the IEEE/CVF Conference Computer Vision and Puttern Recognition, pages 7325-7335, 2020.
C. K. Chui and X. Li. Realization of neural networks with one hidden layer. In Multivariate approximation: From CAGD to wavelets, pages 77-89. World Scientific, 1993.
M. Du. N. Liu, and X. Hu. Techniques for interpretable machine learning. Communications of the ACM, (3(1):68-77, 2019.
FICO. Fico community explainable machine learning challenge. 2018. URL https: tattps://comt //commnittt. fico. com/ s/ axplainabllee.....e www.maachneeeee - -ea----arrinnn-aalllleeeeeeeeeee (ewlllnnneetaabe-31111
E. Freund and Simon. Modern elementary statistics, volume 256. Prentice-Hae Englewood Cliffs, NJ, 1967.
J. H. Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, pages 118-1133,, 2001.
J. H. Friedman and B. E. Popescu. Predictive learning via rule ensembles. The annals of applied statistics, 2(3):916-9555 2008.
A. Ghorbani, A. Abid, and J. Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3681-3688, 2019a.
A. Ghorbani, J. Wexler, J. Y. Zou, and B. Kim. Towards automatic concept-based explanations.
Advances in Neural Information Processing Systems, 32, 2019b.
T. J. Hastie and R. J. Tibshirani. Generalized additive models. Routledge, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
R. R. Hoffman, S. T. Mueller, G. Klein, and J. Litman. Metrics for explainable ai: Challenges and prospects. arXiv preprint arXiv: / 2018.
A. G. Ivakhnenko. Polynomial theory of complex systems. IEEE Iransactions on Systems, Man, and Cybernetics, (4):364-378, 1971.

---

P. W. Koh, T. Nguyen, Y. S. Tang. S. Mussmann, E. Pierson, B. Kim, and P. Liang. Concept bottleneck models. In International Conference on Machine Learning, pages 5338 5388. PMLR, 2020.
H. Lakkaraju and O. Bastani. how do fool you?" manipulating user trust via misleading black box explanations. In Proceedings of the AAAT/ACM Conference on AI, Ethics, and Society, pages 79-85, 2020.
K. Lang. Newsweeder: Learning to filter netnews. In Machine Learning Proceedings 1995, pages 331-339. Elsevier, 1995.
T. Laugel, M.-J. Lesot, C. Marsala, X. Renard, and M. Detyniecki. The dangers of post-hoc interpretability: Unjustified counterfactual explanations. arXiv preprint arXiv: arXiv: 1907.09244 2019.
Z. C. Lipton. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue, 16(3):31-57, 2018.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization, arXiv preprint arXiv: 1,005007,, 2017.
Y. Lou, R. Caruana, J. Gehrke, and G. Hooker. Accurate intelligible models with pairwise interactions. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 623-631, 2013.
S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
A. Madsen, S. Reddy, and S. Chandar. Post-hoc interpretability for neural nlp: A survey. arXiv preprint arXiv: 048400 2021.
Massart. Some applications of concentration incqualities to statistics. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 9, pages 245-303, 2000.
A. H. Miller, W. Feng, A. Fisch, J. Lu, D. Batra, A. Bordes, D. Parikh, and J. Weston. Parlai: A dialog research software platform. arXiv preprint arXiv: 1705. 06476, 2017.
Muramatsu and W. Pratt. Transparent queries: investigation users' mental models of search engines. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 2 217-224, 2001.
Nie. Generating polynomials and symmetric tensor decompositions. Foundations of Computational Mathematics, 17(2):423 465, 2017a.
J. Nie. Low rank symmetric tensor approximations. SIAM Journal on Matrix Analysis and Applica- tions, 3814)155 2017b.
A. Nitanda. Stochastic proximal gradient descent with acceleration techniques. Advances in Neural Information Processing Systems, 27, 2014.
H. Nori, S. Jenkins, P. Koch, and R. Caruana. Interpretml: A unified framework for machine learning interpretability.. arXiv preprint wwXivv/909.092200 2019.
S.KK. Oh, W. Pedrycz, and B.-J. Park. Polynomial neural networks architecture: analysis and design. Computers & Electrical Engineering, 29(6):703-725, 2003.
R. K. Pace and R. Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3): 291-297, 1997.
B. Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12). 2011.
M. T. Ribeiro, S. Singh, and C. 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.
C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
Y. Shin and Ghosh. The pi-sigma network: an efficient higher-order neural network for pattern classification and function approximation. In IJCNN-91 -e-atlle International Joint Conference Neural Networks, volume i, pages 13-18 vol.1, 1991. doi: 1LL1109/JCNN.119911...
A. Shrikumar, P. Greenside, A. Sheherbina, and Kundaje. Not just black box: Learning important features through propagating activation differences. arXiv preprint Ttff::6650071... 2016.
12

---

A. Shrikumar, P. Greenside, and A. Kundaje. Learning important features through propagating activation differences. In International conference on machine learning, pages 3145-3153. PMLR, 2017.
D. Slack, A. Hilgard, S. Singh, and H. Lakkaraju. Reliable post hoc explanations: Modeling uncertainty in explainability. Advances in Neural Information Processing Systems, 34, 2021.
M. H. Stone. The generalized weierstrass approximation theorem. Mathematics Magazine, 21(5):
237-254, 1948.
M. Tsang, Liu, S. Purushotham, P. Murali, and Y. Liu. Neural interaction transparency (nit): Disentangling learned interactions for improved interpretability. Advances in Neural Information Processing Systems, 31, 2018.
G. Van Horn, O. Mac Aodha, Y. Song, Y. Cui, C. Sun, A. Shepard, H. Adam, P. Perona, and
S. Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8769-8778, 2018.
G. Van Horn E. Cole, S. Beery, K. Wilber, S. Belongie, and O. Mac Aodha. Benchmarking representation learning for natural world image collections. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 12884- 12844, 2021.
C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie The caltech-uesd birds-200-2011 I dataset. 2011.
M. J. Wainwright, High-dümensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
K. Weierstrass. On the analytical representability of so-called arbitrary functions of real variable. Meeting reports of the Royal Prussian Academy Sciences in Berlin, 2:633-639, 1885.
7. Yang, C. Jin, 7. Wang, M. Wang, and M. I. Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622, 2020.
R. Zhang, P. Madumal, Miller, A. Ehinger, and B. I. Rubinstein. Invertible concept-based explanations for enn models with non-negative concept activation vectors. arXiv preprint arXiv:2006.1544 2020.
13

---

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 deseribe the limitations of your work? [Yes] See conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(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 of all theoretical results? [Yes] See Appendix Section A.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix Sec- tion A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please see Section 4 and supplementary material.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Please see Sections and 4.
(b) Did you mention the license of the assets? [Yes] See accompanying supplementary material.
(c) Did you include any assets either in the supplemental material URL?? [N/A]
No new assets except code, see 3(a).
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [Yes] See supplementary material.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] No participant risks were identified in the experiment design.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [Yes] See Section 5.
14


Reviews:
[{"review_id": "E7d2EfVz4gx", "reviewer": "Reviewer_arrH", "summary": "This paper proposes a fully-interpretable model which is in the line of generalized additive models (GAMs). In order to let the fully-interpretable model scalable, the authors reduce the conventional GAMs to a polynomial one. By doing tensor decomposition, the proposed model can be effortlessly scalable and model higher-order feature interactions without a combinatorial parameter explosion. Experimental results validate the effectiveness of the proposed method both in the perspectives of prediction and human evaluation. Theoretical results also guarantee their model’s performance. ", "questions": "What if we continue to increase the length of explanation? Is it the 7 global optimal in Figure 2C?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The technique of this paper is sound. The authors provide a clear view and logic of the proposed idea with the basic form of the polynomial additive models and how it can be scalable by low-rank decompositions. The improving on geometric rescaling and shared bases for multi-class problems also make sense.\n2. So is the clarity of this paper according to the above comments. \n3. The human subject evaluation is also convincing. \n\nWeaknesses: \n1. It would be better to provide the details in the human subject evaluation. For example, the authors could provide the explanation provided by the models in the bird prediction task. Then we may have a better understanding on how the model is interpreted. \n2. The significance of the proposed method seems fair. The proposed method is not post-hoc, which means the prediction and interpretation all count on the proposed method. Table 1 shows pretty good prediction results where the proposed method can mostly outperform all the baselines including DNN. But it seems a bit tricky since the DNN is just a simple MLP. Outperforming an MLP may not be a big advantage. In addition, what are the reasons to choose the four datasets presented in the paper? I am concerned that the results are cherry picking so that the proposed method cannot work well in prediction. If so, a slightly better interpretable ability may not be worth applying to real world tasks. Good prediction plus post hoc explanation may be sufficient.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "9sFHjci-PcJ", "reviewer": "Reviewer_wzTc", "summary": "The paper proposes to make Generalized Additive Models (GAMs) scalable, by tensor rank decompositions of polynomials. Specifically, the traditional GAMs are re-written into the tensor computation form. The weight matrices are then processed with rank decomposition, making the GAMs a series of inner products and are more computationally efficient. The authors also propose several tricks to help learning, including feature rescaling, sharing basis across classes, and extending GAMs with non-linear operations. Experiments under different data domains are conducted, including MLPs and CNNs. The experiments make use of the concept bottleneck backbone to further improve its performances. Human subject evaluations are also included since this paper is related with interpretability. This is a well-written paper, with in-depth understanding of GAMs and comprehensive experiments.", "questions": "Please see the Weakness part.", "limitations": "The paper proposes a series of extensions of SPAM to address some possible limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper addresses an important problem in interpretable machine learning, i.e., how to build efficient and effective models besides interpretability. The paper chooses GAMs as prototypes, making a smart application of tensor decomposition to make GAMs more efficient. The paper is very well-written.\n2. The paper considers a series of extensions for the proposed SPAM models. These extensions are consistent with the core contribution.\n3. Comprehensive experiments are conducted. With both quantitative analysis and human studies.\n\nWeaknesses\n1. I would avoid adding \"fully-interpretable models\" in the abstract. Is SPAM really \"fully-interpretable\"? I think \"inherently interpretable\" could be better.\n2. I think adding some more analysis about the learned SPAM models (i.e., which features or feature interactions are important) could help readers understanding what has been learned inside models for some of the tasks.", "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": "67_Nt8JxPUs", "reviewer": "Reviewer_othi", "summary": "This paper proposes SPAM which extends Generalized Additive Models (GAM) with polynomials. SPAM learns a polynomial model that can capture any-order interactions among features. The authors leverages the proved symmetric property and assumed low-rank property of the weight matrices to simplify the optimization problem. For multiple-class classification tasks, the authors propose to use shared bases to further speed up training. The authors show under some assumption, the generalization error of SPAM scales exponentially w.r.t. the chosen low-rank order. The authors conduct experiments with several datasets and show that proposed SPAM achieve better results than various of baseline models. The authors also conduct human evaluation on how good SPAM is comparing with a black box model and the results show SPAM achieve much better results than using a black box model with post-hoc explanation.", "questions": "- Can you show some empirical resutls about the effects of using shared bases? I'm curious to see how much that trick would improve. Do you think it makes sense to use a shared bases for $u_1, u_{2i}, ..., u_{ki}$ in equation 3?", "limitations": "- I think it's worth noting the running time of the SPAM on different datasets to help understand the scalability of SPAM. I guess for extremely high-dimension datasets (like high-resolution images or videos or texts), SPAM might not be able to train efficiently. It would be great if the authors can provide some discussions on this part.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of using polynomials to improve GAM is novel. The authors address the challenges of using polynomials well (mainly, scalability) by leveraging some nice properties of the problem.\n- The authors provide thorough analysis for the proposed models. The charaterization of the generalization error, the geometric rescaling, data preprocessing, and shared bases idea for multi-class problems help the readers get a deeper understanding of the proposed model.\n- The experimental section is thorough. Other than regular comparsion with baseline methods, the authors check the effects of order, sparsity assumtion for higher order interactions and verify the generalization error empirically. The human evaluation setting is novel and provide more evidence on why a fully-inpretably model might be better.\n\nWeaknesses:\n- For Table 1, I think the authors can include results for NA^2M since SPAM at lease uses order-2 interactions. ", "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": {}}]

Author rebuttal:

Decision: Accept