Year: 2021

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 interactions 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 human beings, and we call it a representation bottleneck. We theoretically prove the underlying reason for the representation bottleneck. Furthermore, we propose a loss to encourage/penalize the learning of interactions of specific complexities, and analyze the representation capacities of interactions of different complexities.

heading: 1 INTRODUCTION
text: The revolution from shallow to deep models is a crucial step in the development of artificial intelligence. Deep neural networks (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; Montú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, our research first investigates the bottleneck of knowledge representation, i.e., which types of knowledge points (e.g., certain visual concepts) are likely to be encoded by a DNN, and which types of knowledge points are difficult to be learned. To this end, we discover that the interaction between input variables is an effective tool to analyze the knowledge representation. It is because the DNN does not consider input variables working independently, but it encodes the interaction between input variables to form an interaction pattern for inference. For example, the inference of a face image can be explained as the interaction between left and right eyes, the interaction between nose and mouth, and etc.
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 interactions, instead of encoding interactions of intermediate complexity. This also indicates a dramatic difference from human cognition.
The interaction can be understood as follows. Let us take the face recognition task for example. Let φi=mouth measure the numerical importance of the mouth region i to the classification score. Then, the interaction utility between the mouth region i 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 φi=mouth by 0.1, then, we consider 0.1 as the utility of the interaction between i and j.
Multi-order interactions. In order to represent the interaction complexity mentioned in the representation bottleneck, we use the multi-order interaction utility between variables i, j proposed by Zhang et al. (2020). The interaction of the m-th order I(m)(i, j) measures the average interaction utility between variables i, j on all contexts consisting of m variables. In this way, the order m
� �� � �
(a) Interaction pattern (b) Representation bottleneck(c) Whether humans/DNNs extract new information from patches.
much new information little new information little new information much new information much new information little new information
5% 10% 30% 70% 90% 95% patches
In te
ra ct
io n
st re
ng th
Figure 1: (a) Five pixels (g, h, i, j, k) interact with each other, forming an edge pattern for classification. (b) Representation bottleneck. A DNN is likely to encode low-order and high-order interactions, 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), the information is already redundant for human cognition. Then, people learn little new information from the additional 5% patches. In comparison, the DNN encodes most interactions when the DNN is given very few patches or most patches.
reflects the contextual complexity of the interaction. A low-order I(m)(i, j) measures the relatively simple collaboration between variables i, j and a few m contextual variables, while a high-order I(m
′)(i, j) corresponds to the complex collaboration between i, j and m′ massive contextual variables, where m′ m. Moreover, we prove that the multi-order interaction is a trustworthy tool to 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 output =∑n−2
m=0 ∑ i,j∈N,i6=j w (m)I(m)(i, j) + ∑
i∈N local utility of i + bias. For example, the inference score of a face can be decomposed into the interaction utility between left and right eyes, between mouth and nose, and etc. Therefore, we can take the utility I(m)(i, 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 interactions enables us to discover a representation bottleneck of DNNs. As Figure 1(b) shows, low-order and high-order interaction utilities I(m)(i, j) usually have high absolute values, while middle-order interaction utilities I(m)(i, j) usually have low absolute values. In other words, a DNN is more likely to encode the interaction between variables i and j, when i, j interact with a few contextual variables. Similarly, it is also easy for the DNN to learn the interaction, when i, j interact with most contextual variables. However, it is difficult for the DNN to learn the interaction, when i, j cooperate with a medium number of contextual variables. The difficulty of learning middle-order interactions reflects a representation bottleneck of DNNs.
Cognitive gap between DNNs and humans. Such a representation bottleneck also indicates a significant gap between the knowledge representation of DNNs and the visual cognition of humans. As Figure 1(c) shows, people usually cannot extract meaningful information from a 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 a 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 knowledge representation in DNNs by learning interactions of specific orders. We propose two losses to encourage/penalize the DNN to make inferences by interactions of specific orders, thereby boosting/preventing the learning of such interactions. Experimental results have validated the effectiveness 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 interactions represent more structural information than the normally trained DNNs. In addition, high-order interactions were vulnerable to adversarial attacks.
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 encourage/penalize 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.

heading: 2 RELATED WORK
text: The representation capacity of DNNs. The evaluation of the representation capacity of DNNs provides a new perspective to explain and analyze DNNs. Pascanu et al. (2013) and Montúfar et al. (2014) used the number of linear response regions in a deep rectifier MLP to evaluate its representation 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 memorization 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 analyze 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 theoretically 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 recent years. Based on the Shapley value (Shapley, 1951), Grabisch & Roubens (1999) proposed the Shapley interaction index to define the interaction in a cooperative game. Lundberg et al. (2018) used the interaction effect to build tree ensemble explanations for the decision of 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 Tsang et al. (2017) interpreted DNNs by detecting statistical interactions between input variables and interactions between network weights respectively. Peebles et al. (2020) and Tsang 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 in the recommendation system. Lengerich et al. (2020) applied the ANOVA technique to model interaction effects and further explored the relationship between dropout and interactions. Zhang et al. (2020) proposed the multi-order interaction, and used it to understand and boost dropout. In this paper, we used the multi-order interaction to study the complexity of interactions encoded in DNNs.

heading: 3 REPRESENTATION BOTTLENECK
text: 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 a set of n variables N = {1, . . . , n} (e.g., an input image with n 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 1(a) shows, pixels i, j ∈ 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 the utility of this pattern as 0.01. Similarly, if the existence of this pattern decreases the network output, we consider this pattern has a negative utility.
Furthermore, the multi-order interaction I(m)(i, j) between two input variables i, j ∈ N , 0 ≤ m ≤ n−2, is proposed to measure interactions of different complexities (Zhang et al., 2020). Specifically, the m-th order interaction I(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 1(a) shows, five pixels (i, j, g, h, k) collaborate with each other and form an edge pattern for classification. Thus, the pair-
wise interaction between pixels i, j also depends on three contextual pixels g, h, k. Mathematically, the multi-order interaction I(m)(i, j) is defined as follows:
I(m)(i, j) = ES⊆N\{i,j},|S|=m[∆v(i, j, S)], (1)
where ∆v(i, j, S) = v(S ∪ {i, j}) − v(S ∪ {i}) − v(S ∪ {j}) + v(S). Here, v(S) is the output score when we keep variables in 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(xS) can be implemented as any scalar output of the DNN (e.g., log P (ŷ=y
truth|xS) 1−P (ŷ=ytruth|xS) of the true category), where we replace the pixel values
inN \S of original input x by the baseline value (the average pixel value over images) to construct a masked image xS . Then, ∆v(i, j, S) = [v(S∪{i, j})−v(S∪{i})]− [v(S∪{j})−v(S)] measures the marginal interaction effects of the collaboration between i, j in a context S.
Generic metric. The proposed multi-order interaction I(m)(i, j) is a generic metric, which has a strong connection with the Shapley value (Shapley, 1951) and the Shapley interaction index (Sundararajan et al., 2020) in game theory. In addition, it has been proven that I(m)(i, j) satisfies the following five desirable properties, i.e., linearity, nullity, commutativity, symmetry, and efficiency properties. The connections with existing metrics and five properties are introduced in Appendix A.

heading: 3.1 REPRESENTATION BOTTLENECK
text: According to the efficiency property of I(m)(i, j), we find that the output of a DNN can be explained as the sum of all interaction utilities of different orders between different pairs of variables.
v(N) = v(∅) + ∑
i∈N µi + ∑ i,j∈N,i 6=j ∑n−2 m=0 w(m)I(m)(i, j) (2)
where µi = v({i}) − v(∅), and w(m) = n−1−mn(n−1) . Because I (m)(i, j) measures the interaction between variables i and j encoded in DNNs with m contextual variables, we can consider the interaction utility I(m)(i, j) as a specific reason for the inference, which makes a compositional contribution w(m)I(m)(i, j) to the output.
In this way, we can categorize all underlying reasons for the network output into different complexities. 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 J (m) of the encoded m-th order interaction as follows:
J(m) = Ex∈Ω[Ei,j [|I(m)(i, j|x)|]]
Em′ [Ex∈Ω[Ei,j [|I(m′)(i, j|x)|]]] (3)
where Ω denotes the set of all samples. J (m) is computed over all pairs of input variables in all samples. J (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: a DNN usually encodes strong low-order and high-order interactions, but encodes weak middle-order interactions. Such a phenomenon is shared by different DNN architectures trained on different datasets, which is illustrated by the J (m) curves in Figure 2. Specifically, when the order m is smaller than 0.1n or greater than 0.9n, its interaction strength J (m) is usually high. In comparison, J (m) is usually low when the order m approximates 0.5n. Moreover, as shown in Figure 3(a), we find that such a phenomenon does not only exists in the well-trained DNNs, but also exists in the entire network 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.1n variables) interact with each other. Similarly, it is also easy for the DNN to encode the complex interaction where massive variables (e.g., more than 0.9n variables) interact with each other. However, it is difficult for the DNN to learn the middle-complex interaction in which a medium number of variables (e.g., about 0.5n variables) participate. Let us take Figure 1(c) for an example. When a DNN is given very few patches sparsely distributed on the horse image,
the DNN can successfully extract the interaction between the few patches. Similarly, when the DNN is given almost all patches of the horse image, 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 collaborations between two patches. In a word, the interaction pattern encoded by the DNN is either too simple or too complex. The difficulty of learning interaction patterns of moderate complexity reflects a common tendency in the feature representation in the DNN.
Such a representation bottleneck also indicates that DNNs and human beings encode different types of visual patterns for inference. As Figure 1(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-ImageNet dataset (Le & Yang, 2015) and the CIFAR-10 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 Resnet-18/20/50/56 (He et al., 2016). Due to the high dimension of input variables (n = 224 × 224 for ImageNet), the computational cost of J (m) is intolerable. To reduce the computational cost, we split the input image into 16 × 16 patches, and considered each patch as an input variable. To compute J (m), we set v(S|x) = log P (ŷ=y
∗|xS) 1−P (ŷ=y∗|xS)
given the masked sample xS , where y∗ was the true label and P (ŷ = y∗|xS) was the probability of classifying the masked sample xS to the true category. In the masked sample xS , 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 J (m) is an average over all possible contexts S, all pairs of variables (i, j), and all samples x, which is computationally infeasible. Therefore, we approximated J (m) 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) (Dua et al., 2017). Each sample in the two datasets contained n = 12 and n = 10 input variables, respectively. We analyzed a 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. For each MLP network, we trained two models for the classification on the two datasets, respectively. In the computation of J (m), P (ŷ = y∗|xS) was also computed by setting the baseline value of a variable to the average value of the variable. Please see Appendix C for details.

heading: 3.2 EXPLAINING THE REPRESENTATION BOTTLENECK
text: In this subsection, we theoretically prove the underlying reason for the representation bottleneck. Let W denote network parameters of a DNN. We focus on the change ∆W of network parameters, which also represents the strength of training the DNN. The change of weights is calculated by ∆W = −η ∂L∂W = −η ∂L ∂v(N) ∂v(N) ∂W . L denotes the loss function, and η is the learning rate. According to Eq. (2), the network output v(N) of the DNN can be decomposed into the sum of multi-order
interactions I(m)(i, j). Therefore, ∆W can be further represented as the sum of gradients ∂I (m)(i,j) ∂W of multi-order interactions.
∆W = −η ∂L ∂v(N) ∂v(N) ∂W = ∆WU + ∑n−2 m=0 ∑ i,j∈N,i 6=j ∆W (m)(i, j), (4)
where U = v(∅) + ∑
i∈N µi. Specifically,
∆WU def = −η ∂L
∂v(N)
∂v(N)
∂U
∂U ∂W , ∆W (m)(i, j) def = R(m)
∂I(m)(i, j)
∂W ,
where R(m) = −η ∂L∂v(N) ∂v(N) ∂I(m)(i,j) . Here, ∆WU represents the component of ∆W w.r.t. ∂U∂W , and
∆W (m)(i, j) represents the component of ∆W w.r.t. ∂I (m)(i,j) ∂W . Therefore, besides ∆WU , we can consider there are additional n(n−1) 2
2 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 ∆W (m)(i, j). In this way, we can consider ∆W (m)(i, j) measures the strength of learning the interaction between variables i and j under contexts of m variables.
Theorem 1. (Proof in Appendix B) Assume Ei,j,S [∂∆v(i,j,S)∂W ] = 0. Let σ 2 denote the variance of ∂∆v(i,j,S) ∂W . Then for ∆W (m)(i, j) = R(m) ∂I (m)(i,j) ∂W , Ei,j [∆W
(m)(i, j)] = 0 and the variance of ∆W (m)(i, j) is (η ∂L∂v(N)w (m))2σ2/ ( n−2 m ) , where w(m) = n−m−1n(n−1) .
Theorem 1 shows that the strength |∆W (m)(i, j)| of learningm-order interactions is proportional to F (m) = w(m)/ √( n−2 m ) = n−m−1 n(n−1) / √( n−2 m ) . Therefore, when the order m is small or large (e.g., m = 0.05n or 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.5n), the training strength of the m-order interaction is much lower. The above analysis explains why it is easy for a DNN to learn low-order and high-order interactions, but difficult for a DNN to learn middle-order interactions.
Simulation of the curve of the interaction strength. We find that the above training strength |∆W (m)(i, j)| can be used to simulate the distribution of interaction strengths J (m) in real applications, which verifies our theory. Based on Theorem 1, the training strength w.r.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 normalize F (m) and J (m) by F̂ (m) = F (m)/F (0) and Ĵ (m) = J (m)/J (0) respectively, such that F̂ (0) = Ĵ (0) = 1. As Figure 3(b) shows, the curves of normalized F̂ (m) can well match the distributions of Ĵ (m) in real applications. 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. Therefore, 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.

heading: 3.3 METHOD TO CONTROL INTERACTIONS OF SPECIFIC ORDERS
text: The representation bottleneck is widely shared by DNNs of different architectures for various tasks, when DNNs are normally trained. In this section, we mainly explore methods, which force the DNN to learn interactions of specific orders. In this way, we can investigate the properties of feature representations of such DNNs.
In order to force the DNN to learn interactions of specific orders, we propose two simple-yet-efficient 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 ∆u(r1, r2) between two subsets of variables S1 and S2:
∆u(r1, r2) = ES1,S2:∅⊆S1(S2⊆N [v(S2)− r2 r1 v(S1)], (5)
where the subsets S1 and S2 are randomly sampled from all input variables N , such that ∅ ⊆ S1 ( S2 ⊆ N , |S1| = r1n, |S2| = r2n, and 0 ≤ r1 < r2 ≤ 1. Theorem 2. (Proof in Appendix B) The output change ∆u(r1, r2) can be decomposed into the sum of multi-order interactions between different pairs of variables.
∆u(r1, r2) = (1− r2 r1
)v(∅) + ∑n−2
m=0 ∑ i,j∈N,i 6=j w̃(m)I(m)(i, j)
where w̃(m) =  ( r2 r1 − 1)(m+ 1)/[n(n− 1)], m ≤ r1n− 2
(r2n−m− 1)/[n(n− 1)], r1n− 2 < m ≤ r2n− 2 0, r2n− 2 < m ≤ n− 2
(6)
Interestingly, as Figure 4(a) shows, we can consider that the output change ∆u(r1, r2) mainly encodes interactions whose orders are in the range of [0, r2n]. The weight coefficient w̃(m) of the m-th order interaction reached a peak at the r1n-th order in ∆u(r1, r2).
Encourage/penalize interactions of specific orders. Based on the above analysis, ∆u(r1, r2) only contains partial interactions of the [0, r2n]-th orders. Hence, we propose two losses based on ∆u(r1, r2), which encourage and penalize the DNN to use interactions of specific orders for inference, respectively. The first loss L+(r1, r2) forces the DNN to mainly use interactions encoded in ∆u(r1, r2) for inference, thereby boosting the learning of these interactions.
L+(r1, r2) = − 1 |Ω| ∑ x∈Ω ∑C c=1 P (y∗ = c|x) logP (ŷ = c|∆uc(r1, r2|x)), (7)
whereL+(r1, r2) is the proposed cross entropy that uses ∆u(r1, r2) for classification. Here, Ω is the training set, and C denotes the number of classes. Given an input image x ∈ Ω, y∗ is the true label, and ŷ denotes the predicted label. Here, ∆uc(r1, r2|x) = vc(S2|x)− r2r1 vc(S1|x) denotes the change of the logits of the category c, where the logit vc(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 P (ŷ = c|∆uc(r1, r2|x)) as the probability of using the C-dimensional vector {∆uc(r1, r2|x)|1 ≤ c ≤ C} to classify the sample to the category c. We input the C-dimensional vector {∆uc(r1, r2|x)|1 ≤ c ≤ C} into the softmax layer to compute the probability.
Besides, the second loss L−(r1, r2) is designed to prevent the DNN from encoding interactions of the [0, r2n]-th orders. Specifically, we maximize the entropy of classification based on ∆u(r1, r2), in order to make ∆u(r1, r2) non-discriminative.
L−(r1, r2) = 1 |Ω| ∑ x∈Ω ∑C c=1 P (ŷ = c|∆uc(r1, r2|x)) logP (ŷ = c|∆uc(r1, r2|x)), (8)
where L−(r1, r2) denotes the minus entropy of the classification probability based on ∆uc(r1, r2).
In this way, we can train a DNN using the following loss,
Loss = Lossclassification + λ1L+(r1, r2) + λ2L−(r1, r2) (9)
where λ1 ≥ 0, λ2 ≥ 0 are two constants to balance the three terms. Effects of the two losses. We find that the loss L−(r1, r2) can successfully penalize interactions of [0, r2n]-th orders. L+(r1, r2) can encourage interactions of the [r1n, r2n]-th orders, instead of encouraging interactions of the [0, r2n]-th orders. Specifically, we conducted the following experiments. We trained AlexNet networks on the Tiny-ImageNet dataset to encourage interactions of specific orders without penalizing any interactions by setting λ1 = 1, λ2 = 0. In experiments, we set [r1 = 0.2, r2 = 0.5], [r1 = 0.3, r2 = 0.7], and [r1 = 0.6, r2 = 0.9] in the L+(r1, r2) loss to learn three AlexNet models, respectively. We also trained AlexNet models to penalize interactions of specific orders by setting λ1 = 0, λ2 = 1. Two DNNs were trained by setting [r1 = 0, r2 = 0.2] and [r1 = 0, r2 = 0.5] in the L−(r1, r2) loss, respectively. Figure 4(b) shows the interaction strength J (m) of these DNNs. When we encouraged the DNN to encode interactions of the [r1n, r2n]-th orders, the interaction strength J (m) of the [r1n, r2n]-th orders significantly increased, compared to the normally trained DNNs. Figure 4(b) also shows that the loss L−(r1, r2) could successfully remove interactions of the [0, r2n]-th orders.

heading: 3.4 INVESTIGATION OF THE REPRESENTATION CAPACITIES
text: In the previous subsection, we introduce 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 to train four types of DNNs. The first 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, n]-th orders by minimizing the L−(r1, r2) loss with λ1 = 0, λ2 = 1, r1 = 0.7, r2 = 1.0. The third DNN was learned to boost interactions of the [0.3n, 0.7n]-th orders by minimizing the L+(r1, r2) loss with λ1 = 1, λ2 = 0, r1 = 0.3, r2 = 0.7. The fourth DNN was trained to penalize interactions of the [0, 0.5n]-th orders by minimizing the L−(r1, r2) loss with λ1 = 0, λ2 = 1, r1 = 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 architectures on the CIFAR-10 and the Tiny-ImageNet dataset.
Figure 4(c) and Figure 7 (in the appendix) show that the trained DNNs successfully learned interactions as expected. In other words, interactions of the [0.7n, n]-th orders were penalized in the low-order DNN. Interactions of the [0.3n, 0.7n]-th orders were boosted in the middle-order DNN. Interactions of the [0, 0.5n]-th orders were penalized in the high-order DNN.
Classification accuracy. Firstly, Table 1 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 it was not necessary for a DNN to encode low-order interactions and high-order interactions to make inferences. Middle-order interactions can also provide discriminative information.
Bag-of-words representations vs. structural representations. Theoretically, high-order interactions 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. Specifically, as Figure 5 shows, in the first experiment, we tested the DNN on images where m 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 6 and 8, 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 centrally-surrounding masking method. The area indicated the sensitivity to the structural destruction. We found that such area of high-order DNNs were 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. (2021) have demonstrated that adversarial attacks mainly affect high-order interactions. Therefore, we conducted experiments to train DNNs mainly encoding highorder 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 set λ1 = 1, λ2 = 1. Specifically, the DNN was trained to encourage interactions of the [0.6n, n]th orders by setting r1 = 0.6, r2 = 1 for L+(r1, r2) and simultaneously penalize interactions of the [0, 0.5n]-th orders by setting r1 = 0, r2 = 0.5 for L−(r1, r2) simultaneously. We used the aforementioned MLP-5 and MLP-8 networks in Section 3.1. Each MLP was trained on the census and commercial dataset, respectively. Figure 9 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 L∞ norm. We set the attack strength = 0.6 with 100 steps for the census dataset, and set = 0.2 with 50 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 1 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.

heading: 4 CONCLUSION
text: 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 adopt the multiorder interaction, and we use the order to represent the complexity of interactions. It is a common phenomenon that a DNN usually encodes very simple interactions and very complex interactions, but rarely learns interactions of intermediate complexity. We have theoretically proved the underlying reason for the representation bottleneck. Furthermore, we propose two losses to learn DNNs which encode interactions of specific complexities. Experimental results have shown that it is not necessary for a DNN to encode or avoid encoding interactions of specific orders, in terms of classification performance. However, high-order interactions usually encode more structural information than low-order interactions, and are usually vulnerable to adversarial attacks.

heading: 5 REPRODUCIBILITY STATEMENT
text: This research discovered and theoretically explained the representation bottleneck phenomenon, based on the multi-order interaction. Appendix A shows the trustworthiness of the multi-order interaction, by introducing its five desirable properities and its connections with existing typical metrics in game theory. Appendix B and Section 3.2 provide proofs for all theoretical results in the paper. Section 3 and Appendix C have discussed all experimental details, including the computation of interaction strength and how to train DNNs by the proposed two losses, which ensure the reproducibility. Furthermore, we will release the code when the paper is accepted.

heading: A THE MULTI-ORDER INTERACTION
text: Zhang et al. (2020) proposed the multi-order interaction between input variables i, j as follows:
I(m)(i, j) = E|S|⊆N\{i,j},|S|=m∆v(i, j, S)
where ∆v(i, j, S)=v(S∪{i, j})−v(S∪{i})−v(S∪{j})+v(S). I(m)(i, j) denotes the interaction between variables i, j ∈ N of them-th order, which measures the average interaction utility between 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 u and v are combined, w(S) = u(S) + v(S), then the multi-order interaction of the combined game equals to the sum of multi-order interactions derived from u and v. I.e., I(m)w (i, j) = I (m) u (i, j) + I (m) v (i, j). •Nullity property. A dummy variable i ∈ N satisfies ∀S ⊆ N \ {i}, v(S ∪ {i}) = v(S) + v({i}). Then, variable i has no interactions with other variables, i.e., ∀m,∀j ∈ N \ {i}, I(m)(i, j) = 0. • Commutativity property. ∀i, j ∈ N, I(m)(i, j) = I(m)(j, i). • Symmetry property. Assume two variables i, j are equivalent in the sense that i, j have same cooperations with other variables, ∀S ⊆ N \{i, j}, v(S∪{i}) = v(S∪{j}). Then, for any variable k ∈ N , I(m)(i, k) = I(m)(j, k). • Efficiency property. The network output of a DNN can be decomposed into the sum of interactions of different orders between different pairs of variables.
v(N)− v(∅) = ∑
i∈N µi + ∑ i,j∈N,i6=j ∑n−2 m=0 w(m)I(m)(i, j).
where µi = v({i})− v(∅) represents the independent effect of variable i, and w(m) = n−1−mn(n−1) .
Connection with Shapley value and Shapley interaction index.
Shapley value. Shapley (1951) proposed the Shapley value to measure the numerical importance of each player to the total reward in a 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). For a given DNN and an input sample with a set of input variablesN = {1, . . . , n}, we use 2N = {S|S ⊆ N} to denote all possible variable subsets of N . Then, the DNN v can be considered as v : 2N → R that calculates the output v(S) of each specific subset S ⊆ N . Each input variable i is regarded as a player, and the network output 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 variables as follows:
φi = ∑
S⊆N\{i}
|S|!(n− |S| − 1)! n! [v(S ∪ {i})− v(S)]
where v(S) denotes the network output when we keep variables in S unchanged while mask variables in N \ S by following the setting in Ancona et al. (2019). It has been proven that the Shapely value is an unique method to fairly allocate overall reward to each player that satisfies linearity, nullity, symmetry, and efficiency properties.
Connections between the Shapley interaction index and the Shapely value. Input variables of a DNN usually interact with each other, instead of working individually. Based on the Shapley value, Grabisch & Roubens (1999) further proposed the Shapley interaction index to measure the interaction utility between input variables. The Shapley interaction index is the only axiomatic extension of the Shapley value, which satisfies linearity, nullity, symmetry, and recursive properties. For two variables i, j ∈ N , the Shapley interaction index I(i, j) can be considered as the change of the numerical importance of variable i by the presence or absence of variable j.
I(i, j) = φ̃(i)j always present − φ̃(i)j always absent,
where φ̃(i)j always present denotes the Shapley value of the variable i computed under the specific condition that variable j is always present. φ̃(i)j always absent is computed under the specific condition that j is always absent.
Connections between the multi-order interaction and the Shapley interaction index. Based on the Shapley interaction index, Zhang et al. (2020) further defined the order of interaction, which represents the contextual complexity of interactions. It has been proven that the above Shapley interaction index I(i, j) between variables i, j can be decomposed into multi-order interactions as follows:
I(i, j) = 1 n− 1 ∑n−2 m=0 I(m)(i, j).

heading: B PROOF OF THEOREMS

heading: B.1 PROOF OF THEOREM 1
text: Motivation of Theorem 1. Let W denote network parameters of the DNN. Let L and η denote the loss function and learning rate of training, respectively. According to the efficiency property of I(m)(i, j) in Eq. (2), the network output v(N) of a DNN can be decomposed into the sum of multi-order interactions I(m)(i, j). Therefore, the change of weights ∆W can be computed by:
∆W = −η ∂L ∂v(N) ∂v(N) ∂W = ∆WU + ∑n−2 m=0 ∑ i,j∈N,i6=j ∆W (m)(i, j)
where U = v(∅) + ∑
i∈N µi. Specifically,
∆WU def = −η ∂L
∂v(N)
∂v(N)
∂U
∂U ∂W , ∆W (m)(i, j) def = R(m)
∂I(m)(i, j)
∂W .
where R(m) = −η ∂L∂v(N) ∂v(N) ∂I(m)(i,j) . Based on the analysis in Section 3.2, ∆W (m)(i, j) = R(m) ∂I (m)(i,j) ∂W represents the strength of learning the average interaction between variables i and j under contexts ofm variables. Therefore, in Theorem 1, we aim to prove that the variance (strength) of learning the m-order interaction is (η ∂L∂v(N)w (m))2σ2/ ( n−2 m ) .
Proof skeleton in Theorem 1. Actually, the essence for the bottleneck is that the strength (i.e., the gradient) of learning middle-order interactions ∆W (m)(i, j) is much smaller than low-order and high-order interactions. Such a small gradient is caused by the following reasons. First, the updating gradient of I(m)(i, j) is a sample average of the gradient of ∆v(i, j, S) over contexts S. Second, the number of possible contexts S is given by ( n−2 m ) , and the middle-order interactions corresponds to massive possible contexts. Third, combining the first two points, we derive that the gradient of learning middle-order interactions is significantly lower than the gradient of learning low-order interactions and the gradient of learning high-order interactions. Therefore, DNNs usually fail to encode middle-order interactions.
Proof of Theorem 1. The m-order interaction I(m)(i, j) between variables i, j is defined as,
I(m)(i, j) = ES⊆N\{i,j},|S|=m∆v(i, j, S)
= 1(
n−2 m
) ∑ S⊆N\{i,j} |S|=m ∆v(i, j, S). (10)
Assume Ei,j,S [∂∆v(i,j,S)∂W ] = 0. Let σ 2 denote the variance of the gradient ∂∆v(i,j,S)∂W . Based on Eq. (10), we have, ∂I(m)(i, j)
∂W = ∑ S⊆N\{i,j} |S|=m ∂I(m)(i, j) ∂∆v(i, j, S) ∂∆v(i, j, S) ∂W
= 1(
n−2 m
) ∑ S⊆N\{i,j} |S|=m ∂∆v(i, j, S) ∂W .
Because the gradients ∂∆v(i,j,S)∂W on different contexts are independent with each other, we have Ei,j [∂I (m)(i,j) ∂W ] = 0, and the variance of ∂I(m)(i,j) ∂W is σ 2/ ( n−2 m ) .
Furthermore, because ∆W (m)(i, j) = −η ∂L∂v(N)w (m) ∂I (m)(i,j) ∂W , then Ei,j [∆W (m)(i, j)] = 0 and the variance of ∆W (m)(i, j) is (η ∂L∂v(N)w (m))2σ2/ ( n−2 m ) , where w(m) = n−m−1n(n−1) .
Therefore, the conclusion of Theorem 1 holds.

heading: B.2 PROOF OF THEOREM 2
text: Let S1, S2 denote the two variable subsets randomly sampled from all input variables N , where |S1| = r1n, |S2| = r2n, and 0 ≤ r1 < r2 ≤ 1. According to the efficiency property of the multi-order interaction, we have,
ES1 [v(S1)] = v(∅) + ES1 [ ∑ i∈S1 µi] + ES1 [ ∑ i,j∈S1,i6=j [ r1n−2∑ m=0 r1n− 1−m r1n(r1n− 1) I (m) S1 (i, j)]]
= v(∅) + r1nEi(µi) + ES1 [ r1n−2∑ m=0 r1n− 1−m r1n(r1n− 1) ∑ i,j∈S1,i6=j I (m) S1 (i, j)]
= v(∅) + r1nEi(µi) + r1n−2∑ m=0 (r1n− 1−m)ES1 [Ei,j [(I (m) S1 (i, j))]]
where I(m)S1 (i, j) def = ES′⊆S1\{i,j},|S′|=m(∆v(i, j, S′)). Similarly,
ES2 [v(S2)] = v(∅) + ES2 [ ∑ i∈S2 µi] + ES2 [ ∑ i,j∈S2,i6=j [ r2n−2∑ m=0 r2n− 1−m r2n(r2n− 1) I (m) S2 (i, j)]]
= v(∅) + r2nEi(µi) + r2n−2∑ m=0 (r2n− 1−m)ES2 [Ei,j [(I (m) S2 (i, j))]]
where I(m)S2 (i, j) def = ES′⊆S2\{i,j},|S′|=m(∆v(i, j, S′)). Note that the contexts when computing I(m)S1 (i, j) and I (m) S2 (i, j) are different. When m < r1n < r2n, we obtain that ES1 [Ei,j(I (m) S1 (i, j))] = ES2 [Ei,j(I (m) S2
(i, j))] = Ei,j(I(m)(i, j)). Therefore, ∆u(r1, r2) can be rewritten as follows:
∆u(r1, r2) = E(S1,S2)[v(S2)− r2 r1 v(S1)]
= ES2 [v(S2)]− r2 r1 ES1 [v(S1)]
= (1− r2 r1 )v(∅) + n−2∑ m=0 ∑ i,j∈N,i6=j w̃(m)I(m)(i, j)
where w̃(m) =  ( r2 r1 − 1)(m+ 1)/[n(n− 1)], m ≤ r1n− 2
(r2n−m− 1)/[n(n− 1)], r1n− 2 < m ≤ r2n− 2 0, r2n− 2 < m ≤ n− 2
Then, the conclusion holds.

heading: C EXPERIMENTAL DETAILS AND RESULTS
text: C.1 IMPLEMENTATION DETAILS
The sampling strategy when computing J (m). The interaction strength J (m) is defined as,
J (m) = Ex∈Ω[Ei,j [|I(m)(i, j|x)|]]
Em′ [Ex∈Ω[Ei,j [|I(m′)(i, j|x)|]]] , where I(m)(i, j|x) = ES⊆N\{i,j} |S|=m [∆v(i, j, S)].
To precisely compute J (m), we need to average all possible contexts S ⊆ N , all pairs of variables i, j ∈ N , and all samples x ∈ Ω, which is usually computationally infeasible. Therefore, we computed J (m) approximately by a sampling strategy (Zhang et al., 2020).
On each image dataset, we first sampled 50 correctly classified images in total. On the ImageNet and Tiny-ImageNet dataset, these images were sampled from different 50 classes. On the CIFAR10 dataset, we sampled 5 images from each class. Then, for each image, we sampled 200 pairs of patches i, j ∈ N . Since DNNs usually encodes stronger interactions between neighbor patches, we restricted that patch i is located at the neighbor patch j with a radius of two patches. Next, for each pair of patches i, j and each order m, we randomly sampled 100 contexts S from all possible contexts, where |S| = m. To plot the curve of interaction strength, we computed 13 orders for J (m), where m = r10n, 0 ≤ r ≤ n and m = 0.05n, 0.95n. On each tabular dataset, since there are only a few input variables (n = 12 on census and n = 10 on commercial), we sampled all 100 instances and all pairs of variables for computation. For each pair of patches i, j ∈ N and each order m, we randomly sampled 100 contexts S from all possible contexts.
Considering the randomness in the sampling process, we also conducted an experiment to evaluate the stability of the estimated interaction strength J (m) via the sampling-based approximation method. Specifically, given an input image x and a sampling number q, we measured the instability of J (m)(x), when we repeatedly computed the interaction for q times. The instability w.r.t. J (m)(x) was computed as Eu,v;u6=v|J (m) u (x)−J (m) v (x)|
Ew|J(m)w (x)| , where J (m)u (x), J (m) v (x) denotes
the estimated J (m)(x) at the u-th sampling time and the v-th sampling time, respectively. Then, the instability value was computed by averaging over 50 images and all sampled orders, i.e., instability = Ex∈ΩEm[Eu,v;u6=v|J (m) u (x)−J (m) v (x)|
Ew|J(m)w (x)| ]. We used the trained AlexNet on the Tiny-
ImageNet dataset and VGG-16 on the CIFAR-10 dataset to compute the instability.
We aim to evaluate how the estimated J (m) value will be affected by the randomness in the sampling process. During the sampling process to compute J (m)(x), we need to sample over multiple pairs of variables (i, j) and multiple contexts S. Therefore, we first fixed 100 pairs of (i, j), and evaluated the instability of J (m)(x) w.r.t the sampling of the contexts S. Figure 9(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. Secondly, we evaluated the instability w.r.t the sampling processes of (i, j), where the sampling number of S was set to 100 as mentioned above. As Figure 9(b) shows, when the sampling number of (i, j) pairs increased, the instabilities decreased. When the sampling number of (i, j) pairs was greater than 200 (i.e., our setting), the instability was less than 0.1, which indicated a stable approximation of J (m)(x). These results demonstrated that our sampling strategy can well approximate the interaction strength J (m).
Implementation details of adversarial attacks. Here, we introduce how to measure the adversarial robustness in Section 3.4. We adopted the untargeted PGD attack (Madry et al., 2018) with the L∞ constraint ‖∆x‖∞ ≤ to generate adversarial examples. For the census dataset, we set = 0.6 and 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 set to 0.01 for all attacks.

heading: C.2 MORE EXPERIMENTAL RESULTS.
text: In this subsection, we provide more experimental results besides the results in the main paper. Due to the computational cost, when we trained DNNs on the Tiny ImageNet dataset, we selected 50 object classes from 200 classes at equal intervals for training and testing. In the computation of ∆u(r1, r2), we set ∆u(r1, r2) = ES2 [v(S2)] − v(∅) when S1 = ∅. Figure 7 shows the distributions of J (m) of four types of DNNs (i.e., normally trained DNNs, low-order DNNs, middle-order DNNs, and high-order DNNs) mentioned in Section 3.4. The distributions of J (m) in Figure 7 were consistent with that of AlexNet model (see Figure 4(c)), which further demonstrates that these DNNs could successfully learn interactions as expected. Figure 8 shows classification accuracies using AlexNet network on images with different numbers of patches being masked. These results further verifies that high-order DNNs were more sensitive to the destruction of structural information. Figure 9 shows the J (m) distributions of normal DNNs and high-order DNNs on two tabular datasets.

heading: C.2.1 MORE EXPERIMENTS ON STRUCTURAL REPRESENTATION
text: More masking methods to verify structural representations. Besides, we conducted experiments to investigate a DNN’s capacity of encoding structural information by using a new masking method. Specifically, we masked m patches in each image and only preserved a single large region of n−m patches, as shown in Figure 10. 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 11 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 as 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 randomly-surrounding masking method. The area between the blue curve and the orange curve measures the sensitivity of the DNN to the structural destruction.
Based on the accuracy on masked samples in Figures 11 and 12, we found that the aforementioned area of the high-order DNN were much larger than the area of the normally trained DNN. This experimental results verify 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 6 and 8.
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.7n, n]-th orders based on L−(r1, r2) loss, and trained middle-order DNNs by boosting interactions of the [0.3n, 0.7n]-th orders based on L+(r1, r2) loss.
Figure 13 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 indicates that the learned DNN encoded rich structural information for inference. I.e., the larger area between the accuracy curve on images generated by the random masking method and the accuracy curve on images generated by the centrally-surrounding masking method means the richer structural information in the DNN. In this way, Figure 13 compares the capacity
of encoding structural information between four types of VGG-16 networks. Similarly, Figure 14 compares the capacity of encoding structural information between four types of AlexNets.
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 on the above two types of samples. Furthermore, for low-order DNNs trained on the Tiny ImageNet dataset, the accuracies on images generated by the random masking method were even higher than the accuracies on images generated by the centrally-surrounding masking method. This result further verifies 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 samples, which indicates that high-order DNNs encoded most structural information.
(iii) The capacity of Middle-order DNNs to encode structural information was somewhere in between low-order DNNs and high-order DNNs. It indicates that middle-order DNNs encoded more structural information than low-order DNNs, but middle-order DNNs encoded less structural information than high-order DNNs.
Experimental results demonstrated that it was the high-order interaction that was mainly responsible for encoding structural information.

heading: C.2.2 MORE EXPERIMENTS ON ADVERSARIAL ROBUSTNESS
text: Comparisons on adversarial robustness between four types of 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.5n]-th orders based on L+(r1, r2) and simultaneously penalizing interactions of the [0.6n, n]-th orders based on L−(r1, r2). We set λ1 = 10, λ2 = 10. The middle-order DNNs were trained to encourage interactions of the [0.3n, 0.7n]-th orders based on L+(r1, r2). We set λ1 = 10, λ2 = 0. We used the MLP-5 and MLP-8 networks in Section 3.1. 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 2 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 normally trained DNNs. (ii) High-order DNNs exhibited the lowest robustness, which were 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 strong connection between adversarial robustness and the orders of the encoded interactions.
More explorations on Adversarial robustness. We further explored the relationship between adversarial robustness and the order of interactions. We conducted experiments on images in the ImageNet dataset and the Tiny ImageNet dataset, in order to explore interactions of which orders were vulnerable to adversarial attacks.
Specifically, let x denote a normal sample, and let x′ = x + denote an adversarial sample. Then, according to the efficiency property of I(m)(i, j), the significant output change caused by adversarial perturbations, v(N |x) − v(N |x′), can be represented as the sum of differences in multi-order interactions as follows.
v(N |x)− v(N |x′) = ignorable bias + ∑ m w (m) ∑ i,j ∆I (m)(i, j),
where ∆I(m)(i, j) = I(m)(i, j|x) − I(m)(i, j|x′) is the compositional adversarial effect on the interaction utility I(m)(i, j|x) caused by adversarial perturbations. In this way, the overall attacking utility (the output change) can be decomposed into adversarial effects on massive compositional interactions I(m)(i, j|x).
Therefore, Figure 15 uses the change of multi-order interactions ∆I(m)(i, j) 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 interactions, and rarely affected low-order interactions. This phenomenon has been showed in some previous studies. The above experiments further verified the connection between adversarial robustness and the order of the encoded interactions.
Although experimental results showed a strong connection between adversarial robustness and the order of the encoded interactions, the order of interactions does not fully determine the adversarial robustness. Previous studies have shown that interactions encoded in adversarially-trained DNNs were usually more robust to attacks.

heading: C.2.3 MORE EXPERIMENTS ON DIFFERENT HYPER-PARAMETERS
text: Training DNNs with both L+ and L− w.r.t. different pairs of (r1, r2). We investigated the performances of DNNs when we simultaneously used multiple L+ and L− with different pairs of (r1, r2) in the loss function. We used the following five sets of experimental settings, including (i) L+(0, 0.3) and L+(0.7, 1.0); (ii) L+(0.3, 0.7) and L+(0.7, 1.0); (iii) L+(0.2, 0.4) and
L+(0.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 example, the DNN trained with L+(0, 0.3) & L+(0.7, 1.0) simultaneously boosted both interactions of the [0, 0.3n]-orders and interactions of the [0.7n, n]-orders. These results further verified the effectiveness of the proposed losses.
Furthermore, DNNs trained with L+ and/or L− w.r.t. different pairs of (r1, r2) further verified the conclusion obtained in Table 1 (left). I.e., although the interactions of different orders performed differently in both adversarial robustness (Table 1 (right)) and the capacity of encoding structural information (Figures 6, 8, 13, and 14), interactions of different orders had similar classification accuracies (the difference was within±1% accuracy). It 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 of a single (r1, r2) pair had been investigated. Figure 4 (b) and Figure 4 (c) showed that using the L+(r1, r2)/L−(r1, r2) loss boosted/penalized interactions of the [r1n, r2n]-th orders.
Second, in spite of that, we conducted new experiments to further investigate the effects of multiple (r1, r2) pairs. We used the following five sets of experimental settings, including (i) L+(0, 0.3) and L+(0.7, 1.0); (ii) L+(0.3, 0.7) and L+(0.7, 1.0); (iii) L+(0.2, 0.4) and L+(0.6, 0.8); (iv) L−(0, 0.5) and L+(0.6, 1); (v) L+(0, 0.5) and L−(0.6, 1). We used these parameters to train DNNs on the CIFAR-10 dataset. Figure 16(a) shows that L+(r1, r2) and L+(r′1, r ′ 2) loss simultaneously boosted interactions of the [r1n, r2n]-th orders and the [r′1n, r ′ 2n]-th orders. For example, by using L+(0, 0.3) and L+(0.7, 1.0), the trained DNN simultaneously boosted both interactions of the [0, 0.3n]-th orders and interactions of the [0.7n, n]-th orders.
In addition, we conducted experiments on two tabular datasets, i.e., the census dataset and the commercial dataset. We extended above five different experimental settings (w.r.t. r1 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 can use L+(r1, r2) and L+(r′1, r ′ 2) loss to simultaneously boost interactions of the [r1n, r2n]-th orders and interactions of the [r′1n, r ′ 2n]-th orders.
Third, we conducted new experiments to investigate the effects of the parameter λ. Specifically, we fixed λ1 = 0, and adjusted λ2 = 0.01, 0.1, 1, 5 to study the effects of λ2. We trained DNNs on the Tiny ImageNet dataset. First, we trained high-order DNNs by penalizing interactions of the [0, 0.5n]-th orders. Figure 16(b) shows that the interaction strength of the [0, 0.5n]-th orders decreased as λ2 increased. The results indicated that the larger λ2 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, n]-th orders. Similarly, we found that the strength of these high-order interactions also decreased as λ2 increased. This further indicates that the larger λ2 value penalized the high-order interactions more significantly. We also conducted experiments on the census dataset and the commercial dataset. Specifically, we fixed λ1 = 0, and adjusted λ2 = 0.1, 1, 10. We trained high-order DNNs by penalizing interactions of the [0, 0.5n]-th orders. Here, we used the MLP-5 networks mentioned in Section 3.1. Figure 18(a) also shows the same pattern that the larger λ2 value penalized interactions of the [0, 0.5n]-th orders more significantly. These results showed that the parameter λ2 controlled the strength of penalization.
Furthermore, we investigated the effects of λ1 on two tabular datasets. Specifically, we fixed λ2 = 0, and adjusted λ1 = 0.1, 1, 10 to study the effects of λ1. We trained middle-order DNNs by boosting interactions of the [0.3n, 0.7n]-th orders. Here, we used the MLP-5 networks mentioned in Section 3.1. Figure 18(b) shows that the parameter λ1 controlled the strength of boosting interactions.

heading: C.2.4 TIME COMPLEXITY ANALYSIS.
text: 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 a single NVIDIA GeForce RTX 3090 GPU and used 4 subprocesses in data loading. Table 3 shows 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.
In fact, a more reasonable experiment should compare the time of training the DNN to convergence, i.e. the time cost of training a DNN with a certain decrease of the classification loss. However, due to the time limit of the rebuttal, this experiment has not been finished. Nevertheless, the current loss curve has indicated that the learning with additional losses does not cause a too long training time. We will report such results after the acceptance of the paper.

heading: C.2.5 OTHER VALIDATION EXPERIMENTS
text: Using new metric to validate bottleneck. Besides, to further remove effects of magnitudes of |I(m)(i, j|x)| on different samples for fair comparison, we adopted the following new metric.
J̄ (m) = Ex∈Ω Ei,j [|I(m)(i, j|x)|]
Em′ [Ei,j [|I(m′)(i, j|x)|]] (11)
where Ω denotes the set of all samples. We found that using the new metric resulted in few changes to the distribution of the interaction strength. Figure 19 shows a similar representation bottleneck phenomenon when we used the new metric, i.e., the middle-order interaction was less likely to be encoded in DNNs.
Validation of zero-mean assumption in Theorem 1. We further verified the reliability of the zeromean assumption in Theorem 1. To this end, we analyzed the mean value Ei,j,S [∂∆v(i,j,S)∂W ] of the gradient w.r.t. the parameter W at the first convolutional layer when we trained ResNet-18 on the Tiny ImageNet dataset.
Since the above gradient ∂∆v(i,j,S)∂W is a high-dimensional vector, it is difficult to visualize the expectation of 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 o1, o2, . . . , o5. We examined the mean value and the standard deviation of the gradient strength projected on each direction oi, over gradients w.r.t. different triplets (i, j, S) computed on 10 different samples. Given each input sample, we computed gradients ∂∆v(i,j,S)∂W for 10 pairs of (i, j) and 1000 contexts S.
The examination was conducted when |S| = 0.05n, |S| = 0.5n, and |S| = 0.95n. Tables 4 and 5 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 0, which validated the zero-mean assumption in Theorem 1.
In addition, for simplicity, we used σ2 to denote the variance of the gradient ∂∆v(i,j,S)∂W in Theorem1, without distinguishing different sizes of contexts S. Tables 4 and 5 show that there existed some small difference between variances of the gradient when we considered different sizes of contexts S. However, such difference is negligible in the proof and does not affect the conclusion of Theorem 1. This is because the learning strength of the m-th order interaction is proportional to n−m−1 n(n−1) / √( n−2 m ) , whose difference between different sizes of contexts was much larger than the above difference in variance.

heading: C.2.6 CLARIFICATION OF THE INSIGHT OF TABLE 1
text: Table 1 compared the classification accuracy (left part) and compared adversarial robustness (right part) between DNNs encoding different orders of interactions.
Table 1 did provide some new insights. By comparing results in Table 1 (left) with results in Table 1 (right) and Figures 6, 8, 13, and 14, we found that although the interactions of different orders performed differently in both adversarial robustness (Table 1 (right)) and the capacity of encoding structural information (Figures 6, 8, 13, and 14), interactions of different orders had similar classification accuracies. It showed that although interactions of different orders had their distinctive properties, such difference did not necessarily affect their classification accuracies.

Review summaries:
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. 

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. 

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:  1) 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.  2) The authors develop novel loss functions to encourage/penalize the interactions of specific complexities and then, investigate the representation capacities of the learned DNNs.