DISCOVERING AND EXPLAINING THE REPRESENTATION BOTTLENECK OF DNNS
Authors: Huiqi Deng
Qihan Ren
Hao Zhang
Quanshi Zhang
Venue: ICLR 2022 Oral (2022)
Keywords: representation bottleneck
representation ability
interaction
explanation

Abstract: This paper explores the bottleneck of feature representations of deep neural networks (DNNs), from the perspective of the complexity of interactions between input variables encoded in DNNs. To this end, we focus on the multi-order interaction between input variables, where the order represents the complexity of interactions. We discover that a DNN is more likely to encode both too simple and too complex interactions, but usually fails to learn interactions of intermediate complexity. Such a phenomenon is widely shared by different DNNs for different tasks. This phenomenon indicates a cognition gap between DNNs and humans, and we call it a representation bottleneck. We theoretically prove the underlying reason for the representation bottleneck. Furthermore, we propose losses to encourage/penalize the learning of interactions of specific complexities, and analyze the representation capacities of interactions of different complexities. The code is available at https://github.com/Nebularaid2000/bottleneck.

Published as a conference paper at ICLR 2022
DISCOVERING AND EXPLAINING THE REPRESENTA- TION BOTTLENECK OF DNNS
Huiqi Deng' Qihan Ren, Hao Zhang, Quanshi Zhang!
Shanghai Jiao Tong University {denghq7, rengihan, 603023- 2gs edu.
ABSTRACT
This paper explores the bottleneck of feature representations of deep neural net- works (DNNs), from the perspective of the complexity interactions between input variables encoded in DNNs. To this end, we focus on the multi-order in- teraction between input variables, where the order represents the complexity of interactions. We discover that DNN is more likely to encode both too simple and too complex interactions, but usually fails to learn interactions of intermediate complexity. Such a phenomenon is widely shared by different DNNs for different tasks. This phenomenon indicates a cognition gap between DNNs and humans, and call it representation bottleneck. We theoretically prove the underlying reason for the representation bottleneck. Furthermore, we propose losses to en- courage/penalize the learning of interactions of specific complexities, and analyze the representation capacities of interactions of different complexities. The code is available https: htt.a//www.....eeeeeeeeeeeeee/ee
INTRODUCTION
The revolution from shallow to deep models a crucial step in the development of artificial intelli- gence. DNNs usually exhibit superior performance to shallow models, which is generally believed as a result of the improvement of the representation power (Pascanu et al. 2013 Montúfar et al.] 2014). To this end, instead of considering previous issues of the accuracy and the generalization ability of DNNs, we focus on the following two questions about the representation capacity:
Are there any common tendencies of DNNs in representing specific types of features?
Does a DNN encode similar visual concepts as human beings for image classification?
In order to answer the above two questions, we first investigate the bottleneck of feature representa- tion, i.e., which types of concepts are likely to be encoded by DNN, and which types of concepts this end, we discover that the interaction between input variables an effective tool to analyze the feature representation. It is because instead of considering input variables working independently, the DNN encodes the interaction berween input variables to form an interaction pattern for inference. For example, the inference of face image be explained as the interactions between left and right eyes, between nose and mouth, etc.
are difficult to learned.
As the answers to the above questions, we discover a common representation bottleneck of DNNs in encoding interactions, i.e., a DNN is more likely to encode both too complex and too simple inter- actions, instead of encoding interactions of intermediate complexity. This bottleneck also indicates a dramatic difference between the inferences of DNNs and humans.
The interaction can be understood follows. Let take the face recognition task for example. Let dimmouth measure the numerical importance of the mouth region i to the classification score. Then, the interaction utility between the mouth region and the nose region j is measured as the change of the @i-mouth value by the presence or absence of the nose region j. If the presence of j increases the importance di=mouth by 0.1, then, we consider 0.1 the utility of the interaction between i and j.
Equual contribution.
QQanssh Zhang is the corresponding author. He is with the John Hopcroft Center and the MOE Key Lab of Artifical Intelligence, Al Institute, at the Shanghai Jiao Tong University, China.

---

Published as a conference paper at ICLR 2022
much new information little new information
little information much new information
much information
Interaction strength
little new information
0.1n
0.5n
0.9b
Order
5%
10%
30%
70%
90%
95% patches
(a) Interaction pattern(b) Representation bottleneck(e) Whether humans/DNNSs extract new information from patches.
Figure 1: (a) Five pixels (g, h, j, interact with each other, forming edge pattern for classifi- cation. (b) Representation bottleneck. A DNN is likely to encode low-order and high-order inter- actions, but usually fails to learn middle-order interactions. (c) The cognition gap between DNNs and humans. Humans extract little information from a few image patches (e.g.. 5% patches). Also, given almost all patches (e.g., 90% patches), people learn little new information from the additional 5% patches since the information is already redundant for human recognition. In comparison, the DNN encodes most interactions when the DNN given very few patches or most patches.
Multi-order interactions. In order to represent the interaction complexity mentioned in the rep- resentation bottleneck, we use the multi-order interaction utility between variables i, proposed by Zhang et al. (2020). The interaction of the m-th order (im)),,) measures the average interaction utility between variables i. on all contexts consisting of m variables. In this way, the order m reflects the contextual complexity of the interaction. A low-order 1 (i, j) measures the relatively simple collaboration between variables i, and a few m contextual variables, while a high-order (im)) corresponds to the complex collaboration between j and m' massive contextual vari- ables, where m' > m.
Moreover, we prove that the multi-order interaction is trustworthy tool analyze the representation capacity of DNNs. Specifically, the output score of a DNN can be decomposed into utilities of compositional multi-order interactions between different pairs of variables, i.e., model oulput Em= Eije,, (m)) (i,j) Eien local utility of bias. For example, the inference score of face can be decomposed into the interaction utility between left and right eyes, between mouth and nose, etc. Therefore, we take the utility [(mm) j) as the underlying reason to explain the DNN, because each interaction makes a compositional contribution to the output.
Representation bottleneck of DNNs. Surprisingly, the above decomposition of multi-order interac- tions enables us to discover a representation bottleneck of DNNs. As Figure shows, low-order and high-order interaction utilities [(m)(i, (i.j) usually have high absolute values, while middle-order interaction utilities 7 7(m) (i. usually have low absolute values. In other words, DNN more likely to encode the interaction between variables and j. when i, interact with few contextual variables. Similarly, it is also easy for the DNN to learn the interaction, when i, interact with most contextual variables. However, it is difficult for the DNN to learn the interaction, when i, cooperate with a medium number of contextual variables. The difficulty of learning middle-order interactions reflects representation bottleneck of DNNs.
Cognitive gap between DNNs and humans. Such a representation bottleneck also indicates a significant gap between the concepts encoded by DNNs and the visual cognition of humans. As Figure[[c) shows, people usually cannot extract meaningful information from few image patches. Besides, if people are given almost all patches, then the information is already too redundant and inserting additional patches will bring in little new information. In contrast, the DNN encodes most information, when the DNN is given only a few patches or is given most patches.
Theoretical proof. In this paper, we theoretically prove the mechanism that is responsible for the representation bottleneck. Such proof also enables us to simulate the distribution of interactions of different orders, which well matches the distribution of interactions in real applications.
Beyond the theoretical proof, another important issue is how to guide the learning of feature rep- resentation in DNNs by learning interactions of specific orders. We propose two losses to en- courage/penalize the DNN to make inferences by interactions of specific orders, thereby boost- ing/preventing the learning of such interactions. Experimental results have validated the effective- ness of the two losses. Next, we investigate the representation capacities of several DNNs which encoded interactions of different orders. We find that the DNNs mainly encoding high-order interac- tions represent more structural information than the normally trained DNNs. In addition, high-order interactions were vulnerable to adversarial attacks.
2

---

Published as a conference paper at ICLR 2022
In summary, this paper makes three contributions:
This study discovers a representation bottleneck phenomenon of DNNs, i.e., it is difficult for a
DNN to learn middle-order interactions. It also clearly proves that DNNs and humans use different
types of visual concepts for inference.
We theoretically prove the underlying reason for the representation bottleneck.
We design two losses to encourageepenalize the DNN to learn interactions of specific orders. Experiments have validated the effectiveness of the proposed losses. Besides, we investigate the representation capacities of DNNs which encode interactions of different orders.
2
RELATED WORK
The representation capacity of DNNs. The evaluation of the representation capacity of DNNs provides a new perspective to explain and analyze DNNs. Pascanu al. (2013) and Montúfar et al. (2014) used the number of linear response regions in deep rectifier MLP to evaluate its represen- tation capacity. The information bottleneck theory (Shwartz-Ziv Tishby 2017 used the mutual information to explain how DNNs gradually learned the information during the training process. Achille & Soatto (2018). Amjad & Geiger (2019) and Hjelm et al. (2019) further improved the representation capacity by optimizing mutual information. Arpit et al. (2017) studied the memoriza- tion behavior of DNNs during training to analyze the feature representations. Xu (2018) proposed Fourier analysis to understand the generalization. In addition, several metrics were proposed to alyze the generalization capacity or robustness of DNNs, including the stiffness (Fort et al.] 2019). the sensitivity (Novak et al.] 2018), and the CLEVER score (Weng et al. 2018 Neyshabur et al. 2017) examined whether existing complexity measures can guarantee generalization.
Previous researches mainly studied the theoretical maximum complexity, generalization ability, and robustness of DNNs. In comparison, our research focuses on the limitation of DNNs in feature representations, i.e., which types of interactions are unlikely to be encoded.
Interactions. Interactions between input variables of a DNN have been widely investigated in re- cent years. Based on the Shapley value (Shapley [95I]. Grabisch & Roubens (1999) proposed the Shapley interaction index to define the interaction in cooperative game. Lundberg et al. (2018) used the interaction to build tree ensemble explanations for DNNs. Janizek et al. (2021) extended Integrated Gradients (Sundararajan et al.] 2017) to explain the pairwise feature interaction in DNNs. Sundararajan et al. (2020) proposed the Shapley Taylor interaction to measure interactions among multiple variables. Tsang et al. (2020) and [sang et al. (017)) interpreted DNNs by detecting sta-
tistical interactions between input variables and interactions between network weights, respectively.
Peebles et al. (2020) and sang et al. (2018) achieved the disentanglement of features by restricting interactions. Song et al. (2019) and Lian et al. (2018) designed network architectures to effectively learn feature interactions. Lengerich et al. (2020) applied the ANOVA technique measure inter- actions and further explored the relationship between dropout and interactions. /Zhang et al. (2020) proposed the multi-order interaction, and used it understand and boost dropout.
Besides, the team of Dr. Quanshi Zhang has adopted the game-theoretic interactions to build up a theoretical system explain the representation capacity of DNN, including explaining the gen-
eralization ability (Zhang et al., 2020), the adversarial transferability and adversarial attacks (Wang 2021bbr a) of a DNN, and explaining concepts encoded a DNN (Cheng et al., 2021 2021 a. Zhang et al. 2021b a).
Ren
et al.
3 REPRESENTATION BOTTLENECK
Before the analysis of the representation bottleneck, let us first introduce multi-order interactions between input variables, which are encoded in a DNN. Given a pre-trained DNN v and an input sample with set of n variables N [1....,n) n. (e.g., an input image with pixels), v(N) denotes the network output of all input variables. Input variables of DNNs usually interact with each other to make inferences, instead of working individually. In this study, we mainly discuss the pairwise interactions. For example, as Figure aa) shows, pixels i,j E N interact with each other, forming an edge pattern for classification. If the existence of this pattern increases the network output by 0.01, we consider this pattern has a positive utiliry of 0.01. Similarly, if the existence of this pattern decreases the network output, consider this pattern has negative utility.
3

---

Published as a conference paper at ICLR 2022
N.NO 0 < S n 2, was proposed to measure interactions of different complexities (Zhang al. 2020). Specifi-
Furthermore, the multi-order interaction (i. between two input variables i.
cally, the m-th order interaction 7(m)) (i, j) measures the average interaction utility between variables i,j under all possible contexts consisting of m variables. Therefore, the order m can be considered to represent the contextual complexity of the interaction. For example, as Figure IT) shows, five pixels (i. j. g. h. k) collaborate with each other and form an edge pattern for classification, Thus, the pairwise interaction between pixels i, j also depends on the three contextual pixels g. h k. Mathe- matically, the multi-order interaction [(m) (i, is defined as follows:
(1) where (,) = uSS (t.j)) - v(S U (1)) (S (1)) oSS). Here, e(S) is the output score when we keep variables in S S N unchanged but replace variables in N S by the baseline value. The baseline value follows the widely-used setting in Ancona et al. (2019), which is set as the average value of the variable over different samples. Let us take the multi-category image classification for example. Given an input image x, v(S) = v(æs) can be implemented any scalar
(
output of the DNN (e.g., log P(j=y""![ss) P(p-yamlzs) of the true category), where we replace the pixel values in N S of original input x by the baseline value (the average pixel value over images) to construct a v(S - (v(S - e(S) quantifies
masked image Zg. Then, Av(i,j, the marginal effects (the importance) of the variable j that are changed by the presence or absence of the variable i. It represents the utilities of the collaboration between i, in a context S.
Generic metric. The proposed multi-order interaction f(m) is generic metric, which has strong connection with the Shapley value (Shapley) [95T] and the Shapley interaction index (Sun-) dararajan al. (0200) in game theory. In addition, has been proven that ((m)(i, satisfies the following five desirable properties, i.e., linearity, nullity, commutativiry, symmetry, and efficiency properties. The connections with existing metries and five properties are introduced in Appendix
3.1 REPRESENTATION BOTTLENECK
According to the efficiency property of (i,j), we find that the output of a DNN can be explained as the sum of all interaction utilitics of different orders between different pairs of variables.
xNN) = v(t) + ΣIEN H4 + > Ei.EEN.HHS
n--
w (m) f(m)) (i.j)
(2)
where μ4 = v((i) e0). and (m))) (n 1- 1-mm)/ [m(n- 1)]. Because / (Tm) j) measures the interaction between variables i j encoded in DNNs with m contextual variables, we can consider the interaction utility I [(m² (t. as a specific reason for the inference, which makes a compositional
contribution (m)) ((m) (i. the output.
In this way, we can categorize all underlying reasons for the network output into different com- plexities. Low-order interactions can be considered as simple underlying reasons, relying on very few variables. High-order interactions can be regarded as complex underlying reasons, depending on massive variables. In order to measure the reasoning complexity of the DNN, we measure the relative interaction strength ((m) of the encoded m-th order interaction follows:
Ezen (1 (i. []]
f((m)
E [Ewen [ (1. [III)=
where Ω denotes the set of all samples. ((m) is computed over all pairs of input variables in all
samples. ((m) is normalized by the average value of interaction strength. The distribution of J(m) measures the distribution of the complexity of interactions encoded in DNNs.
Representation bottleneck. Based on the above metric, we discover an interesting phenomenon: DNN usually encodes strong low-order and high-order interactions, but encodes weak middle-order interactions. Such phenomenon is shared by different DNN architectures trained different datasets, which is illustrated by the ((m) curves in Figure 2
Specifically, when the order m is smaller than 0. or greater than 0.9m, the interaction strength (mm is usually high. In comparison, ((m) is usually low when the order m approximates 0.5m. Moreover, Figure 3(a) shows that such a phenomenon does not only exists in well-trained DNNs, but also exists in the entire training process.
The above phenomenon indicates that a DNN is more likely to learn simple interactions where a few variables (e.g., less than 0. In variables) interact with each other. Similarly, it is easy for DNN to
4

---

Published as a conference paper at ICLR 2022
AlexNet
VGG-16
ResNet-18/20
ResNet-50:56
MLP tabular
Strength
5.0
Tiny ImageNet
ImageNet
5.0
ImageNet
Imageeect
5.0
ImageNet Tiny ImageNet
ImageNet Tiny IntggNett
1.5
MLP-5
CIFAR-10
CIFAR-10
CIFAR-10
CIFAR-10
MLP-8
2.5
2.5
2.5
1.0
MLP-8
0.0
0.0
0.0
0.0
0.1n
0.5n order
0.9n
0.1n
0.5m order
0.9m
0.1n
0.5m order
0.9g
0.1m
0.5n order
0.9m
0.
0.5n
0.9n
order
Figure 2: The distributions of interaction strength J(m) of different DNNs trained on various image datasets and tabular datasets [
encode complex interactions where massive variables (e.g., more than 0.9n variables) participate. However, it is difficult for DNN to learn middle-complex interactions in which medium number of variables (e.g., about 0.5z variables) participate. Let us take Figure (e) for an example. When a successfully
c)
DNN is given very few patches sparsely distributed on the horse image, the DNN extract the interaction between the few patches. Similarly, when the DNN is given almost all patches, then the insertion of two new patches will make the DNN trigger strong collaboration between the two patches and massive existing patches. However, when the DNN is just given a half patches, it is difficult for the DNN to encode interactions between the two patches. In a word, the encoded interaction pattern is either too simple or too complex. The difficulty of learning interaction patterns of moderate complexity reflects a common tendency in the feature representation of DNNs.
Such representation bottleneck also indicates that DNNs and human beings encode different types of visual patterns for inference. As Figure[[c) shows, (i) Given very few patches, a DNN can encode much information from low-order interaction patterns between patches. However, it is difficult for people to recognize such low-order interactions.
(ii) Given almost all patches of an image, any additional patches are already too redundant for human cognition, so people do not obtain much new information from additional patches. (iii) Given a medium number of patches, the DNN usually extracts little information, while people can extract much information for recognition.
Implementation details. In order to measure J(m), we conducted experiments on three image datasets including the ImageNet dataset (Russakovsky et al.] 2015), the Tiny-ImageNer dataset (Le) & YYng 2015) and the CIFAR-I0 dataset (Krizhevsky et al. 2009). We mainly analyzed several
DNNs trained on these datasets for image classification, including AlexNet (Krizhevsky et al. 2012), VGG-16 (Simonyan& & Zisserman 2014) and ResNett-1/20050//5 (He et al.]|2016] Due to the high dimension of input variables (n = 224 x 224 for ImageNet), the computational cost of f(m) is intolerable. To reduce the computational cost, we split the input image into 16 x 16 patches, and P( considered each patch as an input variable. To compute (mm), we set (S(xx) = log T-P(g=y" [as] given the masked sample Is, where y" is the true label and P(ù y (x<=)) is the probability of classifying the masked sample Iy to the true category. In the masked sample Iy, pixel values in image patches in N S were replaced by the average pixel value over different patches in all images,
just like in Ancona et al. (2019). Note that (m) is an average over all possible contexts S, all pairs of variables (i, (), and all samples x. which is computationally infeasible. Therefore, we approximated (mm) using a sampling strategy (Zhang et al. 2020). Please see Appendix C for sampling details. In addition, we conducted experiments on two tabular datasets, including the UCI census income dataset (census) and the UCI TV news channel commercial detection dataset (commercial) (Dual al. 2017). Each sample in the two datasets contained n = 12 and n = input variables, respectively. We analyzed five-layer MLP (namely, MLP-5) and an eight-layer MLP (namely, MLP-8) network. Each layer except for the output layer contained 100 neurons. In the computation of (m)) P(ğ = =y" (rs) was also computed by setting the baseline value of variable the average value of the variable. Please see Appendix C for details.
3.2 EXPLAINING THE REPRESENTATION BOTTLENECK
In this subsection, we theoretically prove the underlying reason for the representation bottleneck. Let W e R denote the network parameters of a DNN. We focus on the change AW of network parameters, which also represents the strength of training the DNN, The change of weights is calcu-
Note that the strength of high-order interactions on tabular datasets is higher than that on image datasets. It may he because the image classification usually depends on low-order interactions, but the classification on tabular data mainly depends on high-order interactions, therehy foreing DNNs to learn high-order interactions.
5

---

Published as a conference paper at ICLR 2022
Dynamies
AlexNet
VGG-16
ResNet-18
ResNNet-5 Net-50
Strength
40 spoch
1.0
1.0
f(m)
1.0-
((o)
1.0
P(0)
3.0-
80 spoch
[(m)
f0n0
(m)
120 spach
0.5
0.5-
160 epocly
0.0
0.1m
0.5m Order
0.5m
0.1n
0.5m
0.9m
0.0
0.1n
0.5n
0.9m
0.1n
0.5m
0,9h
0.0
0.1m
0.5n
0.9m
Order
Order
Order
Order
(a) Dynamics
(b) Simulations
Figure 3: (a) Distributions of the interaction strength ((m) of ResNet-20 model over different orders, which were measured after different training epoches. The DNN was trained on the CIFAR- 10 dataset. (b) Simulations of the j(m) distributions based on f((m) curves on the ImageNet dataset.
aL Be(N) Here, L denotes the loss function, and is the learning DL 1 ae(N) BW lated by AW w
rate. According to Eq. 2 the network output v(N) of the DNN can be decomposed into the sum of multi-order interactions [(m) (i,g). Therefore, AW can be further represented as the sum of gradients (f.)) of multi-order interactions.
8W
aL dv(N) AW 11 Du(N) aW AW - 2-=2
m=o Σ
Aw(m)ii,
(4)
where U = v(0) EIEN M4. Specifically,
dL (v(N) OU do(NN OU aw AWa del
AW (1.5) del (m) (l (i.j)
aW
aL (e(N) where ((m) = 1) De(NN (1a)) Here, AWy represents the component of AW w.t. aw and Ai(m)(i.) represents the component of AW w.r. (1fm) oW
80
Therefore, besides AWv, we can consider there are additional m(n-1)² paths w.r.t. different pairs of i,j and different orders m in the backpropagation, and the weight change through each propagation path is (i,))) In this way, we can consider the norm of AW(m)) (i.e., ([ (i. (122) measures the strength of learning the interaction between variables and j under contexts of m variables.
2
Theorem (Proof in Appendix Assume Eij,s
( = Let a² denote the vari- aW
ance of each dimension of 8Aplig.5) Then, Bi ( W (m)) (i, o and the variance of each (TaeN m(=-1) "=- (mm²) Therefore, (mm)) =
dimension of (i,m) is (n at n-m-1
n-m-1 K ((1) (e(N) m(n-1) o0 (m=3). where is the dimension of the network parameter W.
Theorem 1 shows that the strength (i.e., the (2-norm (m) (i,j)ll2) of learning m--rder inter- actions is proportional to p(m) n-m-1 // (²=²). Therefore, when the order m is small or large (e.g., m 0.05n 0.95n), the training strength of the m-order interaction is relatively higher. In contrast, when the order m is medium (e.g., m = 0.5m), the training strength of the m-order inter- action is much lower. The above analysis explains why is easy for DNN to learn low-order and high-order interactions, but difficult for DNN to learn middle-order interactions.
Simulation of the curve of the interaction strength. We find that the above training strength can be used simulate the distribution of interaction strengths J(m) in real applications, which verifies our theory. Based on Theorem 1, the training strength w.t.. the order m is proportional to the aforementioned F(m) so we can use F(m) to simulate J(m), For fair comparison, we normalized
F(m) and (mm by ((m) p(m) (0)) and f((m = J[m)/ /(()) such that ((0) = j(o) = 1. Figure ((b) shows that the curves of f(m) can well match the distributions of j(m), Due to the redundancy of feature representations in DNNs, we usually consider that the actual dimension ní of the latent space of DNNs is much lower than the number n of input variables. Thus, instead of directly using the number n. of input variables, we adopted a smaller n' (i.e,, n' < n) in F(m) for the simulation.
3.3 METHOD TO CONTROL INTERACTIONS OF SPECIFIC ORDERS
The representation bottleneck is widely shared by DNNs different architectures for various tasks, when these DNNs normally trained. In this section, mainly explore methods, which force the

---

Published as a conference paper at ICLR 2022
(a)
Encourage
Penalize
(c) AlexNet on CIFAR-10
Alex on Tiny
(0.2%,
[0.2n,
(Cn, 0.2s
Nonmal DNN
it.
0.5vl (6/46, D.6n)
0..3n.
jre, 0.5e]
ooder DNN
Weight
Siroggh
Strongth
Midilleunkz DNM
Miskil--uriir Hi Highyorder DNN
Highsonde DNN
0.00
0.2m
0.4n
0,60
0.8g
1.0n
0.2g
0.6m
1.0n
0.1n
0.50
0.90
0.3n
0.5m
0.5ts
Order
Order
Order
Crier
Figure 4: (a) Weight coefficients (6(m) of different orders with different pairs of (r1, (2), (b) Distri- butions of the interaction strength ((m) over different orders. Each curve indicates a AlexNet whose interactions were encouraged/pennalzed by L (r(,,))) and L (r), with certain pairs of (ri, r2). (c) Distributions of ((m) of four types of DNNs (AlexNet). The Appendix C provides more results.
DNN to learn interactions of specific orders. this way, we can investigate the properties feature representations of such DNNs.
In order to force the DNN to learn interactions of specific orders, propose two losses in the training process. The two losses encourage and penalize interactions of specific orders, respectively. Before designing the two losses, let us focus on the output change Au(ri,
Au(ri, r2) = Sg (g,gs, - r2/r1 e(S1)),
(5)
where the subsets S₁ and S2 are randomly sampled from all input variables N, such that (1 S S1 E S r1
S2 C .N, |S|] = "in,|sa) = r2,, and
< r2 S 1.
Theorem 2. (Proof in Appendix B) The output change Au(ri, r2) can be decomposed into the sum of multi-order interactions between different pairs of variables.
Au(r1, r2) (2/r1)/((0) Em
m== Σ
(m) p(m)) (i,
LJENN
(r2/11 1) 1)/ (n 1)} (r2n - m 1)/mm(n 1)),
rin
(6)
where
(m))
rin - 2 < m r2n
0,
F2n 2 < m S n
Interestingly, as Figure 4a) shows, we can consider that the output change Au(ri, r2) mainly encodes interactions whose orders are in the range of [0, ryn]. The weight coefficient (m)) of the m-th order interaction reaches a peak at the 7-h order in Au(r1,72).
Encourage/pennalze interactions of specific orders. Based the above analysis, Au(ri, r2) only contains partial interactions of the [0, ren]-th orders. Hence, we propose two losses based on Au(ri: r2), which encourage and penalize the DNN to use interactions of specific orders for in- ference, respectively. The first proposed loss L (r1.r2) forces the DNN mainly use interactions encoded in Au(r1, 12) for inference, thereby boosting the learning of these interactions.
1 [ Σ
L (+(,)))))=
Ply" c/z: log P(j = r(a
(7)
where I (f1, is the cross entropy that uses Au(r1, r2) for classification. Here, St is the training set, and C denotes the number of classes. Given an input image E Ωt y" is the true label, and denotes the predicted label. Here, Auc(ri, r2/0) = (S2 r2/r1 . ve (e) [z) denotes the change of the logits of the category c, where the logit (S(x)) denotes the feature dimension corresponding to the c-th category before the softmax layer. The two subsets S1. S2 are randomly sampled. In this way, we compute Plğ cl c/Aug(r1, x)) as the probability of using the C-dimensional vector (11,(r1) < < C} to classify the sample to the category c. We input the C-dimensional S c S C} into the softmax layer to compute the probability.
vector (Au,(ri,
Besides, the second loss L (r1, is designed to prevent the DNN from encoding interactions of the [0, r2n]-th orders. Specifically, we maximize the entropy of classification based on Au(ri, r2). in order to make Au(r1,72 72) non non-discriminative.
L (T1,72))
Σ
P (r1, log P(j ([Ame(ri,raaa)))
(8)
EE
where L (2) denotes the minus entropy of the classification probability based on Au (11,
In this way, we can train a DNN using the following loss
Loss LoSSelasafiaatin + A I (F1, + Agt. (r.,((1))2)
7

---

Published as a conference paper at ICLR 2022
(left) Classification accuracies of four types of DNNs, including the normally trained DNNs, and the other three types of DNNs mainly encoding low-order, middlc-order, and high-order interactions. (right) Comparison of adversarial accuracies between normally trained DNNs and DNNs mainly encoding high-order interactions on the census dataset and the commercial dataset.
Table 1:
CIFAR- 10
Tiny Image Net
Normal training
Penalize oww-rrder boost high-order
Model
Model
AlexNer
VGG16
VGG19
Alex
VGG16 VGG19
Normal training
90.61
56.00
52.56
MLP-5 census
38.22
7.31
Low internction
86.97
89.99
89.74
58.68
55.60
55.04
MLP-8 on census
39.33
2.02
Mid intoraction
86.65
90.29
90.03
53
55.84
53.36
MLP-5 on commer
27.01
High interaction
88.68
90.84
90.79
56.12
55.36
53.28
MLP-8 on commer
25.92
20.58
where A1 0, A2 2 0 are two constants to balance the three terms.
Effeets of the two losses. In experiments, we found that the loss L - (T1,T2) usually could success- fully penalize interactions of the [rin, 72n]]th orders and (21, could encourage interactions of the [rin, r2n]-th orders, instead of penalizing/encourainng interactions of the [0, rrn]-th orders. Specifically,
follows. We trained AlexNet the Tiny-ImageNet dataset to encourage interactions of specific orders without penalizing any interactions by setting
conducted experiments
A = 1, Ao O. Besides, we set [ri 0.2, r2 0.5), [ri 0.3, r2 0.7]. and [ri 0.6, r2 0.9 in the (r1,, r2) loss to learn three AlexNet models, respectively. We also trained AlexNet models to penalize interactions of specific orders by setting \ 0, d2 1. Two DNNs were trained by setting [r] = 0, r2 0.2] and [r] = 0, = 0.5] in the L (r1,, r2) loss, respectively. Figure 4fb) shows the interaction strength ((m) of these DNNs. When we encouraged the DNN to encode interactions of the [r)m, r2n]- -th orders, the interaction strength J(m) of the [rin, r2n] -th orders sig- nificantly increased, compared the normally trained DNNs. Figure (b) also shows that the loss L (f1,r2) could successfully remove interactions of the [rin, r2n]-th orders.
3.4 INVESTIGATION OF THE REPRESENTATION CAPACITIES
In the previous subsection, we introduced two losses, which force the DNN to encode interactions of different orders. In this subsection, we investigate the representation capacities of such DNNs. Thus, we conducted experiments train four types of DNNs. The first type of DNN was normally trained. The other three types of DNNs were trained to mainly encode low-order, middle-order, and high- order interactions, respectively. Specifically, the second DNN was trained to penalize interactions of the [0.7n, -thth orders by minimizing the L (r1, r2) loss with X1 0, 1, 0.7, 1.0 The third DNN was learned to boost interactions of the [0.3n, 0. 0.7n|-th orders by minimizing the (+(ri,r)) loss with A 1, A2 O, ri 0.3, r2 = 0.7. The fourth DNN was trained penalize interactions of the [0, 0.5m] -th orders by minimizing the (ri, loss with λ = 0, A2 1, 0,r2 0.5. The second DNN, the third DNN, and the fourth DNN were termed the low-order DNN, the middle-order DNN and the high-order DNN, respectively. In experiments, we trained three versions of each DNN based on the above four settings. We applied architectures of AlexNet and VGG-16/19 on the CIFAR-10 10 and the Tmny- dataset.
Figure c) and Figure g (in the appendix) show that the trained DNNs successfully learned inter- actions as expected. In other words, interactions of the [0.7n, n|-th orders were penalized in the low-order DNN. Interactions of the [0.3m, 0.7n] -th orders were boosted in the middle-order DNN. Interactions of the [0, 0.5m0..)... -th orders were penalized in the high-order DNN.
Classification accuracy. Firstly, Table [ shows classification performance of the above four types of DNNs. In general, the four types of DNNs achieved similar accuracies. The similar performance indicated that was not necessary for a DNN to encode low-order interactions and high-order inter- actions make inferences. Middle-order interactions could also provide discriminative information.
Bag-of-words representations vs. structural representations. Theoretically. high-order interac- tions usually represent the global structure of objects, which requires the complex collaborations of massive input variables. In comparison, low-order interactions learn local patterns from local and simple collaborations of a few input variables.
Therefore, we conducted two experiments to examine whether the high-order DNN encoded more structural information than the normally trained DNN. Specificcl, as Figure5]shows,, in the first ex-
'The parameter X2 was set 0.1 for VGG-16/19 networks trained on the Tiny-ImageNet dataset.
8

---

Published as a conference paper at ICLR 2022
90%
80%
70%
60%
50%
40%
90%
80%
70%
60%
50%
40%
masked
Figure 5:
Tested images by random masking (left) and centrally masking (right).
Nommal DNN on CIFAR-10
High-order DNN on CIFAR-10
Normal DNN Tiny ImgNet
High-order Tiny ImeNet
random
random
random
randon
accuracy
0.75
centrally surrounding
0.75
centrally sur surroushing
centrally-surroome
contrally-ssuroole surrommding
0.30
0.50
0.2
0.2
0.25
area: small
0.25
arca, arra:large
area: small
Karge
0.1a
0.1n
0,9m
0.0
0.50
0.9n
0.0
0.1n
0.5n
0.9m
Preserving rale
Preserving rale
Preserving rate
Preserving rate
Figure Classification accuracies using VGG-16 on images with different numbers of patches being masked. The Appendix
C provides more results.
periment, we tested the DNN images where patches in each image were randomly masked. In the second experiment, we tested the DNN on images where m patches in each image on the image boundary were masked, and the patches in the center were preserved. In this way, we consider the structural information in tested images was destroyed in the first experiment, but such information was maintained in the second experiment. Here, in each sub-figure in Figures and we computed the area between the accuracy curve on samples generated by the random masking method and the accuracy curve on samples generated by the surroundds masking method. The area dicated the sensitivity to the structural destruction. We found that such area of high-order DNNs was much larger than the area of normally trained DNNs. This phenomenon indicated that normally trained DNN usually encoded local patterns, just like the bag-of- words representations, which were robust to the structural destruction. However, high-order DNN encoded more structural information.
Adversarial robustness. Ren et al. (202bb) have demonstrated that adversarial attacks mainly af- fected high-order interactions. Therefore, we conducted experiments to train DNNs mainly encoding high-order interactions based on the proposed losses, in order to verify whether such DNNs were more vulnerable to adversarial attacks. To train DNNs mainly encoding high-order interactions, we trained to encourage interactions of the [0.6n, n]- th orders by setting 71 = 0.6, F2 = 1 for L (71, r2) and simultaneously penalize interactions of the [0. 0.5m]]th orders by setting r
set X 1, A2 = 1. Specifically, the DNN
0, = 0.5 for L- L-(r1, r2). We used the aforementioned MLP-5 and MLP-8 networks in Section 3.1l Each MLP was trained on the census and commercial datasets, respectively. Figure 7 in the appendix shows distributions of interaction strength of these DNNs. Then, we compared the adversarial robustness between normally trained DNNs and the DNNs whose high-order interactions were boosted. We adopted the untargeted PGD attack (Madry) et al. 2018) based on Too norm. We set the attack strength = 0.6 with 100 steps for the census dataset, and set = 0.2 with steps for the commercial dataset. The step size was uniformly set to 0.01 for all attacks. Please see more details in Appendix C Table shows that DNNs with boosted high-order interactions exhibited significantly lower adversarial accuracies than normally trained DNN, especially on the census dataset. These results verified that high-order interactions were vulnerable to adversarial attacks.
4 CONCLUSION
In this paper, we have discovered and theoretically proved the representation bottleneck of DNNs, from a new perspective of the complexity of interactions encoded in DNNs. We adopted the multi- order interaction, and used the order to represent the complexity of interactions. We discovered a common phenomenon that a DNN usually encoded very simple interactions and very complex inter- actions, but rarely learned interactions intermediate complexity. We have theoretically proved the underlying reason for the representation bottleneck. Furthermore, we proposed two losses to learn DNNs which encoded interactions of specific complexities. Experimental results have shown that is not necessary for DNN to encode avoid encoding interactions of specific orders, in terms of classification performance. However, high-order interactions usually encode more structural infor- mation than low-order interactions, and are usually vulnerable adversarial attacks.

---

Published as a conference paper at ICLR 2022
5 REPRODUCIBILITY STATEMENT
This research discovered and theoretically explained the representation bottleneck phenomenon, based on the multi-order interaction. Appendix ( AJsowws the trustworthiness the multi-order inter- action, by introducing its five desirable properties and its connections with existing typical metrics in game theory. Appendix and Section 3.2 provide proofs for all theoretical results the paper. Section 3 and Appendix C have discussed all experimental details, including the computation of in- teraction strength and how to train DNNs by the proposed two losses, which ensure the reproducibil- ity. Furthermore, the code has been released
Acknowledgments. This work is partially supported by National Science and Technology In- novation 2030 Major Project of the Ministry of Science and Technology of China under Grant (2021ZD011 602), the National Nature Science Foundation of China (No. 61906120, U19B2043), Shanghai Natural Science Fundation and Technology Major Project (2021SHZIZZ00000,
Shanghai Municipal Science
REFERENCES
Alessandro Achille and Stefano Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE transactions on pattern analysis and machine intelligence, 40 (12):2897-2905, 2018
Rana Ali Amjad and Bernhard C Geiger. Learning representations for neural network- clas- sification using the information bottleneck principle. IEEE transactions on pattern analysis and machine intelligence, 42(9):2225-221) 2019.
Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with a poly- nomial time algorithm for shapley value approximation. In International Conference Machine Learning, pp. 272-281. PMLR, 2019.
Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. International Conference on Machine Learning, pp- 243-242. PMLR, 2017.
Xu Cheng, Chuntung Chu, Yi Zheng, Jie Ren, and Quanshi Zhang. A game-theoretic taxonomy of visual concepts dnns. arXiv preprint arXiv:2106. 10938, 2021.
Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017.
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective on generalization in neural networks. arXiv preprint arXiv:1901.0949) 2019.
Michel Grabisch and Mare Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of game theory, 28(4):547-565, 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Devon Hjelm, Alex Fedorov, Samuel Aavoie-Marchildon Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Joseph Janizek, Paseal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks. Journal of Machine Learning Research, 22(104): 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
10

---

Published as a conference paper at ICLR 2022
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, volume 25, pp. 1097-1105, 2012.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 23/N, 7(7):3, 2015.
Benjamin Lengerich, Eric P Xing, and Rich Caruana, On dropout, overfitting, and interaction effects in deep neural networks. arXiv preprint arXiv:2007.00823 2020.
Jianxun Lian, Xiaohuan Zhou, Fuzheng Zhang, Zhongxia Chen, Xing Xie, and Guangzhong Sun. xdeepfm: Combining explicit and implicit feature interactions for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1754-1763, 2018.
Scott M Lundberg and Su-In Lee. unified approach to interpreting model predictions. Proceed- ings of the 31st international conference neural information processing systems, pp. 4768- 4777, 2017.
Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint 180.vv:800.000000 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems, 2014.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring gener- alization in deep learning. Advances in Neural Information Processing Systems, 2017.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study. arXiv preprint arXiv:1802.08766 2018.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. arXiv preprint arXiv: 1312.6098, 2013.
William Peebles, John Peebles, Jun-Ya Yan Zhu, Alexei Efros, and Antonio Torralba. The hessian penalty: A weak prior for unsupervised disentanglement. Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part VI 16, pp. 581-597. Springer, 2020.
Jie Ren, Mingjie Li. Qihan Ren, Huiqi Deng, and Quanshi Zhang. Towards axiomatic, hicrarchical, and symbolic explanation for deep models. arXiv preprint arXiv:2 1..0226 2021a.
Jie Ren, Die Zhang, Yisen Wang, Lu Chen, Zhanpeng Zhou, Xu Cheng, Xin Wang, Yiting Chen, Jie Shi, and Quanshi Zhang. came-theoretic understanding of adversarially learned features. arXiv preprint arXiv:2103.00 00.00344..4,, 2021b.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJV), 15(3):211-22) 2015. doi: 10. 1007/51 1263-015-0816-y.
I.S Shapley. Notes on the n-person game-ii: ii: The value of n-person game, the rand corporation, the rand corporation. Research Memorandum, 670, 1951.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. arXiv preprint arXiv: 1703.070 008100 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference Learning Representations, 2014.
11

---

Published as a conference paper at ICLR 2022
Weiping Song, Chence Shi, Zhiping Xiao, Zhijian Duan, Yewen Xu, Ming Zhang, and Jian Tang. Autoint: Automatic feature interaction learning via self-attentive neural networks. In Proceed- ings of the 28th ACM International Conference Information and Knowledge Management, pp- 1161-1170, 2019.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. PMLR, 2017.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pp. 9259-9268. PMLR, 2020.
Michael Tsang, Dehua Cheng, and Yan Liu. Detecting statistical interactions from neural network weights. In International Conference on Learning Representations, 2017.
Michael Tsang, Hanpeng Liu, Sanjay Purushotham, Pavankumar Murali, and Yan Liu. Neural in- teraction transparency (nit): Disentangling learned interactions for improved interpretability. Ad- vances in Neural Information Processing Systems, 31:5804-5813, 2018.
Michael Tsang, Dehua Cheng, Hanpeng Liu, Xue Feng, Fric Zhou, and Yan Liu. Feature inter- action interpretability: A case for explaining ad-recommendatioo systems via neural interaction detection. In International Conference on Learning Representations, 2020.
Xin Wang. Shuyun Lin, Hao Zhang, Yufei Zhu, and Quanshi Zhang. Interpreting attributions and interactions of adversarial attacks. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pp. 1095-1100 1104, 2021a.
Xin Wang, Jie Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang, and Quanshi Zhang. A unified approach to interpreting and boosting adversarial transferability. In International Conference on Learning Reprexentations, 2021
Tsui- Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. arXiv preprint arXiv:1801.1057 2018.
Zhiqin John Xu. Understanding training and generalization in deep learning by fourier analysis. arXiv preprint arXiv: 1808. 042995 2018
Die Zhang, Huilin Zhou, Hao Zhang, Xiaoyi Bao, Huo, Ruizhao Chen, Xu Cheng, Mengyue Wu, and Quanshi Zhang. Building interpretable interaction trees for deep nlp models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 14328-14337, 2021a.
Hao Zhang, Sen Li, Yinchao Ma. Mingjic Li, Yichen Xic, and Quanshi Zhang. Interpreting and boosting dropout from game-the view. In International Conference Learning Repre- sentations, 2020.
Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang, Interpreting multivariate shapley interactions in dnns. In Proceedings of the AAAI Conference on Artificial Intellgence, volume 35, pp. 10877-10886, 2021
12

---

Published as a conference paper at ICLR 2022
A
THE MULTI-ORDER INTERACTION
Zhang et al. 2020) proposed the multi-order interaction between input variables i,j as follows:
[(m) (i, = ( -B
where A -
(1, denotes the interaction
between variables i E N of the mn-th order, which measures the average interaction utility between
variables i.j under contexts of m variables. It has been proven that I [(m) (i.j) satisfies the following five desirable properties.
Linear property. If two independent games and combined, ie., for VS C N, w(S) u(S) + v(S), then the multi-order interaction of the combined game equals to the sum of multi- [i, (i, + I! (i.
order interactions derived from u and I.e., T60m) [i,
Nullity property. A dummy variable i E NN satisfies VS C N
W (d).v(5 uS ((]) v(S) + v(()))
Then, the variable i has no interactions with other variables, i.e., Vm, Vj E N (im Commutativity property. Vi,j E N, (im) = ((m) (j,
Symmetry property. Assume two variables i,j are equivalent in the sense that i.j have same cooperations with other variables, AS S N (i.5), (S) = e(Su Then, for any variable
k E N, (i,) = (im) (j,kk) k).
Efficiency property. The network output of DNN can be decomposed into the sum of interactions of different orders between different pairs of variables.
c(N) v(0)= = ExEx 14 + Σ EnJENNA
n E
(m) ( ((m)) (im)),.
m=0
where b4 v((()) v(0) represents the independent effect of variable i, and mm(m) 1- 1-11-m n(n-1)*
Connection with the Shapley value and the Shapley interaction index.
Shapley value. Shapley 1951) proposed the Shapley value to measure the numerical importance of each player to the total reward in cooperative game. The Shapley value has been widely used
to explain the decision of DNNs in recent years (Lundberg & Lee 2017 Ancona et al. 2019). Specifically, we can consider DNN with a set of input variables N {I....,.1 .. as game. Each input variable (e.g., an image pixel or a word) is regarded as player, and the network output v v(N) of all input variables can be considered as the total reward of the game. The Shapley value aims to fairly distribute the network output to each individual variable as follows:
|S| 1)! n!
(ii) Σ SCNVE)
( -iS))
where uSS) denotes the network output when we keep variables in S unchanged while mask vari- ables in N S by the baseline value. The baseline value usually follows the setting in Anconal ct al. (2019) which is set as the average value the variable over different samples. this way, (S (+)) v(S) represents the marginal contribution of i when the variable i is present w.E.t. the case when the variable i absent, given the context S C N \ {i}. Then, the Shapley value of i measures the average marginal contribution of over different contexts S. It has been proven that the Shapely value is the unique method to fairly allocate overall reward to each player that satisfies linearity, nullity, symmetry, and efficiency properties.
Shapley interaction index. Grabisch & Roubens (1999) proposed the Shapley interaction index T(SS) measure the interaction utility between input variables in the subset S N. In particular, the Shapley interaction index between two variables i, E N. ji) measures the change of the numerical importance (i.e., Shapley value) of i by the presence or absence of j.
Inder(i,j) Ō(i) always present
H(i) always absent.
(10)
where {(1), always present denotes the Shapley value of the variable computed under the specific con- dition that the variable j is always present. ((1); always absens is computed under the specific condition that j is always absent.
Connections with the Shapley interaction index and the Shapley value. We found that the multi- order interaction has strong connections with the Shapley interaction index and the Shapley value.
13

---

Published as a conference paper at ICLR 2022
Specifically, it has been proven that the interaction index Inder(i,j) between variables i.j, which closely related to the Shapley interaction index, can be decomposed into multi-ordes interactions as follows.
Inder(1,
n m=o 7(m) ( (i.j).
Besides, the Shapley value of the variable also can be decomposed into the multi-order interactions.
< Σ
BIENUO E k=
7 (1, v(i) vv()
B PROOF OF THEOREMS
B. PROOF OF THEOREM 1
Motivation of Theorem Let W denote the network parameters of the DNN. Let L and r denote the loss function and learning rate of training, respectively. Here, we consider the change of net-
work parameters AW be(N oW whose norm indicates the learning strength of the DNN. According to the efficiency property of (i, in Eq. ( the network output v(N) of DNN can be decomposed into the of multi-order interactions (i. of different orders between different pairs of variables. Therefore, the change AW of parameters can be also decomposed into
ar @e(N),
the sum of the gradient of multi-order interactions w.E.t the parameters, i.e. (t.m) Specifically,
oW
AW = AWU + Em Σ n.ENNY
AW(m((i))
where U - v(0) E ieN Mi. And,
OL do(N) aU
AW (i.)) del ((m) (m))) (i,j)
1 Do(N) OU Ow AW del
OW
where R(m)
AL @e(N) Based on the analysis in Section 3.2 the term A AW(m) (i.j) 1) Dv(N) (i)))
R(m) ar(m) oW represents the strength of learning the m-order interactions.
Thus, we aim to study the strength AW(m) (i.j) of learning the m-order interaction in Theorem 1.
Proof skeleton in Theorem 1. To theoretically explain the representation bottleneck, we prove that the strength of learning middle-order interactions (i.e., (i, ss 0.5m) is much smaller than the strength of learning low-order and high-order interactions. It is because that the learning strength of middle-order interactions is average of the learning gradients of Au j. S)s (i.e.,
OW over massive contexts S, which results cancellation of these gradients. In contrast, the learning strength of low-order interactions (high-order interactions) the average of (Ar(i.j.)) oW over a few contexts S, which mitigates the cancellation phenomenon. Thus, DNNs are more likely encode low-order and high-order interactions, but usually fail encode middle-order interactions.
8Av(5.1.S)
Proof of Theorem 1. The m-order interaction (i.j) between variables i. is defined as,
(mm) (i,j) BL Au(i,j
(11)
Σ
SENME Au(i,,,)) T8|mm
(n-2)
We use W [W,, W2,.., WK] E KK to denote the network parameters. Then, based on the Eq.
aT(m) ow
(7(m) AAr(i.j.S)
Σ NALL dAr(i.j.S) aw
AAv(i,
(n-2)
SEN
aw
14

---

Published as a conference paper at ICLR 2022
Assume [Es,,sl (B BW dimension of (Av(i. aw each other, then have
0. Without loss of generality, let o² denote the variance of each Since the gradients [Av(i,5.) on different contexts are independent with aw
I (i,5)
Eill
OW =0,
Om(m) (1.1) = (mmm² vk- I....,K. K.
Var.
Owk
where K is the dimension of network parameters W. at (m)) (i.5)
Furthermore, because Aw(m) =
Do(N
ow then
E, | (A (i, 0,
0L
Var, AW & (f, = (1 de(NN
w /02 4k = 1, K.
where (m)
n-m m 11 and AW (m) (i,j) = -1 De(N) w (m) (l (a.5)
ar
represents the k-tth dimension
Dwk
of (w (i..). Moreover, we can obtain,
K A AW (1,5)² = Σ
B (ll(m) (i,)) = E
E. AW (m)) (i,j)
k=1
(m)) (i.5))) + Var, | (AW(") (i.j))
(12)
(AW, (i.j)
0L n - 1 (1 Ov(N) n(n - /
Therefore, the conclusion of Theorem 1 holds.
B.2 PROOF OF THEOREM 2
Let S2 denote the two variable subsets randomly sampled from the universal set N including all input variables, where |S1] rin, | r2n, and 0 S1 r2 < 1.
When we consider each S₁ as the universal set, according to the efficiency property of the multi- order interaction, we can obtain,
r
Es. [v(S:)] = v0) + Es.
Σ m4] + Es,
Σ
Σ
Tin(rin - 1) (i.
rin 1 m
(m)
S:
iESt
1JE8
m=0
rin-2
= v(( + rinE + Es,
Fin
Σ
S (i.5)
Tin(rin 1)
m=0
ijj
r-n-2 Σ
v00 + (1)
(rin msB., E., 1( (TT)) (i,
where ((m) (i. del Sscgs (Au(,, S')).
Similarly, when consider each S2 as the universal set, we can obtain,
Es, [(a)) v00 + Es.
Σ ni] +
Esg
Σ
Pan - 1 1 m
(m)
(i.))
(2
S2
rESa
m==
T2n-22 2
= =v( + (2nlE -
Σ
(ren- 1 - m)Es,
EE (1 (m))
(i,j))]
m=0
15

---

Published as a conference paper at ICLR 2022
(a)4
ML.P
MLP-5 commercial
MIPP-8
MLP-8 comueeciial
(b)
0.15-
Alechet Tar
DNN high order DNN
Strength
onger DNN
highe DNN
ooder DNN
instability
500
number 6,
Alcolet V121- to CIFAMI1
0,050
0.1m
0.5m
0.1n
0.5m
0.9n
0.1n
0,5g Order
0.90
01025
200
number of
Figure 7: (a) Distributions of the interaction strength ((m) of normal DNNs and high-order DNNs, where high-order DNNs were trained by encouraging high-order interactions and penalizing low- order interactions simultaneously. (b) The instability of J [[m) (x) w.n.t. the sampling number of pairs of variables (i.j) and the sampling number of contexts S.
where I (i,j) (L)Es (Av(i, (A0()) Note that the contexts when computing (mm) 81 (i,5) and (mm)
$2 (i, are different. It is easy to obtain that
Es. [ (1 (i. Es, (4 (mm) (t,5)) = B (1(m)) (i,5)).
When m < Pin < r2n. Therefore, Au(ri, r2) can be rewritten as follows:
Au(ri,72) Biss,ss,nncs,,s,,s.//
72/r1 v(S))
EEs2Es, (v(2) r2/m1 s( [Bs(u((2)) - 12/
=(1 -11-22/1) (0(0) Σ m=o JJEN
Σ
7(m) (i,
(r2/r1 - 1m + 1) 1)],
m S Ti - rin 2 < S r2n -
where (m))
(r2n m 11/mm-1)//m 1 1)), 0,
r2n 2 < m mn5n
Then, the conclusion holds.
C EXPERIMENTAL DETAILS AND MORE RESULTS
C.I IMPLEMENTATION DETAILS
The experiments were conducted on the CIFAR-10, Tiny-ImageNet, ImageNet, and two tabular datasets. Due to the computational cost, selected 50 classes from 200 classes equal intervals (i.e., the 4th, 8th, 196th, 200th classes) when we trained DNNs on the Tiny-ImageNer dataset.
The sampling strategy in the computation of (mm) The interaction strength ((m defined as,
f(m) Eren [ (1 (i,j [=] E, EE [E., [[ (m (1, [II| where 7(m) (i,jlz) Escayba) (v( 181mm
To precisely compute ((m), we need to average all possible contexts $ C N, all pairs of variables i j N, and all samples x Ω which is usually computationally infeasible. Therefore, adopted the sampling strategy used in Zhang et al. 2020) to approximately compute ((m),
The sampling strategy was conducted as follows. With respect to the sampling number of input samples, sampled 50 correctly classified samples image datasets. On the ImageNet and the Tiny-ImageNet dataset, these images were sampled from different 50 classes. On the CIFAR-10 10 dataset, sampled 5 images from each class. Then, for each image, sampled 200 pairs of patches i.j E N. Since DNNs usually encode stronger interactions between neighbor patches, we restricted that patch i should be located at the neighborhood patch j with a radius of two patches. Next, for each pair of patches j. and each order m, we randomly sampled 100 contexts S from all possible contexts, where [S] = m. Besides, we computed 13 different orders for j[m), where 0, 0.05m, 0n1 0.2n, 0.8n, 0.9n, 0.95n, 1.0m. On each tabular dataset, since there are only
16

---

Published as a conference paper at ICLR 2022
VGG 16 on CIFAR 10
VGG-16 16 on Tiny ImgNet
VGG 19 on CIFAR 10
VGG 19 on Tiny ImgNet
Normal DNN
Normal DNN
Normal DNN
Normal DNN
Strength
Low-order DNN
Low-r DNN
Low-order DNN
Low-order DNN
Middie-order DNK
Middlo-order DNK
Middlle-rder DNN
Mide DNN
High-order DNN
Hidr
High-order DNN
Higle DNN
2
0
0.1n
0.5m Order
0.9n
0.1n
0.5n
0.9n
0.1n
0.5n Order
0.9m
0.1n
0.5n
0.9m
Order
Order
Figure 8: Distributions of the interaction strength ((m) of four types of DNNs. The low-order, middle-order, and high-order DNNs trained by following the parameter setting mentioned in Section 3.4 while A2 was set as 0.1 (instead of 1) for low-order DNNs on the Tiny-ImageNe dataset.
Normal DNN CIFAR-10
High-order DNN on CIFAR-10
Normal DNN Tiny ImgNet
Highrorder DNN Tiny IngNeet
random
random
random
random
accuracy
0.75
centrally surnounding
0.75
contnally surruuld--
0.4
centrally surrunddig
0.4
Sontrally-surooummie
0.50
0.50
0.2
0.25
area: small
0.25
large
area: small
area: Jarge
0.1n
0.5m
0,9t
0.1n
0.5n
0.9n
0.0
0.1n
0,50
0,9h
0.0
0.1a
0.5m
Preserving rate
Preserving rate
Preserving rate
Preserving rate
Figure 9: Classification accuracies using AlexNet architecture on images with different numbers of patches being masked.
a few input variables (n1 12 on the census dataset and n 10 on the commercial dataset), we sampled 100 instances and all pairs of variables for computation. For each pair of patches and each order m, we randomly sampled 100 contexts S from all possible contexts.
To validate the reliability of the approximated ((m) via the above sampling strategy, we evalu- ated the (in)stability of ([m) during the sampling process. Specifically, we designed an insta- bility metric when ((m) repeatedly computed for times. Firstly, for each input image x, ( (i.j =)]1
we defined Jm (xr) (6.17 The instability w.r.f the ((m)(x) was computed as
Eu.araatt (x) (x)) where f((m) JT) ((r)((r)) denote the estimated ((m)(x) at the u-th sam-
Eu "_
pling time and at the w-th sampling time, respectively. Then, the instability of ((m) was computed as follows.
instability
E. 1
The instability is average over all sampled images and all sampled orders.
Based on the above definition, we used the trained AlexNet on the Iny-ImmteNet dataset and VGG- 16 the CIFAR-10 dataset to compute the above instability. We conducted two experiments to evaluate the instability of ((m) w.r// the sampling of the contexts S and the sampling of pairs (i, respectively. In the first experiment, we fixed 100 pairs of (i,j) and evaluated the instability of ((m) w.n the sampling of the contexts S. Figure b)) shows that on the two datasets, when the sampling number of S increased, the instability decreased. Furthermore, when the sampling number of S was greater than 100 (i.e. our setting), the instability value was less than 0.05, which indicated a stable approximation. In the second experiment, of (i. where the sampling number of was set to 100 as above-mentionns when the sampling number of (i,j) pairs increased, the instability decreased. When the sampling number of (i,j) pairs was greater than 200 (i.e., our setting), the instability was less than 0. which indicated a stable approximation of (m). These results demonstrated that the adopted sampling strategy could well approximate the interaction strength ((m)
evaluated the instability W.Et the sampling processes
As Figure ( shows,
Implementation details of adversarial attacks. Here, introduce how to measure the adversarial
robustness in Section 3.4 We adopted the untargeted PGD attack Madry et al.) (018)) with the Los constraint || ||rl| olc to generate adversarial examples. For the census dataset, set 0.6 and
17

---

Published as a conference paper at ICLR 2022
90%
80%
70%
60%
50%
40%
90%
80%
70%
60%
50%
40%
masked
Figure 10:
Images generated by random masking (left) and randomly masking (right).
Normal DNN on CIFAR-10
High-order DNN on CIFAR-10
Normal DNN on Tiny ImageNetTligh onder DNN on Tiny ImageNett
nandom
random
random
random
accuracy
0.75
randomly durrounding
0.75
randomls Surrounding
randomly-surroennll surroinding
0.4
0.4
0.50
0.50
0.2
0.2
0.25
area: small
0.25
large
arca: small
Jare
0.0
0.0
0.5n
0.9n
0.1n
0.5n
0.9n
0.1n
0.5n
0,9n
Preserving rale
Preserving rale
Preserving rate
Preserving rate
Figure 11: Classification accuracies using VGG-16 architecture on images with different numbers of patches being masked (by random masking and mandomly-surroundee masking).
the attack was conducted with 100 steps. For the commercial dataset, we set = 0.2 and the attack was conducted with 50 steps. The step size was to 0.01 for all attacks.
C.2 MORE EXPERIMENTAL RESULTS.
In this subsection, provide more experimental results besides the results in the main paper.
C.2.1 MORE EXPERIMENTS ON THE EFFECTIVENESS OF LOSSES
Except for the AlexNet architecture, also used the proposed losses train four types of DNNs of 16 and VGG-19 architectures, i.e., normally trained DNNs, low-order DNNs, middle-order DNNs, and high-order DNNs, on the CIFAR-10 dataset and the Tiny-ImageNet dataset. The pa- rameters were set as the same in Section 3.4 Note that when F1 O. we set Au(r1, r2) Es, [Sx)] v()) Experimental results Figure 8 demonstrated that the four types of DNNs usually could successfully learn interactions as expected, which further validated the effectiveness of the proposed losses.
C.2.2 MORE EXPERIMENTS ON STRUCTURAL REPRESENTATION
Verify structural representations on more DNNs. Figure 9 shows classification accuracies using AlexNet network on images with different numbers of patches being masked. These results further validated that high-order DNNs were more sensitive to the destruction of structural information.
More masking methods to verify structural representations. Besides, designed new mask- ing method to further investigate a DNN's capacity of encoding structural information. Specifically, masked patches in each image and only preserved single large region of m patches, as shown in Figure IO The position of the preserved region was randomly determined, instead of being fixed in the center of the image previously. We called the new masking method as randomly- surrounding masking method. By doing so, the structural information within the large region was maintained.
Figures and 12 show experimental results. In each sub-figure, the x-axis represents the ratio of preserved patches, and the y-axis represents the classification accuracy when only the masked images were fed input. In addition, the blue curve denotes the accuracy curve on the samples generated by the random masking method, and the orange curve shows the accuracy on the samples generated by the orange curve measures the sensitivity of the DNN to the structural destruction.
masking method. The area between the blue curve and the
Based on the accuracy on masked samples in Figures II and 12 we found that the aforementioned area of the high-order DNN was much larger than the area of the normally trained DNN. The exper- imental results verified that high-order DNNs encoded more structural information than normally trained DNNs. Such results were also consistent with results obtained in our previous experiments in Figures and
18

---

Published as a conference paper at ICLR 2022
CIFAR-
High-arder on CIFAR-10
Tiny ImageNet High-arder DNN Tiny ImageNet
mundom
random
random
random
accuracy
Fandomlysse wurooundii
0.75
random suroundding
randomly-suroummien
randomll-- surtonncing
0.4
0.50
0.50
0.2
0.2
area: small
0.25
area large
arca: small
area:
Large
0.0
0.1n
0.5a
0.9n
0.1n
0.5m
0.9n
0.1m
0.5a
0.9h
0.
0.5n
0.9n
Preserving rute
Prescrving rate
Preserving rate
Preserving
Figure 12: Classification accuracies using AlexNet architecture on images with different numbers of patches being masked (by random masking and randomiy-surroundinng masking).
Low-order DNN CIFAR-10
Middle-arder CIFAR-IO
High-order DNN CIFAR-10
Normal DNN CIFAR-1O
accuracy
random
random
random
random
0.75
contaally surroundgg
0.75
centrally surrrouuddii
0.75
-ontally-surroummdee
0.75
centrally-smroonding
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0,25
0.In
0.5a
0.9n
0.In
0.5n
0.9n
0.1n
0.5n
0.9n
0.5n
0.9a
Preserving rate
Preserving rate
Preserving rate
Preserving rate
Low-order DNN Tiny ImgNet Middle-order DNN Tiny ImgNet High-order Tiny ImeNet
Narmal DNN Tiny Neg
random
random
accuracy
0.4
0.4
centralyy surrounding
0.4
centrally Byy.lyysuuuu sumounding
0.4
centrally sumoundinng
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.1n
0.5n
0.9n
0.5n
0.9n
0.1n
0.1m
0.5n
0.9n
Preserving rate
Preserving rate
Preserving rate
Preserving rate
Figure 13: Classification accuracies of low-order DNNs, middle-order DNNs, high-order DNNs, and normally trained DNNs (using VGG16) on images with different numbers of patches being masked. Here, we used the random masking method and the centrally-surroundiing masking method. The blue color indicated that the random masking method had lower accuracy, while the red color indicated that the random masking method had higher accuracy. The phenomenon that the random masking method had higher accuracy may be because the random masking method preserved more abundant local information in generated images, while the masking method will make the unmasked regions concentrate together. Considering that adjacent regions often contain similar feature information, the centrally-surrounding masking method will lead to redundancy of information and limit the diversity of information.
Comparisons of structural representations between four types of DNNs. We further compared the capacity of encoding structural representations among four types of DNNs (i.e., normally trained DNNs, low-order DNNs, middle-order DNNs, and high-order DNNs). To this end, we followed the experimental setting in Section 3.4 We trained low-order DNNs by penalizing interactions of the [0. r1-th orders based on L r2, loss, and trained middle-order DNNs by boosting interactions of the [0.3n, 0.7n]]th orders based on I (21,T2) loss.
Figure compares classification accuracies on images generated by the random masking method (which were considered as bag-of-words features without structures) and images generated by the centrally-surrounding masking method (with structural patterns). The large gap between the two classification accuracies indicated that the learned DNN encoded rich structural information for inference. Lee, the larger area between the accuracy curve on images generated by the random masking method and the accuracy curve images generated by the method means the richer structural information in the DNN. In this way, Figure [3 compares the capacity of encoding structural information between four types of VGG-16 networks. Similarly, Figure 14compaaes the capacity of encoding structural information between four types of AlexNets.
masking
To this end, we obtained three conclusions.
(i) Low-order DNNs trained on the CIFAR-10 dataset encoded little structural information, because such DNNs did not exhibit much difference in classification accuracy the above two types of
19

---

Published as a conference paper at ICLR 2022
Low onder DNN on CIFAR-10
Middle-order DNN CIFAR-10
High-arder DNN on CIFAR-10
DNN CIFAR-10
midoen
random
random
accuracy
centeilly By surtounding
0.75
contr -uurrounding
0.75
centally
contally-srrrmmdiin surrounding
0.75
centrally surroundding
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.1n
0.5n
0.5n
0,9n
0.5n Preserving rale
0.10
0.5n
0.9n
Preserving rate
Preserving rate
Preserving rate
Low-order DNN Thy ImaNet Middis-order DNN Tiny Imneeet
Higb-order on Tiny Img
Nornal DNN Tiny ImgNet
accuracy
0.6
random
mindom
random
random
0.4
centrall yy strroundinn
0.4
centrall Saroundingg
0.4
0.4
centrally supounding
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.1n
0.5m 0.9n
0.1n
0.5n 0.9n
0.1n
0.5n
0.9m
0.1m
0.5m
0.9n
Preserving rate
Preserving rate
Preserving rate
Preserving rate
Figure 14: Classification accuracies of low-order DNNs, middle-order DNNs, high-order DNNs, and normally trained DNNs (using AlexNet) on images with different numbers of patches being masked. Here, used the random masking method and the centrally-surrrunddin masking method. The blue color indicated that the random masking method had a lower accuracy, while the red color indicated that the random masking method had higher accuracy. The phenomenon that the random masking method had higher accuracy may be because the random masking method preserved more abundant local information in generated images, while the centrally-surrounddie masking method will make the unmasked regions concentrate together. Considering that adjacent regions often contain similar feature information, the centrally- satirrall--urrrunding masking method will lead to redundancy of information and limit the diversity of information.
(m)
adv
ResNet18 on ImgNet
R8 on Tiny ImgNet
VGG16 on ImgNet
VGG16 Tiny Img
Averuee ((m)
0.02
0.050
0.01
0.025
0.00
0.025
0.00
0.000
-0.02
0.000
0.1n 0.3n 0.5n 0.7n 0.9n order
-0.01
0.1n
0.3n 0.5n 0.7a 0.9n order
0.In 0.3n
0.5n order
0.7n 0.9m
-0.025
0. 0.3n 0.5n 0.7n 0.9n order
Figure 15: The multi-order interaction I (m) normal samples and I ((m) adversarial samples for normally trained DNNs. Adversarial perturbations mainly affected high-order interactions.
samples. Furthermore, for low-order DNNs trained on the Tmny-ImageNet dataset, the accuracies on images generated by the random masking method were even higher than the accuracies on images generated by the surroully masking method. This may be because the random mask- ing method preserved more abundant local information in generated images, while the centrally- surrounding masking method will make the unmasked regions concentrate together. Considering that adjacent regions often contain similar feature information, the eenrraly-surrrunddii masking method will lead to redundancy of information and limit the diversity of information. This result further verified that low-order DNNs preferred bag-of-words representations, but failed to encode structural information.
(ii) High-order DNNs showed the highest accuracy difference between the above two types of sam- ples, which indicated that high-order DNNs encoded most structural information.
(iii) The capacity of Middle-order DNNs to encode structural information was somewhere in be- tween low-order DNNs and high-order DNNs. It indicated that middle-order DNNs encoded more structural information than low-order DNNs, but middle-order DNNs encoded less structural infor- mation than high-order DNNs.
Experimental results demonstrated that it was the high-order interaction that was mainly responsible for encoding structural information.
20

---

Published as a conference paper at ICLR 2022
Penalizing [0, 0,5m]
Penalizing [0.7n.
L'00.03)&
nummal (0,03)
0.01 A n.1
0.01 As 0.1
L-00.0007 L700.20000 700.0.0)))
A
(1, & (OLO.))
2
0.In 0.3n 0.5n 0.7n 0.9n order
0.30 0.50 0.7n urder
0.1n 0.3n order
0.7n 0.9n
0.1n
0.3n
0.5n 0.7n
0.9h order
(a) Distribution of using multiple L*, L (ri.2))
(b) Effects of Ag
Figure 16: (a) Distributions of the interaction strength ((m) of normally trained DNN and DNNs trained by using multiple L+, L_ and (r1, r2) pairs. (b) Distributions of the interaction strength (mm) of DNNs trained by using different A2s.
L"(0.033 & (0..
normal
L &1,...3) & (07.))
narmal
L (0.3.077) & (...7.
L. (0,05) & 1166, & (M
L (0.3,07) & (07.1)
(0,05) & (OL6,
(0.2.144 (0,6CL))
2
(LA.0))
(0.L5)
2
0.In 0.3n 0.5n 0.7n 0.9n order (a) Distribution of ((m) (census dataset)
0. 0.3n 0.5n 0.7n 0.9n order
0.1n 0.3n 0.5n 0.7n 0.9n order
0n 0.3n 0.5n 0.7n 0.9n order
Distribution of ((m) (commercial dataset)
Figure 17: Distributions of the interaction strength [(m) of normally trained DNN and DNNs trained with - and/or I.- w.r.f. different pairs of (2).)).
C.2.3 MORE EXPERIMENTS ON ADVERSARIAL ROBUSTNESS
Comparisons on adversarial robustness between four types DNNs. We further compared the adversarial robustness between four types of DNNs, including low-order DNNs, middle-order DNNs, high-order DNNs, and normally trained DNNs. To this end, we followed the experimental setting in Section 3.4 Here, the low-order DNNs were trained by encouraging interactions of the [0, 0.5m]]th orders based on L (r1,T2) and simultaneously penalizing interactions of the (0.6n, n]-th orders based on L r2). We set Å 10, A2 10. The middle-order DNNs were trained to encourage interactions
the [0.3n, 0.7n]-th orders based on L (r1, 72). We set λ = 10, A2 O. We used the MLP-5 and MLP-8 networks in Section 3.] Each MLP was trained on the census dataset and commercial dataset, respectively. Adversarial attacks were conducted by following experimental settings in Section 3.4
Table reports the adversarial robustness of four types of DNNs. We obtained following results. (i) Low-order DNNs usually exhibited the highest adversarial robustness, which outperformed nor- mally trained DNNs. (ii) High-order DNNs exhibited the lowest robustness, which was significantly lower than normally trained DNNs. (iii) The robustness of middle-order DNNs was somewhere in between low-order and high-order DNNs. The above results showed a significant connection between adversarial robustness and the orders of the encoded interactions.
More explorations on Adversarial robustness. We further explored the relationship between ad- versarial robustness and the order of interactions. We conducted experiments Ren et al. (202Tb) on images in the ImageNet dataset and the Tiny-ImageNe dataset, in order to explore interactions of which orders were vulnerable to adversarial attacks.
Specifically, let x denote a normal sample, and let x' = denote adversarial sample. Then, according to the efficiency property of ((m))i.)) the significant output change caused by adversar- ial perturbations, v(N[x) u (N[[z', can represented as the sum of differences in multi-order interactions as follows.
v(N[z) - u(V ignorable bias Σm (m)) Σns (m))) (i,
where (i = (T)) (i,jlz) 1 (T) (i.jia') is the compositional adversarial effect on the interaction utility ((m) (i,j]z) |z)) caused by adversarial perturbations. In this way, the overall attacking utility (the output change) can be decomposed into adversarial effects on massive compositional interactions (mm) jlx).
21

---

Published as a conference paper at ICLR 2022
A2 0.1
4
A2
A 0.1
2,
A,
Penalizing 005m. (census)
Penalizing [0, 0.55mm]] (commercial)
Boosting [0.3n, 0.7m] (census) Boosting [0.3n, 0.7n)coomerciia)
1.5
1.0
0.5
0.In 0.7n 0.9n
0.In 0.3n 0.5n 0.7n 0.9n order
0.1n 0.3n 0.7n 0.9n
0.1n 0.5n 0.7n 0.9n
order
order
order
(a) Effects of A2
(b) Effects of
Figure 18: Distributions of the interaction strength J(m) of DNNs trained by using different pairs (A1, A2) the census dataset and the commercial dataset.
Table 2: Comparison the adversarial accuracy between normally trained DNNs, low-order DNNs, middle-order DNNs, and high-order DNNs the census dataset and the commercial dataset.
Normal training
penalize high-order
boost middle-order
Penalize low-order
Model
boost low-order
& boost high-order
MLP-5 on census
38.22
42.40
15.93
7.31
MLP-8 on census
39.33
44.65
18.10
2.02
MLP-5 5-5 on commercial
27.01
29.76
23.70
22.00
MLP-8 commercial
25.92
28.86
22.55
20.58
Therefore, Figure 15 uses the change of multi-order interactions (z as specific reasons for adversarial vulnerability. This figure shows the difference between interactions of normal samples and interactions of adversarial samples. Adversarial perturbations mainly affected high-order in- teractions, and rarely affected low-order interactions. This phenomenon has been showed in some previous studies. The above experiments further verified the connection between adversarial robust- ness and the order of the encoded interactions.
In summary, experimental results showed strong connection between adversarial robustness and the order of the encoded interactions. Nevertheless, the order of interactions does not fully determine the adversarial robustness. For example, previous studies have shown that interactions encoded in adversarially trained DNNs were also more robust to attacks.
C.2.4 MORE EXPERIMENTS ON DIFFERENT IYPER-PARAMETERA
Training DNNs with both L and L- w.r.f. different pairs of (r1, We investigated the performances of DNNs when we simultaneously used multiple L+ and L- with different pairs of (21,12) in the loss function. We used the following five
of experimental settings, in- cluding (i) L (0, 0.3) and L (0.7,1.0); (ii) L (0.3, 0.7) and L (0.7, 1.0); (ii) L (0.2, 0.4) and L L0.6. 0.8): (iv) L (0, 0.5) and L+ (0.6, 1): (v) L (0, 0.5) and L (0.6,, 1) to learn DNNs. DNNs were trained on the CIFAR-10 dataset, the census dataset, and the commercial dataset, respectively.
Figure 16 a) shows that the trained DNNs successfully learned interactions as expected. For ex- ample, the DNN trained with L 0.3) & L (0.7, 1.0) simultaneously boosted both interactions of the [0, 1..3n]ordees and interactions of the [0.7n, n]- -orders. These results further verified the effectiveness of the proposed losses.
Furthermore, DNNs trained with I+ and/or L- w.t.. different pairs of (r1,72) further verified the conclusion obtained in Table [ (left). Le.. although the interactions of different orders performed differently in both adversarial robustness (Table [ (right)) and the capacity of encoding structural information (Figures 6
9 and 14 interactions of different orders had similar classification
curacies (the difference was within = 11% accuracy). showed that although interactions of different orders had their distinctive properties, such difference did not necessarily affect their classification accuracies on normal images.
Effects of hyper-parameters. We further investigated the effects of different hyper-parameters.
First, the effects a single T2) pair have been investigated. Figure (b) and Figure (c) show that using the L (ri,r2)/E (r1, loss boosted/penalized interactions of the [r,n, ram -th orders.
Second, in spite of that, we conducted new experiments to further investigate the effects of multiple (21,2) pairs. We used the following five sets of experimental settings, including (i) T.+ 0.3)
22

---

Published as a conference paper at ICLR 2022
Table 3: Comparison of the running time between normally training DNNs by 200 epochs and training DNNs by 200 epochs with the proposed losses.
CIFAR-I0
Viny--maaeNet
Model
AlexNet
VGGI6
AlexNet
VGGI6
Normally training DNNs
0..66
0.83
0.89 h
9,25
Training using L (21,
1.36
2.35
1.87
27.28 h
Training using L (21,
1.27
2.12
1.82 h
26.68 h
VGG-16 CIFAR-10
VGG-16 Tiny ImgNet
AlexNet CIFAR-10
AlexNet Tiny ImgNet
train loss
2
Normal
Normal
Normal using I.
Normal
using I."
2.5
using I."
2.5
using I.*
using L
using L
using L."
using L
0
0.0
0.0
100
200
100
200
100 epoch
200
0
100
200
epoch
epoch
epoch
Figure 19: Curves of classification loss LosSclassificatinn W.K.f training epochs for normally training DNNs and training DNNs with the proposed losses.
and L (0.7,, (ii) L (0.3000.7 and L+ (0.77 (iii) L+ and (0.6, 0.8); (iv) L (0,0,..5 and L (0.6. 1); (v) (0, (0, 0.5) and L (0.6. 1). We used these parameters train DNNs on the CIFAR-10 10 dataset. Figure [6(a) a) shows that L (r1, r2) and L (r(,rz) loss simultaneously boosted interactions of the 1m,,722) -th orders and the [r ('n,rkmn r'sn]-th orders. For example, by ing I,+ (0. 0.3) and I,+ (0.7, 1.0), the trained DNN simultaneously boosted both interactions of the [0, 0.3n|-th orders and interactions of the [0.7n, n1-thh orders.
In addition, we conducted experiments on two tabular datasets, i.e., the census dataset and the com- mercial dataset. We extended above five different experimental settings (w.r. Ti and r2) for image data to the training of DNNs in tabular data. Thus, we trained five MLP-5 networks on each tabular dataset following each experimental setting. The architecture of the MLP-5 has been introduced in Section 3.1 Figure 17 shows that we could use L (T1, and L (r1, r() loss to simultancously boost interactions of the [rin, r2n]-th orders and interactions of the [r(n, r2n] n1]-th orders.
Third, we conducted new experiments to investigate the effects of the parameter X. Specifically, 0,1, 5 study the effects of X2. We trained DNNS on the Tiny-ImageNer dataset. First, we trained high-order DNNs by penalizing interactions of the [0, 0.5n|]-t orders. Figure 16(b) shows that the interaction strength of the [0, 0.5m]]-th orders decreased as A increased. The results indicated that the larger d2 value penalized interactions of the [0, 0.5n]-th orders more significantly. Second, we trained low-order DNNs by penalizing interactions of the [0.7n, r2]-th orders. Similarly, found that the strength of these high-order interactions also decreased as X2 increased. This further indicated that the larger X2 value penalized the high-order interactions more significantly. We also conducted experiments on the census dataset and the commercial dataset. Specifically, we fixed A = O, and adjusted X₂ 0.1, 1, 10. We trained high-order DNNs by penalizing interactions of the [0, 0.5m]]th -th orders. Here, we used the MLP-5 networks mentioned in Section 3.] Figure [8(a) also shows the same pattern that the larger X2 value penalized interactions of the [0, 0.5n] -th orders more significantly. These results showed that the parameter X2 controlled the strength of penalization.
we fixed A O, and adjusted \₂
Furthermore, we investigated the effects of λ₁ on two tabular datasets. Specifically, we fixed X = O, and adjusted X = 0.1, 1, 10 to study the effects of d1 We trained middle-order DNNs by boosting interactions of the [0.3n, 0.7n] orders. Here, we used the MLP-5 networks mentioned in Section Figure 18 b) shows that the parameter X₁ controlled the strength of boosting interactions.
3.1
C.2.5
TIME COMPLEXITY ANALYSIS.
We compared the running time between training DNNs by 200 epochs using the proposed losses and normally training DNNs by 200 epochs. We trained these models with a mini-batch size of 128 on single NVIDIA GeForce RTX 3090 GPU and used 4 subprocesses in data loading. Table T showss that the time cost of training DNNs with the proposed losses was about three times as much as the time cost of normally training DNNs, which was acceptable in real applications.
23

---

Published as a conference paper at ICLR 2022
AlexNet
VGG-16
ResNet-
ResNet-50/56
MLP on tabular
Strengtt
5.0
Tiny ImageNet
ImageNet
5.0
Tiny lengeNett
ImageNet
5.0
Tiny ImageNet
ImageNet
5.0
Tiny ImageNa
ImageNet
1.5
MLP-5
MLP-5
CIFAR-10
CIFAR-10
CIFAR-10
CIFAR-10
2.5
2.5
1.0
0.0
0.5n order
0.9G
0.0
0.1m
0.1m
0.5n order
0.9n
0.0
0.3n
0.5n
0.9n
0.1n
0.5n
0.9h
order
order
order
Figure 20: The distributions of interaction strength (im) of different DNNs using new metric. These DNNs were trained on various image datasets and tabular datasets.
Table 4: Mean values and standard deviations (μ+ = of the projections at the first five principal directions of the gradient(at initialization), which were computed under different sizes contexts.
- 0.05n
- 0.5m
S] 0.95n
The first direction The second direction
0.0024+0.1000
0.0025+0.1740
0.0103+0.2277
0.0089+0.0880
0.0003++.1134
0.0076++0.1906
The third direction The fourth direction The fifth direction
0.0005510.0855
-0.0012:10.135
0.013910.1819
0.0029-10.8002
-0.0012:10.12
-0.0010=0.1543
0.0000:10.0766
0.0005++0.1161
0.0022+t0.1533
In fact, a more reasonable experiment should compare the time of training the DNN convergence, f.e. the time cost of training a DNN with a certain decrease of the classification loss. To this end, we plotted curves of the classification losses w.r.t. training epochs of normally trained DNNs and DNNS trained with the proposed (ri, r2) and L- (r1, r2) losses, respectively. Figure 19 shows that the three types of DNNs all achieved convergence the 200-th epoch, which validated the reliability of the above comparison on the time cost.
C.2.6 OTHER VALIDATION EXPERIMENTS
Using new metric to validate bottleneck. Besides, to further remove effects of magnitudes of on different samples for fair comparison, we adopted the following new metric.
(1 (i. [())) jim) Eren Em [E., [[ (i. [|)]
(13)
where f2 denotes the set of all samples. We found that using the metric resulted in few changes to the distribution of the interaction strength. Figure 20 shows a similar representation bottleneck phenomenon when we used the new metric, iee,, the middle-order interaction less likely to be encoded in DNNs.
Validation of zero-mean assumption in Theorem We further verified the reliability of the zero-
mean assumption in Theorem 1. To this end, we analyzed the mean value E.j,s Dw gradient w.r.t. the parameter W at the first convolutional layer when we trained ResNet-18 on the Tiny-ImageNet dataset.
(B.((1.).S) of the
Since the above gradient (An(i.j.)) is nigh-dimensional vector, it is difficult to visualize the ex- DW
pectation all dimensions. Alternatively, we inferred and analyzed the projections on the first five principal directions of the gradient. Then, the validation was simplified as analyzing the mean value and standard deviation of each projection.
Specifically, we computed five principal directions as 01, ....... Os. We examined the mean value and the standard deviation of the gradient strength projected on each direction o; over gradients w.r.t different triplets (i, S) computed on 10 different samples. Given each input sample, we computed gradients @dvlk,,S) for 10 pairs of (i,j) and 1000 contexts
BW
The examination was conducted when |S| = 0.05m, |S| 0.5n, and S = 0.95n. Tables 4 and [] report the above mean values and standard deviations for the network at initialization and the network trained for 40 epochs, respectively. Tables 4 and 5 show that these mean values were almost O, which validated the zero-mean assumption in Theorem 1.
In addition, for simplicity, we used o² to denote the variance of the gradient aهز( in Theo- rem 1, without distinguishing different sizes of contexts S. Tables 4 and 5 show that there existed
24

---

Published as a conference paper at ICLR 2022
Table 5: Mean values and standard deviations (μr + of the projections at the first five principal directions of the gradient (at 40 epochs), which were computed under different sizes of contexts S.
| = 0.05n
5 0.5n
=1=0095m
The first direction The second direction
-0.0015::::037
0.0003+:0.865
0.0423
-0.0209:10.3042
0.0042:10.5653
0.0802-0.9754
The third direction The fourth direction The fifth direction
-0.0284:0.2817
0.0070=0.5164
0.0269=0.7845
0.0208=0.2315
0.0003=0.5057
0.0281=0.7231
-0.0018:+01885
0.0082++04178
-0.0358-+0.6115
small difference between variances of the gradient when considered different sizes of con- texts S. However, such difference negligible the proof and does not affect the conclusion of Theorem This is because the learning strength of the m-th order interaction is proportional to
8-m=1 ("m=.) whose difference between different sizes of contexts much larger than the m)n-1)
above difference in variance.
C.2.7 CLARIFICATION OF THE INSIGHT TABLE
Table 1
compared the classification accuracy (left part) and compared adversarial robustness (right part) between DNNs encoding different orders of interactions.
Table did provide some new insights. By comparing results in Table | (left) with results in Table I (right) and Figures 6 9 13 and [4 found that although the interactions of different orders performed differently in both adversarial robustness (Table (right)) and the capacity of encoding structural information (Figures 9 13 and 14), interactions of different orders had similar clas- sification accuracies. showed that although interactions of different orders had their distinctive properties, such difference did necessarily affect their classification accuracies.
25


Reviews:
[{"review_id": "j28VpljiHhw", "reviewer": "Reviewer_cEoR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The paper is well-written and easy to follow. In particular, Figure 1 and 2 support the concept of representation bottleneck reasonably well.\n- Two questions the authors raise about DNNs are rational, and prove convincingly that this phenomenon is a common problem of DNNs.\n- The idea of describing the representation of the DNN using multi-order interaction utility is good and easy to understand.\n\nWeaknesses\n- The authors propose two losses to encourage/penalize DNNs to learn interactions of specific orders and show the results in Figure 4. This loss can stimulate interactions of specific orders well. High-order DNN seems to have been fully explained and experimented, but not on middle-order and low-order interaction. I wonder why the authors didn't explain it in detail.\n- The authors conduct several experiments, but these show similar results, making it difficult to gain new insights. And it is difficult to understand what Table 1 means and shows. \n- Although this paper shows good enough insight to others, it would be good to present directions for solving the problem of representation bottleneck or providing a clear problem definition for future works.\n- I know it’s due to the limitations of the amount, but putting too many formulas and terms into the sentence. Instead of including all the formulas in the sentence, it would be better to reorganize it and make it easier to legible.\n", "summary_of_the_paper": "This paper discovers and theoretically proves the representation bottleneck phenomenon that indicates cognition gap between DNNs and humans. This paper proposes losses to encourage or penalize the DNN to control interactions of specific complexities, and analyze the representation capacities of interactions.", "summary_of_the_review": "This paper introduces and proves the representation bottleneck, which is a common  phenomenon in the DNNs. This is well-written and easy to understand. There seems to be some shortcomings in the experiments and conclusion, but the paper provides good insights to others.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_rguPHDyAWh", "reviewer": "Reviewer_FMrV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1) The novelty of the paper lies in using the multi-order interaction proposed in Zhang et al. (2020) to understand the complexity of interactions in DNNs. \n\n2) The major strength of the paper lies in the extensive study of different neural networks and datasets to back the claim. Also, the effect of the proposed loss functions $L^{+}$ and $L^{-}$ on deeper networks like AlexNet, VGG-16, and ResNet-18/20 is quite interesting.\n\n\nSuggestions:\n\n1) The number of sets $S$ s.t. $|S| = m$ is given by $n \\choose m$. This function increases from $m = 1 \\ldots \\frac{n}{2}$ and decreases thereafter till $n$. Thus, for achieving large $I^{(m)}(i, j)$ at $m = \\frac{n}{2}$, the model needs to capture dependence between the variables $i$ and $j$ for significantly higher number of contexts, compared to the cases when $m=3$ (local context) or $m=n-2$ (global context). One may not need the dependence to be large for all possible contexts in the intermediate context length case.  Hence, can the authors give an example to explain why the increasing number of contexts in the intermediate contextual interactions doesn't necessarily lead to a small $I^{(m)}(i, j)$ always?\n\n2) Since, the authors consider $v(S|x) = \\log \\frac{1 - \\Pr[\\hat{y} = y^{\\star}]}{  \\Pr[\\hat{y} = y^{\\star} }$ for computing $J^{(m)}$ (which depends on the probability scores of a data example), I believe the magnitudes of $v(S|x)$ aren't necessarily comparable for different examples. Then, isn't the following definition of $J^{(m)}$ a proper relative interaction strength to measure?\n\\begin{equation*}\n    J^{(m)} = \\mathbb{E}_{x \\in \\Omega} \\frac{ \\mathbb{ E }   I^{(m)} (i, j \\mid x)   }{\\mathbb{E_k } \\mathbb{E} |I^{(k)} (i, j | x) | \n }\n\\end{equation*}\n\nThe above interaction measure measures the strength of the contextual utility for each example.\n\n3) In the adversarial robustness experiments, are the low-order and intermediate-order interactions more robust to adversarial attacks? It will be great to have some experiments for intermediate-order interactions, to possibly showcase the fact that neural networks are susceptible to adversarial attacks because of the cognition gap.\n\n\n\n\n", "summary_of_the_paper": "The authors study the complexity of interactions between input variables in deep neural networks (DNNs). They use a multi-order interaction utility between pairs of variables to represent the interaction complexity between input variables encoded in DNNs. The results can be summarized as follows:\n\n1) DNNs are more likely to encode simple and complex interactions between pairs of input variables but aren't good enough to encode the intermediate ones. The authors define the simplicity of interaction depending on its contextual complexity.\n\n2) The authors develop novel loss functions to encourage/penalize the interactions of specific complexities and then, investigate the representation capacities of the learned DNNs.\n\n", "summary_of_the_review": "Overall, the paper makes an important evaluation study to further the understanding of the representation capacity of DNNs. The novelty is in using the multi-order interaction proposed in Zhang et al. (2020) to understand the complexity of interactions in DNNs and the proposal of different loss functions to encode/penalize interactions of specific complexities. Hence, I am leaning towards a positive score for the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HqohfM5Gq3Y", "reviewer": "Reviewer_t6sY", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strength]\n1. This paper discovers a very interesting tendency (called representation bottleneck) in existing DNNs, i.e., a DNN is usually more likely to encode low-order and high-order interactions, but difficult to encode middle-order interactions. $\\\\\\\\$\n2. This paper analyzes theoretically the reason behind the bottleneck. Moreover, the simulated results based on Theorem 1 well match the real cases, which validates the theoretical reason. $\\\\\\\\$\n3. From the perspective of the bottleneck, the authors explore the difference between DNN learning and human learning, which provides the key idea of the proposed two losses. $\\\\\\\\$\n4. To relieve the bottleneck phenomenon, the authors propose two novel losses to enable DNNs to learn interactions of any specific orders. $\\\\\\\\$\n5. Experimental results demonstrate the effectiveness of the two losses, and show that middle-order interactions can provide useful information for classification. $\\\\\\\\$\n\n[Weakness]\n1. The explanation for the representation bottleneck is not intuitive enough.  $\\\\\\\\$\n2. There is a lack of discussion why the trained DNNs do not achieve a significant improvement than a normally trained DNN.$\\\\\\\\$\n3. The experiments on adversarial robustness can not well support the conclusions, since they were only conducted on tabular datasets. $\\\\\\\\$\n\n[Suggestions]\n1. I would suggest the authors give an additional illustration of the intuition behind the proof for the bottleneck. $\\\\\\\\$\n2. It’s expected to give guidance on how we can use the two losses to boost the classification performance. $\\\\\\\\$\n3. It’s not clear why the output change in Eq.(5) can represent interactions of specific orders. $\\\\\\\\$\n4. The authors are suggested to report results in terms of adversarial accuracy on more datasets such as image data.  $\\\\\\\\$\n5. The authors are suggested to clarify whether the proposed two losses will increase the time complexity.  $\\\\\\\\$\n\n***\nAfter carefully reading the response, other reviews, and the revised version of the manuscript. \n\n1. The added proof skeleton makes the theory more clear and intuitive. \n2. New experimental results show a strong connection between representation capacity and interaction orders, which may inspire follow-up studies. \n\nOverall, I think this work is insightful and may make a great impact on both training and explaining of deep neural networks. I have modified the score accordingly.\n\n\n\n", "summary_of_the_paper": "This paper studies the representation ability of DNNs from the perspective of interactions (the multi-order interaction). The authors discovered an interesting representation bottleneck phenomenon, i.e., in a normally trained DNN, low-order and high-order interaction patterns are easy to be learned, while middle-order interaction patterns are difficult to be learned. Moreover, they give a theoretical explanation that the bottleneck origins from that different interaction patterns have different learning strengths (gradients). To relieve the bottleneck problem, the authors propose two novel loss functions, which allow the model to encode interactions of specific orders, including middle-order interactions. The experiments have validated the effectiveness of the proposed losses. Finally, the authors explored some properties of DNNs encoding different-order interactions. ", "summary_of_the_review": "This paper discovers and theoretically explains an interesting representation bottleneck in existing DNNs, and relieves the bottleneck by proposing two novel losses. As the discovered bottleneck reflects the common difficulty to learn middle-order interactions, this work may provide a new direction to train DNNs. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8ORNWrOr664", "reviewer": "Reviewer_4jZH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The research topic of this paper is significant in understanding the representation power of deep neural networks, and is interesting to the entire community of deep learning. The writing of this paper is clear enough, and the main contents are easy to follow.\n\nStrengths:\n- The definition of the relative interaction strength is elegant.\n- The theoretical and numerical analysis in Section 3.2 is novel and interesting. \n- The loss functions to encourage or penalize interactions of certain orders are also novel and very natural.\n- There are experiments showing the effects of these loss functions and connecting them to properties such as accuracy and robustness.\n\nHowever, there are several concerns of this paper. The following are about theory.\n- Regarding Thm 1, how reasonable is the assumption that $\\frac{\\partial}{\\partial W} \\Delta v(i,j,S)$ is a Gaussian? At least some numerical validations should be made here. \n- Regarding the simulation in Fig 3, there is still a tiny gap between the blue and orange curves, which does not look like a random pattern. Can you explain where this gap comes from? \n- Regarding equation 5, there are two issues. First, it is confusing to reload the notation $\\Delta v$. I would recommend using another symbol. Second, are you missing an expectation in this equation?\n- In equation 7, it is clearer to write $L^+(r_1,r_2)$ rather than $L^+$. Simimlar in equation 8. \n- Regarding equation 9 and simulations in Fig 4, it is possible to use multiple $L^+$ or $L^-$ with different $(r_1,r_2)$ pairs? If so, why are you not using it? I feel this can provide more flexibility and is therefore potentially more useful. \n\nThere are also concerns regarding experiments. In summary, the experiments are not extensive and cannot well support the findings.\n- Regarding accuracy, what can we read from Table 1 (left)? The numbers seem random.\n- Regarding structural representations, Fig 5 & 6 make some sense, but what about other masking methods? \n- Regarding robustness, Table 1 (right) tells us that penalizing low-order and boosting high-order interactions harm robustness. What about doing the opposite, i.e. penalizing high-order and boosting low-order interactions? Does it improve robustness?\n- In general, the experiments are not extensive. In order to better understand the effects of the proposed loss functions, there should be experiments carefully adjusting the $\\lambda$'s and $(r_1,r_2)$'s so that we can extract general patterns of the effects. \n- In addition, I do not see any significant improvement by using the proposed loss functions. Are there scenarios where using the proposed loss functions outperforms standard training in any of the metric (accuracy, robustness)? \n- Finally, figures and tables are a bit small so hard to read. \n\nScores can be modified based on authors' feedback and additional experiments. \n\n----------------------\nAfter rebuttal: I have carefully read the response and added experiments.\n\n- The revised theory with milder assumption is great.\n- The additional experiments are excellent and provide a much more complete picture of the proposed theory. \n\nI have modified the score accordingly. ", "summary_of_the_paper": "The paper looks at representation bottleneck of deep neural networks, from the multi-order interaction (within subsets of pixels) point of view. Specifically, the paper provides a novel definition on the relative interaction strength, and then analyzes this quantity both theoretically and numerically. The paper next proposes two loss functions that encourage or penalyze interactions of certain orders, and conducts multiple experiments on different combinations of these loss functions. ", "summary_of_the_review": "Theory is excellent but there is space for improvement in the experiments. \n\n----------------------\nAfter rebuttal: experiments are extensive and insightful enough. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes an important evaluation study to further the understanding of the representation capacity of DNNs. The novelty is in using the multi-order interaction proposed in Zhang et al. (2020) to understand the complexity of interactions in DNNs. The authors discovered an interesting representation bottleneck phenomenon, i.e., in a normally trained DNN, low-order and high-order interaction patterns are easy to be learned, while middle-order interaction patterns are difficult to be learned. They also propose two novel loss functions, which allow the model to encode interactions of specific orders, including middle-order interaction. All reviews are positive.
Decision: Accept (Oral)