Towards the Dynamics of a DNN Learning Symbolic Interactions
Authors: Qihan Ren
Junpeng Zhang
Yang Xu
Yue Xin
Dongrui Liu
Quanshi Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: deep learning theory
learning theory
knowledge representation
Primary area: learning_theory
TL;DR: We prove the two-phase dynamics of a DNN learning interactions in the training process.

Abstract: This study proves the two-phase dynamics of a deep neural network (DNN) learning interactions. Despite the long disappointing view of the faithfulness of post-hoc explanation of a DNN, a series of theorems have been proven [27] in recent years to show that for a given input sample, a small set of interactions between input variables can be considered as primitive inference patterns that faithfully represent a DNN's detailed inference logic on that sample. Particularly, Zhang et al. [41] have observed that various DNNs all learn interactions of different complexities in two distinct phases, and this two-phase dynamics well explains how a DNN changes from under-fitting to over-fitting. Therefore, in this study, we mathematically prove the two-phase dynamics of interactions, providing a theoretical mechanism for how the generalization power of a DNN changes during the training process. Experiments show that our theory well predicts the real dynamics of interactions on different DNNs trained for various tasks.

Towards the Dynamics of a DNN Learning Symbolic Interactions
Qihan Ren "en'", Junpeng Zhang 12,, Yang Xu², Yue Xin', Dongrui Liu Quanshi Zhang' 't 'Shanghai Jiao Tong University "Beijing Institute for General Artificial Intelligence ZZejiang University *Shanghai Artificial Intelligence Laboratory frenqihan, zhangip63, zqs1022)0ajtu. edu. cn
Abstract
This study proves the two-phase dynamics of deep neural network (DNN) learning interactions. Despite the long disappointing view of the faithfulness of post-hoc explanation of a DNN, a series of theorems have been proven [27] in recent years to show that for given input sample, a small set of interactions between input variables can be considered as primitive inference patterns that faithfully represent DNN's detailed inference logic that sample. Particularly, Zhang al. [41] have observed that various DNNs all learn interactions of different complexities in two distinct phases, and this two- woophhse dynamics well explains how DNN changes from under-fitting to over-fitting. Therefore, in this study, we mathematically prove the two-phase dynamics of interactions, providing theoretical mechanism for how the generalization power of a DNN changes during the training process. Experiments show that our theory well predicts the real dynamics of interactions on different DNNs trained for various tasks.
Introduction
Background: mathematically guaranteeing that the inference score of a DNN can be faithfully explained as symbolic interactions. Explaining the detailed inference logic hidden behind the output score of DNN is considered one of the issues for the post-hoe explanation of DNN. However, after comprehensive survey of various explanation methods, many studies (8 [2 have unanimously and empirically arrived disappointing view of the faithfulness of almost all post-hoc explanation methods. Fortunately, the recent progress (27) has mathematically proven that given a DNN for a classification task usually only encodes small set of interactions between input variables in the sample. It is proven that these interactions act like primitive inference patterns and can accurately predict all network outputs, no matter how we randomly mask the input sample"] An interaction refers to non-linear relationship encoded by the DNN between a set of input variables in S. For example, as Figure shows, a DNN may encode non-linear relationship between the three image patches in $ (21, x2, 233 to form dog-snout pattern, which makes a numerical effect I(S) on the network output. The complexity (or order) of an interaction is defined as the number of input variables in the set S, i.e., order(S) = |S|
specific input sample (.-, , 2x.]"
Our task. Since Zhou et al. 44 found that high-order (complex) interactions usually have much higher risk of fittingt than low-order (simple) interactions, in this study, we hope to further track
"Equal contribution.
"Quanshi Zhang is the corresponding author. He is with the Department of Computer Science and Engineering, the John Hoperoft Center, at the Shanghai Jiao Tong University, China. zqs10220sj edu. cn.
'The proof 27 requires the DNN generate relatively stable inference outputs on masked samples. which is formulated by three mathematical conditions (see Appendix (B). It is found that DNNs for image classification, 3D point cloud classification, tabular data classification, and text generation
'It proven that matter how we randomly mask variables of the input sample, we can always use numerical effects a few intcractions to accurately regress the network outputs on all masked samples.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Network output v(2)
Interacionn-bwedd lugical modell
rog
Σn.
s)
10500
[b]
DNN usually only small number of salient interactions
Model equivalence
(r(5)1))-022
.M
6s (x0=0.0
1.0
VGG-15 on Mhit
interactions with sallent effects
The AND--R logical model alomys accuratcly mimicis cutputs the DNN on all masied samples
Moat interactions have
negligitee wffectss
index intteartitts
1d
Distribution of interaction
Change the distribution interaction strength throughout training process
strength rexl over different orders
order
10
10
10
10
1st phase
2nd phase
Figure 1: (a) is proven that the DNN's inference on a certain sample is equivalent to a logical model that uses small number of AND-OR interactions for inference. Each interaction corresponds to non-linear (AND or OR) relationship between a set S of input variables (e.g., image patches). (b) Sparsity of interactions. We show the strength [(S] of all 2 interactions sorted in descending order. (c) Illustration of the two-phase dynamics of a DNN learning interactions of different orders.
the change in the complexity of interactions during training, so as to explain the change of the DNN's generalization power during training. In particular, the time when the DNN starts to learn high-order (complex) interactions indicates the starting point of over-fitting,
Specifically, we focus on the two-phase dynamies of interaction complexity which was empiri- cally observed by [41], and we aim to mathematically prove this dynamics. First, before training. a DNN with randomly initialized parameters mainly encodes interactions of medium complexities. As Figure shows, the distribution of interactions appears spindle-shaped. Then, in the first phase, the DNN climinates interactions of medium and high complexities, thereby mainly encoding interac- tions of low complexity. In the second phase, the DNN gradually learns interactions of increasing complexities. We have conducted experiments to train DNNs with various architectures for different tasks. It shows that our theory can well predict the learning dynamics of interactions in real DNNs.
The proven two-phase dynamics explain hidden factors that push the DNN from under-fitting to over-fitting (1) In the first phase, the DNN mainly removes noise interactions, (2) In the second phase, the DNN gradually learns more complex and non-generallzaable interactions toward over-fitting.
2 Related work
Long-standing disappointment on the faithfulness of existing post-hoe explanation of DNNs. 15 have explained the inference score of DNN, but how to mathemati- cally formulate and guarantee the faithfulness of the explanation still an open problem. For example, using interpretable surrogate model to approximate the output of a DNN 3
Many studies 33 40 29,
is classic explanation technique. However, the good matching between the DNN's output and the surrogate model's s output cannot fully guarantee that the two models use exactly the same inference patterns and/or use the same attention. Therefore, many studies 28 12 have unanimously and empirically arrived at disappointing view of the faithfulness of current explanation methods. Rudin (28) pointed out that inaccurate post-hoc explanations of DNNs would be harmful to high-stakes applications. Ghassemi et al. [12] showed various failure cases of current explanation methods in the healthcare field and argued that using these methods to aid medical decisions was a false hope.
35 34
New progress towards proving the faithfulness of symbolic explanation of DNN. Despite the disappointing view of post-hoc explanation methods, we have established a theory system of interactions within three years, which includes more than 30 papers, quantify the symbolic concepts encoded by a DNN and explain the hidden factors that determine the generalization power and robustness of DNN. We revisit this theory system as follows.
Proving interactions act as faithful primitives inference patterns encoded by the DNN. Recent achievements in the theory system of interactions have provided a new perspective to formulate primitive inference patterns encoded by DNN. We discovered 2 and proved [27] that DNN's inference logic on a certain sample can be explained by only a small number of interactions. Further- more, we discovered that salient interactions usually represented common inference patterns shared by different samples (sample-wise transferability of interactions) 21), and proposed a method to extract generalizable interactions shared by different DNNs (model-wisc transferability of interactions) [4.

---

The above studies indicated that salient interactions could be considered primitive inference patterns encoded by a DNN, which served as the theoretical foundation of this study. Based on interactions, we also defined and learned the optimal baseline value for the Shapley value [25] and explained the
encoding of different types of visual patterns in DNNs for image classification 6
Using interactions to explain the representation power of DNNs. Our recent studies showed that interactions well explained the hidden factors that determine the adversarial robustness [24]. adversarial transferability [37], and generalization power [44 of a DNN. We also discovered and proved the representation bottleneck of a DNN encoding middle complexxity interactions [7]. In addition, we proved that compared to a standard DNN, Bayesian neural network (BNN) tended to avoid encoding complex interactions (26), thus explaining the good adversarial robustness of BNNs. We discovered and explained the phenomenon that DNNs tended to learn simple interactions more casily than complex interactions [22]. We found that complex interactions were less generalizable than simple interactions [44), and further discovered the two-phass dynamics of a DNN learning interactions of different complexities 44. To this end, this study aims to theoretically prove the discovery in 41 to better understand the two-phase dynamies of interactions.
Using interactions to unify the common mechanism of various empirical deep learning methods. We proved that fourteen attribution methods could all be explained as a re-allocation of interaction effects (8) We proved that twelve existing methods to improve adversarial transferability all shared the common utility of suppressing the interactions between adversarial perturbation units [42].
3 Dynamics of interactions
3.1 Preliminary: interactions
Let us consider a DNN and an input sample æ [_r,... _ with input variables indexed by N = (1.... n). In different tasks, one can define different input variables, e.g., each input variable may represent image patch for image classification or a word/token for text classification. Let
us consider a scalar outpuf of a DNN, denoted by v(xr) E R. Previous studies 4 43 show that the
output score v(z) can be decomposed into the sum of AND interactions and OR interactions.
((x) = v(zz) + EOAscN and (S|x) + Σ L (S)x))
0FSEN Lor
(I)
UASCN
where the computation of (S|x) and Lor(S will be introduced later in Eq.
How to understand the physical meaning of AND-OR interactions. Suppose that we are given an input sample æ. According to Theorem 2 non-zero interaction effect Tana (S] (/)r)) indicates that the entire function of the DNN must equivalently encode an AND relationship between input variables in the set C N, although the DNN does not use an explicit neuron to model such an AND relationship. As Figure shows,, when the image patchs in the set S. (21 nose, 22 tongue, 23 = check) are all present (i.e., not masked), the three regions form a dog-snoul pattern, and make a numerical effect [Sg push the output score u v(z) towards the dog category. Masking any image patch in S2 will deactivate the AND interaction and remove Ladd (S2 x)) from (x)) This will be shown by Theorem 2 Likewise, Iar (S(x)) can be considered as the numerical effect of the OR relationship encoded by the DNN between input variables in the set S. As Figure [ shows, when one of the patches in S (ar, = spotry regionl, , 3z spotty region2) is present, a speckles pattern is used by the DNN to make a numerical effect Tor (S1 (æ:) on the network output u(xz).
Definition and computation. Given DNN and input æ, the AND-OR interactions between each specific set of input variables S C (S * i) are computed as follows
Inaa( (S|zz) = (-
Unnd (xT), Jor (S(x)) = EErss (-1))s1-121 14' var (INYT), (2)
where Tr denotes the sample in which input variables in N \ T are masked while input variables in T are unchanged. The network output on each masked sample u v(zr), T S N, is decomposed into two
'For example, one may set e(æ) the loss value sample æ. For multi-category classification task, one usually either set v<x) to the output score the ground -ruth category before the softmax operation, or
follow 7 to set (zz) = log I-p(ymhhay See Table for summary of mathematical settings for interactions.
'The masked states of input variables are represented by specific baseline values b = [b,,,".,,b b..]" by following (1). See Appendix G.3 for the detailed setting of baseline values.
3

---

components: (1) the component (#r(( = (.5 +rr that exclusively contains AND interactions, and (2) the component U (2T) (w)) yr that exclusively contains OR interactions. subject
to e(ær) (PT) + For (fr). Appendix F.1 shows that (ar) r r( + Lessect (S" m) and
(xr) = S N: (S"(z)) The sparsest AND-OR interactions are extracted by minimizing [S]=a) Please see Appendix C for details about the computation and Appendix D for mathematical support of the coefficient in Eq.
the following objective 200 : min(r7) } Σ scN Ma (S]= +
Salient interactions and noisy patterns. Let us enumerate all 2n combinations of variables 5 S N, and compute the interaction effects [S)() and (S) We can identify a few salient interactions from all these interactions, i.e., interactions whose absolute value exceeds a threshold (S)x()) 2 or [S]x) 2 r). Other interactions have small effects and are termed noisy patterns.
Theorem 1 (Sparsity property, proven by (27. and discussed in Appendix BB. Given a DNN and an input sample x with n input variables, let dnl {S S N (S((()))z)) 2 7] denote the ser of salient AND interactions whose absolute value exceeds a threshold T. If the DNN can generate relatively stable inference outputs v(ærs) on masked samples] then the size of the set [S]] has an upper bound of On5 /T), where & is intrinsic parumeter for the smoothness of the network functiinn vi.)) Empirically, & is usually within the range of [1.9,2.2].
Theorem 2 (Universal matching property, proven in [4] and Appendix F.I. Given an input sample a. let us construct the following surrogate logical model f(-) to use AND-OR interactions for inference. which are extracted from the DNN v(-) on the sample i:. Then, the output of the surrogate logical model f() can always match the output of the DNN v(.), ), no malter how the input sample is masked.
VS C N, f(ts) = m((s), f(+s)= = x( > aad (1)))-
AND relation T)
dy ufigerss
Σ (T TCN
OR relation T
s triggers
(3)
TEN
(alling)
Fertin)
-I( m0)) + Eoyres Tand (Tpr= +t ETgNAmSH Tor (T(==))
(4)
so u1( - #ra) + EVERRWerEES Imm (T| + ETeRumsSS Tor (Txx=)),
(5)
where Pand is the set of all salient AND interactions, and Der the set of all salient OR interactions.
What makes the interaction-basee explanation faithful. The following four properties guarantee that the inference score of DNN can be faithfully explained by symbolic interactions.
Sparsity property. The sparsity property means that a DNN for a classification task usually only encodes small number of AND interactions with salient effects, ie., for most of all 2" subsets of input variables S C N, I (z) has almost zero interaction effect, Specifically, the sparsity property has been widely observed on various DNNs for different tasks (21. and it also theoretically proven (see Theorem D. The number of AND interactions whose absolute value exceeds the threshold T ((aaa (S)==]] 2 r), is (nf//)), where E empirically within the range of [1.9, 2.2]. This indicates that the number of salient interactions is much less than 2". Furthermore, the sparsity property also holds for OR interactions, because an OR interaction can be viewed as special kind of AND interaction
Universal matching property. The universal matching property means that the output of the DNN on a masked sample &s can be well matched by the sum of interaction effects, no matter how we randomly mask the sample and obtain øss. This property is proven in Theorem 2
Transferability property. The transferability property means that salient interactions extracted from one input sample can usually be extracted from other input samples as well. If so, these interactions considered transferable across different samples. This property has been widely observed by 21 on various DNNs for different tasks.
"This is formulated by three mathematical conditions. (1) The DNN does encode highly complex interactions. (2) Let us compute the average classification confidence when we mask different random sets of k input variables (generating (ær : | = n k}). Then, the average confidence monotonically decreases when more input variables are masked. (3) The decreasing speed of the average confidence is polynomial. See Appendix ( for the detailed mathematical formulation.
"If we Hip the masked state and the presence state of each input variable (i.e., taking by as the presence state of the i-th variable, while taking 2; the masked state), then OR interactions can be viewed as special kind of AND interactions. See Appendix E for details.

---

Extracting interactions from different time points during training
O
Gap training loss and testing loss
Time point 1
Time point 2
Time point
Time point
Time point
Time point 6
Six time points
Aleffitt
onder A
order A
order 2
order
order
order
training epochs
V0S-11 CIRAR 30
Six time points
100
8
order A
order A
order 8
order
order
order
training epochs
BERT Meduu
Six time points
SET-2
0r0or K
order
order
order
order
ordor
training epochs
Figure 2: The distribution of interaction strength 7 over different orders k. Fach row shows the change in the distribution during the training process. Experiments showed that the two-phase phenomenon widely existed on different DNNs trained on various datasets. It also verified the finding in [4 that the beginning of the 2nd phase was temporally aligned with the time point when the loss gap increased. Please see Appendix I.1 for results on the other six DNNs trained for 3D point cloud/image/sentimen classification.
Discrimination property. This property means that the same interaction extracted from different samples consistently contributes to the classification of a certain category. This property has been observed on various DNNs (1],, and implies that interactions are discriminative for classification.
Complexity/order of interactions. The complexity (or order) of interaction is defined as the number of input variables in the set S, i.e., order(S) def [S). In this way, a high-order interaction represents a complex non-linear relationship among many input variables.
3.2 Two-phase dynamics of learning interactions
Zhang et al. 41 have discovered the following two-phase dynamics of interaction complexity during the training process. (1) As Figure 2 shows, before the training process, the DNN with randomly initialized parameters mainly encodes interactions of medium orders. (2) In the first phase, the DNN removes initial interactions of medium and high orders, and mainly encodes low-order interactions. (3) In the second phase, the DNN gradually learns interactions of increasing orders.
To better illustrate this phenomenon, we followed 41 to conduct experiments on different DNNs, including AlexNet [171. VGG (31, BERT 99 DGCNN [38] and on various datasets, including
image data (MNIST 19. CIFAR-10 16. CUB-200-2011
36 and Tiny-ImageNet (18), natural
language data (SST-2
32 ), and point cloud data (ShapeNet
39 For image data, followed 41I
to select a random set of ten image patches as input variables. For natural language data, we set the entire embedding vector of each token as an input variable. For point cloud data, we took point clusters as input variables. Please see Appendix G.3 for the detailed settings. We set v(zr)= log (p(y" muth [m)[[1 p(y" muth [==]] by following [7]. where p(y muth (z) denotes the probability of classifying the input sample æ to the ground-truth category. We followed [41] to define the in-
teraction whose absolute value is greater than or equal to 0.03 Eg [[=()) - m[(r))]] as salient interaction. For interactions of each k-th order, we normalized the strength of salient interactions as 1(4) Ex (E ( (and.ur) Σ 1k (S)))) (S)=))) I/Z to enable fair comparison between dif-
ferent training epochs") where Z Eis Ex EE (and. 3s 22 (ype denotes
the normalizing constant.
Figure shows how the distribution of interaction strength (()) of different orders changed throughout the entire training process, and it demonstrates that the two-phase dynamics widely existed on different DNNs trained on various datasets. Before training, the interaction strength of medium orders dominated, and the distribution of interaction strength of different orders looked like a spindle. In the first phase (from the 2nd column to the 3rd column in the figure), the strength of medium- and high-order interactions gradually shrank to zero, while the strength of low-order interactions
'The normalization removes the effect of the explosion of output values during the training process and enables us to only analyze the relative distribution of interaction strength.
5

---

increased. In the second phase (from the 3rd column to the 6th column in the figure), the DNN learned interactions of increasing orders (complexities).
How to understand the two-phase phenomenon. Previous studies 26 have observed and partially proved that the complexity/order of an interaction can reflect the generalization ability foility" the interaction. Let us consider an interaction that is frequently extracted by DNN from training samples (see the transferability property in Section 3.2) If this interaction also frequently appears in testing samples, then this interaction is considered generalizable" 10 otherwise, non non-generalizable. To this end, Zhou al. [4 have discovered that high-order (complex) interactions are less generalizable between training and testing samples than low-order (simple) interactions. Furthermore, Ren et al. [26] have proved that high-order (complex) interactions are more unstable than low-order (simple) interactions when input variables or network parameters are perturbed by random noises.
Therefore, the two-phase dynamics enable us revisit the change of generalization power of DNN:
Before training. the interactions extracted from an initialized DNN exhibited a spindle-shaped distribution of interaction strength over different orders. These interactions could be considered random patterns irrelevant to the task, and such patterns were mostly of medium orders.
2. In the first phase, the DNN mainly removed the irrelevant patterns caused by the randomly initializzdd parameters. At the same time, the DNN shifted its attention to low-order interactions between very few input variables. These low-order interactions usually represented relatively simple and generalizable" 10 inference patterns, without encoding complex inference patterns.
3. In the second phase, the DNN gradually learned interactions of increasing orders (increasing complexities). Although there was no clear boundary between under-fitting and over-fitting in mathematics, the learning of very complex interactions had been widely considered typical sign of over-fitting 10
3.3 Proving of the two-phase dynamics
3.3.1 Analytic solution interaction effects
As the foundation of proving the dynamics of the two phases, let us first derive the analytic solution to interaction effects specific time point during the training process. Then, Sections 3.3.2 and 3.3.3wii will use this analytic solution to further explain detailed dynamics in the second phase and the first phase, respectively. Later experiments show that our theory can well predict the true dynamics of all AND-OR interactions during the learning of real DNNs.
The proof in this subsection be divided into three steps. (1) We first rewrite DNN's inference on an input sample as a weighted sum of triggering functions of different interactions. (2) Then, we can reformulate the learning of the DNN on an input sample interactions at an intermediate time point during training can be obtained as the optimal solution to the linear regression problem under a certain level of parameter noises.
linear regression problem. (3) Thus, the
Step 1: Rewriting a DNN's inference on an input sample as a weighted sum of triggering functions of different interactions. For simplicity, let us only focus on the dynamics of AND interactions, because OR interactions can also be represented as a specific kind of AND interactions (see Appendix E for details). In this way, without loss of generality, let just analyze the learning of AND interactions w.r.f. (z)) = o(zs) + Easscy (S) az), and simplify the notation as v(x) v(ar)) + EeSseN [(5]zz) in the following proof. Our conclusions also be extended to OR interactions, as mentioned above.
Given a DNN, follow 226 22 to rewrite the inference function of the network v(x). This is inspired by the universal matching property of interactions in Theorem 2 i.e., given any arbitrarily masked input sample ds w.E.t. a random subset S C N, the network output can always be represented as a linear sum of different interaction effects v(x = Øs) = ETsss [[']a = Ø). In this way, the
following equation rewrites the inference function of the DNN 11x: is) the weighted sum of
triggering functions of interactions (see Appendix F2 for proof).
YSA N, v(x=ts) = fx==aa) subject to f(x) del E WT Jr()),
(6)
Unlike the traditional definition of the over over-fittingggeneraae fittingg/geneaaizzation power on the entire model over the entire dataset, the interaction first enables us to explicitly identify detailed over fitted/generalizable inference patterns (interactions) on specific sample.

---

where the interaction triggering function (x)x) is real-valued approximation of the binary indicator
function ((gs triggers the AND relation 2) in Eq. B) and returns the triggering value of the interaction
pattern T. In particular, we set wp v( mp), Jn(æ) = 1. (r(2) is computed as a sum of
compositional terms in the Taylor expansion of v(x)).
0 1m+- +
Jr(x)= Σ
II (a: bc)* /WT,
(7)
I.= mEQT
n.l Oz
m= EET
where the scalar weight wy should be computed as wr = 1[ =) to satisfy the equality in Eq. (6)
and Qr = {m...... mT]"" Vi E T, n, E NN; $ T, n, 0}. See Appendix F.2 for proof.
Understanding (x) and wr. Let us consider a masked sample as in which input variables in N \ S are masked. If T S S, which means all input variables in are not masked in æş, then Jr((s) = 1, indicating the interaction pattern is triggered; otherwise, Jr(ăs) = 0. indicating the interaction pattern is not triggered. wr is a scalar weight. Particularly, let 1 (T) denote the interaction extracted from the function f(x) = ΣTeN (r)r) then we have Ty (T
wrr
Step 2: Based on Eq. (6), the learning of the DNN on an input sample can be reformulated as learning the scalar weight Wr for each interaction triggering function (x), under linear regression setting. We can roughly consider the learning problem as a linear regression to a set of potentially true interactions, because it has been discovered by [21 4 that different DNNs for the same task usually encode similar sets of interactions. Therefore, the learning of DNN can be considered as training model to fit a set of pre-defined interactions. In spite of the above simplifying settings, subsequent experiments in Figure f still verify that our theoretical results can well predict the learning dynamics of interactions in real DNNs.
Specifically, let the DNN be trained on a set of samples D = {(x, y)). According to The- orem 2 given each training sample H, output scores of the finally converged DNN all 2 randomly masked samples (æs : S S N can be written in the form of yss def y(æs) = v(xa)+
which is determined by parameters EBSTeN 1 (as triggers interaction T)- wi v( + Eostes wi, "i,
{wi T N {wi: T S N} can be taken as set of true interactions that the DNN needs to learn. Therefore, the learning of the converged interactions on the training sample x can be represented as the regression towards the converged function y)a))) on all masked samples ((as, ys) S C N).
L(w) = EEsN((us - w JJ {2
(8)
where we simplify the notation as follows. w = vec(fur T TENN) E R²" denotes the weight vector of 2n different interactions, and ((xs) def vec(fJr( T TC Rd" denotes the vector of triggering values of 2" different interactions (T C N} on the masked sample Øs..
Step 3: Directly optimizing Eq. ( gives the interactions of the finally converged DNN wr t wi, but how do we estimate the interactions in an intermediate time point during the training process? To this end, we assume that the training process of the DNN is subject to parameter noises (see Lemma TD. In fact, this assumption is common. Before training, randomly initialized parameters in the DNN are pure noises without clear meanings. In this way, the DNN's training process can be viewed as a process of gradually reducing the noise on its parameters. This is also supported by the lottery ticket hypothesis [10], i.e., the learning process actually penalizes most noisy parameters and learns a very small number of meaningful parameters. Therefore, as training proceeds, the noise on the network parameters can be considered gradually diminish.
Lemma 1 (Noisy triggering function, proven in Appendix F33) the inference score of the DNN contains unlearnable noise, iee,, VS N, ((zs)) v(xs) + Aus, Aus -N(0, then the interaction between input variables w.E.t. 0 a T C N, extracted from inference scores {ū(xs)} can be written as i(T[=) = [[T(=) + Arr, where A denotes the noise in the interaction caused by the noise in the output Aes, and we have E[A[r] = 0 and Var [ar] = 2l In this way, given input sample ă, we can consider the scalar weight wr = [[T = i), and consider the interaction
triggering function Jr = Jr(x) + ET, where Jr (x()) is defined in Eq. 77 eT = ATT/wT represents the noise term on the triggering function. We have Ejer] 0 and Var (er] x TI w.r.t. noises.
Note that in the converged output ys. the true interactions {wi T C N actually mean interactions extracted from the finally converged DNN, which probably contain over over-fitted interaction patterns. Lee., {wy '' C N) is not the ideal representation for the task.
7

---

Therefore, the learned interactions under umavoidable parameter noises can be represented as mini- mizing the following loss, where we vectorize the noise e = veo(fer: _ E)) for simplicity.
[(w)= E.EsccNlys- w [(=s())) E.Escn w (J)(s + +e))
(9)
Remark. The minimizer to Eq. (9) does not represent the end of training, but represents the intermediate state of interactions after a certain epoch in the training process. We formulate the training process as process of gradually reducing the noise the DNN's parameters, and the minimizer i to Eq. (9) represents the optimal interaction state when the training is subject to certain parameter noises. We will show later that the minimizer i computed under different noise levels can accurately predict the dynamics of interactions during the training process (see Figures and
and 8
Assumption 1. To simplify the proof, we assume that different noise terms ET on the triggering function are independent, and uniformly set the variance as A T C N, Var jer] = 2?
Assumption Tis made according two findings in Lemma T (1) the interaction triggering function (r(x)) is real-valued subject to the noise on the DNN's parameters, (2) the variance of the interaction triggering function (x) increases exponentially along with the order [T]. More importantly, the assumed exponential increase of the variance in the above finding (2) has been widely observed in various DNNs trained for different tasks in previous experiments 126 (2].
Theorem 3 (Proven in Appendix F.4.. Let ib mrg L(w) denote the optimal solution to the minimization of the loss function L(w). Then, we have
w = (J + 2" diagg()) JJ (JTJ diag())) Jw" " -M
(10)
E 22" is matrix to represent the triggering values 2 interactions (w.rl. 2n columns) on 2n masked samples (W.r.. 2n rows). æs, "'2'''' D2nn
where J = (J(xs)) ), (xss),,.. ... )] )1T "( (z
enumerate all masked samples. y def (,(=,))) ... ( Sqe )1 E RR² enumerates the finally- converged outputs on 2" masked samples. e de vec([Var(er] T NJ) = vec((2)T)2 : T (TNN) N))
R²² denotes the vector of variances of the triggering values of interactions. The matrix M is defined as M del (JJ J +""dia((c)) J, and w veo( : C N3).
In this way, Theorem provides an analytic solution to the minimization of [(w) under parameter noises. Experiments in Figure f will show that the learning dynamics of interactions derived from our simplifying assumption can still predict the real distribution of interactions over different orders.
3.3.2 Explaining the dynamics in the second phase
Based the above analytic solution, this subsection aims prove that in the second phase, the DNN first encodes interactions of low orders and then gradually encodes interactions of higher orders.
The second phase can be viewed as process of gradually reducing the noise level 0². The analytic solution v in Theorem 3 under different noise levels o² enables us to analyze the dynamics of interactions during the second phase. This is because the noise on the network parameters can be considered to gradually diminish during the training process, as we assume in Section [ Then accordingly, the noise level 2² of the noise term GT on the interaction triggering function also gradually diminishes during training. At the start of the second phase, the noise level x² is large, and the interaction triggering function Jr(m) is dominated by the noise term éT. Later, as training proceeds in the second phase, the noise level x² gradually decreases, making less effect on the interaction triggering function.
The change of the analytic solution v along with the decreasing noises 0² explains the dynamics in the second phase. We prove that as o² decreases, the ratio low-order interaction strength to high-order interaction strength in the analytic solution i decreases. This means that the DNN gradually learns higher-ordde interactions in the second phase, which can be verified by our observation in Figure 2 The detailed results are derived follows.
Lemma 2 (Proven in Appendix F.5). The compositional term (x)) in the Taylor expansion in Eq. 7 always has fixed values on 2n masked samples (æs S C N), Lee. VS C N. Jr(as) 1(T C S). means that the matrix J = [J J. ((xs)) )..s) _ ) E (0, [0,1)3"xx* in Eq. 110 is fixed
binary matrix, no matter how we change the DNN v(-) or the input sample x.
8

---

k=2
x00,
k=3
10
12
14
k-n-2
k=n-1
Figure 3:
Monotonic increase of (k) along with d² mentioned in Proposition We show the curves
of (() when we set different numbers of input variables n and different orders k: 1,
Earty 2nd phase
Intermediate time in the 2nd phase
Late the 2nd phase
Real (99)
Distr. (49
Distr. (9)
Theo. Distr. (e)
(
(P)
AleoNet
CUB
2
order
V0G-11
32
order Order
order k
order k
order A
00
onder &
BEXT BERT-Meslum
04
5ST22
15
Figure 4: Comparison between the theoretical distribution of interaction strength ((k) and the
real distribution of interaction strength ( in the second phase. Please see Appendix J.3 for the comparison on the other six DNNs trained for 3D point cloud/image/senimmntt classification.
Theorem 4 (Proven in Appendix [..). According Theorem 3 we can write the analytic solution of the interaction effect uT w.r.t. subset T as ur m.."", where vn E R1X2" denotes row vector of the matrix M [MT,, 1it, ... riTrg= ]7, indexed by T. Combining with Lemma 2 for any two subsets T,T" 1 C N of the same order, i.e., [2] [1"|, we have || |
Ila is greater than I and decreases monotonically as o² decreases throughout training. The norm || 2 is only determined by ni, o², and the order (T), but is agnostic to finall-converged interactions (wi : N).
Proposition 1. For any two subsets T,T NN with [T| < (T'), || lla/ aaa//rrrrlll
Proposition I shows monotonic decrease of || | mr l|a along with the decrease of o². The physical meaning of | ll can be understood as follows. According to w w' |mrl]l reflects the strength of the DNN encoding the interaction T. In this way, | measures the relative strength of encoding a low-order interaction w.z.f that of encoding high- order interaction T
Conclusions from Theorem and Proposition 7 Because the second phase is viewed as a process of gradually reducing the noise level o², Theorem 4 and Proposition] I explain why the DNN mainly encodes low-order interactions and suppresses high-order interactions at the start of the second phase (when o² is large). They also explain why the DNN learns interactions of increasing orders during the second phase (when gradually decreases).
Experimental verification Proposition] 1 We measured the relative strength (() def | / subject to [T| = l and [T'| = l + 1, for A: = 1.... n 1, under different values a². Figure shows that when o² decreased, (*) monotonically decreased for all orders = 1, n 1, which verified the proposition. The experiment was conducted using different numbers of input variables
Theorem (Proven in Appendix
F.7
When o = 0, i satisfies 4 o T C N, uo = -
Theorem 3 shows a special case when there no noise on the network parameters. Then, the DNN learns the finally converged interactions {wi T C N). Note that the finally converged DNN probably encodes some interactions of high orders, which correspond to over-fitted patterns.
Experiments on real datasets. We conducted experiments to examine whether our theory could predict the real dynamics of interaction strength of different orders when we trained DNNs in practice. We trained AlexNet and VGG on the MNIST dataset, the CIFAR-10 dataset, the CUB-200-201

---

dataset, and the Tiny-ImageNet dataset, trained BERT-Tiny and BERT-Medium on the SST-2 dataset, and trained DGCNN on the ShapeNet dataset. Then, we computed the real distribution of interaction strength over different orders on each DNN, and tracked the change of the distribution throughout the training process. As mentioned in Section 3.2 the real interaction strength of each k-th order was T(S a m)]l Z
quantified as 1 Ez (S.. S: =
Accordingly, we defined the metrie ((
E. S.jsss م212 Site | Zineo in the same way of /eal measure the theoretical distribution of the interaction strength, where Zihoo E, g. s: 2 Then [s|]] Thoo 0.03 |iihoo (a) :ba
and (2)) def Σs SsCN lig. To compute the theoretical solution w MM" in Eq. (10 given input sample x, we used the set of salient interactions f = (S S N: |r(S]==) 2 +}) extracted from the finally converged DNN to construct the set of true interactions w".
Figure shows that the theoretical distribution T could well match the real distribution 7(h) at different training epochs. Particularly, we used sequence of theoretical distributions of L with decreasing o² values to match the real distribution of ((t)) at different epochs. The o² value was determined to achieve the best match between 7 and 7(k)
3.3.3 Explaining the dynamics in the first phase
Because the spindle-shaped distribution of interaction strength in a randomly initialized DNN has already been proven by [41], in this subsection, let us further explain the DNN's dynamics in the first phase based on Eq. (9). As previously shown in Figure (2] in the first phase, the DNN removes initial interactions of medium and high orders, and mainly encodes low-order interactions.
Therefore, the first phase is explained as the process of removing chaotic initial interactions and converging to the optimal solution to Eq. (9) under large parameter noise (i.e., large σ²). In sum, the first phase is a process of pushing initial random interactions to the optimal solution, while the second phase corresponds to the change of the optimal solution as o² gradually decreases.
4 Conclusion and discussion
In this study, we have proven the two-phase dynamics of a DNN learning interactions of different orders. Specifically, we have followed (26] [22] reformulate the learning of interactions as linear regression problem on a set of interaction triggering functions. In this way, we have successfully derived an analytic solution to interaction effects when the DNN was learned with unavoidable parameter noises. This analytic solution has successfully predicted a DNN's two-phase dynamics of learning interactions in real experiments. Considering a series of recent theoretical guarantees of taking interactions as faithful primitive inference patterns encoded by the DNN [44] 27], our study has first mathematically explained why and how the learning process gradually shifts attention from generalizable (low-order) inference patterns to probably over-fitted (high-order) inference patterns.
Practical implications. A theoretical understanding of the two-phase dynamics of interactions offers new perspective to monitor the overlitting level of the DNN on different training samples throughout training. The two-phase dynamics enables us to evaluate the overfitting level of each specific sample, making overfitting no longer problem w.E.. the entire dataset. We track the change of the interaction complexity for each training sample, and take the time point when high-order interactions increase as a sign of overfitting. In this way, the two-phase dynamics of interactions may help people remove overfitted samples from training and guide the early stopping on few "hard samples."
Acknowledgements. This work is partially supported by the National Science and Technology Major Project (2021 1 1160), the National Nature Science Foundation of China (92370115, 62276165). This work is also partially supported by Huawei Technologies Inc.
In experiments, the real distribution of interaction strength real was computed using both AND and OR interactions. Because the OR interaction was special AND interaction and had similar dynamics. this experiment actually tested the fidelity of our theory to explain the dynamics of all interactions. Nevertheless. Appendix J.4 also reports the fitness of the theoretical distribution ((6) and real distribution of AND interactions.
(k)
10

---

References
[1] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-eeaaaan Bianchi, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[2] David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissec- tion: Quantifying interpretability of deep visual representations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
[3] Zhengping Che, Sanjay Purushotham, Robinder Khemani, and Yan Liu. Interpretable deep models for icu outcome prediction. AMIA annual symposium proceedings, volume 2016, page 371. American Medical Informatics Association, 2016.
[4] Lu Chen, Siyu Lou, Benhao Huang, and Quanshi Zhang. Defining and extracting generalizable interaction primitives from DNNs. In The Twelfth International Conference on Learning Representations, 2024.
[5] Xu Cheng, Chuntung Chu, Yi Zheng, Jie Ren, and Quanshi Zhang. A Game- Theoreic Taxon- omy of Visual Concepts DNNs. arXiv preprint arXiv:2 106. 10938, 2021.
[6] Xu Cheng, Xin Wang, Haotian Xue, Zhengyang Liang, and Quanshi Zhang. Hypothesis for the Aesthetic Appreciation in Neural Networks. arXiv preprint 3rXhv::2188.02645: 2021.
[7] Huiqi Deng, Qihan Ren, Xu Chen, Hao Zhang, Jie Ren, and Quanshi Zhang. Discovering and Explaining the Representation Bottleneck of DNNs. ICLR, 2021.
[8] Huiqi Deng, Na Zou, Mengnan Du, Weifu Chen, Guocan Feng, Ziwei Yang. Zheyang Li, and Quanshi Zhang. Unifying Fourteen Post-hoc Attribution Methods with Taylor Interactions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
[9] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
[10] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
[1I] Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into soft decision tree. arXiv preprint arXiv:1711.09780 2017.
[12] Marzyeh Ghassemi, Luke Dakden-Raynes and Andrew L Beam. The false hope of current approaches explainable artificial intelligence in health care. The Lancet Digital Health, ((11):e745-e750 2021.
[13] Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of game theory, 28(4):547-565, 1999.
[14] John C. Harsanyi. A simplified bargaining model for the n-person cooperative game. Interna- tional Economic Review, 4(2):194-220, 1963.
[15] Been Kim, Martin Wattenberg. Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, and Rory sayres. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2668 2676. PMLR, 10-15 Jul 2018.
[16) Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
11

---

[17] Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in Neural Information Processing Systems, volume 25, pages 1097-1105, 2012.
[18] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
[20] Mingjie Li and Quanshi Zhang. Defining and Quantifying AND-OR Interactions for Faithful and Concise Explanation of DNNs. arXiv preprint arXiv:2304. 13312, 2023.
[21] Mingjie Li and Quanshi Zhang. Does a Neural Network Really Encode Symbolic Concepts? International Conference on Machine Learning. 2023.
[22] 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. In seirth- Conference on Neural Information Processing Systems, 2023.
[23] Jie Ren, Mingjie Li, Qirui Chen, Huiqi Deng, and Quanshi Zhang. Defining and Quantifying the Emergence of Sparse Concepts in DNNs. In The IEEE/CVF Computer Vision and Pattern Recognition Conference, 2023.
[24] Jie Ren, Die Zhang, Yisen Wang, Lu Chen, Zhanpeng Zhou, Yiting Chen, Xu Cheng. Xin Wang, Meng Zhou, Jie Shi, and Quanshi Zhang. Towards a Unified Cheerrhhe View of Adversarial Perturbations and Robustness. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 3797-38 10. Curran Associates, Inc., 2021.
[25] Jie Ren, Zhanpeng Zhou, Qirui Chen, and Quanshi Zhang. Can We Faithfully Represent Absence States to Compute Shapley Values on a DNN? In International Conference on Learning Representations, 2023.
[26] Qihan Ren, Huiqi Deng, Yunuo Chen, Siyu Lou, and Quanshi Zhang. Bayesian Neural Networks Tend to Ignore Complex and Sensitive Concepts. International Conference on Machine Learning, 2023.
[27] Qihan Ren, Jiayang Gao, Wen Shen, and Quanshi Zhang. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. In The Twelfth International Conference on Learning Representations, 2024.
[28] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206-215, 2019.
[29]
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
[30] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. International Conference on Learning Representations, 2014.
[31] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2014.
[32] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing, pages 1631-1642, 2013.
[33] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pages 9259-9268. PMLR, 2020.
[34] Sarah Tan, Giles Hooker, Paul Koch, Albert Gordo, and Rich Caruana. Considerations when learning additive explanations for box models. arXiv preprint 10X1v:1801008600, 2018.
12

---

[35] Joel Vaughan. Agus Sudjianto, Erind Brahimi, Jie Chen, and Vijayan N Nair. Explainable neural networks based on additive index models. arXiv preprint 1806. 2018.
[36] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The Caltech- UCSD Birds-200-2001 / Dataset. 2011.
[37] Xin Wang, Jie Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang, and Quanshi Zhang. A Unitied Approach to Interpreting and Boosting Adversarial Transferability. In International Conference on Learning Representations, 2021.
[38] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph enn for learning on point clouds. ACM Trans. Graph., 38(5), 2019.
[39] Li Yi, Vladimir G Kim, Duygu Ceylan, I-Chao Shen, Mengyan Yan, Hao Su, Cewu Lu, Qixing Huang, Alla Sheffer, and Leonidas Guibas. A scalable active framework for region annotation in 3d shape collections. ACM Transactions Graphics (ToG), 35(6):1-12, 2016.
[40] Jason Yosinski, Jeff Clune, Anh Nguyen, Thomas Fuchs, and Hod Lipson. Understanding neural networks through deep visualization. arXiv preprint arxiv::506.055777 2015.
[41] Junpeng Zhang, Qing Li, Liang Lin, and Quanshi Zhang. Two-phase dynamics of inter- actions explains the starting point of a dnn learning over-fitted features. arXiv preprint arXiv:2405.102622 10262v1. 2024.
[42] 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 arXiv:2207. 1694, 2022.
[43] Huilin Zhou, Huijie Tang, Mingjee Li, Hao Zhang, Zhenyu Liu, and Quanshi Zhang. Explaining how a neural network play the go game and people learn. arXiv preprint 1r.00:2310.09838 2023.
[44] 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. In Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024. AAAI Press, 2024.
13

---

A Properties of the AND interaction
The Harsanyi interaction [4] (i.e., the AND interaction in this paper) was a standard metric to measure the AND relationship between input variables encoded by the network. In this section, we present several desirable properties/axioms that the Harsanyi AND interaction (S)(e) satisfies. These properties further demonstrate the faithfulness of using Harsanyi AND interaction to explain the inference score of a DNN.
(1) Efficiency axiom (proven by [4]. The output score of model can be decomposed into interaction effects of different patterns, i.e. (<)) Escv (S(we)
(2) Linearity axiom. If merge output scores of two models i and U2 as the output of model v, i.e. VS S N, v( = Un ( + U2 (2 then their interaction effects Mh (S|z)) and 1 (S[z) can also be merged as VS S N. [m
I (S] (S]x).
(3) Dummy axiom. If a variable i E N is dummy variable, i.e. VS S N (1) (()s0))))) v(xs)+ ((z then it has no interaction with other variables, VO o E N \ (0). (())a) O.
(4) Symmetry axiom. If input variables i,j E N cooperate with other variables in the same way. YS _ \ {i, (ll.)),,(ssstti s()))())) = s(sst))) then they have same interaction effects with other variables. VS Ç N [i.j], (S U [z) [S U ()).
(5) Anonymity axiom. For any permutations и on N, we have VS (ia = Lndd (TS))), where S (i( E 5}, and the new model mv is defined by (TT)( = v(zg). This indicates that interaction effects not changed by permutation.
(6) Recursive axiom. The interaction effects can be computed recursively. For i E N and $ S N (1). the interaction effect of the pattern U (f) is equal to the interaction effect of S with the presence of minus the interaction effect of S with the absence of i, i.e. VS C ( (S U [i)|a=) (S) x. is always present) Tana (S] (=). Tand (Sm(S)) is always present) denotes the interaction
effect when the variable i is always present as a constant context, i.e. (S(e, i is always present)
E (-))((1))3--1)) v(zLu(s))
(7) Interaction distribution axiom. This axiom characterizes how interactions are distributed for "interaction functions" 33 An interaction function ur parameterized by a subset of variables T is otherwise, vr 0. The function models pure interaction among the variables in T, because only if all variables in are present, the output value will be increased by The interactions encoded in the function ey satisfies Lnnd (T) c, and
defined as follows. VS C N, T' S S, (Tes)
VS * T, (S]m)) = O.
B Common conditions for sparse interactions
Ren et al. [27 have formulated three mathematical conditions for the sparsity of AND interactions, as follows.
Condition 1. The DNN does not encode interactions higher than the M-th order: V E (S N
[S] 2 M + 1), Ionr(S
Condition 1 implies that the DNN does not encode extremely high-order interactions. This is because extremely high-order interactions usually represent very complex and over-fitted patterns, which are unnecessary and unlikely to be learned by the DNN in real applications.
Condition 2.
Let consider the average network output (b() de Essss(((ss) v(wa)] over all masked samples Øs with ls unmasked inpul variables. This average network outpui monotonically increases when l increases:
S k, we have ū(k') < ((K).
Condition 2 implies that a well-trained DNN is likely to have higher classification confidence for input samples that are less masked.
Condition Given the average network output ((()) of samples with i unmasked input variables, there is polynomial lower bound for the average network output of samples with k'(k' < k) unmasked inpul variables: 4 k k, ((k)= > ( ((,) where
0 is positive constant.
Condition 3 implies that the classification confidence of the DNN does not significantly degrade on masked input samples. The classification/dlttttion of masked/occluded samples is common in real
14

---

scenarios. In this way. a well-trained DNN usually learns to classify a masked input sample based on local information (which can be extracted from unmasked parts of the imput) and thus should not yield significantly low confidence score on masked samples.
C Details of optimizing {tr} to extract the sparsest AND-OR interactions
A method is proposed 120 4 to simultancously extract AND interactions Land (S| (5)z) and OR interac- tions [5r(S]z)) ([)= from the network output. Given a masked sample æT. [20] proposed to learn a decom- position u( Vund +
towards the sparsest interactions. The component Vand (2r) was explained by AND interactions, and the component the (xr) was explained by OR interactions. Specif- ically, they decomposed u(xr)) into (2r) 0.5 ((r)) +or and Vand (2:) 0.5 v(zr) Yr. where f?r T _ N} is a set of learnable variables that determine the decomposition. In this way, the AND interactions and OR interactions can be computed according to Eq. (2). i.e., Land (S]x) (TCs((1))S))1 Vana( and Lor [S(x))
( Vor ((N
The parameters }rr were Iearned by minimizing the following LASSO-like loss to obtain sparse interactions:
min 1 SCN
(11)
Removing small noises. A small noise ós in the network output may significantly affect the extracted
interactions, especially for high-order interactions. Thus, 20 proposed to learn to remove a small noise term 8ş from the computation of AND-OR interactions. Specifically, the decomposition was rewritten as Vana( = (.5()( 5r) + "T and Unr (xr) = (x - Ôr) + 7T. Thus, the parameters {ỘT), ). and (vr) are simultaneously learned by minimizing the loss function in Eq. (I1). The values of } were constrained in [-C, <)
where ( = 0.02 [u((r) - v((ra))-
D Where does the coefficient (-1) 12 in Eq. (2) come from?
In fact, it proven in and [23] that the coefficient (-1)181-127) in Eq. (2) is the unique coefficient to ensure that the interaction satisfies the universal matching property. Recall that the universal matching property means that no matter how we randomly mask an input sample æ, the network output on the masked sample æs can always be accurately mimicked by the sum of interaction effects within S. An extension of this property for AND-OR interactions also mentioned in Theorem
E OR interactions can be considered a special kind of AND interactions
The OR interaction can be considered a specific kind of AND interaction, when we flip the masked state and presence (unmasked) state of each input variable.
Given an input sample x E IR,, let xT denote the masked sample obtained by masking input variables in N T. while leaving variables in T unchanged. Specifically, the baseline values b E IR" are used to mask the input variables, which represent the masked states of the input variables. The definition of ar is given as follows.
Fi. iED bi. i T
(ΦT);
(12)
Based on the above definition, the AND interaction is computed as [Sna(()ar))
Ercs(-1)181-m1), Uand (IT), while the OR interaction is computed as Iar (S(2:)
-Ergs(-1) vor (œ To simplify the analysis, let us assume Uaad(.) = (.)(.) = 0.5v(-).
Then, let us consider masked sample ãτ, where flip the masked state and presence (unmasked) state of each input variable. In this way, का is defined as follows.
NEN T
(ØT)
(13)
by
T
15

---

Then, we compute Therefore, the OR interaction (S)(S( in Eq. interaction (S) as follows.
2 in main paper can be represented as an AND
(S(())
(14)
TCS
Σ (-11)151-171u TCS
(15)
Lnn (S|
(16)
In this way, the proof of the sparsity of AND interactions in 27 can also extend to OR interactions. Furthermore, we can simplify our analysis of the DNN's learning interactions by only focusing on AND interactions.
F Proof of theorems
F.1 Proof of Theorem
Proof. (1) Universal matching theorem of AND interactions.
We will prove that output component (an on all 2" masked samples {æs : S N) could be universally explained by the all interactions in S N, i.e. 4A * S C N, (an)
Exrres ana a=) + u(xr)) In particular, we define Cand ( = v((r)) (Lee we attribute output on an empty sample to AND interactions).
in 2 To compute the sum of AND interactions Eoytes land (T]xx) 2 20ycss Ex.r((11) -1-11 vand (z).. we first exchange the order of summation of the set L C T S and the set T 2 L. That is, we compute all linear combinations of all sets T containing I. with respect to the model outputs Pand(22 2) given set of imput variables L, i.e., ETucrcs((1)) 1 Vnnd ( (ln all summations over the set L C S.
Specifically, the AND interaction defined and (T(x)
-1-11
In this way, we can compute them separately for different cases L C C S. In the following, we consider the cases (1) I. S T, and (2) T. C T S T. S, respectively.
(1) When L 5 = T, the linear combination all subsets containing L with respect to the model output Vnnd (z). is (-1)1s) (s -1S) ( = Unnd (.)..
(2) When L C T C S, L + S, the linear combination of all subsets T containing L with respect to the model output Vand( is Ericrrs (-11))s(11)))))00) (1) (ada( For all sets T S S 7 T., let us consider the linear combinations of all sets T with number [T'] for the model output Vand (
respectively. Let m := |T| LZ, (0 m | L)). then there are total of C..
|s|-IZ| combinations
of all sets 7 of order [T). Thus, given L, accumulating the model outputs Uamd (L) corresponding
[5) 15|-|74
all T 2 L, then 2
Uand vand(
11 0.
m=0
Please the complete derivation of the following formula.
Eesres (Tna(T
Eesres Eisa (-1) Vand (2
Eiss Em.crrss (-1) -11) vand(( Vand (xO)
(17)
18 151 |.]
= (a0d) -' Vand(a
- |zl (1- (-1)m
- Vana(
m=0
L=8
-aand (xS) - Uund (xig)
Vand (an)( - v((z))
16

---

Thus, we have 4D # S N, (as) = Eeeres Lnnd (T|x) + v(zg).
(2) Universal matching theorem of OR interactions.
According to the definition of OR interactions, we will derive that AS S N, (x = Erarszz (S) where we define (ar( 0 (recall that in Step (1), attribute the out- put on empty input to AND interactions).
Specifically, the OR interaction is defined as Ioe (T) = E (ZN)))) in 2
Similar to the above derivation of the universal matching theorem of AND interactions, to compute -1) (L we first exchange the order of summation of the set L C N and the set T: T + 0. That is, we compute all linear combinations of all sets T containing L with respect to the model outputs Vor N L) given a set of input variables I,, i.e., (-1))) (x compute all summations over the set L N.
the sum of OR interactions Er:rnsy (Tr(Taa)) a:) = EET-rsse
(-1)
Then, we
In this way, we can compute them separately for different cases of L C C N,NS + 0. In the following, we consider the cases (1) L N S. (2) N. (3) LNS # 0, N. and (4) LnS 0, L + N \ S, respectively.
(1) When L = N \ S. the linear combination of all subsets T containing with respect to the model output Uor (0 (z) is
-1 (-1) Uve (2:)) For all sets T T 2 L,T n S * (then T * N S.T * L), let consider the lin- ear combinations of all sets T with number (T) for the model output Vor (xs), respectively. Let
(3) v
[T'] = [T] [4) (1 - |T'| < [S), then there are a total of c/T' combinations of all sets T" of order [T') Thus, given I. accumulating the model outputs Var (ar)) corresponding all T 2 T,, then
Ex L uo (E) (xs)
Σ |8|
I- 0/3/1 1 (-1)1T") (xs)
(2) When L == N (then = N). the linear combination of all subsets T containing L with respect to the model output Vor N is ET.mssuTTa (-1)) (-1 (x (-1)1 oor (xrp) Vor (xx)
(3) When L E + L + N. the linear combination of all subsets T containing L with respect to the model output "o(( is Cxarsssp.rrp(-11)771--o.aa. (Z)))) For all sets T : T 2 L n S + 0, let us consider the linear combinations of all sets T with num- ber [T] for the model output Vor (xs), respectively. Let us split [T] L| into [T'] and [T"),
i.e. T - [ IT' + [T") where T' = {iile E T. & L. E N NYS), T" {ili TTi L, i E S} (then 0 S [T" S S - (Sn and !T") + [T" + |L] = [T). In this way, there are a total of 181-) combinations of all sets 7 of order [T"). Thus, given L, accumulating the model
G/T"1
outputs (xNNE) corresponding to all T 2 L, then -= ((m =
Var ( ETeNAS Σ |S|- SnL] T
( - T" +1T" = 0.
=0
(4) When Lns N S. the linear combination of all subsets T containing L with respect to the model output Vor (x) is ΣT (-1)) (-1))71-144 (g ( Similarly, let us split [T] L into [T'l and [T"), i...|..T [T' L = T T where T" = {ili E T, & L,i N \ S}. 1"d {ili E TTTE S) (then 0 < T SS) and [T'| + [ + L [T). In this way, there
total of IT combinations of all sets T of order [ Thus, given L, accumulating the model
[s]
outputs Vor Vor(x (L) corresponding to all T 2 L, then (-1m) vor ( =
Vor (ZN)L) ET
Σ
|81
12" ( (-1) (-1)TT+H = O. (
T
17

---

Please see the complete derivation of the following formula.
E Emiasoo [x(T[x)=
E ETmrIsAa
(- Borl (1)
=-Ensx ugN EnTTSSHUTE (-1) 21 (20N1))
18
Σ
[8]
(-1))01
(x))
Carl
(2pp)
|-1
L=Nis
I=N
18 SULI
) eir (2E
E
Σ
Σ
151- (- 1) (-1- 11)
Ln8
T'CNISIL
IT"100
Σ
[s]
(-1)
vor (ZN2)))
LNS-ALANIS
12 =
= (-1) vxr(2)) - Var var()))
E LN870.L#N
Uar (()
T'NNSS
E
Σ
L
(xss)) Var (20g)
(xs))
(18)
(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(xs) = (x)) + Vor (xx) = v(x.)) + EBSres (T)
ETeros Joe (T)x), thus, we obtain the universal matching theorem of AND-OR interactions.
F2 Proof of Eq. (6) and Eq. 7
Before we give the derivation of Eq. (6) and Eq. 77. we first prove the following lemma.
Lemma 3. The effect [(T of an AND interaction w.r.f subset T on sample be rewritten as
8 +....................... kn
T(T)x)) Σ tEQT II.
(xs - bz)
(19)
T..
Ox ... Fx
GE
where QT {[TT...,, Vie T. NeTTmNNNVVVii 0}.
Note that a similar proof was first introduced in 26
Proof. Let denote the function on the right of Eq. 19 by (TTwx), i.e., for S 0.
m +rit Kay
()) def E
II JET
(x. b.)
(20)
IH my! dx
21 Ox
Actually, it has been proven in 13 and 23 that the AND interaction [(T (see definition in Eq. (2) is the unique metric satisfying the following property (an extension of the property for AND-OR interactions is mentioned in Theorem 2 i.e.
VSC N, v(zs) E T(T|=) + o(zg).
(21)
Thus, as long as we can prove that K(T(=)) also satisfies the above universal matching property, we can obtain [[T)x) KT)))).
18

---

To this end, we only need to prove K also satisfies the property in Eq. (21). Specifically, given an imput sample IR,, let us consider the Taylor expansion of the network output v(zs) of an arbitrarily masked sample æs, which is expanded æq b [b,.... 6n] I Then, have
V v(Es) Σ
Σ
II ((+s): bz)*
(22)
Oz
Or
a0 1=1
where b, denotes the baseline value to mask the input variable zi.
According to the definition of the masked sample æ,s, we have that all variables in S keep unchanged
and other variables are masked to the baseline value. That is, V i E S, (æs); = V i & S, (mss); by. Hence, we obtain Vi E S. ((xs); b,) expansion terms, only terms corresponding to degrees in the set Ps {[ Tn. I Vi
if n, > 0. Then, among all Taylor
S. क. E Ni & S, πτ₃ = 0} may not be zero (we consider the value of ((xs); - b to be always equal if n. 0). Therefore, Eq. (22 can be re-written as
0
YSCN, v(ms)
Σ REPs
(a) bz)
(23)
... Ox
Ox
IES
We find that the set Ps can be divided into multiple disjoint sets as Ps Urgs Qr. where E Nt; $ T, ग. = 0}. Then, we can further write Eq. 23 as
Qr = [|,,... _
F + +5a
ASAA N, v(xs)) = Σ Σ
II
(x: - b.)*t
I To! Ozy 7n
TCS TEQT
KET
Σ 07TES
K(T[x) v(ar)) // according to the definition of ((T)z)) in Eq. 20
(24)
The last step is obtained as follows. When T 0, Qr only has element =0,,.. ... OTT which corresponds to the term v(xg).
Thus, K(T)a:) satisfies the property in Eq. 21 and this means T(T K(T)=) =
Eneor I n. du 0m
prittstang
III b))
Then, let us continue the proof of Eq. (6) and Eq.
Proof. Given a specific sample é, let us consider the following function defined in Eq. 6 and Eq. (
f(x) ETEN wr Jr(
(25)
where the scalar weight
WT
[[Tlx x). and the function JT(x)
g-14--479 EneQr le 8z 0n.5
I (I: =a /WT-
19

---

We will then prove that AA S N. f(Øs) = v((s).
(ws))
Σ TEN
WT (xb)
(26)
0 1...... +
Σ
II ((ts):: b,) // wr cancels out
(27)
I==1 N..
0x
Dxn"
TCN TEQT
20 iET
0m + t
Σ
II ((ts) - 6,)*t
(28)
i= Ty!
Orn Tm
TgS TeQr
iE
I g S, then 3j T S, s.t. (is)) bj = 0, which makes the whole term zero
(29)
go
ΣE
(d. b))
(30)
TES TEQT IT: TT! d dx
KE
I/ when T S. we have vi E T, (ms); +;
(31)
= Σ
T(T = +) + v( // the inverse direction of Lemma we have just proven
GFTCS
(32)
= =(((s) // the inverse direction of universal matching theorem
(33)
Remark. The function (xx essentially provides a continuous implementation of Eq. 3 in the universal matching theorem (Theorem 2). The weight wT = [(T'(x Φ) is the interaction effeet w.r.. to subset 7' on the unmasked sample ă, while the function (r is a continuous extension of the indicator function 1 (&s triggers the AND relation T') (thus call Jr (x) triggering function and the value of this function triggering strength).
F.3 Proof of Lemma
Proof. Given the inference scores on masked samples (ū(xx) : S N}, the interaction between in- put variables w.r.t. T C N can be computed as [(T[=)) = (=cr(-1)))) 11)71-181 ū(xs) (the computation of AND interactions in Eq. (2)
Since we assume that VS S N, ((x) = v(xs) + Aus, Aug ~ N(0, T(T)2)) can be written as
i(T
Σ (-1) (((ss)))))
(34)
SCT
Σ (-1) (o(xs) + Aus)
(35)
SCT
(-1) v(xs)
Σ
(-1) 1I-1s Avs
(36)
SCT
SCT
[TT + ATr
(37)
where [(T = Escr (-)( vzx)) is noiseless component (not random variable), and
Aly = - Aug is the noise component on the interaction.
Since each Gaussian noise Aus A (10, ) VS C N, is independent and identically distributed, it easy to see E[ATT] = Escr( -1) us] = 0. The variance of A is computed as
Var [T] = Var Σ (-1)1 S Ars)
(38)
SCT
Var(Ause + Var( .... Var( Aus
(39)
= 21 d²
(40)
because there are total of 2T subsets for S C T.
20

---

Furthermore, according to the analytic form of interaction effect in Eq. (9 we note that the values of [(] and (x) have ratio of wr. Therefore. if we write Jr(x) Jr(x) er, then the noise term satisfies ET Alr/wT, and thus Eler] = O, Var[er] 2
E,4 Proof of Theorem
Proof. We concatenate all J (xs) (w.r.. all 2n masked samples æs. S C N) into a matrix J s ), (a=s)). J, ..... J (1 OJ E {0, 1)2"x²" to represent the triggering strength of 2 interactions on 2n masked samples We also concatenate all noise terms on all 2 masked samples cl²' to represent the noise term over J. We concatenate the output score vector y def [y(æs,) ), (ars))... y( ) R?² to represent the finally converged outputs on all 2 masked samples.
into a matrix & = [c(1) c,2),
The optimal weights v can be solved by minimizing the loss function L(w) in Eq. 9 The loss function can be rewritten as follows:
v arg min L(w)
(41)
İ () = EsEs [yss w w (J(xs) + +
(42)
= Eg
1 - (J + E)2113
(43)
2n
1
Ee [(y
(J + 8) E)m) (y- (J + E)w)]]
(44)
2
1
y
y
2y Eg [J + E) w TTE [J + E) (J + E)] w)
(45)
2d
Taking the derivative with respect to w and setting it to zero, we get:
aï.
-BB [J + + y) + 2Bg [J E) + E)w] = =0,
(46)
dw
Ee [J + E) (J + +]] w == Ee [J + E) y]
(47)
(J EelE JJ J JEE + Eg E El J y:
(48)
(JT J EelE El) J J y. // because B[E]
(49)
Notice that the sample covariance matrix 1 E converges to the true covariance matrix Cov(E),
when m 2" large. Therefore, Egg E Eg [2" (ov
2*Cov(E). Because we assume
noises on different interactions are independent, it is a diagonal matrix, denoted by Cov(E)= = diag(c), (c).
where = vec((Vare [Var(er] T C N)) = vec((2/Tlo² T NT) E 2 denotes the vector of variances of the triggering strength of 2n interactions.
Thus, we have:
(J T J + 2" diag(()) = J y.
(50)
Next, we can prove that the matrix JTJ J + 2" d'dig(( is always invertible. as follows. (1) We can prove that JT J is positive semi-tefinite, because Vu + 0, u J Ju [ 2 0. (2) We can further prove that J J is positive definite. Let us denote the eigenvalues of J J as ' Ar E R (because J is real symmetric, its eigenvalues must be real). Note that the diagonal elements of J J are all positive, so we have I[" = - J) > O. Combining the positive semi demiitefiniteness, we know that the eigenvalues of J J must be all positive, without having zero eigenvalue. It means that J is positive definite. (3) We can prove that JTJ + 2"diag (c) is positive definite. The diagonal matrix 2" diag is positive definite, because all its diagonal elements are positive. The sum of two positive definite matrices is still positive definite. (4) Since J J + 2n diag(c) is positive definite, it cannot have zero eigenvalue, and is thus invertible.
21

---

So the optimal weights can be solved as
(JTJ+ 2" diagg(() JJ y.
(51)
Next we will show that y = TT Eoyrgs wi in the main paper. According to the Lemma we have Jr(x) 1 C S). Therefore, yzzg) can be rewritten as y( ErçN (xs))) where we define w def v(zg) for simplicity of notation. Writing the sum in vector norm, we obtain y(æt) = (xs) wv. Furthermore, the whole vector y can be written as y = w.
wv. Recall that definition of y(as)) is given by y(æs) = =(
With y = T we have ii (J J + d'din(()))-13 Jw" Mw..
F5 Proof of Lemma 2
Proof. According to Eq. 77), the interaction triggering function on an arbitrarily given sample & is given by
8
Kay
Jx(x) = Σ
II
(z - 6.)" /WT -.)=
(52)
TEQT ii=1 T.. 7x7
FET
where wr I(T = 2), and Qr {[ nnl Vi T, of
Specifically, now we consider masked sample ass and we will prove that JT()))) 1(T C S). We consider the following two cases.
Case 1: T g S. Then, there exists some j T S. Since j S, according the masking rule of the sample &g, have (øs) b, 0. Since E T, we have Ny E N Therefore, ((ts), by) 0. In this way, we have
VT E QT
II ((ts); 6;) =0 0. 'ET'
(53)
Since each term in the summation equals zero, we have ( = O.
Case 2: T C S. In this case, Vi T, have i E S. Therefore, according to the masking rule, have vi E T + E + (Øs); = ftz.
According to the analytic form of (T)xz) in Eq. 19 in the proof in Appendix F2 we can derive the value WT as
g Kay
WT =
Σ
I
i==1 T,
0x ... 0xx
II XE
(#.
0z)*
(54)
rEQT
Therefore, we can derive the value of (T()) follows.
g 3a +5
Jr(ts)= = Σ n i= Tel 0z
II ((ts); - bz) /wr
(55)
dz
nEQr
iET
Emerr
1 +
Hir ((ts); - b²)
IT ne. 0u ... 8u
11 by Eq. (54)
(56)
Ererr 11 Nel On."" ......
g
IhET (Ø, - b,)%
0T + tang ETERU 11 nT. Be Ba
mher (#: - bz)
(57)
851 Enerr II= m.. Oz
Ilr (#: bz)
// because we have proven Vi E T, (#s); = 5;
(58)
=1
(59)
Combining the two cases, we can conclude that Jy =
In this way, no matter how we change the DNN v(.) or the input sample x, the matrix J
(, (mss),;" ((sss) )] E {0. 1) x2" in Eq. (10) is a always a fixed binary matrix.
22

---

F.6 Proof of Theorem 4
Proof. We prove that for any two subsets 7,7" C N of the same order, the vector my is a permuta- tion of the vector mr.
The proof consists of two steps. First, we show that there exists symmetric matrix transformation T(.) Pk- ... Pi P: Pk. where P, is permutation matrix, that maps both J J and JJJ + d") to themselves, i.e., T(JTJ JJ T(J J + 2"diag(e) JJJ (e)ag()). We will show that this transformation T(-) applies permutation the rows and columns of the same order.
Second, we show that this transformation also maps M itself, i.e., T(M) M, implying that row vectors of the same order in M are permutations each other.
From Theorem have:
(JTJ 2" diag(()) JJJJ
(60)
To simplify the notation, we denote = J and D = 2n d'))a Then, we have:
( D)M
(61)
We construct transformation T()) which permutes the rows and columns of a 2 x 2 matrix based on element selection. Let us first consider the matrix B. For the matrix D, the analysis similar because diagonal elements 2 are the same for each order. Thus, (-) maps B to itself, it also maps D to itself.
Step 1:
Given the set N = (1, 2. n). the subsets S2, S2n can be regarded as selec- tions from the power set of N, denoted as 2N Consider permutation P acting N. Under this permutation, the selections S1,S2, SSe transform correspondingly. For ex- ample, if N
(1,2,3} is mapped to
{3, 13 under the permutation P. the list 00 [1] (11.:(2 [2}, (3), (1,2), [1,3), (2, [1,2,3}] (1, is mapped to 1H}.
of subsets [8t, S2, S2 [0, [3), (2), (1), (3, (3,
.. on the matrix This permutation induces transformation P.Pk-1 P.))P.) PR-1P B == JJJ J by permuting its rows and columns.
Since the permutation acts on N and preserves the inclusion relation, the transformation T(-) is invariant, meaning T(B) B. Similarly, have T(B D) B D.
Step 2: We apply T(-) to the matrices B + D and B in Eq. (61). Since the transformation is invariant, we have:
+ DD++MM=117
(62)
Thus:
... SPA-I-..PP(E P(B+D))PP ... PA-IP,M P PAPA11 ... P(B)) ... PA-1Pk
(63)
We can easily see that if M is a solution to this equation, then T(M) Py PA-11.... P.P--...P,,PPP. P,MP, Pk-1Pk is also a solution, since pa I = 1,... k, where I is the identity matrix. In addition, because B + D is invertible (as shown in (apendixF.44) this solution is unique. Therefore:
T(M) MM
(64)
This shows that the transformation T(-) also maps M to itself.
Conclusion:
We have shown that, under the transformation T(.), the affected rows of M permutations of each other. Note that only the rows with the same order will be permuted to each other because T(-) is derived from the permutation of the power set of N, so the order of the rows is preserved.
For any two subsets T,T' T' N of the same order, we can construct a permutation of indices from T to I"' that maps mr mT. Therefore, my is permutation of myr
23

---

Output function v(.)
v(x) log
pla ply xx)
pla
Threshold r
==0.03 Em [x(x)
v
Image data: using the zero baseline on the feature map after ReLU
Baseline value b
Text data: using the [MASK] token
Point cloud data: using the cluster center of each point cluster
Table Mathematical setting of hyper-parameters for interactions.
F.7 Proof of Theorem 5
10). when there is no noise (i.e., o 0), it is obvious that (J J) JJ- Jw " which means that the optimal weights vó are the same as the true weights w.. So - N, ur = wj.
Proof. From Eq.
G Experimental details G.1 Models and datasets
We trained various DNNs on different datasets. Specifically, for image data, we trained VGG- on the MNIST dataset (Creative Commons Attribution-Saare Alike 3.0 license), VGG-11/VGG-16 on the CIFAR-15 10 dataset (MIT license), AlexNet/VGG-16 on the CUB-200-200 dataset (license unknown), and VGG-16 on the Tiny ImageNet dataset (license unknown). For natural language data, we trained BERT-Tiny and BERT-Medium on the SST-2 dataset (license unknown). For point cloud data, trained DGCNN the ShapeNet dataset (Custom (non-commerical) license).
For the 200-200-2011 dataset, we cropped the images to remove the background regions, using the bounding box provided by the dataset. These cropped images were resized to 224x and fed into the DNN. For the Tiny ImageNet dataset, due to the computational cost, we selected 50 classes from the total 200 classes at equal intervals (i.e., the 4th, 8th.... 196th, 200th classes). All these images were resized 224x 224. For the MNIST dataset, all images were resized to 32x32 for classification. To better demonstrate that the learning of higher-order interactions the second phase was closely related to overfitting, we added a small ratio of label noise to the MNIST dataset, the CIFAR-10 dataset, and the CUB-200-201 dataset to boost the significance of over-fitting of randomly selected 1% training samples in the MNIST dataset and the CIFAR-10 dataset, and randomly reset their labels. We randomly selected 5% training samples in the CUB-200-2011 dataset and randomly reset their labels.
the DNNs. Specifically,
G.2 Training settings
We trained all DNNs using the SGD optimizer with learning rate of 0.01 and momentum of 0.9. No learning rate decay was used. We trained VGG models, AlexNet models, and BERT models for 256 epochs, and trained the DGCNN model for 512 epochs. The batchsize was set to 128 for all DNNs on all datasets.
G.3 Details computing interactions
First, we provide summary of the mathematical settings of the hyper-parameter for interactions Table | including the scalar output function of the DNN v(.), the baseline value for masking, and the threshold т. These settings are uniformly applied to all DNNs. More detailed settings for different datasets can be found below.
Image data. For image data, we considered image patches as input variables to the DNN. To generate a masked sample æs, we followed [41] to mask the patch on the intermediate- layer feature map corresponding each image patch in the set N \ S. Specifically, we considered the feature map after the second ReLU layer for VGG- 1/VGG-16 16 and the feature map after the first ReLU layer for AlexNet. For the VGG models and the AlexNet model, we uniformly partitioned the feature map into 8x8 patches, randomly selected 10 patches from the central 6x6 region (i.e., we did not select patches that were on the edges), and considered each of the 10 patches as an input variable in the set N to calculate interactions. We considered each of the 10 patches as an input variable in the set N to calculate interactions. We used a zero baseline value to mask the input variables in the set N S to obtain the masked sample xg.
24

---

Natural language data. We considered the input tokens as input variables for each input sentence. Specifically, we randomly selected 10 words that are meaningful (i.e., not including stopwords. special characters, and punctuations) as input variables in the set N to calculate interactions. We used the "mask" token with the token id 103 to mask the tokens in the set N \ obtain the masked sample g-
Point cloud data. We clustered all the points into 30 clusters using K-means clustering, and randomly selected 10 clusters the input variables in the set N to calculate interactions. We used the average coordinate of the points in each cluster to mask the corresponding cluster in N S and obtained the masked sample æs.
For all DNNs and datasets, we randomly selected 50 samples from the testing set to compute interactions, and averaged the interaction strength of the k-th order on each sample to obtain (2)
G.4 Compute resources
All DNNs can be trained within 12 hours on single NVIDIA GeForce RTX 3090 GPU (with 24G GPU memory). Computing all interactions on a single input sample usually takes 35-40 seconds, which is acceptable in real applications.
H Potential limitations of the theoretical proof
In this study, we have assumed that during the training process, the noise on the parameters gradually decreased (a2 gradually became smaller). Although experiments in Figure 4 and Figure g have verified that the theoretical distribution of interaction strength can well match the real distribution by using set of decreasing o² values, it is not exactly clear how the value of o² is related to the training process. The value of x² probably does not decrease linearly along with the training epochs/iterations, which needs more precise formulations.
I More discussions about the two-phase dynamics
L.1 Does the model re-learn the initial interactions during the second phase?
Our theory does not claim that in the second phase, DNN will not re-encode interaction that is removed the first phase. Instead, Theorem Ancorrmaannd and Proposition collectivvyy indicate the possibility of DNN gradually re-encoding a few higher-order interactions in the second phase along with the decrease of the parameter noise.
The key point this question that the massive interactions in fully initialized DNN are all chaotic and meaningless patterns caused by randomly initialized network parameters. Therefore, the crux of the matter not whether the DŇN re-learns the initially removed interactions, but the fact that the DNN mainly removes chuotic and meaningless initial interactions in the first phase, and learns potential target interactions in the second phase. In this way, although a few interactions may be re-encoded later in the second phase, we do not consider this problem with the training of DNN.
1.2 About extending the theoretical analysis specific network architectures
Our current analysis is agnostic to the network architecture, and aims to explain the common two- phase dynamics of interactions that is shared by different network architectures for various tasks. Fig. and Fig. 5 demonstrate this shared two-phase dynamics.
On the other hand, although DNNs with different architectures all exhibit the two-phase dynamics of interactions, the length of the two phases and the finally converged state of the DNN are influenced by the network architecture and can slightly vary among different architectures. Eq. (TO) shows that our current formulation is to use the finally converged state of DNN to accurately predict the DNN's learning dynamics of interactions. Therefore, the learning dynamics predicted by our theory also exhibits slight differences among different DNN architectures and datasets accordingly. but it still matches well with the empirical dynamics of interactions. To this end, studying how the network architecture affects the finally converged state of DNN may be good future direction.
25

---

More experimental results
J.1 More results for the two-phase phenomenon
In this subsection, we show the two-phase dynamics of learning interactions on more DNNs and datasets. See Figure 5 and Figure details.
VGG-16
24
CLU
22
order
order 10
order
order
order
VGG-16 Tiny impheet
21
b.
12
19
order
order
order
VGG--16 CFAR--10
VSG 31 MNIST
34
order k
order
order k
order k
order
order
BERT- TTy
SST-2
Falle
order
order
order
order k
order
order
DOCNN
Shapotet
02
06
order
order
order
order k
order
order
Figure 5: The distribution of interaction strength I ( different orders k. Each shows
the change of the distribution during the training process. Experiments showed that the two-phass phenomenon widely existed on different DNNs trained various datasets.
BEXT Ttny
AGNews
(.00
order
order
BERT BERT-Medine Mediledd um AGNewss
Fraa
order
order R
order
order
order &
order
BERT Tiny
ce
MNLI
rit
c4
ca
62
order
82:
order R
order
order &
co
order k
order
DEAT-Medium
(80
14
c4
order
order &
order
order k
order k
order
Figure 6: Demonstration of the two-phase dynamics of interactions on more textual datasets.
26

---

J.2 More details for the alignment between the two phases and the lass gap
Besides the loss gap. in Figure 7 we also show the training loss and the testing loss separately. In fact, instead of considering underfitting (or learning useful features) and overfitting (or learning overfitted features) two separate processes, the DNN simultaneously learns both useful features and overfitted features during training. The learning useful features decreases the training loss and the testing loss, which alleviates underfitting. Meanwhile, the learning of overfitted features gradually increases the loss gap.
Extracting interactions from dificrent time points baringgtaingg
sinn and Sotting
pare
Time portz
Tirepsima
prire
Time point
Thme point
onder
Simulunnously
leaming peresatzele interactions and swwfiited intaractions
anter
onder
2073
Scitine
back lan
onder22
order
onder
Figure 7: Demonstration of the training loss and the testing loss (the last column) in addition the two-phase dynamics of interactions (Ist column to 6th column) and the loss gap (7th column).
J.3 More results for the experimental verification of our theory
In this subsection, we show results of using the theoretical distribution of interaction strength (k) to match the real distribution of interaction strength ykk) on more DNNs and datasets, as shown in Figure 8
27

---

Early the 2nd phase
Intermediate time in the 2nd phase
Late in the 2nd phase
Real Distr. rea
Theo. Distr. tioe
Real Distr nual
Theo. Distr. tiso
Real Distr. rai
Theo, Distr.
(0)
30
CUB
C2
order X
order X
order
orderk 14
order
order
VOG-36 Tiny lmggitt
92
order X
order
order
00
VCG-16 01AR-30
order X
onder A
onder
order
order &
64
VGa 11 MAVIST
order X
order A
order
order k
BERT TIN
SST
2
order
order it
order
00
&
DSCCN Shopetet
64
K
order X
12
order
Figure 8: Comparison between the theoretical distribution of interaction strength (k) and the real distribution interaction strength (16) the second phase on more DNNs and datasets.
J.4 Using the theoretical distribution (k) to predict the real distribution AND interactions
In this subsection, we show results of using the theoretical distribution of interaction strength (k) match the real distribution AND interactions (rather than the AND-OR interactions), as shown in Figure 9
theo to
28

---

Early the 2nd phese
Intermediate time in the 2nd phase
Late in the 2nd phase
Roal Distr. feel
Theo. Distr: liee
Real Distr. feal
Theo. Distr. fhee
Roal Distr. real
Theo. Distr. the
04
AlecNet
cUS
92
order
VSG-16 CUS
64
02
order
order
order
order
order
order It
Tiny Imgghtt
64
order
order A
VGG-11 CHIMR-30
order A
order
order
X
order At
VGa 15 CIFR 10
order X
order
order
order
order 1
order It
order X
onder A
order
order X
order X
order A:
BERT Mellium
onder
order
BERT Tny 55--2
C.F.R.
arder
onder
order k
order K:
onder
onder.l:
Stapehiet
03
order
order
order
order
onder
Figure 9: Comparison between the theoretical distribution of interaction strength distribution of interaction strength of AND interactions.
(k) theo and the real
29

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect our paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Although we have no room for a separate Limitations section the main paper, provide discussion of potential limitations in Appendix G.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
30

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide the assumptions in the main paper, and the proof for all theorems in Appendix E.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
The contribution of this paper mainly theoretical. Nevertheless, we provide the detailed experimental settings in Appendix F to reproduce the experiment results. The code will be released when the paper accepted.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
31

---

(a) If the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The code will be released when the paper is accepted. All datasets used in this paper are publicly available. Nevertheless, to enhance reproducibility, we provide the detailed experimental settings in Appendix F.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.ca cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https btatsss.cc/pbbliguuudeeee. (ooeeSubmm wttpesummmsssisPPeee Psioniolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details on dataset preprocessing can be found in Appendix F.I. Details on training settings can be found in Appendix F.2. Details on how to compute interactions can be found in Appendix F.3.
32

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
The main contribution of this study is to provide theoretical proof for the two- phase dynamics phenomenon discovered in previous studies. The experiments in this study are mainly to reproduce the two-phase dynamics phenomenon for better illustration and to verify that our theory study does not propose new methods to boost performance or discover a new phenomenon, refrain from reporting error bars for clarity.
Justification:
predict the trend of the interaction dynamics real DNNs. This
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the compute resources needed in Appendix F.4, including the type of GPU and the approximate amount of time for training DNNs and computing interactions.
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///aaapp.cccpaa/aa/ccccaaaa
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The contribution of this paper is mainly theoretical, which has yet been applied to real applications. The social impact could be little, for now.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system leams from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
34

---

Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: All models and datasets used in this paper are already publicly available.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the original paper for all datasets. The name of the license is included for each dataset in Appendix F.I, although some licenses are unknown.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwpppsawithhhooooooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
35

---

Researchers should communicate the details of the dataset/cooeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "q4ZRdTAs6j", "reviewer": "Reviewer_iitK", "summary": "The paper investigates the two-phase dynamics of interactions during training by reformulating the learning of interactions as a linear regression problem. The authors provide an analytic solution to the minimization problem and use this solution to explain the two-phase dynamics of interactions.", "questions": "* Do you think **it is possible to analyze the exact dynamics** of interactions by considering specific neural network architectures and data models? This direction may enhance the results of the paper.\n* Are there any **practical implications** of the theoretical findings?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper provides **a theoretical explanation for the two-phase dynamics of interactions**, which appears to be a novel contribution to the literature.", "weaknesses": "* **Presentation of the paper is difficult to follow**, especially for someone like me who is not familliar with the literature. It would benefit from improved clarity and readability, particularly in summarizing relevant literature and explaining the mathematical setting.\n* The paper only characterizes minimizers, which are the ending points of learning and **do not consider the exact training dynamics**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review. We will answer all your questions. **If you have new questions, please let us know as soon as possible. Thank you.**\n\n**Q1:** \"Presentation of the paper is difficult to follow ... particularly in summarizing relevant literature and explaining the mathematical setting.\"\n\nA: Thank you. We will follow your suggestions to improve the presentation as follows. \n\n$\\bullet$ First, we will revise the related work section to add a more thorough summarization of relevant literature on interactions. The theory system of interactions has been surveyed in both [27] and the related work section in this paper, which consists of more than 15 papers published in top-tier conferences/journals (T-PAMI, NeurIPS, ICML, ICLR, CVPR, etc.) since 2021. The theory system of interactions explains DNNs from different perspectives. E.g., (1) proving that the decision-making logic of a DNN on a sample can be explained by a small number of symbolic interactions [21,23,27]; (2) proving that the interactions well explain the hidden factors that determine the generalization power, robustness, and adversarial transferability of a DNN [24,37,41,45]; (3) proving that internal mechanisms of many empirical deep learning methods can be reformulated using interactions (e.g., finding that the common essence of 14 attribution methods is the reallocation of interactions [8]).\n\n$\\bullet$ Second, regarding the mathematical setting of interactions, we only need to set hyper-parameters including the scalar output function of the DNN $v(\\cdot)$, the baseline value $\\boldsymbol{b}$ for masking, and the threshold $\\tau$. Detailed settings of $v(\\cdot)$, $\\boldsymbol{b}$, and $\\tau$ have been introduced in [Line 85 and Footnote 3], [Footnote 4 and Appendix F.3], and Line 157, respectively. These settings are uniformly applied to all DNNs. Alternatively, you may also see Table 1 in the *response pdf file* for these settings. Nevertheless, we will also clarify these in the main paper.\n\n---\n\n**Q2: Does the \"characterization of minimizers\" represent the end point of learning or the intermediate state in the training dynamics?**\n\n> The paper only characterizes minimizers, which are the ending points of learning and do not consider the exact training dynamics. \n\nA: Thank you. In fact, the characterization of the minimizer (i.e., the optimal solution to Eq. (9)) **does not** represent the state of the end of learning, but represents the *intermediate state* of interactions after *a certain epoch in the training dynamics*. This is because as mentioned in Lines 239-247, we formulate the training process as a process of gradually reducing the noise on the DNN's parameters, and the minimizer $\\hat{\\boldsymbol{w}}$ to Eq. (9) represents the optimal interaction state when the training of the DNN is subject to unavoidable *parameter noises*. In this way, the minimizer $\\hat{\\boldsymbol{w}}$ computed under different noise levels accurately predicts the exact dynamics of interactions (please see Fig. 4 and Fig. 6), because the parameter noise is the key factor that controls the training dynamics in the second phase.\n\nNevertheless, we will further clarify this in Line 239-247. We hope this answer helps address your concern, and please let us know if you have new concerns.\n\n---\n\n**Q3: Ask about extending the theoretical analysis to specific network architecture.**\n\n> Do you think it is possible to analyze the exact dynamics of interactions by considering specific neural network architectures and data models? This direction may enhance the results of the paper.\n\nA: A good question. First, we would like to clarify that the analysis is agnostic to the network architecture. To be precise, a recent work [27] has shown that except for cases where an extremely poor architecture fully damages the feature representation of a DNN, architectures for most typical models (including both SOTA models and sub-optimal models ranging from the MLP, the LeNet to transformer-based LLMs) are no longer the key factor that leads to the emergence of sparse interactions. Instead, the property of stable inference on masked samples is the direct cause for the emergence of sparse interactions. Similarly, *the two-phase dynamics of interactions in this paper is shared by different network architectures for various tasks*. Please see Fig. 2 and Fig. 5 for this two-phase dynamics.\n\nOn the other hand, although DNNs with different architectures all exhibit the two-phase dynamics of interactions, the length of the two phases and the finally converged state of the DNN are also influenced by the network architecture. Eq. (10) shows that our current progress is to use the finally converged state of a DNN to accurately predict the DNN's learning dynamics of interactions. In this way, how the network architecture affects the finally converged state of a DNN is also a good future direction.\n\n---\n\n**Q4:** \"Are there any practical implications of the theoretical findings?\"\n\nA: A good question. A theoretical understanding of the two-phase dynamics of interactions provides a new perspective to monitor the overfitting level of the DNN on different training samples throughout the entire training process. Previous metric (e.g., the loss gap between the training set and testing set) only measures the overfitting level of the DNN over the entire dataset. In comparison, the discovered two-phase dynamics enable us to evaluate the overfitting level of each specific training sample, making overfitting no longer a problem w.r.t. the entire dataset. We can track the change of the interaction complexity for each training sample, and take the time point when high-order interactions increase as a sign of overfitting. In this way, the two-phase dynamics of interactions may help people remove overfitted samples from training and guide the early stopping of a few \"hard samples.\" We will clarify this in the paper.", "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": "kEzgyMJ2b7", "reviewer": "Reviewer_bep2", "summary": "This study investigates the two-phase dynamics of DNNs learning interactions during training, demonstrating that DNNs initially focus on simpler, low-order interactions and progressively transition to more complex, high-order interactions. The learning process is reformulated as a linear regression problem, which facilitates the analysis of how DNNs manage interaction learning under parameter noise.", "questions": "- How is it ensured that the model does not re-learn the initial interactions during the second phase? Please justify. \n- Please justify the disparity in VGG-16 on CIFAR-10 and VGG-11 MNIST based on Figure 5. It seems their distribution is a bit different from the others in the last time point.", "limitations": "- The experiments on textual data are limited. Expanding the analysis to include a broader range of datasets could provide a more comprehensive understanding of the DNN's interactions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The research backs its theoretical claims with sufficient experimental evidence. This thorough analysis strengthens the credibility of the study's conclusions.\n- The study explores the two-phase dynamics of DNNs, clarifying how networks transition from simple to complex interactions. This clarifies the mechanisms underlying neural network generalization and susceptibility to overfitting.", "weaknesses": "- The experiments on textual is limited compared to those on vision tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are glad to answer all your questions. **If you have new questions, please let us know as soon as possible, so that we can try our best to answer any further questions in the discussion period.**\n\n**Q1: Ask for experiments on more textual datasets.**\n\n> The experiments on textual data are limited. Expanding the analysis to include a broader range of datasets could provide a more comprehensive understanding of the DNN's interactions.\n\nA: Thank you. We have followed your suggestion to conduct **new experiments** on more natural language datasets, including the AG News dataset [cite1] for news classification, and the MNLI dataset [cite2] for natural language inference. We train the BERT-Tiny model and the BERT-Medium model on these datasets. Fig. 1 in the *response pdf file* shows that on all these models and datasets, the dynamics of interactions over different orders during the training process all exhibit the two-phase phenomenon.\n\n[cite1] Zhang et al. Character-level Convolutional Networks for Text Classification. NeurIPS 2015.\n\n[cite2] Williams et al. A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference. NAACL 2018.\n\n---\n\n**Q2:** \"How is it ensured that the model does not re-learn the initial interactions during the second phase? Please justify.\"\n\nA: A good question. Our theory does **not** claim that in the second phase, a DNN will not re-encode an interaction that is removed in the first phase. Instead, Theorem 4 and Proposition 1 both indicate the possibility of a DNN gradually re-encoding a few higher-order interactions in the second phase along with the decrease of the parameter noise.\n\nEssentially, we think the key point to this question is that the massive interactions in a fully initialized DNN are all chaotic and meaningless patterns caused by randomly initialized network parameters. Therefore, the crux of the matter is not whether the DNN re-learns the initially removed interactions,  but the fact that the DNN mainly removes *chaotic and meaningless initial interactions* in the first phase, and learns *target interactions* in the second phase. In this way, although a few interactions may be re-encoded later in the second phase, we do not consider this as a problem with the training of a DNN.\n\n---\n\n**Q3: Ask about slightly different distributions of the finally learned interactions in Figure 5.**\n\n> Please justify the disparity in VGG-16 on CIFAR-10 and VGG-11 MNIST based on Figure 5. It seems their distribution is a bit different from the others in the last time point.\n\nA: Thank you for your comments. In fact, our conclusion that \"DNNs with different architectures all share the same two-phase dynamics\" does **not** mean that different DNNs all encode exactly the same distributions of interactions. Instead, the distributions of interactions encoded by different DNNs may be slightly different, but their dynamics consistently exhibit two phases.\n\nIt is because Eq. (10) in our paper has shown that the distribution of interactions is determined by the state of the finally converged DNN after the last epoch, and feature representations of the finally converged DNN are affected by the network architecture and the dataset. Thus, the learning dynamics predicted by our theory also accordingly exhibit such slight differences among different DNNs and datasets.\n\nBesides, experimental results in Fig. 4 and Fig. 6 also show that our theory can well predict the slight difference of the interaction distributions between different DNNs throughout the entire training process. I.e., our theory predicts different interaction distributions for different DNNs and datasets.", "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": "7jAgulI0PU", "reviewer": "Reviewer_xnzG", "summary": "This paper studies the training dynamics (underfitting to overfitting) of deep neural networks via the perspective of symbolic interactions. They formulate the learning of interactions as a linear regression problem on a set of interaction triggering functions. They show the two-stage dynamics. In the first stage, neural networks first remove initial interactions and learn low-order interactions. In the second stage, neural networks learn increasingly more complicated interactions, leading to overfitting. Through empirical experiments, they show the story is valid for various architectures.", "questions": "* Line 21, \"the three conditions\". what are these three conditions?\n* Line 21, \"for\" -> \"For\"\n* Line 100, Eq. (2), can you explain more where does the factor (-1)^{|S|-|T|} comes from? This sign seem to be canceling terms out?\n* In Figure 2, it would be nice to also include training loss, not just train-test gap. Is there a time point when the interactions are too simple such that increasing order actually helps alleviate underfitting but still not overfitting?\n* How does the initial I_k distribution change with different initialization scales?", "limitations": "The authors adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well written, clear in motivation. Figures are pleasure to read.\n* Statements are justified with math theorems. \n* The link between underfitting-overfitting vs the distribution of I_k is novel.\n* Testing extensively on various architectures", "weaknesses": "* The contribution is not fully clear.  Since this work heavily relies on [26][27][45], it should clearly highlight what's new and what's known in pervious works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are glad to answer all your questions. **If you have new questions, please let us know as soon as possible.**\n\n**Q1: Ask for further clarification on the paper's contribution.**\n\n> The contribution is not fully clear. Since this work heavily relies on [26] [27] [45], it should clearly highlight what's new and what's known in previous works.  \n\nA: Thank you. We will follow your suggestion to further clarify a list of substantial contributions over previous works [26, 27, 45].\n\n(1) [27] is a theoretical foundation for our paper. As introduced in Lines 20-22 and Appendix B, [27] just proves that under three conditions, the a DNN's decision-making logic can be faithfully explained by a few symbolic interactions. Based on [27], we aim to further prove the two-phase learning dynamics of interactions.\n\n(2) We just use the re-formulation of the linear representation of interactions in [26] as a mathematical tool to prove the learning dynamics of interactions. In comparison, [26] just aims to discover the interaction bottleneck of Bayesian neural networks, which is fully different from our task of proving the learning dynamics of interactions on all types of DNNs.\n\n(3) Our proof of the learning dynamics does not have any direct connection with [45]. However, by combining the proven dynamics and [45]’s finding that \"high-order interactions have weaker generalization power,\" we will obtain the following significant conclusion: our derived dynamics of interactions also explain the dynamics of the generalization power of a DNN. This has been introduced in Lines 170-190.\n\n---\n\n**Q2:** \"Line 21, 'the three conditions'. what are these three conditions?  \"\n\nA: We have provided the three conditions in Appendix B. Please see Appendix B for details. In addition, we will revise Line 21 to make the reference to Appendix B clearer. \n\nSpecifically, the three conditions can be intuitively understood as requiring a DNN to generate relatively smooth inference scores on masked samples, and [27] shows that the three conditions are quite common and can be satisfied by DNNs trained for many real applications.\n\nNote that the proof of interaction dynamics in this paper does not depend on the three conditions. The three conditions are just used to prove the sparsity of interactions.\n\n---\n\n**Q3:** \"Line 21, 'for' -> 'For'. \"\n\nA: Thank you. We will correct this typo.\n\n---\n\n**Q4: Ask about the computation of interactions.**\n\n> Line 100, Eq. (2), can you explain more where does the factor (-1)^{|S|-|T|} comes from? This sign seem to be canceling terms out?  \n\nA: A good question. In fact, it is proven in Appendix E.2 that the coefficient $(-1)^{|S|-|T|}$ in Eq. (2) is the **unique** coefficient to ensure that the interaction satisfies the **universal matching property**. The universal matching property (in Line 105) means that no matter how we randomly mask an input sample ${x}$, the network output on the masked sample $x_S$ can always be accurately mimicked by the sum of interaction effects within $S$.  An extension of this property for AND-OR interactions is also mentioned in Theorem 2.\n\nNevertheless, we will clarify how the coefficient $(-1)^{|S|-|T|}$ is derived in the paragraph following Eq. (2).\n\n---\n\n**Q5: Ask for including the training loss in Fig. 2**\n\n> In Figure 2, it would be nice to also include training loss, not just train-test gap. Is there a time point when the interactions are too simple such that increasing order actually helps alleviate underfitting but still not overfitting?  \n\nA: We have followed your suggestion to show the training loss in Fig. 2. Please see the last column of Fig. 2 in the *response pdf file* for details. In fact, instead of considering underfitting (or learning useful features) and overfitting (or learning overfitted features) as two separate processes, the DNN simultaneously learns both useful features and overfitted features during training. The learning of useful features decreases the training loss and the testing loss, which alleviates underfitting. Meanwhile, the learning of overfitted features gradually increases the loss gap.\n\n---\n\n**Q6:** \"How does the initial I_k distribution change with different initialization scales?\"\n\nA: A good question. A short answer is that initializing a DNN with different scales only uniformly rescales the magnitudes of all interactions $\\forall S\\subseteq N, I^{new}(S|x)=\\lambda\\ I^{old}(S|x)$ by a constant $\\lambda$, but does not change the distribution $I^{(k)}$ of different interactions.\n\n**Theoretical analysis.** Let us take the output of a ReLU network corresponding to the target category before the softmax layer as the function $v$. If all randomly initialized parameters (the biases are typically initialized to zero) in the ReLU network are scaled with a constant $c$, $\\theta^{new}=c\\ \\theta^{old}$, then the value of all interactions will be scaled to $\\lambda=c^L$ times of their original values, where $L$ is the number of layers of the network. This is because the scaling of all initial parameters will cause the network output on any input to be scaled to $\\lambda=c^L$ times of the original value, $v^{new}(x)=c^L\\ v^{old}(x)$. Then, scaling the output $v(x)$ by $\\lambda$ will also scale the interaction $I(S|x)$ by $\\lambda$, according to Eq. (2). However, since all interactions are multiplied by the same constant $\\lambda=c^L$, the *normalized distribution* $I^{(k)}$ across different orders (defined in Line 159) remains the same. \n\nWe have also conducted **new experiments** to verify that initial $I^{(k)}$ distribution does not change with different initialization scales. We tested VGG-16 on the CIFAR-10 dataset. Fig. 3 in the *response pdf file* shows that when we scaled the initialized parameters with a constant $c=0.5$, $c=1.5$, and $c=2$, only the magnitude of interactions changed, but the distribution of interactions remained the same.", "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:
We would like to thank all reviewers for the constructive comments and questions. We have carefully considered all your comments and answered all the questions, and will revise the paper to clarify all your concerns. In addition, we have followed your suggestions to conduct **new experiments**, please see the **response pdf file** for results.

**Please let us know if you have further questions, so that we can get back to you as soon as possible.**

Meta-review: The paper gives a theoretical study of how the dynamics of learned symbolic interactions in DNNs evolve. The paper gives theoretical and empirical evidence for a two-phase learning dynamic for DNNs on data with sparse complex interactions.

While there has been some concern over the clarity of the paper and the overall message, reviewers appreciated the strength of the theoretical claims, backed with empirical evidence, and agree that this paper should be accepted. I therefore recommend accepting the paper.
Decision: Accept (poster)