Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs
Authors: Qihan Ren
Jiayang Gao
Wen Shen
Quanshi Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Explainable AI
Neural networks
Symbolism
Primary area: visualization or interpretation of learned representations
TL;DR: This study proves the emergence of sparse interaction primitives under three common conditions.

Abstract: This study aims to prove the emergence of symbolic concepts (or more precisely, sparse primitive inference patterns) in well-trained deep neural networks (DNNs). Specifically, we prove the following three conditions for the emergence. (i) The high-order derivatives of the network output with respect to the input variables are all zero. (ii) The DNN can be used on occluded samples, and when the input sample is less occluded, the DNN will yield higher confidence. (iii) The confidence of the DNN does not significantly degrade on occluded samples. These conditions are quite common, and we prove that under these conditions, the DNN will only encode a relatively small number of sparse interactions between input variables. Moreover, we can consider such interactions as symbolic primitive inference patterns encoded by a DNN, because we show that inference scores of the DNN on an exponentially large number of randomly masked samples can always be well mimicked by numerical effects of just a few interactions.

Published as a conference paper at ICLR 2024
WHERE WE HAVE ARRIVED IN PROVING THE EMER- GENCE OF SPARSE INTERACTION PRIMITIVES IN DNNS
Qihan Ren, Jiayang Gao, Wen Shen, Quanshi Zhang* Shanghai Jiao Tong University (zenqihan, giy0515, adashen, zqs1022) jtu. edu.e.du.c cn
ABSTRACT
This study aims prove the emergence of symbolic concepts (or precisely, sparse primitive inference patterns) in well-trained deep neural networks (DNNs). Specifically, we prove the following three conditions for the emergence. (i) The high-order derivatives of the network output with respect to the input variables are all zero. (ii) The DNN can used on occluded samples and when the input sam- ple is less occluded, the DNN will yield higher confidence. (iii) The confidence of the DNN does not significantly degrade on occluded samples. These conditions are quite common, and we prove that under these conditions, the DNN will only encode a relatively small number of sparse interactions between input variables. Moreover, we can consider such interactions as symbolic primitive inference pat- terns encoded by a DNN, because we show that inference scores of the DNN on exponentially large number of randomly masked samples can always be well mimicked by numerical effects of just few interactions. The code is available at httpp:://githue com
xa lab/ http//nneractiiio ion sparsssty
INTRODUCTION
In the field of explainable AI, one of the fundamental problems is whether the inference logic of deep neural network (DNN) can really explained as symbolic concepts. Although some interest- ing phenomena of the emergence of concepts in DNNs have been discovered in previous studies (Li) Zhang 2023b Ren et al. 2023a), the core problem is still not strictly formulated or proven, i.e., strictly proving whether the knowledge encoded by DNNs is indeed symbolic.
To this end, it is a significant challenge to prove whether or not the knowledge encoded by a black- box DNN is symbolic. Up to now, heuristic studies usually explained DNN features using manually annotated concepts (Bau et al. 2017| Kim et al. 2018), without formally defining or proving the concepts in DNN. Thus, the proof of the emergence of symbolic concepts in DNNs will have profound impact on both theory and practice.
However, the definition of concepts encoded by DNN is still open problem, because it is complex cross-disciplinary issue related to cognitive science, neuroscience, and mathematics. Nev- ertheless, let ignore cognitive issues and limit our discussion the scope of whether we can obtain relatively small set of primitive inference patterns to strictly explain the complex changes of inference scores of the DNN on different input samples.
To be precise, we hope to prove set of sufficient conditions to enable us to represent the knowledge of a DNN as symbolic primitives. To this end, if we ignore cognitive issues, Ren et al. (2033)) and Li & Zhang (2023b) have considered Harsanyi interactions (Harsanyi] 1963) to represent the symbolic primitives encoded by a DNN. trained DNN usually only encoded few salient interactions, and they have also observed that the network output could be well mimicked by these interactions. Specifically, each interaction repre- sents AND relationship between set S of input variables, and this interaction has numerical effect ((S) on the inference score of the DNN. The input variables can be image regions for image classification words for natural language processing. As Figure shows, when classifying a dog
because they have empirically observed that a well-
"Quanshi Zhang is the corresponding author. He is with the Department of Computer Science and Engi- neering, the John Hoperoft Center, the Shanghai Jiao Tong University, China.

---

Published as a conference paper at ICLR 2024
S
Interaction (activated)
(6)) =8))004
Explained as
Interaction 2
[(5)==
$
(deactivate)
v(x) ((5)) + +7(5)
to
1(s))=
+1(+)) +
Interaction
(deactivated)
Figure 1: Illustration of interactions encoded by DNN. Each interaction S corresponds to an AND relationship among a specific set of input variables (image patches). The patches 21 and 24 are masked, so that interactions S₂ and S₃ are deactivated.
image, a DNN may encode a salient interaction among three image regions in S = (x1 I2, xz)- Only when all three image regions are present will the interaction be activated and contribute nu- merical effect ((S) to the inference score of the DNN. Masking any regions in S will deactivate the interactions and make ((S) = O.
Therefore, the proof of the emergence of interaction primitives is to prove a set of common con- ditions, which makes DNN only encode a small number of symbolic (sparse) interactions. means that given an input sample æ, the inference score v(x) of the DNN can be disentangled into the sum of the effects (SS of few salient interactions, i.e., v(x) EsERawn I(S) bias, which can be called interaction primitives. Specifically, we prove three conditions. (i) The DNN has at most M order non-zero derivatives, where M < n, and
the number of input variables to the DNN. (ii) The DNN can be used occluded samples (e.g., image with some patches being masked), and yields a higher classification confidence when the sample is less occluded. (iii) The classification confidence of the DNN does not significantly degrade occluded samples. Because these conditions are common for many DNNs, and the proof does not depend on the specific archi- tecture of the network, our proof ensures that the emergence of symbolic interaction primitives is universal phenomenon for various networks trained for different tasks.
In fact, the essential reason for the emergence sparse interaction primitives is neither the architec- ture of the neural network, nor the sparsity of network puramettrr/intermmdaatt the property of the task. be precise, when the task requires the DNN to conduct smooth inference on masked/occluded samples, well-trained DNN usually encodes sparse interaction primitives.
features, but
RELATED WORK
We have developed system of theerthcoretic interactions for explaining DNNs in the last three years, and have published more than fifteen papers in this direction. This system focused on ad- dressing the following problems explainable AI: (i) explicitly defining, extracting, and counting interactions encoded by DNN, (ii) explaining the representation capacity (e.g., generalization abil- ity and adversarial robustness) of DNNs from the perspective interaction, and (iii) summariz- ing/explaining common mechanisms shared by different empirical deep learning methods.
Explicitly defining and extracting interactions encoded by DNN. A representative approach in explainable Al to explain the interactions between different input variables (Sundararajan al.,
2020 Tsai et al.) 2022). Based on game theory, Zhang et al. (2021a]) 1a b 2020) defined multi-variate interaction and multi-order interaction. Ren et al. (2023a) discovered the sparsity of interactions in experiments. Li & Zhang (203bb) further discovered that salient interactions were usually transfer- able across different input samples and exhibited certain discrimination power. [Chnn al. (2024) extracted generalizable interactions shared by different DNNs. These studies indicated that salient interactions could be considered interaction primitives encoded by a DNN. Furthermore, Ren al. (2023b) used the sparsity of interactions to define the optimal baseline value for the Shapley value. Cheng et al. (2021a) used interactions of different complexities to explain the encoding of specific types of shapes and textures in DNNs for image classification. Cheng et al. (2021b) discovered that salient interactions usually represented prototypical visual patterns in images.
Explaining the representation capacity of DNNs using came-theoretic interactions. Game- theoretic interactions have been used to explain the representation capacity of a DNN, although the following studies used the multi-order interaction (Zhang al. 2020), rather than the Harsanyi
2

---

Published as a conference paper at ICLR 2024
interaction. Nevertheless, the Harsanyi interaction has been proven to be compositional elements in the multi-order interaction. The multi-ordes interaction has been used to explain the adversar- ial robustness (Ren al.] 2021; Zhou et al. 2024), adversarial transferability (Wang et al. 2021 and generalization ability iZhang et al. 2020 /Zhou et al. 2024) of a DNN In addition, Deng et al.. (202T) proved the difficulty of DNN in encoding cimplexco interactions. |Ren et al. (2023c) proved that compared to standard DNN, Bayesian neural network (BNN) tended to avoid encoding complex Harsanyi interactions. Liu et al. (2023) explained the intuition that DNNs learned simple Harsanyi interactions more easily than complex Harsanyi interactions.
Summarizing common mechanisms for the success of various empirical deep learning methods. Deng al. (2024) found that the computation of attribution values for fourteen attribution methods could all be explained as a re-allocation of interaction effects. Zhang et al.] (2022a) proved that twelve methods to improve the adversarial transferability in previous studies essentially shared the common utility of reducing the interactions between adversarial perturbation units.
3 DNNS TEND TO ENCODE SPARSE INTERACTIONS
3.1 OVERVIEW OF THE EMERGENCE OF SYMBOLIC (SPARSE) INTERACTIONS IN DNNS
In this study, we aim to prove that symbolic (sparse) interactions usually emerge in a well-traine DNN. Recent studies (Ren al. 2023a Li & Zhang 2023b) have empirically discovered the emer- gence of symbolic (sparse) interactions in various DNNs on different tasks. In mathematics, the emergence of symbolic (sparse) interactions means that the DNN's inference logic can be repre- sented as the detection of small number of interactions with a certifiably low approximation error.
Definition. A clear definition of interactions encoded by a DNN is required. In this study, the interaction is defined as the Harsanyi dividend (Harsanyi 1963). Let us consider trained DNN e and an input sample x = [x],-... xn.] with n input variables indexed by N = { .n.. The input variables can be image regions for image classification or words in an input sentence for a natural language processing task. Furthermore, without loss of generality, let us assume that the output of the DNN on the sample dimensional output, we may choose one dimension of the output vector as the final output var). In
scalar, denoted by v(x)= E RR. For DNNs with multi-
particular, for classification tasks, we set v(x)- = log T-ply-ym by following Deng et al. (222))
ply-y"th (x)
The interaction effect of the Harsanyi dividend (Harsanyi 1963) (or the Harsanyi interaction) be-
tween a set S C . of input variables is defined as tollows:
((S) (-1) m ((T),
(1)
where u(T) def u(xr)) v(wg). Here, v(Er) denotes the network output on the masked input
sample ær, where the variables in N T are masked using their baseline values = [b,...., b, and the variables in T are unchanged. Accordingly, v(xa) denotes the network output on the sample Vp. where all the input variables are masked. In particular, we have u0) = I(0) 0.
Each interaction can be understood as an AND relationship between input variables in S. For exam- ple, as Figure shows, to recognize a dog face, let a DNN encode the collaboration between three image regions in S = {#1, 22, } Only when the image regions æ1, T2, and 23 are all present will the interaction be activated and make a certain numerical effect I(S) on the network output. The absence (masking) of any of the three image regions (e.g., the masking of 24 in Figure I deactivates the interaction and removes the numerical effect, ie., I(S) = O.
We followed Li & Zhang (2023b) to visualize interactions encoded by PointNet++ QQ et al. 2017b) on the ShapeNet (Yi et al. 2016) dataset. Each point cloud in this dataset contained 2500 points. To simplify the visualization, Li & Zhang (202bb) considered each semantic par["] on the point cloud as a single input variable to the DNN. Figure shows that the interaction $ = light.. front wheel) usually contributed a positive effect to the network output (i.e., I(S) > 0), whereas the interaction = (front wheel, back frame, mid frame) usually had a negative effect (i.e., I(S) < O).
Faithful compositional inference patterns. We use the following three axiomatic properties to define interactions as representations of faithful inference patterns (or concepts) encoded by a DNN.
Annotations of the semantic parts were provided by the ShapeNet dataset. See Appendix C.2 for details.
3

---

Published as a conference paper at ICLR 2024
A salient interaction (light, front wheel (highlighted color)
0.2
sample
sample
sample 3
sample 4
sample's 5
froqueccy
((5) 1.72
(())
1(5) 1.90
((S) 181
1(5)
((5)
A salient interaction $ = {front wheel, back frame, mid frame) (highlighted color)
sample1 1
sample
3ample
sample 1
sample 5
hrqqeetcy
0.25
I(S) 0.84
((5)
1.20
((5) = 0.93
-5.02
1())= = =1.23
((S)
Figure 2: Interactions extracted by PointNet++ on different samples in the ShapeNet dataset and their corresponding effects I (S)). Histograms on the right show the distribution of interaction effects (S) on different "motorbike" samples.
(I) Sparsity property. A DNN is supposed to encode few salient interactions on a specific sample.
(2) Universal matching property. The network output any arbitrarily masked sample is supposed to be well matched by the effects of specific interactions.
(3) Sample-wise transferability property. Salient interactions supposed be shared across dif- ferent samples in the same category.
Li Zhang 2023b) have empirically discovered the sparsity of Harsanyi interactions. They have also observed significant overlap between salient interactions extracted from different samples in the same category, which indicated the trunsferability of interactions across different samples. In addition, it has been proven that the Harsanyi interaction satisfies the universul matching property.
Theorem (Proven in Ren et al. (2023a) and Appendix [. Let the input sample x: be arbitrarily masked obtain masked sample æg-- The output of the DNN on masked sample æs can be disentangled into the sum of all interaction effects within S: VS C N, v(xs) = Erçs I(T) + v(xg).
Furthermore, the Harsanyi interaction has been proven to satisfy seven desirable properties in game theory, e.g., the efficiency, linearity, dummy, and symmefry properties. In addition, the Harsanyi interaction can explain the elementary mechanism of three existing game-theoretic at- tribution/interaction metrics, e.g., the Shapley value P (Shapley 1953). See Appendix A for details.
Illuttaaing the emergence of interaction primitives. The core task of proving the emergence of symbolic primitives is to prove that in well-trained DNN, the interactions defined above sparse. Although there are as many as 2n interactions corresponding to all subsets S in 2 = {S S S N), recent studies (Ren al., 2023a Li & Zhang 2023b) have empirically discovered that these interactions were usually sparse in well-trained DNN. That is, only a few salient interactions have significant effects on the network output and can be taken as salient interaction primitives. In comparison, most other interactions have near-zero effects (i.e., (S) 2 0), which are referred to as noisy patterns. According to Theorem T the network output can be summarized by a small number of salient interactions, i.e., v(x)= ~ Σ EEeRatm.Sp I(S) + o(xgg.
Although the sparsity of interactions has already been demonstrated in previous studies (Ren et al., 2023a Li & Zhang (023b), we still conducted experiments in this study to better illustrate this phenomenon. We followed Li & Zhang (2023b) to conduct experiments
various neural net-
works including multilayer perceptrons (MLPs), residual MLPs (ResMLPs) (Touvron et al. 2022), )
Fl
al., 2012). VGG (Simonyan & Zisserman, 2014). ResNet (He et al.) 2016)., PointNet (Qi et al. [2077]] 70). PointNet++ (Qi et al., (017b), and on different datasets, including tabular data (the fic-lac-foe dataset (Dua & Graff 2017), phishing
LeNet (LeCun et al., 1998), AlexNet (Krizhevsky
dataset (Dua & Graff] (017). and wifi dataset (Dua & Graff 2017)), point cloud data (the ShapeNet dataset Yi 20T6p). and image data (the MNIST-3 dataset (LeCun al. 1998) and CelebA- eyeglasses dataset (Liu et al., 2015)). For better visualization, we drew a curve of the interaction strength by normalizing the interaction i(S) /(S)/ maxs' [[(5)] in descending order. Fig- ure shows the strength curve that was averaged over different samples in the dataset, which was
We have o(i) Esgrn [5TF (S U (i)), which means that the Shapley value Φ(i) can be explained as the result of uniformly assigning each Harsanyi interaction T(S J {i}) to each involved variable.
Please see Appendix C.1 for details on these DNNs and datasets.
4

---

Published as a conference paper at ICLR 2024
tic-tac-toe
witl
wif
CelehA ey eyegllsses
MLP--
R
MT-P-5
R-sMIPP5
RecNet-34
[759]
salient
salient
sallent
salient
B00g
B0000
1o0dy
Toley
sdd
Alo 1300
201
16e ShageNist
380
the
phishing
phishing
ShopeNet
Celebd-gyoglasee
MLP-5
ResMI.P-5
PointNet
PointNettw
ResNet 10
sallent
salient
sallent
salient
5000y
Dolay
notay
Dolic
2.
95
MNNST-33
MNIST-3
M
MNIST-3
Celebi eyeglaoses
LeNet
ResNet-30
BesNet- 41
VGG-16
BesNet 34
1651
salient
talienl
salient
sihent
selient
Dalcy
Dolay
1000y
1000y
14
MG
Index Intractton. S
Indes Intornction
S
Index interationS S
index of Interaction.
indes of Interaction
Figure 3: Normalized strength of different interactions, shown in descending order. Various DNNs trained for different tasks all encoded sparse interactions. In other words, only relatively small number of interactions had a significant effect, while most interactions were noisy patterns and had near-zero effects, í.e., I(S) O.
computed according to the method in &Li Zhang 2023b). Figure 3 successfully verifies that inter- actions encoded by various DNNs on different tasks were all sparse. Moreover, we followed Li & Zhang 2023b) to define interactions with [Z()) > T = 0.05 maxs' [[())) as salient interactions.
3.2 PROVING THE SPARSITY OF INTERACTIONS
Despite these achievements, there is still no theory to prove the emergence of such sparse interactions as symbolic primitives. Therefore, in this subsection, we make an initial attempt to theoretically prove the sparsity of interactions. To be precise, we need to prove the conditions, under which the output of a DNN can be approximated by the effects of a small number of salient interactions, instead of a mass of fuzzy features. More interestingly, the proof will show that the sparsity of interactions depends on the property of the classification task itself, rather than the architecture of the neural network, or the sparsity of the parameters/ineermddiaeeee
features.
Given a trained DNN e and an input sample x = [m1, ... .n. let v(x) E R denote the scalar network output on the sample x. Let us consider the Taylor expansion of the network output v(x), which is expanded at the point b = [bi,... bn] T.
b1)*1 ... (2n b..)) (x)1
v (r)
(2)
Oz
Ki. Kny!
Strictly speaking, there are no high-order derivatives for ReLU neural networks. In this case, we can still use the finite difference method (Peebles et al. 2020: Gonnet & Scholl 2009) to compute the equivalent high-order derivatives yielded by the change ReLU gating states.
Assumption 1-a. Interactions higher than the M-th order have zero effect, ie., V. (S N [S] > M + 1}, I(S)= The order is defined as the number of input variables in S, order(S) def [S]. Assumption 1-,3. The network is assumed to have at most M-rrder non-zero derivatives, i.e., V VbER". V ki Kn E N, S.I. K1 + +... Kn 2 M + 1, we have
8 (onnn
O.
0x 11..0
In mathematics, Assumption 1-a can be derived (see Appendix B.2) from Assumption 1-3 (assum- ing no derivatives higher than the M-th order in the Taylor expansion of the function v), which is stronger assumption than Assumption 1-a and is specific to continuously differentiable function In comparison, Assumption 1-a can be applied to more general networks than Assumption 1-3.
In fact, only Assumption 1-a without Assumption 1-3 is already enough to conduct our later proof. The assumed non-existence of high-order interactions in Assumption 1-a is not strange, and has been illustrated in many large language models (please see Figure This is because high-order
"This is a common setting for simple DNN or DNN with almost zero high-order derivatives. In fact, it not necessary for most DNNs have derivatives of very high orders during training.
5

---

Published as a conference paper at ICLR 2024
OPT-1.3B Sample
OPT-L.3B Sample
LLMMA-78
15
LLMMA77
Aquila-B
Aquila-B
1o
Sample
Lo
Sample2
Sample
03
Sample 2
00
order m
order m
Order
order m
onderm
onder in
Figure 4: -e--and-whisker diagram for the strength interactions [[S] of each order m. We tested different LLMs (OPT-1.3B, II LLaMA-7B, and Aquila-7B) on the SQuAD dataset. Experiments show that high-order interactions on these networks were usually close to zero. Please see Appendix D.I for experimental details and Appendix E.1 for results on more samples.
(a)
5.0
OPT-1.38
5.0
L.aMA-78
5.0
Aquile-7B
OPT-1.38 LLaMA-78
Aquila-78
0.0
0.0
0.0
Average 1.18+0.22
1.18#0.22
1.11+0.39
order 71
Order m
10
order m
10
Figure 5: (a) Visualization of the monotonicity. Each curve shows the monotonic increase of the average output of the m-th order a(m) with the order m on a sample. The shaded area indicates the standard deviation of all m-order outputs on sample, i.e., Std Std(s)_m(((()) Note that the value of standard deviation does not affect our proof, because the proof only relies on the average output (0m)) (b) The average value of p over different input samples, along with the standard deviation.
interactions usually represent extremely complex patterns and are usually unnecessary in real ap- plications. For example, let us consider an interaction with a nonzero effect I(S) corresponding to the AND relationship between M' 100 > M input variables. This indicates that if any of the 100 input variables is masked, then the interaction will be deactivated. Such elaborate in- teraction is usually considered as an over- over-fitted pattern in real applications and it is not commonly learned by DNN. In addition, ignoring very high-order interactions is common in the literature game-theoretic interactions (Sundararajan et al. 2020 Tsai et al.] 2022). In spite of that, we admit that there are few special cases where high-order interactions may appear in real applications, but in those cases, extensive high-order interactions can be summarized as simple effect, thereby not hurting the proof of the sparsity of interactions. Please see Section 3.3 for further discussion.
Second, let consider classification task in a real-world application, where some input samples may be partially occluded or masked. In fact, the classification of occluded samples is quite com- mon, and a well-trained DNN is supposed to yield higher classification confidence for samples that are less masked. Therefore, we make the following monotonicity assumption:
Assumption 2 (Monotonicity). The average network output is assumed to monotonically increase with the size of the unmasked set S of the input variables, ie.., V m S m, we have i((m') < i(m), def E ())m(((S)), u(S) v(æs) v(za).
where af ((m)
This assumption indicates that the average classification confidence of the DNN increases when the input sample is less occluded. Specifically, (m) =ms]=m[[t ( v v(xx)] 2 0 represents the average network output over all masked samples xg with [S] = m. We refer to (mm) as the average output of the m-th order in the following discussion.
Justification of the monotonicity assumption. Assumption 2 commonly holds on different samples and DNNs. We justify this assumption through both theoretical analysis and experiments. Theoreti- cally speaking, if we limit our discussion to two specific masked samples S and S' s.f. S Ç S", we cannot always ensure u(S) < u(S", because some variables S' \ may be unrelated to the clas- sification, and may even have negative contributions to the classification. However, Assumption 2 focuses on the average output over all mn-order masked states, ((0)) = Ejs]=m (u{),, which is much stabler and more robust than the output on specific masked state u(S). Thus, the monotonicity assumption is common for an input sample. Please see Appendix H for an example.
For experimental justification of Assumption 2, we conducted experiments on three Large Lan- guage Models (LLMs), including the OPT-1.3B model (Zhang et al. 2022b), the BAAI Aquila-7B model (FlagAl 2023). and the LLaMA-7B model (Touvron et al. | (2023). We tested these networks on 1000 sentences from the SQuAD dataset (Rajpurkar et al. 2016). For each input sentence, followed (Salowee/Shhnneee et al. (2023) to select n = 10 words from the sentence as input variables to reduce the computational cost. Please Appendix D.I for details the input sentences, how to determine

---

Published as a conference paper at ICLR 2024
Our theory can explain the sparsity of interactions in about 84.52% 89.87% samples, because these samples had monotonic values of a(m). Nevertheless, the remaining 10.13% -15,4% samples without the monotonicity also encoded very sparse interactions. Our proof is still significant enough, although we cannot prove the sparsity on all input samples.
Table 1:
OPT-1.3B
LLaMA-7B
Aquila-7B
Percent of samples with monotonicity
89.87%
84.52%
87.46%
Samples with monotonicity Samples without monotonicity
29.06=52.46
50.71+440.35
30.16:+2..2
Avg # of valid interactions
42.67
79.71
69.94
the set N, and how to mask words in NÀT when computing v(TT). Table shows that all LLMs, over 84% of the input samples satisfied the monotonicity assumption. F() also visualizes the increase of the average output of the m-th order a(m) along with the order m on different LLMs.
Table T also shows that because of the complexity of training an LLM, in a few cases, the average network output of the m-th order was not always monotonic along with the order m. In fact, this conflicted with the common logic, but it was still possible because the extremely high diversity of sentences made the LLM difficult to be sufficiently trained (fully converge). In this study, we did not consider such case and only focused on the ideal case where network was well-trained.
Third, we need to ensure that the classification confidence of the DNN does not significantly degrade on masked input samples. In real applications, the classification/deeecti common. Thus, for a well-trained DNN, its confidence when classifying occluded (masked) samples should not be substantially lower than its confidence for unmasked samples.
of occluded samples is
Assumption 3. Given the average network output of samples with m unmasked input variables, m(m), we assume a lower bound for the average network output of samples with m' (m' S m) unmasked input variables, Le., m' S m, ((m²m) 2 mmm)"" (mm), where p > is a positive constant.
In Assumption 3, we bound the decrease of the average output of order m by a polynomial of
degree p. If this assumption is violated. i.e., (mm²) (m')p ((m)) for m' I m. then it implies either extremely low classification confidence on masked samples or extremely high classification
confidence on normal (unmasked) samples, which are both undesirable cases in real applications.
We also conducted experiments to illustrate the value of p on real DNNs and datasets. We used the same LLMs and dataset as those in the previous experiment. Figure (b) shows that the value of across different samples was around 0.9 to 1.5, which was reasonable for further analysis.
Proof of the sparsity of interactions. Under the above conditions, we prove that interactions en- coded by a DNN are sparse. We start by analyzing the upper bound of the sum of the effects of all k-order interactions, denoted by (kk) def Es I(S).
Theorem 2 (Proven in Appendix B.3, There exists mo E 1 < k < M, the sum of the effects of all k-order interactions can be written as
1.... , M }. such that for all
A (k) = (A 00) ps + 1
1p]-1 + ... + al (6)
+ ) (0))
(3)
where [2(0]] < 1, |
< n. |a 10.1.... , 13 for 1,
[p] and
< logn
Arrl-1
0
if > O.
(4)
n²
[p]+1
nF
<
logn
Cppl-1
ao
if <.0
(5)
np- lp]+1
np
Here, X def Σ
(k) a; del MM
for 0, 1,... [p] and [p] denotes the
greatest integer that is less than or equal to p.
The above theorem indicates that the sum of effects of all k-ooderr interactions is O(n+t)). Then, we discuss the sparsity of interactions in the following two cases.
Case 1: When the positive and negative interactions of the k-th order do not fully cancel out each other. Let (B) det
Ei 1(8) denote the remaining proportion of the effects of k-order
Σ1s1=k [S())]
7

---

Published as a conference paper at ICLR 2024
Table 2: Comparison between the number of valid interactions and the derived upper bound.
OPT-1.3B
LLaMA-7B
Aquila-7B
MLP (tabular dataset)
Real # of valid interactions Upper hound
28.73-152.37
50.53-140.37
30.13126.20
54.42.1.6.81 229. 129.1111100 139.52
197.84-188.8 188.87
293.20
184.23
interactions that are not cancelled out. Here, the absolute value of this proportion In!*)] should not be negligible. Thus, let us set [y{*k] > A. Otherwise, we consider that the positive and negative interactions almost cancel out, and then this instance belongs to Case
Without loss of generality, we set small positive threshold T subject to 0 < & Ergs||u[T)) [u(T)) Then, we consider all interactions with [[S)] 2 T as valid (salient) interactions. We consider all interactions with [[()) < T as noisy patterns. In fact, as Figure shows, shows,, most interactions below the threshold 5 had roughly exponentially decreasing strength, which meant that most non-salient interactions (noisy patterns) had almost zero effect.
Therefore, let us use R7(A) def IKS N | [S] = k. [.()s 2 r] to denote the number of valid interac- tions of the k-th order. The following theorem provides an upper bound for R(k)
Theorem 3 (Proven in Appendix
B. B.4h. R(()) has the following upper bound:
Rd*
(
"1 [m] 11
dg 4.%)
(6)
The above theorem indicates that if positive interactions do not fully cancel with negative interac- tions (i.e., [n)*)] is not extremely small), then the number of valid interactions (*)) of the k-th order has an upper bound of On //rr/*)),, )), which is much less than the total number of (#) potential interactions of the k-th order most cases.
In fact, the final number of valid interactions also depends on the value of p. Although we cannot theoretically guarantee different DNNs all have small p values, experiments in Figure show that was around 0.9 to 1.5 on common tasks. Nevertheless, Eq. (6) just shows an upper bound of valid interactions, which is much more than the real interaction number. Please see Table 2 for the higher sparsity of real interactions than the upper bound. Thus, Theorem 3 shows that it is quite common for a DNN to encode sparse interactions.
Case 2: When positive and negative interactions of the k-th order almost cancel each other. In this case, the absolute value of 17 can be extremely small. such an extreme situation, the number of valid interactions proportional n /|rr)(()) Then, the upper bound for the number of interactions R()) is much higher, according to Theorem However, R()) still much less than (2) if (8) is not exponentially small.
Real number of valid interactions vs. the derived bound. We conducted experiments to compare the real number of valid interactions with the derived upper bound. We used the same LLMs and dataset as those in previous experiments. Besides, we also trained a 5-layer multi-layer perceptron (MLP) on a tabular dataset named TV news (Dua & Graff 2017). Specifically, we set M set r = 0.05 max [[(S") for all LLMs, and set = 0.1 maxs [[())) for the MLP. shows that the real number of valid interactions was about 30 to 50, while the derived bound was about 200 to 260. Note that the number of all potential interactions was 2 200 1024. Please see Appendix F.2 for the number of valid interactions and the bound on several example sentences.
We
3.3 WHEN ARE INTERACTIONS NON-SPARSE?
Despite the above proof of the sparsity of interactions under certain assumptions, there exist some special cases in which the DNN does not encode sparse interactions.
Scenario 1.
Let consider the scenario where the network output contains some random noise, Le., we can decompose the network output into o' r'(xs) = v(ms) + es. where es denotes a fully random noise. this case, the effect of each interaction can be rewritten as 1'(S) = I(S) + (S)., where 1(S) denotes the interaction extracted from the normal output component v(æs), and (S) = (-))(- (8) (2)) (er - <a) denotes the interaction extracted from the noise. Because I, (S) is sum of 91 noise terms, the variance of I. (S) w.t.t the noise is 2 times larger. In this case, the value of (S), as well as T'()), is not likely to be zero, i.e., we will not obtain sparse interactions.
8

---

Published as a conference paper at ICLR 2024
In fact, this scenario does not satisfy Assumptions 1-a and 1-3. In this case, small noises in v(())) to obtain sparse interactions. To this end, Li & Zhang (003a) proposed a method to estimate and remove potential small noises from the network output and boost the sparsity.
simply ignore
Scenario 2. Let us consider the second scenario, in which the network output on a masked sample 2 is purely dependent on the number of variables in S. We consider an example which the sign of u(S) is decided by the parity of the number of variables in S, i.e., if [S]] is odd, then u(S) +1; otherwise, u(S) = -1. In this case, [(5) is always positive if [S] is odd, and always negative if [S] is even, which is not sparse. In fact, this scenario does not satisfy Assumption 2 (the monotonicity assumption). In addition, the classification of the parity does not represent the typical paradigm for classification because there are inference patterns for classification.
Scenario 3. In this scenario, the network encodes high-order OR relationships between the in- put variables. For example, the network may encode an OR relationship "blue patch 1" V... "blue patch m" to recognize the sky. Such an OR relationship will be explained as a large number of lower-order Harsanyi interactions. However, in real applications. such high-order interactions, e.g., the detection of the sky, can actually be taken as a single concept. If we disentangle and remove such high-order interactions from the network output, the remaining output is likely to generate sparse Harsanyi interactions. In addition, this scenario does not satisfy Assumptions 1-a and 1-B.
Scenario 4. Let us consider the scenario in which the network output is in the form of a periodic function, e.g., v(xs)) sin(Eneg 2.). In this case, interactions encoded by the network are not sparse. This scenario does not satisfy Assumptions 1-o, 1-3, and Assumption 2.
Scenario Let us consider the special task that heavily relies on the information of all input vari- ables, e.g., judging whether the number of I's in a binary sequence (e.g., the sequence [0, O, 1, O, 1) odd or even. In this task, the value of p may be large, and the monotonicity assumption is not satisfied, As result, the interactions may not be sparse. See Appendix E.3 for experiments.
SIGNIFICANCE OF THE EMERGENCE OF INTERACTION PRIMITIVES
The emergence of symbolic interaction primitives can be considered as a theoretical foundation for the field of explainable AI. Many studies have attempted to explain the feature representation of DNNs as the encoding of different concepts with clear meanings. For example, [Bau et al. (2017) 2020 examined how each convolutional filter was related its encoded fuzzy concept. Kim et al. 2018) attempted to find a certain feature direction in the intermediate layer corresponding to a specific manually-defined concept. However, the fundamental issue behind these explanations, i.e. whether DNN can be faithfully explained as symbolic concepts, has not been studied.
The proof of the emergence of interaction primitives may provide a new perspective to analyze the generalization power and robustness of DNN. In fact, -heee-theoretic interactions have been used to explain overfitting (Zhang et al.) 2020). adversarial robustness (Ren et al., (221). and adversarial transferability (Wang all]|[2222 [2021). , although these studies used multi-order interactions (Zhang al., 2020) for an rather than the Harsanyi interaction.
Given the sparsity property and the universal matching property, the sample-wiss transferability property can be obtained by contradiction. If interactions are not transferable across samples, then means that the DNN activates different sets of salient interactions on different samples, and this indicates that the number of interaction patterns encoded by the DNN will be explosively large.
CONCLUSION AND FUTURE WORK
This study provided a set of conditions for the emergence of symbolic interaction primitives for inference. Under these conditions, proved that DNN encoded very sparse interactions between input variables. The commonness of these conditions indicated that the emergence of symbolic (sparse) interactions was not unusual, but might be a universal phenomenon for various well-trained Al models, because the proof does not rely on the network architecture. In future work, we will attempt to derive tighter upper bound for the number of valid interactions R(k) encoded by the network. Additionally, will further quantify the precise conditions that prevent the emergence of symbolic interaction primitives from occurring in a DNN.
Harsanyi interactions are compositional elements of multi-order interactions (Ren al. 2023a

---

Published as a conference paper at ICLR 2024
Acknowledgements. This work is partially supported by the National Science and Technology Major Project (2021ZD01 10000111622) 1602), the National Nature Science Foundation of China (92370115, 62276165, 62206170).
ETHIC STATEMENT
This paper aims to prove the emergence of sparse primitive inference patterns in well-trained DNNs under certain conditions. The proof potentially provides theoretical support for explaining DNNs the concept level. There are no ethical issues with this paper.
REPRODUCIBILITY STATEMENT
We have provided proofs for the theoretical results this study Appendix B
We
have also provided experimental details in Appendix [C.T] Appendix D.I Furthermore, we have released the code at /tttpa://qitee com s tu xai lab/ interactioon-sparaityy
C.2
and Appendix
REFERENCES
David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissection: Quantifying interpretability of deep visual representations. In Proceedings of the IEFE Confer- ence on Computer Vision and Pattern Recognition (CVPR),July 2017.
David Bau, Jun-Yay Yan Zhu, Hendrik Strobelt, Agata Lapedriza, Bolei Zhou, and Antonio Torralba. Understanding the role of individual units in deep neural network. Proceedings of the Na- tional Academy of Sciences, 117(48) 2020. doi: 10. 10.1077/pas..900335111 org
1907375177. URL 1ttp:/pp.......1111111111
https: // www wttp:/ppaaa..r..oo/aoeeeooo
Steven Bird, Ewan Klein, and Edward Loper. Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit. O' O'Reilly Media, Inc., 2009.
Lu Chen, Siyu Lou, Benhao Huang, and Quanshi Zhang. Defining and extracting generalizable interaction primitives from DNNs. In The Twelfth International Conference on Learning Repre- sentations, 2024. URL
n Eorum? wtwp:/wwwneeeeeee.eeeeeeeeee.e Eor.m::idd--aaayEVNeee
Xu Cheng, Chuntung Chu, Yi Zheng, Jie Ren, and Quanshi Zhang. Game-Theoretic Taxonomy of Visual Concepts in DNNs. arXiv preprint arXiv:2106.1099 2021a.
Xu Cheng, Xin Wang, Haotian Xue, Zhengyang Liang, and Quanshi Zhang. A Hypothesis for the Aesthetic Appreciation Neural Networks. arXiv preprint 2rXiv::2108.02646. 2021b.
Huiqi Deng, Qihan Ren, Xu Chen, Hao Zhang, Jie Ren, and Quanshi Zhang. Discovering and Explaining the Representation Bottleneck of DNNs. ICLR, 2021.
Huiqi Deng, Na Zou, Mengnan Du, Weifu Chen, Guocan Feng, Ziwei Yang, Zheyang Li, and Quan- shi Zhang. Unifying Fourteen Post-hoc Attribution Methods with Taylor Interactions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::///ccc..
ics. uci eecimedumml
FlagAl. Baai aquila language model, 2023. URL http://s//gghhtb....///ggggggggp
Aquila
Gaston H Gonnet and Ralf Scholl. Scientific computation. Cambridge University Press, 2009.
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.
John C. Harsanyi. A simplified bargaining model for the n-person cooperative game. International
Economic Review, 1(2):194-220 220, 1963. ISSN 00206598, 14682354.
10

---

Published as a conference paper at ICLR 2024
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, and Rory sayres. Interpretabilityy beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings Machine Learning Research, pp. URL https: http:::/pppccceeeiiiiiii
1868-2677.. PMLR, 10-15 Jul 2018.
ml www.mm.....r./sB000
kiml 8d. html.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, volume 25, pp. 1097-1105, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-233) 1998.
Mingjie Li and Quanshi Zhang. Defining and Quantifying AND-OR Interactions for Faithful and Concise Explanation of DNNs. arXiv preprint arXiv:2304.13312, 2023a.
Mingjie Li and Quanshi Zhang. Does a Neural Network Really Encode Symbolic Concepts? Inter- national Conference Machine Learning, 2023b.
Dongrui Liu, Huiqi Deng, Xu Cheng, Qihan Ren, Kangrui Wang, and Quanshi Zhang. Towards the Difficulty for Deep Neural Network Learn Concepts of Different Complexities. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), December 2015.
William Peebles, John Peebles, Jun- Yan Zhu, Alexei Efros, and Antonio Torralba. The hessian penalty: A weak prior for unsupervised disentanglement. In Andrea Vedaldi. Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020, pp. 581-597, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58539-6,
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 (CVPR), July 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hi- erarchical feature learning on point sets in a metric space. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017b. URL https:: http:::/pproeedddssseeeee File/ htt///dfff&bbeee http:///.eeeee000111/e6eeeeeeaa3
wwtppppr.pppp.....eeeee files//aper/20117 Papetr
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383-2392, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10. 10.186533v1/D16-11 1264. URL htttss://aclentthlogg.
org/DD6- 1264
Jie Ren, Die Zhang, Yisen Wang, Lu Chen, Zhanpeng Zhou, Yiting Chen, Xu Cheng, Xin Wang, Meng Zhou, Jie Shi, and Quanshi Zhang. Towards a Unified Theoretec View of Adversarial Perturbations and Robustness. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp- 3797-3810 10. Curran Associates, Inc., 2021.
Jie Ren. Mingjie Li, Qirui Chen, Huiqi Deng, and Quanshi Zhang. Defining and Quantifying the Emergence of Sparse Concepts in DNNs. In The IEEE/CVF Computer Vision and Pattern Recog- nition Conference, 2023a.
11

---

Published as a conference paper at ICLR 2024
Jie Ren, Zhanpeng Zhou, Qirui Chen, and Quanshi Zhang. Can We Faithfully Represent Absence States to Compute Shapley Values on a DNN? In International Conference on Learning Repre- sentations, 2023b. URLptttts////peeeeee// http://wwww..ttttooomaaaaaaaaaaa
Qihan Ren, Huiqi Deng, Yunuo Chen, Siyu Lou, and Quanshi Zhang. Bayesian Neural Networks Tend to Ignore Complex and Sensitive Concepts. Internationall Conference Machine Learning, 2023c.
Lloyd S Shapley. A value for n- i-person games. Contributions to the Theory of Games, 2(28):307- 317, 1953.
Wen Shen, Lei Cheng, Yuxiao Yang, Mingjie Li, and Quanshi Zhang. Can the inference logic of large language models be disentangled into symbolic concepts? arXiv preprint arXiv:2304.01083, 2023.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2014.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language pro- cessing, pp. 1631-1642, 2013.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pp. 9259-9268. PMLR, 2020.
Hugo Touvron, Piotr Bojanowski, Mathilde Caron, Matthieu Cord, Alaacldin El-Nouby, Edouard Grave, Gautier Izacard, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, and Hervé Jégou. Resmlp: Feedforward networks for image classification with data-efficient training. IEEE Trans- actions Pattern Analysis and Machine Intelligence, pp. 1-9, 2022. doi: 10.1 2022 3206148.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint 20211:2302.13971, 2023.
Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley interac- tion index. arXiv preprint arXiv:2203.0000 008700 2022.
Xin Wang, Jie Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang. and Quanshi Zhang. Unified Approach Interpreting and Boosting Adversarial Transferability. In International Conference on Learning Representations, 2021.
Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625 641, 2019.
Li Yi, Vladimir G Kim, Duygu Ceylan, I-Chao Shen, Mengyan Yan, Hao Su, Cewu Lu, Qixing Huang, Alla Sheffer, and Leonidas Guibas. scalable active framework for region annotation in 3d shape collections. ACM Transactions Graphics (ToG), 35(6):1-12, 2016.
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, pp. Press, 2021a.
AAAI
Hao Zhang, Sen Li, YinChao Ma, Mingjie Li, Yichen Xie, and Quanshi Zhang. Interpreting and Boosting Dropout from resentations, 2020.
View. In International Conference on Learning Rep-
Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang. Interpreting Multivariate Shapley Interactions in DNNs. In Thirty- AAAI Conference on Artificial Intelligence, AAAI 202/, pp. 10877-10886. AAAI Press, 2021b.
12

---

Published as a conference paper at ICLR 2024
Quanshi Zhang, Xin Wang, Jie Ren, Xu Cheng, Shuyun Lin, Yisen Wang, and Xiangming Zhu. Proving Common Mechanisms Shared by Twelve Methods Boosting Adversarial Transferabil- 2022a.
ity. arXiv preprint arXiv:
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01063 2022b.
Huilin Zhou, Hao Zhang, Huiqi Deng, Dongrui Liu, Wen Shen, Shih-Han Chan, and Quanshi Zhang- Explaining Generalization Power of DNN using Interactive Concepts. In Thirly-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024. AAAI Press, 2024.
13

---

Published as a conference paper at ICLR 2024
A AXIOMS AND THEOREMS FOR THE HARSANYI DIVIDEND INTERACTION
A.1 DESIRABLE THERRTHE PROPERTIES
The Harsanyi dividend was designed as a standard metric to measure interactions between input variables encoded by the network. In this section, present several desirable axioms and theorems that the Harsanyi dividend interaction I(S) satisfies. This further demonstrates the trustworthiness of the Harsanyi dividend interaction.
The Harsanyi dividend interactions I(S) satisfies the efficiency, linearity, dummy, symmetry, anonymity, recursive and interaction distribution axioms, as follows. We follow the notation in the main paper to let u(S) =(xs) - v(2)).
(1) Efficiency axiom (proven by Harsanyi (1963). The output score of a model can be decomposed into interaction effects of different patterns, L.e. u(N)= = EsgN T(S).
(2) Linearity axiom. If we merge output scores of two models 41 and u2 as the output of model u, L.e. AS C. N, u(S) (S) + uS)),, then their interaction effects Iu, (S) and Iuz(S) can also be merged as AS C N, (SS) = I,, (S) + (S).
(3) Dummy axiom. If a variable i N is dummy variable, i.e. AS E NM u u(S) + u((()), then it has no interaction with other variables, V # N ((S
(4) Symmetry axiom. If input variables i,j N cooperate with other variables in the same way, VS _ (N(i.)). ( = u(Su (i),, then they have same interaction effects with other variables, AA C NVG,,), U (1)) T(S (i))-
(5) Anonymity axiom. For any permutations स on N, we have VS C N, = where s a (x))) and the new model su is defined by (mu)( This indicates that interaction effects are not changed by permutation.
(6) Recursive axiom. The interaction effects can be computed recursively. For N and S N MEE, the interaction effect of the pattern S U (i} is equal to the interaction effect of S with the presence of minus the interaction effect of with the absence of i, i.e. VS C N (f), T(S U (t))= T(S is always present) (SS). T(Sli is always present) denotes the interaction effect when the variable i is always present as a constant context, i.e. (S)i is always present) = --cs(-1))51-1 (-))5111) 41. uLL (t)..
(7) Interaction distribution axiom. This axiom characterizes how interactions are distributed for "interaction functions" (Sundararajan et al. 2020). An interaction function ur parameterized by a subset of variables T is defined follows. VS C N,, T C S, ur(S)= = c; otherwise, ur(S) 0. The function ur models pure interaction among the variables in T, because only if all variables in T present, the output value will be increased by c. The interactions encoded in the function ur satisfies 1 I(T') and VS + T, ((S) = O.
A.2 CONNECTION TO EXISTING GAME-THEORETIC ATTRIBUTION/INTERACTUII METRICS The Harsanyi interaction I(S) is actually the elementary mechanism of existing game-theoretic attributionninteraation metrics, as follows.
Theorem 4 (Connection to the Shapley value (Shapley 1953), proven in both Harsanyi (1933) and Appendix B.5). Let d(i) denote the Shapley value of an input variable i. Then, the Shapley value o(1) can be explained as the result of uniformly assigning attributions of each Harsanyi interaction to each involving variable i, i.e., o(1) = Esgr(( ا (SS (i)).
Theorem 5 (Connection to the Shapley interaction index (Grabisch & Roubens
1999). proven in
both Ren et al. (023a) and Appendix [B6)). Given a subset of input variables T C N, the Shapley interaction index Timple (T) can be represented as Shapiis (T) = EsgNyr T8|+T (SUT). In other words, the index I Shaples (T') can be explained as uniformly allocating I(S") s.f. S' = SUT to the compositional variables of S' we treat the coalition of variables in as a single variable.
Theorem 6 (Connection to the Shapley Taylor interaction index (Sundararajan et al. 2020). proven in both Ren et al.) (2023a) and Appendix [B.7). Given a subset of imput variables T S N, the k- th order Shapley Taylor interaction index Toypiey-Tojio(IT can be represented as the weighted sum of interaction effects, i..,, phhptee Taytor (T) = T(T) if| < k; SShplee Tostor (T)) = EscNvo (%%+)) T(SUT)
if [T] = k; and I Tonior (T) = 0 > k.
14

---

Published as a conference paper at ICLR 2024
B PROOF OF THEOREMS
B. PROOF OF THEOREM IN THE MAIN PAPER
Theorem 1. Let the imput sample be arbitrarity masked to obtain masked sample æs. The output of the DNN the masked sample æg can be disentangled into the sum of effects of all interactions within the set S:
AS C N, v(Es) = -Ers T(T) + v(sg).
Proof. According to the definition of the Harsanyi interaction, we have AA C N,
I = E Σ (-1) u(L)
TSB
TCS
Σ Σ (-1)
LESTCST2LL
Σ
Σ
(-1)--10u((1
LCS
JC8:824 Tizt
18-1441
SS| | |L] (-1)
= Σ ='((L) uL)
Σ
LCS
m
=u( v((s)) v(zz))
Therefore, we have v(Es) = Ergs I(T) v(00).
B.2 DERIVATION OF ASSUMPTION 1-a FROM ASSUMPTION 1-3 IN THE MAIN PAPER
Before we give the derivation of Assumption 1-a from Assumption 1-3, we first prove the following lemma.
Lemma 1. The effect I(S) (S + 0) of an interactive concept can be rewritten as
I(S) ((s)=Ereh Exeqs
g01 gpitt**ng
+Eay
I (2; - b.)%%
Oxy Ox" Men
Ki
Kin
where Qs {[K1,..... K.] I
0}.
Note that similar proof was first introduced in Ren et al. (023c).
Proof. Let denote the function on the right of Eq. (8 by I(S), i.e. for S + 0,
gN twitt.t..n..
Iies (2; b:)
i(S) def En
(9)
KEES Oz ... Dzh =
x.!...Kp
According to Eq. 1.. we define ī(0) = 0. Actually, it has been proven in Grabisch & Roubens 1999) and Ren et al. (2033a) that the Harsanyi interaction I(S) defined in Eq. ① is the unique metric satistying the universal matching property mentioned in the main paper, i.c.
VSCN, v(æs)= E
I(T) + v(z)).
(10)
Thus, long can prove that i(S) also satisfies the above universal matching property, can obtain I(S) I(S).
To this end, we only need to prove I(S) also satisfies the universal matching property in Eq. 10 Specifically, given an input sample E RR, let us consider the Taylor expansion of the network
15

---

Published as a conference paper at ICLR 2024
output v(xs) of arbitrarily masked sample æs(S S N), which is expanded zip b [bq.-.. bnl Then, we have
g goitt Ou
((x)) b1) ... ((x5), bm) br)
VSEN, v(zs) = Σ
(11)
Oun"
Kg!...m. Kn!
==
where by denotes the baseline value to mask the input variable zi.
According to the definition of the masked sample sg, we have that all variables in S keep unchanged and other variables are masked to the baseline value. That is, V S, (æs); zz V & S, (æs).
b,. Hence, we obtain Vi & S, [(#s); bj]tt = 0. Then, among all Taylor expansion terms, only terms corresponding degrees k: in the set Ps = [[6 Kine
E S. E N; vi & S, n2 = 0)
may not be zero. Therefore, Eq. (II) can be re- re-written
gu tong
Has b.)
V v(as)
Σ
(12)
dz
KE Ps
We find that the set Ps be divided into multiple disjoint sets P3 Urgs Qr, where Qr
([K1,-.. Knn] iA E T, E NN;Vi T, = =0. Then, derive that
g gest.ttnn
I - b,) K1 KI!...K.
YSCN, v(rs) = Σ Σ
Or Ox.
TCS NEQT
2
(13)
Σ rCs
Î(T) + v(xz))
The last step is obtained as follows. When T 0, Qr only has one element & [0. which corresponds to the term v(z)). Also, [(0) = O, which leads to the final form. Thus, I(S) satisfies
the universal matching property in Eq. (10 and this lemma holds.
Then, we prove that by combining Lemma] 1 and Assumption 1-3, we can obtain Assumption 1-a. Assumption 1-a. Interactions of higher than the M-th order have zero effect, ie., V {S S N |8] 2 M + 1}, I(S) = O. Here, the order of an interaction is defined as the number of imput variables in S, ie.. order(S) def |S]
Proof. According to Lemma have
0o +or+++aog Kay
Di (x: - D3)
I(S) Σ KEQs du Nx
(14)
Ki! KI!...Ki! Kin
===
where Qs [[81. ...., Kn T IViE E EN S, -].
We note that when |S] 2 M + 1, we have V K E Qs. + ... + Kn 2 M +1. Then, combining
with Assumption 1-3, have
Fm + kap
=0,
VK E Qs-
(15)
0x 8L
x=
This leads I(S)= = VS (S CN M+1].
B.3 PROOF OF THEOREM 2 IN THE MAIN PAPER
To facilitate the proof of Theorem 2 in the main paper, we first prove the following two lemmas.
Lemma 2. For each M < m < n, the average network output of the me-th order can be written as
M
(mm)
(A)
(16)
where (kk) EISNIT=* T(T).
16

---

Published as a conference paper at ICLR 2024
Proof. According to the definition of ā ((m), we have
(m)
Esgn, [s(]
(17)
EsgN. (0(a))) 2(21))
(18)
[Bgg,Is]== Σ Erss (TT)
// //according to Theorem
(19)
= =[sgN k= Σ TTS.TT ((T)
m
(20)
ETESITI I(T)
BsCN,
(21)
k=1
SCN,1S|=m E ETSSITT TESTITE I(T)
(22)
k=1
72
m
11 K
E ETSNITE I(T)
(23)
k=1
Ke
Σ
ETSNIT ((T)
(24)
A(R)
(25)
From Eq.
22 to Eq.
23 we note that each single T S N([T) is repeatly counted for
(m=)) times the sum Σ Escris Ersa,T I(T). And from Eq. (23 to Eq. 24 we use the
following property:
11
m
n!
m!!
n!
(n k)!
71
n k
m
k:
m!(n - m)! k!(m k)) kl(n - k)) (m - k)).(n - m.).
k
m k.
(26)
Furthermore, according to Assumption 1-a, we have VS E {s C N
|S| 2 M + 1}. I(S) = 0.
Therefore, we have Vk: 2 M + 1, (k) = O. This leads to
VM mm3 n, ((m) Σ
m
A
(4))
M
m
(R)
(27)
Lemma Given n E N+ and M E N+, where M < n, if m E {n,n - 1, 1,.., (T)
M), ΣM 1= = 0, then we have wi = 0 for k = 1,... M.
Proof. We first represent the above problem using the matrix representation: if Cw 0, where
Wi
C
IR (M+1)xM
and w
w2
E M
(28)
WM
then we have = 0.
To prove this lemma, we only need to prove that rank(C)) C*) = M.
If we perform elementary row transformations the matrix, i.e., subtracting the (8 1)-th row from the i-th row (i 1, .), and using the formula (*) (n=1) (n-1). the matrix can be
17

---

Published as a conference paper at ICLR 2024
transformed as below, with its row rank unchanged:
Lete ... 1
C'
(29)
To prove that its rank is M, we only need to prove that the first M rows of C' are linearly indepen- dent, which is further equivalent proving non-zero determinant of the square matrix consisting of the first M rows, ie..
def D det
(30)
M
We can recursively obtain the equations below:
D
det
(31)
k
k=1
det
I/ subtracting (i + 1)-th row from i-th row
(32)
det
(33)
("-M)
("TM)
(34)
(35)
Now we can see that
D
M #
(36)
I (K)
This leads to the conclusion:
V m {n,n 1,... nn M). Σ M k==1
Wkk 0, then wy 0 for k 1, 1,,,,, M.M
Next, we will prove Theorem
Theorem 2. There exists ma E [n, 1.... n M). such that for all 1 < k < M, the sum of the effects of all k-order interactions can written as:
A (A()) + a (2) mn mlll-1
a + ag (11).
(k)
(k)
(37)
-1
18

---

Published as a conference paper at ICLR 2024
where | 1, |a001 < n, la;
(2)
E {0,1,... , 1}
1,... [p] 1, and
8 S logn
1
[
1p -1
40
if O,
(38)
1
n2 [p]t1
np
1
[pp] -1
ag
8 S logn
if <.
(39)
np [p
np
Here, X def
M
mg
(
+ 0, a
def Σ
M k=
for 0, ... [p]] 1, and [p]
denotes
k=
the greatest integer less than or equal to p.
Proof. First, according to Assumption 3, if we let m = 1, then the average output of order m should satisfy ((m) S mp -((),, Then, according to Assumption 2, we further have ū(m) 2 a
v(z))) v(zz)) = O. Combining with the conclusion in Lemma 2
we have
m
VM SMsman Sn,
0 OSu (m)mm)
A mmp 7(1)
(40)
Deriving the form of (4), For each A 1 1 k S M, we consider its n-ary representation after being divided by ((), i.e.
(k)
a (k)
g(k) (2(R)
+ (b)
9(b) no (1 (1)
(K) + + a1 n + dg
(k)
(41)
[1]
A (k)
ngle
(K)
(k)
+ di n + ao (R)
(k)
(2))
(42)
9(b)
where g(a) E N. | E f0, 1.. n for i 1,... (M)), and la
(k)
Note that we absorb
the decimal part into do Then, let us consider the following two cases for each 1 S k S M. We will show that in both cases, (a) can be represented as the form in Eq. 377.
Case 1: if g < [pl - 1. In this case, A (k) can directly be represented as the form in Eq. 37
(k) (A (2)) aa (R)
+ [2)-nn/pl-1 1pl
(k) (()) +1 n2(()) (8)
+ (k) gik) no(h) + n + (bt)) a1)) (43)
where we simply set (R) a (k)
91 O, and 8 can be arbitrary (we will discuss
(k)
the choice and range of ê in Case 2).
Case 2: if (R) 2 [p]. In this case, we first merge all terms with degree higher than equal to [p] into a single term. According to Eq. (42 we have
(4))
(k) ?
(A) Lp]
|p) n
+a
+a (k)
1 1 + ... + aj (k) n + do (k)
ppl
(1))
(44)
(1(0)
+ t [ 11
+ (k) + a (1)) 201)
(45)
where ((k) E 1) denotes the sign of this term.
Let us consider all orders in the set G [k 1 S k < M. 2 [p]}. Each order k has the
corresponding ((k), We set 8 = max 8(k, and let b-- = arg maxxer (4)) Then, for any ie E G,
we can rewrite the first term Eq. (45) as
(-5(A)
8(0) _8 pto p,
(46)
Note that since maX (A) > 8(k) and (k) E { f-11 1}. we have
[2()]
(0) 5601 In -6 <
(47)
19

---

Published as a conference paper at ICLR 2024
In partieular, | because 8th") 6. Therefore, for any & G. (
can be rewritten
A (1 (A)
+ -1 Le1-1 ppl 1pl11 + + ai n + du
(A)
(k),
(k) 22)
(48)
where | - 1, 100
(8) < a
1 E 10,1, ...
1) for i 1, [p] -
Deriving the upper bound of 8. Next, we will derive the upper bound for by using the inequality in Eq. 40). Let plug in the expression of ((k) into the Eq. 440), and obtain
M
M
M
((m)
(k)
+
Lp1-1
n
+
n
((()
(49)
According to Lemmal we have the following assertion:
M mg
mg E {n,n 1, M},
(k) +
(50)
This can be proven by contradiction: if for any E {n. n 1,. M). we all have E M
then according to Lemma obtain ( 0 for all k M. However, have mentioned above that [A(*))
which leads to contradiction.
M Let us denote def Σd
(k) a. def M
(m))
(k) a
for i 0,1, [p] therefore
using the inequality in Eq. for m mp we can write
< (mo)
(Ane*o
an a S my a0)) S nn. 0 (51)
+ [lvl
When X > 0, by using the right-side inequality, we obtain
(1-
4ppl-1 nP- pjj+
ao
)
8 < log,
(52)
nP
Similarly, when < 0, by using the left-side inequality, we obtain
(=x
1 [[p))-
ag
S logn
(53)
n ppl-1pi+111
np
B.4 PROOF OF THEOREM 3 IN THE MAIN PAPER
Theorem 6. R(k) has the following upper bound:
ū(1)
kk)) < (R)
(4)) p+5
P+ + 1
11 + + (k)
(54)
Proof. According to the definition of (k), we have
(A) = Σ s|=
T(S)
(55)
= (B)
15|= I(S) // according to the definition of (k)
(56)
Then, we obtain
(R)
Σ S
[((S
(57)
(T)
Σ - [((S)
(58)
(1))) // aacorrding R()) (S C N |S]= k, [T() 2 r}
(59)
20

---

Published as a conference paper at ICLR 2024
Note that ( always has the same sign as 178h) making
4 sy(4y
0. Therefore, we can simply add
absolute value to the left-hand side of the above equation and get
[
-R(R)
TypiT
Since 7 > O, we can obtain
|A(K) x(1) (2
((() < [|n) [|n]R)]
n x+6 (R)
[1p] 1 1 ... + (2)
(60)
B.5 PROOF OF THEOREM 4 IN THE APPENDIX
Before proving Theorem 4 we first prove the following lemma, which can serve as the foundation for proofs of Theorem
and 6
Lemma 4 (Connection to the marginal benefit). Aur(S) Encr(-1)
denotes the
marginal benefit (Grabisch & Roubens 1999) of variables in T' S N given the environment S. We have proven that Aur(S) can be decomposed into the sum of interaction utilities inside T and sub-environments of iee. Aur(S) = Es'ss I(TUS).
Proof. By the definition of the marginal benefit, we have
Aur(S) (-1) (() u(UUS)
35T
Σ 1-1 Σ I(K) by the universal matching property
kgLus
Σ (11) Σ Σ T(L'US') I| since Lns 0
1CT
MELS'S
Σ
Σ
11) 1114 Σ I(EUU))
8'S8
LCT
MCL
Σ
Σ
(-1) I(E'US))
SCS
MCT LCT 1.2!!
[T] [Z']
Σ
I(S UT)+
(-1)
I(L'US')
1- |7/|
5C8
V=T
E'ST
|=|
2/T
[2] (17-161))
= Σ
T(S' + Σ
I(L'US):
11
1 1- |2
S'CS
PCT
Σ
T(S' UT)
S'ÇS
Then, let us prove Theorem
Theorem 4. Let 66) denote the Shapley value of input variable i. Then, the Shapley value s(i) can be explained as the result of uniformly assigning attributions of each Harsanyi interaction to each involving variable ie., Φ(t) Escr T(S {1)).
21

---

Published as a conference paper at ICLR 2024
Proof. By the definition of the Shapley value, we have
(ii =E
U (it) w(S)
18
N1-1
Σ
((S - uu()
(N1-1)
SENVE [8|=m
N1-1
Σ
(S)
(NI-1
m=D
SC (
[8]=m
NN-1
E
Ei(LU(i)) 1C8
// by Lemma
INI
m=0
SCNV(:)
[8]mm
Σ SCNMO - S2L
(()
M
LCN
m=0
Σ (()
// since S 2 I. 18| m 2 [d]
NI
LCNV m=|
SENVE S2L
NN-1
INI- |L]
I(LU (i))
(M--I)
m [1|
LCN m=|Li
IN1-141-1
[N |4| -
E (1)
Σ
II
(N
k
LCNVO
Then, we leverage the following properties of combinatorial numbers and the Beta function to sim- (N--
plify the term uz = > k= -1
(i) A property of combinitorial numbers. (m)
(ii) The definition of the Beta function. For p.q > 0, the Beta function is defined as B(p.9) 4)
Jo --11(1 dd.
(iii) Connections between combinitorial numbers and the Beta function.
When p.g Zz, we have B(p.4) )
For m. n E 2 and n > m. we have (m)
m- m- B.nnnn++l.mm
IN -1I-1
IN| |Z] -1
W1.
IN
[NN]
[1] -1 -1)
(IZ) ([Z)+ + A). B(N [T]] 1.IT| +
k
IN -
|IN1- - [L]
1) B(INI - k A)
LLI-
!
k
IN
[ [1] 141-1) 1)
B(N [T| 1.
h
O=O
Then, solve ! and 2 respectively. For L, we have
22

---

Published as a conference paper at ICLR 2024
1 =
4
IN 1N-1L1-1 -1
Σ
|N| - |2|
-1
- (1 - 1llltt de
4
(|N - [r] -1
111
Σ
- (1 - x)²
(1 - x) 11-1 dx
k=0
=
[1(1
2)
1--1 dr
For ②, we have
11
(IN) - |L] -2
Σ
(IN) -1)
BQM 11 k))
k-1
IN1-161-2
(NN
|L] 2
=[NN| |4| - 1)
Σ
B(N 14| - 1,14 + W/' + 1
W'
K=
=(IN| - |2| - 1) f.
IN 41-2
Σ
|IN)-
[
|7| 2
IN-IL -1 (1 x 11|t dx
=(IN| - |4| -14-1)
[IN
INI-14122
Σ
[N]
- |7| 2
11- (1 - x)²²²
(11 - x) 141 do
b''
-1
= (INI - 14| -1) 1) f. (1-2) x²) 41 dx
|N| - |T.|
[L] +
Hence, we have
N -1|-1 J
WL - =
[L] 4+11
+
Therefore, we proved x(1) = 1 Esgnvo wr T(LUU ( =Eecrra 18t (i)).
B.6 PROOF OF THEOREM IN THE APPENDIX
Theorem S. Given a subset of input variables T C N, the Shapley interaction index Shhpleey (T) can be represented as psuupler (T)) = EsCNyT (SUU), explained as uniformly allocating T(S') s.1. S' = SUT to the compositional variables of S' if we treat the coalition of variables in I' as a single variable.
other words, the index Saupley (T) can be
Proof. The Shapley interaction index (Grabisch Roubens, 1999) is defined as Shapley (T)
E Escrvr [8 1-
(S) Then, have
(1M-177 13
23

---

Published as a conference paper at ICLR 2024
SShupley (T)
Σ SENAT
| |S|
ITD
Aur(S)
(I
[T]
1)!
[M--1
Σ
Aur(S)
M I
(NIIITI
m=0
S N
18 mm
IM-IM
E
Σ
IILUT)
by Lemma
M [T|
(NIIITI
m=0
SENV?
LCS
18 -m
INI-17I
E
Σ T(LUT)
. +
(N-
LENYT
m= 4
SCMAT
18
$2L
1
Σ
INI-TI
Σ
[N] |L|- ITT) (UUUT)
N +
(INI-ITI)
m - [T.]
IEMT m=
m
IN1-1E1-171 Σ
[NN] |2] 12')
E I(UU))
M - +1
(NI-ITI) 14|++
k
IENAT
Similar the proof of Theorem 4 we leverage the properties of combinatorial numbers and the Beta function to simplify wT.
IN1-IZI-1
[NI |2] -
WT.
-
14|++
-I
[N]
[1| 141-1111 [(1)) (1Z)+
13 (IN -I- - -
IN|-1Z|-111
[IN] - |L| - 127)
|Z|
-B(NN - 111 -1
[ -+ 1
k
N NI |2|
[ [1] (r') B [ -
k-
Then, solve I and 2 respectively. For C. we have
11-1D--12
[ - 11| - 11-1111111
Σ
(1 23)1 +k-1 do
k==
[IN- -
Tl
|N| |2| - [7]
[4]
Σ
-11-11111711 x)* (1 13)-1111-11 de
k
k=
/'' [Z] (1 (-xx)(t 1411 du
For ②2, have
24

---

Published as a conference paper at ICLR 2024
IN| 1411
[N|
|Z|
[T]
) B N |L] -
Σ (IN1 |4| [T]
k -
|N 111-1
|N|| - |7| W'
[2] -1) - 41-1-41-1711 + + +1)
=[ - [3] (T))
Σ
-(IN] [a]] (TT)
I
14| 1-11
| - |1|
12
1-14--111- -لا dr
k'
===0
[
INI- T1-1
=[|N] - [2] (21)
[N| - [T]] - (T)
1-144-171-- x)
(1 2)1² dr
K'=0
=(IN - [L] (T)) / (1 x)) (4]
[ |1| 12
[1]
Hence, we have
W [[]
IT
- +1
wz L + 2
L
Therefore, proved that SShupley (T) |-1-121F1 ELEAr
I(LUT) I(LUT) EigNio ZZT
B.7 PROOF 6HEOREMBIIN THE APPENDIX
Theorem 6. Given a subset of input variables T C. N, the k-th order Shapley Taylor interaction index 1 (hopler-Tooior(T) can be represented as weighted sum of interaction effects, i.e., Shopley-Toyfor (T)
T(T) [T) < k; Shopley Taylor (T) Escrar (55 -1 "(SUUT) [T) k; and Shhplly Tayler (T) = 0 if
[T| >
Proof. By the definition of the Shapley Taylor interaction index,
Aur(0)
if [T' k if [T] k
1 Shapley (hyler(k) (T)
IN Escrvr (
(u)
if [T] k
i of the main paper, we have When [2'l < k. by the definition in Eq.
Shoppey- Taylor(k) (T) = Awr(0)
(-11) 11-14 u(L) I(T).
LCT
When [T] = kt we have
25

---

Published as a conference paper at ICLR 2024
(ShuleeyTTayootin (T)
Aur(S)
IN| SCMAT
(1
INI-
Σ Σ
Aur (S)
INI
(!
SCNVT 18|-
[8]
Σ ILUUT)
Σ
I/ b/ Lemma 4
II [8]
M=0
NYT
LES
18|-m
INI-k
k
Σ
Σ
Σ I(LUT)
N
(N
LEN
m=|
181
NAT
$2L
IN
[N]
|L|
Σ E
I(LUT)
|NI
LCNYT mm/4| (NNIT)
[1|
|N| 17|-
|N| - [T| -k
Σ I(LU)
Σ
[N LCNVT
(2)+m)
m
WL
Similar to the proof of Theorem Beta function to simplify wL.
we leverage the properties of combinatorial numbers and the
- Σ
IN| L -
m=0
[[)+ml)
[N--
m
|N| -
[N
|L|
- k)
((1)+ m) BB(N |L|- m. [2] + m)
m
|N|
|1| k.
(INV -14| - 14|-m,111) m,111++11
m
m=m
-|=k
(IN) - [T - k) )
m
B [N] |4| m. 12) m)
...
m
Then, solve ! and 2 respectively. For D. we have
IN 1
1
Σ
[N] [L] -
x 1N11111----
(1- -1-z) 11+mm dx
m7
[N] 1|
[ |1|
Σ
[
|L]
k
x 1111-11 (1 1 x)
x k-1 (1 - 21111111 dx
m
= [' |L| x k-1 (11 (1-a0
-1-=)) 1111 dr = |1] B(k, LI) = (14+--1)
For ②,, have
26

---

Published as a conference paper at ICLR 2024
IN IN-I4
(IN) ( r/
|L| - ---1 BB[N]] -IL - m, -m,/LL + m
(IN) - [1| k).
[N] 14
(IN) |4| - - 1 1) B3 BB(N |T - m'' - -1,1%] + m 1)
(IN) - |T,| k).
ml'
m
IN1-I4
|NN| - |4| b 1
(INI - -14| - 11|- k)
Σ
x | 21 -2 (1 x)) 11 dx
mn
=f. (IA1 - 14|- -
[IM-ID
|N| | [T|]
ks
x 111- (1 x)m
- (1 x) 11 de
m'
In 0
=f, (IN) (Z|-K) x (1 (1-x)) (1-x)161 dr (I/V L - k) B(k, |Z| + 11)
[IV| 1L|-k
(14) 1)
Hence, we have
|N| - |1] -k
11 =0 + 2 (11+)-1)
(14) + 1) ((2LTT)
LII (ks - 1)!
N
L - k (LL) + 1)1 (A- - 1)!
([T] + 1)!
L
+1
(LT) + R)!
[L] (Ks - 1)!
N
L
Ll-k k
|||l (k 1)!
([T) + 1)
L
+ k
( + A: 1)!
1 [N
[L] k
LL (k-
1)
[ +
[L + 1s 1)!
|N
[Z] (k- 1)!
[L] T l (IL) + 1s 1)!
[N].
[T M!!
l (IL) AA)!
[N] 1
k (EA)
Therefore, we proved that when [T] = k pStupey--uggor (T) = INT IN
Eieno T(LU =
&
ELENYr INI * (1.5 T(LUT)=
(1(14) T(LUT). (MIUU))
C EXPERIMENTAL SETTINGS FOR VISUALIZING INTERACTION PRIMITIVES
C.I MODELS AND DATASETS
We used the models (including MLP, ResMLP, LeNet. AlexNet, VGG, PointNet, and PointNet+++) provided by Li Zhang (2033) and followed their experimental settings. The MLPs and ResMLPs used this experiment all had fully-connected layers. Each hidden layer had 100 neurons. The fic-tac-toe dataset, the wifi dataset, and the phishing dataset refer to the UCI tic-tac-toe endgame dataset (Dua & Graff 2017), the UCI wireless indoor localization dataset (Dua & Grafi 2017), and the UCI phishing website prediction dataset (Dua & Grafi 2017), respectively. The MNIST-3 dataset is a binary classification dataset, where images of the digit "three" in the MNIST dataset (LeCun) et al. 1998) were taken positive samples, while images of other digits were taken as negative samples. The CelebA-eyeglant dataset is a binary classification dataset, where images with the attribute "eyeglasses" in the CelebA dataset (Liu et al. 2015) were taken as positive samples, while
27

---

Published as a conference paper at ICLR 2024
other images were taken as negative samples. The heavy computational cost did not allow to test on all samples in these datasets. Thus, similar to previous studies Li & Zhang (023b), we used a subset of samples to compute interactions. For all models except for LLMs, followed the setting of testing samples in Li Zhang (2023b), in which 50 samples from the CelebA-eyeglasses dataset, 100 samples from the ShapeNer dataset and the MV/S7-3 dataset, and 500 samples from each of the three tabular datasets have been selected to compute interactions.
C.2 THE ANNOTATION OF SEMANTIC PARTS
As mentioned in Section 3.1, given an input sample with n input variables, the DNN may encode at most 2" potential interactions. The computational cost for extracting salient interaction primitives high, when the number of input variables n. is large. For example, if each 3D point of a point-cloud (or each pixel of an image) is taken as a single input variable, the computation is usually prohibitive. In order to overcome this issue, Li & Zhang (023b) annotated 8-10 semantic parts in each input sample, and the annotated semantic parts are aligned over different samples. Then, each semantic part in an input sample is taken as "single" input variable to the DNN.
For the ShapeNet dataset Yi et al. 2016), Yi et al. have provided annotations for semantic parts for input samples in the motorbike category. The semantic parts include gas tank, seat, handle, light, wheel, and frame. Based on the original annotation, [i & Zhang (2023b) further divided the annotation for each motorbike sample into more fine-grained semantic parts, including gas tank, seat, handle, light, front wheel, back wheel, front frame, mid frame, and back frame.
For images in the MNIST-3 dataset, we used the semantic parts annotated by Li Zhang (023b). The annotation of different parts was based on some key points in each image. Figure shows examples of these semantic parts.
3
3
3
3
3
Figure Examples of annotated semantic parts for samples of the MNIST-3 dataset.
D EXPERIMENTAL SETTINGS FOR LARGE LANGUAGE MODELS AND MLPS
D. MODELS AND DATASETS
We used off-the- shel- trained LLMSs (including the OPT- model, the LLaMA-7B model, and BAAI Aquila-7BB model) moddell provided by Huggingface in all experiments. The detailed information on these models and the training data can be found on the corresponding web pages.
To construct input sentences, for each paragraph in the SQuAD dataset, we first took the initial 30 words. Then, starting from the 31st word, we evaluated the following two conditions: 1) the current word had specific meaning and was not stop word in NLTK (Bird al. 2009). 2) there were no punctuations like the period or the semicolon in the five positions preceding the current word. If both conditions were satisfied, we stopped this process and considered the current word as the targer word for the L.M to predict. We considered the words before this target word as the input sentence for the L.M. If either condition was not satisfied, we incorporated the current word into the input sentence and continued evaluating the next word until this process stopped. For each input sentence, we used 10 meaningful words (words that are not NLTK stop words or punctuations) annotated by Shen et al. (2023) to construct the set of input variables N, so that have | = 10. When masking the input sentence, we only masked words in N, without changing other "background" words. We tested on the first 1000 sentences in the SQuAD dataset. It was because the heavy computational cost did not allow us to test on all 20000+ sentences in the dataset.
reseraa 1amaa 7b-hf
httess///uggingfaccccc/////////
28

---

Published as a conference paper at ICLR 2024
Another potential way to determine the set N is to select regions with significant Shapley values. is because Theorem shows that the Shapley value o(i) can be explained as the result of uni- formly assigning attributions of each Harsanyi interaction each involved variable i. Therefore, the Shapley value can serve as a reasonable metric to measure the saliency of input variables.
In order to ensure the inference logic of the network was meaningful, we discarded sentences for which the LLM predicted meaningless words, such as "the", "a", and other stop words. In addition, discarded sentences on which the classification confidence of the LLM is low. Specifically, we set a threshold ç for v(x)) - v( Given an input sentence æ, if v(x)) (2 < &. then we discarded this sentence. We set { for the OPT-1.3B model, { 2 for the LLaMA-7B model, and Ç = 3 for the BAAI Aquila- 7B model and the MLP.
D.2 OR INTERACTIONS AS A SPECIFIC KIND OF AND INTERACTIONS
In addition to the Harsanyi interaction defined in Eq. ( which represents the AND relationship between input variables, Li & Zhang (2023a) have also defined OR interactions, follows.
(S) = Eres (- (1))ss1-(T uNN ((N)T), s.t. S 0,
(61)
where u(N \ = (.T v(21g) The OR interaction represents the OR relationship between input variables. In particular, (0) - u(0) 0. In later discussions, use (S) to denote the Harsanyi interaction (or the AND interaction) in order to distinguish it from the OR interaction. It worth noting that an OR interaction can be regarded as a specific AND interaction, if we inverse the definition of the masked state and the unmasked state of an input variable.
Simultaneously extracting AND-OR interactions. In fact, a well-trained DNN usually encodes com- plex interactions between input variables, including both AND interactions and OR interactions. Li & Zhang (023a) proposed a method to simultaneously extract AND interactions (S) and OR interactions (S) from the network output. Given a set S C N and the corresponding masked sam- ple s.s, Li & Zhang (2023a) proposed to learn a decomposition uSS) = unnd + (Sr( towards the sparsest interactions. The (Sa) term was explained by AND interactions, and the (Sr term was explained by OR interactions, subject to (0) = Wand (0) = 0, (or = uor(0) = O.
u = Vand (S) Wor (S), 'aan (8) TCS and (T), Mar (S) = - T Tor(T)
3))=
(62)
Specifically, they decomposed u(S) into (S) 0.5 u(S) + and (S) = 0.5 (()) - Ys, where {ys) JSC are set of learnable variables that determine the decomposition of output scores for AND and OR interactions. Then, they learned the parameters {yh} by minimizing the following LASSO-like loss to obtain sparse interactions:
min {TS)
sCN ! (S)I + (Tx))+
Tna
663)
Removing noises. As discussed in Section 3.3 small noise cy in the network output may signif- icantly affect the extracted interactions, especially for high-order interactions. Thus, Li & Zhang (023a) proposed to learn to remove the noise term és from the computation of AND-OR inter- actions. Specifically, the decomposition was rewritten as (S) = 0.5 - (x((S) es) + 7s and Uor (S) 0.5 (u(S) - Eg) + 7s. Thus, the parameters { and } are simultancously learned by minimizing the loss function in Eq. 63) The values of { were constrained in [- {] where
<= 0.04 [u(2) v(zg)).
When illustrating the near-zero effects of high-order interactions in Figure we extracted both AND and OR interactions (can be regarded as a specific kind of AND interactions) and removed the noises from the network output as mentioned in Section D.2 When computing the number of valid (salient) interactions in Table I and 2, we only extracted AND interactions and we still removed the noises from network output.
When comparing the real number of valid interactions with the derived bound in Table 2 we only considered the first M interactions. This was because the theoretical bound can only be com- puted for the first M-order interactions, due to the Assumption 1-a (interactions higher than the M-th order have zero effects). In this way, we only considered the first M- interactions for fair comparison. Nevertheless, it is already shown in Figure g that high-order interactions usually had small effects, so ignoring interactions higher than the M-th order did not affect the conclusion.
29

---

Published as a conference paper at ICLR 2024
E MORE EXPERIMENTAL RESULTS
E. MORE RESULTS TO ILLUSTRATE THE NEAR-ZERO EFFECT OF HIGII-ORDER INTERACTIONS
We visualize the average strength of interactions [(m) samples. Figure 7 and all all show that high-order interactions on these LLMs usually have effects that are close
E -|
[[()]] of the m-th order more
Sample
Sample
Lo
Sample
Sample 4
Sample 5
1.0
25
order m
32
ordec m
order
20
order
order m
4.4
Sample
Sacplle
8.0
Sample
Sample
Sample
K500
05
0.1
0.2
order
order
order order
Figure 7: order on the 0.T-1.3B model.
Visualization of the average strength of interactions (
(m)
||s|=m||[(S]] of the mn-th
E8
=m
Sample
Sample 2
Sample
Sample
Sample 5
03
0.1
onterr
ocder
13
ordeet 7
order m
orderm
13
Sample 6
Sample
0.0
Sample
Sample
Sample 10
8.0
92
0.
onlerm
0.0
octier
60
order
3.0
onder
orderw:
10
Figure 8: Visualization of the average strength of interactions p(m) order on the LLaMA-7B model.
18 [[S() of the mn-th
str
Sample
Sample
0.4
Sample
6.5
Sample
Sample
2.8
ondero m
2.0
order m
onder m
ortler
order
Sample
Sample
Sample
Sample
0.3
Sample
6.
1000
0.c
m
ordec'm
Figure 9: Visualization of the average strength of interactions y(m) order on the BAAI Aquila-7B model.
EE
EE
[[S( of the m--hh
E.2 COMPARISON BETWEEN THE REAL NUMBER OF VALID INTERACTIONS AND THE BOUND ON EXAMPLE SENTENCES
In this section, we show several example input sentences along with their real number valid (salient) interactions and the derived upper bound. We also show the strength of the normalized interaction I(S) I(S)/ max [[())] on these examples in descending order, similar Fig- ure 3 Figure 10 and 12 shows the results on OPT-1.3B, LLaMA-7B, and BAAI Aquila- respectively.
30

---

Published as a conference paper at ICLR 2024
Ingut sentence: The Parthers beat the Seattle Sechewkss in the divisional round, running up a 31-0 halftime then bolding off furious second half comehack attempt win 31 24, avenging their elimination from
1.0
0.8
salient
[[(S]
0.6
Predicted word: playoff
0.4
10015
0.2
Real # valid (salient) Interactions:
0.0
250
500
750
1000
Upper bound: 65.20
index interaction
Input sentence: CBS provided digital streams of game via CASSports. com, and the CBS Sports apps tablets, Windows 10, Xbox One other digital media players (such Chromecast and Roku). Due to Verizon Communications excluslvity, streaming on smartphones was only
1.0
salient
((())
10015
Predicted word: available
valid (salient)
250 500 750 1000
Upper bound: 119.03
iDdex of Interaction
Figure 10: Comparison between the real number valid interactions and the derived upper bound, and visualization of normalized interaction strength in descending order the OPT-1.3B model. Words in bold are the input variables in the set for which we compute interactions.
Input sentence: With Rivera having Linebackee with the Chicago Bears in Super Bowl X.X. and Kubiak replacing Elway at the Broncos' defeats Super Bowls XXI and
[[(]]
Predicted word: XX
noisy
0.2
Real #f valid (salient) Interactions:
Upperbound: bound: 132,23
500
index of interaction S
December 28, 2015, ESPN Deportes anpounced that they had reached an agr agreement with CBS and the NEL be the exclusive the third dedicated gpanish-language
Input
1.0
0.8
salient
broadcaster game, marking
[[()]
0.6
0.4
noisy
Predicted word. broadcast.
0.2
0.0
valid (saliunt) interacions:
250
500
750
1000
Upunrhound: bound: 93.54
Index of Interaction
Figure 11: Comparison between the real number of valid interactions and the derived upper bound, and visualization of normalized interaction strength in descending order on the LLaMA-7B model. Words bold are the input variables in the set for which we compute interactions.
31

---

Published as a conference paper at ICLR 2024
Input seatence: Super Bowl 50 was American football game determine the chemplon of the National Foothall League (NFL) for the 2015 season. The A merican Football Conference (C) champion Deaver Broncos
saltent
[T()]]
Predicted word: defeated
noisy
0.2
Real #o valid (salient) interactions: 46 Upperbound: bound: 168.25
0.0
250
500
750
1000
Index of interaction
Input sentence: fter punt both teams, Carolina got-on track with 9- 9-play, 73-yard scoring drive. Newton completed 4 of passes for 51 yards and rushed twice 25
1.0
0.8
salient
[|(s]]
0.6
naisy
Predicted word: yants
0.2
Real valid (salient) interactions:
Upcerbound: bound: 104.95
Index of Interaction
250
500
750
1000
Figure 12: Comparison between the real number of valid interactions and the derived upper bound, and visualization of normalized interaction strength in descending order the BAAI Aquila-7B model. Words in bold are the input variables in the set N for which we compute interactions.
E.3 MORE DISCUSSIONS AND EXPERIMENTS ABOUT THE VALUE OF p
Although Assumption 3 does not constrain the upper bound for the constant p. we have conducted experiments on LLMs to measure the true value of in real applications. Figure (5)) shows that the value of p across different samples was around 0.9 to 1.5. According either Theorem or experimental verification in Table 2 interactions encoded by these LLMs were sparse.
Despite the lack of the bound for p. our theory is still complete. It is because the contribution of our study is to clarify the conditions that lead to the emergence of sparse interaction primitives, instead of guaranteeing sparse interaction in every DNN. In most tasks (e.g., the aforementioned classification tasks), these conditions are commonly satisfied, so that our theory has guaranteed the sparsity of interactions without a need of actually computing the interactions. Section 3.3 discusses a few special cases that do not satisfy the three common conditions. Therefore, instead of showing that sparse interaction primitives will emerge in all scenarios, the goal of this paper is to identify common conditions that provably ensure the emergence of sparse interaction primitives.
In addition, let us analyze how the sparsity of interactions depends on the value of p. Some special tasks heavily rely on the global information of all input variables, e.g. the task of judging whether the number of I's in a binary sequence is odd or even (i.., judging the parity). Then, in these tasks, the value of p may be large. Therefore, we conducted experiments to train an MLP to judge whether the number of I's in a binary sequence (e.g., the sequence [0. 10.111...000,1.011111 or even. Specifically, each binary sequence contains 10 digits. The MLP has 3 layers, and each layer contains 100 neurons. We trained the MIP on 1000 randomly generated samples for 50000 iterations, with the learning rate set to 0.01, and the MIP achieved 100% accuracy on these samples. We then tested the value of p and found that p was around 9.9 to 19.7, which is relatively large.
is odd
Fortunately, in most classification tasks as shown in Figure b), the network usually shows certain level of robustness the masking of input samples. Therefore, the value of p will not be very large in most classification tasks, thus ensuring the sparsity of interactions encoded by the network.
E.4
SIZE OF IMAGE REGIONS DOES NOT AFFECT THE SPARSITY OF INTERACTIONS
We would like to clarify that the objective, i.e., the proof of the emergence of sparse interactions, is agnostic to the selection of input variables for interactions. To better illustrate this, we conducted experiments the MNIST-3 dataset to show that the interactions were still sparse when the size of image regions varied. Specifically, the original image parts annotated by Li & Zhang (023b) were of the size of x pixels. Then, enlarged the size of image parts to 5 x 5 pixels and 7 x pixels. Figure [3 shows that the use of input variables of different sizes did not clearly affect the sparsity of interactions.
32

---

Published as a conference paper at ICLR 2024
Reglan size= x
Reglan
Regionsize 7
3
1.0
1.0
1.0
salient
0.8
salient
0.8
salient
[((]]]
0.6
0.6
0.6
0.4
noisy
0.4
noisy
0.4
noisy
0.2
0.2
0.2
0.01
0.0
0.0
200
400
200
incex of Interactions
incex of InteractionS
index of interattion
Figure 13: Normalized interaction strength in descending order. We compared the sparsity of inter- actions when we extracted interactions by setting different sizes of image regions input variables. Interactions were still sparse when the size of image regions varied.
E.5 EXPERIMENTS ON RNNS
We conducted experiments on an RNN (i.e., the LSTM) to explore the possibility of applying the Harsanyi interaction to wider range of tasks. Specifically, trained LSTMs with 2 layers the SST-2 dataset (Socher et al., 2013) (for sentiment classification) and the CoLA dataset (Warstadt) et al. 2019) (for linguistic acceptability classification). The LSTM can be considered take natural language as sequential data. Although these tasks are not equivalent to other prediction tasks on sequential data, they provide potential insights into how we can extend the Harsanyi interaction. Figure 14 shows that the network encodes relatively sparse interactions.
Sample 1
Sample
Sample 3
Sample
SST2
Index Intervetio
Lndes of Liilecctionn
indin of inseratioon
indes of Lislecaction
Sample 1
Sample
Sample 3
Sample 4
CalAA
indes interaction
23
of Interaation
imtrncton.S
indes internction. 2*
Figure 14: Interaction strength in descending order. The LSTMs also encode sparse interactions.
F DISCUSSION ON THE SETTING OF THRESHOLD T IN SECTION 3.2
In fact, the setting of r is quite reasonable, because most interactions with [I(S) < 7 actually have zero interaction effect I(S) 0, instead of having extremely small yet non-zero effeet by coincidence. According to I(S) (rcs(-1)\S1-11) u(T),, interaction I(S) is computed by adding and subtracting exponential number of non-zero terms. In this case, we usually obtain two types of interaction effects. First, we may obtain T(S) = O, if the DNN does not encode an AND relationship between exact set of variables in S. Then, different u(T) values for T C S will eliminate each other, as long as the DNN does not bring random noises to the output u(T)). Alternatively, may obtain I(S) with considerable value T(S)
In real applications, it is unrealistic for a DNN to be elaborately trained that adding up 2 terms results in extremely small yet non-zero zero interaction I(S), although we do not fully deny the negligible possibility that we may have few interactions with extremely small interaction effects.
33

---

Published as a conference paper at ICLR 2024
G BROADER IMPACT OF PROVING THE EMERGENCE OF SYMBOLIC (SPARSE) INTERACTIONS
Proving the emergence of symbolic (sparse) interactions provides alternative methodology for deep learning, i.e., communicative learning. In contrast to end-to-end learning from the data, in communicative learning. people may directly communicate with the middle-level concepts encoded by the DNN to examine and fix the representation flaws of the DNN. Communicative learning may include, but not limited to, (i) the extraction and visualization of symbolic concepts, (ii) the alignment of such implicitly encoded concepts and explicitly annotated human knowledge, (iii) the diagnosis of representation flaws a DNN, (iv) the discovery of new concepts from DNNs to enrich human knowledge, and (v) interactively fixing/debugging incorrect concepts in DNN.
H AN EXAMPLE TO ILLUSTRATE THE VALIDITY OF ASSUMPTION 2
Assumption 2 assumes that the average network output (mm) =m [u[)) monotonically in- crease with the order m, which considers all (*)) possible subsets S with size m, and the average network output is much stabler and more robust than the output on specific masked state uSS). This assumption is common for most models, without requiring all input variables to carry useful information. For example, let us explain the target model v(z) = 214223 + 21 + 22 + 22 23, where the input = [21, T2, Fz, Fz. 25] contains 5 input variables indexed by N = {1, 3, 4,5), and each input variable 2; {0.1} binary. Here, 21, Z2. and 23 are related to the classifi- cation, while and 25 are unrelated to the classification. Then, for |S] 2, the value of all possible u{)) are listed as follows: u( (11 2)) 2, u((1,3)) = 1, u((1, = 0, (((1,5)
0,
3)) 3, u u((2,4]) 4}) 1, u([2,5) 5}) 1, u((3, 4}) = 1, u((3,5)) 1, u((4,5
0.
Similarly, for [S] 3, the value of all possible u(S) are listed as follows: 2((1,2,3)) = 5,
1(f1,2,44 2, 4))
u((1,2,5))
2, (1, 3,4))
(((1,,,5))
1, (11,4,55)
0,
(112,3,4) = 3, (.55) = 3. ((2 4,5)) = 1, u((3,4,5)) = 0. We can see that
E [[s)) 1 1.8 ([s)= which satisfies the monotonicity assumption.
I CAN WE HAVE AN EFFICIENT WAY TO VERIFY ASSUMPTION 2 AND ASSUMPTION 3 (APPROXIMATING p VALUE) ON A SPECIFIC SAMPLE
In order to efficiently test whether Assumption 2 and Assumption 3 are satisfied, given an input sample æ, we can simply sample set of subsets (not all subsets) (S), S2, ... SS for each order m s.r. |S|| m, to approximate ((m) and the value p. which significantly reduces the computational E u(S.). where |S|| = m for S S Then, we can simply use the above approximated (m) to compute the value In this way, the computational cost of empirically testing the monotonic increase of ((m) and a rough estimation the value of Ond), which is much less than ((2").
cost. Mathematically, we have (m)) i
34


Reviews:
[{"review_id": "Cc2WxiEyHJ", "reviewer": "Reviewer_WKdR", "summary": "The main contribution of this paper is to provide another line of proof that AI models (at least those which are well trained) have (sparse) symbolic interactions emerge. In the end, the paper provides a proof that symbolic interactions can appear under a set of conditions on the AI model and its interaction with the data. Most importantly is using the Harsanyi dividend as the definition of interactions in an AI model. This along with several restrictions on the set of interactions with meaningful effect, how revealing more interactions ensures more confidence from the model, and bounding how poor the model performs on masked examples and how well it performs on unmasked examples.", "questions": "1. How limiting is the focus on Harsanyi interactions in your opinion? While I believe this focus is ok for input such as an image or textual data (which are by nature sub-dividable), can this be applied to real valued inputs? This is of particular interest in many applications such as time-series forecasting, reinforcement learning and control, etc…", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper does a really nice job justifying their assumptions and explaining in detail where they come from. This is especially apparent in section 3.2 where each assumption is restated in less formal detail, and often experiments are performed to justify these in large language models.", "weaknesses": "I've increased my score accordingly from the conversation w/ the authors.\n\n\n-----before edits---\n\nThis review is from an outsiders perspective, as I have very little experience in explainable AI. Outside of some experience in causality, I am primarily a reinforcement learning researcher. These weaknesses are a set of questions, which I believe limit the scope of work as presented. Overall, I think the paper is well written and provides many of the explanations and details I needed to understand and gain a reasonable intuition on the primary contribution.\n\nI can’t speak well enough on the novelty and significance of this work, but I believe if others are satisfied the paper is sufficiently novel I will happily agree.\n\n1. While using language is a decent entry to test the main properties of large models, this work (specifically how interactions are encoded) seems like it might be limited when working with models for image data. Specifically, how might one actually build a set of interactions (S) such that we achieve what is illustrated in figure 1? \n2. While the paper says these are properties of a well trained AI model, don’t these assumptions really speak more to the data you are using to train and test the AI model? Assumption 2 does speak towards the output of the model, but isn’t this necessarily implying the input data can be well partitioned into the discrete set of interactions?\n3. Assumption 3 is the weakest in terms of justification. While it applies to our current models, I’m not sure the upperbound on inference confidence is a property generally exhibited by “AI models”. This wouldn’t be an issue if this was stated as a part of the discussion of assumption 3, but I don’t buy the upperbound portion being undesirable.\n\n\n### Edits\n- I think you should mention the relationship to shapley values a bit more prominently in your main text. You have the relations expanded in the appendix, but as a sentence of a footnote should include a point to this in your main text (I was distracted thinking how much this reminded me of Shapley values, but was not familiar with Harsanyi interactions). \n- Figures 1 and 2 should be moved closer to where they are referenced in the paper. \n- section 3.1: “sparse symbolic (spase) interactions” I think the first sparse should be removed?\n- 3.2: “Assumption 1-\\alpha” you can use \\boldsymbol{\\alpha} to make the symbol bolded in the assumption header.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O8nyY2CpQW", "reviewer": "Reviewer_8DUx", "summary": "The paper under review studied the emergence of symbolic concepts of deep neural networks.\nConsider the set of subsets of each input data (e.g. an image or a sentence), the authors defined interaction between these subsets.\nThen, the authors zoomed into DNN models satisfied three proposed conditions, showed that sparse positive interactions emerge under these conditions.\nIn addition, practicality of the proposed conditions are illustrated by simulations.", "questions": "1. Figure 3: would the authors please provide more experiment details? Didn't find much in appendix neither. Here are a few main questions:\n - did the authors train the 5 mentioned models or existing trained model were used?\n - Size of training, testing data.\n - For each of the input, how was the subsets selected? for instance, for a image from MNIST, following the paper notation $\\mathbf{x} = (x_1, \\dots, x_n)$, is each $x_i$ just a pixel? \n\n\n2. Thm 2 and Thm 3: any insight on coefficients $\\lambda$'s in eq(4) and eq (7)? How Thm2 and Thm 3 imply sparsity are unclear. \nBased on eq (7), valid number of k-th order interactions is bound by roughly a constant times $\\lambda^{(k)} * n^{p+\\delta}$.\nOn one hand, $\\lambda^{(k)}$ can be large. On the other hand, the authors claims $n^{p+\\delta}$ is much less than \n$n \\choose k$. Yet bound on $p$ is not required, in case where say $n-k < p$, not sure how the claim holds.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The idea of qualitatively measure whether a DNN model can emerge a few symbolic concepts is novel and grounded.\nThe paper is well written, easy to follow. Plots are very illustrative and helpful.", "weaknesses": "1. Soundness of assumption 2 and 3: \n\n- assumption 2 assumes the more unmasked subsets of an input, the higher expected output. Intuitively, if each subset carries useful info, then yes.\nHowever, in many situation that is not the case. For instance, even in Figure 2, three unmasked regions (row 2) yield a much smaller output than two unmasked regions (row 1). The authors also mention that if there are many noisy regions, then only focus on the salient regions.\nIn practice, how to does one know such info apriori?\n\n- assumption 3 assumes there exists a constant $p$ such an inequality hold. But no bound on $p$ is derived. \nFrom the definition, $p$ can be arbitrarily large. Then it is not clear how Thm 2 shows the sparsity of interactions for models satisfies assumption 1-3.\n(See more details in Question section.)\n\n2. These lead to my major concern: practicality. While intuitively, the proposed three criterion all make sense, however, for a general DNN model, how to validate these three conditions, besides empirically testing after training, is somehow unclear.\n\n\n3. Implication of the work: my understanding is that the authors aim to derive conditions, under which DNN models will produce sparse positive interactions (considered as small number of concepts). As detailed above, if one can't test these conditions prior training, how would these conditions be used? On the other hand, it would be nice if the authors could comment on implications of Thm 3, i.e. how would knowing many DNN are able to learn a few key concepts benefit us?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sU64GI6aEv", "reviewer": "Reviewer_JPCH", "summary": "The authors set out to prove that the knowledge in a deep neural network can be understood as a function of very few sparse interactions as compared to the total possible large space of possible interactions between input features. They define these interactions through the Harsanyi dividend, and make assumptions under which they prove that the total number of salient interactions is upper bounded by a quantity which is much smaller than the total possible interactions. These assumptions are tested empirically, and the proof shows that neural networks learn to represent complex functions using few symbolic rules.", "questions": "1) I would like the authors to comment on the weakness I mentioned above.\n\nWhile I am not very familiar with the background work in this field, the paper tackles an important problem in deep learning, and does a convincing job justifying its claims. As such I am recommending acceptance.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) I found the paper very interesting to read. The paper is well motivated and the authors tackle the important but challenging problem of trying to show that deep neural networks learn symbolic concepts, and not just general fuzzy and arbitrarily complex interaction functions of their inputs.\n\n2) I found the assumptions made by the authors in the proof to be generally reasonable, and the authors give satisfactory empirical evidence that these assumptions hold for some important classes of networks.\n\n3) The proof was worked through quite clearly, and I found I could follow along reasonably well without needing to go through related works despite not having prior background knowledge in this subfield.", "weaknesses": "While the work shows that the number of valid interactions tends to be much smaller than the total possible set of interactions, this does not mean that the number of interactions is small in an absolute sense. For high dimensional inputs such as images, there can still be an extremely large number of interactions depending on the level of abstraction of the concepts being looked at to describe these interactions. For images, would pixels, patches, or some general localized features be the right abstraction to view interactions? As such, I am not sure if thinking of neural networks as learning these sparse interactions is a useful perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5JgRlo1WKw", "reviewer": "Reviewer_iVY1", "summary": "This paper attempts to prove the emergence of sparse interaction primitive inference patterns in well-trained AI models. Core to this proof, is three necessary conditions that must be satisfied for this sparse interaction between input variables.", "questions": "* Can you clarify if the core proof of the paper applies to other AI models that are not DNN's? If it does, can you provide evidence for this, and if it does not, perhaps think of refining your claims, and title to be only applicable to DNNs.\n* Can you clarify how the reader should group input variables to form the set of $S$?\n* Can you include error bars for the top row of Table 1, and include error bars for Figure 4 and Figure 5 (a). Also can you re-run with more random seeds to see if the error bars in Table 1 reduce.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is well-written and clear.\n* The paper contributes novel proofs for theorems 2 onwards.\n* The paper appears well-placed in the relevant literature.\n* The papers theoretical results appear significant and relevant to the ICLR community.", "weaknesses": "* The claim of to \"prove the emergence of symbolic concepts (or more precisely, sparse primitive inference patterns) in well-trained AI models.\" (Line 1), appears too broad and un-substantiated, specifically encompassing \"AI models\". It appears the evidence presented in the paper is only applicable and demonstrated for Deep Neural Networks (DNNs). For example, I cannot see how this proof or claims can be applied to other AI models that are not DNNs, such as Random Forests, which considers the outputs of all trees; k-NN's, that use all features to compute distances, or Boosting algorithms (e.g., Gradient Boosting Machines). Specifically, the empirical evidence presented in the paper in Figure 3, Figure 4, Figure 5 and Table 1, only apply to deep neural network models, and there is no other AI models that are not DNN's to support this claim.\n* It is not clear how the input variables should be grouped to form the set of $S$ input variables. For example, in the dog image example, \"image regions\" are proposed; however, there is no indication or discussion on how large these \"image regions\" should be for the approach and proof to work. For example, does this sparse primitive approach still hold if the \"image regions\" are too small, e.g., each region is a single pixel, and does it still hold if the \"image regions\" are too large, e.g., encompassing most of the image, or even half of the image. Some discussion on this, and how to select these groupings could be informative to the reader.\n*  Missing error bars; and large error bars. There appears to be missing error bars for Figure 4, Figure 5 (a), Table 1 (top row: Percent of samples with monotonicity). The provided error bars in Table 1 and Table 2, are so large that they overlap; leading the reader to suspect that the claim of the input samples satisfying the monotonicity assumption is not empirically verified, as the numeric results in Table 1 are not statistically significant, as the error bars overlap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)