Towards the Difficulty for a Deep Neural Network to Learn Concepts of Different Complexities
Authors: Dongrui Liu
Huiqi Deng
Xu Cheng
Qihan Ren
Kangrui Wang
Quanshi Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: representation complexity
deep learning
TL;DR: This paper theoretically explains the underline mechanism that makes simple concepts more likely to be learned by DNNs.

Abstract: This paper theoretically explains the intuition that simple concepts are more likely to be learned by deep neural networks (DNNs) than complex concepts. In fact, recent studies have observed [24, 15] and proved [26] the emergence of interactive concepts in a DNN, i.e., it is proven that a DNN usually only encodes a small number of interactive concepts, and can be considered to use their interaction effects to compute inference scores. Each interactive concept is encoded by the DNN to represent the collaboration between a set of input variables. Therefore, in this study, we aim to theoretically explain that interactive concepts involving more input variables (i.e., more complex concepts) are more difficult to learn. Our finding clarifies the exact conceptual complexity that boosts the learning difficulty.

Towards the Difficulty for a Deep Neural Network to Learn Concepts of Different Complexities
Dongrui Liu"*
Huiqi Deng'
Xu Cheng
Qihan Ren
Kangrui Wang"
Quanshi Zhang"
Shanngaai Jiao Tong University
University of Chicago
Abstract
This paper theoretically explains the intuition that simple concepts are more likely to be learned by deep neural networks (DNNs) than complex concepts. In fact, recent studies have observed 45 27 and proved 47 the emergence of interactive concepts in a DNN, i.e., proven that a DNN usually only encodes a small number of interactive concepts, and be considered to their interaction effects to compute the inference score. Each interactive concept encoded by the DNN to represent the collaboration between a set of input variables. Therefore, in this study, we aim to theoretically explain that interactive concepts involving more input variables (i.e., more complex concepts) more difficult to learn. Our finding clarifies the exact conceptual complexity that boosts the learning difficulty.
Introduction
Deep neural networks (DNNs) have exhibited superior performance in various tasks, but the reason for their superior performance remains an open problem. To this end, many attempts have been made to explain the representation capacity of DNNs from different perspectives. For example, Montufar et al. (35) used the number of linear response regions in a DNN to evaluate the expressive power of the DNN. Dinh et al. (13) and Petzka et al. 39 used the flatness of loss functions at minima explain the generalization power.
In this paper, explore fundamental yet not well-formulated problem in terms of the representation capacity of DNNs, i.e., what types of concepts are easier to be learned by DNNs. However, the core challenge of this problem is that researchers have not reached consensus on how to define a concept encoded by DNNs. Therefore, previous findings 5 28 34 that DNNs easily learn simple concepts remain intuition empirical observations, without clear theoretical formulation and explanation.
Fortunately, Ren et al. 45), Li and Zhang 27 have observed and Ren et 47 have, for the first time, mathematically proven that the emergence of interactive concepts is a common phenomenon shared by different DNNs. I.e., proved that under some common conditions, a well-trained DNN will encode just small number of interactive concepts for inference. Specifically, the interactive concept encoded by DNN defined as a Harsanyi interaction [18) in game theory, which represents an AND relationship between input variables in specific set S. For example, as Figure aa) a) shows, the DNN encodes the co-appearance relationship between input variables (image (#1, 12, 23)) Only when all three patches
patches) æ1, 12, and æs to form the mouth concept all present, the mouth concept is triggered, and adds a numerical effect I(S) to the inference score y. The masking of any patches (e.g., #1) will break this AND/co-appearame relationship of the mouth
"Equal contribution
This research is done under the supervision of Dr. Quanshi Zhang. He is with the Department of Computer Science and Engineering, the John Hopcroft Center at the Shanghai Jiao Tong University, China. Correspondence to: Quanshi Zhang <zqs10226 @ edu.eedu.cn>.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Trigger(S) (S.)
(Sig =1
13
Training an MIL Trining a PointNet on Trining ReaNetel
Trainng LSTM oz
tactaee dataeci saliest
SlapeNet dutiect
CelebA dataset
CoLA daraset
yalient
Dolse
TONA
taise
nose
(1)
(b)
(1g)
Veaining Mll
Toinnng Alee Net
Trining BesNes-32 32
Traising a CNN
7-rrder
TV news datsset
CdidhA datanct
MNIST datsact
concept
cutceepl
(r(s))
saliem
otlint
unmask(s
11050
Bo5e
unnass((s
masked image X7
Different in ttrucciion
Difierent interactions
Different interactions
Different interactions
Figure 1: (a) Interactive concepts encoded by DNN. Each interactive concept S represents an AND relationship between input variables (image patches) in S. Masking any input variables in will deactivate the concept S. (b) Extensive experiments illustrate the common concept-emergence phenomenon. Various DNNs encode very sparse interactive concepts for inference. Only a small number of interactions have salient effects (S) and are termed interactive concepts. Other interactions w.r.f other S N all have almost zero effect T(S) so O, thus being termed noisy patterns. For clarity, sort the strength of interaction effects in descending order.
concept, and removes the numerical effect I (S)), i.e., making T(S) 0. More crucially, it proved in [47] that the network output each input sample be represented as the sum of numerical effects of such a few interactive concepts, i.e., > Sccoceptte (S)).
The mathematical proof in 47 makes the interactive concept the first concept whose emergence in DNNs certificated. Furthermore, and Zhang [27 have discovered that the interactive concepts have considerable transferability over different samples and strong discrimination power for classification. In this way, we can roughly consider such interactive concepts a rigorous definition of
concepts encoded by DNNs.
Explaining the difficulty of learning complex interactive concepts. Therefore, in this study, given the above interactive concepts, we aim to further explore the learning difficulty of these concepts, and explain that DNN is more likely encode simple interactive concepts. Here, we use the number of variables in an interactive concept S to represent the complexity of the concept, which is also termed the order of the concept. Thus, low-order interactive concepts usually represent simple AND interactions among few input variables.
Specifically, we find that low-order interactive concepts encoded by DNNs generally more stable to inevitable noises in data. In this way, low-order interactive concepts usually exhibit consistently positive (or negative) effects on the inference score of different samples in the same category. In comparison, high-order interactive concept is more likely to have significantly diverse effects on inference scores of different samples. This explains the reason why DNNs easily learn simple interactive concepts.
In addition, discover that our research may provide new perspective to explain previous find- ings/understandings of the conceptual complexity [5] 34 63 28 Besides, the conceptual complexity can directly explain the adversarial robustness of DNN. Thus, our study is of considerable value in explaining the representation capacity of a DNN.
Interactive concepts cognitive concepts. Although the Harsanyi interactive concepts visualized by [27] seem partially aligned with cognitive concepts to some extent, we do not think such interactive concepts fit humans' cognition 24! (53. For example, the recognition of a big ball concept and that of a small ball concept have almost the same cognitive complexity for humans. In comparison, is more difficult for the DNN to recognize large ball, because it has to a high-order interaction that contains a lot pixels to examine whether all pixels within the ball have the same color. Thus, this study elarifies the exact formulation for the conceptual complexity interactive concepts that boosts the learning difficulty, which is different from the cognitive difficulty.
2 Explainable AI (XAI) theories based on game-theoretic interactions
Explaining DNNs based on system of game-theoretie interactions becomes an emerging direction in recent years. Specifically, such a system aims to tackle the following challenges in XAI.

---

Defining, extracting, and quantifying interactive concepts encoded by DNNs. Quantifying the interactions between different imput variables [57 is a new perspective to formulate the knowledge encoded by a DNN. Based on game theory, Zhang et al. 66
introduced multi-variate interaction and multi-order interaction to quantify the interactions encoded by the DNN. Ren et al. [45] empirically observed and Ren et al. [47] further proved that DNN usually just encoded a small number of salient interactions. Ren et al. [44] defined the optimal baseline value for computing the Shapley value based on these interactions. Li and Zhang (27 found that salient interactions usually have high transferability over different samples and DNNs. These findings showed that these salient interactions could be viewed interactive concepts encoded by DNN.
68 67
Using interactive concepts to explain/measure the representation power of DNNs. The repre- sentation power of DNNs has been explained by game-theoretic multi-order interaction, including generalization power Besides, Cheng et al.
adversarial robustness 45 70], and adversarial transferability [60].
8 used interactions to investigate how shapes and textures were encoded in found that salient interactions often represented prototypical patterns encoded by DNNs. Deng et al.
DNNs. Cheng et al. 9
[I] derived that the DNN was less likely to encode mid-order interactions. In comparison, Ren et al. [46] proved that the Bayesian neural network was less likely to encode high-order interactions, thereby obtaining good adversarial robustness.
Unifying the common underlying mechanism shared by previous empirical findings. Interactions have superior representation power, and we find that many previous studies can be re-explained from the perspective of interactions. Deng et al. 12 proved that fourteen attribution methods could be reformulated and considered as a certain allocation of interaction effects. Besides, Zhang et al. 69 proved that reducing the interactions was the common underlying mechanism shared by twelve previous studies for improving adversarial transferability.
3 Explaining simple interactive concepts are easy to learn
3.1 Preliminaries: sparse interactive concepts emerge in DNNs
It is generally believed that the learning of DNNs is a fitting problem between the ground-truth label and the model output, instead of explicitly learning specific concepts like graphical models. However, Ren et al. [55, Li and Zhang [27] have empirically observed and Ren et al. [47] have mathematically proven the counter-intuitive emergence of concepts in DNNs, i.e., it is proven that under set of common conditions, DNN encodes just a small number of interactive concepts for inference.
Specifically, given a pre-trained DNN and input sample [Ir [.]] with n variables indexed by N- {1.... n. v(z) E R denotes a scalar output of the DNN Each interaction in [45 27 47
is defined Harsanyi dividend (or Harsanyi interaction) [8]] in game theory, which represents collaboration (AND relationship) between input variables in a specific set S (S C N). For example, as Figure a)) shows, the co-appearance of image patches forms a mouth interaction S {z1, 22, Only when these three patches are all present, the mouth interaction will be triggered, and make a certain interaction effect (SS) on the network output. The absence (masking) of any patches of 31, 22. and z3 will deactivate the mouth interaction and remove the interaction effect, i.e. ((S) = 0. The interaction effect [S]) on the input sample is computed as follows.
[(SW=) Erco( 81-171, <(TT):
(1)
where æy denotes the masked input sample, when we mask input variables in N T and keep variables in T unchanged. Please see more properties of the Harsanyi dividend in the supplementary material.
Theoretically, there are 2" potential subsets S of input variables (S E 2 {SIS C N)). The proven concept-emergence phenomenon refers to that only a small number of subsets S E Raalient S 2d make salient interaction effects [S]]a on the network output, and can be considered as interactive concepts. Interaction effects of all other subsets are close zero (I(S)e zs 0), which can be considered as ignorable noisy patterns. Therefore, the network output v(z) can be well approximated by interaction effects of small number of interactive concepts, i.e..
v(x) Σ sCN (S(x)) ~ Σ Seftattnn
1(S1x)
'Here, v(w) E I can be implemented either scalar output of the DNN or dimension of output vector (e.g., the confidence score of classifying the sample the ground- truth category v(æ) log Mman
p [m]
3

---

phenomenon on various DNNs, including multi-layer perceptrons (MLPs), long short-term memory (LSTM), AlexNet 233, ResNet 19]. convolutional neural networks (CNNs), and PointNet [41] trained on different types of data, including tabular data (UCI dataset [6], natural language data (CoLA 66 and SST-2 [56]) image
We also conduct experiments to illustrate the
data (MNIST (26) and CelebA (3I), and point cloud data (ShapeNet (65] ). We follow experimental
settings in [45 22,, and Figure [bb) shows that interactive concepts encoded by a DNN are usually
indeed sparse.
Theorem 1. Given an input sample E R" with variables, there are 2" different masked samples æT W.E.t all potential subsets S N. Then, (45] has proven that
VT v(œT) Eecr SCT 1(S[x) Rz Σ SERein&sCT (S(xx).
Theorem I means that we a small number of interactive concepts in Qaaiien well approximate network outputs on anyone æy of the 2" masked samples.
Trustworthiness of interactive concepts. The mathematical proof in 47 makes ((S) become the first concepts whose emergence in DNNs certificated. Equations 2 and (3) further guarantee that interactive concepts can faithfully explain the output of DNNs. In addition, Li and Zhang (27] have discovered that (i) interactive concepts are transferable across different samples; (ii) interactive concepts are discriminative, i.e., if a concept S has salient interaction effects ((S) set of samples, then the concept tends to push these samples to be classified towards the same category. In this way, we can roughly consider such interactive concepts relatively rigorous definition of concepts.
Complexity (order) of interactive concepts. The complexity of an interactive concept S is defined as the number of input variables involved in S, which is also termed the order of the interactive concept, i.e. complexity(S) = order(S) = |S]. Thus, low-order interactive concepts usually represent simple AND relationships among a few input variables. In comparison, high-order interactive concepts often refer to as relatively complex AND relationships among a large number of input variables.
3.2 Simple interactive concepts in data are more stable and easier learn
Unlike other interaction metrics 16 32 57], sparse interactive concepts are certificated to emerge in DNN, and can faithfully represent the inference score of DNNs. Therefore, in this study, we aim to further explore the learning difficulty of these certificated concepts. Specifically, we theoretically explain that a DNN more likely to encode simple (i.e., low-order) interactive concepts.
In this subsection, we show that low-order interactive concepts encoded by DNNs are generally more stable inevitable noises in data, compared to high-order interactive concepts. Specifically, derive an approximate analytical solution to the variance (instability) of interactive concepts' effects w.r.t data noise, and show that the variance (instability) increases along the order of concepts in an exponential manner.
Theorem 2 (proven in the supplementary material). Given a neural network v and an arbitrary input sample x' E IR", the network output can be decomposed by using the Taylor expansion i.e., v(a') = ESEN Emeqq Us.x - [S, x (aa=). In this way, according to Equation 7 the Harsanyi interaction effect T(S(a') ) on the sample x' can be reformulated as follows.
I(S)=') = =E US.T J n T(x²).
Here, J(S, lhes (sign(z) bi) A-4 denotes a Taylor expansion term of the degree n, where the degree π E Qs = [......, JTlllVi E S, E No:Vi & S, = 0} and by is the baseline gm"u(a))
value to mask the inpul variable xi. In addition, Us Ih 84 " ... -he [sign(x - b:))"
where vlg denotes the sample whose input variables are all masked.
Σn
Theorem 2 rewrites the Harsanyi interaction effect [(S) of each concept from new perspective, to facilitate the analysis of the instability of interactive concepts. The derivation of Theorem 2 is inspired by [2 70 (66. in which the Harsanyi interaction effect is re-written as the sum of the Taylor interaction effects. Therefore, in this study, we define a new baseline value b, to further extend the finding in [2] and obtain Theorem 2 which significantly simplifies the further proof. Specifically, the new bascline value by is set as follows to represent the masked state of the i-th input variable. i.e.,

---

a; <- b;. Previous studies usually set b, μn [m[x:] as the average value over different samples to represent the masked state 12] However, we consider that pushing the input variable x, to move a large distance T E R towards μ4 has been significant enough to remove its information. To this The above new setting ensures comparable
end, we set b. = Z; - + if x4 > μ4; else, b, = 2; + 7 perturbation magnitudes over different dimensions.
Next, we analyze the variance (instability) of the interaction effect [(S) = x + c) when we add a Gaussian perturbation e ~ (N I² to the input sample æ. Here, the Gaussian perturbation E R"' considered as rough representation of inevitable variations in data, e.g., shape deformation and object rotation variations in image classification. However, such variations are quite difficult to formulate, so we use Gaussian perturbation as a rough representation. Fortunately, we find that our reformulation of interactions in Theorem 2 enables us to directly apply the finding in [46] to prove the variance (instability) of the interaction effect [(S] = x x++6) c).
Theorem 3.
Let us add Gaussian perturbation ~ N(0,0²1) to the input sample x. Lel us first consider the case with the lowest degree it- = [
..aa E Qs, satisfying that vi E S, f. = 1; & 8, म. 0. The mean and variance of [S, +| + E) over the Gaussian perturbation are given as
1 (1)))))
191
[S, - =]]]= Var,[J(S, E]]
(5)
Furthermore, for the more general case with an arbitrary degree т E Qs = [[TI,- Fn / S,
E
N+;Wi $ S, = 0}, the mean and variance of J(S, π| + E) are computed as
I. [T n + c)] = Te II LES" (1+ 4)m,,, Varc[J(S, m| + c)] = Vara
(1 S ). (6)
Theorem 3 shows the (variance) instability of interactive concepts of different complexities (orders)
w.r.f data variations. It indicates that the variance of J(S, म E) roughly increases along with the order(S) = | in an exponential manner. Similar conclusions are also introduced in (70]. Furthermore, according Equation (4), the interaction effect [(5] + e) of the concept S can be represented as the weighted sum of J(S, π l + e). and coefficients Us.= w.r.l. different orders and degrees are usually chaotic. Hence, we can roughly consider that the variance (instability) of the interaction effect T(S] - e) increases along with the onler |S] exponentially, as well. In other words, compared to high-order concepts, low-order concepts are much more stable to slight input perturbations.
Experimental verification. Here, we conduct experiments to verify whether the variance (instability) of interaction effects indeed increased along with the order in approximately exponential manner. Specifically, to mimic variations in the data, we add Gaussian perturbations ~ (O, 0.02*1) to each training sample. Then, we compute the average mean EEme =Ems x the average variance (=m)=Emm x [E [Vr. concepts w.r.f. Gaussian perturbations. For verification, we calculate such metrics on DNNs trained for image classification and DNNs trained on tabular data. We train AlexNet (23] VGG-11 (55]. ResNet- 18220 [99 on the CIFAR-10 10 dataset (22) and the Imay- dataset (55 respectively. We also train five-layer MLP 45 on the UCI census dataset (namely census dataset) and the UCI TV news dataset (namely TV news dataset) [6], respectively. In addition, considering the computational cost of [(S]x + e) in Equation (I) is intolerable if each pixel is considered as an input variable, we divide images into 8 8 patches [5] to calculate I(S) x ee). Please see the supplementary material for more implementation details.
[ [ ( as + <)]lI] and + <)]] of interaction effeets of the s-th order
Figure 2 shows that the variance (instability) v(s) of interaction effects increases in an exponential manner along with the order of the interactive concept. In addition, the relative stability 5² /VV() of interaction effects decreases significantly along with the order s. Such phenomenon successfully verifies findings in Theorem 3
3.2.1 Formulating the conceptual learning as linear regression problem
Note that, Li and Zhang (27 have discovered that interactive concepts have high transferability over samples in the same category, i.e., most interactive concepts extracted from different samples may
*We need to avoid the case of over- pertuurturbbtion by setting b, < max(b,, ) if x; > pa: b, + min(b,, n.). otherwise. Fortunately, such cases are uncommon in real applications, so we ignore such settings in the following theoretical analysis.
5

---

log[vin
Five-layer MLP on Census
Five-layer MLP on TV news
200
v /WW)
ResNet-20 CIFAR-10
ResNer-18 on Tiny-ImageNet
AlexNer on CIFAR-10
AlexNet on Tiny-InageNet
VGG-11 CIFAR-IO
VGG-11 oo Tiny-ImageNet
0.1n
0.5m
0.9n 0.1n
0.5n
0.9m
Order
Order
Figure 2: The logarithm of the variance of interaction effects log[V([)] and the stability of interaction effects (measured by E /////VVV /VVL). The variance V of interaction effects increases along with the order interactive concepts exponentially. The stability of effects decreases along with the order.
all belong to the same subset f2. S Quatieat. Therefore, we can consider the interactive concepts as common knowledge learned by the DNN, and we aim analyze the difficully of learning each interactive concept with different complexity.
To facilitate the analysis, first simplify the conceptual learning linear regression problem. Specifically, we first rewrite the interaction effect of an interactive concept S. Given an input sample æ, according to Equation 4 the interaction effect of the concept on the sample ær' (obtained by applying some transformations on σ), [(S|ar) can be rewritten as
T(S]=²) = Us C=
where the constant Us [(][=) denotes the interaction effect the sample æ, and the function for the triggering state on the transformed sample æ' is given as Cs(x') = =Ereqs US, x (xx) //Us.
Theorem 4. Given an arbitrarily masked sample ær (T S N), the function Cs(ær) defined above can be computed as the binary triggering state of the concept in the sample ær.
Y N, Cs(ær)) = II A((ar)= 1 CT),
(8)
where A. (xxr)) E [0.1) denotes whether the variable x; is present A:(æT) or being masked A:(xr) = 0 in the sample ær.
The function Cs(ær) represents the triggering state of the concept S under an arbitrarily masking condition A T C N. Only when all variables in S are present under the masking condition T, the concept S is triggered (s(ær) = 1. If any of variables in is masked, then the concept S will not be triggered Cs(ær) = 0, yielding zero interaction effect I (S][r) = 0. Theorem shows that given masked sample ær. the concept is only triggered when the sample ær contains all variables in i..,, T S.
Thus, inspired by (46.. we can extend the conclusion continuous version that explains the output of the DNN as a linear regression of very few salient interactive concepts based on Equation (3).
v(xx)= ESEN Us Cs(x')
E Us Cs(x'),
where the triggering state Cs(x') of each interactive concept can be considered as an input dimension of the linear function, which reflects whether the input sample x' contains the concept S.
Therefore, the absolute value of the weight coefficient Us in Equation (9) can be viewed as the strength of the DNN encoding the interactive concept S. Considering the sparsity of interactive concepts discussed in Section 3.1] most interactive concepts have ignorable coefficients Us- = O, and not so many concepts S have large absolute value of [Us]. Thus, we can consider that the DNN only learns a small number of salient interactive concepts.
3.2.2 Explaining the learning difficulty of concepts
Equation (9) in the previous subsection enables us to understand DNN for the classification task as pseudo-linear function. Then, if an input feature dimension has stable value (i.e., the triggering state Cs of an interactive concept S stably being present/absent) across all samples in the same category, then we consider this feature dimension (i.e., the concept) easy to learn. In comparison, when we extract the same concept from different samples in the same category, if this concept exhibits inconsistent interaction effects (e.g., such a concept does not consistently present or absent over different samples), then this feature dimension (i.e., the concept) is hard to leam.

---

Fiveslayer Canuu
AlesNet CIFAR-10
VGG-11 CIFAR-10
ResNe-30 CIFAR-10
15
(P333 0.
0.3n
130
200
100
150
200
Five-layer MLPP TV news
AlexNia Tinp-lmageNe
VGG-I1 Ting-ImagoNel
ResNect 88 on Tiny-lmapoNat
5 0.0n
1.0
10
50
100
150
200
50
100
150
200
100
150
200
Epoch
Epoch
Fgoch
Fpoch
Figure 3: Consistency ((S) of s-order interactive concepts. The curve shows the mean consistency Esc I.I [8(] over different interactive concepts of the s-th order, and the shade indicates the Effects of low-order concepts are more consistent than those
standard deviation of high-order concepts.
Five layer MLP on Census
Ale on CIFAR-10
VGG-1 an CIFAR-10
RexNes20 on CIPAR-10
0.10
0.15
1.50
1.25
0.05
0.3
30
150
150
100
30
100
150
200
* 0.2n
Five-layer MT. Pnn TV news
AlexNet ImagaNet
on Tiny ImageNet
ReaNet-1 Tmy-InageNN
1.75
[x(5)=_(x(5)]
0.02
0.05
0.9
1.50
50
100
150
200
50
L60
150
200
50
150
150
200
0.00
Opoch
Epoch
Epoch
Epoch
Figure 4: Instability x(S) of s-order interactive concepts to data variations. The curve shows the average instability Esg =. [R[S]] over different interactive concepts of the s-th order, and the shade represents the standard deviation std [x(S]]. Effects of high-order concepts are more sensitive data variations than those of low-order concepts.
To analyze the consistency/stabiiity of the concept w.n. data variations, we use small perturbations e to represent various inevitable variations in the data, such as shape deformation and object rotation variations. Theorem shows that high-order interactive concepts are much more unstable to inevitable variations in the data than low-order interactive concepts. This makes high-order concepts more likely to be influenced by data variations and less likely to be consistently present or absent in samples of the same category, which boosts the learning difficulty.
Experimental verification. We conduct experiments to verify the claim that high-order interac- tive concepts are less stably extracted under data variations than low-order interaction. We use the following two metrics to evaluate the each interactive concept S (i.e., each single input di- mension of the above linear function) of a certain order. Specifically,
use the first metric ((S) = E. [|==xx (SS [ e x. [T(S) ==]] to measure the relative consistency of the interactive concept appearing over different input samples in certain category c. Here, X. denotes set of training samples belonging to the category c, and Stdze x, ([([)) indicates the standard deviation of I(S () over different input samples. A large B(S) value means that the interactive concept S in all samples of the category e has similar/consistent effects [()])). is easier for a DNN to learn such a consistent concept S.
In addition, we use another metric k(S) to verify whether the interaction effect of the high- order interactive concept is usually less stably extracted than those of the low-order interac- tive concept. To this end, the metric x(S) -E x [E. [[ + <) c) - [x]]]]] concept 5 to the inevitable slight variations e in the data. Here, (s(=+e) = I(5) + +e/UUs computed in Equation 7 denotes the trigger state of the interactive concept on the sample x'
[|{[S] [ICs(x:) measures the relative instability of the interactive
To this end, we use DNNs and experimental settings the experimental verification paragraph of Section 3.2 for evaluation. Figure and Figure 4 show the change of the average consistency ((S) and the average instability x(S) of s-order interactive concepts through the learning process, respectively. At each training epoch, low-order concepts usually obtain higher consistency B(S) and

---

Five layer MLP on Consus
AlexNet on CIFAR 10
VGG-II CIRAR-10
ResNet- 20 CIRAR-10
sim?? maal 65
0.3
0.5
9.5
0.2c
Epoch
150
Fpoch
250
50
150
150
Ponch
200
0.0
50
160
150
Epoch
200
5
0,
Fivelayeer MLP on news
AlexNet on Tay ImapeNet
VGG- 11 on Tiny ImageNet
ResNes 18 on Tiny ImageNet
10
10
simef) linal
5.
Fpoch
Prnch
0.0
200
0
Figure 5: The weighted Jaceard similarity sim(1!") ( between s-order interactive concepts learned after the intermediate epoch r and those learned after the final epoch - Low-order concepts usually have higher Jaccard similarity during the learning process, which indicates that DNNs first learn low-order concepts and then gradually learn more about high-order concepts.
lower instability x(S) than high-order concepts. It means that low-order concepts usually are more consistent and more stable. Thus, this experiment explains the reason why low-order interactive concepts are easier to learn.
3.2.3 Fast learning of low-order concepts
In this subsection, we illustrate the phenomenon that low-order interactive concepts are usually learned faster than high-order concepts, as support for the claim that low-order interactive concepts are easier be learned. We have theoretically proven in Section 3.2 and experimentally verified that low-order interactive concepts are more consistently present or consistently absent in different samples of the same category, which makes low-order interactive concepts easier be learned. Then, this experiment is conducted to check whether low-order concepts are really learned faster than high-order concepts.
Specifically, we examine whether interactive concepts encoded by the finally-learned DNN Vtinal (x) have already been encoded by the DNN that is ((x)) trained after 1 epochs. If so, consider such interactive concepts learned fast. Specifically, let I [=), [Sa[z))]]
R
denote a vector of interaction effects for all d = (*) interactive concepts of s-order. Then, we compute the Jaccard similarity between s-order interactive concepts encoded by the DNN Unmai (x) and those encoded by the DNN (x)), i.e., sim (7(-) ) m||min[[] (, 7!-) )l1/))111 max] 7 l1
and || ||2 denotes Ll-norm. We extend the d-dimensional vector [ into 2d-dimensional vector
with non-negative elements 7( = ((T (TIT" [max{ (( 1,0,, min(T T) R2
Similarly, compute T:t) with non-negative elements based T(a) In this way, large similarity sim(1," (1()) I [())) at an earlier epoch indicates that interactive concepts are easier to be learned.
To this end, let us use DNNs and experimental settings introduced in the experimental verification paragraph of Section 3.2 for evaluation. Figure]]shows that DNNs first learn low-order interactive concepts, and then learn high-order interactive concepts. Such a phenomenon verifies the conclusion that DNN easily learns low-order (simple) interactive concepts.
Explaining findings in previous studies
4.1 Explaining ad adversarial robustness
Previous study 4 has discovered that low-order interactions are more robust to adversarial attacks than high-order interactions. Notice that their high-order (low-order) interactions are different from, but highly related to our high-order (low-orden interactive concepts. Specifically, our interactive concepts can be explained as elementary components for such multi-order interactions in [43] Please see the supplementary material for the proof. Therefore, from this perspective, our conclusion that "low-order interactive concepts are easy to learn" can also explain how a DNN encodes concepts of different adversarial robustness.
8

---

Five-layer MLP Census
AlexNet CIFAR-10
VGG-11 CIFAR-10
ResNet-20 CIFAR-10
0.4
0.4
440
0.2
0.0
0.3n
0.5m
0.5m
0.0
0.1n
0.5m
0.5n
0.0
0.1n
0.5n
0.9n
0.0
0.1m
0.50
0.3m
Fave-layer MLP on TV news
AlexNet Tiny Imy-eemaeNNe
VGG-11 on Tiny Iny-lemgeeet
ResNet- 18 on Tiny-Imageen Inngeeeet
4
0.5
1.0
0.5
0.2
0.0
0.3n
0.50
0.3n
0.0
0.30
0.5m
0.9n
0.00
0.3n
0.5n
0.5n
0.0
0.1n
0.5n
0.90
Order
Order
Order
Order
Figure 6: Average adversarial sensitivity A of s-order interactive concepts to adversarial pertur- bations. Low-order interactive concepts are usually much less sensitive to adversarial attacks than high-order interactive concepts.
Can we use interactive concepts in this paper to verify the heuristic findings of adversarial represent the inference logic of DNN by a set of interactive concepts, i.e., v(x) R SEP [(S]ar). In this way, we conduct experiments to evaluate the sensitivity of each interactive concept S to adversarial perturbations. The symbolic conceptual representation of interactive concepts allows us to measure the adversarial robustness in a more direct way. That is, if the effect of interactive concept does not significantly change under adversarial attacks, we consider this interactive concept is robust to adversarial attacks. In contrast, if the effect of an interactive concept changes significantly under adversarial attacks, we consider this interactive concept is sensitive to adversarial attacks.
robustness in [ According Equation 2
To this end, we use the metric (S) Exs ( 6) [(S]=)]] xE [[(()]=)]] to evaluate the [E=ex(1
sensitivity of the interactive concept S to adversarial perturbations, where denotes the adversarial perturbation generated by the lxc attack (33]. In this way, small a(S) value indicates that the interactive concept S is robust to the adversarial attack.
We follow experimental settings in the experimental verificution paragraph of Section 3.2 to evaluate different DNNs. Figure 6 shows that compared to high-order interactive concepts, low-order concepts usually obtain smaller A Esg,,1s [a{S)) values. Such phenomena demonstrate that low-order interactive concepts are more robust to adversarial attacks.
4.2 Connections to existing findings on what are learned first by DNN
In this subsection, we discuss some related studies on which kind of knowledge is usually first learned by a DNN. Most previous studies conducted experiments to explore the knowledge that was easier to be learned by DNN, without providing much theoretical support. However, we find that our theorems can partially explain mechanisms behind some previous findings.
Arpit et al. [5] trained DNNs to classify both normal samples and white-noise samples to different object categories. In this way, they considered that the DNN encoded simple concepts to classify normal samples, but the DNN had to learn complex concepts to classify white noises to randomly- assigned labels. They observed that the DNN usually learned normal samples first, because the classification accuracy of normal samples increased before that of white noises. To this end, our research provides more insights into such an observation. Specifically, Cheng et al. [8] have proven that the classification of noisy data usually depends on high-order concepts, i.e., the classification of noisy data forces the DNN to memorize each specific white-nois sample as a specific high-order interactive concept. Let us combine this conclusion with our finding that high-order interactive concepts are hard to learn. Then, we can easily owe the slow learning of white-noise samples observed in [5] to the difficulty of learning high-order concepts.
Mangalam and Prabhu 34 considered/defined easy samples as training samples that could be correctly classified by shallow machine learning models, such as support vector machine (SVM) and random forests (RF). They discovered that DNNs first learned easy samples, and then gradually learned more about hard samples. To this end, our research verifies such observation. Specifically, we claim that easy samples mainly contain low-order interactive concepts. Thus, hard samples mainly contain high-order interactive concepts corresponding to complex interactions between numerous

---

input variables, and thus are difficult to be classified by shallow models (e.g., the SVM and the RF). In this way, the fast learning of low-order concepts is another understanding the finding [3].
Xu et al. 63 discovered that during the training process, DNNs usually first learned samples of low frequencies (e-g,, robust noises), and then encoded samples of high frequencies (e-g., sensitive to noises). However, the original design of DNNs is not towards learning specific spectrums, and techniques of deep learning are not developed by assuming a periodic loss landscape of training samples. Therefore, we believe there should be a more direct explanation for the spectrum-learning phenomenon discovered by [3]. To this end, our research explains this phenomenon as the difficulty of learning high-order concepts. According to Section 4.1 low-order concepts usually are less sensitive input perturbations, thereby corresponding to low-frequency components defined in the loss landscape in [63]. Accordingly. high-order concepts correspond to high- figh-freeuency components.
Liu al. (28) discovered that during adversarial training, the training loss of the DNN trained on easy samples decreased faster than that of the DNN trained on hard samples. To this end, we consider easy samples in adversarial training mentioned by [28 may mainly contain low-order interactive concepts. It is because, as discussed in Section 4.1
43 discovered that low-order interactions were robust adversarial perturbations. Thus, the fast learning of easy samples in adversarial training can be roughly owing to the learning of low-order concepts.
Conclusion and discussion
In this paper, theoretically explain the trend of DNNs learning simple concepts. Since the emergence of interactive concepts of DNNs has been observed [45 27 and proved [47), we aim to theoretically explain the explicit theoretical connection between the conceptual complexity and the difficulty of learning concepts. In this way, we prove that low-order interactive concepts in the data are much more stable than high-order interactive concepts, which makes low-order interactive concepts more likely to be encoded. Besides, our research can also provide new insights into several w.r.f. the conceptual representation of DNNs.
previous empirical understandings 5 34 63 23
There are very few ways to define and examine what is a "concept." In this paper, we only use the following three properties to support the faithfulness of using sparse salient interactions as concepts encoded by the DNN.
Ren al. [47] have proved that well-trained DNN encode just small number of salient interactions for inference under some common conditions.
45 have proved that, such a small number of salient interactions extracted from a sample can well mimic DNN's outputs on numerous masked samples.
Ren et al.
Li and Zhang 27 have discovered that salient interactions have considerable transferability and strong discrimination power.
However, the above properties cannot guarantee a clear correspondence between an interactive concept and a concept in human cognition. Up to now, we cannot mathematically formulate what is concept in cognitive science. Thus, there is still long way to unify the learning difficulty of a DNN and the cognitive difficulty of human beings.
Acknowledgments
This work is partially supported by the National Nature Science Foundation of China (62276165), National Key R&D Program of China (2021ZD01 1 1602), Shanghai Natural Science Foundation (21JC1403800,2122) 11.222211440000 1434600), National Nature Science Foundation of China (U19B2043). This paper is also partially supported by Huawei Technologies Inc.
References
[1] Alessandro Achille and Stefano Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE transactions on pattern analysis and machine intelligence, 40(12):2897-2055 2018.
[2] Sravanti Addepalli, Anshul Nasery, Venkatesh Babu Radhakrishnan, Praneeth Netrapalli, and Prateek Jain, Feature reconstruction from outputs can mitigate simplicity bias in neural networks. 2022.
10

---

[3] Rana Ali Amjad and Bernhard C Geiger. Learning representations for neural network- based classification using the information bottleneck principle. IEEE transactions on pattern analysis and machine intelligence, (2(9):2225-2233) 2019.
[4] Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with polynomial time algorithm for shapley value approximation. In International Conference on Machine Learning, pages 272-281. PMLR, 2019.
[5] Devansh Arpit, Stanistaw Jastrzæbski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pages 233-242. PMLR, 2017.
[6] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
[7] Chuanchuan Chen, Dongrui Liu, Changqing Xu, and Trieu- Truong. Saks: Sampling adaptive kernels from subspace for point cloud graph convolution. IEEE Transactions Circuits and Systems for Video Technology, 2023.
[8] 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.
[9] Xu Cheng, Xin Wang, Haotian Xue, Zhengyang Liang, and Quanshi Zhang. A hypothesis for the aesthetic appreciation in neural networks. arXiv preprint arXiv:: 2108.:::0000006666 2021.
[10] Huiqi Deng, Na Zou, Mengnan Du, Weifu Chen, Guocan Feng, and Xia Hu. A general taylor framework for unifying and revisiting attribution methods. arXiv preprint arXiv:2105.33841 2021.
[11) Huiqi Deng, Qihan Ren, Xu Chen, Hao Zhang, Jie Ren, and Quanshi Zhang. Discovering and explaining the representation bottleneck of dnns. International Conference on Learning Representations, 2022.
[12] Huiqi Deng, Na Zou, Mengnan Du, Weifu Chen, Guocan Feng, Ziwei Yang. Zheyang Li, and Quanshi Zhang. Understanding and unifying fourteen attribution methods with taylor interactions. arXiv preprint arXiv:2303.01500 2023.
[13] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
[14] Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: new perspective on generalization in neural networks. arXiv preprint vrXiv:190// 9999999 2019.
[15) Robert Geirhos, Hörn-K Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 1):665-673, 2020.
[16] 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.
[17] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[18] John C Harsanyi. A simplified bargaining model for the n-person cooperative game. Interna- tional Economic Review, 194-2294220, 1963.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
11

---

[20] Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. Transactions on Machine Learning Research, 2022.
[21] S Kormblith, M Norouzi, Lee, and G Hinton. Similarity of neural network representations revisited. In International Conference on Machine Learning, pages 3519-3522 PMLR, 2019.
[22] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[23] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
[24] Stephen Laurence and Eric Margolis. Concepts and cognitive science. 1999.
[25] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-2324, 1998.
[27] Mingjie Li and Quanshi Zhang. Does neural network really encode symbolic concept? In International conference on machine learning. PMLR, 2023.
[28] Chen Liu, Zhichao Huang, Mathicu Salzmann, Tong Zhang, and Sabine Süsstrunk. On the impact of hard adversarial instances on overfitting in adversarial training. arXiv preprint urXiv:2/12.07322 2021.
[29] Dongrui Liu, Shaobo Wang, Jie Ren, Kangrui Wang, Sheng Yin, Huiqi Deng, and Quanshi Zhang. Trap of feature diversity in the learning of mlps. arXiv preprint arXiv:2112.00980. 2021.
[30] Dongrui Liu, Chuanchaun Chen, Changqing Xu, Robert C Qiu, and Lei Chu. Self-supervised point cloud registration with deep versatile descriptors for intelligent driving. IEEE Transactions on Intelligent Transportation Systems, 2023.
[31] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference computer vision, pages 9730-3738, 2015.
[32] Scott M Lundberg, Gabriel G Brion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprini
2018
[33] 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
[34] Karttikeya Mangalam and Vinay Uday Prabhu. Do deep neural networks learn shallow learnable examples first? 2019.
[35] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.
[36] Ari Morcos, Maithra Raghu, and Samy Bengio. Insights on representational similarity in neural networks with canonical correlation. Advances in Neural Information Processing Systems, 31, 2018.
[37] 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: 2018.
[38] 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: 6098, 2013.
12

---

[39] Henning Petzka, Michael Kamp, Linara Adilova, Cristian Sminchisescu. and Mario Boley. Relative flatness and generalization. Advances in Neural Information Processing Systems, 34: 18420-18432, 2021.
[40] Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: A learning proclivity in neural networks. Advances in Neural Information Processing Systems, 34:1256-1277 2021.
[41] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[42] Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein. Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. Advances in neural information processing systems, 30, 2017.
[43] Jie Ren, Die Zhang, Yisen Wang, Lu Chen, Zhanpeng Zhou, Yiting Chen, Xu Cheng, Xin Wang, Meng Zhou, Jie Shi, et al. A unified game-theoretic interpretation of adversarial robustness. 35th Conference on Neural Information Processing Systems (NeurIPS 2021), 2021.
[44] Jie Ren, Zhanpeng Zhou, Qirui Chen, and Quanshi Zhang. Can we faithfully represent absence states to compute shapley values dnn? In The Eleventh International Conference Learning Representattinss, 2022.
[45] Jie Ren, Mingjie Li, Qirui Chen, Huiqi Deng, and Quanshi Zhang. Defining and quantifying the emergence of sparse concepts in dnns. In JEEE Conference on Computer Vision and Pattern Recognition, 2023.
[46] Qihan Ren, Huiqi Deng, Yunuo Chen, Siyu Lou, and Quanshi Zhang. Bayesian neural net- works avoid encoding complex and perturbation-sensitive concepts. Proceedings of the 40th International Conference on Machine Learning, pages 28889-28913, 2023.
[47] Qihan Ren, Jiayang Gao, Wen Shen, and Quanshi Zhang. Where we have arrived in proving the emergence of sparse symbolic concepts in ai models. arXiv preprint arXiv:2305. SoXiv:2305.0/93) 2023.
[48] Joshua Robinson, Li Sun, Ke Yu, Kayhan Batmanghelich, Stefanie Jegelka, and Suvrit Sra. Can contrastive learning avoid shortcut solutions? Advances in neural information processing systems, 34:4974-4986. 2021.
[49] Luca Scimeca, Seong Joon Oh, Sanghyuk Chun, Michael Poli, and Sangdoo Yun. Which shortcut cues will dnns choose? a study from the parameter-space perspective. arXiv preprint arXiv:2110.03095, 2021.
[50] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. Advances in Neural Information Processing Systems, 33:9573-999 9585, 2020.
[51] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28): 307-317, 1953.
[52] Wen Shen, Qihan Ren, Dongrui Liu, and Quanshi Zhang. Interpreting representation quality of dnns for 3d point cloud processing. Advances in Neural Information Processing Systems, 34: 8857-8870, 2021.
[53] Thomas Shuell. Cognitive conceptions of learning. Review of educational research, 56(4): 411-436, 1986.
[54] Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv: arXiv: 1703.00810, 2017.
[55] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 15X. 2014.
13

---

[56] Richard Socher, Alex Perelygin. Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing, pages 1631-1642, 2013.
[57] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pages
PMLR. 2020.
[58] Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley interaction index. arXiv preprint arXiv:2203.00870 2022.
[59] Xin Wang. Jie Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang, and Quanshi Zhang. A unified ap- proach to interpreting and boosting adversarial transferability. arXiv preprint 000:02000.04055,, 2020.
[60] 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 Representations, 2021.
[61] Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 11625-641, 2019.
[62] Teu Weng, Huan Zhang, Pin-Yi 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: 10578, 2018.
[63] Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint arXiv: 00003,6633, 2019.
[64] Zhiqin John Xu. Understanding training and generalization in deep learning by fourier analysis. arXiv preprint arXiv:1808. 04295, 2018.
[65] Li Yi, Vladimir G Kim, Duygu Ceylan, I-Chao Shen, Mengyan Yan, Hao Su, Cewu Lu, Qixing Huang, Alla Sheffer, and Leonidas Guibas. A scalable active framework for region annotation in 3d shape collections. ACM Transactions on Graphics (ToG), 35(6):1-12, 2016.
[66] Die Zhang, Hao Zhang, Huilin Zhou, Xiaoyi Bao, Da Huo, Ruizhao Chen, Xu Cheng, Mengyue Wu, and Quanshi Zhang. Building interpretable interaction trees for deep NLP models. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 14328 14337. AAAI Press, 2021.
[67] Hao Zhang, Sen Li, YinChao Ma, Mingjie Li, Yichen Xie, and Quanshi Zhang. Interpreting and boosting dropout from a game-theoretic view. In International Conference on Learning Representations, 2020.
[68] Hao Zhang, Yichen Xic, Longjie Zheng, Die Zhang, and Quanshi Zhang. Interpreting multi- variate shapley interactions in dnns. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference
Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 10877-10886. AAAI Press, 2021.
[69] Quanshi Zhang, Xin Wang. Jie Ren, Xu Cheng, Shuyun Lin, Yisen Wang, and Xiangming Zhu. Proving common mechanisms shared by twelve methods of boosting adversarial transfcrability. arXiv preprint arXiv:2207. /694, 2022.
[70] Huilin Zhou, Hao Zhang, Huiqi Deng, Dongrui Liu, Wen Shen, Shih-Han Chan, and Quan- shi Zhang. Concept-level explanation for the generalization of a dnn. arXiv preprint arXiv:2302.13091, 2023.
14

---

A Literature on the representation capacity of DNNs
Formulating and evaluating the representation ability of DNNS is emerging perspective to explain DNNs. Pascanu et al. [38] and Montufar et al. 35 evaluated the representation capacity of DNNs
based on the number of linear response regions. Kornblith et al. [21]. Raghu al. [42], and Morcos
et al. [36] analyzed representations similarity between DNNs by using canonical correlation analysis. Shen al. [52]. Chen et al. 77 and Liu al. 300 measured the quality of knowledge representations encoded in DNNs for point cloud processing. The information- bottleneck theory [54] quantified information encoded in DNNs, and was extended to improve the representation capacity of DNNs 1B Xu [64] and Xu et al. 633 explained the generalization of DNNs from the perspective of Fourier analysis. Furthermore, several metries were proposed to evaluate the robustness generalization capacity of DNNs, including the flatness of loss functions at minima 13] the stability of optimization
17 the CLEVER score [22] the stiffness [14, and the sensitivity metries 37
In contrast to previous empirical studies, we mathematically formulate concepts encoded by DNNs and theoretically prove that DNNs mainly learn simple concepts.
B Literature on interactions
Many studies investigated interactions between input variables of DNNs in recent years. Grabisch and Roubens [I6] proposed the Shapley interaction index to measure the interaction between players in cooperative game, based on the Shapley value [51]. Lundberg et al. 32 used the Shapley interaction
index to analyze tree ensembles. Sundararajan et al. [57] proposed the Shapley- Taylor interaction
index, and Tsai et al. [58] defined Faith- Taith-Shap, which was another interaction index.
In this paper, we use interactions between input variables of DNN to represent concepts encoded by the DNN. this way, We theoretically explain and empirically verify that DNN is easier to learn simple interactive concepts.
C Literature on the shortcut learning and simplicity bias of DNNs
Many studies focused on the underlying principles and limitations of DNNs. Geirhos al. [15). Robinson et al. [48], and Scimeca et al. [49] investigated the shortcut learning in DNNs. Le., DNNs may find decision rules that perform well on standard datasets, but fail to generalize to real-world scenarios. For example, DNNs successfully detected pneumonia by identifying hospital-specifie metal tokens on the scan, but they failed learn much about pneumonia and achieved low performance for scans from novel hospitals. Meanwhile, many studies proposed simplicity bias, i.e., standard training procedures for DNNs have a bias towards learning simple models [50] 20, 40). Specifically, DNNs
tend to learn low-rank embeddings 20 or simple features [50]
29
40
From the perspective of the simplicity bias, our study considers the definition of interactive concepts in [47], and analyzes the bias towards learning simple concepts. This work clarifies an exact form of the complexity of concepts that DNN difficult learn.
D Axioms and theorems for the Harsanyi dividend interaction
In this section, we introduce that the Harsanyi dividend interaction I(S) satisfies several desirable axioms and theorems.
The Harsanyi dividend interactions T(S) satisfies the efficiency, linearity, dunmy, symmetry, anonymity, recursive and interaction distribution axioms, follows.
(1) Efficiency axiom (proved by 18).. The reward of neural network can be decomposed into interaction effects of different contexts, i.e. w(N) Esex I(S).
(2) Linearity axiom. If we merge rewards of two neural networks w and the reward of model i.e. VS C N, u(S)= = (e(S) + ((S), then their interaction effects (S) and (S) can be represented as AS N, (.() (.) (S).
(3) Dummy axiom. If a variable
is a dummy variable, i.e. VS C NM) (i) = v(S) + v((i)), then it does not interact with other variables, v0 S ESCNN (SU
15

---

CETISUS
TV news
0.5
0.4
frequency
0.3
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
W/l1/mary [Mat]]
Wal/max, [0,11
Figure 7: The average histograms of absolute effects of interactive concepts encoded by five-layer MLPs.
(4) Symmetry axiom. Given input variables i,j e N. iA (ML.)) ( then VS ((t (i]) = I(S u (i)).
(5) Anonymity axion. For any permutations
.N, have VS C. (, where a (i ES), and the new model Tv defined by (#T)(=))==(S)) This indicates that interaction effects not changed by permutation.
(6) Recursive axiom. The interaction effects can be calculated recursively. Given E N and S S N M the interaction effect of the pattern Suf*} can be represented as the interaction effect of S with i minus the interaction effect without i, i.e. N ((SU(it) [(S] always pres
T(S is always present) denotes the interaction effect when the variable is always present as constant context, i.e. i is always present) --cs(-1))51114 u(L (i)).
(7) Interaction distribution axiom. This axiom shows how interactions are distributed for "interaction functions" [57]. The definition of the interaction function vr parameterized by a subset of variables otherwise, (T = 0. The function models pure interaction among the variables in T. because only if all variables in are present, the output value will be increased by c. The interactions encoded in the function ur satisfies I(T) and YS + T, I(S) 0.
T is given as follows. VS S N, if T C S, (S(
E
Sparsity of interactive concepts
In this section, conducted experiments verify the sparsity of interactive concepts. To this end, we computed effects Us of all 2" interactive concepts encoded by DNN following [45]. Specifically, trained five-layer MLP on the census dataset and the TV news dataset), respectively. For better visualization, we re-scaled effects of interactive concepts Us by |Us|/ maxs [Usr]. Moreover, the strength of effects are average over different samples in each dataset. Fig. shows histograms of absolute effects of interactive concepts.
F
Complexity of interactive concepts
Many previous studies ically, Given pre-trained DNN and masked sample æs, the multi-order interaction 7(m) (i, used in (59 67 is given as follows:
59 45 43 used multi-order interactions analyze DNNs. Specif-
7(m) (i.j) (ScNN6.0..s11mm0A66.....3
(1)
where Av j. S) = v( - v(z ((zsu())) + u v(ss). They consider that (i,))
reflects the collaboration with contextual variables (m pixels). In this way, the order measures the number of variables in S. Therefore, a low-order interaction denotes relatively simple collaboration between input variables with a small context S. In contrast, high-order interaction represents complex collaboration between input variables with large context S.
In this paper, we consider that the number of variables in an interactive concept S can measure the complexity of an interactive concept encoded by DNN, namely the order of the interactive concept, (mmplexit((S)oorderr
[S]. Thus, low-order concepts usually represent simple AND relationships among few input variables. comparison, high-order concepts often refer as relatively complex AND relationships among large number of input variables.
16

---

G Proof of Theorems
G.1 Proof of Theorem 2 in the main paper
Theorem 2. Given a neural network v and an arbitrary input sample x' E ER,, the network ousput can be decomposed by using the Taylor expansion (TO), i.e., v(z') = EsEN Imers Us [S, x=aa). In this way, according to Eq. (1), the interaction effect I(S]=') on the sample w' can be reformalated as follows.
1(S)x²) = -E TEQS Us. J(S, (()).
Here, J(S,m|a') Ihes (sign(z) b.) 2i=be denotes a Taylor expansion term of the degree æ
where the degree π { ( T. E T, E Nt; S. 0} and by is the baseline Tm 0"'((as)) value to mask the input variable z;. addition, Us.== I1 xd oz 0x. -iggs be)l*,
where zly denotes the sample whose input variables all masked. _ m..
Proof. Let denote the function on the right of Eq. (2 by I(S)xe), i.e.,
[(S)x') Σ nEQs (S,
(3)
We need prove that for any arbitrary input sample Va' E R., [(S]=²) = I(5]x²).
Actually, it has been proven in [66] and 45 that the Harsanyi dividend [(S]=') is the unique metric satisfying the faithfulness requirement mentioned in the main paper, i.e., satisfying
A YTCN, N, v(a't) = E T(S)=²)-
Thus, as long as we can prove that T(S]=²)) also satisfies the above faithfulness requirement, we can obtain f(S|=²) T(S)==).
To this end, we only need to prove i(S]=') also satisfies the faithfulness requirement in Eq. Specifically, given an input sample Væ' R", let consider the Taylor expansion of the network output v(r)) of an arbitrarily masked sample (' S N), which is expanded at z'g = Then, have
(b...., bu].
8Th (a'k) Or
VT ((47))
(aT) 1=1
b T
(5)
OZ
IT's
m2
where π E { { T..llii E N, E N} denotes the degree vector of Taylor expansion terms, and w E.= Ts. addition, b, denotes the reference value to mask the input variable 2;.
According to the definition of the masked sample w'y, we have that all variables in T' keep unchanged and other variables masked to the reference value. That is, V T, (wf), Iys i T, (æf); b.
Hence, we obtain vi g T, [(rf)) b.] = 0. Then, among all Taylor expansion terms, only terms corresponding degrees in the zero. Therefore, Eq. (5) can be rewritten as
{[=I,-.. To] E T, E Nivi & T, क. 0} may not be
8Th ((()())))))))
NT'N, v(2's)
Σ TEP
IP n.. dr 1 Or
II 1 6.)* SET
(6)
We find that the set P can be divided into multiple disjoint sets follows, P = UsgrQs, where Qs = ([T........). /Vi E S,m, m E :Ni S, n; = 0}. Then, we can derive that
8T (((() Oa
YTCN, v(xr)) Σ Σ
II
b.)
SCT REQs
EES
Σ SCT RCQS
Σ
7
0t (
II
(6.)*
(8.
Ri. de
SE
IES
tamed USS.
termed
x(
where T E a pre-defined constant and d sign(a; - r:) E (-1,1) is a sign function satisfying
22m 1 (m = Ei - m.). Then, Eq. (7) can be re-written
N, 0(xt)
Σ
Σ
Us.- J(S, Σ i(S)x').
(8)
SCT MEQS
SCr
17

---

Thus, [(S]=²) satisfies the faithfulness requirement in Eq. when f 2%
Therefore, Theorem 2 holds.
G.2 Proof of Theorem 3 in the main paper
Theorem 3. Let us add a Gaussian perturbation e (N to the input sample æ. Let us first consider the case with the lowest degree it = ( At] E Qs. satisfying that vi E S, 3, 1; S, = The mean and variance of J(S, #|x + E) over the Gaussian perturbution e are given as
(S + e)] Us
Var. c)] = (1 (L+()))))''
Furthermore, for the more general case with an arbitrary degree π E Qs = (M Fn ViES, Ni; $ S. = 0}, the mean and variance of J(S, π| + e) are computed as
E. [SS, x| + E. III ies (1 (1+ </T)"'), Var, (J(, x + e)]
Var.
(1+ +c/T)"
Proof. If we only consider Taylor expansion term of the lowest degree, then [(S)=') Us.* J(S, it)",, where J(S, t x²) lles sign( b;) -b-b.
Let us add Gaussian perturbation e (N0, I to the input sample æ. Then, we have [(S]a x + + Us.*
JJS, + e)
sign(a; + bi) 24 + Ei b,
J(S, n x +
II iES
sign(2; + -b)) bi + sign(2; + b,) -b,) 4
II iE
According to the setting of the baseline value, we have Vi E S. - b, E {-r,T)- In Section 2.2, we have assumed that the perturbation is small, i.e., vi E S, S T. In this way, have sign(x; + 6, - b.) = sign(x, - bi), and we can obtain
sign(a; b,) b + sign(2; 6,) Si
II iES
(10)
II iES
(1 + sign(e: - -b:) +)
[ E.
II
[1 sign(x; -b,) b.). =)
LieS
(11)
[Jrr]](S,F +c] = Var
II
sign(1; - -bi) (
LES
Since sign(r; - b,) E (-1,1), we have + sag b.) N(1, (O17)))
Proposition 1. If random variables X1, X2, Xx independent of each other, then
E|XiX2...- .x] II= E[X,), and Var[XIX2--. ..]] (E|x,j VarlX.|²)
According to the above proposition, we have
Bc[J(S, * +
II =
$ES
Var Var_[J(S, + +e]]
II
11 + (a/T)²)
II 1
(12)
(1 11 (a/T)2) [s]
18

---

Therefore,
Ex[ + 6)] = E. J(S, # l + +e]] - =Us,
[ + c)] Var,[Us,* J(S, オ| x <)] -US. (11+0117))6111
(13)
According to Theorem 2, given an arbitrary input sample x', we have
bj
J(S, π x
II iEs sign(xr b,)
(14)
Let us add Gaussian perturbation NO, I² to the input sample In this way, have
sign( + - b.) 24 + co b
JSS π a t) = II
iE
(15)
b,
sign( + - b.) 4 x
II iES
sign(a; + - b.)
According to the setting of the baseline value, Vi E S, - by E [-T,T]. We assume that the perturbation is small, Le., Vi S, lel In this way, sign (xt + e, bi) sign(xi 6,), and can obtain
J(S, n. + E)
II
sign( b.) Ht -
sign(x; - b,) 5i - (16)
iES
III
T [ + sign(x; b.) -
i
(JS, c)] E. II
1 sign(x; b.) 4
LieS
(17)
Var, [[S, E)]
Var.
II LieS
[ + sign(a; - b1) E/
Since Vi E S, 6, is independent of each other, according to Proposition 1 and Eq. 17 we have
Ee [[(, x + +)]
II Re;
[1 + sign b.) 4
iES
II Ee, (1 (i+sigu(z; sign(x; 6,) 4
27.
Bes [11 sign(x; b.)
4 T. ))
Vare x
7
iE9
EES
(18)
Since sign(a; by) E {-1,1}, we have Ee, (1 sign(x; - b.) - 4)
Re, [11 + [) Vk
N Therefore, we obtain
[11
Ef x.
Eg[J(S, x x [
Er;
-
iE9
1+ E -
E2
LiES
+6] +
II E,
(1+ E
Er,
[1 +1+ )
E1
iE9
1E
Vars
II Lie
1
m
19

---

G.3 Proof of Theorem in the main paper
Theorem 4. Given an arbitrarily masked sample ær (VT S N), the function Cs(ær) defined above can well fit the binary activation state of the concept S in the sample
VTC C(S(ar) = II A.(xT) = 1(8 T);
(19)
where A.(Tr) E 10 denotes whether the variable is present A:(ær) = 1 or being masked A((rr) = the sample ar.
Proof. We know that the function of the activation state on arbitrary sample x' is given by
Cs(a'' EnErs JS, mt(=)/UUs.
(20)
sign(a, - b,) x4
where J(S, M (2=)=
II iEs
7
Specifically, now consider masked sample æy, and we will prove that Cs(æT) 1(S S T). We consider the following two cases.
Case 1: S Ç T. Then there exists some j E S S\Z T. Since j & T. according to the masking rule of the sample ær, we have (IT)) bj = 0. Since j E S, we have
sign(((rr); -r;) ( bi
n
VT E Qs J(S, π (T)))TT)=
II iEs
(21)
In this way, we have Cs(xr) = EnEQs JS, π aT/TT//U = 0.
Case 2: C T. In this case, Vi S. we have i E T. According to the setting of the reference value in Section 2.3 of the main paper, we have (ær); b, {T, -T). Then we have sign((æT)) b,)
(mr)e-be 1, E S. This further implies that
VT Qs: J(S,T(a1) = II.Es (sigu((or): - b,). (IT))
=1
(22)
Therefore, we can derive
Cs(Er) = Emegs
TEQS U
(23)
Recall that Us a(S Iiss (sign(z; r.)) x: mi=b) 1, because 24. by E (r,- So actually, we have
Eners Us. (S, rr)r), in which J(S,Tla)
Us Σ TEQs
Us.
(24)
Therefore, Cs(xT) Emeqs US. 1. Combining the two cases, we can conclude that Cs( -T) -lies A((
G.4 Relation between interactive concepts and multi-order interactions
In this section, we derive that high-order interactive concepts (computed via the Harsanyi dividend [8] can considered as elementary components for high-order interactions used in 43].
Given pre-trained DNN and a masked sample æs, the multi-order interaction ((m) used in
43 is given as follows:
(im Esgn (sc
(25)
where Au(i,j,S) (a0ps))=(((suu) v( ( v( v( + w(xs).
Let Aer(S) Excr(- ( denote the marginal benefit of variables TC N S given the environment this way, Avr(S) can be represented the sum of interaction effects inside T' and sub-environments of S, i.e. (vr(S) ( (4).
20

---

Thus, the ((m) (2. can be represented as follows,
7( (i.j) (4.CN (.
-ESCNMH..),11=m Σ ((,U0
LCS
Σ
Σ
I(LU (i,))
(LNEE LCS
18
E
Σ
n2-2
(CN(( Sm
LESCNita 18
m
E
(1,i)
(CN(E
Sm
Σ
I(L (
Therefore, prove that 7(m) (1,5) Er
LLCNVGa) 1/
(i.i))
G.5 Theoretical connection between variance and learning difficulty
There is close connection between the variance of interactive concepts and the learning difficulty. In fact, a similar connection has been discovered by [46]. The theoretical connection is proved as follows. Specifically, we simplify the learning of DNN into a linear regression problem. In this very simple setting, we assume each i-th concept encoded by the DNN to be a specific feature, and use fr to represent the triggering (presence) state of the i-th concept in training sample. Because according to Eq. (9) in the main paper, the network output v(-) is the sum of a small number of salient interactive concepts, roughly simplify and rewrite the inference output of the DNN the following linear function
y y=w T wifh fi ..... +... wafa where f = [A. T Then, wy can be viewed as the strength of the DNN encoding the i-th interactive concept. In this way, if wi O, the DNN does not learn the i-th interactive concept.
We suppose that training samples are sampled from ~ P(f) = N [ E²²) and y denotes the ground truth label. Specifically, μ [Pi, P2.... Pa]" and Σ diag(o?. 0z ..,.....)) 03).
The toy regression problem can be formulated as follows,
L = (w f-y') -²)²
(26)
We derive the optimal weights to the above regression task in three steps.
Step 1. The optimal weight wy for the regression problem in Eq. (26) is computed by
1
V1 visis d, w; det del K,,... KK-1, S. ".t Ka)
(27)
where K = pn T + こ. < = y and K, denotes the j-th column of the matrix K.
Step 2. We further prove that for the optimal w, have
|wy]
|p//0
v1 i,j < d,
(28)
Mj/o
Step Based on Step 2, we can derive |usgl x [1/a2], where w; denotes the strength of DNN encoding the i-th interactive concept. |w]] x [1/oz indicates that the learning effect of the i-th interactive concept is inversely proportional to the variance of the i-th interactive concept. Therefore, interactive concepts with high variances (high-order interactive concepts) more difficult to learn.
21

---

H Experimental Settings
Training details. We trained AlexNet 23
VGG-11 [55, ResNet-11/20 19] on the CIFAR-10
respectively. We also trained a five-layer MLP on the UCI census dataset (namely census dataset) and the UCI TV news dataset (namely TV news dataser) [6], respectively. Each layer of the MLP contained 100 neurons. We trained each neural networks for 200 epochs with SGD optimizer.
dataset [22] and the Tiny ImageNet dataset 25
Sampling details. Since, the computational cost of T(S[x) was intolerable in real implementation, applied the sampling-based approximation method in [67] to calculate T(S az). Due the high dimension of image data (e.g. 224 x 224 for ImageNet), we uniformly split the input image into 8 8 patches. Furthermore, we random sampled 12 patches and considered these patches as input variables for each image. The remaining 52 patches are set to the baseline value.
Implementations details. Here, introduce how measure B(S) and k(() in Section 2.3. On the Tiny ImageNet dataset, we randomly sampled 100 training images. These training images were randomly sampled from different 10 classes. On the CIFAR-10 dataset, we randomly sampled 10 training images from each class. For tabular datasets, we randomly sampled 50 training samples from each class. For image datasets, we
2 when the input data normalized by its standard deviation. For tabular datasets, we set = when the input data is normalized by its standard deviation. In this way, we the baseline 6; mar(2; - T. if x; μt, and we the baseline b, min( + T, (A), if 24 14i For Gaussian perturbation c, we set a = 0.02. Besides, for each training sample, we randomly sampled five Gaussian perturbation with five different seeds, respectively.
Adversarial attack. Here, introduce how measure ( in Section 3.1. For tabular datasets, randomly sampled 50 training samples from each class from the training set. On the Ting-ema randomly sampled
dataset, we randomly sampled 100 training images. These training images from different 10 classes. On the CIFAR-10 10 dataset, we randomly sampled 10 training images from each class. We used the lxc untargeted PGD attack by following 33 in which the constraint 16/255, and the attack was conducted with 5 steps with the step size 3/255.
22


Reviews:
[{"review_id": "zyiFSlea8T", "reviewer": "Reviewer_B4Wy", "summary": "The paper provides theoretical results explaining why simpler concepts are easier to learn for neural networks. The paper refers to prior work on interactive concept models, which define a concept as a subset of input features, and defines the complexity of each concept as the number of features contained within it. The main theoretical results of the paper argue that the variance of a concept and its interaction under noisy input increases exponentially with the size or complexity of the concept. Hence, more complex concepts are more likely to be influenced by small variations in the data. The paper then presents empirical evidence supporting these claims, and shows empirically that lower order concepts are more stable and learnt quicker than higher order ones. ", "questions": "1. Can the authors make the connection between variance and learning difficulty more concrete theoretically?", "limitations": "See weaknesses.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes an interesting analysis around interactive concepts.\n2. The empirical evaluation backs the claims of the paper.", "weaknesses": "1. The theoretical analysis does not match the claims of the paper's abstract. The theory only explains higher variance for higher order concepts, but the connection between higher variance and difficulty of learning is not made explicit theoretically. \n2. Several lines of work around shortcut learning and simplicity bias of networks are missing from related works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper. We will try our best to answer all your questions. Please let us know if you still have further concerns, or if you are not satisfied with the current responses, so that we can further update the response ASAP.\n\n---\nQ1: Ask for the theoretical connection between variance and learning difficulty. \"... the connection between higher variance and difficulty of learning is not made explicit theoretically.\"\n\nA: Thank you for your insightful comments. In fact, this is a great challenge. Up to now, there is no certificated strict correspondence between the aforementioned interactive concepts and neurons in the DNN. Therefore,  in order to derive an analytic connection between variances and learning difficulty, let us discuss our recent findings in the difficulty of learning different interactive concepts. Specifically,  we simplify the learning of a DNN into a linear regression problem. In this **very simple** setting, we assume each $i$-th concept encoded by the DNN to be a specific feature, and use $f_i$ to represent the triggering (presence) state of the $i$-th concept in a training sample. Because according to Eq. (9) in Line 200, the network output $v(\\cdot)$ is the sum of a small number of salient interactive concepts, we roughly simplify and rewrite the inference output of the DNN as the following linear function\n$$y=w^\\top  f=w_1f_1+\\cdots +w_df_d ,$$\nwhere $f=[f_1,\\cdots, f_d]^\\top$. Then, $w_i$ can be viewed as the strength of the DNN encoding the $i$-th interactive concept. In this way, if $w_i \\approx 0$, the DNN does not learn the $i$-th interactive concept.\n\nWe suppose that training samples are sampled from $f \\sim P(f) = N(\\mu, {\\Sigma}^2)$ and $y^*$ denotes the ground truth label. Specifically, $\\mu=[\\mu_1,\\mu_2,...,\\mu_d]^{\\top}$ and $\\Sigma={\\rm diag}(\\sigma_1^{2},\\sigma_2^{2},...,\\sigma_d^{2})$.\n\nThe toy regression problem can be formulated as follows,\n$$L=E_{P(f)}[\\dfrac{1}{2}(w^\\top  f-y^*)^2]$$\nIn this way, we can derive the optimal weights to the above regression task $|w_i| \\propto |1/\\sigma_i^2|$, where $w_i$ denotes the strength of the DNN encoding the $i$-th interactive concept. Please see Fig. 2 in *the response pdf file* for the proof overview (due to the limit of the page number). This is our recent finding, and we will add the full proof to the appendix if the paper is accepted. $|w_i| \\propto |1/\\sigma_i^2|$ indicates that the learning effect of the $i$-th interactive concept is inversely proportional to the variance of the $i$-th interactive concept. Therefore, interactive concepts with high variances (high-order interactive concepts) are more difficult to learn.\n\nIn fact, it is difficult to analyze the exact dynamics of learning concepts in much more complex real-world settings. We only analyze the connection between variances and learning difficulty in the above very simplified toy setting. Nevertheless, the above analysis still provides conceptual and analytic insights into the relation between variances and difficulty of learning.\n\n\n---\nQ2: \"Several lines of work around shortcut learning and simplicity bias of networks are missing from related works.\"\n  \nA: We will cite and discuss papers [cite1-6] for shortcut learning and simplicity bias in the related work section in the revised paper. From the perspective of the simplicity bias, our study considers the definition of interactive concepts in [26], and analyzes the bias towards learning simple concepts. More crucially, we try to induce an approximate analytic explanation from the common intuition of the bias, based on the theory of game-theoretic interactions. This work clarifies an exact form of the complexity of concepts that a DNN is difficult to learn.\n\n[cite1] Shah H, Tamuly K, Raghunathan A, et al. The pitfalls of simplicity bias in neural networks[J]. Advances in Neural Information Processing Systems, 2020, 33: 9573-9585.  \n[cite2] Huh M, Mobahi H, Zhang R, et al. The low-rank simplicity bias in deep networks[J]. arXiv:2103.10427, 2021.  \n[cite3] Geirhos R, Jacobsen J H, Michaelis C, et al. Shortcut learning in deep neural networks[J]. Nature Machine Intelligence, 2020, 2(11): 665-673.  \n[cite4] Pezeshki M, Kaba O, Bengio Y, et al. Gradient starvation: A learning proclivity in neural networks[J]. Advances in Neural Information Processing Systems, 2021, 34: 1256-1272.  \n[cite5] Scimeca L, Oh S J, Chun S, et al. Which shortcut cues will dnns choose? a study from the parameter-space perspective[J]. arXiv preprint arXiv:2110.03095, 2021.   \n[cite6] Addepalli S, Nasery A, Radhakrishnan V B, et al. Feature Reconstruction From Outputs Can Mitigate Simplicity Bias in Neural Networks[C]//The Eleventh International Conference on Learning Representations. 2022."}, {"review_id": "Z0LtNiqh0R", "reviewer": "Reviewer_DenZ", "summary": "In this paper, the authors proved several theoretical results that formalized the idea that simple interactive concepts achieve a smaller variance in their interaction effects in the face of Gaussian perturbations, and are thus more stable and easier for deep neural networks (DNNs) to learn. The authors also provided experimental verifications to verify their theoretical results, and pointed out the connections between their theoretical work and previous findings on DNN learning.", "questions": "How can we leverage the results and theoretical insights from this work to design better algorithms for training DNNs, or help DNNs learn complex concepts?", "limitations": "Since I did not find a section on the limitations of their work, the authors are encouraged to include a discussion of the limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a rigorous theoretical framework for understanding concept learning of DNNs.\n- The paper formalizes the idea of conceptual complexity and establishes a formal link between conceptual complexity and learning difficulty of DNNs.\n- The paper sheds light on previous heuristic findings on DNN learning, and advances our understanding of DNNs.", "weaknesses": "- While the theoretical derivations of the results in the paper are impressive, I am not sure how the insights from a theoretical understanding of DNN learning could help us train better DNNs. In other words, I am not certain about the practical implications and contributions of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper. We will try our best to answer all your questions. Please let us know if you still have further concerns, or if you are not satisfied with the current responses, so that we can further update the response ASAP.\n\n---\nQ1: Ask how to use theoretical insights of this paper. \"While the theoretical derivations of the results in the paper are impressive, I am not sure how the insights from a theoretical understanding of DNN learning could help us train better DNNs ... \"How can we leverage the results and theoretical insights from this work to design better algorithms for training DNNs, or help DNNs learn complex concepts?\"\"\n\nA: A good question. Analyzing the representation flaw of DNNs has become an emerging direction in recent years, *e.g.,* shortcut learning [cite1,2] and simplicity bias of DNNs [cite3,4]. For decades, researchers have realized that it is easy for an AI model to encode simple concepts, and it is more difficult to encode complex concepts. However, there are two core challenges for future development in this direction.   \n(1) How to define the concepts encoded by a DNN is still an open problem. There is no formal and universally accepted definition of concepts so far.   \n(2) It is still a challenge to provide analytic connections between the complexity of concepts and the difficulty of learning concepts.   \nTherefore, in this paper, we theoretically explain the trend of DNNs learning simple concepts. Specifically, we prove that low-order interactive concepts in the data are much more stable than high-order interactive concepts, which makes low-order interactive concepts more likely to be encoded.\n\nThe above theoretical analysis provides a specific form of the complexity of concepts that boosts the learning difficulty. Thus, in the future, we may design new neural networks, whose architectures strengthen the capacity of encoding complex (high-order) concepts and meanwhile boost the stability of these concepts (to improve the quality of concepts). However, there is still a large gap between the breakthrough in theory and achievements in practice.\n\n[cite1] Geirhos R, Jacobsen J H, Michaelis C, et al. Shortcut learning in deep neural networks[J]. Nature Machine Intelligence, 2020, 2(11): 665-673.  \n[cite2] Scimeca L, Oh S J, Chun S, et al. Which shortcut cues will dnns choose? a study from the parameter-space perspective[J]. arXiv preprint arXiv:2110.03095, 2021.  \n[cite3] Shah H, Tamuly K, Raghunathan A, et al. The pitfalls of simplicity bias in neural networks[J]. Advances in Neural Information Processing Systems, 2020, 33: 9573-9585.  \n[cite4] Huh M, Mobahi H, Zhang R, et al. The low-rank simplicity bias in deep networks[J]. arXiv:2103.10427, 2021.\n\n---\nQ2: \"Since I did not find a section on the limitations of their work, the authors are encouraged to include a discussion of the limitations.\"\n  \nA: Thanks a lot. We will follow your suggestions to add a new section to discuss the limitation of this paper. The limitation is that there are very few ways to define and examine what is a ''concept.\" In this paper, we only use the following three properties to support the faithfulness of using sparse salient interactions as concepts encoded by the DNN.   \n$\\bullet$ [26] proved that a well-trained DNN would encode just a small number of salient interactions for inference under some common conditions. See Line 83.    \n$\\bullet$ [24] proved that, such a small number of salient interactions extracted from a sample $x$ could well mimic DNN’s outputs on numerous masked samples {$x_T | T\\subseteq N $}. See Theorem 1.  \n$\\bullet$ [15] have discovered that salient interactions have considerable transferability and strong discrimination power. See Line 103.\n\nHowever, the above properties cannot guarantee a clear correspondence between an interactive concept and a concept in human cognition. Up to now, we cannot mathematically formulate what is a concept in cognition science. Thus, there is still a long way to unify the learning difficulty of a DNN perspective and the cognitive difficulty of human beings."}, {"review_id": "rj1qShcbIP", "reviewer": "Reviewer_jTKY", "summary": "This paper explores the problem of the learning difficulty of interactive concepts. The paper theoretically shows that a DNN is more likely to encode simple interactive concepts (with fewer variables in the interaction). Low-order interactive concepts are more stable to data noises and they exhibit consistent effects on the inference scores of different samples. Experiments on various DNN architectures using image and tabular datasets are done to validate the results. The paper also compares and relates their findings with existing theoretical and empirical works on trying to analyze and explain DNNs.", "questions": "See weaknesses.", "limitations": "The paper does not provide a limitations section. Perhaps authors can explain the assumptions behind the proof and its impacts on real-world applications. The paper does not provide any ethical statement in the paper nor do I think it is needed.\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "[S1] The paper presents a novel contribution by deriving an approximate analytical solution to the variance of interactive content's effects w.r.t data noise and showing that it increases along the order of concepts in an exponential manner.\n\n[S2] The proof provides novel insights explaining DNNS. The findings are useful in explaining existing empirical works such as adversarial robustness results for different ordered concepts, why adversarial training is faster for certain concepts, etc\n\n[S3] Experiments are conducted on four types of architectures and two datasets. The results are consistent with the theoretical findings.\n\n[S4] Paper is well-written and covers various existing works.", "weaknesses": "[W1] Authors claim that easy samples mainly contain low-order interactive concepts. Is there existing work showing that this claim is true or can authors show it? How is \"easy\" defined? Is it based on how \"easy\" (fast?) is it for a specific network to learn or is it a more universal concept?\n\n[W2] How was the variance value used in the experiments chosen? What is the impact if it is changed? What is the impact if a different type of noise is used?\n\n[W3] Could authors experiment on newer architectures such as transformers? What about textual data input?\n\n[W4] Can you provide a limitation/broader impacts section? E.g., Are there any assumptions? Does the definition of \"simplicity\" match real-world applicability? What can/cannot this new understanding do towards guiding the design of future networks, etc..", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts on the review of this paper. We will try our best to answer all your questions.\n\nPlease let us know if you still have further concerns, or if you are not satisfied with the current responses, so that we can further update the response ASAP.\n\n---\nQ1:  \"Authors claim that easy samples mainly contain low-order interactive concepts. Is there existing work showing that this claim is true or can authors show it? How is \"easy\" defined? ...\"\n\nA: A good question. The claim in Line 313 that *easy samples mainly contain low-order interactive concepts* is actually supported by the heuristic findings in [4]. Cheng et al. [4] discovered that OOD samples, which were considered as difficult samples, usually contained much more high-order interactions than normal samples (simple samples). Besides, Mangalam and Prabhu [20] defined easy samples as training samples that could be correctly classified by shallow machine learning models, such as SVM. To this end, we conducted **new experiments**, in which for each $l$-th layer of an MLP, we learned a specific linear classifier $y=softmax(M * f_l)$ to use the $l$-th layer's feature $f_l$ for classification. Because high layers mainly encoded more complex features than low layers, in this experiment, we tested whether the classifier based on more complex features (in higher layers) also encoded more high-order concepts. Then, we quantified the interactions between input variables encoded by different classifiers in different layers. Fig. 1 in *the response pdf file* shows that higher layers usually encoded more complex interactions. This also partially supported the above claim.\n\n---\nQ2:  \"How was the variance value used in the experiments chosen? What is the impact if it is changed? What is the impact if a different type of noise is used?\"\n\nA: Thanks. We set the variance of noise $\\sigma^2=0.02^2$ in all experiments in the main paper. We have followed your suggestions to conduct **two new experiments** to answer your questions. These two experiments were conducted on the AlexNet trained on the CIFAR-10 dataset.\n\n**Experiment 1**.  We tested the instability of interactive concepts $\\kappa(S)$ (defined in Line 234) by setting input noises with different variances $\\sigma^2$. We added Gaussian perturbations $\\epsilon \\sim  \\mathcal{N}(0, {\\sigma}^2I)$ to each training sample. Table 1 in *the response pdf file* verifies that high-order concepts were less stable than low-order concepts. This claim was not affected by the change of $\\sigma^2$.\n\n**Experiment 2**. As you requested, in this experiment, we computed the instability $\\kappa(S)$ (defined in Line 234) by applying two different types of noises, *i.e.,* Gaussian perturbations $\\epsilon \\sim  \\mathcal{N}(0, {0.02}^2I)$ and uniform perturbations $\\epsilon \\sim  \\mathcal{U}(-0.02, +0.02)$ on each training sample. Table 2 in *the response pdf file* verifies that the type of noises did not affect the claim that high-order concepts were less stable than low-order concepts.\n\n---\nQ3: \"Could authors experiment on newer architectures such as transformers? What about textual data input?\"\n\nA: Thanks. We have followed your suggestions to **conduct new experiments** on the BERT (a classical transformer-based model) on textual data. Specifically, we used the pre-trained BERT model [c1] and fine-tuned it for the sentiment classification task on the SST-2 dataset. We added Gaussian perturbations $\\epsilon \\sim  \\mathcal{N}(0, {0.02}^2I)$ to the token embedding of each training sample. We computed the instability of the interactive concept $\\kappa(S)$. Table 3 in *the response pdf file* verifies that the interaction effect of the high-order interactive concept was usually less stable than that of the low-order interactive concept on textual data.\n\n[c1] J. Devlin et al. “Bert: Pre-training of deep bidirectional transformers for language understanding,” in NAACL-HLT, 2018. \n\n---\nQ4:  \"Can you provide a limitation/broader impacts section?...\"\n\nA: Thanks a lot. We will follow your suggestions to add a new section to discuss the limitation of this paper. The limitation is that there are very few ways to define and examine what is a ''concept.\" In this paper, we only use the following three properties to support the faithfulness of using sparse salient interactions as concepts encoded by the DNN.   \n$\\bullet$ [26] proved that a well-trained DNN would encode just a small number of salient interactions for inference under some common conditions. See Line 83.    \n$\\bullet$ [24] proved that, such a small number of salient interactions extracted from a sample $x$ could well mimic DNN’s outputs on numerous masked samples {$x_T | T\\subseteq N$}. See Theorem 1.  \n$\\bullet$ [15] have discovered that salient interactions have considerable transferability and strong discrimination power. See Line 103.\n\nHowever, the above properties cannot guarantee a clear correspondence between an interactive concept and a concept in human cognition. Up to now, we cannot mathematically formulate what is a concept in cognition science. Thus, there is still a long way to unify the learning difficulty of a DNN perspective and the cognitive difficulty of human beings."}, {"review_id": "SSYpZ7tdbm", "reviewer": "Reviewer_otLW", "summary": "Theoretical work using prior work defining \"interactive concepts\" to quantify difficulty of concepts and show why DNNs prefer learning simpler concepts by approximating the concept learning process for DNNs by linear regression. ", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) Useful theoretical contribution that clearly uses interactive concept idea to formally define \"easy\" concepts and show why DNNs prefer to learn these shortcuts \n\n2) Well-written and easy to follow\n\n3) Empirical proof showing that higher order interactive concepts are more vulnerable to noise in the data", "weaknesses": "1) More discussion can be provided on why this particular experiment designed by the authors is a good way to verify the claims made. \n\n2) More clear explanation of what is the contribution of prior work and that of this work. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your great efforts. We are glad that all reviewers have given us positive comments. We will try our best to answer all your questions.\nPlease let us know if you still have further concerns, or if you are not satisfied with the current responses, so that we can further update the response ASAP.\n\n---\nQ1: More discussion can be provided on why this particular experiment designed by the authors is a good way to verify the claims made.\"\n\nA: Thanks. We have followed your suggestions to discuss more about the design of experiments w.r.t. the verification of our claims. Specifically, we have three main claims, *i.e.,* high-order concepts are usually less stably extracted under data noises, are learned more slowly, and are more sensitive to adversarial attacks. All these three claims have been verified in experiments, which proved the difficulty of learning high-order concepts.\n\n**For Claim 1**: *high-order interactive concepts are less stably extracted under data variations than low-order interactive concepts.* The experiment in Line 232 was designed to verify this claim in a direct manner. We directly quantified the instability metric $\\kappa(S)$ of concepts of different orders. We found that high-order concepts were less stable under data variations than low-order concepts, which verified Claim 1.\n\n**For Claim 2**: *Fast learning of low-order concepts.* The experiment in Line 253 was designed to verify this claim in a direct manner. We extracted interactive concepts from the finally-learned DNN $v_{\\text{final}}(x)$, and extracted interactive concepts from the DNN $v_{t}(x)$ trained after $t$ epochs. A high Jaccard similarity between $s$-order concepts extracted from $v_{t}(x)$ and $s$-order concept extracted from $v_{\\text{final}}(x)$ would indicate the fast learning of $s$-order concepts, because many concepts had been already learned after $t$ epochs. Fig. 5 in the main paper shows that low-order concepts usually had higher Jaccard similarity during the learning process, which verified Claim 2.\n\n**For Claim 3:** *High-order interactive concepts are more sensitive to adversarial attacks.* The experiment in Line 285 was designed to verify this claim in a direct manner. We directly quantified the sensitivity metric $\\alpha(S)$ of concepts of different orders under adversarial attacks. We found that high-order concepts were more sensitive to adversarial attacks than low-order concepts, which verified Claim 3.\n\n---\n\nQ2: '' More clear explanation of what is the contribution of prior work and that of this work.\"\n\nA: We have followed your suggestions to clarify the distinctive contribution of this work over previous studies.\n\nPrevious papers [2, 16, 20] mainly study the phenomenon that *DNNs easily learn simple concepts* in an experimental manner. Thus, the easy learning of simple concepts is still a common intuition without a clear theoretical formulation or analytic explanation, because how to define a concept encoded by a DNN is still an open problem.\n\nIn comparison, thanks to the recent progress in [26], we follow its mathematical definition of interactive concepts. This enables us to provide an explicit theoretical connection between the complexity of concepts and the difficulty of learning concepts. Specifically, we derive an approximate instability for interactive concepts of each specific order, which reveals the high instability of high-order concepts. Thus, our research provides an approximate yet analytic explanation of the difficulty of learning high-order concepts."}]

Author rebuttal:
Thanks for all reviewers' great efforts and comments. This paper has received rating of a *strong acceptance*, a *weak acceptance*, and two *borderline acceptance*. We are glad to answer all your questions and conduct **new experiments as requested.**

**Please let us know if you still have further concerns, so that we can update the response as soon as possible.**

Meta-review: The reviewers were all in agreement that the paper presents interesting, novel and significant technical contributions on better understanding neural network learning and should be a good fit for NeurIPS.
Decision: Accept (poster)