Fast Generic Interaction Detection for Model Interpretability and Compression
Authors: Tianjian Zhang
Feng Yin
Zhi-Quan Luo
Venue: ICLR 2022 Poster (2022)

Abstract: The ability of discovering feature interactions in a black-box model is vital to explainable deep learning. We propose a principled, global interaction detection method by casting our target as a multi-arm bandits problem and solving it swiftly with the UCB algorithm. This adaptive method is free of ad-hoc assumptions and among the cutting-edge methods with outstanding detection accuracy and stability. Based on the detection outcome, a lightweight and interpretable deep learning model (called ParaACE) is further built using the alternating conditional expectation (ACE) method. Our proposed ParaACE improves the prediction performance by 26 % and reduces the model size by 100+ times as compared to its Teacher model over various datasets. Furthermore, we show the great potential of our method for scientific discovery through interpreting various real datasets in the economics and smart medicine sectors. The code is available at https://github.com/zhangtj1996/ParaACE. 

Published as a conference paper at ICLR 2022
FAST GENERIC INTERACTION DETECTION FOR MODEL INTERPRETABILITY AND COMPRESSION
Tianjian Zhang Feng Yin 1,, Zhi-Quan Luo!
1 "Scooo of Science and Engineering, The Chinese University of Hong Kong, Shenzhen Shenzzen Research Institute of Big Data
t tianji aanjang link. cuhk. edu.cn {yinfeng, Luoz///ck..oog cn
ABSTRACT
The ability of discovering feature interactions in black-box model is vital to explainable deep learning. We propose principled, global interaction detection method by casting our target multi-arm bandits problem and solving it swiftly with the UCB algorithm. This adaptive method is free of ad-hoc assumptions and among the cutting-edge methods with outstanding detection accuracy and stability. Based on the detection outcome, a lightweight and interpretable deep learning model (called ParaACE) is further built using the alternating conditional expectation (ACE) method. Our proposed ParaACE improves the prediction per- formance by 26% and reduces the model size by 100+ times compared its Teacher model over various datasets. Furthermore, we show the great po- tential of our method for scientific discovery through interpreting various real datasets in the economics and smart medicine sectors. The code is available at http://ghhu...omm////gg//////au
INTRODUCTION
Explainable machine learning is an active research field that focuses on providing interpretable models, transparent explanations, and confident decisions practical AI systems. Investigating feature interaction vital to model interpretability. Interaction detection should be able to reveal which subset of features influence the output output jointly, and what the corresponding nonlinear transformation is. We aim to find the underlying interactions from data, such that we can interpret the model properly. To go one step further, we hope that new models be built with the aid of the detected interaction knowledge economically to avoid heavy parameterization.
In this paper, first restrict ourselves to interaction detection. A novel method is derived directly from the most acknowledged definition of feature interaction (Friedman et al. 2008). We further apply the obtained interaction knowledge design transparent and refined neural network (NN). This approach fits well into the data science life cycle Yu & Kumbier 2019), which was applied, for instance in Tsang et al. (2020a), successfully for interpretable recommender system design.
The main contributions of this paper include: 1) fast and principled interaction detection method, 2) a lightweight and interpretable neural network model that can surpass Teacher, 3) thorough theoretical analysis and performance evaluations with real datasets. More details are given below.
1. We propose generic interaction detection method based on a global statistical metric, namely the expected Hessian, Hij Ex and applicable to any pre-trained learning model, F(x), being for instance, deep neural network model or a tree model. It is also flexible to use for multi-way interaction detection.
8 F(x)
Notably, our method is model-agnostic
02,02,
2. To speed up the detection process, we evaluate the expected Hessian via adaptive sampling using the Upper Confidence Bound (UCB) algorithm (Lai & Robbins 1985), which can sig- nificantly reduce the computational complexity. Besides, thorough analysis of the proposed interaction detection method are conducted.
3. Using the detected interaction pairs, we further design a compressed but interpretable Student model which surpass its Teacher by 26 % terms of data fitting performance

---

Published as a conference paper at ICLR 2022
averaged over various datasets. The compressed model reduces its size over 100 times compared to the baseline fully-connected, wwrr-parameterized neural network (OverparaFC).
4. We demonstrate the linkages between our compressed model and the classic alternating conditional expectation (ACE) model (Breiman & Friedman 1985).
5. We conduct large-scale performance evaluations and further explain the obtained model interpretability with some real datasets.
The remainder of this paper is organized as follows. Section introduces all related works. Our proposed interaction detection method is introduced in Section B] By exploiting the detection outcome, a new variant of lightweight and interpretable deep learning model is introduced in Section Experimental results are given in Section 5 Finally, we conclude the paper in Section 6
RELATED WORKS
Interaction Detection: Early works adopt pure statistics for detecting feature interactions, and
representatives include ANOVA and GUIDE (Wonnacott & Wonnacoti 1990; Fisher 1992; Loh 2002). These works have motivated a plethora of new methods with the aim to enhance the detection accuracy and/or efficiency. The first class of methods centered around the GA ? M and tree models,
for instance Lou et al. 2013);; Sorokina et al. 2008); FFiedman et al. 2008); Lundberg et al. (2020) The second class of methods were built the so-called factorization machines (Rendle (2110) as
well as its new variants (Xiao et al.) 2017 Song et al.) 2019) with attention mechanism. The third
class exploits the most recent advances in deep learning, including the Neural Interaction Detection
(NID) and some new variants (Taang et al., 201 8a b. Cui et al.] 2019): Persistence Interaction
Detection (PID) (Liu et (0020, Integrated Hessians (IH) (Janizek al. 2020), Shapley interaction (Zhang et al. 2020 SSnndaaaraaan et al.) 2020). etc. Although we have witnessed well improved interaction detection performance for many datasets over the decades, the above methods still lead to inconsistent detection results for some other datasets. The reasons twofold. Firstly, the interaction strength is empirically defined, for instance, NID method computes the interaction strength via summarizing the neural network weights. Secondly, specific deep learning model is required, for instance, an f fgrregulaiized ReLU network is required by the latest NID and PID methods to maintain high accuracy. In contrast, our proposed method is derived directly from the definition of feature interaction (Friedman et af. 2008) and moreover is not confined to any specific learning model.
There are two categories of approaches to address model interpretabilityy namely the transparency-basee and post-hoc approaches (Došilović et al., 2018). Transparency- based approaches require the model itself be simple and interpretable, like linear models, decision trees, etc. One can directly read off the interpretations from their coefficients or decision rules. But often, they are less accurate due to limited representation power. In contrast, post-hoc approaches extract useful information from a pre-trained model, which is often complex and hard to interpret. Well-known methods such as LIME (Ribeiro et al. (0166) and SHAP (Lundberg & Lee| (017)) fall in this category, but they did not take feature interaction into account. Recently proposed symbolic metamodel (Alaa & van der Schaar 2019) captures nonlinear interactions by approximating the black-box model with explicit symbolic expressions. There are also some other post-hoc approaches based on sensitivity analysis (Cortez & Embrechts 2013). which return a quantification of fea- ture importance V4 E da:;
Model Interpretability:
(2F())) )²] (Kucherenko et al. 2009) and interactions Vij Fll F()( [2]
0z,0z,
(Roustant et al., 2014) by input perturbation. Our work aims to combine the strengths of the two categories. Concretely, we first extract the interaction knowledge by a post-hoc method, and then build transparent and interpretable learning model as illustrated in Figure 3
Model Compression and Knowledge Distillation (KD): Model compression (Bucilua et al. 2006) aims to learn a small compressed model (Student) from a large complex model (Teacher) with augmented training data produced by the Teacher. Compared to the Teacher, the Student can make similar or even better predictions. Knowledge distillation (Hinton et al. 2013) mainly deals with multi-class classification problems and extracts "valuable information that defines rich similarity structure over the data". Our work introduces a novel viewpoint of knowledge (the interacted relationships) and targets lightweight but more accurate Student model.
2

---

Published as a conference paper at ICLR 2022
3 PROPOSED INTERACTION DETECTION METHOD
Before diving into in-depth discussions of interaction detection, we need to formally define what feature interaction is. The textbook definition according to Friedman et al. (2008) is given below. Definition 3.1 (Friedman & Popescu 2008). function F R' + R is said to exhibit an interaction between two of its variables I, and 3; if the difference in the value of F(x) as result of changing the value of D3 depends on the value of zzj.
Equivalently, if Exx on 24, then we say 24 and 2j are interacted. Otherwise, 2; and z, have no interaction, if F(x) can be expressed as the sum of two functions fúz and füj (Sorokina et al. 2008), namely,
F
Dzydzz [=]
> O, namely the partial derivative w.r.t Ty turns out to be dependent
F(x) f (FI. -1-1, I.. Ep) + fu (#1..... 25-1
Tp)
where Aay) is irrespective to THg)- Similarly, higher-order (multi-way) interaction can be defined. In this paper, we mainly focus on pairwise interaction, while multi-way interaction is only briefly discussed due to space limitations.
3.1 INTERACTION STRENGTH MEASURE
Motivated by the above definition of interaction, it is natural to take advantage of the Hessian matrix H := F(x). The magnitude of its entry 8 (x)) contains rich information about the local dz,
curvature at data point Note that F Fxx) is regression function here, not loss function. This idea was originally considered in the economics community (Ai & Norton 2003) and rediscovered for sensitivity analysis in Roustant et al. (2014). The goodness of F(x) essentially influence the interaction detection performance, see our Theorem M.2 in the supplement.
approximator can
We define g(x,
6² F(x) Du;da,
12 to measure the local interaction strength of the i-th and j-th a2
measure of the global interaction strength. If fi,j) 2 O, we say feature 2; and v, have weak interaction; otherwise, if fi, is significantly larger than zero, then 2; and xy have strong interaction. In this paper, we focus on the global interaction.
features at point x. We then use f(i.j)
Ex [x(x,,,)))
Ex
3.2 INTERACTION STRENGTH EVALUATION
The above defined global interaction strength f(i.j)
0² F²x(() 2 mostly unavailable due to the unknown in- Bu.Bu
Ex
P(x). The Monte Carlo method can be used to approximate it by computing the sample mean over the training data(Roustant et al.) 2014).
put distribution
A
The Hessian matrix 22 F(x) for neu- ral networks a certain data point can be calculated analytically and efficiently, by using the automatic differentiation (Paszke) al. 2017). However, using this analytical solution prob- lematic for some learning models, such as the ReLU network, Random Forest (RF), etc., see supplement A For example, the landscape of a ReLU network is piece-wise linear shown in Figure [ thus the exact Hessian is a zero matrix at almost every point. So, we turn to the following numerical evaluation for broader horizons.
Analytical Evaluation:
X,
Figure I: The landscape of a ReLU network with two inputs (X1, X2).
Numerical Evaluation: Finite difference method is common way to approximate the Hessian given data point (Campolongo & Braddock 1999). i.c.,
Fx) ~ 4hühg
[F e,h, + e,,,,) F(x + e,,, - eey
0æ,00;
- F + eyhh -,h,,) + F(x - e,/, - -e,h,)
3

---

Published as a conference paper at ICLR 2022
where e; is one-hot vector with the i-th element being equal to and the rest of elements being zeros. We also note that if the computation of gradient 5F is cheap (e.g., F is a neural network), then 8x
Hij can be approximated as 2h dz:
@Fix+e,h) 0F(x-e,h))
to reduce computation, which similar
das
to the feature interaction score defined in Greenside et al. (2018). The choice of perturbation size h2 or by (abbr. ((g)) is critical. Generally, we do not want h2g) to be too small (incurring round-off error) or too large (incurring truncation error) to get a good overall approximation of the derivative (Jerrell 1997 Baydin et al. 2018). For our problem, we particularly do not want hyg) to be too small so that the four evaluated points (shown in the numerator of Equation D lie on the same hyperplane (e.g., region A in Figure D. which makes the quantity in Equation always zero The following theorem reveals that choosing a sufficiently small hug) is not necessary.
Theorem 3.1. For any x and y. function shows no interaction between them, i.e., it can be decomposed as F(z, y) a(x) + b(y) if and only if. for any h, k 0, F(r + h, + k) F(x h,y k) F(x h,y y + k)) + F(x h. k) = 0.
The magnitude of the numerator in Equation T tells us whether F locally separable for variables x, and 2j at point x, see our proof in supplement B
The main issue of the finite difference method lies in the computational complexity for approximating the global interaction strength ((,, especially when the function evaluation itself is expensive. Using all the training samples for finding just few strongest interaction pairs can be a total waste of computation resources. In general, for dataset with N samples in p-dimensional feature spaces, a total number of 4Np(p- - 1)/2 arithmetic evaluations of the surrogate regression function F are needed. If the Hessian happens to be sparse, that is, there are only a few interactions existing in the ground truth function, massive evaluations on those feature pairs with zero interaction strength should be avoided.
3.3 IDENTIFICATION OF THE k-STRONGEST PAIRWISE INTERACTIONS
In practice, do not have to obtain the interaction strengths for all interaction pairs, because many of them are simply too weak to have an impact on the output, and the top k strongest pairwise interactions are well sufficient for data modeling and prediction. Finding the top l strongest pairwise interactions fits perfectly into the best k-arms identification problem in the context of multi-armed bandits.
Inspired by the recent work (Bagaria et al. 2018b), we can treat each entry of the Hessian Hig as an arm Ar (see Figure 2 Since Hessian is symmetric matrix, we only need to consider p(p 1)/2 arms in the set {.A, i-th row and j j-th column of the Hessian, we will evaluate the local interaction strength g(x;, i) on randomly selected training data point Xg. The strength (, j) can be regarded as a random reward, where X is uniformly drawn from the training data (x1,-... XN). For ease of notation, we let f(; E) == g(xg, i. as the random reward of the arm and define pr Eg (f:; {)] as the true mean value. Our goal is to find the best & arms with the highest mean reward.
[ra]) For example, if we choose to pull the arm for the
This reformulation is reasonable since the following three essential assumptions for multi-armed bandits (Slivkins et al. 2019) are satisfied.
a. Only the reward will be observed after each pull;
b. The reward for each arm is drawn independently and identically from its reward distribution; c. The reward for each round is bounded. Since we only consider functions F(x) defined on a compact set, if F is a continuous function and twice differentiable, its first- and second-orded derivatives are bounded accordingly.
3.4 DETECTING THE l- S-STRONGEST PAIRWISE INTERACTIONS WITH UCB ALGORITHM
In this section, we briefly introduce the UCB algorithm Lai & Robbins 1985) for finding the k-strongest interactions. Here, we design a sequence of estimators (fe(r)) for the mean reward of the arm A, and construct confidence interval (()). We let f((r) denote the estimator after pulls of the arm A.. Several assumptions need to be made before we give out the primary outcome.
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 UCB (1A,
m,)),,,k))
2
A.
I: For each urm {AA, x E [n]], compute an intiaal (1 6) confidence interval by running (og(n) stepe of the estimator to obtain: (P.(1) (1)
2: B = () () Ser best arms
(Ar
[n]) I/ of amss under consideration
4: while TRUE do iteration t. pick amm A, that maximizes ft 1) + C+(B 1) among arms in S.
5:
6:
if arm A,, is evaluated less tham rn times then
11 22
I
Refine the confidence interval and estimate the arm A,, updating the ostimator one more time.
else
Sct j..(t) to be the current mean of the arm and set C+((+) (+) O.
10:
end
UCBs(()
Cald
if Anm A, such that Vi (t(()) C.(t) < (t) C.((f) then
12:
Add A,, to
Ax(1)
Remove A, from the set under consideration, that S S (AA.).
14:
if the size of B. [B] = k. then
16: end if
AD
17:
end If
end while
Figure 2: Top Left: The entries of the Hessian are treated as arms. Bottom Left: Illustration of the notations used Algorithm|] []] This is snapshot taken iteration where the colored solid bar and the red dashed bar are the true mean reward and the current estimate for each arm, respectively. At each iteration, the arm with the highest UCB will be pulled. Right: Pseudo-code for the UCB algorithm.
Assumption 1. Finite mn evaluations of one arm are sufficient to obtain an accurate reward. Assumption 2. Estimators fe(r) are su-suaaaassinn.
Assumption 2 satisfied because the reward is bounded (Hoeffding's lemma, 1963). Here, d, are pre-defined parameters. In the following analysis, we will choose a = max, (ar), such that all fe(r) are o-subgaussian.
Let fe(r) = 1 f(r; and we construct the 5 confidence intervals (see supplement C of fe(r) as,
2x log
C(0==
i m if > m
(2)
H, [f(0) ((()))((()))) C(O), fe(r) + c(O) w.p. 1-8, 8,
where H, denotes the true expectation. Increasing number of pulls of one arm, the uncertainty of the reward for that arm will decrease. When the number of pulls reaches m, the uncertainty of the arm and set C(c) = 0. Let (t) count the number of pulls of arm A, till iteration t. To simplify the notations, we let (t) = fe, (r) and Ct(() = C(G,(tt) be the sample means and confidence intervals iteration Now, we formally introduce the complete procedure in Algorithm
remove
The Algorithm I is initialized by evaluating all arms O(lo((n) times, then each subsequent iteration, it picks the arm with the highest UCB, i.e., max; [iz (t) C,))). to evaluate (see Figure 2 one arm has been evaluated for m times, we will its true mean value and the uncertainty to zero. At the end of each iteration, if there exists one arm whose Lower Confidence Bound (LCB) is higher than all the other's UCB, we will put into the set best arms.
In the following, we give theoretical analysis on the complexity of this algorithm. We have to further define (k) = max(0, P4; /4),, where it is the index for the k-th best arm and A indicates the gap of true values between the top-k arms and the rest.
Theorem 3.2. With probability 1 0 -(,)), given maximal pulling times m for each amm, Algorithm
returns the k-strongest interaction pairs in O Σn= log(n) (- (1)
log(nm) (Plgggmm))
Am/ time, where (- (AA.)
short for min(:,).
5

---

Published as a conference paper at ICLR 2022
Remark 3.1. When & < n,, the complexity of Algorithm for finding the top k interactions is On (mn) (n) + km log(n)) under some natural assumptions on the distribution of Ds being superior the naive algorithm (every arm is pulled times) with complexity (
Remark 3.2. For k = 1, namely the strongest interaction pair identification, it requires at most 8a² (a log(n'm) m)) m) pulls. We leave the complete proof in supplement C
3.5 EXTENSION TO MULTI- WAY INTERACTION
dz,dz, dhra ji,,,,)) and the higher-order ones can be approximated by the finite difference method as well, but the computational complexity will increase geometrically. For remedy, one can detect higher-order interactions from the obtained pairwise ones. For instance, based on the k-strongest pairwise interaction strengths, we can further construct an undirected graph G, in which each node represents feature. We develop Algorithm 2 detect the multi-way interactions through checking all the cliques in the graph G. and more details are given in supplement(i [ Despite the computation complexity, to use because the associated learning model is agnostic and the form of interaction is adaptive as compared with some existing methods, such as Min al. (2014), which relies on a logistic regression model and multiplicative interactions of particular form.
Similarly, the third-order derivatives 8
proposed algorithm is more advantageous
4 MODEL COMPRESSION WITH DETECTED INTERACTIONS
The detected interactions can be used for designing structured and more transparent models. A similar idea was mentioned in Tsang et al. (2020b). But we propose new architecture called Parametric ACE (ParaACE), inspired by several seminal works on Generalized Additive Model (GAM) (Hastie) 2017) and (nonparametric) Alternating Conditional Expectation (ACE) method (Breiman & Friedman The original ACE method is based on the following model,
1985).
((Y) Σ òu (Xx) +e,
and solves for the optimal transformation functions {0, (1..... Opp nonparametrically in the Hilbert space. However, it only considers transformation of each single feature and is time consuming for large feature dimension p. We build the ParaACE model with the detected interactions
(xx; 1 (0.).))=) == Bo + Σ B,s, (z.: + Σ Spterss (xZ, Or,),
(5)
where {Ir) is a set of indices for the detected interaction pairs, 8; and r; are the transformation functions for single feature and interacting features with the corresponding parameters {0,,) } and {0r.). ). ( is a weight vector for the output of all the transformation functions.
The new architecture is shown in Figure with two meta layers: the optimal feature transformation layer (Equa- 5ion boxed in red and green) and an optional fix-up layer (boxed in yellow). The optimal transformation layer gives the transformation functions of both the main effects and interacting features explicitly. The fix-up layer can be un- derstood the inverse function for the optimal transforma- tion of the output, O(Y), in the original ACE (Fquation 4 Another functionality of the fix-up layer is to alleviate the negative impacts of the wrongly detected interactions the output. More explanations are given in supplement H
Identity
Input
te(Fs)
I1
322
Output
3 p
altual
Optimal
Optional fte-up
transformation
layer
Candidate
interactions
ResNet
layer
We highlight the advantages of this model as follows: 1) interpretable, unlike many other models, ParaACE model gives explicit transformations of features, making it interpretable. 2) lightweight, this model can significantly reduce the number of parameters from the original one, and unlike the pruning technique (Han et al. 2015), it does not need extra memory store the indices of the preserved weights.
Figure 3: Parametric ACE model.

---

Published as a conference paper at ICLR 2022
3) flexible, the structure of NN is modularized by blocks, which is easy to plug in/off for other applications. The fix-up layer can be redesigned as block-wise subnetworks to capture high-level interactions, end up in the shape of a hierarchical deep network.
EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Datasets: We generated 10 synthetic datasets (p 10) as was used in Tsang et al. (201 8a) to test the accuracy of different interaction detection methods. We added a scaled Gaussian noise "7 0.1 N (0. 1) to get the noisy data. We also selected 5 real datasets, namely the Elevators for controlling an F16 aircraft (Itorgo 2019), Parkinsons for predicting the total UPDRS scores (Tsanas)
et al. 2009). Skillcraft for game player behavior analysis (Thompson et al. 2013), Cal housing for house price prediction (Pace & Barry 1997). and Bike sharing for predicting hourly bike rental count
Fannaee-T & Gama 2014). The datasets are preprocessed, and details are shown in supplement DD]
Neural Network Configuration: For the baseline OverparaFCC (Teacher), we used the architecture of p-5000-900-400010000 100-30-1 (indicating deep neural network with p inputs, one output, and hidden layers with 5000, 900, 400, 100, 30 neurons, respectively), which is a standard ReLU network with the last hidden layer being linear. For the ParaACE model (Student), the size of the network mainly depends on the number of candidate interactions we choose; more interactions imply more blocks. However, the configuration for each subnetwork is fixed, the structure of which is 1-50-8-1 for main effects and 2-50-8-1 for pairwise interactions. These subnetworks are ReLU networks with linear output. The fix-up layer is chosen as a single layer ResNet with the number of neurons equal to 15. All the above networks were initialized with Kaiming's 's strategy (He et al. 2015).
Optimizer Setup: We chose adam (Kingma & Ba 2014) as the optimizer, with the default setup in MXNet (Chen et al. 2015), and the batch size set to be 500 for all the datasets.
5.2 PAIRWISE INTERACTION DETECTION
We first test on 10 different synthetic datasets (p 10) (Tsang et al. 2018a to show the superiority of our proposed method. Datasets with higher imput dimensions (p = 50, 100) were compared as well, see supplement F. To compare the detection performance of different methods,
adopt the we compared our proposed method with various existing methods, including ANOVA (Wonnacott & Wonnacott 1990). AG (Sorokina al.) 2008). IH (Janizek et al. (2020), NID (Tsang et al. (0188)), and PID (Liu et al. 2020). HierLasso (Bien et al. 2013) and RuleFit (Friedman et al. 2008) have been omitted due their weak performances. For our method, we pick the same number of data samples n = 10000 for the training of OverparaFC and run 5 independent Monte Carlo tests. In Algorithm [ we pull each arm 3 times for initialization. Fach arm will be pulled at maximally m = 100 times, and we terminate when k = 20 strongest interactions stand out. We take ü., (1) upon termination as the final scores for our method. In this experiment, our proposed method needs around 1500 pulls of arms to pick out the top 20 interactions, however, naively pulling each arm 100 times needs 100C? = 4500 pulls in total.
ROC-AUC metric (see supplement
E In Table
Table 1: Interaction detection methods in comparison. ROC-AUCs of pairwise interaction strengths proposed by (with ha(s) 0.8) versus various baselines on a test suite of synthetic functions (see Table 4 in the supplement).
ANOVA*
AG
IHP
NID
PID
Our m
0.992
0.0
0,989
0.970 1 9.2c 3
0.986 1 4.1c
0.947 1: 2.5c
0.468
0.88 : 1.4e- 2
0.968
0.79 - 3.10 2
0.804
5.70 2
0.944 3.2c
[((
0.657
0.0
0.999 + 2.0e-3
1.0.0
1 1.0 0.0
F((
0.563
0.999 + 1.4e-3
1
0.85 = 6.7e-2
0.935 3.9e
0.997 = 2.7e-3
Fx(x)
0.544
0.67 + 5.7e-2
0.0
0.988 + 2.3e-2
Fa(x)
0.780
0.64 + 1.4e-2
0.932
0.98 + 6.7e-2
0.925 + 3.7e-2
[(()
0.726
0.81 1: 4.9c
0.611
0.84 1 1.76-11 2
0.888 1: 2.8c 2
0.714 1: 7.0c
Fx(
0.929
0.937
1 1.40 3
0.954
0. 0.989 1 4.40 3
1.0
0.984 + 4.2c
Fx(
0.783
0.808 1 5.7e-3
0.831
0.83 - 5.3e-2
0.972 -: -
0.948 + 4.6e-2
(x(
0.765
0.0
1
0.995
9.5e-
0.987 + 3.5e-2
0.0
average
0.721
0.87 + 1.4e22
0.931
0.92 = 2.3e-2
0.957 + 6.2e-2
0.945 = 5.6e-3
Time (6)
132
0.007
14.7
Small standard deviation means high stahility, post- hoc method, model agnostic method.
7

---

Published as a conference paper at ICLR 2022
From the results, we conclude the following: (1) PID outperforms all others; (2) proposed method is as competitive as the PID method; (3) while the average performance of our method is only slightly worse than the PID method due to the poor result dataset 7: this is due to the term
[+(2225202788) in (x(x) has little impact on the output, and such interactions are hard to detect. Apart from the above facts, both NID and PID work by analyzing the connectivity of NN, which strongly relies on specific sparse ReLU networks and empirical interaction strength computations, and thus are risky to generalize and may fail for some other datasets. For instance, for the function (x)(x) = ufrr + xgrgutta the ROC-AUÇ of NID degrades to around 0.69, while our method maintains 1.0 robustly. Moreover, our method is model-agnostic and can be directly applied to any pre-traines trained learning models, such as tree models, kernel regression models, etc., which is impossible for other methods.
5.3 MODEL. COMPRESSION WITH INTERACTION KNOWLEDGE
In this section, we construct a Student model with the learned interactions. With the interaction knowledge extracted from the Teacher model, we first show that the Student model trained under the same setup can achieve vell-improved prediction accuracy (on average). We use normalized RMSE RMSE measure the performances of all competing models such
(NRMSE), which is defined by that the comparison across different datasets is fair and convenient.
Fmua - -umin
For synthetic data, we use 800 training samples and 200 test samples. The noise 1j is injected described earlier. We choose the top 20 pairwise interactions with our new detection method to build the ParaACE model. We compared our proposed ParaACE with OverparaFC, KD for regression (Chen et al. 2017), and two recent pruning methods known as Lottery Ticket Hypothesis (LTH) Frankle & Carbin, 2019) and SynFlow (Tanaka et al., 2020). The results are shown in Table 2 As we expected, the KD method shows similar performance as the OverparaFC, because the Student model tries hard to approximate its Teacher. However, our ParaACE model can improve the performance of the OverparaFCC by 26.0 26.0% on average, and the model compression ratio (CR ==
parameters in uncompressed modal, parameters in the compressed model
is around 300. More details can be found in supplement L We also
found that the ParaACE model is sample efficient. To be concrete, the ParaACE trained on a small training set can surpass the over-parameterrzed NN trained with substantially more data, see Figure 13 in supplement K
Table 2: NRMSE of the baselines: OverparaFC, KD, and LTH versus proposed ParaACE tested on the synthetic datasets in T (The results were averaged over 5 folds.)
F;
Fg
Fg
F2
F;
Fg
F-
Fs
Fg
F10
Average
CR
OverparaFC
0.026
0.054
0.059
0.062
0.042
0.041
0.018
0.024
0.032
0.023
0.038
KD (student)
0.029
0.055
0.061
0.064
0.041
0.042
0.019
0.024
0.032
0.024
0.039
278
LTH
0.027
0.044
0.032
0.032
0.039
0.033
0.018
0.021
0.029
0.025
0.030
18
SynFlow
0.025
0.048
0.034
0.035
0.039
0.031
0.015
0.018
0.026
0.022
0.029
280
ParuACE
0.025
0.035
0.031
0.030
0.038
0.025
0.016
0.019
0.023
0.021
0.026
283
For real-world datasets, we built the ParaACE model with the top 50 pairwise interactions for Elevators, Parkinsons, Skillcraft, Bike sharing, and the top 20 pairwise interactions for Cal housing (since the number of features is smaller). For most datasets, the detected interactions can help improve the predictive performance and significantly reduce the model size, see Table 3 for detailed results. The comparison with KD is omitted as it is supposed to be close to the Teacher.
Table Performance comparison between OverparaFC, LTH, SynFlow, and ParaACE on real- world datasets. (The results were averaged over 5 folds.)
OverparaFC
LTH
SynFlow NRMSE
ParaACE
Datasets
NRMSF
Parameters
NRMSE
CR
CR
NRMSE
Parameters
CR
Elevators
16599
0.0483
4999461
0.0523
0.0479
120
0.0475
39848
125
Parkinsons
S875
20
0.0251
5009461
0.0180
87
0.0229
120
0.02204
40946
122
Skilleraft
0.0937
5004461
0.1228
120
40397
124
Bike sharing
17379
15
0.0403
4984461
0.0404
87
0.0405
120
0.0420
38201
130
Cal housing
20640
0.1059
4949461
0.1038
87
0.1026
120
0.1022
16388
302
Due to space limitations, we give more results for classification tasks in supplement Furthermore, show the performance gain induced by interaction detection via ablation study in supplement N
8

---

Published as a conference paper at ICLR 2022
5.4 MODEL INTERPRETATION
For synthetic data, we take (x) sinh (x) + x2) + arceos (tanh( + 2s + x7)) + cos(24 + ars) + sec(2777g) an example. Three dominant pairwise interactions {æ1, x22), { ( have been detected successfully and visualized in Figure (left). The ground truth transformations are shown in the upper part of the figure. Besides, the transformations for the single features can also be learned accurately. Taking Fx(x) exp a1 x22 | (13)lsal log("} + + 2² <g)) + 29 + T+ for example, wherein feature d6 is not involved, mg is linearly transformed, and 310 is transformed by function. All of them correctly learned shown in Figure (right).
(5(
(gg)
2E 1- 03 6a 16
sinh(x1 22)
co8(24 + 25)
sec (ec(
(110)
ground truth $10(-)
Figure 4: Visualization of the transformations in F1o (left) and F3 (right).
For real applications, first take the Cal housing dataset for further analysis as less expert knowledge is required. From Figure we can easily recognize that {longitude, latitude) and [IotalRooms, Iotalleerroooss show strong interactions. This makes sense, because {longitude, lati- tude} indicates the location, and
indicates the fraction of bedrooms. Also in the Parkinsons dataset, find (Age, Sex) interacted, which is consistent with the result that "age at onset (of Parkinson's disease) was 2.1 years later in women than in men" in Haaxma al. (007)) Interaction detection may also have significant impact drug combination discovery (Julkunen et al. 2020). We applied our interaction detection method on an RF model trained with the Drug combination dataset. Among the top 34 detected drug-drug interactions, 15 pairwise interac- tions have been verified in the DrugBank database (Wishart et al. 2018) (see supplement J These results confirmed the effectiveness of our interaction detection method and strongly call for careful investigation of the unexplored drug pairs, potentially of great value.
Parkinsons
Drug combination
housing
longkude
lsttude
10-
hous Mousing Medivii
Iire upp
totalhtomms
20-
coterbedroomr
populacion
houveholls
Swener
medianincome
bingrtude
housin Age
Lartude
Ree nos
forrettalds
medianencome
40
10
20
30
40
FDA spproved drous
Figure 5: Heat maps of interaction strengths for Cal housing, Parkinsons, and Drug combination data. Note that darker color indicates stronger interaction.
CONCLUSION
This paper proposed fast, generic, and model-agnostic interaction detection method. thorough analysis of the computational complexity of our adaptive method proved its superior efficacy. The detected interaction knowledge can further exploited to build a novel Student model, called ParaACE, which is compact, more interpretable, and mostly more accurate than its Teacher and other competing methods. We also showed experimentally that our ParaACE model sample efficient owing to its simple architecture. Its model-aggnssie property enables tremendous applications in different domains of finance, medicine, biology, wireless communication, where a significant number of well- performed black-box models have been built but not interpreted yet.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was supported by Guangdong Provincial Key Laboratory of Big Data Computing and by NSFC under Grant 61731018. The corresponding author is Feng Yin.
REFERENCES
Rishabh Agarwal, Nicholas Frosst, Xuezhou Zhang, Rich Caruana, and Geoffrey E Hinton. Neural additive models: Interpretable machine learning with neural nets. arXiv preprint arXiv:2004. 13912, 2020.
Chunrong Ai and Edward C Norton. Interaction terms in logit and probit models. Economics letters, 80(1):123-129 2003.
Ahmed M Alaa and Mihaela van der Schaar. Demystifying black-box models with symbolic metamodels. NeurlPS, pp- 11301-11311, 2019.
Vivek Bagaria, Govinda Kamath, Vasilis Ntranos, Martin Zhang, and David Tse. Medoids in almost- linear time via multi-armed bandits. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenty-Firs First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 500-509, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018a. PMLR.
Vivek Bagaria, Govinda M. Kamath, and David N. Tse. Adaptive Monte-Carlo optimization, 2018b.
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):1-9, 2014.
Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: survey. Journal of machine learning research, 18 (153), 2018
Jacob Bien, Jonathan Taylor, and Robert Tibshirani. A lasso for hierarchical interactions. Annals of statistics, 1113::1111, 2013.
Leo Breiman and Jerome H Friedman. Estimating optimal transformations for multiple regression and correlation. Journal of the American statistical Association. 80(391):580-53) 1985.
Cristian Bucilua, Rich Caruana, and Alexandru Niculescu-Mizz Model compression. In Proceedings of the 12th ACM SIGKDD international conference Knowledge discovery and data mining, pp- 335-541. ACM, 2006.
Francesca Campolongo and Roger Braddock. The use of graph theory in the sensitivity analysis of the model output: a second order screening method. Reliability Engineering & System Safety, 64 (1):1-12, 1999.
Guobin Chen, Wongun Choi, Xiang Yu, Tony Han, and Manmohan Chandraker. Learning efficient object detection models with knowledge distillation. In Advances Neural Information Processing Systems, pp. 742-751, 2017.
Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. MXNet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint arXiv:1512.012774 2015.
Paulo Cortez and Mark Embrechts. Using sensitivity analysis and visualization techniques to open black box data mining models. Information Sciences, 225:1-17, 2013.
Tianyu Cui, Pekka Marttinen, and Samuel Kaski. Learning pairwise interactions with Bayesian neural networks, 2019.
Filip Karlo Došilovié, Mario Brčić, and Nikica Hlupić. Explainable artificial intelligence: A survey. In 2018 41st International convention on information and communication technology, electronics and microelectronies (MIPRO), pp. 0210-0215. IEEF, 2018
10

---

Published as a conference paper at ICLR 2022
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::/archii/ ics. www.uciieeuuua...
Hadi Fanace-T and Joao Gama. Event labeling combining ensemble detectors and background knowledge. Progress in Artificial Intelligence, 3(2-3)1113-122 2014.
Ronald Aylmer Fisher. Statistical methods for research workers. Breakthroughs in statistics, pp. 66-70. Springer, 1992.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Jerome H Friedman, Bogdan E. Popescu, et al. Predictive learning via rule ensembles. The Annals of Applied Statistics, 233):9669544 2008.
Peyton Greenside, Tyler Shimko, Polly Fordyce, and Anshul Kundaje. Discovering epistatic feature interactions from neural network models of regulatory DNA sequences. Bioinformatics, 34(17); i629-i637, 09 2018. ISSN 1367-4803. doi: 10. 10.009/biommommaiicstty7755 URL https
10,
Charlotte Haaxma, Bastiaan R Bloem, George Borm, Wim JG Oyen, Klaus Leenders, Silvia Eshuis, Jan Booij, Dean E Dluzen, and Martin WIM Horstink. Gender differences in parkinson's discase. Journal of Neurology, Neurosurgery Psychiatry, 78(8):819-88) 2007.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 15Xiv:1510.00149, 2015.
Trevor Hastie. Generalized additive models. Statistical models in S, pp. 249-307. Routledge, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026 1034, 2015.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv:1503.0253: 2015.
Giles Hooker. Generalized functional anova diagnostics for high-dimensional functions of dependent variables. Journal of Computational and Graphical Statistics, 16(3):709-732, 2007.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Luis Itorgo. Regression datasets (accessed: February 12, 2020), 2019. URL wwwph:tpp///wwte dec Fc. ut..pp.p//1tee st.upp.p//lloorrg//egresss inteeassssonDDDDaaaaa / html
Joseph D. Janizek, Pascal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks, 2020.
Max E Jerrell. Automatic differentiation and interval arithmetic for estimation of disequilibrium models. Computational Economics, 10(3):295-316, 1997.
Heli Julkunen, Anna Cichonska, Prson Gautam, Sandor Szedmak, Jane Douat, Tapio Pahikkala, Tero Aittokallio, and Juho Rousu. Leveraging multi-way interactions for systematic prediction of pre-clinical drug combination effects. Nature communications, 11(1):1-11, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
S Kucherenko et al. Derivative based global sensitivity measures and their link with global sensitivity indices. Mathematics and Computers in Simulation, 79(10)3300-3301 2009.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
11

---

Published as a conference paper at ICLR 2022
Benjamin Lengerich, Sarah Tan, Chun-Hao Chang, Giles Hooker, and Rich Caruana. Purifying interaction effects with the functional anova: An efficient algorithm for recovering identifiable additive models. In International Conference Artificial Intelligence and Statistics, pp. 2402- 2412. PMLR, 2020.
Zirui Liu, Qingquan Song, Kaixiong Zhou, Ting Hsiang Wang, Ying Shan, and Xia Hu. Towards inter- action detection using topological analysis on neural networks. arXiv preprint arXiv:2010. 13015, 2020.
Wei- Loh. Regression trees with unbiased variable selection and interaction detection. Statistica sinica, pp. 361-386, 2002.
Yin Lou, Rich Caruana, Johannes Gehrke, and Giles Hooker. Accurate intelligible models with pairwise interactions. In Proceedings of the 19th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 623-631, ACM, 2013.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In I, Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gareett (eds.), Advances in Neural Information Processing Systems 30. pp. 4765-4774. Curran Associates, Inc., 2017.
Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lec. From local explanations to global understanding with explainable AI for trees. Nature Machine Intelligence, 2(1):2522-588 5839, 2020.
Martin Renqiang Min, Xia Ning. Chao Cheng, and Mark Gerstein. Interpretable sparse high-order boltzmann machines. In Artificial Intelligence and Statistics, pp. 614-622 PMLR, 2014.
Thomas Muchlenstaedt, Olivier Roustant, Laurent Carraro, and Sonja Kuhnt. Data-driven kriging models based on fanova-decomposition Statistics and Computing, 22(3):723-738, 2012.
Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics Probability Letters, 33 (3):291-297, 1997.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Detioo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
William JE Potts.
Generalized additive neural networks. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 194 200, 1999.
S. Rendle. Factorization machines. In 2010 IEEE International Conference on Data Mining, pp. 995-1000, 2010.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016.
Olivier Roustant, Jana Fruth, Bertrand looss, and Sonja Kuhnt. Crossed-derivative based sensitivity measures for interaction screening. Mathematics and Computers in Simulation, 105:105-118 2014.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Proceedings of the 34th International Conference on Machine Searning-Volume
Learning- Volume 70, pp.
JMLR. org, 2017.
Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-295 2019.
Weiping Song, Chence Shi, Zhiping Xiao, Zhijian Duan, Yewen Xu, Ming Zhang, and Jian Tang. Autoint: Automatic feature interaction learning via self-attentive neural networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 19, pp. 1161-1170, 2019.
12

---

Published as a conference paper at ICLR 2022
Daria Sorokina, Rich Caruana, Mirek Riedewald, and Daniel Fink. Detecting statistical interactions with additive groves of trees. In Proceedings of the 25th international conference on Machine learning, pp. 1000-1007. ACM, 2008
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pp. 9259-9268. PMLR, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks with- out any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33, 2020.
Joseph J Thompson, Mark R Blair, Lihan Chen, and Andrew J Henrey. Video game telemetry critical tool the study of complex skill learning. PloS one, 8(9), 2013.
Athanasios Tsanas, Max A Little, Patrick E McSharry, and Lorraine O Ramig. Accurate telemon- itoring of parkinson's disease progression by noninvasive speech tests. IEEE transactions on Biomedical Engineering, 57(4):884-89) 2009,
Michael Tsang, Dehua Cheng, and Yan Liu. Detecting statistical interactions from neural network weights. In International Conference on Learning Representations, 20.8a.
Michael Tsang, Hanpeng Liu, Sanjay Purushotham, Pavankumar Murali, and Yan Liu. Neural interaction transparency (NIT): Disentangling learned interactions for improved interpretability. In NeurlPS, pp. 5809-5818 18, 2018b.
Michael Tsang, Dehua Cheng, Hanpeng Liu, Xue Feng, Eric Zhou, and Yan Liu. Feature interaction interpretability: case for explaining ad-recommendation systems via neural interaction detection. In International Conference on Learning Representations, 2020a.
Michael Tsang, Dehua Cheng, Hanpeng Liu, Xue Feng, Eric Zhou, and Yan Liu. Extracting and leveraging feature interaction interpretations. In International Conference on Learning Representations, 2020b.
Peter D Tumney.
Cost-sensitive classification: Empirical evaluation of hybrid genetic decision tree induction algorithm. Journal of artificial intelligence research, 2:369-409, 1994.
Martin J Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
David Wishart, Yannick D Feunang, An Guo, Elvis J Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayceda, et al. Drugbank 5.0: major update to the drugbank database for 2018. Nucleic acids research, (6741))D(074-1008,, 2018
Thomas H Wonnacott and Ronald Wonnacott. Introductory statistics, volume 5. Wiley New York, 1990.
Jun Xiao, Hao Ye, Xiangnan He, Hanwang Zhang, Fei Wu, and Tat-Seng Chua. Attentional factorization machines: Learning the weight of feature interactions via attention networks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI' pp- 3119-3125, 2017.
Bin Yu and Karl Kumbier. Three principles of data science: predictability, computability, and stability (PCS). arXiv preprint 1rXiv:1901.08152 2019.
Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang, Interpreting multivariate interactions in dnns arXiv preprint arX1v:2010.05045, 2020.
13

---

Published as a conference paper at ICLR 2022
Supplementary Document
Fast Generic Interaction Detection for Model Interpretability and Compression
A PROBLEMS WITH ANALYTICAL EVALUATION
In this section, first illustrate the conceptual difference between local and global interaction and then state the problems of analytical evaluation.
Illustration of Local vs. Global Interaction. A quick example showing the difference of lo- cal/global interaction is the MATLAB symbo (Figure (()). There is no local interaction inside the flat region, but two input variables globally interact.
Analytical evaluation works for neural networks with differentiable activation functions, egg- si sigmoid, tanh, etc. However, it problematic when use neural networks with piece-wise linear activation functions (PLNN), such as ReLU, Leaky ReLU, and so on. The Hessian will be zero matrix at every second-order differentiable point, and it will no longer provide information about local interaction. Imagine the function landscape is joint with many facets, and the interaction information hidden in the boundary of those facets (the set of non-differentiable points).
A simple example is checkerboard-like function, e.g., XOR function F(r1, 1 [ > 0}, where ø1, 22 are uniformly drawn from [-1, 1]. this case, 21 and 22 are clearly interacted, OF will be zero for almost all sampled points. The
however, the second-order derivatives 8 interaction information is hidden the line œ1 and x2 0.
(a) origin function
(b) approximated function
Figure 6: The MATLAB symbol. (a)Imagine the MATLAB symbol as the landscape of a function F(I1, ((),, there is no interaction locally in the flat region, but Φ and 22 interact globally, i.e., there no global decomposition F( x22) a(x;) + b(x2)) (b) (Problems with analytical evaluation) The function is approximated by PLNN, and the landscape is spliced by flat facets. The Hessian matrix is zero matrix on almost every point (no local interaction). but ø1 and ø2 still interact globally.
B PROOF THEOREM 3.1 AND DISCUSSION ON THE CHOICE OF
Theorem 3.1
For any and y, function F shows interaction between them, i.e. can be decomposed as F(x,y) = a(x) + b(y) if and only if. & h k > 0, F(r + h + k) F(x + h1 y F(x h, + k) + F(x h,y = 0.
Proof. (+) trivial. (+) We will directly have, wh, and Vz, y.-
F(x + + k) F(x h, k)
F(x h, y + k)
F(x h1 k)
k
k
F(x + h. + k) - F(x h, + b) F(x + h, - k) - F(x h, k)
h
With permission of Math
14

---

Published as a conference paper at ICLR 2022
Let l + 0, will have OF (x h, b) By
aF By (a: h, y) for any positive h; let h - 0, will have OF dr
OF Ou of y.
(z, 11 OF Ou
(x, k)) k) for any positive k. Thus, OF is irrespective of x and
is irrespective
By
Remark B.1. Theorem 3.7 can be extended for higher-order interaction with the same machinery.
Ave. AUC score versus h on synthetic datasets
0.95
Ave. AUC scom
0.90
0.05
PID
Our meihod
0.0
0.2
0.4
0.6
0.8
1.0
122
1.4
Figure 7: Average ROC-AUC score versus hug) on synthetic datasets. The error bar represents one standard deviation (5 folds).
A guide for the choice of h5g)- We empirically test the sensitivity of hag)), see Figure 7 For standardized features, we suggest using har) E [0.6, 0.9) as the rule-of-thumb.
Further discussions on the choice of hug) People may argue that for the interaction detection task, a small number of evaluations for each feature pair are already enough to get pretty good results, and the benefits of using the UCB algorithm is trivial. This is not always true. We address this from two perspectives in the following, First, in many scenarios, the function can only be evaluated sequentially, and the evaluation may be very expensive. The benefits of the UCB algorithm are revealed then. Second, we empirically study the performance of evaluating each arm evenly under different configurations (perturbation size ha()). and the number of evaluations for each arm). see Figure 8 The ROC-AUC scores were obtained from the OverparaFC model trained as described in Section 5.2 We expect that given the fixed perturbation size h, the ROC-AUC scores will rise as the number of evaluations increases. This is consistent with the observation that the bricks are brighter from top to bottom. Also, we observed that with a properly chosen h E [0.6, 0.9]. the interactions can be correctly detected with relatively small number of evaluations (the bricks are brighter in the middle, see dataset 3, 4, and 5). The corresponding reasons can be that (a) if h is too small, four evaluated points lie in the same flat region with high probability, which is harmful to interaction detection; (b) if is too large, some evaluated points may be out of the distribution of the training data, which makes the detected interaction strength less representative. Even though the suggestion of using 1xg) & [0.6, 0.9] is purely empirical, the plots here help us better understand the essence of statistical interactions and their detection process.
C PROOF OF THEOREM 3.2
Recall that we construct the 1 å confidence intervals of fe(r) as,
C(I) c(0= -
20 log
if f <
if f >
Pr E [f(()) C(O), fe(r) + c(O) w.p. 1
This is derived from concentration incquality (Inequality 2.9 in Wainwright (2019)). We set d which is small number and easy to analyze. We have, Lemma C.1 (high probability event/clean event). With probability (w.p.) 1 2. all true values fr lie in the their confidence intervals during the run of the algorithm.
2
mm
15

---

Published as a conference paper at ICLR 2022
Average AUC on the dataset 1
Average AUC on the dataset 2
# evaluations
# evaluations
0.9
0.8
0.0
0.05
0.35
0.65
0.95
1.25
1.55
0.05
0.35
0.65
0.95
1.25
1.55
# evaluations
Average AUC on the dataset 3
1.0
# evaluations
Average AUC dataset
1.0
0.8
0.8
0.05
0.35
0.65
0.95
1.25
1.55
0.05
0.35
0.65
0.95
1.25
1.55
evaluations
Average AUC on the dataset 5
1.0
evaluations
Average AUC dataset
0701 m1N
0.8
0.8
0.6
0.05
0.35
0.65
0.95
1.25
1.55
0.05
0.35
0.65
0.95
1.25
1.55
Average dataset
Average dataset
evaluations
evaluations
0.9
0.6
0.8
0.05
0.35
0.65
0.95
1.25
1.55
0.05
0.35
0.65
0.95
1.25
1.55
Average AUC the dataset 9
Average AUC the dataset 10
evaluaaionn
# evaluations
010-4
0.7
0.05
0.35
0.65
0.95
1.25
1.55
0.05
0.35
0.65
0.95
1.25
1.55
Figure 8: The ROC-AUC scores obtained for 10 synthetic datasets under different configurations of perturbation size (horizontal axis), and the number of evaluations on each interaction pair (vertical axis). We expect that given the fixed perturbation size h, the ROC-AUC scores will rise as the number of evaluations increases. This is consistent with the observation that the bricks are brighter from top to bottom. Also, observed that with properly chosen h [0.6, 0.9). the interactions can be correctly detected with a relatively small number evaluations (the bricks are brighter the middle, dataset 3, 4, and 5).
Proof. It's equivalent proof:
2
P([vt,Vr [n], In,
- n?
The opposite of this event
t and r, s.t., s.t, - -A(()) > Ct()).
Since we have,
2
P([1,, - (A) > (+(+)) <8= n 3 and we evaluate at most nm times (n arms, each arm pulled times).
P(33 and r, s.t., |p4 (t)(t) (t))) < 8nm
(union bound)
2 n
P([VLVr -00-) (.())) 2 1
(clean event)
16

---

Published as a conference paper at ICLR 2022
Using Lemma C.1
we restate Theorem 3.2 as follows.
Theorem C.2 (Restating Theorem strongest interactions with most
3.2
With probability 1 O ((1))), Algorithm
returns the k-
((
(240² A
S
Σ i=1
log (m() A m
local interaction strength evaluations. This takes O
(E log(n)
((-
(
(ollognmm m
time.
A
Proof. We first analyze the running of algorithm till the first strongest interaction comes out. If we choose update arm * i time t, then we have
(att) Ct(t) (t) (t).
(6)
For equation 6 to occur, at least one of the following three events must occur:
E (Az S p1; - -Ct(t))
& (i((1) 14 C((), Eg 4 MM μt S 20,
To see this, note that if none of E1, E1,E2, Eg occurs, we have
(2) μs + (0,(1)
(EEs (E)
(1) + c.(t)
Pi; iu + Cc; (1).
From Lemma C.1 E and &g do not occur during the run of the algorithm with probability - 2 because
w.p. (1-23) 2 n/ Ims 1m--)(() S C.().ii 1I
also implies w.p. 1 - @ (1)), the algorithm does not stop pulling arm until event Eg stops occurring.
Let ((w) index the iteration in which Algorithm I evaluaaes arm A; for the last time before declaring it to be the w-th strongest interaction. Let's first consider how many pulls needed for each arm to (1)
pick out the first strongest interaction. If C.(c!") arm A,, that is,
for arm A,, then stop evaluating
4 (1)
20 log 3mm
C,(G 0,
>
80²
log(n ( m) or (T(c!") 2 m.
Note that (t) denotes for the number of pulls of arm A, at iteration We will evaluate arm A4 at Sa² most م log(ném) mm) A m times. To pick out the first strongest interaction, we need at most M
evaluations satisfying
((
S0²
Σ i=1
log(n'm) A m (1)))
<
17

---

Published as a conference paper at ICLR 2022
This result can be extend find all top l strongest interactions coneretely,
80²
M <
log(n"
Am
(A
t=1
24
log(n Vm)
Am
(A
24
Jog(nm)
A m
Di=1 log(n) ((-
The Algorithm| takes O for maintaining a priority queue(to find the minimal LCB or maximal UCB) in each iteration.
m time, where (log((n) is the time
Ai
Theorem C.3 (Remark If we further assume that As N(7, 1), for some , and m en, for E [0, 1]. then the expected pulls of arms (over randomness in A;) satisfies
RIM] S On log(ne)) + km))
with probability - O n over randomness in Algorithm Thus, the expected running time is well bounded by On log (nm) log(n) + km log(n)).
Proof. This follows directly from the Appendix 2 of Bagaria et al. 20).
D DATASETS PRE-PROCESSING
D.1 SYNTHETIC TEST SUITE
To make our experimental results convincing, we follow the test suite ever used in Tsang et al. (2018)) with the details given in Table 4 Among others, F1 is widely used test function for interaction detection, which can be generated as described in Sorokina al. (2008). For all the other functions,
the input dimension is set 10, and I1,..., T10
s.3.d U(-1,1).
Table 4: Test suite of data-generating functions
(((x)
Ti 22g sin -xx (1g + 22))
29
1227
210
Fx(x)
/
2|1rg] sin (0.5..)) log( + unsl + 1)
2210] V 1 [xg]
2220
Fx()
exp (mn
222 apat (wx) |20| log( + 28 u² (rg)
+
x
Fi(x)
expl W1
| + [auzaal
(a |م4| (11 log(2)
ug a
2x)) 29
270
Fs(x)
1 u + 2 + exp(p4 + aa) + [ - 27| 23242110
Fo(x)
exp (1 + exp( (3 + st. 1) cas(as 3s)
23 2
|
F+(x)
(arctan(21) arctan(222)) max(xara 0) (#725,,22728))
I
Fx())
Fi4g 2 2 sin sin( 2g)) arcoos arccos(0..22j))
Fo(x)
tanh(2i72 + sgs4) / exp((zs + =w) log (1062773) + 1) 29 +
110
Fxo(x)
sinh (z, + 22) arcoos (tanh(zz 2, c0s 2z) sec (272g)
D.2
REAL DATASETS
All the real datasets are publicly available. We preprocessed the datasets as follows. For Parkinsons data, remove the column motor UPDRS and predict the total UPDRS. For SkillCraft data, the
18

---

Published as a conference paper at ICLR 2022
target is set to be LeagueIndex. For the Bike sharing data, the feature weather is converted into one- hot representation. Before feeding the data into neural networks, we performed data normalization first for all datasets.
The Drug combination dataset is processed as follows. There are 110 features extracted, among which the first 50 features are the concentration of 50 unique FDA-approved drugs, and the last 60 features are the one-hot encodings for the cell lines.
E ROC-AUC FOR PAIRWISE INTERACTION DETECTION
We calculate the ROC-AUC scores for the synthetic datasets, where the ground truth interaction pairs are known. To obtain the ROC-AUC value, two vectors are needed, namely the pairwise interaction score E I and ground truth E {0, 1]:4,, both them are dimension æ(p-1) = 45. By setting different thresholds for the pairwise interaction score ranking, different classifiers with False Positive (FP) rate and True Positive (TP) rate can be obtained. The ROC-AUC value is approximated from those (FP, TP) pairs by the trapezoidal rule.
F PAIRWISE INTERACTION DETECTION ON HIGH- DIMENSIONAL DATASETS
We created two new high-dimensional datasets by simply combining the 10 synthetic datasets considered in the paper. The new datasets have either 50 (using F1-F5) or 100 features (using F1-F10). The labels of the two datasets are the sum of the original labels in each dataset of input dimension p 10. The training sample size is increased to 500,000 to mimic big data. We compared 5 different model architectures and our method consistently outperforms NID, see the Table 5 below for the results.
Table 5: ROC-AUCs comparison for high high-dimensional datasets
ROC-AUC score (NID/Ours)
data size: 500,000 100
data size: 500,000 * 50
Big network' with main effect + Llreg
0.743/0.768
0.831/0.864
Big network without main effect 1.reg
0.699/0.700
0.803/0.855
Small network? with main effect + Llreg
0.731/0,744
0.836/0.859
Small network without main effect + Lireg
0.701/0.742
0.796/0.840
Standard big network without main effect
0.646/0.653
0.583/0.793
Big network: 1-5000-900-400-1000
Small network: p-140-100-60-200
Here we also report the computational complexity of our UCB-based interaction detection method. Due to the randomness of the UCB algorithm, the number of pulls fluctuates. Note that we select top = 200 interaction pairs for 100-dimensional case, and the total number of pulls is around 40000, while the naive approach needs 100 100 99/2 495000 pulls. We select top 100 interaction pairs for 50-dimensional case, and the total number of pulls is around 21000, while the naive approach needs 100 x 50 x 49/2 122500 pulls.
Discussion on High Dimensional Data: For high dimensional data, the Hessian matrix will be too huge to handle. One possible solution is focus on the important features. We may first take advantage of DSepLaFr(Shrkkuaar et al.] (017) or SHAP (Lundberg & Lee 2017) to screen out the most important features, and then apply our interaction detection method. If the number of important features is still too large to handle, we may use ANOVA and F-test to select an affordable number of interaction candidates to pull log(n) times, and explore the remaining pairs with a small probability, say 5%, like the common strategy used in reinforcement learning..
G EXTENSION TO HIGHER-ORDEL INTERACTIONS
We define three-way interaction follows, and higher-order interactions be defined similarly.
19

---

Published as a conference paper at ICLR 2022
Definition G.1 (three-way interaction). A function F among three of its variables T,, 2, and 2k if,
Rp -
IR is said to exhibit interaction
0 F() 0r,0r,0r
2
Exx
> 0.
The naive method to detect higher-order interactions is quite similar to FANOVA graph (Muehlen staedt et al. 2012). We give three examples of detecting higher-order interactions from the synthetic data. We detect the pairwise interaction strength first, then build weighted graph (the edge weight corresponds to the interaction strength). By setting proper number of clusters, higher-order interac- tions can be discovered correctly, see Figure 9
(a) = Tg + D243304 + 25 + dig2g
(b) y = e Dg + [22 /3| - 14 + (IrrدT) )2 + 28
+ 34 (ng) +2 (c) y = Fn a2 + 22
(b)
Figure 9: The nodes (features) are clustered correctly. The color of edges indicates pairwise interaction strength. Nodes with the same color belong to the same cluster.
Algorithm 2 Hie mieraachicaa Higher-Order Interaction Detection ion
Require: The target number of i-way interactions 1
Detect top-k(2) pairwise interaction via UCB algorithm.
2: Construct an undirected graph G based on the detected pairwise interactions.
3: Enumerate all the cliques the graph G.
4: for i. = 3, 4,...... .p do
5: if (3)
then
6: break
7: end if
8: Find c(i relime
(C e(+) every complete subgraph of C admits detected interaction)
9: Detect the top (0) stronggst i-way interactions in clu) via the UCB algorithm.
end for
11: return All the detected interactions with their strengths.
One drawback of the above naive clustering method is that it doesn't 't allow for the overlap of nodes, ie. variable may appear in several interactions (Fs in the test suite). To address the above problem, we propose the Algorithm 2 which detects the higher-order interactions hierarchically. We first construct an undirected graph from the detected pairwise interactions. To shrink our search space for higher-order interactions, we restrict ourselves to the set of all cliques e of the graph G. where clique C E in a graph is subset of vertices that are all joined by edges. We use g()) S C to denote the collection of the i-cliques (the cliques with vertices). For example, to detect 3-way interactions, one only needs search in the ((3), which contains the cliques with
c())) three vertices. Furthermore, we can shrink the search space to ceipp for é-way interactions, based on the detected (é 1)-way interactions (see line 8 in Algorithm 2). For example, while detecting 4-way interactions, we put 4-clique (2, 3, 4, 6) into consideration only if all the 3-way interactions (3, 4. 6), (2, 6). (2, 6), (3, 4, 6) exist. We then use the UCB algorithm to verify if the cliques
20

---

Published as a conference paper at ICLR 2022
in c Tefine admit the interaction relationship. In this way, we detect the i-way interactions from the
detected (i 1)-way interactions information.
The 3-way interaction strength can be calculated from Equation 8 However, with the order of interaction increasing, the number of function evaluations for one gradient computation increases geometrically. We do not recommend detecting the interaction whose order is higher than four, which is uneconomical to compute and hard to interpret. We found our proposed Algorithm 2 can successfully detect the higher-order interactions for Fs in the test suite
Fx)
[+ h(e; + ex.) M
+ex))
dr,On,00k
8h3
+ F(x + +
-xx)
(8)
F(x+ h ex) ex) F(x h(c; +x))
Fx h(e - c1)) F(x h--;; oj -c,))
H MORE ON THE PARAMETRIC ACE
In section 4, we introduced a parametric ACE model based on the following generalized linear additive model with main effects and pairwise feature interactions, namely,
((Y) Σ Bist (Kru 1s:) + Σ Spteri (XI, Or:) +e.
The consideration of interactions improves the model performance significantly, compare to General-
ized Additive Neural Networks (GANN)(Potts) 1999 Agarwal et 2020 see Table 6
Table 6: NRMSE of the GANN versus our proposed ParaACE network on the synthetic datasets in (Table 4.
(The results were averaged over folds.)
Fi
F2
Fs
F.
Fi
F6
Fr
Fi
Fu
Fig
average
CR
GANN
0.033
0.063
0.064
0.068
0.053
0.052
0.028
0.032
0.040
0.033
0.046
959
ParaACE
0.025
0.035
0.031
0.030
0.038
0.025
0.016
0.019
0.023
0.021
0.026
283
The idea behind the original nonparametric ACE algorithm (Breiman & Friedman 1985) is to alternate between an inner process for finding the optimal transformation functions of the inputs and an outer process for finding the optimal transformation function of the output.
Here, made several modifications. First, all the transformation functions represented by small subnetworks. Second, we reformulate the above regression equation approximately as
R
Y 8-1
Σ Bis: (Za, o..) +
Σ 1=1
Sptors (xI, 0r.)
(10)
Therefore, the uix-up layer shown Figure can be understood as the inverse optimal transformation of the output 0 (-). To be more general, 0 (-) takes all input transformations individuals instead of their high-level summary (weighted sum). Our parametric ACE then alternately tunes the fix-up layer conditioned the current optimal transformation layer (outer iteration) and tunes the optimal transformation layer conditioned on the current fix-up layer until some convergence condition is met.
Another important function of the fix-up layer is alleviate the negative impacts of wrongly detected pairwise interactions and/or undetected higher-order interactions altogether on the output. For this purpose, we could make this fix-up layer a network of small subnetworks, so that the whole architecture is a network of small subnetworks. Each subnetwork can be regarded as meta-neuroo that is expected to be more competent than any SOTA activation function. With such nice structure,
2 A demo can be found at htttt::/gituu..coo///iii 19tp:ttt99999/9/ 996/ParaACCF
GGANN is parametric version of GAM, which only considers the transformations of univariates (single features).
21

---

Published as a conference paper at ICLR 2022
have divided the hypeer-arametery naturally into blocks and the whole network can hopefully be made adaptive to new tasks more rapidly by tuning just a few blocks.
It is possible for ParaACE learn "contradictory" models, which present the same function (Lengerich et al., 2020). For example, the main effeet might be absorbed into the interaction effects. Thus the direct interpretation through subnetworks may sound that convincing. [Lnnerich et al. (2020) proposed an algorithm to purify the interaction effect by calculating the functional ANOVA (Hooker 2007), based on a piecewise-constant function F. This algorithm is applicable to any function F by first constructing a piecewise-constard approximation F. Particularly, for our ParaACE model, the overall computation will be much easier since we explicitly have the univariate and bi-variate feature transformation. The number of bins required to approximate ParaACE with f reduces significantly, and so does the complexity of the follow-up purifying algorithm.
I EXTENSION CLASSIFICATION TASK
We generated the datasets for binary classification from the synthetic regression datasets (1000 samples with injected noise). We choose the median of the target as threshold to separate each synthetic regression the dataset into classes. The comparison between the baseline OverparaFC and our proposed ParaACE in terms of classification accuracy is shown in Table For real-world datasets, we picked Higgs Boson (Baldi al. 2014), Spambase (Dua & Graff 201 7, and Diabetes (Tumey 1994).Bote the classification accuracy and the compression ratio are reported in Table X
Table 7: Accuracy of the bascline OverparaFC versus proposed ParaACE network on the synthetic classification datasets. The results were averaged over folds.
Fj
Fg
F5
F4
F;
Fi
Fr
Fg
Fg
F10
Average
CR
OverparalFC
0.955
0.896
0.887
0.872
0.907
0.939
0.964
0.971
0.932
0.953
0.927
ParaACE
0.908
0.94
0.916
0.96
283
Table 8: Performance comparison between OverparaFC and ParaACE on various real-world classifi- cation datasets.
OverparaFC
ParaACE Accuracy
Datasets
Accuracy
Parameters
CR
Higgs Boson
98050
28
0.698 + 3.0e
5049461
0.730 +: 2.8e -3
184
Spambase
4601
57
0.950 + 8.0e 3
5194461
0.950 + 7.9e
120
Diabetes
768
0.741 2.5c 4949461
0.789 1.7c
302
J DETECTED PAIRWISE INTERACTIONS FOR SYNTHETIC AND REAL DATA
Synthetic data:
Figure shows the pairwise interaction strength produced by our proposed method.
For the Cal housing dataset, we terminate the UCB algorithm when k 20 interactions stood out; for the other four datasets, we terminate at A = 50. The green, orange, and blue points represent the UCB, estimated mean, and LCB respectively. For the drug combination dataset, the results are shown in Figure
Real data: We provide the detected interactions for five real datasets in Figure 11
K EMPIRICAL RESULT FOR SAMPLE EFFICIENCY
Figure 13 shows our proposed framework is sample efficient. The data are from the test suite (Table and noise 17 is injected. Increasing the training sample size, both over-parameterized neural nets and proposed ParaACE perform better. But ParaACE is less data-hungry since fewer training samples
22

---

Published as a conference paper at ICLR 2022
X2
X1
14
X2
12
30
10
20
50
x30
23.32
F1
F2
Fi
F4
F5
X0.
11
34.
12.
80
30
19
F6
F7
Fs
Fg
Fi0
Figure 10: Heat maps of pairwise interaction strength proposed by our method for functions Fi-Fio (Table Cross-marks indicate the ground truth interactions.
are needed for ParaACE to achieve a similar performance of the over over-parameterized neural nets. The experiments show that ParaACE still performs well, even if with small training samples.
L DETAILS ON THE COMPARISON WITH KD, LTH, AND SYNFLOW
L.1 COMPARISON WITH KD
KD is widely used for multi-class classification problems, which extracts knowledge from the "soft label" by controlling the temperature. but fewer KD methods are there for regression problems. Currently, people mainly use the Teacher bounded regression loss (Chen et 2017) and the hint loss deal with the objective detection problem. Passing unlabeled data the Teacher model to produce pseudo labels can also help. In these ways, the Student is expected to have similar performance to the Teacher.
We let wver-parameterized FC 000-5000-90044001000-3300 with architecture 10-70-70-70-70- data and 4000 pseudo data (labeled by the Teacher). The loss function we adopted is L Hint loss, where the Hint loss is used on the layer with 30 neurons.
be the Teacher, and a ReLU network be Student. The Student trained with 800 original
It shows that KD trained with pscudo data and carefully designed loss function achieves similar performance as the Teacher, while ParaACE trained with original data and simple L2 loss achieves significantly better performance.
L.2 COMPARISON WITH LTH
We used the pruning technique proposed in the lottery tickets hypothesis (LTH) paper (Frankle & Carbin 2019). We pruned the fully connected neural network after every 20 epochs. Every time 20 % weights were pruned in each layer except for the last layer. We trained 500 epochs, and set the batch size be 400. We report the best test performance in each round of pruning in Figure [4
Figure 14 shows that, in most cases pruning the network properly can improve the model performance. But if the network was over-pruned, the performance may drop.
L.3 COMPARISON WITH SYNFLOW
We implemented the single shot SynFlow for regression tasks based the official code repository Intpp:://gitubb.com www.tuubb.ooggggaeeeeeeeee woom/ggnguii-ii Latngggliiab/SSaptiii----- Finoptt--Flow/// (Tanaka et al.] (222)). The sparsity set to 10 2.447 for synthetic datasets, thus the neural network is compressed 280 times. For real-world datasets,
23

---

Published as a conference paper at ICLR 2022
flevators
Confidence Interval each amm
divikote
3g
6.5
6.3-
5.1
100
Parkinsona
Confidence Interval for each smm
6.125
5,000
1,75
1.50
1.233
SWilCoof
0:215
0.302
-0.005
-6.21
125
Bike sharing
Confidence interval for each am
withert
witherr
-0.22
20
60
1do
Indea
Confidence Interval arm
lngllde
6.175
houingMadaaage
0.003
hountoke
8.052
rudi
6.002
8
6222
Armal
Figure 11: Left: Heat maps of pairwise interaction strengths on real datasets. Right: Confidence interval for each interaction pair. The green, orange, blue points denote the UCB, estimated mean, and LCB respectively.
24

---

Published as a conference paper at ICLR 2022
Drug combiration
Amfostire Cabatitzel
landerarilyy Minsantrone
Fetamustire phosphate sodium: Minworcinee
Vamodeglh; Catooloeel
Thingaanin: onree Seltinh
Megastrni anecnn M Inoortmnn
Thonganioe anr Mitoariioe
Temoudie dinate Cabentaaal
Thogranine: Oycrrbbii hydroclorise
Quinac the hyprochio Mc; Mizosantrone
60-
Thoggarine: Cobactzael
Vincistinn suftits Cabeohavel
Thinguavie:: Flourldine
Unadi mustard Cytorabite Sydorhhlordee
Cedltnt: Mimonntonn
Missaatronn: Cylarabrn hydrochior
00.
Goftink: Cytrabiie hedrcctoride
Missorttonn: Cabairaed
Mitsertrons: Roturdrre
Ruadiitiis: Vincrlliine
Cytarbiine tydicctioriee
tertpoxade;
Vinordlinee
hndrsclizride
Vinorelinne
Visorebiee buttrtte Cytambiine hydrochondee
Catar hool: Floqurtine
Craatinnt Micoontroe
Exerolimu;; Flesundrre
50/00A approved shupo
Figure 12: Heat maps of pairwise interaction strengths for drug combination data. The top 34 detected interactions are listed, among which 15 of them (marked in red) are verified in the DrugBank (Wishart et al. 2018).
compressed the model by 120 times. And we retrained the neural network after the single-shot prune ppost-training). Note that we did not prune the biases here.
We set the hyper parameters for the post-training process as follows. The batch size is to be 500, and the number of epochs is 100. We use Adam as the optimizer with Ir = 0.001, betas = (0.9, 0.99).
M ACCURATE APPROXIMATION FUNCTION BENEFITS INTERACTION DETECTION
Suppose the underlying ground truth function is f(x), and our approximation function is go (x)) we omit the 0 in the following. We show that the estimation eπтоr for Hessian Ex 02,0z,
o(x))) Ex 80,0s, fxx) is bounded by o(e). when [f() - g(x)
for all x. This im- plies more accurate pre-trained model leads to better interaction detection accuracy. According the following theorem, deep neural networks are good surrogate functions due to the universal function approximation capability (Hornik 1991).
Theorem M.1. Assume I; are uniformly drawn from [-1, 1, 1] independently, if there exist an such that fx) g(x)] S for all x E RP, then
8g((x)
0 fx)((x)
Ex
Ex
S.
Ox,
Proof.
8 g(x) dn,0rr
Ex
8 gx((x) dn,On,
p(x)dx
8 gg(()
Or,ON, pl Di));; (xxx,))xxx
= -/ p(x)(s) / 8 (x(x dz,0x,
p(a;, 23 dd
[where p(z,, = 1/4]
1 p(x)))) L'.''' 0 (x) da, da,
0x,02,
25

---

Published as a conference paper at ICLR 2022
where
[. Pg g(x)
Or, dr,dd,
0g(Xx (5s+ = 1, 1,,,)) - 0g -1, d
dx,
o( = 1, 1) g 1/: 31 1, -1)
(g(x) (i: = 21, = - g Xiis -1, 1)).
We can derive Ex
8" fix) (xg
in a similar fashion. Thus,
0 (x))
f(x(x
Ex
Ex
Ox,
Ex (0(x)15 Fi = 1, D.j. = 1) -
1, = 1)
4
((X(ij, = -1 = 1) + f(x,i)) -1, 1)
I(X = 1, = -1) + f(x)1)) = 1, =-1)
+ 1x =- -1, 1) - (x) = =11 = - 1)]
Ex [4c]
4
Theorem M.2. Assume T2 are uniformly drawn from [-1,1] 1] independently. and further assume
8 f(x)
gg(()
S M, (,,,)))))) If there exist an > 0, such that If(x) g(x)l S for all
TRP, then
0 gg((x)
27
fxx(x
27
Ex
Ex
$ 2Mc.
0x,Os,
Or,
Proof.
02 (x) dz,dr,
0 f(x) 27 Ex
Ex
dx,dr,
0
02 fxx) dx,0x
Ex
0x,0x,
0
0 sx))
On,Ür, + xP(())
pg(()
=Fx
0n,ün;
On,0x,
(Pg(x)
82 f(x)
)]
Ex ( (flg(x) G² f(x)
Ex
Ox,0x;
òr,Ox,
0x,0x, dr,dx,)
<e 2M (Using Theorem M.I)
Note that M can be interpreted as the magnitude of the strongest local interaction. For the functions with strong interactions, higher approximation quality is desired.
26

---

Published as a conference paper at ICLR 2022
Table 9; Ablation study show the effectiveness of interaction detection the synthetic datasets in (Table (The results were averaged over folds.)
Fi
F4
F4
F5
F6
F7
Fi
Fio
averige
CR
ParaACE (with random interaction)
0.026
0.042
0.035
0.060
0.032
0.025
0.044
0.031
283
ParaACE (with detected interaction)
0.025
0.035
0.031
0.030
0.038
0.025
0.016
0.019
0.023
0.021
0.026
283
N ABLATION STUDY FOR THE EFFECTIVENESS OF INTERACTION DETECTION
To show how much performance gain able to obtain from the interaction detection procedure. We conduct am experiment that input random pairwise interactions to ParaACE to compare with the one with detected interactions synthetic datasets, see Table
27

---

Published as a conference paper at ICLR 2022
Synthetic dataset
Synthetic dataset2
0.02
OuapantCC
Oversantc
1,11-
1000 18811
0.021-
-24
2.035
3,000
1,00
100
020
902
1200
1206
1403
1600
160
610
200
5000
1203
1/00
2000
1ambbr baaney samoks
rurber buaning sumpro
Synthetic dataset
Synthetic cataset
OeapiranC
Overurac
0.05
0.65
0.02
0.45
0.24
0.04
0.02
3.02
1030
Do samslks
number
samaks
Synthwilc delaset
Synthelic dataset
0.250
OverganFC Pariac
0.00
Overganti Paraact
3.655
0.33
2.030
3,000
0.230
3.15
400
520
802
1200
1200
1403
1000
160
630
3000
1202
1000
1000
number triiiing ramske
rumber of tr cample
Synthetic dataset 7
Synthotic dataset
OscrzaraC ParaACE
ParaAct
3.015
3.012
3.098
400
520
552
1000
1200
1402
2000
400
630
2000
1202
1400
2000
rumbet di Dannng sampro
Synthetic dataset 10
Overparaff
3.008
Overganfi PereAct
Far AACE
0.000
2,022
0.705
1nd WWet
2.000
0220
0.00
3.54
802
2000
1200
1420
1000
110
630
2003
5000
1202
1400
1.00
rumber of trilaan complie
Figure 13: Performance comparison on synthetic datasets while reducing the number of training samples. For each dataset, we tried different training data 5 times in one experiment, and the performances (of ten experiments) were all tested on the same test set. The error bar shows the maximal and minimal test NRMSE in 5 folds.
28

---

Published as a conference paper at ICLR 2022
Synthetic data
Real data
Thevstor: LTI
0.15
C653
0.12
0.10
C.5
6299
0.4
24
85
65
104
Megges Famdinng
Partera
Parterts Welges femanhg
0.54
0.45
0.00
0.37
035
034
Syrthere dntaret
Synthetic
Selleratt LTM
0.40
0.9
0.14
0.12
0.19
0.05
0.60
0.
Synthele datanet
Synthetic catanet
Bice shartng.
0.2
0.34
0.37
0.24
130
30
28
0.5
2.
65
124
Synthtic dollact S,LIH
Synchalic datanct 12. LTH
6.44
0224
0.244
0.04
0.00
0.3
0394
0.088
132
30C
20
6.
106
Figure 14: Performance comparison on both the synthetic and real datasets while reducing the percent of weights retained by the LTH. The error bar shows the maximal and minimal test NRMSE in folds.
29


Reviews:
[{"review_id": "vf0W-0SJw_I", "reviewer": "Reviewer_bpD2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper has several strong points as follows:\n\n- the authors propose the algorithm by building up from the first principles i.e. by inspecting the expected Hessian. Furthermore, the proposed finite difference method holds the promise of being a true model agnostic implementation. Such methods are of high importance and can be used in settings where the model is black-box by design or by method of delivery (e,g. a binary file)\n- The simplification of the problem to best k arms leads to a more computationally feasible solution. This is a novel contribution and the authors also explored this by conducting several theoretical analysis\n- The model compression algorithm presented by the authors is very interesting. By itself, its an interesting contribution and could perhaps be used independent of the interaction detection method. The performance achieved by this method is also highly promising (read more on this below).\n- Finally, the analysis on the consistency of the discovered interactions is very well presented and provides an insight into how the method can be used for other settings in a debug and develop method\n\n\nThe paper can be improved upon by addressing some of the aspects below:\n\n- The claim about model agnosticity of the method seems to be well supported. It would be also interesting if the authors can discuss whether their implementation can be framework agnostic e.g. can work with scikit-learn, pytorch, tensorflow models? The proposed methods seems to be gradient free and thus it would be interesting to comment on this\n- The assumption in 3.3 b sounds interesting. Can the authors provide more insights into why the draws can be considered coming from independent reward distribution? E.g. if there are higher level interactions present, would this first order interaction be somehow impacted by the order of the draw?\n- The presentation of the paper can be improved upon as well. For example, in table 1, the authors can consider annotating the methods by whether these are \"post-hoc\"/ \"model agnostic\" / \"statistical methods\" and so on\n- While the model compression method presented is very interesting, the claims about interpretability of the proposed model may need to be reduced and/or substantiated. The fix-up layer seems to introduce non-linear transformations and its not immediately apparent how would the model interactions directly be interpretable in that setting. For example, would a simple GAM on the interactions and their proposed model be equivalent? In general, the claims of interpretability  (valid from the interactions, perhaps unsubstantiated on the ParACE model) and compressibility may need to clearly separated out\n\nOn some other aspects, its not apparent why the ParACE model would provide such a boost in performance. Is this an artifact of the selected datasets or would such a boost be expected in general? It would be interesting if the authors can provide some insights into this aspect", "summary_of_the_paper": "Identification of feature interactions from black-box models, on a global as well as on a local scale, can lead to a better understanding of the operating modes of the black-box models. In this paper, the authors presented a principled approach to identify global interactions by casting the problem as a multi-arm bandit problem and proposes a solution using UCB algorithm. The authors claim that their method interaction discovery method is free of ad-hoc assumptions with good detection accuracy and stability. Furthermore, the authors showcase the importance of the learned interactions by proposing a new deep learning model based on these interactions and showcase the improvements in model size (thereby competing against pruning methods) as well as in accuracy (thereby competing against generalization methods). ", "summary_of_the_review": "Overall this is a very nice paper. Identification of interaction terms can lead to very novel analysis of the black-box models and can even lead to knowledge discovery e.g. discovering drug-drug interactions. The paper also seems to have 2 strong contributions where the proposed ParACE model leads to a very novel compressible architecture. The paper can be improved upon by addressing some of the aspects but even in its current state it will be of interest to the larger AI/ML community. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZdgriG_hVBG", "reviewer": "Reviewer_vh8A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The desire to consider hessian (and second derivatives in general) as the interaction strength is natural and has been discussed in the literature. \nThe authors add to this idea more effective estimation by evaluating only those elements of the Hessian matrix that can be valuable.\nHowever, the paper doesn't focus on the effectiveness of this multi-armed approach. Instead, they compare to other approaches for interaction detection from the literature.  \nWriting is mostly clear, while in some parts it is hard to understand the exact approach, so it can't be reproduced without source code provided.\n\nPros\n* The paper contains a lot of material to explore with many experiments in the main text and in the supplementary\n* Theoretical justification on why should it work in a form of a couple of natural theorems.\n\nCons\n\nExperimental results:\n* No experimental for the efficiency of the proposed approach on how does it work compared with the estimation of the full Hessian matrix\n* Only a low dimensional case is considered, while the method is designed to outperform others in terms of efficiency in high dimensions. Please, focus on providing evidence, that your method works well in high dimensions.\n* It would be interesting to consider simple architectures as an alternative to ParaACE, as other architectures seem to be too complex to learn well for a dataset of size 800. Also, the results will depend on correct applications of regularization techniques. Have you tried them?\n\nPresentation:\n* Language, in general, is either too simple in terms of used constructions or too hard to understand. Better to have another round of proofreading. Some examples:\n** With the increase of training samples -> Increasing the number of training samples (or \"the training sample size\")\n* No reference to Table 1 in the main text as well as some other tables. Please, provide a reference to them in the main text.\n* ROC AUC is a better term for provided scores than AUC, as you consider the ROC curve for the interaction detection\n* Figure 13: you have no uncertainty in sample size, so it should be not crosses, but vertical uncertainty bars (by the way, what are they? One, two, three STDs?)\n* I suppose, that you don't own the rights for the MATLAB logo (Figure 6), so maybe you should cite the figure source?\n* Figure 5: what is the color bar? Does darker blue color correspond to stronger interaction?\n\nTheoretical results:\nTheorem M.1 says nothing about absolute values of the elements of the Hessian matrix, only with non-absolute values.\nSo, if the approximation quality is good, in reality we can have pretty bad estimate for an integral $E_x |\\frac{\\partial^2 F(x_1, x_2)}{\\partial x_1 \\partial x_2}|$. For example, you can consider $F(x_1, x_2) = \\sin(w(x_1 + x_2))$. While this function lies in $[-1, +1]$, the intergral is proportional to $w^2$, which can take arbitrary large values.\n\nHard to reproduce:\n* Distillation approach never defined. As there are plenty of them out there, please specify, which one you have used. What is the exact loss function? \n* The notation in the definition of the NN architecture is not clear: p-5000-900-400-100-30-1, 1-50-8-1, 2-50-8-1 don't explicitly define the architecture \n* What is a ReLU network - unclear\n* Single layer ResNet - not defined \n\nDesign choices:\n* Why Kaiming’s strategy for initialization?\n* Typical batch size is a power of 2. Why 500 in your case?", "summary_of_the_paper": "The paper proposes to detect pairwise estimation using a more efficient evaluation of Hessian values via sampling based on the multi-armed bandit approach.", "summary_of_the_review": "The authors propose a more efficient method for hessian matrix estimation with little novelty and not comprehensive experimental results.\nIf experimental issues are resolved with experiments on real datasets of high dimension and comparison with a proper baseline, then there is a change for the acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BqaP3d9EbGC", "reviewer": "Reviewer_QLX7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n+ a fast and principled interaction detection method,\n+ a lightweight and interpretable neural network model that can surpass its Teacher, \n+ good theoretical analysis and performance evaluations with real datasets. \n+ method directly derived from definition of feature interaction\n+ the work has taken theory and material from multiple domains and plugged them at apt joints\n+ transferring the problem of feature interaction to multi-armed bandits\n+ supplement has proofs of statements and explainations\n+ apart from synthetic datasets, the real world datasets belong to non-intersecting domains\n+ code zip\n\nCons:\n- Upper Confidence Bound (UCB) algorithm is dated 1985 - has nothing else come up interim?\n- similarly comparison with classic alternating conditional expectation (ACE) model (1985) feels a bit outdated\n- some text book and paper definitions are repeated, instead could have just cited the prior art\n- the number of training samples in synthetic data could be increased and tried out at variant degrees\n- conclusion section is weak\n\nMiscellaneous:\n- theoretical analyses -> theoretical analysis\n- F (x), for instance, rewrite\n- explain why - an ‘1-regularized ReLU network is required by the latest NID and PID \n- The work uses established methods - extract the interaction knowledge by a post-hoc method, and then build a transparent and interpretable learning model - is this combination novel?\n- How is interaction different from functional dependency?\n- Finite m evaluations of one arm are sufficient to obtain an accurate reward. - is this assumption valid? upper bound of m in practice?\n- intelligent, unlike - > interpretable\n- parallelizable -> how powerful the smartphone is to support the feature?\n- explain more on the cross domain practical applications\n- recommended to compare with other state of art approaches in real analysis \n- using Matlab logo as function was cool :-)", "summary_of_the_paper": "The paper handles the important area of model that can be interpreted using feature interactions - aligned to theme of explainable deep learning. The authors chose to use the problem of multi-arm bandit, solving it by UCB algorithm with good speed and accuracy. A lightweight and interpretable deep learning model (called ParaACE), built using alternating conditional expectation (ACE) method is the crux of the work. It is shown that the proposed method improves accuracy by 26% and reduces the model size by 100+ times as compared to its Teacher model over various datasets. The paper has extensive supplementary material, as well as shared code.", "summary_of_the_review": "This paper is recommended for acceptance at ICLR. The paper is thoroughly written with sound technical backing - especially the code sharing and the content will help in improving the state of art in recent advances in explainable deep learning approaches for others to build on. The applicability in practical use needs more justification.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4d2jmSZMwd", "reviewer": "Reviewer_akne", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n- To my knowledge, no one has applied a multi-armed bandits approach to interaction detection\n- The ParaACE model is a nice idea for model compression, and it shows promise. The fixup layer, in particular, is a clever way to try to include higher order interactions to recover the performance of the full model. Most papers that use identified interactions to build a new model (e.g. https://www.cs.cornell.edu/~yinlou/papers/lou-kdd13.pdf) are primarily focused on creating interpretable models (not compressed models), and thus those papers do not include anything like a fixup layer (which breaks interpretability by including higher-order interactions). Thus, the very idea of extracting the pairwise interactions for the purpose of creating a **compressed** model (rather than an interpretable model) is, to my knowledge, novel - and I think difference in objectives is worth highlighting more prominently.\n- In a similar spirit to the point above, the authors show that ParaACE often surpasses the performance of its overparamerized teacher model; once again, this is a relatively novel angle to models constructed using learned feature interactions, because most such models are concerned about **matching** the teacher performance and rarely concerned about exceed it. By forfeiting interpretability with the fixup layer, ParaACE shows that constraining the model with the ParaACE architecture is a smart way to combat overfitting.\n- The authors have done a good amount of technical work to evaluate their approach in different contexts.\n\nWeaknesses:\n1. My main concern is that there appears to be a much more computationally efficient baseline that the authors have overlooked. The authors estimate the Hessian using the method of finite differences (equation 1), which requires four model evaluations to get one entry in the Hessian matrix. For neural networks, there exists an efficient way to get the entries for an entire **row** of the Hessian as follows: first, compute the gradient $\\partial F(\\boldsymbol{x})/\\partial x_i$ for all $x_i$ in a standard backpropagation pass. Then, add a small perturbation $h$ to some input $x_j$. After making the perturbation, recompute the gradients $\\partial F(\\boldsymbol{x} + \\boldsymbol{e}_j h)/\\partial x_i$ for all $x_i$ in another standard backpropagation pass (as in the text, $\\boldsymbol{e}_j$ is a one-hot vector with the $j$th entry set to 1 and zero elsewhere). Estimate the Hessian entries for the row as $\\frac{1}{h} [\\partial F(\\boldsymbol{x} + \\boldsymbol{e}_j h)/\\partial x_i - \\partial F(\\boldsymbol{x})/\\partial x_i]$. This approach fills in the entire $j$th row of the Hessian and requires only two forward-backward passes through the model. This is the idea adopted in https://academic.oup.com/bioinformatics/article/34/17/i629/5093210, though I suspect references to this approach exist even earlier in the literature. It is true that the multi-armed bandit approach could likely be adapted to using this technique to fill out the hessian matrix (perhaps now the \"arms\" would correspond to rows in the hessian, rather than individual entries in the hessian?), though I am not sure how dramatic the computational gains would be relative to the naive approach.\n\n2. Elaborating more on my concerns re the computational complexity of the current UCB approach: the authors write that in their experiment with only 10 features, \"our proposed method needs around 1500 pulls of arms to pick out the top 20 interactions, however,\nnaively pulling each arm 100 times needs 4500 pulls in total\" - and yet, using the approach I suggested in (1.) with a naive 100 pulls per row of the hessian, the total number of pulls needed would be 1000, which is *smaller* than the 1500 pulls needed for finding only the top 20 interactions. This difference would be even more dramatic for experiments with even more features. The authors mention experiments with more features in supplement F - however, it looks like the authors only discuss the AUCs and *don't mention the number of pulls needed for these larger experiments*. I think it's important to report the number of pulls.\n\n3. Regarding the fact that the Hessians are evaluated on examples randomly drawn from the training data: this could conceal cases where the Hessians are near 0 due to saturation effects (this is analogous to the gradient saturation problem in the context of feature importance scoring method (Figure 1 in the DeepLIFT paper https://arxiv.org/pdf/1704.02685.pdf)). However, I recognize that, depending on the perturbation size h, this saturation issue could be overcome. Still, it is worth considering whether to adopt an approach like the one in https://academic.oup.com/bioinformatics/article/34/17/i629/5093210, where interaction strength was defined as the change in the feature importance of feature i in response to perturbations in j (and \"feature importance\" could be computed using alternatives to the gradient that are less likely to suffer from saturation issues); even though it is more heuristic, it may bring down the number of arm pulls needed to detect a true feature interaction.\n\n4. In terms of benchmarking the compression offered by ParaACE, I think there are successors to the LTH approach that are worth including in the benchmarks to make them more compelling - e.g. \"Pruning neural networks without any data by iteratively conserving synaptic flow\" (NeurIPS 2020: https://arxiv.org/abs/2006.05467)\n\n5. A minor but important note regarding the extent to which ParaACE is interpretable: note that a pairwise interaction subnetwork is capable of learning main effects of features too; thus, ParaACE may not be that interpretable in terms of decomposing the prediction into main effects and interaction effects.\n\nMinor\n- The authors called ParaACE \"intelligent\" (bottom of page 6) - I think they meant \"intelligible\" or \"interpretable\"?\n- The authors mention \"smartphones\" in the context of the parallelizability of ParaACE - not sure what the connection is; smartphones are typically mentioned for portability rather than parallelizability?\n", "summary_of_the_paper": "The authors propose two key ideas. The first is the idea of using the UCB algorithm to identify strong feature interactions in a computationally efficient way; each set of interacting features is an \"arm\" that could be \"pulled\", and pulling the arm corresponds to evaluating the strength of the interaction by computing the corresponding entry in the Hessian on a random training example. The finite difference method is used for computing Hessians. The second key idea is that of using the identified pairwise interactions to build a lightweight GAM-like model that they call ParaACE. In experiments, the authors show the UCB approach is effective at identifying feature interactions compared to alternative methods, and they demonstrate that ParaACE offers strong gains in model compression compared to other competing approaches, and often improves performance relative to its overparameterized teacher model.", "summary_of_the_review": "I think the work proposes several interesting ideas; these ideas may be based on prior literature and may seem straightforward in hindsight, but I think they involved creative thinking to propose in the first place. Although I am not convinced by the computational efficiency of the proposed UCB algorithm and think a more computationally efficient baseline is missing from the comparisons, I think the idea of taking a multi-armed bandits approach to model interpretation is still clever, and the UCB algorithm could likely be extended/modified to leverage a more computationally efficient way of evaluating interactions. I also think the ParaACE approach to compressing models and combatting overfitting is a novel take on how feature interactions can be made useful (prior work has been heavily focused only on interpretability). However, at least for model compression, I think there is at least one baseline method worth including. Overall, I rate the paper above the acceptance threshold as-is.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of feature interactions identification in black-box models, which is an important problem towards achieving explainable AI/ML. The authors formulate the problem under the multi-armed bandit setting and propose a solution based on the UCB algorithm. This simplification of the problem leads to a computationally feasible solution, for which the authors provide several theoretical analyses. The importance of the learned interactions is showcased in a new deep learning model leveraging these interactions, leading to a reduction in model size (thereby competing against pruning methods) as well as an improvement in accuracy (thereby competing against generalization methods). Although the proposed approach essentially builds on the specific UCB algorithm, it could likely be extended/modified to other (potentially more efficient) bandit strategies. A drawback of this work resides in the experiments being entirely synthetics. In order to close the gap with practice, experiments on real datasets of higher dimensionality should be conducted.
Decision: Accept (Poster)