Defining and extracting generalizable interaction primitives from DNNs
Authors: Lu Chen
Siyu Lou
Benhao Huang
Quanshi Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Transferability
Generalization Power
Primary area: visualization or interpretation of learned representations
TL;DR: We develop a new method to extract transferable features shared by different DNNs.

Abstract: Faithfully summarizing the knowledge encoded by a deep neural network (DNN) into a few symbolic primitive patterns without losing much information represents a core challenge in explainable AI. To this end, Ren et al. (2024) have derived a series of theorems to prove that the inference score of a DNN can be explained as a small set of interactions between input variables. However, the lack of generalization power makes it still hard to consider such interactions as faithful primitive patterns encoded by the DNN. Therefore, given different DNNs trained for the same task, we develop a new method to extract interactions that are shared by these DNNs. Experiments show that the extracted interactions can better reflect common knowledge shared by different DNNs.

Published as a conference paper at ICLR 2024
DEFINING AND EXTRACTING GENERALIZABLE INTER- ACTION PRIMITIVES FROM DNNS
Lu Chen Siyu Lou Benhao Huang!
Quanshi Zhang"
Shanghai Jiao Tong University, Shanghai, China Fastern Institute of Technology, Ningbo, China {lu. chen, si siyu. lou, abhoc1098hbh, 2qs1022| ss jtu edu. en
ABSTRACT
Faithfully summarizing the knowledge encoded by a deep neural network (DNN) into few symbolic primitive patterns without losing much information represents a core challenge in explainable AI. To this end, Ren al. (2024) have derived a series of theorems prove that the inference score of DNN can be explained a small set of interactions between input variables. However, the lack of general- ization power makes it still hard to consider such interactions faithful primitive patterns encoded by the DNN. Therefore, given different DNNs trained for the same task, we develop a method to extract interactions that are shared by these DNNs. Experiments show that the extracted interactions can better reflect common knowledge shared by different DNN
INTRODUCTION
Explaining and quantifying the exact knowledge encoded by a deep neural network (DNN) presents new challenge explainable AI. Previous studies mainly visualized patterns encoded by DNNs (Bau et 2017 Kim et al. 2018) and estimated a saliency map on input variables (Simonyan et al. 2013 R. Selvaraju et al. 2017). However, a new question that can we formulate the implicit knowledge encoded by the DNN as explicit and symbolic primitive patterns? In fact, we hope these primitive patterns serve as elementary units for inference, just like concepts in human cognition.
However, there is no widely accepted way to define the concept encoded by DNN, because cannot mathematically define/formulate the exact concept in human cognition. Nevertheless, if we ignore cognitive issues, Ren al. (2024; Li & Zhang (2023b) have derived series of theorems as convincing evidence to take interactions as symbolic primitives encoded by DNN. Specifically, interaction captures the intricate nonlinear relationship encoded by the DNN. For instance, when a DNN processes a sentence "It is raining cats and dogs!", the DNN may encode the interaction between a set of input variables S {raining, cats, and, dogs} C N. When all words in S present, an interactive effect I(S) emerges, and pushes the DNN's inference towards the semantic meaning of "heavy rain." However, any word in masked, the effect will be removed.
Ren et al. 2024) have mainly proven two theorems to justify the convincingness of considering above interactions as primitive inference patterns encoded by the DNN. First, is proven that under some common conditions well-trained DNN usually just encodes limited number of interactions w.r.t a few sets of input variables. More crucially, let us randomly mask an input sample x in different ways to generate an exponential number of masked samples. It is proven that people can use just a few interactions to accurately approximate the DNN's outputs on all these masked samples. Thus, these few interactions referred to as interaction primitives.
Despite the aforementioned theorems, this study does not yet deem the above interactions as faithful primitives of DNNs. The core problem is that existing interaction extraction methods cannot the- oretically guarantee the generalization (transferability) of the interactions, e.g., ensuring to extract
Equaal contribution.
QQanshi Zhang is the corresponding author. He is with the Department of Computer Science and Engi- neering, the John Hopcroft Center. the Shanghai Jiao Tong University. China.
fhttps: / http///ttuuuaoooo comm sjttssai-iiissae lb/ general zaall e- interaction "Plesse see Appendix B for details.

---

Published as a conference paper at ICLR 2024
distinctive
shared
distinctive
2 DNN
nn DNN
black dog
said black dog
dog over David
Interaction primitives
black dog
black
ADO
black
AND
dog over
dog
they said
over
Input voriables
They
said
the
black
dog
is
over
David
Input sentence
They the black dog David.
Negative sentiment
Figure Distinctive and shared interactions. When we extract AND-OR interactions from two DNNs, AND interactions S₁ {black, dog) and S2 {black, dog, over), and OR interactions S3 {black, dog) } and S4 = (black, over} are shared by two DNNs, while interactions, such as the AND interaction S3- (thyy, said), are distinctive interactions encoded by single DNN.
common interactions shared by different AI models. Interactions, which not shared by different DNNs, may be perceived as -utto--distribution signals without clear meanings.
Therefore, in this study, revisit the generalization of interactions. Specifically, we identify clear mechanism that makes the existing method extract different interactions from the same DNN under different initialization states, which hurts the generalization power of interactions.
Thus, to address the generalization issue, we propose a new method for extracting generalizable interactions. A generalizable interaction is defined as Figure I shows. Given multiple DNNs trained for the same task and an input sample, if an interaction can be extracted from all these DNNs, then consider it generalizable. Our method is designed extract interactions with maximum gen- eralization power. This approach ensures that if an interaction exhibits significant impact on the output score for DNN, it usually demonstrates noteworthy influence for other DNNs. We ducted experiments on various dataset. Experiments showed that our proposed method significantly improved the generalization power the extracted interactions across different DNNs.
GENERALIZABLE INTERACTION PRIMITIVES ACROSS DNNS
2.1 PRELIMINARIES: EXPLAINING THE NETWORK OUTPUT WITH INTERACTION PRIMITIVES
Although there is no theory to guarantee that how to define concepts that fit well with human cogni- tion, Li Zhang (203a) and Ren et al. (024) still provided mathematical supports to explain why still use interactions between input variables as the primitives concepts encoded by the DNN. Specifically, there are two types of interactions, i.e., AND interactions and OR interactions.
R" R, let us consider an input sample [2 222 ... _T, with n input variables indexed by N = (1.,...,, n). Here, v(x) E R denotes the function output on xf" Then, Ren al. (2023b) have used the Harsanyi dividend (Harsanyi 1963) ( S]x to quantity the numerical effect of the AND relationship between input variables in SC N, which is encoded by the function v. We consider this interaction AND interaction.
AND interactions. Given function
Tanal (S|x)=
E-13 vXT).
where (0) x) v(xa), and xx denotes a sample whose input variables in N \ masked
Each AND interaction Jana(S x) reveals the AND relationship between all variables S. For in- stance, let consider the slang term S (203, 34,, 45, 2 256) in the sentence "x, It, 222 is, 30g raining, X4 = cats, 233- = and, F6 dogs!" as a toy example. The co-occurrence of four words forms the semantic concept of "heavy rain" and contributes a numerical effect Lana(S) (S x) the function output. Otherwise, the masking of any word x; E S invalidates the semantic concept and climinates the interaction effect, i.e., obtaining Tana(S masked
on the masked sample.
If' the target functiion/mode///etwwwkk has vectorized output, e.g., a DNN for multi-category classification, we may set vxx) log //y=> xx)
I-p(ump publ by following (Deng et al. 2022).
*We followed [Li & Zhang 2023a) to obtain two discrete states for each input variable, i.e., the masked and unmasked We simply masked each input variable N using baseline values.
2

---

Published as a conference paper at ICLR 2024
OR interactions. Analogously, R. To this end, (Zhou et al. 2023: Li & Zhang 2023a) have defined the following OR interaction effect Lnr( measure the OR interaction encoded by In particular, [nr( x) v(xg).
also the OR interaction to explain the function R
Tur (S - E ( 111
(2)
Each OR interaction (S]x) describes the OR relationship between all variables in S. Let us consider an input sentence "x, This, 42 - movie, 23 is, I4 boring, Vi and, 36
disappointing" for sentiment classification. Let us set S = { F6.. The presence of any word in will contribute a negative sentiment effect (Sr to the function output.
Sparsity of interactions. Theoretically. according to Equation ( a function can encode at most 2 different AND interactions w.r.f. all 2 subsets VS, S _ N. However, Ren et al. (2024) have proved that under some common condition most well-trained DNNs only encode a small set of AND interactions, denoted by Ω i.e., only a few interactions E Ω have considerable effects (nn All other interactions have almost zero effects, i.e., and ( (S) 51x R O, which can be regarded as a set of negligible noise patterns.
It is worth noting that OR interaction can be regarded specific AND interaction, if we inverse the definition of the masked state and the unmasked state of an input variable Thus, the proven sparsity of AND interactions can also indicate the conclusion that well-trained DNNs tend to encode a small number of OR interactions.
Definition of interaction primitives. Considering the above proven sparsity of interactions, define an interaction primitive as a salient interaction. Formally, given a threshold т, the set of interaction primitives are defined as Ω (S C N [[(S)x) 7}.
Theorem 1 (Universal matching theorem, proved by (Ren et al., 2024)). As the corollary of the proven sparsity in Ren et al. (2024), the function's 's output on all 2n masked samples {xs|S S
N} could be universally explained by the interaction primitives in Ω, s.t., [S2] << 2", i.e. VS S
N, N(v(x))= = Ergs Land (T(x)= = EIgs:ren (T]x
In particular, Theorem shows that if we arbitrarily mask the input sample x, we can get 2n 2" different masked samples VS,S C N. Then, we can universally match the output of the function v(xs) on all 2n masked samples using only few interaction primitives in f2
2.2 FAITHFULNESS PROBLEM WITH INTERACTION-RAN EXPLANATIONS
Basic setting of using AND-OR interactions to explain a DNN. In this section, we consider to employ both AND interactions and OR interactions to explain the DNN's output. This is because the complexity of the representations in DNNs makes it difficult to rely solely on either AND inter- actions or OR interactions to faithfully explain true inference primitives encoded by the DNN.
To this end, we need to decompose the output of the DNN into two terms v(x) = (x) + (x), so that we can use AND interactions to explain the term (an(() (x) and use OR interactions to explain the term (x). In this way, the first challenge is how to learn an appropriate decomposition of (x) and (x) that reveals intrinsic primitive interactions encoded by the DNN. We will discuss this challenge later.
No matter how we randomly decompose uxx) = Uand (x) (xx)+aa (x). Theorem 2 states that we can still interactions to fit the DNN's outputs 2" randomly masked samples [xy. [T C N). Further- more, according to the sparsity of interaction primitives in Section [21] we can obtain Proposition i.e., the 2" network outputs on all masked samples can usually be approximated by small number of AND interaction primitives in Qand and OR interaction primitives in f2"r, s.t., [(and] | < 2".
Theorem 2 (Universal matching theorem, proof in Appendix Cp. Let us be given DNN and an input sample x. For each randomly masked sample XT, T C N. we obtain
u( (xT) = Vand (xT) + vor(xx) = ESST lana (S(xT) + +Σ Se(ssSSTTT))) (S(xT). (3)
SCT
'To compute (S)x), we use baseline value b, and set x, b, to represent its masked state. If we consider b; variable as the presence of the variable, and consider the original value x; as its masked state (i.e.. using r(br) to represent e(*Nyr) in Equation (2)), then (rr(S) x)) in Equation Q can be formulated the same the AND interaction in Equation
3

---

Published as a conference paper at ICLR 2024
Proposition 1. The output of a well-trained DNN on all 2n masked samples {xr C N} could be universally approximated by the interaction primitives in gyand and 12 S.L. [Qandd |S29| & 2", i.e. AT S N, N,y(XT) = Esgr (mma(S(xr) =Ese e(xx)++ + L0sscr:sen I (S) + ESrT Tor (S|xT), where v(xo) = Vand (xo) U (Xp).
Tor (S(xr) a
Problems with the faithfulness of interactions. Although the universal matching capacity proven in Theorem 2 is quite significant advantage of AND-OR interactions, it is still not the ultimate guarantee for the faithfulness of the extracted interactions. To be precise, there still no standard way to faithfully decompose the (amd( (x) term and the (x)(x) term that reveal intrinsic primitive interactions encoded by the DNN, considering the following two challenges.
Challenge 1, ambiguous decomposition of (x) and (x) usually brings in considerable uncer- tainty in the extraction of interactions. Let us take the following toy Boolean function as an example to illustrate the diversity of interactions, [(x =
A A 23 + 322 A 23 + Ig A I4 + x44 V 255, where x = [T1. Z2, 23, 24, I5. T and T3 E {0, 1}. We have two ways to decompose fxx). First, we can 21 A Ø2 A 23 + D2 A 23 + 23 A I4 and Vor (x) Z1 V Ts, then to plain fxx with an OR interaction (S = (4) and three AND interactions (and = {1, 3))),
simply decompose Vand
(S = (2) and (S {3, 4)) ). Alternatively, we can also
exclusively AND interactions
to explain fxx). Specifically, we can rewrite Uand (xnd( = 21 A A + 22 A + 23 A 24 + 24 Vas
T1 A 22 A 23 + 22 I3 + Iz x44 + (x4 + Ia I4 A æ5) and Uor (x) = w.r. 2; {0, 13. Thus, the Cand term can be explained by total of six AND interaction primitives. This is a typical case for diverse strategy of extracting interactions that are generated by different decompositions.
The aforementioned fxx is just an exceedingly simple function. In real-world applications. DNNs usually encode intricate AND-OR relationships among input variables, making exceptionally chal- lenging to formulate an explicit expression for the DNN function or to establish a definitive ground- truth decomposition of Vand(x) and U (x). Consequently, the diversity issue with interactions are ubiquitous and unavoidable.
Challenge 2, how to ensure the interaction primitives are generalizable. is commonly considered that generalizable primitives are usually transferable over different models trained for the same task, instead of being over-fitted by a single model. Thus, if an interaction primitive can be consistently extracted from different DNNs, then it can be considered as a faithful concept. Otherwise, non- generalizable monntraansfrrbble interactions do not appear as faithful concepts, even though they still satisfy the criteria of sparsity and universal matching in Theorem
Definition 1 (Transferability of interaction primitives). Given m different DNNs trained for the
same task, v(1), .,(2),,. ...., (mm), we use AND-OR interactions to explain the output score (x) of each DNN w(0) on the input sample x. Let ()nd.(() = {S S N [ > ,00 and sym (S C N (S(x) > /(0) denote a set of sparse AND interaction primitives and set of sparse OR interaction primitives, respectively. Then, the set of generalizable AND and the set of generalizable OR interaction primitives for the i-th DNN, are defined as Simm = n (2mma.(t) and Ditma N 52x,(0), respectively. The generalization power of AND and OR interactions of the 1 l/|52"..0)) respectively.
i-th DNN, can be measured by (0 / and
Definition I introduces the generalization power of interaction primitives. A larger value signifies higher transferability and, consequently, more generalizable interactive primitives.
2.3 EXTRACTING GENERALIZABLE INTERACTION PRIMITIVES
Neither of the aforementioned two challenges has been adequately tackled in previous interaction
studies. In essense, interactions are determined by the decomposition of the network output v(x) =
Vand (on(x)++x)) tor (x). Thus, if we rewrite the decomposition Vand = 0.50(x7)++))) and var (xT)
(x.: - Tr, then the learning of the best decomposition is equivalent to learning a set of {rr) }. Here, the parameter "TT E R for subset T S N determines specific decomposition between Vand (xr) and vxr Therefore, our goal is to learn the appropriate parameters (Tr) that reduce the aforementioned uncertainty of interaction primitives and boost their generalization power.
4

---

Published as a conference paper at ICLR 2024
To this end, to alleviate the uncertainty of the interactions, the most intuitive approach is to learn the sparsest interactions, considering the principle of Occam's ' Razor, as follows. It is because the sparsest (or simplest) explanation is usually considered the most faithful explanation.
min (Tr) [ |1 ||Tel]1:
(4)
where Land = (T] Fand 2m x)]
T Iur (T) (T2 |x] E IR"., Ta S N.
The above ( norm loss promotes the sparsity of both AND interactions and OR interactions.
2.3.1 ONLY ACHIEVING SPARSITY IS NOT ENOUGH
Although the sparsity can be used to reduce the uncertainty of interactions, the sparsity of interac- tions w.r.t each single input sample obtained in Equation (4) does not fully solve the above two challenges. First. Ren et al. (2023c) have found that the extraction of high-order interactions is usually sensitive to small noises in input variables, where the order is defined as the number of in- put variables in SS, Le., order(() (S) |S]. It means that when different noises are added to the input samples, the algorithm may extract fully different high-order interaction [ Similarly, this will also hurt the generalization power of interaction primitives over different samples, when these samples contain similar sets of input variables.
Second, optimizing the loss Equation may lead to diverse solutions. Given different ini- tial states, the loss in Equation (4) may learn two different sets of parameters {fr} as two lo- cal minima with similar loss values, while the two sets of parameters {(r} generate two different sets of interactions. We conducted experiments to illustrate this point. Given pre-trained BERT model (Devlin al.] (219) and an input sentence x on the SST-2 dataset for sentiment classifica- tion, we learned the parameters } to extract sparse interaction p In this experiment, we repeatedly extracted two sets AND-OR interactions by applying two different sets ini- tialized parameters {, which are denoted by (A4and AAt) and (Bund B Annd {S N (S|x)] > TAmm)} denotes the set AND interaction primitives extracted by a certain initial- ization of {. where the parameter Tq determined to ensure that each set selected the most salient K = 100 interactions. We used the transferability of interaction primitives in Definition I Sund [A4nnd | I/ and Sur |.4or B [ measure the diversity of interactions caused by the different parameter initializations. Table 2 shows that given different initial states, optimizing the loss in Equation (4) usually extracted two dramatically different sets of AND-OR teractions with only 21 % overlap. Figure T2 further shows the top 5 AND- OND-OR interaction primitives extracted from BERT model on the same input sentence, which illustrates that given different initial states, the loss in Equation would learn different AND-OR interactions.
Third, prioritizing sparsity cannot guarantee high generalization power across different models. Since DNN may simultaneously learn common knowledge shared by different DNNs and be over- fitted to some wewoooffte-disrribeee primitives. We believe that the shared common interactions are more faithful, so the transferabiliity another way to guarantee the generalization power of interaction primitives. Therefore, we hope to formulate and extract common interactions that generalizable through different DNNs.
patterns, different DNNs may only share partial interaction
We conducted experiments to illustrate the difference between interactions extracted from two DNNs by using Equation (4). We used BERT Vasse and BERTLARGE Ularge (Devlin et al. 2019) for the task of sentiment classification. Specifically, given an input sentence x, we learned two sets of pa- rameters {>baee } and { large for the BERT-base model and the BERT-large model, respectively.
Then we extracted two sets of AND-OR interactive concepts base (?orrbase) and Ilage (or,lange), respectively. Subsequently, we computed the transferability of the extracted interaction primitives according to Definition [ Figure shows that the transferability of the extracted AND- OR interaction primitives was much lower than interactions proposed in this study.
2.3.2 EXTRACTING GENERALIZABLE INTERACTIONS
As discussed above, the sparsity alone is not enough to tackle the aforementioned challenges. There- fore, in this study, we propose to use the generalization power as straightforward purpose, to
'lease Appendix D for details.
5

---

Published as a conference paper at ICLR 2024
boost the faithfulness of interactions. Meanwhile, the sparsity of interactions is also supposed to be guaranteed. Given a total of m DNNs ,,((2__ ...., u(() trained for the same task, the objective of extracting generalizable interactions shared by the m DNNs revised from Equation ( as follows.
min
(m))
[roomax (Tana) |I + |roomaax(Tar]ll,
(5)
TT
where and =
(1)
(2)
((m)
E R xm and Jor (2)
(2)
((m)
R xm
(+)
and and
and
and
Land (Ti (T))x)....... and (T2m [x]] E I² and 1 represent the all 2" AND-OR interactions extracted from the i-th DNN, T3 N. The matrix operator rowmax() computes the &o norm of each [I,
E R For each specific subset of variables Ta S N, the rowmaxx) operation returns the most salient interaction strength over all m interactions from the m DNNs. Please see Appendix (F more discussion on the matrix and
row within the matrix, i... rowmax mmd)
Unlike Equation 4 the revised loss in Equation 5 only penalizes the most salient interactions over all m interactions extracted from m DNNs, with respect to each subset Tą S N. This loss function ensures that if a DNN encodes a strong interaction w.r.f the set Tg, then we can also extract the same interaction w.E. Tr from the other
DNNs without a penalty. The l norm also makes that the m DNNs share similar sets of sparse interactions. Considering the sparsity of interactions, for most subset Tk, the effect r(()
and/or (T& (x) is supposed to keep almost zero on all m DNNs.
Just like in Equation 44, we decompose the output of the i-th DNN as and (xT)= 0.5v (xT) ( +7 and ( (xr) 0.5v (xT) YF' (0) compute two vectors of AND-OR interactions, I and (())
Redundancy of interactions. However, it is important to emphasize that only penalizing the largest interaction among the m DNNs in Equation (5) still faces the redundancy problem. Specifically, for each i-th DNN, we compute a total of 2 AND interactions and 2" OR interactions w.r.l. different subsets T C N. Some of these 2n+1 interactions, denoted by the set D selected by the loss in Equation (5) as the most salient interactions over m DNNs, while the set of other unselected interactions denoted by oothers (T S N) \ 2 Then, the redundancy problem is caused by a short-cut solution to the loss minimization in Equation (5). i.e., using unselected not-so-salient interactions in others to represent numerical effects of selected interactions 2 as discussed in Challenge 1 Section 2.2, As short-cut solution to Equation (5), this may also reduces the strength of the penalized salient interactions in Equation (5), but generates lots of redundant interacitons.
(1)
Therefore, we revise the loss in Equation (5) to add penalties on unselected interactions to avoid the short-cut solution with coefficient of a, follows
min (7 (m. (m)y ([rowmax(Lam))l: + [[oo)ma((@<)ll))>>>> + a (I[ | + ||ox]]1),
(6)
where a [0, 1] is a positive scalar. We extend the notation of the & norm || ||ı represent the sum of the absolute values of all elements in a given vector or matrix. It is worth noting that the generalization power of interactions guaranteed by the rowmax() function in Equation (5). which assigns much higher penalties to non- ren-genrralizable interactions than generalizable interactions.
Sharing decomposition between DNNs. Optimizing Equation 6 is challenging To address this challenge, we introduce set of strategies to facilitate the optimization process. We assume that when all m DNNs are sufficiently trained, these DNNs tend to have similar decompositions of AND
interactions and OR interactions, i.e., obtaining similar parameters, VT C (m)
N.
...
7T
7T 7T where fir represents the common decomposition shared by all DNNs, and ( represents the decomposition
To achieve this, we introduce two types of parameters for 7T
(6)
(4)
specific to each i-th DNN. We constrain the significance of the unshared decomposition by using
bound (8) (6)
T7 where T
(i)
0.5 Ex( (x) ol (xo)]. During the training process, if
(t) sign("
then we set 97 Ty
7 Please see Appendix
detailed explanation of Equation 6
NNte that regardless of whether Equation (6) is optimized to the optimal solution, theoretically, the ex- tracted AND-OR interactions can still satisfy the property of universal matching in Theorem 2

---

Published as a conference paper at ICLR 2024
Modeling noises. Furthermore, we have identified potential limitation in the definition of the interactions. i.e., the sensitivity to noise. Let us assume that the output of the i-th DNN has small noise. We represent such noises by adding small Gaussian noise ér NN00 to
the network output and (xx) = (t) (xx) + cF In this case, we can derive that I (T) =
(())
(T) E ETi. We prove that the variance of and (I") caused by the Gaus- sian noises (eex~N((.02))
[ [Tadd and (T) F1 I
and (S)]² = o (please see Appendix D
for details). Similarly, the variance of rut (T) is also 2! 2 for OR interactions. It means that the variance/instability of interactions increases exponentially with the order of the interaction [?]]
(2) based Equation (6 to remove tiny noisy Therefore, we propose to directly learn the error term Cf
signals, which are unavoidable in real data but cannot be modeled as AND-OR interactions, i.e,
(() setting ((() (x)) and (xT) + Uor (xT) + in order to enhance the robustness of our interaction
(t)
(6)
(Ty < Te (4) subject to Te 0.02-
extraction process. The error term is constrained to small range
|b(0) (x) (0) (xx)]. During the training process, if |c01| > Te (5) then we set
[c(0] (6) sign( (c7 (
Then, we conducted experiments to examine whether the extracted AND-OR interactions could still accurately explain the network output, when removing the error term. We followed experimental set- tings in Section X to extract interactions on both BERT and BERT models. We computed the matching error e(xr) = |e(x)) ppprrox (xr) )1 where y.pprrox (xr) was the network output ap- proximated by all interactions based on Theorem 2 Figure [3] shows matching errors of all masked samples w.r.t. all subsets 7' Ç N, when we sorted the network outputs for all 2n masked samples in
a descending order. It shows that the real network output was well approximated by interactions.
EXPERIMENT
In this section, we conducted experiments verify the sparsity and generalization power of the interaction primitives extracted by our proposed method on the following three tasks.
Taskl: sentiment classification with language models. We jointly extracted two sets of AND-OR interaction primitives from the BERT model and the BERT model (Devlin et al. 2019) by
following Equation 6 We finetuned the pre-trained BERT model and the BERTLARGE model
on the SST-2 dataset (ochhrr et al.. 2013) for sentiment classification. For each input sentence x containing n tokens we analyzed the log-odds output of the ground-truth label, i.e., e(x)
p(y=)"*hp) (x) by following (Deng et al. 2022).
log 1-p(y==pthh
Task2: dialogue task with large language models. We extracted two sets of AND-OR interaction
primitives from the pre-trained LLaMA model (Touvron et al. 2023) and OPT-1 model (Zhang et al. 2022b). We explained the DNNs' outputs on the SQuAD dataset (Rajpurkar et al.) 2016). We took the first several words of each document in the dataset as the input of a DNN, and let the DNN predict the next word. For each input sentence x containing n words we analyzed the log-odds output of the (n + 1) word that was associated with the highest probability by the DNN, max
i.e., (xx) = log 1-p(y=y"" [[y=)""[x) (x)
Task3: image classification task with vision models. We extracted two sets of AND-OR interaction primitives from the ResNet-20 model (He et al. (0166) and the VGG-16 model (Simonyan & Zisser- man 2015). which were trained on the MNIST dataset [LeCun] 1998). These models were trained to classify the digit "3" from other digits. In practice, considering the 2n computational complexity, we have followed settings in (Li & Zhang (023b), who labeled few important input patches in the image as input variables. For each input image x containing n patche we analyzed the scalar output before the softmax layer corresponding to the digit "3."
Sparsity of the extracted primitives. We aggregated all AND-OR interactions from various sam- ples, and draw their strength in a descending order in Figure 2 This figure compares the curve of interaction strength [S) C N between our extracted interactions, the traditional interactions (Li
Please see Appendix O for details.
7

---

Published as a conference paper at ICLR 2024
In logg space log (1(5930)
Interaztion Strength
BERT pAr
LERT
LiaMA
OPT-1338
ResNet-20
VGG-16
12
10
10
10m1
Outs
20
mong PCNP
Harcomy
Traditioral
18
Figure 2: Strength of AND-OR interactions log [(S]x)) over different samples in a descending order. All interactions above the dash line had much more significant effect (shown in log space) and were considered as salient interactions.
(ratio of shared interactione)
I: Sentiment Classification
Task 2: Diologue Tost
Task 3: image Clossification
Benera generalizatio power
(meosured by Sond and Say
0.8
And Interaction (Ours) Sand
6.6-
Interaction (Ours) Spr
And Interaction [Traditiona) Syud
0.4
Gr Interaction (Traditional) Sor
0.2
159
250
350
456
80
160
200
150
50
And Interaction (Harsanyl) Sant
of salient interactions
If of salient interactions
of salient interactions (c)
(a)
(b)
Figure 3: Generalization power (measured by Snd and Sor) of the extracted primitives interactions.
& Zhang 2023b 10
namely, Traditional) and the original Harsanyi interactions (Ren et al. 2023a)
(namely, Harsanyi). The competing method (Li & Zhang 2023b) (Traditional in Figure extracts the sparest interactions according to Equation (4), and the original Harsanyi interactions (Ren et al., 2023a) (Harsanyi in Figure 2) extracts interactions according to Equation ( 11 We found that most of the interactions had negligible effect. Although the proposed method reduced the sparsity bit, the extracted interactions were still sparse enough be considered as primitive inference patterns. For each DNN, we further set threshold ا00 to collect a set of salient interactions from this DNN as interaction primitives, i.e., (()) = 0.05 maxs [/]
Generalization power of the extracted interaction primitives. We took the most salient k inter- actions from each i-th DNN as the set of AND-OR interaction primitives, i.e., [S2=dd O1| = |92 @1 k, E {1, 2). We used the metric and and Sor Definition to measure the generalization power of interactions extracted from two DNNs. FigureBshone the generalization power of interactions when we computed Sand and Sor based on different numbers of most salient interactions. We found that the set of AND-OR interactions extracted from the proposed method exhibited higher generalization power than interactions extracted from the traditional method.
Low-order interaction primitives are more stable. Furthermore, we compared the ratio of shared interactions of different orders, i.e., order(S) 5) = =|S For interactions of each order o, we computed the overall strength of all positive interactions and that of all negative interactions of the i-th DNN, which were shared by other DNNs, Sharedt.(00
"ope((nd.oo Esengd |||== max(0, 1 (Slx)) dvnd 118 min(O, Iup (S[x)), respectively.
and Shared (0) sides,
= Eope (und.or) Escopa
Be-
All (0)
Empe(und.rr) Esern:o.. max(0, (S(x)) and (l)
Eope(ant arn Esesro.()) min(0, I (Slx)) denote the overall strength of salient positive in- teractions and that of salient negative interactions, respectively. In this way, Figure 4 reports (Shared+.00) ((0) and (AI A()) for different orders within the three tasks. shows that low-order interactions were more likely to be shared by different DNNs than high-order interactions. Besides, Figure 4 further shows higher ratio of interactions extracted by the proposed method were shared by different DNNs than interactions extracted by the traditional method. In particular, the high similarity of interactions between ResNet-20 and VGG-16 shows that although two DNNs for the same tasks had fully different architectures, there probably existed a set of ultimate interactions for a task, and different well-optimized DNNs were likely to converge to such interactions.
Visualization of the shared interaction primitives across different DNNs. We also visualize the shared and distinctive interaction primitives in Figure This figure shows that generalizable interac-
IIn the implementation of the competing method, we also learned an additional error term to remove small noises, just like in Section 2.3.2 to enable fair comparisons. Please see Appendix H for more details.
8

---

Published as a conference paper at ICLR 2024
Traditional Our internctions
BERT EAST
BERT LARG
LiaMA
ResNet-20
VGG-16
Al
interactions
Shared
Figure 4: Overall interactions and shared interactions. The red and black bars show the overall strength of positive interactions All+-("(o) and that of negative interactions All All--(( (o) of each o-th order. The orange and green bars indicate the strength of positive interactions that are shared by the other DNN Shared ((9 (o) and that of the shared negative interactions Shared (o), respectively.
BERT BAS8
LARGE
Distinctive interactions the BASE model
Shared interactions
Distinctive interactions the BERT
Our interactions
Ring just cold wet Seattle -iz -zle without rain -wear
AND
Just cold
wet
Just wet
without -wear
Seattle rain
wear
cold
wet
rain
just cold
-wear
Ring just wet without
-12 -zle without
Ring without
Ring Seattle -iz
rain
Ring
without
without rain -wear
just cold
wet
Ring just Seattle
Ring just cold wet Seattle -iz -zle without rain -wear
Ring -wear
Traditional
interactions
-wear
cold
wet
cold wet Seattle
Seattle -wear
without
Ring
wet
-I2 without
-i2 rain
without
Ring
cold
without
wet
wet
-zle
-iz
-wear
-wear
Seattle
The Ring just left me cold and wet like I was out in the Seattle dr-iz-zle without rain-wear.
Figure 5: Visualization of the shared and distinctive interaction primitives across different DNNs. We selected some salient interactions from the most salient & 50 AND-OR interactions each DNN. The black and gray color show the AND interactions and the OR interactions, respectively. The left and right column show the distinctive interactions extracted from the BERTBASE model and the BERT model, respectively. The middle column shows the shared interactions extracted ffo for more interactions.
from both models. Please see Appendix
tions shared by different models can be regarded as more reliable concepts, which consistently con- tribute salient interaction effects to the output of different DNNs. In comparison, non-generalizable interactions, which are sometimes over-fitted by a single model, may appear as ouitt---ist features. From this pespective, we consider generalizable interactions as relatively faithful concepts that often have a significant impact on the inference of DNNs. Figure further shows that, our method extracted much more shared interactions than the traditional which shows that our method could obtain more stable explanation of the inference logic of a DNN. It is because the interactions shared by different DNNs were usually considered more faithful.
method,
CONCLUSION
In this paper, we proposed method extract generalizable interaction primitives. The sparsity and universal-matchinn property of interactions provide lots of evidence to faithfully explain DNNs with interactions. Thus, in this paper, we propose to further improve the generalization power of in- teractions, which adds the last piece of the puzzle of interaction primitives. Compared to traditional interactions, interactions shared by different DNNs are more likely be the underlying primitives that shape the DNN's output. Furthermore, the extraction of interaction primitives also contributes to real applications. For example, it can assist in learning optimal baseline values for Shapley values RRn al. 2023b) and explaining the representation limits of Bayesian networks (Ren et al. 2023c). In addition, the extraction of generalizable interaction primitives shared by different DNNs provide perspective to formulating the out-of-distribution (OOD) features. Previous studies usually treated an entire sample as an OOD sample, whereas our work redefines the OOD problem at the level of detailed interactions, iee., unshared interactions be regarded OOD information.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work is partially supported by the National Science and Technology Major Project 22212D0111602 the National Nature Science Foundation of China (6277666,,9692 Shang- hai Natural Science Foundation 22JCC140880021122144440303
ETHICS STATEMENT
This paper aims to extract generalizable interaction primitives that shared by different DNNs. This paper utilizes publicly released datasets which have been widely accepted by the machine learn- ing community. This paper does not involve human subjects and does not include potentially harm- ful insights, methods, or applications. The paper also does not involve discrinination/iiss/aiinn issues, as well as privacy and security issues. There no ethical issues with this paper.
REPRODUCIBILITY STATEMENT
We provide proofs for the theoretical results of this study in Appendix C to D experimental details in Section 3 and Appendix O
We also provide
REFERENCES
BAAL Aquila-7b. 2023. URL httphtttp///mmggiigac....///////
David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissection: Quantifying interpretability of deep visual representations. In Proceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition, pp. 6541-6549, 2017.
Huiqi Deng, Qihan Ren, Hao Zhang, and Quanshi Zhang. Discovering and explaining the represen- tation bottleneck of dnns. In International Conference on Learning Representations, 2022.
Huiqi Deng. Na Zou, Mengnan Du, Weifu Chen, Guocan Feng, Ziwei Yang, Zheyang Li, and Quan- shi Zhang. Unifying fourteen post-hoc hoc attribution methods with taylor interactions. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2024.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. Proceedings of NAACL-HLT, 2019.
Amil Dravid, Yossi Gandelsman, Alexei A. Efros, and Assaf Shocher. Rosetta neurons: Mining the common units in a model zoo. IEEE International Conference on Computer Vision, 2023.
John Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194-220 1963.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Been Kim, Martin Wattenberg. Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In International Conference on Machine Learning, pp. 2668-2677. PMLR. PMLR, 2018.
Yann LeCun. The mnist database of handwritten digits. 1998. URL http::///am 1ecun. lecur. com/exdb/nniste
Mingjie Li and Quanshi Zhang. Technical note: Defining and quantifying and-or interactions for faithful and concise explanation of dnns. arXiv preprint arXiv:2304. 13312, 2023a.
Mingjie Li and Quanshi Zhang. Does a neural network really encode symbolic concept? Interna- fional Conference Machine Learning, 2023b.
10

---

Published as a conference paper at ICLR 2024
Dongrui Liu, Huiqi Deng, Xu Cheng, Qihan Ren, Kangrui Wang. and Quanshi Zhang. Towards the difficulty for a deep neural network to learn concepts of different complexities. Advances in Neural Information Processing Systems, 2024.
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. International Conference on Computer Vision, 2017.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint arXiv: (tti::6000.525555 2016.
Jie Ren. Mingjie Li, Qirui Chen, Huiqi Deng, and Quanshi Zhang. Defining and quantifying the emergence of sparse concepts in dnns. IEEE Conference on Computer Vision and Pattern Recog- nition, 2023a.
Jie Ren, Zhanpeng Zhou, Qirui Chen, and Quanshi Zhang. Can we faithfully represent masked states to compute shapley values on dnn? International Conference on Learning Representations, 2023b.
Qihan Ren, Huiqi Deng, Yumuo Chen, Siyu Lou, and Quanshi Zhang. Bayesian neural networks avoid encoding perturbation-sensitiv and complex concepts. International Conference on Ma- chine Learning, 2023c.
Qihan Ren, Jiayang Gao, Wen Shen, and Quanshi Zhang. Where we have arrived in proving the emergence of sparse interaction primitives in dnns. International Conference on Learning Repre- sentations, 2024.
Wen Shen, Lei Cheng, Yuxiao Yang, Mingjie Li, and Quanshi Zhang. Can the inference logic of large language models be disentangled into symbolic concepts? arXiv preprint arX00:2304.01083, 2023.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2015.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Vi- sualising image classification models and saliency maps. arXiv preprint 1rXiv:13/2.6034 2013.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language pro- cessing, pp. 1631-16422 2013.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Jason Yosinski, Jeff Clune, Anh Nguyen, Thomas Fuchs, and Hod Lipson. Understanding neural networks through deep visualization. International Conference on Machine Learning, 2015.
Quanshi Zhang, Xin Wang, Jie Ren, Xu Cheng, Shuyun Lin, Yisen Wang, and Xiangming Zhu. Proving common mechanisms shared by twelve methods of boosting adversarial transferability. arXiv preprint 2rXiv:2277.11633 2022a.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et Opt: Open pre-trained transformer language models. arXiv preprint 22X5v:2005.01066 2022b.
Huilin Zhou, Huijie Tang, Mingjie Li, Hao Zhang, Zhenyu Liu, and Quanshi Zhang. Explaining how a neural network play the go game and let people learn. arXiv preprint arXiv:2310.0983. 2023.
Huilin Zhou, Hao Zhang, Huiqi Deng, Dongrui Liu, Wen Shen, Shih-Han Chan, and Quanshi Zhang. Explaining generalization power of a dnn using interactive concepts. The Association for the Advancement of Artificial Intelligence, 2024.
11

---

Published as a conference paper at ICLR 2024
A PREVIOUS LITERATURE OF USING INTERACTIONS TO EXPLAIN DNNS
Explaining the knowledge encoded by DNNs is one of the ultimate goals of explainable Al but presents significant challenges. For instance, some studies employed visualization techniques to show the patterns learned by a DNN (Simonyan et al. [2013] Yosinski et al., 2015). and some focused on extracting feature vectors that may be associated with semantic concepts (Simonyan al. 2013),
while some studies learned feature vectors potentially related to concepts (Kim et al. 2018). Dravid
et al. 2023) identified convolutional kernels different DNNs that expressed similar concepts.
However, theoretically, whether the knowledge or the complex inference logic of a DNN can be faithfully represented as symbolic primitive inference patterns still presents significant challenges. Up to now, there is still no universally accepted definition of the knowledge, as it encompasses var- ious aspects of cognitive science, neuroscience, and mathematics. However, if we ignore cognitive and neuroscience aspects, Ren et al. (2023a) have proposed to quantify interactions between input variables encoded by the DNN, to explain the knowledge in the DNN. More crucially, Ren et al.) (2024) have derived several theorems as mathematical evidence of considering such interactions as primitive inference patterns encoded by a DNN. Specifically, |Ren et al. (2024) proved that DNNs usually only encoded small number of interactions, under some common conditions Besides, these interactions can universally explain the DNN's output score on any arbitrary masked input samples. Li Zhang
2023b) further discovered the discriminative power of certain interactions.
Besides. Deng et al. 2024 found that different attribution scores estimated by different attribution methods could all be represented as a combination of different interactions. ZZhang et al. (2022a) used interactions to explain the mechanism of different methods of boosting adversarial transferabil- ity. Ren al. |l.] (2023b) used interactions to define the optimal baseline value for computing Shapley values. Deng et al. (2022) found that for most DNNs it was difficult to learn interactions with me- dian number of input variables, and it was discovered that DNNs and Bayesian neural networks were unlikely to model complex interactions with many input variables (Ren el. 2023c Liu al.)
2024). Zhou et al. (2024) used the generalization power of different interactions to explain the generalization power of DNNs.
B THE CONDITIONS FOR UNIVERSAL MATCHING OF THE DNN OUTPUT
Ren et al. (024) have proved that a well-trained DNN usually just encodes a limited number of interactions. More importantly, one can just use few interactions to approximate the DNN's outputs on all 2 masked samples {xs|S S S NN. under the following three common assumptions. (1) The high order derivatives of the DNN output with respect to the input variables are all zero. (2) The DNN works well on the masked samples, and yield higher confidence when the input sample is less masked. (3) The confidence of the DNN does not drop significantly
the masked samples. With these natural assumptions, a well-trained DNN's output on all 2" masked samples can be universally approximated by the sum of just few salient interactions in P, s.f., [S2| < 2".
C PROOF OF THEOREMS
Theorem 2 (Universal matching theorem) Let us be given a DNN u and an input sample x. For each randomly masked sample xT, T C N, we obtain
(xxr) = -and (XT) + Uxr(xx)= = Σ SCT Lnnd (S|xT) + +Σ SE(S:SnT+4)y(0) Lor (S(x))
(7)
Proof. (1) Universal matching theorem of AND interactions.
Ren et al. (2023a) have used the Haranyi dividend (Harsanyi 1963) (S|x) to state the universal matching theorem of AND interactions. The output of wean-trained DNN on all 2" masked samples
[XT C N) could be universally explained by the all interaction primitives in T C N, i.e.
VT C N, Vana =
Esgr Iana (S(x).
Specifically, the AND interaction is defined as (S
E1cs(-1)081-14 Vana(Xx)
in Equation
To compute the sum of AND interactions VT
N, Escr l (S(x)
12

---

Published as a conference paper at ICLR 2024
Esct E (XL), we first exchange the order of summation of the set L S S C. and the set 5 2 I. That is, we compute all linear combinations of all sets S con- taining L with respect to the model outputs Vand given a set of input variables L, i.e, Esngser(-1)18)- cand (xz). Then, we compute summations over the set L C
In this way, we can compute them separately for different cases of L S S C. In the following, we consider the cases (1) L = S = T, and (2) L S S - T # T, respectively.
(1) When L
T, the linear combination of all subsets S containing L with respect to the model output Unnd (x.) ) (-1)1= (Xr.) Vand (xt).
(2) When I, S S C T. + T, the linear combination of all subsets S containing I. with respect to the model output cand (xt) is Es.Lgscr (-1)
For all sets S T 2 L, let us consider the linear combinations of all sets 5 with number |S] for the model output Vand (xr.). respectively. Let | (0 S m [T]- then there are total of Cmm.
(T)- combinations
of all sets S order (S]. Thus, given L. accumulating the model outputs Cand (xt) corresponding to all S 2 L, then Esngsgr( ( |5ml
117 171-|M
Unnd (Xr.)
97- (-1) 0.
m=u
Please see the complete derivation of the following formula.
Eser Jama (S(xT)) = Essr Eiss (-1)111-1 Cand
1e10l-1Eleamdxx (XL)
= =Eerr Esicsca (-1)151-144 -44 Vand (XLL)
Uand (XT)
ELITTLLAT (xL) Σ
m=0 177--1 (-1)
1T|-|b]
(8)
L=T
Vand (XT)
(2) Universal matching theorem of OR interactions.
According to the definition of OR interactions in Section 2.1 we will derive that V7 C N, oor (xT) (S (S for (0]xT) + Es.snryu or (5)x)), s.t., s.t. Lor (0(T)) = Vor (X0).
Specifically, the OR interaction is defined [S(()
- -ELcs(-1))s-
Uar (XNA,)
in Equation Similar to the above derivation of the universal matching theorem of AND interactions.
to compute the sum of OR interactions VT S. N, N.Snss Lor (S((T) =
we first exchange the order of summation of the set L CSSC N and the set S : STT * 0. That is, we compute all linear combinations of all sets containing with respect the model outputs Vor (xr())))) given set of input variables L, i.e. Es.STTTA.s2u-I))) - (x.,,,) Then, we compute all summations over the set L C N.
ESienT 21S5s(11)55-WWWaaasvvv
In this way, we can compute them separately for different cases of L C S S,SSTT + 0. In the following, we consider the cases (1) L N \ (2) N. (3) LDT 0, N, and (4) LNT = 0, L + N \ T, respectively.
N TT, the linear combination of all subsets S containing with respect the model output Vor ( is E 4..nTT For all sets S ear combinations of all sets S with number |S| for the model output (xr(x)), respectively. Let |S" := [S| [L] (1 < S < [T), then there are a total of c/Ss combinations of all sets of order [S]. Thus, given L. accumulating the model outputs V (xT) corresponding all S 2 L, then [T]
(1) When
(01 (x7).
2 L.S n # (then S # N \ T.S + L). let us consider the lin-
Σ Es.snr -I4 ( var (xr)
1 c/S (-1)811)8 -
13

---

Published as a conference paper at ICLR 2024
(2) When L = N (then S N), the linear combination of all subsets S containing L with respect to the model output Vor (xN,) is Essamra.s22(-11555-1laa Vor (Xp).
(-1)1M var (xp)
(3) When LNT * D.L * N, the linear combination of all subsets S containing L with respect to the model output (x)() is Es.srry40s22(-11]- or
For all sets
S 2 L,S n * 0, let us consider the linear combinations of all sets S with num- ber |S| for the model output for (xx), respectively. Let split [S] [L] into |S and |S"|, + SS where S = f (then 0 S is" S IT LD and 5' + S" L S. In this way, there L, E T) cls" [TTL) combinations of all sets s" of order |s"|. Thus, given L, accumulating the model outputs (xN,)) corresponding to all 2 L, then
te.|S|- -
L,i E T). S = E
total of
ITI-MA cls" ITI (T (-1) -1= (1))s)/(n-1))11111aaaaaaaa = 18"1=0
Vor (xr(XN)))) Esegyare Σ
(4) When LOT = = * N \ T, the linear combination of all subsets S containing with respect to the model output Vor (X is Es.snt (0.spr.-11)155)) (-1))55--H
Similarly, let us split ||] into [S'] and [S"]. i...[S - []] = SS' +|"), where S' = {[ili E S, & L, N N)),, |S" S [T) and S' 5 L S. In this way, there
total of cls" combinations of all sets S" of order |S"|. Thus, given L, accumulating the model outputs |T|
S" {ili S, E T) (then
Cor (XN(L) corresponding to all S 2 L, then Es (-1)(s 11-11- (xN(z) = cor (XN,,))
EScAVTA
|T]
s C CS (- (-1))S" = O.
Please see the complete derivation of the following formula.
E- (-1)) eor (XXLL) EssrTro (S(()))) = Σ SisnTHo [- E LCS
-' Σ SisnTs0,s2i (-1)1 181- 11 Vor (XNr))
ClS [T
(-1)189)
(xT vxr
|8
L-NiT
L=N
IT Σ
Σ
Σ
I
129-17nZ1 (- (11)1)11110)))
LAT
S'CNTAR
[S -
IT'
]
Σ
Σ
clS [T]
(-1)15" +10%)
Uor (or(x)))))
OALANT
S'CNYTAL
1S
-(-1) (xr( (x())
Σ
Σ
(x(()))))
LOT LON
S'CNATAL
Σ
Σ
(x
LIT=O S'ENTTLL
(x() (Xp)
(3) Universal matching theorem of AND-OR interactions.
With the universal matching theorem of AND interactions and the universal matching theorem of OR interactions, we can easily get v(XT) (xr) + (xr(x)) EsEt (Sn(()) +
Ese(s.SnT+ojupp (S)x)), thus, we obtain the universal matching theorem of AND-OR in- teractions.
14

---

Published as a conference paper at ICLR 2024
Theorem 3 (proved by Harsanyi (1663)) The Shapley value <b(i) of an input variable i can be explained as a uniform allocation of the AND interactions, i.c. ((i) = EsCNisa [S] ann (S)px)..
D PROOF OF THE VARIANCE OF AND AND OR INTERACTIONS
(0) In this section, we prove that the variance of 1odd (I) caused by the Gaussian noises ET ~N(00, (1( PrS,,am~N00003 ( (S)]² = 2 in Section 2.3.2
is Beg=~N(0,00)) (
Epi, the variance of And (T) is Var( and (T)) Var( Van (T) + Ercr(-1)l1--rig)) (g.) As the AND interaction a (T) and the Gaussian noise C7 (t) are independent of each other, then the variance of ! (T) be decomposed
Proof. Given and (T) = (T) + Ercr(-1))
(i)
(i)
to V
(1) (2)) = Var(1 (T)) + Var ( ep0) = Var War(Ers Erc((
this is because here / (T) can be regarded as a constant.
Since each Gaussian noise ET ~ o0, S N is independent and identically distributed, then the variance is Var(Zand (T)) Var ( Er) ( Var(er.) + Var(e (6)
(8)
Var(e (6) ) = 2 o² (there are a total of 2 subsets for T). Tm 2/21
E THE FAITHFULNESS OF THE SPARSITY AND UNIVERSAL--WATCHING.
This section further demonstrates the faithfulness of the sparsity and universal-matching theorem of AND-OR interactions, both theoretically and experimentally.
Theoretically, the faithfulness of the sparsity and universal-matching theorem of AND-OR inter- actions means that, given an input sample with n variables, we must prove that (1) a well-trained
DNN usually just encodes small number of salient interactions Q (Ren et al. 2024), comparing with all 2n potential combinations of the input variables in a given input sample, i.e., [S2] < 2", and
that (2) the network output v(xs) on all 2" randomly masked samples {xs S N) can be well
matched by few interactions in Ω = {S C N [7(5) x:) >> r as defined in the Definition of
interaction primitives in Section 2.1 These two terms have been proved in Theorem [ and Proposition
Theorem
Then, in practice, considering the 2n computational complexity, we have followed settings in & Zhang 2023b) to extract interactions between set of randomly selected input variables N (1. t). (f < n), while other unselected (n - -) input variables remain unmasked, leaving the original state unchanged. In this case, faithfulness does not mean that our interactions explain all the inference logic encoded between all n input variables for given sample æ in the pre- pre-trained DNN. Instead, it only means that the extracted interactions also accurately match the inference logic encoded between the selected t input variables for given sample x the DNN.
Experimental verification. In addition, have further conducted experiment to verify the faithfulness when we explain interactions between all input variables. To this end, for the senti- ment classification task on the SST-2 dataset in BERTBASF, [ and the universal-matchie erty in Theorem 2 All tokens are selected as input variables. We focused on the matching er- rors for all masked samples XT, VT C N. Specifically, we observed whether the real network output on the masked sample u(xT), YT S N can be well approximated by interactions. We have verified that the extracted salient interactions in Ω faithfully explain the network output, i.e,, VT' C N, v(xT) & v(xe) Se Land (|)r) En SuSSee (S(xT)) Figure 6 lustrates that network output u(xr), VT C N on all 2n randomly masked samples can be well fitted by interactions.
selected sentences containing 15 prop-
tokens to verify the faithfulness of the sparsity in Proposition
15

---

Published as a conference paper at ICLR 2024
DNN's output v(x))
0.0
BERT BASE
-2.5
10000
20000
30000
Index interactions
Figure 6: Universal matching of all interaction primitives to the DNN's output, when we use salient interactions match the DNN's output. Shade area indicates the matching error of different e(xr).
F DETAILED EXPLANATION OF EQUATION
66
This section uses simple example to illustrate Equation 6 more clearly. Let illustrate how the interaction matrices are formatted a toy example. Let us consider two pre-trained DNNs o(1) x(2) and an input sample x with N = {1,2) variables, and take the AND in- example (the OR interaction matrix Ilr can be ob- tained similarly). First, we get all 2 AND interactions extracted from the i-th model r(i) anad (Ti [x), anna (T2 (Ta (Ta) [x]] IR2 according to the description of Equa- tion (4). Here, each interaction value Lana (Tx x) IR, C N denotes the interaction value of each masked sample XT. which is computed according to Equation (T). Second, the AND inter-
teraction matrix annd in Equation (6)
and
action matrix and = and and
(1)
(2)
E I222 x2 represents the interaction values corresponding to the 2
masked samples for each of the two models.
Let us illustrate how to learn the parameter 7/7 in Equation (6). The loss in Equation (6 in the above example can be represented the function of }rr]. as follows.
Loss min (1 mry
[[rowmax((mmo]l + [|rowmax([e)]] |/tor// + ([) | + ||Lvlli)
max Ercs( |81 (-1) [0.5 (xT2) + + Σ TTSS (-1)18911711 (x²,) + 75% ?
min
(2) T&CN
TCS
Σ mmxx(- Enes (-1) (11) (1) (XNVT)) - -- (-1) ( ,0 (XN(T)) - -712!1
CN
Σ (-1)151-137) [0.5 x (xT:) -72
TCS
TWS S 1m1
+o Σ
(
(-1))81-171 (xN()) - -
TCB
T
(10)
(2)) via gradient descent to reduce the loss Equa- Therefore, we only need to optimize (7/ 7T
tion
6
G THE RUN-TIME COMPLEXITY
This section explores the run-time complexity of extracting AND-OR interactions on different tasks. Theoretically, given input sample with input variables, the time complexity is 2", and need to generate masked samples for model inference. Fortunately, the variable number is not too large by following the settings in (Li & Zhang 2023b) and (Shen et al. 2023). In real applications,
16

---

Published as a conference paper at ICLR 2024
Table Average run-time per sample on different tasks.
sentiment classification on the SST-2 dataset w.r. the pair of models (BERTBASE and BERT
dialogue task on the SQuAD dataset w.E. the pair of models (LLaMM and OPT-1.3B)
image classification on the MNIST dataset w.t. the pair of models
(ResNet-20 20 and VGG-16)
45. 14 seconds
46.61 seconds
27.15 seconds
the average running time for sentence in the SST-2 dataset on the BERTLARGE model is 45.14 seconds. Table | further shows the average running time of each input sample for different tasks.
H MORE BASELINE TO VERIFY THE EFFECTIVENESS OF EQUATION (6)
To further verify the effectiveness of the interactions extracted from Equation 6 we conducted experiments on more baseline, namely the original Harsanyi interaction (Ren et al. 2023a). We compared the sparsity and the generalization power of the AND interactions extracted from different DNNs. Figure 7 shows that the interactions extracted by our method exhibit higher sparsity and generalization power compared to the original AND interactions.
To enable fair comparisons, we double the number of Harsanyi interactions extracted from sample by setting (((] = [S] Thus, we congregate both sets of interactions (a total of 2 interactions) to draw curve in Figure 2 and Figure 3 number interactions over different methods.
In this way, can compare the same
In log space log [(()x))
10a-
10'
(ratio of shared interactions) (measured by Sam))
Task Sentiment Classification
Interaction Strength
BERT BERTBASE
BASE
LARGE
generalizzation power
10a
10a
GUrS
base liee
0.6
max (S
10
20
10.4
ours
10"1
ours
10
10
50
150
250
350
450
165
1c5
# of salient interactions
(a)
(b)
Figure 7: Comparing the sparsity and generalization power of the extracted interactions between the original Harsanyi interactions and our proposed method.
I ABLATION STUDY OF THE PARAMETER & IN EQUATION
6
To explore the effect of a on the AND-OR interactions extracted from Equation 6 we conducted an ablation study on a. Specifically, we jointly extracted two sets of AND-OR interactions from the BERT and BERTLARGE models, which were trained by (Devlin et al., 2019) and further finetuned by us for sentiment classification on the SST-2 dataset. For comparison, we set the value of a to [0, 0.2, 0.4, 0.6, 0.8, 1.0], respectively. Here, when a 0, Equation (6) degenerated into Equation (5) indicating that only the largest interactions among the m DNNs were penalized. As increases, the effects of not-so-salient interactions in other models were taken into account. Fig- ure shows that as the value of a increases, the sparsity the extracted interactions did not increase much, but the generalization power of the extracted interactions decreased. This shows the ef-
17

---

Published as a conference paper at ICLR 2024
Interaction Strength In log space
BERTBASE BASE
10a
BERT
generalization power (ratio of shared interactions)
Task 2: Sentiment Classification
Fuu AND insracioon Paaii imanatirs (Oun)
10a-
109
0 0
10"3
10-1
max, (S
4
10
1e5
1,55
02
(a)
(b)
Figure 8: Effect of a on the AND-OR interactions extracted from Equation (6). (a) Strength of all interactions extracted from all samples, which were sorted in a descending order. The increase of different value did not significantly affect the sparsity of interactions. (b) Decreasing generaliza- tion power extracted AND-OR interactions, when the a value increased.
fectiveness of the penalty in Equation (5) boosting the generalization power without significantly hurting the sparsity.
J VISUALIZATION OF MORE SHARED AND DISTINCTIVE INTERACTION PRIMITIVES FOR FIGURE
In this section, we visualized all shared and distinctive interaction primitives across different DNNs in Figure 5 Specifically, we randomly selected 10 tokens in the given sentence, labeling these 10 tokens in red and the other unselected tokens in black. Here, n = 10 input variables denote the embeddings corresponding to these 10 tokens. Since each input variable has two states, masked and unmasked, a total of 2 masked samples are generated. Then, according to Equations 1 and ( total of 20 AND interactions and OR interactions are finally obtained.
Then, we extracted the most salient k = 50 interactions from a total of 2 20 AND interactions and OR interactions as the set of AND-OR interaction primitives each DNN, respectively. Therefore, in our proposed method, 25 shared interactions were extracted from both models, and 25 distinctive interactions were extracted from the BERT BASE and BERT LARGE models, respectively. In contrast, in the traditional method, 16 shared interactions were extracted from both models, and 34 distinctive interactions were extracted from the BERT BASE and BERT models, respectively.
In addition, Figure shows the strength of the interaction value [[S]x) for each salient interaction. Specifically, we show the strength of the interaction value for each distinctive interaction in each DNN. We also show the strengths of two interaction values for each shared interaction extracted from both DNNs, where the strength of the interaction value on the BERT BASE model is on the left and the strength of the interaction value the BERT model is on the right. Figure illustrates that, our method extracted more shared interactions compared to the traditional interaction extraction method.
enteractioneettraation
K DISCUSSION ON THE DIFFERENCES IN THE SIMILARITY OF INTERACTIONS
This section compares the consistency of interactions between different types of DNNs. Since LLaMA (Touvron et al. 2023) and OPT-1-3B (Zhang et al., (022b) have much more parameters than BAST and BERTLARGE (Devlin et al. (019). it is often widely believed that these two LLMs can better converge to the true language knowledge in the training data.
We can roughly understand this phenomenon by clarifying the following two phenomena. First, through extensive experiments, the authors have found that the learning of DNN usually has two phases, i.e., the learning of new interactions and the forgotten of incorrectly learned interactions (this is on- on-going research). In most cases, after the forgetting phase, the remained interactions of an LLM are usually shared by other LLMs. The high similarity of interactions between LLMs has also been observed in (Shen al. 2023)
18

---

Published as a conference paper at ICLR 2024
B
LERT
Our interraction
Distinztive Intoractions For the BERT model
Shared Interactions
Distinctive interactions
for the BERT model
Gol
GAeR 1.0
Wholl
AND
0.23/5
Fing jus cold Stath 325/1.2 d6
Fing i
Seatiu
Seatts a thou
0.10
Birgattioa
Wing col Seatle serreet wit wear
Bagg
Rngges 0.26
cod oour
Seattie da
0.14
0.33
0.25
0.24
Just sol
ooddvet Suetie
221/100
Soazte
0JE/2 41
Big -AI
1222 41
whhaat
cild
Fine Soitts 4:
wiboutrez "Wer
Raglat
0.11
Seatis is
0.1770117
de wf HAREE
0.162.33
can
Aing wat
Fin
sold
0.11/:32
King cog Soctto
who a Hans
Why jus Soutte
4b toot
Jul Suatie
Surthe waar
oud Sorthe
000001177
0.330-40
0.54
Wet Surrde
Sold
Cold Seatti whthoct rail -ee
0.13
Count
Count 25
Count = 25
Traditional
interra tronss
0.23
0
cod
044/272
2.37/L1C
2.300.24
cold
Ren CE'S wet Seitee 42
3.55
0.65
A
Searth wwat
2.35
0.16
B:A// PM
BJA/I 33
05T
0.33
Aingatt
Riag wnd
1ing K8t22
Sagte 0.4
Soutlo Kei
0.15
0.34
C25/3.79
642
Soltti a
0.14
0.14
033
12/0000
25
000/2 24
0.15
0.12
Count 16
col wwer
3.2
jul -Ara
028
VSt sver
Wit attal
0.12
0.12
0.25
1.5
AM
LAR-4
Janteata
málri 0.23
0.11
0.32
623
532
coll wot
kot
de devtteet
vit
Seatte
6:1
vst nann
0.20
Kig Ait Sarts
rann wear
weteet
Lat leazhe
0.29
ren wear
de
wrth zire wec
cold di wit
6,55
0.14
Count
Count
The Ring just left me cold and like was in Seattle di-ie-zle without rein-weor.
Figure 9: Visualization of more shared and distinctive interaction primitives for Figure 5
Second, compared to LLMs,, relatively small models are less powerful to remove all incorrectly learned interactions. For example, a simple model is usually less powerful to regress a complex function. The less powerful models (BERTBASE and BERTLARGE) are not powerful enough accu- rately encode the potentially complex interactions.
Therefore, small models are more likely to represent various incorrect interactions to approximate the true target of the task. This may partially explains the high difficulty of extracting common interactions from two BERT models, as well as why the proposed method shows more improvements in the generalization power of interactions on BERT models.
Experimental verification. To this end, we have further conducted new experiment to compare the interactions extracted from two LLMs, i.e., LLaMA (Touvron et al.] (023) and Aquila-7B (BAAT, 2023 As Figure [0 shows, two LLMs usually encode much more similar interactions than two not-so-large models. In fact, we have also observed similar interactions in anther pair of LLMs, i.e. LLaMA and OPT-1.3B (Zhang et al. (2026)) (please see Figure This partially explains the reason why the performance improvement of these two LLMs is similar to that of LLaMA and OPT-1.3B.
L A CONCRETE EXAMPLE TO ILLUSTRATE THE PROCEDURE
Let us use a concrete input sentence with six tokens to illustrate the experimental procedure from beginning to end.
Step 1: Given the sentence "A stitch in time saves nine" with six tokens, the six input variables are Ii embedding of token "A", 22 embedding of token "stitch",, 3y embedding of token "in",
19

---

Published as a conference paper at ICLR 2024
Our interactions
LLaMA
Aquila-7B
LLaMA
LERTLARGE LARGE
All
10"
Shared
Shared
(a)
(b)
Figure 10: Differences of interactions between different types of DNNs.
x4 =mmbeddding of token "time", z6 = embedding of token "saves", and mg = embedding of token "nine". Although the dimensions of the embedding for the BERT and BERT models are different, we can still compute the interactions between the embeddings corresponding to the same token. Specifically, the embedding I; of token in the BERTBASE model is 24 E 767 and the emhedding 2; of token in the BERTLARGE model is T2 E R2.021
The baseline value for each input variable is bj b2 = by = b4 by b6 special embedding of a masked token, where the special embedding of the masked token is encoded by the BERTBASE BASE and BERTLARGE model, respectively. This special embedding can use the embedding of special token, e.g., the embedding of the [CLS] token. Specifically, the baseline b, in the BERTBAS BASE model is b,- E R 788 and the baseline b; in the BERTLARGE model is b, E R1044.
Step 2:
Step 3: In this case, there are total of 2 masked samples XT. XT, XT,, XTa, XToz XTss used for the model inference. Specifically, the first masked sample is XT, = {b1, b2. by, by. 65, b6 J. where each of its input variables (embedding) is replaced with the corresponding baseline value (embedding of a special token). i.e., F2 b,, i E [1,2, 2,.......00 .6). The second masked sample is XT, = -bbi, b2, b3, b4, bs, 26). where its input variable æg is kept as the original embedding, and the other five input variables are replaced with the corresponding baseline values, i.e. 21 = b1 22 b2, 43y = by, 44 b,. It bg. The third masked sample is X2;- (b), by by, by Vi, by where its input variable Is is kept as the original embedding, and the other five input variables are replaced with the corresponding baseline values, i.e., Iι b,, 22 b2, 23 ba. I4 64, 26 bg- The fourth masked sample is X7; = (bi, b2, by, b4, Ts, )te, where its input variables 225 and mg are kept as the original embedding, respectively, and the other four input variables are replaced with the cor- responding baseline values. Similarly, the 63rd masked sample is XT = { 22, I3, I4, Hs, b where its input variables I1, I2, I3, 24, 2y are kept as the original embedding, respectively, and Is = bg. The 64th masked sample is XTea = {I1, T2, F3, Fz, Zs. / where all input variables are kept unchanged from the original embedding.
Step 4: For each masked sample x E (0,1,-.. 63). we computed the log-odds output of the p(y=g""h>e) ground-truth label vxx,)) ) = log 1-pl 1-p(y=y xry) E I as the model output. In this way, feeding all masked samples X1, into the BERT BASE model produced a total of 2 model outputs BASE (x1s). ) BASSE ), ... ...,, ( Feeding all masked samples XT, into the BERTLARGE model pro- duced total of 26 model outputs (LARGE((xI,) ). LLARGE
L.LGGGE (xTaa).
BASE (xr,) = 0.5g BASE (x1;) + VI; jj E (.. 63) Step 5: Computed the AND outputs w and the OR outputs (BASE(xx)) ) 0.5z (xr,) "T,
BASE
BASE
.j E 1, 1,... 633 for the BERT BASE
LARGE .j E model, respectively. Computed the AND outputs (LARGE(XX) (XT;) = LARGLA (xT;) + TT;
and {0, 1,... .6). and the OR outputs e LARGG (XT,) L.GGE (XT;) ) - IT3 (XT,
LARGE .j {0, (0.1.....,6 63)
for the BERTLARGE model, respectively.
Step 6: Computed the AND interactions
B (T,SE)TT)))))))))))){)) Ergr, (11) BASE (XT),J and 1 BBASE = - - (-1) BASE (xNxT), (IASS()))) E
{0, 10.,,...,600 .63) and the OR interactions
10 633 for the BERTBASE model, respectively. Computed the AND interactions und
LARGE (T, and
E-cr,(-1)(;) (-1)
,.LARGE ( E 10, 63) and the OR interactions
I LARGE (T)lx) -ErST, (-)) 11LLLAE ( E {0, 10,,, 633 for the BERT BERTLARGE LARGE
model, respectively.
20

---

from the Published as a conference paper at ICLR 2024
Table 2: Diversity of two sets of interactions, which are extracted based on Equation same models but with different initialized parameters }rr).
DNNs
Sand
Sor
BERT BASE 10.90%
16.18% 20.90%
BERTLARGE
17.84%
Step 7: Learned the parameters "T,
BASE and LARGE , E {0, 1,.... 633 using the loss in Equation IT, (6). Went back to Step 5 and repeated the iterations until the loss converges.
Step 8: Computed the final AND interactions _ (T) [ |x) and the final OR interactions BBASE ( {0, 1,... 63) for the BERT model using the learnable parameters "T) . (0.1, 1,.. 63}. The final salient interactions of the BERT BASE model are obtained from all 26 inter- actions, where the final salient interactions are those with interaction values greater than the thresh- old , BASE BASE = {T) S N B (I' |x) > BBSSE..
BASE
Computed the final AND interactions [ (T}lx) and the final OR interactions |LARGE (T; x).. E {0, 1, ... 63} for the BERTLARGE model using the learnable parameters "Tyy 10. 63). The final salient interactions of the BERT model are obtained from all 26 interactions, where the final salient interactions are those with interaction values greater than the threshold LLARGE QLARGE
LARGE j E
{T, NN:
andior (Ty|x)] fLARGE].
M MATCHING PRECISION OF AND-OR INTERACTIONS
In this section, we conducted experiments to show the matching precision of the interactions used for matching the network output. Specifically, we extracted traditional AND-OR interaction primitives using various DNNs trained on different datasets following the settings in (Li & Zhang 2023b
E se interatioos)
[I(S]]
Then, we used the metric
Ese [tpp incoutions)
[+ u(N)-v(0)-E se (top iinerustio))ss ((S)
measure
the matching precision of the salient interactions. Figure 11 shows the matching precision of the in- teractions when we computed m based on different numbers of most salient interactions. We found that only few salient interactions were required achieve relatively high matching precision.
MLP-5 on wifi
ResNet- MNIST-3
VGG-
Leflet
AlexNet on selebA--yeggosses
matching precision
10% matcching enor matching ertor
34
of interactions for matching
of interactions for matching
# Interactionn for matching
A interactioon matching A interactions for matching
Figure 11: Matching precision of the interactions used for matching the network output.
N MORE EXPERIMENTS
N. OPTIMIZING THE LOSS IN EQUATION MAY LEAD TO DIVERSE SOLUTIONS
In Section 2.3.1 we mentioned that optimizing the loss in Equation may lead to diverse solutions. Given different initial states, optimizing the loss in Equation 4 usually extracted two different sets of AND-OR interactions. In particular, sets of parameters {rr} as PT (0, 1). the loss in Equation (4) would learned dramatically different interactions with only 21 % overlap. Figure [ furthr shows the top 5 AND-OR interaction primitives extracted from BERT LARGE model on an imput sentence. Both experiments illustrate that given different initial states, the loss in Equation (4) may learn different AND-OR interactions.
shown in Table 2 when set the initial state of two
21

---

Published as a conference paper at ICLR 2024
and
and
and players av synchrunized swimmer
and
Init 1
swimmer
plays
dr y avi wet
dr yy
3.26
3.13
3.04
and
Init 2
plays
plays -ow3 aw wool
jelmmmr
whole dr -ows wet
A.26
3,49
3.37
3.34
3.28
The whole thing plays out with the dr-ows-y he-avi-ness of synchronized swimmer weoring wool wet-suit.
Figure 12:
Top 5 AND-OR interaction primitives extracted from LARGE model, when optimiz-
ing the loss in Equation 4
given different initial states.
N.2 EXAMINING WHETHER THE INTERACTIONS CAN EXPLAIN THE NETWORK OUTPUT
we mentioned to conduct experiments to examine whether the extracted AND-OR interactions could still accurately explain the network output, when removed the error term. Fig- ure 13 shows matching errors of masked samples for all subsets T N when we sorted the network outputs for all 2n masked samples in descending order. It shows that the real network output was well approximated by interactions.
In Section 2.3.2
DNN'S output D(X,))
BERT
BERT
-5.0
200
400
600
800
1000
200
400
600
800
1000
index of interactions
index of interactions
Figure 13: Universal matching of interaction primitives the DNN's output. Shade area indicates the matching error of different v(xr).
O EXPERIMENTAL DETAILS
O.1 PERFORMANCE DNNs
In Section we conducted experiments using several DNNs trained on different types of datasets, including the language and image datasets. In the sentiment classification task, we fintuned the pretrained models, BARTBASE and BERT using the SST-2 dataset. For image classification task, we trained ResNet-20 and VGG-16 16 with the MNIST-3 dataset. Tebpet3 the classification accuracy of the aforementioned DNNs. For the dialogue task, we used the pretrained models, the LLaMA model and O.T- model, directly.
Table Classification accuracy of different DNNs in the sentiment classification and image classi- fication tasks.
Tasks
dataset
DNNs
BERT BASE 91.32%
BERT 93.26%
sentiment classification
SST-2
ResNet-20 100%
VGG-16
image classification
MNIST-3
100%
O.2 THE SELECTION OF INPUT VARIABLES FOR INTERACTION EXTRACTION
This section discusses the selection of input variables for extracting interactions. As mentioned in Section 2.2 given input sample with input variables, extracted most 2n interac-
22

---

Published as a conference paper at ICLR 2024
tions. Therefore, the computational cost for extracting interactions increases exponentially with the number of input variables. For example, we take a word in a sentence (or a pixel in an image) as an input variable, the computation is usually inapplicable. To alleviate this issue, we followed (Shen et al. 2023) to select set of words as input variables and leave other words as the constant back- ground to compute interactions between them. Specifically, we selected 8-10 input variables for each sample in the three tasks. We only extracted the interactions between the selected variables, leaving the rest of the unselected input variables unchanged as background.
For sentences in the SST-2 dataset, we first tokenized the input sentences and selected tokens as input variables for 200 samples. For each sentence in this dataset, some words have no clear se- mantics for sentiment classification, i.e., stop words containing dummy words and pronouns, and consequently, there little interaction within their corresponding tokens. Therefore, we bypassed these tokens without clear semantics, and only selected tokens among the remaining semantic to- kens. To facilitate analysis, we randomly selected n tokens as input variables for sentences with more than 10 semantic tokens. The masking of input variables was performed at the embedding level.
For sentences in the SQuAD dataset, we took first several words in each document the input sample to the DNN. Specifically, we selected the first 30 words in each document as the input sample and the 31st word as the target word, provided that the following conditions were met: 1) The 31st word possessed clear semantic meaning. which means that it did not belong to the category of stop words. 2) The five words immediately preceding the target word did not constitute sentence-ending punctuation marks, such as full stop. If eitee of these conditions was not satisfied, we extended the initial 30 words until all requirements were fulfilled, and selected the next word as the target word. When extracting interactions, we randomly selected a set of n = 10 words which have semantic meanings as input variables. It's worth noting that single word can correspond multiple tokens, so when we masked a specific word, we masked all of its corresponding tokens. The masking of input variables was performed at the embedding level.
For images in the MNIST-3 dataset, we manually labeled the semantic part for 100 positive sam- ples (digit 3) by following (Li Zhang, 2023b). For each image in this dataset, most of the pixels are black background pixels with semantic information, and consequently, there is no interaction within these black pixels. Thus, we considered interactions only within foreground pixels. Specif- ically, we divided whole image into small patches of size x 3 and selected
8 patches in the foreground of an image as input variables. Following (Li & Zhang 2023b), we used the zero patches as the baseline values to mask the unselected patches E N T in the sample.
23


Reviews:
[{"review_id": "8NOtmjUgjP", "reviewer": "Reviewer_f9us", "summary": "The paper begins by revisiting Harsayni's 1963 decomposition of Shapley values into \"and\" cohorts, and extends the idea to a claim that the output of a neural network can be decomposed into sparse contributions from \"and\" and \"or\" cohorts (Theorem 3).  Then it observes that such a composition could be ambiguous, and that it might not generalize to other models of the same data.  Then it proposes a framework for finding small and/or cohorts by optimizing for sparsity (eq 4), and further for maximizing sparsity while blending in another loss term that takes account sharing of variables in some way (eqs 5, 6).  Then it introduces a noising scheme (page 7) and proposes optimizing the search for cohorts in the presence of some level of noise.  Finally, the paper sets up experiments to search for such and/or cohorts within the behavior of a few large neural networks, examining extremely small subsets of the behavior of those network (reducing to 8-10 input variables), by manually selecting 8 patches within MNIST images of \"3\"s and 10 tokens for each set of inputs for SQuAD and SST-2 data sets, and examining the ability to find and/or cohorts that explain behavior of BERT, Llama, ResNet, etc.  It claims that with these methods it able to distinguish interactions that are shared between different models, and interactions that are in common.", "questions": "What is the runtime complexity of the method?\nIn the three data settings (or in the half dozen models) what are the actual numbers of cohorts of AND and OR variables that are found that achieve a specific high level of faithfulness?\nHow are features discretized for analysis?\nWhat are the units of measure for interaction strength?\nWhat can we conclude about the similarity between VGG and ResNet, or the similarity between BERT base and BERT large?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The goal of trying to fully explain a neural network's behavior by decomposing it into just AND and OR interactions is admirable, and so is the ambition of attempting to apply such analysis to huge models such as Llama and BERT and VGG-16.\n\nThe focus on looking for commonalities between different models is interesting: it is an open and interesting question whether different models trained to solve the same task solve them in the same way or different ways, and how to understand the differences.", "weaknesses": "The paper does not refer to other work in examining shared features between networks, for example: https://arxiv.org/abs/2306.09346\n\nThe conclusions drawn from the paper are both noncommittal and unconvincing.  For example, the paper claims \"The sparsity and universal-matching property of interactions provide lots of evidence to faithfully explain DNNs with interactions.\"  However, the methods are considered over only tiny subsets of just 8 or 10 features, (e.g., explained in appendix G, just 8 hand-chosen patches of images of MNIST \"3\" digits, or just 10 words out of the hundreds for each example in the NLP data sets).  As a result, what is being explained with these methods cannot be claimed to be faithful to \"ResNet\" or \"BERT Large,\" but actually a very miniscule slice of the behavior of those huge networks.  The claim of faithfulness is not backed up empirically.\n\nThe methods are not clearly presented.  The main method comes down to Equation 6.  However most of the pages of the paper are spent on discussing Theorem 3, which is only tangentially related to the method and which does not clarify what the method actually does. For example, how continuous neural network features are discretized for the and-or analysis is not discussed at all.  How the search to optimize the discrete objective in Eq 6 is not discussed, and the level of sparsity, or the number of cohorts found in a typical solution is not revealed in concrete terms. If the goal is to clearly explain the method, it would be more helpful to move the tangential theorems to the appendix and spend more pages explaining equation 6 more precisely, with both concrete examples of how the interaction matrices are formatted, and concrete examples of how a search over cohorts would work in a specific small example.  Since runtime seems to be a major concern, it should be discussed. The size of the sets of features is small enough that it seems that a real-data example of how the method operates on a single example could be shown in detail.\n\nThe experiment results are very unclear, and it seems like it would be very difficult to reproduce the results given the information provided.  For example, in results in Fig 2 and 3 the y axis \"Interaction Strength\" is not explained other than that \"it is in log space\" or \"it is the ratio of shared interactions\".  What number is this this strength, and in what units? Beyond the lack of units, after the results are shown, they are not analyzed.  By analyzing the log-odds output of the ground-truth label, it looks like it is measuring faithfulness, but the plot captions claim a measurement of \"interaction strength\".  How interactions are being measured is not clear.  There is a very tiny 1/20 |I(s)|_max inside one of the plots that looks like a hint, but it is not explained.  Similarly, the units for Figure 4 are not explained.  All experiments are compared to a \"Traditional\" baseline which is not explained or summarized other than a reference to \n\nFigure 5 shows some qualitative differences, but it is not clear what conclusions should be drawn from the differences.  For example, it shows that a disjunction \"Ring just cold wet Seattle...\" etc is promoted from the \"Distinctive interactions\" column using Traditional methods to the \"Shared interactions\" column in the Our method.  Is this a success or is this a failure?  If there are two different ways of identifying the interactions, does the new way provide more insight?  Or are they just different? Figure 5 select \"some of the sailent\" interactions - is it cherry-picked?  What does it look like when not?", "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": "", "extra_scores": {}}, {"review_id": "Bj480LkqQJ", "reviewer": "Reviewer_GVkW", "summary": "The main challenge in explainable AI is to effectively summarize the knowledge encoded by a deep neural network (DNN) into a few symbolic primitive patterns without losing significant information. To tackle this, Ren et al. (2023) established a series of theorems demonstrating that a DNN's inference score can be explained as a small set of interactions between input variables. However, these interactions lack generalizability and thus cannot be considered as faithful primitive patterns encoded by the DNN. To address this, the authors propose  a method to extract interactions that are common to different DNNs trained for the same task.", "questions": "See weekness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper is well-written and easy to follow.\n- The experimental design is comprehensive, covering aspects of both NLP and vision, which provides a broad perspective.\n- The paper focus on the interesting the generalization problem of interaction , which is a interesting problem.", "weaknesses": "- The paper does not sufficiently explain why generalizable interactions are important for AI interpretability. Although generalizability is critical in AI algorithms, especially when dealing with different tasks or data from different domains. However, the authors focus on explainable AI, and the generalizability is defined on different models of the same task, which does not align with the conventional understanding of DNN generalizability.\n- The proofs in the paper rely on two papers currently under review ([1,2] See appendix C). This poses a problem as the validity and peer-review status of these references are uncertain. Moreover, it would be beneficial for the readers if detailed derivations of Equation 11 were provided to better understand and verify the proofs.\n- While the paper provides a clear mathematical definition for generalizable interactions, it lacks a discussion on the existence of generalizable interactions. Moreover, the method proposed in the paper is derived heuristically using Occam's Razor principle instead of being grounded on mathematical theorems satisfying the definition. The paper does not satisfactorily address why this approach would yield generalizable interactions.\n- The experimental section of the paper only compares the proposed method with a single baseline. Including more baselines could strengthen the paper's persuasiveness.\n\n[1] Technical note: Defining and quantifying and-or interactions for faithful and concise explanation of dnns.\n\n[2] Where we have arrived in proving the emergence of sparse symbolic concepts in ai models.", "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": "", "extra_scores": {}}, {"review_id": "wMWzOKj3or", "reviewer": "Reviewer_MRpB", "summary": "This paper delves into the realm of deep neural networks (DNNs), addressing a critical gap in understanding the interactions encoded by these models. Unlike existing interaction extraction methods, which lack theoretical guarantees for transferability, this work introduces a precise definition for the transferability of interaction primitives. Building on this foundation, the authors propose a novel method aimed at extracting interactions with maximal generalization power across different DNN architectures. Extensive experiments across language and image domains validate the effectiveness of the proposed method, demonstrating enhanced generalization of extracted interactions.\n\nThis paper makes a significant stride in demystifying the interactions encoded by deep neural networks, introducing novel concepts and methodologies backed by solid experimental evidence. Addressing the highlighted weaknesses and questions will further fortify the paper's contributions, making it a valuable addition to the field of DNN interpretability.", "questions": "1. Parameter Sensitivity: Could the authors provide a more comprehensive analysis on the choice and sensitivity of α? An ablation study exploring how variations in α affect the outcomes would enhance the paper’s rigor.\n\n2. Discrepancies in Performance: What factors contribute to the observed variations in performance improvements across different tasks? A detailed examination of this phenomenon would provide clarity and strengthen the paper’s contributions.\n\n3. Exploration of Interpretability: Can the authors elaborate on whether the distinctive interactions extracted from more powerful models, such as BERT-large, result in enhanced interpretability? An in-depth discussion on this aspect would be highly beneficial.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Relevance and Timeliness: Given the burgeoning interest in interpretability of DNNs, this paper tackles a pertinent and significant problem, contributing to a better understanding of how DNNs encode interactions.\n\n2. Innovative Conceptualization: The introduction of \"interaction primitive transferability\" is a novel and insightful contribution, offering a new lens through which to evaluate and understand interaction primitives in DNNs.\n\n3. Rigorous Experimental Validation: The authors have conducted a comprehensive set of experiments across various settings and domains, including both language and image data, which robustly demonstrate the effectiveness of the proposed method.", "weaknesses": "1. Clarification on Parameter Selection: The paper could benefit from a more detailed discussion on the choice of the parameter α, including its impact on the balance between two competing objectives and its sensitivity to variations.\n\n2. Inconsistencies in Performance Improvements: The observed discrepancies in performance improvements between different tasks (i.e., more pronounced improvements in BERT-base and BERT-large compared to LLaMA and OPT-1.3B) warrant a deeper investigation and explanation.\n\n3. Interpretability of Extracted Interactions: While the paper demonstrates the effectiveness of the proposed method in extracting distinctive interactions, a more explicit exploration of the interpretability of these interactions, especially in the context of more powerful models like BERT-large, would add valuable insights.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)