Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Strengths:
- To my knowledge, no one has applied a multi-armed bandits approach to interaction detection
- 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.
- 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.
- The authors have done a good amount of technical work to evaluate their approach in different contexts.

Weaknesses:
1. 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.

2. 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,
naively 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.

3. 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.

4. 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)

5. 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.

Minor
- The authors called ParaACE "intelligent" (bottom of page 6) - I think they meant "intelligible" or "interpretable"?
- 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?

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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). 
main_review: The paper has several strong points as follows:

- 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)
- 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
- 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).
- 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


The paper can be improved upon by addressing some of the aspects below:

- 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
- 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?
- 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
- 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

On 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 
The authors add to this idea more effective estimation by evaluating only those elements of the Hessian matrix that can be valuable.
However, 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.  
Writing 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.

Pros
* The paper contains a lot of material to explore with many experiments in the main text and in the supplementary
* Theoretical justification on why should it work in a form of a couple of natural theorems.

Cons

Experimental results:
* No experimental for the efficiency of the proposed approach on how does it work compared with the estimation of the full Hessian matrix
* 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.
* 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?

Presentation:
* 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:
** With the increase of training samples -> Increasing the number of training samples (or "the training sample size")
* 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.
* ROC AUC is a better term for provided scores than AUC, as you consider the ROC curve for the interaction detection
* 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?)
* I suppose, that you don't own the rights for the MATLAB logo (Figure 6), so maybe you should cite the figure source?
* Figure 5: what is the color bar? Does darker blue color correspond to stronger interaction?

Theoretical results:
Theorem M.1 says nothing about absolute values of the elements of the Hessian matrix, only with non-absolute values.
So, 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.

Hard to reproduce:
* 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? 
* 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 
* What is a ReLU network - unclear
* Single layer ResNet - not defined 

Design choices:
* Why Kaiming’s strategy for initialization?
* Typical batch size is a power of 2. Why 500 in your case?
summary_of_the_review: The authors propose a more efficient method for hessian matrix estimation with little novelty and not comprehensive experimental results.
If 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Pros:
+ a fast and principled interaction detection method,
+ a lightweight and interpretable neural network model that can surpass its Teacher, 
+ good theoretical analysis and performance evaluations with real datasets. 
+ method directly derived from definition of feature interaction
+ the work has taken theory and material from multiple domains and plugged them at apt joints
+ transferring the problem of feature interaction to multi-armed bandits
+ supplement has proofs of statements and explainations
+ apart from synthetic datasets, the real world datasets belong to non-intersecting domains
+ code zip

Cons:
- Upper Confidence Bound (UCB) algorithm is dated 1985 - has nothing else come up interim?
- similarly comparison with classic alternating conditional expectation (ACE) model (1985) feels a bit outdated
- some text book and paper definitions are repeated, instead could have just cited the prior art
- the number of training samples in synthetic data could be increased and tried out at variant degrees
- conclusion section is weak

Miscellaneous:
- theoretical analyses -> theoretical analysis
- F (x), for instance, rewrite
- explain why - an ‘1-regularized ReLU network is required by the latest NID and PID 
- 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?
- How is interaction different from functional dependency?
- Finite m evaluations of one arm are sufficient to obtain an accurate reward. - is this assumption valid? upper bound of m in practice?
- intelligent, unlike - > interpretable
- parallelizable -> how powerful the smartphone is to support the feature?
- explain more on the cross domain practical applications
- recommended to compare with other state of art approaches in real analysis 
- using Matlab logo as function was cool :-)
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.
review_title: null

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)