Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts
Authors: Emanuele Marconato
Stefano Teso
Antonio Vergari
Andrea Passerini
Venue: NeurIPS 2023 poster (2023)
Keywords: Neuro-Symbolic Integration
Trustworthy AI
Concept Learning
Learning Shortcuts
Mitigation Strategies
TL;DR: A thorough analysis of learning shortcuts acquired by Neuro-Symbolic prediction models and of potential mitigation strategies

Abstract: Neuro-Symbolic (NeSy) predictive models hold the promise of improved compliance with given constraints, systematic generalization, and interpretability, as they allow to infer labels that are consistent with some prior knowledge by reasoning over high-level concepts extracted from sub-symbolic inputs. It was recently shown that NeSy predictors are affected by *reasoning shortcuts*: they can attain high accuracy but by leveraging concepts with \textit{unintended semantics}, thus coming short of their promised advantages. Yet, a systematic characterization of reasoning shortcuts and of potential mitigation strategies is missing. This work fills this gap by characterizing them as unintended optima of the learning objective and identifying four key conditions behind their occurrence. Based on this, we derive several natural mitigation strategies, and analyze their efficacy both theoretically and empirically. Our analysis shows reasoning shortcuts are difficult to deal with, casting doubts on the trustworthiness and interpretability of existing NeSy solutions.

Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts
Emanuele Marconato
Stefano Teso CIMeC and DISI University Trento
DISI and DI
University of Trento and University of Pisa
Trento, Italy
Trento, Italy
emanuele. wwwconatoounitta...
stefano. teso@uni .tefano..esoouuii tn.
Antonio Vergari
Andrea Passerini
School of Informatics University of Edinburgh Edinburgh, UK avergari@exseed. ed. ac uk
DISI
University of Trento
Trento, Italy
andrea. passerina @unitn. it
Abstract
Souro-Symbolic (NeSy) predictive models hold the promise of improved compli- ance with given constraints, systematic generalization, and interpretability, as they allow infer labels that are consistent with some prior knowledge by reasoning over high-level concepts extracted from sub-symbolic inputs. It was recently shown that NeSy predictors are affected by reasoning shoricuts: they can attain high accu- racy but by leveraging concepts with unintended semantics, thus coming short of their promised advantages. Yet, a systematic characterization reasoning shortcuts and of potential mitigation strategies is missing. This work fills this gap by charac- terizing them as unintended optima of the learning objective and identifying four key conditions behind their occurrence. Based this, we derive several natural mitigation strategies, and analyze their efficacy both theoretically and empirically. Our analysis shows reasoning shorteuts difficult to deal with, casting doubts the trustworthiness and interpretability of existing NeSy solutions.
Introduction
Neuro-Symbolic (NeSy) AI aims at improving the robustness and trustworthiness of neural networks by integrating them with reasoning capabilities and prior knowledge [1, 2]. We focus NeSy predictors [3, 4], neural structured-outpe classifiers that infer one or more labels by reasoning over high-level concepts extracted from sub-symbolic inputs, like images text [5, 6, 7, 8, 9, 10, 11]. They leverage reasoning techniques to encourage or even guarantee that their predictions comply with comain-specific regulations and inference rules. As such, they hold the promise of improved systematic generalization, modularity, and interpretability; in that learned concepts can be readily reused in different NeSy tasks, done for verification [12], and for explaining the model's inference process to stakeholders [13, 14, 15]. On paper, this makes NeSy predictors ideal for high-stakes applications that require both transparency and fine-graines control over the model's (in- and out-of- distribution) behavior, such as medical diagnosis [16], robotics [17] and self-driving cars [18].
Much of the promise of these models relies learned concepts being high quality. The general consensus is that the prior knowledge constrains learned concepts to behave as expected [19] and issues with them often tackled heuristically [20]. It recently shown that, however, NeSy predictors can attain high accuracy by leveraging concepts with unintended semantics [21]. Following
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Kg (pedestrian V red = stop)
Kg = (emergencyy A -peedestrian = go] AK)
green
Task
Task 2
red
red
A
y stop stop
y= stop stop
f gD X
Figure 1: Reasoning shortcuts undermine trustworthiness. An autonomous vehicle has to decide whether Y stop Y go based three binary concepts extracted from image x, namely C1 = red light, C2 green light and C3 presence of pedestriee tnns (shown in pink). Left: In Task the prior knowledge K (pedestrian V red = stop) instructs the vehicle stop whenever the light is red or there are pedestrians on the road. The model can perfectly classify an (even exhaustive) training set by acquiring reasoning shortcut that classifies pedestrians as red lights. Right: The learned concepts are then reused to guide an autonomous ambulance with the additional rule that in emergency situations red lights can be ignored, with potentially dire consequences. Our work identifies the causes of RSs (Section 4) and several mitigation strategies (Section 5).
Marconato et al. [21], we refer to these as reasoning shortcuts (RSs). RSs are problematic, as concepts encoding unintended semantics compromise generalization across NeSy tasks, as shown in Fig. 1, as well as interpretability and verification of NeSy systems [12]. Moreover, the only known mitigation strategies are based on heuristics [20, 11].
The issue that RSs and their root causes are not well understood, making it difficult to design effective remedies. In this paper, we fill this gap. We introduce formal definition of RSs and theoretically characterize their properties, highlighting how they are general phenomenon affecting variety of state-of-the-aa NeSy predictors. Specifically, our results show that RSs can be shared across many NeSy architectures, and provide a way of counting them for any given learning problem. They also show that RSs depend on four key factors, namely the structure of the prior knowledge and of the data, the learning objective, and the architecture of the neural concept extractor. This enables us identify several supervised and unsupervised mitigation strategies, which we systematically analyze both theoretically and empirically. Finally, we experimentally validate our findings by testing number of representative NeSy predictors and mitigation strategies on four NeSy data sets.
Summarizing, we: (i) Formalize RSs and identify four key root causes. (ii) Show that RSs are a general issue impacting a variety of NeSy predictors. (iii) Identify number of mitigation strategies and analyze their effectiveness, or lack thereof. (iv) Empirically show that RSs arise even when the data set is large and unbiased, and evaluate the efficacy of different mitigation strategies, highlighting the limits of unsupervised remedies and the lack of a widely applicable recipe.
Contributions.
2 The Family of Neuro-Symbolic Predictors
Notation. Throughout, we indicate scalar constants x in lower-case, random variables X in upper case, and ordered sets of constants x and random variables X in bold typeface. Also, Xay denotes the subset {z....., - [n]] the set {1, n,, and x + K indicates that x satisfies a logical formula K.
NeSy predictors. A NeSy predictor is model that infers n labels Y (taking values in )) by reasoning over a set of k discrete concepts C (taking values in C) extracted from a sub-symbolic continous input X (taking values in X²). Reasoning can be implemented in different ways, but overall its role is to encourage the model's 's predictions to comply with given prior knowledge K, in the sense that predictions y that do not satisfy the knowledge are generally avoided. The prior knowledge K is assumed to be provided upfront and correct, as formalized in Section 3. Normally, only supervision on the labels Y is available for training, with the concepts treated as latent variables.
Example 1. In -NIST-Additin model has to infer the concepts C = (C1, C2) encoding the digil classes, to predict their sum Y, in this case 8. Reasoning drives the model lowards complying with constraint K = (Y C + C2).
[7], given a pair of MNIST images [22], say
E 6 the
The concepts are modeled by conditional distribution po C X) parameterized by 0 E O, typically implemented with a neural network. The predicted concepts can be viewed as "soft" or "neural" predicates with truth value ranging in [0, 1]. As for the reasoning step, the most popular strategies

---

involve penalizing the model for producing concepts and/or labels inconsistent with the knowledge training time [8, 23, 24] or introducing reasoning layer that infers labels from the predicted concepts and also operates at inference time [7, 9, 25, 10]. In either case, end-to-end training requires to differentiate through the knowledge. Mainstream options include softening the knowledge using fuzzy logic [26, 6, 27, 11] and casting reasoning in terms of probabilistic logics [28, 7, 10].
To investigate the scope and impact of RSs, we consider three representative NeSy predictors. The first one is DeepProbLog (DPL) [7], which implements a sound probabilistic-lgic reasoning layer on top of the neural predicates. DPL is a discriminative predictor of the form [21]:
pe (y x; K) Ee uk(y c)) pp(c x)
where the concept distribution is fully factorized and the label distribution is uniform' over all label-concept combinations compatible with the knowledge, that is, uk(y c) {c = /y|} /2(c; K) where the indicator 1 c F K|Y / guarantees all labels inconsistent with K have zero probability, and ((c; K) = Σy = K[Y/y]] is normalizing constant. Infer- ence amounts to computing most likely label argmaxy po (y x; K), while learning is carried out via maximum -lo)eliill estimation, that is given a training set D y)) maximizing
C(po: K) po] ((xy)ED log x; K)-
In general, it is intractable to evaluate Eq. (1) and solve inference exactly. DPL leverages knowledge compilation [29, 30] to make both steps practical.
Our analysis on DPL can be carried over to other NeSy predictors implementing analogous reasoning layers [31, 32. 33, 10, 34]. Furthermore, we show that certain RSs affect also alternative NeSy approaches such as the Semantic Loss (SL) [8] and Logic Tensor Networks (LTNs) [6], two state- of-the-art penalty-based approaches. Both reward a neural network for predicting labels y consistent with the knowledge, but SL measures consistency in probabilistic terms, while LTNs use fuzzy logic to measure a fuzzy degree of knowledge satisfaction. See Appendix A for a full description.
3 Reasoning Shortcuts as Unintended Optima
was recently shown that NeSy predictors are vulnerable to reasoning shortcuts (RSs), whereby the model attains high accuracy by leveraging concepts with unintended semantics [21].
Example 2. To build intuition, consider UNIST-Additan examples of only Iwo sums: 0 0 1 and D
and assume the model is trained on
2 2. Note that there exist two distinct
maps from images to concepts that perfectly classify such examplex: one is the intended solution
7 2), while the other is
2 1).
The latter is unintended.
The ground-trutt data generating process. In order to properly define what RS is, we have to first define what non-shortcut solutions are. In line with work on causal representation learning [35, 36, 37], we do so by specifying the ground-truie data generation process p" (X, Y; K). Specifically, we assume it takes the form illustrated in Fig. 2. In short, we assume there exist i unobserved ground-trut -trtt concepts G (e.g., in MNIST-Addi on these are the digits O to 9) that determine both the observations X (the MNIST images) and the labels Y (the sum). We also allow for extra stylistic factors S, independent from G. that do influence the observed data (e.g., calligraphic style) but not the labels. The ground- truth concepts are discrete and range in G = [mi] x .... x [MR]], whereas the style R99 is continuous. The training and test examples y) are then obtained by first sampling g and s and then x ~ px(X g) and
X
Y
Figure 2: The ground-
truth data generation pro- cess (in black) and a NeSy predictor (in blue).
y (Y g: K). Later on, we will use supp G) to denote the support of p" (G). We also assume that the ground-truth process is consistent with the prior knowledge K, in the sense that invalid examples are never generated: p² (y g: K) = 0 for all yg. that violate K.
What is a reasoning shortcut? By definition, a NeSy predictor po X; K) shown in blue in Fig. 2 acquires concepts with the correct semanties if it recovers the ground-truth concepts, i.e.
(C x) = p" (G x)
V X
(3)
In practice, the distribution of labels given concepts needs not be uniform [10].
3

---

A model satisfying Eq. (3) easily generalizes to other NeSy prediction tasks that make use of the same ground -trut concepts G, as po | X) can be reused for solving the new task [21, 38]. It is also interpretable, in the sense that as long as stakeholders understand the factors G. they can also interpret concept-based explanations of the inference process that rely on C [39]. Naturally, there may exist many concept distributions that violate Eq. (3) and that as such do not capture the correct semantics. However, all those that achieve sub-par log- lig-liiels can be ideally avoided simply by improving learning or supplying more examples. We define RSs those concept distributions for which these strategies are not enough.
Definition 1. reasoning shortcut is a distribution po X) that achieves maximal log- logllikel on the training set but does not match the ground-truti concept distribution,
[ D, K) = maxo'ee L(por (D, A
Po p X)
This makes RSs difficult to improve by regular means and also hard spot based on predictions alone. Yet. since the concepts do not recover the correct semantics, RSs can compromise systematic generalization and interpretability. For instance. the shortcut concepts learned in Example 2 would fail completely at MNIST-Adda Addition tasks involving digits other than 0, 1, and 2 and also at other arithmetic tasks, like multiplication, involving the same digits, as we show experimentally Section 6. An examples of RSs in high-stakes scenario is shown in Fig. 1.
4 Properties of Reasoning Shortcuts
Counting deterministic RSs, We begin by assessing how many RSs exist in an idcalized setting in which the ground-truth generative process is simple, we have access the true risk, and the concepts C have been specified correctly, that is, C = G, and then proceed to work out what this entails. Specifically, we work with these assumptions:
A1. The distribution p" (X S) is induced by a map f (g, + x, i.i. G,S) = 0{ = (g, s)}, where f is invertible, and smooth over
A2. The distribution p" (Y G; K) is induced by map 9k : g r y. This is what happens in MNIST-Addis Addition, as there exists a unique value y that is the sum of any two digits
Our analysis builds on link between the NeSy predictor (Y X; and the concept extractor CC X), which depend on X, and their analogues Po G; K) and po (C G) that depend directly on the ground-truth concepts G. This link is formalized by the following lemma:
Lemma 1. It holds that: (i) The true risk of pe can be upper bounded as follows:
(5) where KL is the Ballback-Leible divergence and H is the Shannon entropy. Moreover, under Al and A2, pe (Y Y X; K) is an optimum of the LHS of Eq. (5) if and only if po G; is an optimum of the RHS. (ii) Under AI, there exists a bijection between the deterministie concept distributions po X) that are constant over the support of p(X g). for each g supp(G), and the deterministic distributions of the form Po CC G).
) (X Yx) (xkk]logPooy x; Ki] & B (Y g: K) Il Po(Y g: K)) HIp g: Ki))
All proofs can be found Appendix B. Lemma implies that the deterministic concept distributions po(CI C X) of NeSy predictors po(YY X; K) that maximize the LHS of Eq. (5), including those that are RSs, correspond one-to-one to the deterministic distributions (C G) yiclding label distributions pe YY] G; K) that maximize the RHS of Eq. (5). Hence, we can count the number of deterministic RSs by counting the deterministic distributions (C G):
Theorem Let be the set of mappings a gg - induced by all possible deterministic distributions po (C | G), i.e., each Po G) = 1 = a(G)) for exactly one a E A. Under A1 and A2, the number of deterministic optima po G) Eq. (5) is:
EaEa 1 L (3k o ag) 8k(g)
(6)
Intuitively, this sum counts the deterministic concept distributions PC X)- embodied here by the maps that output concepts predicting a correct label for each example in the training set. The

---

Table 1: Impact of different mitigation strategies on the number of deterministic optima: is reconstruction, C supervision on C, MTL multi-task learning, and DIS disentanglement. All strategies reduce the number of a's s's in Eq. (6), sometimes substantially, but require different amounts of effort to be put in place. Actual counts for our data sets are reported in Appendix C.2.
MITIGATION
REQUIRES
CONSTRAINT ON
ASSUMPTIONS
RESULT
None
A (gempo(()) (iBk o a8) = (k))
A1, A2
Theorem
MTL
Tasks
(c AUsTT (18kt) n (g) (x))
A1. A2
Proposition 4
Sup. on
AgesCuopCCC Aies (ai(g) = 9.)
A1
Proposition
R
Ax Gl
(a(g) of a(g')
AL. A3
Proposition 6
ground-truth distribution p¹ (G| X) is one such distribution, so the count is always at least one, but there may be more, and all of these are RSs. Eq. (6) gives us their exact number. This formalizes the intuition of Marconato et al. [21] that, as long as the prior knowledge K admits the correct label y to be inferred from more than
concept vector c, there is room for RSs. So far, we have assumed Eq. (2) is computed as in DPL. However, RSs are chiefly a property of the prior knowledge, and as such also affect NeSy predictors employing different reasoning procedures different relaxations of the knowledge. We show this formally in Appendix A. Deterministic RS are also important because- in certain cases they define a basis for all reasoning shortcuts:
Proposition 3. For probabilistic logic approackes (including DPL and SL): (i) All convex combina- tions of two or more deterministic optima po (C X) of the likelihood are also (non noon-eetrrminitiic optima. However, not all convex combinations can be expressed in DPL and SL. (ii) Under Al and A2, all optima of the likelihood can be expressed as a convex combination of deterministic optima. (iii) If A2 does not hold, there may exist non-deteriinistic optima that are not convex combinations of deterministic ones. These may be the only optima.
Combining Proposition 3 (i) with Theorem gives us a lower bound for the number of non- deterministic RSs, in the sense that if there are at least two deterministic RS, then there exist infinitely many non-deterministic ones. An important consequence is that, we can somehow control what deterministic RSs affect the model, then we may be able to implicitly lower the number of non-deterministic RSs as well. However, Proposition 3 implies that there may exist non-deterministic RSs that are unrelated to the deterministic ones and that as such cannot be controlled this way.
5 Analysis of Mitigation Strategies
The key factors underlying the occurrence of deterministic RSs appear explicitly in Eq. (6). These are: (i) the knowledge K. (ii) the structure of supp(G), (ii) the objective function L used for training (via Lemma 1), and (iv) the architecture of the concept extractor Po(C X), embodied in the Theorem by CC G). This gives us starting point for identifying possible mitigation strategies and analyzing their impact on the number of deterministic RSs. Our main results are summarized in Table 1.
5.1 Knowledge-based Mitigation
The prior knowledge K is the main factor behind RSs and also prime target for mitigation. The most direct way of eliminating unintended concepts is to edit K directly, for instance by eliciting additional constraints from a domain expert. However, depending on the application, this may not be feasible: experts may not be available, or it may be impossible to constrain K without also eliminating concepts with the intended semantics.
A more practical alternative is to employ Multi-Task Learning (MTL). The idea is to train NeSy predictor over T tasks sharing the same ground-truth concepts G but differing prior knowledge K(t) for E [7]. É.g., one could learn model to predict both the and product of MNIST digits, in our experiments (Section 6). Intuitively, by constraining the concepts to work well across tasks, MTL leaves less room for unintended semantics. The following result confirms this intuition:
Proposition 4. Consider T NeSy prediction tasks with knowledge K(),, for t E [T] and data sets D(O,, all sharing the same p" (G). Under Al and A2, any deterministic optimum (C G) of the MTL loss (i.e., the average of par-task losses) is deterministic optimum of a single task with prior
5

---

knowledge A, K(), The number of deterministic optima amounts to:
EaEA 1 ( NE= ((3Kc) o oa) - Sko (g))
(7)
This means that, essentially, MTL behaves like a logical conjunction: any concept extractor po(C (C incompatible with the knowledge of any task is not optimal. This strategy can be very effective, and indeed it performs very well in our experiments, but it necessitates gathering or designing a set of correlated learning tasks, which may be impractical in some situations.
G)
5.2 Data-based Mitigation
Another key factor is the support of p" (G): if the support is not full, the conjunction in Eq. (6) be- comes looser, and the number of a's satisfying it increases. This is what happens in UNIST-EvenOde (Example 2): here, RSs arise precisely because the training set only includes a subset of combinations of digits, leaving ample room for acquiring unintended concepts.
We stress, however, that RSs can also occur if the data set exhaustive, as in the next example.
Example 3 (XOR task). Consider lask with three binary ground-truth concepts G = (G1, G2, G3) in which the label Y is the parity of these bils, that K (Y Gi @ G2 @ Gz). Each label Y E {0, } can be inferred from four possible concept vectors g. meuning that knowing y is not sufficient to identify the g it was generated from. this case, is impossible to pin down the ground-truth distribution p" (C G; even if all possible combinations of inputs
observed.
One way of avoiding RSs is to explicitly guide the model towards satisfying the condition in Eq. (3) by supplying supervision for subset of concepts C2 C C, with 1 S [ke]. and then augmenting the log-likelihowe with cross-entropy loss over the concepts of the form Σier log po = 9: x). Here, training examples (x, g), y) come with annotations for the concepts indexed by 1. The impact of this strategy on the number of deterministic RSs is given by the following result:
Proposition 5. Assume that concept supervision is available for all g in S supp(G). Under A1, the number of deterministic optima po ( G) minimizing the cross-entropy over the concepts is:
EaEs 1 (AgES NEES ag(g)= g:
(8)
This strategy is very powerful: if lk]. S supp(G), G). and the support is complete, there exists only map that is consistent with the condition in Eq. (8) and it is the identity. Naturally, this comes at the cost of obtaining dense annotations for all examples, which is often impractical.
5.3 Objective-based Mitigation
A natural alternative is to augment the log-likelihood with an unsupervised penalty designed to improve concept quality. We focus on reconstruction penalties like those used in auto-encoders [40, 41, 42, 43, 44], which encourage the model to capture all information necessary to reconstruct the input x. To see why these might be useful, consider Example 2. Here, the model learns RS mapping both 0 and Z to the digit 1: this RS hinders reconstruction of the input images, and therefore could be avoided by introducing reconstruction penalty.
In order to implement this, we introduce additional latent variables Z that capture the style S of the input X and modify the concept extractor to output both C and Z, that is: po z x) = po x) (z x). The auto-encoder reconstruction penalty is then given by:
R(x) (B(c.))) log Pa (x c, c.z)]
where, Pw (x | c, z) is the decoder network. We need to introduce an additional assumption A3: the en- coder and the decoder separate content from style, that is, popppppCCp.
G.S) == Ex-or (
(P, C,
x) factorizes as po (C G) (Z S) and p (G,S C, Z) Ex-po(x(C.2)1" (G, (G Z x) as
P+ ( GG (S Z). In this case, we have the following result:
Proposition 6. Under Al and A3, the number of deterministic distributions po C G) that minimize
the reconstruction penality in Eq. (9) is:
Enes {Nas Esupp A
a(g) + a(g')
(10)
6

---

KNIST-Addition
Table 2: Q1: Disentanglement (DIS) can be very powerful to lower the frequency of RSs on XOR and AHIST-Additin data sets (the lower the better), Re- sults are averaged over 30 optimal runs.
100%
100%
100%
96. 7%
82.9%
100%
DIS 0%
0%
0%
0%
0%
0%
In words, this shows that indeed optimizing for reconstruction facilitates disambiguating between different concepts, i.e., different ground-truth concepts cannot be mapped to the same concept. However, minimizing the reconstruction can be non-trivial in practice, especially for complex inputs.
5.4 Architecture-based Mitigation
One last factor is the architecture of the concept extractor (C C X), as it implicitly controls the number of candidate deterministic maps A and therefore the sum in Theorem 2. If the architecture is unrestricted. (C X) can in principle map any ground-truth concept g that generated x to any concept c, thus the cardinality of A increases exponentially with
A powerful strategy for reducing the size of A is disentanglement. A model is disentangled if and only if pa (C| G) factorizes as [ Po(C, I G5) [45, 36]. In this case, the maps a also factorize into per-concept maps aj [my] + [my]. dramatically reducing the cardinality of .A, as shown by first experiment. In applications where the h concepts are naturally independent from one another, e.g. digits in MNIST-Addi tion, one can implement disentanglement by predicting each concept using the same neural network, although more general techniques exist [46, 47].
5.5 Other Heuristics based on Entropy Regularization
Besides these mitigation strategies, we investigate empirically the effect of the Shannon entropy Σx= H.n. [po[e)], which shown to increase concept quality in DPL. [20]. Here, Pe(C) is the marginal distribution over the concepts, and Hmm; is the normalized Shannon entropy over m, possible values for the distribution. Notice that this term goes to zero only when each distribution (C;) is uniform, which may conflict with the real objective of the NeSy prediction (especially when only few concepts are observed). Other similar heuristics that are suited for reducing ever-confieence in label predictions are based on label smoothing [48]. energy- -ased models [49]. annealing [50], and many others [51, 52, 53]. In principle, when applied at the concept level, they help reduce the wver-coniieenc in concepts that is typical in deterministic RSs. While they could also be beneficial to mildly reduce the number of RSs, we take the Shannon entropy regularization as a representative of this family for our experiments.
loss, defined
6 Case Studies
In this section, we evaluate the impact of RSs in synthetic and real-world NeSy prediction tasks and how the mitigation strategies discussed in Section 5 fare in practice. More details about the models and data are reported in Appendix C. The code is available at github. gethhu..cmmreeasonnng... shorttuus....
Q1: More data does not prevent RSs but disentanglement helps. We start by evaluating the robustness of DPL, SL, and LTN to RSs in two settings where the data set is exhaustive. In XOR (cf. Example 3), the goal is to predict the parity of three binary concepts g E {0, 1) given prior knowledge K = (y= 9i ① g2 4 ga). The predictor receives the ground-truth concepts as input and has to learn a distribution pa C G). In MNIST-Addi iio (cf. Example 1) the goal is to correctly predict the sum of two MNIST digits, e.g., contains examples of all possible combinations of concepts, i.e., supp(G) =G.
A.E. 2 and y = 3. In both tasks, the training set
Since the tasks are relatively simple, we can afford to study models that achieve optimml likelihood, for which Definition approximately applies. To this end, for each NeSy architecture, we train several models using different seeds and stop as soon as we obtain 30 models with likelihood 2 0.95. Then, we measure the percentage of models that have acquired RS. We do the same also for models modified to ensure they are disentangled (DIS in the Table), see Appendix C for details. The results, reported in Table 2, clearly show that RSs affect all methods if disentanglement is not place. This confirms that, without implicit architectural biases, optimizing for label accuracy alone is not
7

---

Table Q2: Impact of mitigation strategies. We report the Pi-score on the labels (Y) and concepts (C). All tested methods incorporate DIS and are averaged over 10 runs. Top: NeSy meth- ods combined with R, C, H on MNIST-EvenOdd. Bottom: evaluation on single tasks vs MTL on ANdST-A
DPL
SL
LTN
(Y)
(C)
F1 (Y)
Fi(C)
Fi (Y)
K((
85.1 1.6
0.1
99.3
0.2
98.1
0.1
0.0
99.5
0.1
76.3
98.1 0.1
0.1 0.1
0..4
0.1
01.
53.9 0.7
0..
0.1
99.3
215
9..
0.2
0.4
0.2
99.6401
0.1
97
38.1
16.7
R+C
4.4
99.3
615
98.
0.2
0.2
91.9 3.5
88.0
2 6.3
99.4
41.5 8.2
08.2 0.2
98.6 0.1
0.44
NWTST-AAdMM1
DRL
SL (C)
LIN (C)
PY)
(C)
(
(Y
ADD
68.1
0.0
99.5
0.0
674
0.000.0
MULT
100.0 0.0
37.6
07.60222
100.0
76.1
98.1
78.1
MULTIOP
0.0
99.8
100.0 0.0
99.8 0.1
98.3
98.3
sufficient to rule out RSs, even when the data is exhaustive. However, when forcing disentanglement, the percentage of models affected by RSs drops zero for all data sets and methods, indicating that mitigation strategies that go beyond the standard learning setup and specifically, disentanglement can be extremely effective.
Q2: Disentanglement is not enough under selection bias. Next, we look at two ) data sets where RS occur due to selection bias. Label and concept quality is measured using the Fi- score on the macro average measured on the test set. From here onward, all models are disentangled by construction, and despite this are affected by RSs, as shown below.
We start by evaluating KNIST-EvenDee 16 possible pairs of digits out of 100 are given for training: 8 comprise only even digits and 8 only odd digits. As shown [21], this setup allows to exchange the semantics of the even and odd digits while ensuring all sums are correct (because, e.g.,
a variant of MNIST-Addition (inspired by [21]) where only
12 1 3. As commonly done in NeSy, hyperparameters were chosen to optimize for label prediction performance on validation set, cf. Appendix C. The impact of reconstruction (R), concept supervision (C), and Shannon entropy loss (H) on all architectures are reported in Table 3. Roughly speaking, a concept Fi below 95% typically indicates RSs, shown by the concept confusion matrices in Appendix C.5. The main take away is that no strategy alone can effectively mitigate RSs for any of the methods. Additionally, for DPL and LTN, these also tend interfere with label supervision, yielding degraded prediction performance. The SL is not affected by this, likely because it is the only method using separate neural layer to predict the labels. Combining multiple strategies does improve concept quality average, depending on the method. In particular, H + C and + H + C help LTN identify good concepts, and similarly for DPL, although concept quality is slightly less stable. For the SL only concept supervision is relatively effective, but the other strategies are not, probably due to the extra flexibility granted by the top neural layer compared to DPI. and LTN.
Next, we evaluate the impact of multi-task learning on an arithmetic task, denoted MNIST-AddMA Here, the model observes inputs E { and their product, either separately (no MTL) or jointly (MTL). The results Table 3 show that, as in Example 2, all methods are dramatically affected by RSs when MTL is not in place. DPL and LTN also yield sub-par Fi-scores on the labels for the addition task. For SL and LTN, we also observe that, despite high concept F, for the multiplication task, the digit Z is never predicted correctly. This is clearly visible in the confusion matrices in Appendix C.5. However, solving addition and multiplication jointly via MTL ensures all methods acquire very high quality concepts.
0 2), (L) } and has to predict both their sum
Q3: Reasoning Shortcuts are pervasive in real-world tasks. Finally, we look at RSs occurring in BDD-OIA [54], an autonomous vehicle prediction task. The goal is to predict multiple possible actions Y manov__forwaze stop, surn_leftt ourn_right from frames x of real driving scenes. Each scene is described by 21 binary concepts C and the knowledge K ensures the predictions are consistent with safety constraints (e.g., stop = -move_ (orwardd and guarantees concepts are predicted consistently with one another (e.g., rwad_rallllee clear + mobstacle). Since this is high-stakes task, we solve it with DPL, as it is the only approach out of the ones we consider that guarantees hard compliance with the knowledge [7]. See Appendix C for the full experimental setup.
Table 4 lists the results for DPL. paired with different mitigation strategies. In order to get sense of the model's ability to acquire good concepts, also include two basclines: CBM-AU AUC introduced by
8

---

Table 4: Q3. Left: Means and std. deviations over 10 runs for DPL paired with different mitigations.
Right: Confusion matrices on the training set for DPL, alone (top) and paired with mitigation strategies (bottom) for {move_ foove__orvarrd turn left, turn_right concept vectors.
FORWARD
STOP
LEFT
RIGHT
BDD-OIA
Fl-mean (V)
Fl )
DPL+C+H DPL.
CBM-AUC
70.8 0.1
62.1 0.1
c-only
64.8
60.3 0.1
DPL
0.1
39.4
DPL+H
72.1 0.1
48.1 0.3
DPL4C
08.2
6.1
DPL+C
0.3
6.1
Sawada and Nakamura [55] for this task, which learns jointly the concepts together with unsupervised ones, and processes both of them with a linear layer to obtain the labels; C-only, in which the concept extractor is trained with full concept supervision and frozen, and DPL. is only used perform inference. This avoids any interference between label and concept supervision. The Fi-scores are computed over the test set and averaged over all 4 labels and all 21 concepts. On the right, also report the concept confusion matrices (CMs) for the training set: each row corresponds to ground-truth concept vector g, and each column predicted concept vector c.
Overall, the results show that, unless supplied with concept supervision, DPL optimizes for label accuracy (Fi(Y) by leveraging low quality concepts (Fi(C)). This occurs even when it is paired with a Shannon entropy penalty Н. This is especially evident in the CMs, which show that, for certain labels, all ground-truth concepts g are mapped single not unlike what happens in first experiment for entangled models. Conversely, the concept quality of DPL. substantially improves when concept supervision is available, the cost of slight degradation in prediction accuracy. The CMs back up this observation as the learned concepts tend to align much closer to the diagonal. Only for the turn_ turn_left label concept supervision fails to prevent collapse. This occurs because annotations for the corresponding concepts are poor: for a large set of examples, the concepts necessary to predict turn_left are annotated negatives, complicating learning. In practice, this means that all variants of DPL predict those concepts negative, hindering concept quality.
7 Related Work
Shortcuts in ML. State-of-the-art ML predictors often achieve high performance by exploiting spurious correlations or "shortcuts" in the training data [56]. Well known examples include watermarks [57], background pixels [58, 59], and textual meta-data in X-ray scans [16]. Like RSs, regular shortcuts compromise the classifier's reliability and out-of-distributtin generalization and are hard to identify based on accuracy alone. Proposed solutions include dense annotations [60], out-of-domain data [61], and interaction with annotators [62]. Shortcuts are often the result of confounding resulting from, e.g., selective sampling. RSs may also arise due to confounding, as is the case in MNIST- tion (cf. Example 1), however discussed in Section 5, data is not the only factor underlying RSs. For instance, in XOR (cf. Example 3) RSs arise despite exhaustive data.
Reasoning shortcuts. The issue of RSs has so far been mostly neglected in the NeSy literature, and few remedies have been introduced but never theoretically motivated. Stammer et al. [63] have investigated shortcuts affecting NeSy architectures, but consider only input-level shortcuts that occur even if concepts are high-quality and fix by injecting additional knowledge in the model. In contrast, focus RSs that impact the quality of learned concepts. Marconato al. [21] introduce the concept of RSs in the context of NeSy but for continual learning, and proposes a combination of concept supervision and concept-level rehearsal to address them, without delving into theoretical justification. Li et al. [11] propose a minimax objective that ensures the concepts learned by the model satisfy K. Like the entropy regularizer [20] addressed in Section 5, this strategy ends up spreading probability across all concepts that satisfy the knowledge, including those that have unintended semantics. As such, it does not directly address RSs.
Neuro-symbolic integration. While RSs affect number of NeSy predictors, NeSy encompasses heterogeneous family of architectures integrating learning and reasoning [1, 2]. We conjecture that

---

RSs do transfer to all NeSy approaches that do not specifically address the factors we identified, but an in-depth analysis of RSs in NeSy is beyond the scope of this paper. concurrent work, Wang et al. [64] derive the sample complexity of NeSy predictors when no RSs are in place. It is unclear how these bounds may change when RSs are present.
Relation to disentanglement. Recovering the latent variables G has been the center of several works in representation learning [65, 35, 66]. Among these, achieving identifiability of the latent components has been studied in non-linear independent component analysis [67, 68, 69] and recently in Causal Representation Learning [46, 70, 71, 72]. In this respect, several overlaps exist with the natural mitigation strategies that we investigated: (i) multi-task learning has been shown to increase disentanglement [73] and provably leads to identifiability [74, 75], and (ii) latent variables supervision also largely increases the amount of disentanglement [76, 77, 47]. Our work is the witness that the intersection with disentanglement literature beneficial for learning the intended concepts in NeSy and, vice-versa, that mowleege--gudeed learning can be new way of acquiring identifiable
representations, by avoiding RSs.
8 Conclusion
In this work, we provide the first in-depth analysis of RS affecting NeSy predictors. Our analysis highlights four key causes of RS and suggests several mitigation strategies, which we analyze both theoretically and empirically. Our experiments indicate that RSs do naturally appear in both synthetic and real-world NeSy prediction tasks, and that the effectiveness of mitigation strategies is model and task dependent, and that a general recipe for avoiding RSs is currently missing.
We foresee that reasoning shortcuts extend beyond the current scope of NeSy predictors with known prior knowledge. This includes approaches that learn jointly both the concepts and the knowledge, like ROAP [78] and DSL [79], well as fully neural models, like CBMs [80] and their variants [39, 81], which are also likely to be affected by RSs when concept supervision is limited. We plan to investigate further this direction in the near future.
Ultimately, this work aims at jumpstarting research on the analysis and mitigation of RSs, with the hope of leading to more trustworthy and explainable NeSy architectures.
Broader impact. Our work brings the subtle but critical issue of RSs to the spotlight, and highlights benefits and limitations of a variety of mitigation strategies, but it is otherwise fundamental research that has no direct societal impact.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable feedback in improving the current manuscript. We acknowledge Emile von Kricken for proofreading our claims and Yoshihide Sawada for his help in deploying the models on BDD-OIA. We are also grateful to Pedro Zuidberg dos Martires for insightful discussions with us the early stages of the work. We acknowledge the support of the PNRR project FAIR- Future AI Research (PE00000013), under the NRRP MUR program funded by the NextGenerationEU. The research of ST and AP was partially supported by TAILOR, project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
References
[1] Luc De Raedt, Sebastijan Dumančić, Robin Manhaeve, and Giuseppe Marra. From statisti- cal relational to neural-symbolic artificial intelligence. In Proceedings of the Twenty-Nint International Conference on International Joint Conferences on Artificial Intelligence, pages 4943-4950, 2021.
[2] Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illumino,, Hoifung Poon, and COPPE Gerson Zaverucha. Neural-symbolic learning and reasoning: survey and interpretation. Neuro-Symbolic Artificial Intelligence: The State of the Art, 342:1, 2022.
[3] Eleonora Giunchiglia, Mihaela Catalina Stoian, and Thomas Lukasiewicz. Deep learning with logical constraints. arXiv preprint arXiv:2205.00523, 2022.
10

---

[4] Tirtharaj Dash, Sharad Chitlangia, Aditya Ahuja, and Ashwin Srinivasan. A review of some techniques for inclusion of Noominn-knowled into deep neural networks. Scientific Reports, 12 (1):1-15, 2022.
[5] Michelangelo Diligenti, Marco Gori, and Claudio Sacca. Semantic-based regularization for learning and inference. Artificial Intelligence, 2017.
[6] Ivan Donadello, Luciano Serafini, and Artur D'Avila Garcez. Logic tensor networks for semantic image interpretation. In IJCAI, 2017.
[7] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural Probabilistic Logic Programming. NeurIPS, 2018.
[8] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. A semantic loss function for deep learning with symbolic knowledge. ICML, 2018.
[9] Eleonora Giunchiglia and Thomas Lukasiewicz. Coherent hierarchical multi-label classification networks. NeurlPS, 2020.
[10] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic Probabilistic Layers for Neuro-Symbolic Learning. NeurlPS, 2022.
[11] Zenan Li, Zehua Liu, Yuan Yao, Jingwei Xu, Taolue Chen, Xiaoxing Ma, L Jian, et al. Learn- ing with logical constraints but without shorteut satisfaction. In The Eleventh International Conference on Learning Representations, 2023.
[12] Xuan Xie, Kristian Kersting, and Daniel Neider. Neuro-symbolic verification of deep neural networks. 2022.
[13] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-22 215, 2019.
[14] Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su. This looks like that: Deep learning for interpretable image recognition. NeurIPS, 2019.
[15] Zhi Chen, Yijie Bei, and Cynthia Rudin. Concept whitening for interpretable image recognition. Nature Machine Intelligence, 2020.
[16] Alex DeGrave, Joseph Janizek, and Su-In Lec. Ai for radiographic covid-19 detection selects shortcuts over signal. Nature Machine Intelligence, pages 1-10, 2021.
[17] Elisa Maiettini, Giulia Pasquale, Vadim Tikhanoff, Lorenzo Rosasco, and Lorenzo Natale. A weakly supervised strategy for learning object detection on a humanoid robot. In 2019 IEFE-RÁS 19th International Conference on Humanoid Robots (Humanoids), pages 194-201.
IEEE, 2019.
[18] Claudine Badue, Rânik Guidolini. Raphael Vivacqua Carneiro, Pedro Azevedo, Vinicius B Cardoso, Avelino Forechi, Luan Jesus, Rodrigo Berriel, Thiago M Paixao, Filipe Mutz, et al. Self-driving cars: A survey. Expert Systems with Applications, 165:113816,, 2021.
[19] Matt Fredrikson, Kaiji Lu, Saranya Vijayakumar, Somesh Jha, Vijay Ganesh, and Zifan Wang. Learning modulo theories. arXiv preprint arXiv:2301.1145: 2023.
[20] Robin Manhaeve, Sebastijan Dumančié, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in deepproblog. Artificial Intelligence, 298: 103504, 2021.
[21] Emanuele Marconato, Gianpaolo Bontempo, Elisa Ficarra, Simone Calderara, Andrea Passerini, and Stefano Teso. Neuro symbolic continual lcarning: Knowledge. reasoning shortcuts and concept rehearsal. In /CML, 2023.
[22] Yann LeCun. The mnist database of handwritten digits. htp://yann. lecun. comtexdb/mnisl/, 1998.

---

[23] Mare Fischer, Mislav Balunovic, Dana Drachsler- Cohen, Timon Gehr, Ce Zhang, and Martin Vechev. DI2: Training and querying neural networks with logic. International Conference on Machine Learning, pages 1931-1941. PMLR, 2019.
[24] Kareem Ahmed, Eric Wang, Kai- Wei Chang, and Guy Van den Broeck. Neuro-symbolic entropy regularization. In UAI, 2022.
[25] Nick Hoernle, Rafael Michael Karampatsis, Vaishak Belle, and Kobi Gal. Multiplexnet: Towards fully satisfied logical constraints in neural networks. In AAAI, 2022.
[26] Michelangelo Diligenti, Marco Gori, Marco Maggini, and Leonardo Rigutini. Bridging logic and kernel machines. Machine learning, 86(1):57-88, 2012.
[27] Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Wang, and Lise Getoor, Neupsl: Neural probabilistic soft logic. arXiv preprint arXiv:2205. 14266,,, 2022.
[28] Luc De Raedt and Angelika Kimmig. Probabilistic (logic) programming concepts. Machine Learning, 2015.
[29] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229-264, 2002.
[30] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A com- positional atlas of tractable circuit operations for probabilistic inference. Advances in Neural Information Processing Systems, 34, 2021.
[31] Robin Manhaeve, Giuseppe Marra, and Lue De Raedt. Approximate inference for neural probabilistic logic programming. In KR, 2021.
[32] Jiani Huang, Ziyang Li. Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. NeurlPS, 2021.
[33] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. DeepStochLog: Neural Stochastic Logic Programming. In AAAI, 2022.
[34] Emile van Krieken, Thiviyan Thanapalasingam, Jakub M Tomezak, Frank van Harmelen, and Annette ten Teije. A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. arXiv preprini 12 12393, 2022.
[35] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 2021.
[36] Raphael Suter, Djordje Miladinovic, Bernhard Schölkopf, and Stefan Bauer. Robustly disen- tangled causal mechanisms: Validating deep representations for interventional robustness. In International Conference on Machine Learning, pages 6056-6065. PMLR, 2019.
[37] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34: 16451-16467, 2021.
[38] Joaquin Ciinonero-Candelle Masashi Sugiyama, Anton Schwaighofer, and Neil Lawrence. Dataset shift in machine learning. Mit Press, 2008
[39] Emanuele Marconato, Andrea Passerini, and Stefano Teso. Glancenets: Interpretabile, leak- proof concept-based models. NeurIPS, 2022.
[40] Geoffrey Hinton and Richard Zemel. Autoencoders, minimum description length and helmholtz free energy. Advances in neural information processing systems, 6, 1993.
[41] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. In International conference on machine learning, 2014.
12

---

[42] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International conference on machine learning, 2014.
[43] Partha Ghosh, Mehdi SM Sajjadi, Antonio Vergari, Michael J Black, and Bernhard Schölkopf. From variational to deterministic autoencoders. In ICLR, 2020.
[44] Eleonora Misino, Giuseppe Marra, and Emanuele Sansone. VAEL: Bridging Variational Autoencoders and Probabilistic Logic Programming. NeurlPS, 2022.
[45] Francesco Locatello, Stefan Bauer, Mario Lucie, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In ICML, 2019.
[46] Francesco Locatello, Ben Poole, Gunnar Rätsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen. Weakly-supervised disentanglement without compromises. In International Conference on Machine Learning, pages 6348 6359. PMLR, 2020.
[47] Rui Shu, Yining Chen, Abhishek Kumar, Stefano Ermon, and Ben Poole. Weakly supervised disentanglement with guarantees. In ICLR, 2019.
[48] Rafael Müller, Simon Kornblith, and Geoffrey E Hinton. When does label smoothing help? Advances in neural information processing systems, 32, 2019.
[49] Shuang Li, Yilun Du, Gido Martijn van de Ven, and Igor Mordatch. Energy-based models for continual learning. In Energy Based Models Workshop-ICLL 2021, 2021.
[50] Qing Li, Siyuan Huang, Yining Hong. Yixin Chen, Ying Nian Wu, and Song-Chun Chun Zhu. Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In International Conference on Machine Learning, pages 5884-5894. PMLR, 2020.
[51] Hongxin Wei, Renchunzi Xie, Hao Cheng, Lei Feng, Bo An, and Yixuan Li. Mitigating neural network overconfidence with logit normalization. In International Conference on Machine Learning, pages 23631-23644 PMLR, 2022.
[52] Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, and Puneet Dokania. Calibrating deep neural networks using focal loss. Advances in Neural Information Processing Systems, 33:15288-
2020.
[53] Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regularization. The Journal of Machine Learning Research, 23(1):14632-144 2022.
[54] Yiran Xu, Xiaoyin Yang, Lihang Gong, Eisuan-Chu Lin, Tz- Ying Wu, Yunsheng Li, and Nuno Vasconcelos. Explainable object-induced action decision for autonomous vehicles. In IEFF/CV Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[55] Yoshihide Sawada and Keigo Nakamura. Concept bottleneck model with additional unsuper- vised concepts. IEEE Access, 10:41758-41768 2022.
[56] Robert Geirhos, Jörn-Henrie Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning deep neural networks. Nature Machine Intelligence, 2(1 ):665-673, 2020.
[57] Sebastian Lapuschkin, Stephan Wäldchen, Alexander Binder, Grégoire Montavon, Wojeiech Samek, and Klaus-Robert Müller. Unmasking clever hans predictors and assessing what machines really Iearn. Nature communications, 10(1):1-8, 2019.
[58] Kai Yuanqing Xiao, Logan Engstrom, Andrew Ilyas, and Aleksander Madry. Noise or signal: The role of image backgrounds in object recognition. In ICLR, 2020.
[59] Patrick Schramowski, Wolfgang Stammer, Stefano Teso, Anna Brugger, Franziska Herbert, Xiaoting Shao, Hans-Georg Luigs, Kntein Mahlein, and Kristian Kersting. Making deep neural networks right for the right scientific reasons by interacting with their explanations. Nature Machine Intelligence, 278):476-466, 2020.
13

---

[60] Andrew Slavin Ross. Michael C Hughes, and Finale Doshi- Velez. Right for the right reasons: training differentiable models by constraining their explanations. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pages 2662-2670, 2017.
[61] Giambattista Parascandolo, Alexander Neitz, ANTONIO ORVIETO, Luigi Gresele, and Bern- hard Schölkopf. Learning explanations that are hard to vary. In International Conference on Learning Representations, 2020.
[62] Stefano Teso, Öznur Alkan, Wolfang Stammer, and Elizabeth Daly. Leveraging explanations in interactive machine learning: An overview. Frontiers in Artificial Intelligence, 2023.
[63] Wolfgang Stammer, Marius Memmel, Patrick Schramowski, and Kristian Kersting. Interactive disentanglement: Learning concepts by interacting with their prototype representations. arXiv preprint arXiv:21 2021.
[64] Kaifu Wang, Efi Tsamoura, and Dan Roth. On learning latent models with multi celti-instance weak supervision. arXiv preprint arXiv:2306. 13796, 2023.
[65] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8): 1798-1828, 2013.
[66] Aapo Hyvärinen, Ilyes Khemakhem, and Hiroshi Morioka. Nonlinear independent component analysis for principled disentanglement in unsupervised deep learning. Patterns, 4(10), 2023.
[67] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational autoen- coders and nonlinear ICA: A unifying framework. In AISTATS, 2020.
[68] Simon Buchholz, Michel Besserve, and Bernhard Schölkopf. Function classes for identifiable nonlinear independent component analysis. Advances in Neural Information Processing Systems, 35:16946-16661, 2022.
[69] Luigi Gresele, Julius Von Kügelgenn, Vincent Stimper, Bernhard Schölkopf, and Michel Besserve. Independent mechanism analysis, new concept? Advances in neural information processing systems, 34:28233-28248, 2021.
[70] Kartik Ahuja, Divyat Mahajan, Yixin Wang, and Yoshua Bengio. Interventional causal repre- sentation learning. In International conference on machine learning, pages 372-407. PMLR, 2023.
[71] Wendong Liang, Armin Kekić, Julius von Kügelgen, Simon Buchholz, Michel Besserve, Luigi Gresele, and Bernhard Schölkopf. Causal component analysis. arXiv preprinl arXiv:2305.17225, 2023.
[72] Julius von Kügelgenn, Michel Besserve, Wendong Liang, Luigi Gresele, Armin Kekić, Elias Bareinboim, David Blei, and Bernhard Schölkopf. Nonparametric identifiability of causal representations from unknown interventions. arXiv preprint arXiv:2306. 005422 2023.
[73] Eukasz Maziarka, Aleksandra Nowak, Maciej Wolezyk, and Andrzej Bedychaj. On the rela- tionship between disentanglement and multi-task learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 625 641. Springer, 2022.
[74] Séhastien Lachapelle, Tristan Deleu, Divyat Mahajan, loannis Mitliagkas, Yoshua Bengio, Simon Lacoste-Julien, and Quentin Bertrand. Synergies between disentanglement and sparsity: generalization and identifiability in multi-task learning. In International Conference on Machine Learning, pages 18171-18206 PMLR, 2023.
[75] Marco Fumero, Florian Wenzel, Luca Zancato, Alessandro Achille, Emanuele Rodolà, Stefano Soatto, Bernhard Schölkopf, and Francesco Locatello. Leveraging sparse and shared feature activations for disentangled representation learning. arXiv preprint 2304.07900 2023.
[76] Francesco Locatello, Michael Tschannen, Stefan Bauer, Gunnar Rätsch, Bernhard Schölkopf, and Olivier Bachem. Disentangling factors of variations using few labels. In International Conference Learning Representations, 2020. 2020.
14

---

[77] Weili Nie. Tero Karras, Animesh Garg, Shoubhik Debnath, Anjul Patney, Ankit B Patel, and Anima Anandkumar. Semi-supervised stylegan for disentanglement learning, In Proceedings of the 37th International Conference Machine Learning, pages 7360-7369, 2020.
[78] Hao Tang and Kevin Ellis. From perception to programs: regularize, overparameterize, and amortize. In International Conference on Machine Learning, pages 2023.
PMLR,
[79] Alessandro Daniele, Tommaso Campari, Sagar Malhotra, and Luciano Serafini. Deep symbolic learning: Discovering symbols and rules from perceptions. arXiv preprint arXiv:2208. /5611 2022.
[80] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International Conference on Machine Learning, pages 5338 5348. PMLR, 2020.
[81] Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian Weller, et al. Concept embedding models. arXiv preprint arXiv:2209.0905: 2022.
[82] Francesco Giannini, Michelangelo Diligenti, Marco Gori, and Marco Maggini. On a convex logic fragment for learning and reasoning. IEEE Transactions Fuzzy Systems, 2018
[83] Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
[84] Kareem Ahmed, Kai-We Chang, and Guy Van den Broeck. A pseudo-semantic loss for deep generative models with logical constraints. In Knowledge and Logical Reasoning in the Era of Data-driven Learning Workshop. July 2023.
[85] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[86] Tommaso Carraro. LTNtorch: PyTorch implementation of Logic Tensor Networks, mar 2022.
URL https:t//oi...rrg org/ http://g.......2.eeeeeee 5281/zenodo. 6394282.
[87] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://arxiv.orr wwwp:/ss///////.t....oo... 1//./111...9999
[88] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. Advances in neural information processing systems, 28, 2015.
15

---

A Other NeSy Predictors
In this appendix, we outline the NeSy prediction approaches used in our experiments and then show that they share deterministic RSs as DPL.
The semantic loss (SL) [8] a penalty term that encourages a neural network to place all probabiliiy mass on predictions that are consistent with prior knowledge K. In our setting, the SL is applied to a
predictor pa (Y) C) placed on top of a concept extractor pe (C) X) and it can be written as:
SL(po, (x.y): K) == - log E. y) F K} po x)
(11)
Like DPI., the SL relies on knowledge compilation efficiently implement Eq. (11). Importantly, the distribution pa (c x) allocates mass only to concepts с that satisfy the knowledge given y. these are optimal solutions, in the sense that the SL exactly zero. We will make use of this fact in Appendix A.I.
During training, the SL is combined with any regular supervised loss e, for instance the cross-entropy, leading to the overall training loss:
D E(xY)ED C(po. (x, y)) + pSL(po, (x,y), K)
(12)
with μ >> 0 a hyperparameter. During inference, the SL plays no role: the predicted label is obtained by simply taking the most likely configuration through a forward pass over the network.
Logic tensor networks (LTNs) [6] another state-of-the-ar NeSy architecture that combines elements of reasoning- and cemalty-basee approaches. The core idea behind LTNs, and of all other NeSy predictors based of fuzzy logic [82], is to relax the prior knowledge K into real-valued function T[K] quantifying how close a prediction is to satisfying K. LTNS perform this transformation using product real logic [6]. In our context, this function takes the form T[K] : [0, 1] x [o, 1]" - [o, 1]. and it takes as input the probabilities of the various concepts C and labels Y and outputs a degree of satisfaction.
Crucially, fuzzy logies are designed such that, if all probability mass is allocated to configurations (c,y) that do satisfy the logic, then the degree of satisfaction is exactly i.e., maximal. We will leverage this fact in Appendix A.
During training, LTNS guide the concept extractor po X) towards predicting concepts that satisfy the prior knowledge K by penalizing it proportionally to how far away their predictions are from satisfying K given the ground-truth label y. that is. 1 1- (pC x), L y))). During inference, LTNs first predict the most likely concepts è = argmax, po x) using a forward pass through the network, and then predict label ý that maximally satisfies the knowledge given again according to TK]
A.1
Deterministic Optima are Shared
The bulk of our theoretical analysis focuses on DPL because it offers a clear probabilistic framework, however in the following show that deterministic optima do transfer to other NeSy predictors approaches. Specifically, under A2, DPL,, SL, and LTN all admit the same deterministic optima (det-opts).
To see this, let Cy be the set of concepts vectors e from which the label, y can be inferred, that is, Cy = (c ICEC C p² (y | |c) >> 0). Now, take deterministic RS po X) for DPL., i.e., concept distribution that satisfies Definition when the likelihood is computed as in Eq. (2). By determinism, this distribution can be equivalently written a function mapping inputs to concept vectors e(x) E C, that is, po C X = 1[C = é(x)). }. At the same time, by optimality and A2 we have that, for every yx E D, the NeSy predictor (Y X; Ee "k(Y c) (P X) allocates all probability mass to the correct label y. As a consequence, ē(x) E Cy. for every (x.y) E D.
Consider a NeSy predictor that first predicts concepts using po (C X) and then labels using reasoning layer based on fuzzy logic, such that a prediction y E y is chosen so that it minimial distance from satisfaction w.r.t. K, and the distance from satisfaction is also used as training objective. Since é E Cy for every (x, y) E DD by definition of T-norms, the label with minimal distance from satisfaction will necessarily be y: all other labels cannot be inferred from the knowledge.
16

---

so they have larger distance from satisfaction. Hence, training loss will be minimal for this predictor as well, meaning that (o(C) X) is a deterministic RS for it too.
Next, consider a NeSy penalty-based predictor where predictions are obtained by first inferring concepts using MAP over the concept extractor, that is, C argmax, (o | X), and then performing a forward pass over neural prediction layer PY C). By construction, the penalty will be minimal
whenever (y, e(x)) - K. We already established that this is the case for all (x, y) D, meaning that pa C X) is a deterministic RS for penalty-based predictors too.
B Proofs
In the proofs, we suppress K from the notation for readability.
B.1 Proof of Lemma 1: Upper Bound of the Log-Likelihood
Proof plan. The proof of the first point of our claim is split in three parts:
We show that in expectation the log- likelihood in Eq. (2) upper bounded by term containing the KL divergence for pe Y G).
We prove that, under A1, any optimum of Eq. (2) minimizes also the KI.. In this step, we make use of Information Theory [83] to connect the two.
3. We show that assuming Al and A2 the optima pa PY G) for the KL are given only by optima pa Po Y X) for Eq. (2).
We proceed to prove the second point by leveraging the fact that (C G) given by marginalizing Pe(C C X) over the generating distribution y² (X G, S).
Point (i). (I) We upper bound the log-likelihood in Eq. (1) as follows:
C(pe, D) = Ba-n(()Ea-p(())
(x g.s) By-p' (Y x)) log xx]
(13)
Egwp(G) Bxxx' (Xig) B Bynp-rp (ylg) (log (y x))
(14)
Egwp(G) Byrp' (Ylg)
(log Expx (X1g) (Po (y x)])
(15)
Eg By (Ylg)
(ly g))
(16)
log po (y g)
(G) By (YIg)
loogp"p (y g)
(17)
p" (y g)
Eg)D(G) KL(p"(y
() g)]
Hlp (y g))
(18)
In the second line, we introduced the distribution px(x g) = Es Ip g, s)]. in the third line applied Jensen's inequality, and in the fifth line added and subtracted p"(y g). This proves our claim.
(2) We proceed showing that for a deterministic p² (X G, S) every optimum pa (Y X) for the log-likelihowd likelihoodd leads to an optimum po (Y G) for the RHS Eq. (29). We can rewrite the joint distribution as:
y(x,y)= == Be-ns)) g. (y g)]
(19)
E (g) (y g) Earprs) (x s)]
(20)
Eg [p'(y g)p"(x s)]
(21)
Ex-n(C)) [p" (y g)p x)p(x)/p(g))
(22)
(Gpp (y lg))((x)
(23)
= p" (y xx)(x)
(24)
17

---

where p' | x) = Bg- (g)x) (y g)] and p" (G x) is the posterior underlying the data
generative process. Hence, the oogliikel in Eq. (1) can be equivalently written as:
E (xxx)>>(xxx)(loggpp x)] (xxx(() By By-pt(t (Y x) Po [x]
(25)
(x) (Y log (y x)
log <oog"(y"" (y xx]
(26)
pd (y x)
Ex)x(() ( KLip"(y x) (y x)] Hlp" (y x)])
(27)
In the first line, we used p(X, Y) = p' (X), and then added and subtracted logp"(y (y
x).
By comparing Eq. (18) and Eq. (27), we obtain:
Exxp(x)
KL'p" (Y) () x)] Hlp" (Y x))) E # KL (Y g) p g)] H[p (Y g)l)
(28)
Now, consider distribution Po Y X) that attains maximal likelihood. Then, KL(p"(y (y ())lpe x)] 0, and we can rearrange the inequality in Eq. (28) to obtain:
(g) (KL(p"(x (y g)lpp (y g))) = H[Y X H|Y G]
(29)
Here, H|Y X = xxx H[p" (Y x)] and H|Y G| = E g>)(G) H(p ( (Y g)] are conditional entropies.
We want to show that, under A1, the right-hame hand side of Eq. (29) is in fact zero. As for the other conditional entropy term, recall that [83]:
HY X = Y x H|Y] + H|Y = -| Y + H
(30)
where |[---] is the mutual information. rem 2.8.1]. we have:
By the chain rule of the mutual information, cf. [83, Theo-
Y x, = x + IY G
x = J G + +
G
(31)
where 1[:- | is the conditional mutual information. The structure of our generative process in Fig. 1 implies that 1 Y G] = 0, so Eq. (31) boils down to:
|X Y = I G G
(32)
By A1, we have that:
X = H[G X - H(G X, Y
(33)
=H XX) X - HIS (X) X, Y
(34)
HHS (X) X (X)
x
(35)
Plugging this into Eq. (32) entails that I[X Y = I|Y G), or equivalently that H|Y X = H[Y:
GJ. This means that the right-hand side of Eq.. (29) is indeed zero, which entails that the KL is and that therefore po Y G) optimizes the right-hand side of Eq. (5).
(3) We proceed showing that by assuming also A2 whatever optimum Pa Y G) is identified by X) that is also optimum. First, note that under A2 p² (Y G) is deterministic, so we have H[Y Gj O. With Al and A2, both p" (y g) and p² (y x) are deterministic and therefore
po( Y
Eq. (28) can be rewritten as:
E xx) [log (Y = (3k (x) x]] S Eggg=(()) pa po = 3K (g) gg]
(36)
In particular, for each the maximum of the log-lik likelihood is 0 and it is attained when the label probability is one. We make use of this observation the next step.
Next, we show that the bound in Eq. (28) is in fact tight, in the sense that whenever po (Y | G)
maximizes the left-hand side, Po PY X) maximizes the right-hand side. We proceed by contradiction. Fix g and let O be the set of those for which po x f(g.)) s)) < 1 and assume that it has
18

---

non-vanishing measure. Then, the posterior distribution is also strictly less than one:
py g) = (Xig.)) x)]
(37)
= | p(s) gad
/ poly x)pp g, s)dxds
(38)
J p(s) / o1x - f(g. s)xdxds / p(s) / 11- poly |x]]]{x f(g, Jdxds
(39)
= 1 - 1/10000 -pooo x= (gg
(40)
(41)
Therefore, there cannot any optimal solutions pa (Y G) that given by non-optimal probabili- ties po(Y X). This proves the claim.
Point (ii). We consider now which distributions PC G) correspond unique distribution
C X). First, we define as P the set of candidate distributions Pp(C) X), with E θ, for
which it holds:
(s)
= po
(42)
For all distributions of the form Po G) = 1(C c}, for C, P restricts to single element, iee, (C x) = =1{C- cc. We proceed by contradiction and consider a set Ox of non-vanishing
measure such that:
(C x) # 1[C= Vx E Ox
(43)
Let (X G) = Bgnp' (s)P" (X G, G) Then, it holds that:
(C G) /
x pp (C x)p"(x G)dx
=/x =[C=c)r p'(x'x
G)dx+ / PC xx)"'x G) 0x
xxxx
=1-A) +A-
(44)
where we denoted (C G) the normalized probability distribution given by integrating p.p (C X)
on Ox solely, and is the measure of Ox. Notice that the RHS of Eq. (44) exactly 1[C= iff X = 0 or P. (C G) 1(C = c}. which contradicts the claim. Hence, all probabilities CC = 1 cf are only given by probabilities PC x) = 1(C = c), for all x E X.
This yields the claim.
B.2 Proof of Theorem 2: Counting the Deterministic Optima
We want to count the number of deterministic optima the log- in Eq. (1). Recall that, by Lemma 1, under A1 and A2 any optimum po Y X) of Eq. (2) yields optimum po (Y G) of the upper bound in Eq. (5). Following, by point (ii) of Lemma 1 we have that deterministic optima are shared between po C X) and po C G). This means that
equivalently count the number of deterministic optima pe (C G) for the upper bound in Eq. (5). We proceed to do exactly this.
Let A be the set of all possible maps gg CC = I(C (G))). The only a's that achieve maximal likelihood are those that satisfy the knowledge for all g supp(G) for the learning problem, that is:
each inducing a candidate concept distribution
3k(g) = (3k (g))
(45)
i.e., that it is indeed the case that the concepts output by agg) predict the ground- truth label hk(g). Notice that, only one of them is correct and coincides with the identity, i.e., ox(g) g.
These a are those that satisfy the knowledge on all examples, or equivalently the conjunction of the knowledge applied to all examples, that is:
A gEDo
((3k ag) tuk ((k(g)
(46)
19

---

This means that only subset of A contains those maps consistent with the knowledge. The total number of these maps then given by:
Edea C (SK =
(47)
This yields the claim.
B.3 Proof of Proposition 3: Link Between Deterministic and Non-deterministic Optima
Point (i), We begin by proving that, for DPL, any convex combination of optima of the likelihood
Eq. (I) is itself an optimum. Fix any input x. First, p" (y x) is the optimal value of the log-likelihood
in Eq. (2), according to Eq. (29) from point (i) of Lemma 1. Now, let (C x) and y (C))(C) x)
be two concept distributions that both attain optimal likelihood, i.e, for i E (1, holds that
Ee "k(y |c) (c x) = (y x). The likelihood term of any convex combination of the two
optima is given by:
Σ ukly (c x) + (1 - (1-))p(²)( x]]
(48)
Σ ukly| c) x) +(1 A) Σ ukly c)p( x)
(49)
Ap (y p (y x)
Ayp x)
(50)
(51)
Hence, the convex combination is also an optimum of the likelihood. Note that the very same reasoning applies to the Semantic Loss (Eq. (11)), again due to linearity of the expectation over C.
Remark 7. Since SL and DPL limit PC | X) to be factorized as II p(C, X), some convex combinations thut would be in principle solutions as per point (i) cannot be expressed. Essentially, this translates into an additional constraint for the solutions of SI. and DPL that is, given two factorized probabilities (C x) and p(2) x), then:
x1=x))>p x(
X)p (C x) is a solution = + ppC[ is factorized Væ (52)
This applies only to models that integrate probabilistic logic by predicting the concepts indepen- dently, whereby relaxations of SL and DPL, like [10, 84], could naturally express arbitrary convex combinations of deterministic RSs.
Remark 8. The above result does not hold for LTNs, in general. We show this by constructing counter-example for the default choice of T-conorms [6]. That is, a convex combination of deterministic optima that is not itself an optimum. Recall that LTN uses product real logic to define degree of knowledge satisfaction and consider the prior knowledge K = (C1 V C2), where C1 and C2 are two distinct binary concepts. In LTN, the degree of satisfaction of is given by the T-conorm of the logical disjunction, which is defined as S(a, b)
+ ab. Fix an imput x and consider two deterministic distributions (C) x) = 1 (1, T) and p
x) =1(C- = (0,1) T) It is clear that both distributions satisfy the prior knowledge and as such are optimal. Now take any convex combination p(C)- = (C) + (1 - 2)p (C). Then, a = (Ci = 1) + (1 - 2)p (C1 = 1) =)= > and, for similar reasons, = 1 - X. Then, it holds:
S(p(C, = 1), = = X (1 - A) A(1 (1-11 A)
(53)
= - X x 11
(54)
where the equality holds iff X E 10.
Point (i). Under A1 and A2, we can count all deterministic solutions Po C G) via Theorem 2. Here, show that these deterministic optima constitute complete basis for all optimal solutions of Eq. (29). From (i), we have that any convex combination of the deterministic optima is also an optimum. We will show that these are the only optimal solutions.
Recall that the optimal solutions are of the form p" (Y = 3k(g) gg) = 1, as a consequence of A1 and A2 from Lemma 1, for all g supp(G), Notice that any optimal solution (C gg) must place
20

---

mass to those concepts that lead to the correct label. Formally, for every g and y = 5k(g), it holds:
po g) = Σ ukly c)po(c x)
(55)
Σ Po (c g) =
(56)
where the equality holds iff "x(y c) = 1 for all po(c) x) > O. In other words, this means that each C ~ (C g) must be an optimal solution for the logic. This proves the claim.
Point (iii). If A2 does not hold, there can be optima solutions that are given as convex combinations of non-optimal deterministic probabilities. First, notice that according to Lemma 1, point (i), the
optimal solutions for po (Y{ K) minimize the KL term and are equivalent to p" (Y X). Then,
consider for given x an optimal solution p( x) X1 = c1} (1 f) c2) that is
convex combination of two deterministic probabilities. From the convexity of the KL it holds:
[L (yl x) || AuK(y c1; K) + (1 - X)uk(y (y c2; K)]
(57)
S A KL (y x) || uk c1; K)] (1 X) KL (y x) || uk(y K2;
(58)
where the equality holds iff uk(y ci; = uk c2; = p x). This shows that there can exist solutions that are convex combinations of non-optimal deterministic probabilities. We proceed
to show how the space of optimal solutions is defined. On the converse, if uk(y c1 () - ct}
is solution, also ( C2; () - -c2) must be solution:
Σ uk c)(A[CC= = c. + (1 -)1fC = c2ll = p" (y | x)
(59)
)uk(y (1) + -))KKY C2) = -p"(y x)
(60)
Xp-(y x) + (1 AJuk(y C2) = -p"yy x)
(61)
A)uK(y C2) = (1 A)p(y x)
(62)
uk(y C2) = pp p' x)
(63)
We now show that any optimum given by generic (C x). with o E O can be expressed as convex combination of (1) an optimum that is convex combination of deterministic optima and (2)
an optimum that a convex combination of deterministic, but non-optimal, probabilities:
p' x) = Σ
ukly c)p(c x)
(64)
Σ uk(y cc)(Cc xx)+ + Σ "k(y c)p(c | x)
(65)
cECy
CESS
A Σ
uk(y c) x) +
A)
Σ cESy
ukly c)p(c x)
(66)
ceCy
where Cy = fc E C uK = py x)} and Sy C/Cy are two disjoint sets. In the second line, we rewrote the summation on the two terms considering the two sets, whereas in the third À = Eess, p(c x) and p(c x) = p(c x)/(1 - A). Since each p(c x) lead to an optimum by construction, must be that also p(c x) is optimum, by the previous point. In general, there can be many p(c x) leading to optima, even when p(c x) reduces to only the ground-truth element, i.e.,
line we introduced: x = =Eeec, p(c x) and ğic x) = p(c x)/A,
p(c x) = 1{C - fill (x)). Notice that this must hold for all x ~ p (X). This proves the claim.
B.4 Proof of Proposition& 4: Multi-task Learning
When considering multiple task T, suppose that, for each x E n, Dr. we get T different labels y()) ...., (T), each given in accordance to knowledge (())..... ...., K(T), respectively. Similarly to Eq. (2), we consider the learning objective for all tasks with the joint log-likelihood term:
T
log
po (1)
x; K()) =
Logpo(y' (y(() xx; K())
(67)
21

---

Under A1 and A2, Lemma point (1) holds for each task l. In the following, we denote with 8k the underlying maps for each K(t), which by A2 are deterministic. Hence, the learning objective becomes:
C Bx xxx (Y = (ok) (x)) x; K(
(68)
and, similarly to point (i) of Lemma 1, we get the following upper- bound:
T L E Elgpec
(g) g: K(
(69)
Notice that the optimal values for Eq. (69) are given by those distributions that for each term in the summation. Then, following from Theorem 2, we have that the deterministic maps a's that optimize Eq. (69) must be consistent with each task and for each g E supp(G) satisfy:
(()) NEw ((ER) oa)(g) 3K (g)
(70)
which, equivalently to Theorem 2, points to the condition that the maps must be consistent with solving all tasks t. This exactly amounts to solving the conjunction of all knowledge K = Ae K(9, This yields the claim.
B.5 Proof of Proposition 5: Concept Supervision
Let p" | S) be the distribution of ground ground-truth truth concepts restricted to subset S C supp(G):
1 (' S) = -=-" [g) (g) E S} with = Σ p" [g) E
(71)
and p" (X [) (g (GIS)p' (s)P"(X (X g) be the corresponding restricted input distribution.
Under A1, the expectation of the log- log-likelihood term for concept supervision in Section is:
Exep' (x(S) (x(s) log po (1 = fx'(x) (x) x) = Egep' Es (8) log pe (C₁ = gr f(g,s)
S Eg (G]S) log Fs) (po (C, = g, (g.s)))
Eg (G]S) log (C, g, g)
(72)
where (X| S) = (iss (X gg s). In the first line we made use of A1 to write
x = (g, 8), in the second line we used Jensen's 's inequality, and then we introduced the marginal distribution po( (C G) (s) (po ( [GG s))]. Recall that I denotes the subset of the supervised ground-truth concepts and that the ligelikeldhood is evaluated only w.r.t. those concepts.
Now notice that, given A1, the maximum for the LHS of Eq. (72) is zero, i.e., coincides with maximum log-likel Consistently the RHS of Eq. (72) is zero only when PC g) places all mass on gy. We proceed considering those maps a g + e which lead to deterministic, optimal solutions for the RHS. For these, must hold that for each g S:
NEE (g gi
(73)
When taken all together, can estimate how many E A (cf. Appendix B.2) satisfy the above condition for all g:
Eeed Aiet (g(g) = gi
(74)
This yields the claim.
B.6 Proof of Proposition 6: Reconstruction
Under A1, the reconstruction penalty can be written as:
Ex) = -E (G) E Ex-e (Kn.s) (oa c,2)
(75)
-C) htt.://cosssscccccc/c//////////e c.zz] (76)
22

---

From A3, we have that the both encoder and decoder distributions are factorized:
Pe Pe z f (g. s)) pa(c g) s)
(77)
Po ()) c, Pe (g c)pp(s z)
(78)
This yields:
Exxp(X) [xxx( - (gg (G)) (
(erp Plgg (g/c)] + (Z)) pe [s]z
- Fggap' (G) (C P Pvo (glc) Espp"(s) (8) Po (Zis log Po (s|2)
Eggp (G) (C po
(79)
where in the first row we separated the two logarithms and removed the expectations on (o (Z s) and pa (C) g) for the terms (g(g c) and ( z). respectively. In the third line, we discarded the term with the match of the reconstruction of the style, giving the lower bound.
When R goes to zero, the lower bound also goes to zero and the last term of Eq. (79) minimized.
This happens whenever, for each ~ po g). it holds that (g c) = 1. This condition also implies that if for two different g'' and g" there exist at least one such that (o -pocc g") >
then (g c) and (g c) cannot both be optimal.
We restrict now to a deterministic map a g ト c for pe (C G) and describe the condition when optimal decoders are attained, i.e., Pw (g c) = 1 for some c. By the previous argument, an optimal map a that leads to optimal decoders must always map ground-trute truth concepts g different concepts c, that is:
a(g' + agg")
Vg' + g"
(80)
In particular, this condition must hold for all different GG). The number of all solutions is then given by:
EnEA I(AREaupPO Ex'euppo a(g) # a(g')
(81)
as claimed.
C Experimental Details and Further Results
We report here all further details concerning the experiments Section 6.
C.1 Implementation
The code the experiments builds on top of nesy-cl [21] and CBM-AUC [55]. All experiments are implemented with Python 3.8.16 and Pytorch [85] and run over one A100 GPU. The code for the experiments is available at cttpuuu.oooo/rassnnngshhsheeeeee
The implementation of DPL is taken from [21] and follows exactly Eq. (1), where to each world label is assigned accordingly to the prior knowledge K. We implemented SL following the original paper [8]. with the only difference that the prediction of the labels Y is done top of the logits of (C x). This relaxes the conditional independence between labels and concepts while being more in line with the generative process assumed. The implementation of LTN is adapted from LTN-Po pyN-yyyorch [86] and is based on the satisfaction loss introduced in Appendix A.
C.2 Data sets & Count of the Reasoning Shortcuts
Here, we illustrate how to count explicitly the number of deterministic RSs using the equations in Table 1, restricting ourselves to the case where no disentanglement is in place, for simplicity. Similarly to Section 4, we assume A1 and A2 and that GGp = C G, and count the total number of deterministic optima (or det-opts for short) under different mitigation strategies. In the following, Cy C C G refers to the set of c. E C or g E G that are mapped by K to label y y. Note that Ey Cyyl [G).
Explicit count for the likelihood. When the concept extractor po(C) X) sufficiently expressive, the deterministic mappings are essentially arbitrary. Specifically, the set A of these a' includes all functions from G to C. These functions can be explicitly enumerated by counting how many ways there are to map each input vector g to arbitrary vector
23

---

Here, we are interested in counting the number of a's that attain optimal likelihood. Each such has to ensure that each g E 9 is mapped a c E C(s(()) that yields the correct label, or in short, Vg. a(g) E (g)(g) This condition is satisfied if and only if, for every y in the data set, every g E Cy mapped to a e that is also in Cy, and there are exactly [Cy|(c) ways to do this. This immediately shows that the overall number of det-opts is:
ELEd 1 M (g) a(g) -Ilyey Cy Cy|lcy|
(82)
This associates an explieit number to Theorem 2.
Explicit count for the reconstruction. The effect of adding a reconstruction penalty is that now, in order to achieve optimal loss, has to map different g's to distinct concepts c's. Unless this is the case, it becomes impossible to reconstruct the ground-truth concepts from the learned ones, and therefore the imput x generated from them.
The resulting computation is the same as above, except that now we have to associate the different 's to different c's without replacement. This yields the following count:
Eoea L ()) a(g) } =[MRR'EEWAR a(g) + a(B')) Illelllyy |Cyl!
(83)
Explicit count for concept supervision. For the combination of logic and concept supervision, we suppose that for each equivalence class Cy. there are Vyy ground-truth concepts provided with
supervision and that all concept dimensions C2 receive this supervision. Let S C g be the set of supervised concepts, such that [S] Eyey By. From above, this means that we are specifying total of [S] ground-truth concepts. From Table I, we have that the number of det-opts amounts to:
E.Ea (3 (g) = { (MEES N (g 9t} = Iyye |yyl (84)
Finally, combining together the terms of prediction, reconstruction, and concept supervision, we obtain:
EaEd1 A (Boa)(g) = a(g) =(8)) )x
(85)
REG
ag)) + a(g'))
(86)
g.g' g.g' Eggg
(g) 9 8ES
II Ccy By yEY
(87)
The disentangled case. If the network is disentangled, the enumeration procedure becomes sub- stantially more complicated and cannot be written compactly in closed form. While the number of deterministic optima can still be computed exactly using model counting [29, 30], doing so is not necessary for the scope of our paper and therefore left to future work.
C.2.1 Dataset: XOR
This dataset, introduced in Example 3, is a toy data containing 3 bits g (g), 92, ga), for total of 8 possible combinations. The task consists in predicting the XOR operation among them, namely y (g1 b 92 @ gs). The dataset is exhaustive and has no validation and test set. The model performances are evaluated on the training set.
Reasoning shortcut. For this dataset, we have |Col |.| 4. RSs arise depending the structure of the underlying network. When the ground-truth concepts are processed all together without any mitigation strategy, we obtain that the number of det-opts amounts to:
II C,, |c,1 yE>
1c11
44.4
(88)
24

---

The confusion matrices for all methods are reported in Appendix C.5. On the other hand. we show that in the disentangled case, only combinations suffice identify the correct solution, e.g.
(0)) @ (0)) @ a(0) = (a))) @ (0) ① a(1)
(89)
and here the only viable solution for the two a(0) = and (11) = This condition met in all experiments in Table 2.
C.2.2 Dataset: AWIST-AdditiN
We consider the version introduced in [7], which consists of couples of digits, each ranging from to 9, and the target consists in predicting the correct sum, i.e., y + 92. This data set contains all possible combinations, for total of 100. The training set contains 42k data, the validation set 12k, and the test set 6k.
Reasoning shortcuts. RSs arise only as a result of the joint prediction of both digits. Notice that the number of elements Cyl for each sum y can be evaluated as:
|cyl = y + 1, y < (18 - y) + 1, otherwise.
(90)
Therefore, the total number of der-opts amounts to:
|,, = II 29 10 II
(91)
vey
y=1
When providing disentanglement, the number RSs reduce to 0, as it sufficient to have the sums:
a(c) + a(c) = 2 c
(92)
to uniquely identify the value the digit c.
C.2.3 Dataset: MNIST-EvenOdd
This data set, proposed by [21], is a biased version of MMIST-Addition. where only some combina- tions of the digits appear. We consider here more challenging scenario w.r.t. the proposed version, consisting of the sums:
10
10
10 A
(93)
10
Ø 12
12
Overall, the training set contains 6720 data, the validation 1920, and the test 960.
Reasoning shortcuts. We describe the RSs that arise even when the architecture incorporates disentanglement. We evaluate the possible RSs empirically noticing that the system of observed sums can be written as a linear system, as done by Marconato et al. [21]:
(0) + a(6)
(<11) a 6
a(2) + a(8) 10
a(3) a 10
(94)
a(4) + a = 10
a(1) + a9) = 10
(444) + a(8) 12
(a3)) + (9) = -22
Now, notice that we can find independent reasoning shortcuts for each of the two sides since they do not share any digits. For the LHS, we consider the sum aa)) = 10 and notice that we can find at most 10 different attributions for having correct sum. Notice that, some of them are not allowed as (8) = 0, leads to inconsistent values for the fourth sum, and a(8) ) = 3 leads to an inconsistent sum for the first equation. So in total, for the LHS, obtain 7 possible solutions and, by symmetry, the same number also for the LHS. In total, the number of der-oprs is equal to 7 7.
Experimentally, we consider limited concept supervision on / (4. which should be sufficient, in principle, to disambiguate between even and odds digits. This happens because specifying a44 = and (9) 9 admits only the ground-truth concepts as the optimal solution.
25

---

C.2.4 Dataset: MNIST-AddMul
In this dataset, we consider fewer combinations of digits, explicitly:
e
2
(95)
4
and similarly for multiplication. This data set contains 1680 training examples, 480 for the validation, and 240 for the test set.
Reasoning shorteuts. For the case of the addition task, we can have possible solutions, which are:
(=) = 0, ((1) = 1, (2) = 2, and (3) = 3; aa( a (2) 1. and a33 4.
For multiplication, we have that since a(1) aa3) = 3 it can be either a(1) or a<(1) = 3. In both cases, holds that (0) 0 and ax2) be arbitrary. Hence, there in total 2 44 possible det-opts. In MTL, the reasoning shortcut for the addition does not hold since it leads to sub-optimal solution for multiplication.
C.2.5 Dataset: BDD-OIA
This data set contains frames of driving scene videos for autonomous predictions [54). Each frame is annotated with binary labels, indicating the possible actions, Y gnove_forward stop, turn_left, turn_ turn_right). Each scene is also annotated with 21 binary concepts C, underlying the reasons for the possible actions, see Table 5. The training set contains 16k frames, with full label and concept supervision; the validation and the test set contain 2k and 4.5k annotated data, respectively.
For designing the prior knowledge w.r.t. to the concepts in Table 5, we make use of the following rules for move_forward stop predictions:
red_light = -green_light
obstacle V person V rider oother obsea_obstacle
road_clear = mosttacee
(96)
green_light follow V clear = move nove_forward
red_light V stop_sign V obstacle = stop
stop = move_forward
For Surn_lefft and similarly for tarturright we use:
can_turn turn left_lane V Lell__green_liggeeeeeee left_follow
cannot_ turn = no ww_leet______eeeeeeeeeeeeeeeeele lel__lftteeeeeee leftllesttaceeeeeeeeeeee Left_solid_Iie can_turn A -cannot_ turn = turn_left
(97)
Notice that, since the concepts are predicted together, as explained in Appendix C.4, we can count the number of RSs follows:
For move_forward and stop, the labels are predicted with the constraints such that (move_fosse mnove_forward, stop) (1, has no support. Hence, we consider only the predictions (0, 0), (0, 1), (1, Next, we identify:
|Coool = 1, since it corresponds just to the case where no concepts are predicted.
(C,,0) = 23 1, which is the number of different concepts attribution for forward yielding a positive label:
(Co.1)) = 280 are the combination of the remaining concepts that yield the stop action, in agreement with the constraints. These were counted explicitly from the logic implementation.
Overall, the number of det-opts amount to 1- 7? 280280
For turn_ left and surn_right we count the cardinality of positive and negative predictions of the two classes CCo and [Cr]:
26

---

[C = 2 1. that are the only concepts attributions for the positive label;
[Col = 2 |rll are all the remaining concept combinations.
For left and right, separately, we obtain that possible optimal solutions amount 7" 5757.
Altogether, count of det-opts for BDD-OIA goes as follows:
II
Cy |Gy| .7 280280 77 5777 77. 577
(98)
yEy
Table Concepts annotated in BDD-OIA. Table taken from [54]
Action Category
Concepts
Count
green_light
7805
move_forward
follow road_clear
3489
4838
red_ red_light
5381
traffic_sign
1539
car
233
stop
person
163
rider
5255
other_obstacle
455
left_lane
154
left.green_light
885
left_follow
365
turn_left
no no_left_land
150
left_obstacle
666
letf_solid_Ine
316
right_lane
6081
Bight_green_lit
4022
right_follon
2161
turn_right
no no_right_lane
4503
right_obstacle
4514
right_solid_line
3660
C.3
Optimizer and
Selection
The Adam optimizer [87] was employed for all experiments, with exponential decay of the learning rate amounting ? 0.95, exception made for BDD-OIA, where added weight-decay with parameter w = 4- 10 and was set to 0.1, to avoid over-fitting.
The learning rate for all experiments was tuned by searching over the range 10 : 10-2, with total log steps. We found the SL penalty of and 10 for XOR and ANIST-AddMul, respectively, work well in experiments. The strength of the single mitigation strategies (n)) for each method 2,5 5, 10), varying the learning rate.
was chosen accordingly to a grid-search over 77 E {0.1, 0.5, 1, The best hyper-parametery were selected, in the first step, based Fi-score for label accuracy on the validation set and, in the second step, on the lowest mitigation loss, accordingly to the value in the validation set. In particular, for SL chose those that yielded the best trade-off between SL. minimization and label prediction. For LTN, we found that concept supervision did interfere with the original training objective, for which the best weight for the mitigation strength was found at ? 10 It was adopted for both LTN+C and LTN+R +C in Q2 of Section 6. The param--ass for the combined mitigation strategies were selected according to the aforementioned criterion, by only searching the best-combined mitigation strength, while keeping the individual best strengths fixed from the previous grid search.
the highest performances in
For BDD-OIA. we selected the learning rate ranging in the interval 10 + 10 upon selecting those with best Fi-scores labels in the validation set. The strength of the concept supervision and entropy regularization were varied in between 1,5).
All best dyper-parametee for our tests reported in the code in the Supplementary Material.
27

---

C.4
Architectures
processed each XOR: For this data set, we adopted two MLPs, one for the encoder Pa G) and one for the decoder Pa(G C), both with a hidden size of 3 and ReLU activations. This architecture is used to empirically validate RSs without forcing disentanglement. For the disentangled case, we considered linear layer with weight w and bias b.
For SL only, added an additional MIP,, with hidden size of 3 and tanh activations, implementing the map from the logits of C to Y.
MNIST-AddMul: We report here the architectures that has been used for IWIST-Adiition INIST-Kultiillictiion and MNIST-EvenOdd. For the joint prediction, i.e. without disentan- glement, used the encoder in Table 6. When considering disentanglement, digit with the encoder Table and then stacked the two concepts together. For the reconstruction, used the decoder in Table 8. For SL only, added an MLP with hidden size of 50, taking as input the logits of both concepts and processing them to the label.
Table Double digit encoder for MNIST-
INPUT SHAPE
LAYER TYPE
PARAMETERS
ACTIVATION
(28, 56, 1)
Convolution
depth=32, kemel=4, stride=2, 1
ReLU
(32, 14, 28)
Dropout
p 0.5
(32, 14, 28)
Convolution
depth=64, kerne=4,, stride=2, padding
RcLU
(64, 7, 14)
Dropout
= 0.5
(64, 7, 14)
Convolution
depth=128, kemnel=4, stride=2, padding=1
ReLU
(128, 3.
Flatten
(2688)
Linear
dim=20, bias True
Table Single digit Encoder for MNIST-AddMul
INPUT SHAPE
LAYER TYPE
PARAMETERS
ACTIVATION
(28, 28, 1)
Convolution
depth=61, kernel=1, stride=2, padding=1
ReLU
(14, 64)
Dropout
0.5
(14, 14,,14,64 64)
Convolution
depth=128, kerne=4,, stride=2, padding=1
ReLU
77,
Dropout
0.5 depth=256, kernel=1, stride=2, padding=1
7,28)
Convolution
ReLU
(,6)
Flatten
(2304)
Linear
dim=10, bias True
Table 8: Decoder for MNIST-Additinn
INPUT SHAPE
LAYER TYPE
PARAMETERS
ACTIVATION
(40,
Unflatten
(128, 3,7) 7)
ConvTranspose2d
depth=64, kemel=(5, 4), stride=2, padding=1 p = 0.5
ReLU
(64, 7, 14) 14)
Dropout
(128, 3,
Conv ConvTranspose2d
depth=32, kerne=(44, 4), stride=2, padding-1
ReLU
(32, 14, 28)
Dropout
p 0.5
(128, 3,
ConyTranspose2d
depth=1, kemel= 4), stride=2, padding=1
Sigmoid
BDD-OIA: Images of BDD-OIA are preprocessed following [55] with a Faster-RCNN [88] pre-trained on MS-COCO and fine-tuned 100k [54]. Successively, we adopted the pre-trained convolu- tional layer on [55] to extract linear features, with dimension 2048, These are the inputs for the NeSy model, which is implemented with fully-connected NN, Table 9.
28

---

Table 9: Fully connected layer for BDD-OIA
INPUT SHAPE
LAYER TYPE
PARAMETERS
ACTIVATION
(2018, 1)
Linear + BatchNorm ld
dim=1024
Softplus
(1024)
Linear BatchNormid
dim=512
Softplus
(512)
Linear + BatchNormid
dim=256
Softplus
(256)
Linear + BatchNormid
dim= 128
Softplus
(128)
Linear + BatchNormld
dim=21
Softplus
29

---

C.5
Confusion Matrices
Following, we report the label and concept-level confusion matrices (CMs) for XOR, MMIST-EvenOhe and MNIST-Mul score over the labels.
For all of them, we report those obtained in runs with maximal Fi-
C.6 XOR
NONE
DIS
10A.0)
(10.11
10.041
(0.14)
(0.1.0
[04.43
11.,00
(1.10)
(11111
DPL
LTN
DPL.
LTN
Figure 3: CMs for XOR: (Left) All NeSy models fail for RSs without any mitigation. (Right) Providing DIS avoids all RSs.
C.7 SELLST-venDdd
Predicted
Predicted
Predicted
2 3 5
0 1 2
1 2
4 5
6 7 8 9
0
L AWN
Ground-truth
2
2
3
7
8
9
Figure 4: NeSy models without mitigation strategies. (Left) DPL picks RS that uses only 3 digits. (Middle) SL optimizes for label predictions but does not always predict a correct configuration for the digits. (Right) LTN also picks a RS using only 3 digits.
Predicted
Predicted
Predicted
1 2 3 4 5 8
0
0
Ground-truth
0aLont PNN
Figure 5: NeSy models with R. (Left) DPL picks a sub-optimal RS, (Middle) SL optimizes for label predictions but through RS. (Right) LTN also picks sub-optimal RS. For all runs, we found that interferes with the standard learning objective DPL and LTN, respectively.
30

---

Predicted
Predicted
Predicted
1
2 4
789
189
0
Ground-truth
A
2
2
2
3
5
5
00
7
9
9
Figure 6: NeSy models with C. (Left) DPL picks a sub-optimal RS and fails to predict correctly the digits 4 and 9. (Middle) SL predicts correctly the 4's and 9's but does not avoid the RS. (Right) LTN
picks a RS that uses only 3 digits.
Predicted
Predicted
Predicted
0
1
2
3
6 7 4
5
012
3
4
5
6
7
8
0
1
2
3
4
5
7
0
1
Ground-truth
2
3
4
4
6
6
5
6
7
7
8
8
9
9
Figure 7: NeSy models with h. (Left) DPL picks RS that uses concepts more sparsely. (Middle) SL picks a RS, irrespectively of the mitigation. (Right) LTN tends align the diagonal but fails to predict correctly multiple digits. The performance, nonetheless, is sub-optimal.
Predicted
Predicted
Predicted
4
0 1 2
3 4 5 6
7
0 1
3
7
8
Ground-truth
6 00 0000000 1
3
7
9
Figure 8: NeSy models with R and и. (Left) DPL picks sub-optimal RS by using only three digits. (Middle) SL picks a RS. (Right) LTN learns correctly the odd digits but learns a RS for the even ones.
Predicted
Predicted
Predicted
1
2 3 4 5 6 7 8 9
0 1
2
3
4
5
6
7
8
0
2 3 4
5 6 7 8 9
Ground-truth ttrth
1
2
Ground-tree
000 4
6
Figure 9: NeSy models with R and C. (Left) DPL picks sub-optimal RS by using only three digits. (Middle) SL improves along the diagonal but fails to correctly encode four digits. (Right) LTN picks a RS.
31

---

Predicted
Predicted
Predicted 2
2 4 5
6
7 8 9
Ground-truth
2
Figure 10: NeSy models with and н. (Left) DPL correctly retrieves almost all digits but fails with the digit 7. For this method, we also found runs completely recovering the diagonal. (Middle) SL picks sub-optimal RS. (Right) LTN avoids the RS.
Predicted
Predicted
Predicted
2
2 3
2 3
0
0
Ground-truth
2
2
2
33
3
3
4
5
5
6
5
000
Figure 11: NeSy models with R, C and и. (Left) DPLcorrectly identifies the underlying concepts.
(Middle) SL does not avoid RSs. (Right) LTN also identifies the correct digits.
32

---

C.8 MNIST-
Predicted
Predicted
Predicted
Ground
Figure 12: CM the addition task. All models, DPL (Left). SL (Middle), and LTN (Right) fail for the RS introduced in Example 1, while failing also to predict the digit 3.
Predicted
Predicted
Predicted
Ground-truth
Figure 13: CM the product task. (Left) DPL picks RS where it fails capture the correct semantics of all digits, except 0, (Middle, Right) SL, and likewise LTN, acquires a RS where it never predicts correctly the digit 2.
Predicted
Predicted
Predicted
Ground-truth
Figure 14: CM MTL. Once the predictors are trained for solving addition and multiplication jointly through MTI., they all successfully acquire the concepts with the intended semantics: all confusion matrices are very close being diagonal.
33


Reviews:
[{"review_id": "ZJRio1Rki7", "reviewer": "Reviewer_yCW5", "summary": "The paper presents a in depth analysis of reasoning shortcuts and the impact they have of the learning process of neuro-symbolic learners. \nOn the ground of the performed analysis, they propose 4 different mitigation strategies to alleviate the problem: \n\n1. Knowledge-based mitigation\n\n2. Data-based mitigation\n\n3. Objective-based mitigation \n\n4. Architecture based mitigation ", "questions": "See above", "limitations": "Not applicable", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper studies an important problem and it is very well presented. It is easy to follow and the formalisation of the concept of reasoning shortcuts was needed. \n\nThe experimental analysis supports the claims. ", "weaknesses": "I have only couple of perplexities regarding the first two mitigation strategies: \n\n1. in the knowledge-based mitigation, the authors claim that depending on the application, collecting new knowledge might not be feasible. They then proceed in proposing Multi-task learning as a practical alternative. Here it is were I get confused: \n     - how can this be more practical? In addition to collecting more knowledge you now need to collect additional labels. \n     - if I understand correctly, in proposition 4 in the end the conclusion is anyway that the deterministic optimum $p_{\\theta}(\\mathbf{C} \\mid \\mathbf{G})$ of the MTL loss is a deterministic optimum of a single task whose prior knowledge is the conjunction of all the prior knowledge used in the different MTL tasks. How is it then better defining different MTL tasks than collecting more knowledge? \n\n2. In section 5.2 the authors say that RSs can occur also when the dataset is exhaustive. This to me seems more of a problem related to not choosing the right concepts, for the task, i.e., there is not a bijective correspondence between the concepts in $\\mathbf{C}$ and $\\mathbf{G}$. For example, suppose we have the (very simple) task of distinguishing bird images from non-bird images, and suppose we have one concept encoding the classes \"pigeon, flamingo, duck\" (and we have the simple background knowledge that any of these classes implies \"bird\"). In this case, one mitigation strategy could be to add more supervisions on the concept (as proposed), but wouldn't it be better to actually take concepts that are \"meaningful\" for the task? \n\nOn the line of the last point above, I was very surprised from the amount of reasoning shortcuts learnt in the MNIST-addition task in table 2. Can you provide some examples for such RSs? Also, these results are taken on *optimal* runs. What would be the results on 30 *standard runs*?  Also, can you provide some results in terms of accuracy on both the concepts and the final outcome when using disentanglement and when not? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments about our work, in particular for finding it important, needed, and well-presented. Below, we address their concerns.\n\n**Is MTL more practical than further constraining the prior knowledge?**\n\nWe agree that, compared to constraining the knowledge only, multi-task learning (MTL) is more expensive in that it requires gathering both extra knowledge and extra labels.  However, MTL is a sensible choice whenever the first option is infeasible, as we noted in Section 5.1.  It is in this sense that MTL is more practical.\n\nTo see this, consider the MNIST-Addition experiment (Table 3, bottom). Here, the knowledge specifies how to perform addition and no extra constraints can be added without changing the semantics of the task. This can be side-stepped by pairing the latter to a multiplication task, and doing so completely avoids RSs.\n\nSection 5.1 currently reads “experts may not be available, or it may be impossible to constrain K without also eliminating concepts with the intended semantics”.  We agree this is confusing and will change it to “experts may not be available, or it may be impossible to further specialize the knowledge K without altering the semantics of the prediction task”.\n\n**Do Reasoning Shortcuts appear when changing the underlying concepts?**\n\nWe fully agree that the structure of the knowledge K and the concepts appearing therein determine whether, and how many, RSs exist.  This follows from Theorem 2.\n\nManipulating K and C is one way of reducing the number of RSs.  One option is to replace low-level concepts with higher-level variants.  For instance, in BDD-OIA one could compact all obstacle concepts (e.g., “pedestrian”) into a *single* “obstacle” concept.  This leads to a sensible reduction of RSs, which can be evaluated using Eq. (6).$*$\n\nThe main issue is that doing so is not always possible. In the XOR problem, for instance, we cannot lump together any concepts without changing the semantics of the problem.\nIdentifying cases in which concept manipulation can work, and automating said procedure, is an interesting research question worth investigating in future work.\n\n$*$ This case still obeys Theorem 2 if we replace C, G, and K with their “coarser” variants.\n\n**Extended results for Table 2**\n\n**Example of RSs for MNIST-Addition:** In section C.2.2, we described the RSs affecting the MNIST-Addition task with all digits. We will clarify this in the main text. The idea is as follows: when both digits are processed together (no disentanglement) the model can map the two digits to whatever combination of concepts gives the correct sum. As an example, all the sums $G_1 + G_2 = 0 + 2 = 1 + 1 = 2 + 0 = 2$ can be mapped to the combinations $C_1=1$ and $C_2=1$.\n\n**Optimal vs. standard runs:** The reason why we considered 30 optimal runs is because reasoning shortcuts are defined as models that achieve (near) optimal performance by leveraging unintended concepts.  The performance of standard models is not representative of this definition.\n\nRegardless, we report the label and concept accuracies of 30 such models in the rebuttal PDF for DPL, SL, and LTN on both MNIST-Addition and XOR, with and without disentanglement.  All models fare much better at prediction labels rather than concepts, as expected, indicating that even “non optimal” models suffer from RSs.  These results are compatible with those reported in the main text.\n\n*More in detail*: without disentanglement (-), all models achieve high label accuracy (Acc$(Y)$) by leveraging poor quality concepts, as shown by the low concept accuracy (Acc$(C)$).  By imposing disentanglement (DIS), the concept accuracy generally improves, indicating that models get closer to the intended semantics. \n\nOn the XOR data set, some of the models learned do not reach optimality, regardless of architecture (DPL, SL, LTN).  This occurs because they sometimes remain stuck in bad local minima, with and without disentanglement.  This is reflected by the large variance observed in the XOR results. Conversely, on MNISTAddition, we obtained stable runs, yielding most of the time an optimal behavior. The only exception here is LTN without disentanglement, for which we observed more variability.\n\n"}, {"review_id": "QzkErKQp04", "reviewer": "Reviewer_szNE", "summary": "_Background_: The authors are interested in studying the properties of sequential, two-stage neuro-symbolic pipelines. Stage 1 is a neural network that reduces a high dimensional input (eg: an MNIST image) to a low-dimensional relaxation of a symbolic space (eg: 10 dimensional onehot vector) and Stage 2 is a probabilistic function (neural network or otherwise) that predicts the labels given the symbols utilizing a provided knowledge base. However, when trained end-to-end, the symbolic representation often collapses and the symbols learned are not equivalent to the ground truth symbols. This is called a reasoning shortcut (RS).  \nThis work focuses on investigating the causes of such reasoning shortcuts and presenting suitable remedies for the same. The authors formally define reasoning shortcuts for NeSy architectures as symbolic mappings which allow the model to achieve a locally optimal loss, but whose semantics do not match the ground truth semantics.  \nThe authors identify four factors to mitigate the occurrence of reasoning shortcuts: 1) additional prior knowledge,  2) additional data, 3) additional reconstruction targets in the objective function, and 4) additional inductive bias in model architecture design. They study the impact of these reasoning shortcuts mitigations on five NeSy prediction tasks with three NeSy algorithms.  \nThe authors find that different combinations of mitigation strategies helps improve performance in different cases.", "questions": "See weaknesses section", "limitations": "The authors have adequately addressed potential limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:** \n-  While the concept of reasoning shortcuts was previously known, this paper is the first to offer a formal definition and analysis of reasoning shortcuts as a limitation of instantiations of neurosymbolic models.  \n- The mitigation strategies proposed are widely used in the neurosymbolic community, but they haven’t been connected before under the umbrella definition of reasoning shortcut mitigations. Hence, this paper brings a fresh perspective to why such strategies work well for NeSy systems.\n\n**Quality and Clarity**\n- The setup, definition, and analysis of reasoning shortcuts is well motivated and well explained.\n  \n**Significance**\n- The paper identifies a significant problem with previous work and provides a formal definition of the problem and mitigation strategies to address the problem. \n- I’m intrigued by the analysis of counting reasoning shortcuts because it presents a method to quantify how well a knowledge base describes a dataset / data generation process. \n", "weaknesses": "**Clarity:**\n- Table 1: DIS is mentioned in the caption, but no row for it exists in the table. \n- Table 2: It took me a long time to figure out that each number is the frequency of RSs for a baseline on a dataset. Please explain what the rows, columns, and values mean for each table. \n-  Line 276: “when forcing disentanglement…” Disentanglement is a property of the architecture. How is the architecture modified to enforce disentanglement? The appendix doesn't mention this. \n- “Roughly speaking, a concept F1 below 95% typically indicates an RS” I’ll defer to the author's judgement here because I’m not familiar with the data, but to me, a low concept F1 *on its own* signifies that the symbol extraction hasn’t been successful. Did the authors perhaps mean a low concept F1 but a high prediction F1 hints at the existence of RS's? \n- Table 4 results: I'm not sure that I understand the results here. I defer to the authors, but I think this table and task demands extra scrutiny. \n  - The prediction accuracy and the concept accuracy both seem low (< 80% as a ballpark figure). Is this close to the state-of-the-art performance for this dataset? \n  - \"concepts tend to align much closer to the diagonal...\" I don't quite understand how being closer to the diagonal implies better concept generalization. The concepts aren't ordered, so an incorrect prediction, regardless of perceived distance from the correct concept, should be incorrect. Maybe I'm misunderstanding this sentence. \n\n**Significance:**\n- The method only compares against ablations of the same model. I'm concerned that this paints an incomplete picture about the relative performance of NeSy predictors compared to other models on these tasks. This lowers the significance of this architecture for the neurosymbolic community. I'd advise the authors to look into other fully neural and neurosymbolic methods that might have similar problem statements, and/or provide reasons for why the baselines are not suitable for the datasets. I've provided a couple of works I'm familiar with that are related (but not exactly equivalent) to the base algorithm studied in this paper.\n  * ROAP[1]: ROAP presents an end to end algorithm for symbol grounding and symbol manipulation when external knowledge is not available, but we have diversity of tasks to instantiate a multi-task learning objective. I am reminded of ROAP because one of their tasks is similar to the MNIST digit grounding tasks presented here. \n  * Concept Embedding Bottleneck models[2]: Concept embedding bottleneck models instantiate an extra layer that creates a concept embedding that's used for downstream prediction. I am reminded of CEM models because their algorithm is geared towards leveraging explainable symbolic information in real world tasks without loosing accuracy.    \n  * I'd also be interested in whether the authors think these models use the mitigation strategies presented for reasoning shortcuts.\n\nOverall, I'm giving this paper a __weak accept__. The authors formalize an interesting problem which is definitely interesting to the broader neurosymbolic community. However, the related work / evaluation focuses on a very specific definition of neurosymbolic models.\n\n[1] https://arxiv.org/abs/2206.05922\n[2] https://arxiv.org/abs/2209.09056", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest in our paper and for finding it clear and significant. Below we address the points raised by the review.\n\n**Typos and clarifications:** \nThank you for pointing these out, we will update Tables 1 and 2 accordingly.\nAs indicated in the main text, our architectural implementation of disentanglement is described in Appendix C - and specifically in Section C.4.  We will clarify this.\n\nThe concept confusion matrices illustrate the mapping between ground-truth and learned concepts.  Specifically, rows/columns each represent a concept vector c (or g) and are sorted lexicographically (i.e., the first row is the vector (0, 0, 0), the second row is (0, 0, 1), etc.)  A model unaffected by RS would have c = g, so its confusion matrix would be the identity.  The more diagonal the confusion matrix, the better the semantics acquired by the model.  We will clarify this in the text.\n\n**The 95 \\% threshold:**\nWe chose a threshold of 95% on the F1-score as a proxy for non-RS solutions because the best-performing approach, DPL+H+C, achieves F1(Y) around 91% and F1(C) around 88% (see results in Table 3, top) while failing to properly recognize the digit 7 (as shown by the confusion matrix in Fig. 10, Appendix C.7). More generally, high F1(Y) and sub-par F1(C) indicate a model affected by a RS (as suggested by Eq. 4.)\n\n**BDD-OIA performance:**\nIn BDD-OIA, the SotA accuracy performances are obtained with the CBM-AUC [3] model.  \nThis method is also below 80% F1 for labels and concepts: CBM-AUC obtains F1-mean (Y) of 70.8 $\\pm$ 0.1  % and F1-mean (C) of 62.1 $\\pm$ 0.1%. We will include these results in the Table of results.\n\n**Comparison with other NeSy predictors**\n \nGiven how broad and heterogeneous NeSy is, we had to focus on a selection of representative architectures:  DPL is a prototypical probabilistic logic approach based on a reasoning layer; SL represents penalty-based probabilistic logic models; LTN represents penalties based on fuzzy logics (see the “NeSy Predictors” paragraph on page 3).\n\nThank you for pointing out [1] and [2]. Notice that both architectures comply with the structure of NeSy predictors shown in Fig. 2, as they extract concepts C and process them to yield a prediction Y, and as such fall within the larger scope of our results.  The main differences are:\n\n* ROAP learns knowledge during training. From our perspective, this is not a substantial difference: even if the learned knowledge resembles the ground-truth knowledge, the model is still subject to the same RSs that the latter entails.  Worse, since the knowledge is not fixed, the model is less likely to acquire concepts with the right semantics.  On the bright side, since ROAP learns multiple tasks, it naturally leverages MTL mitigation.  We will mention this as an example usage of MTL in the knowledge mitigation section.\n\n* CEM learns both concepts and a (linear) prediction layer mapping concepts to labels.  Unlike NeSy architectures, CEMs cannot leverage prior knowledge and (like other concept-based models) require full concept supervision, cf. Section 2.\n\nWe fully agree that investigating RSs for neural architectures, concept-based models, and NeSy models with learned knowledge is a critical direction of research, and we plan to pursue it in future work.  We will mention this in the conclusion.\n\n[3] Sawada and Keigo \"Concept bottleneck model with additional unsupervised concepts.\" IEEE Access 10 (2022)\n"}, {"review_id": "rJ8znLQlfs", "reviewer": "Reviewer_Qpe9", "summary": "This paper proposes mitigation and evaluation strategies for \"reasoning shortcuts\" in neuro-symbolic reasoning models, roughly corresponding to when the concepts (i.e., latent variables) extracted do not match the \"true\" ground-truth factors. The paper then examines reasoning shortcuts on several proposed, simple datasets, including XOR, MNIST-Addition, MNIST-EvenOdd, MNIST-AddMul, and BDD-OIA. ", "questions": "What differences would you highlight between the reasoning-focused tasks in this paper and the more traditional tasks in the disentanglement literature? How are the approaches discussed in this paper particularly well-suited for those tasks? ", "limitations": "I think some more explicit discussion of the theoretical limitations demonstrated by related works (e.g., Locatello et al. 2019) would have been useful.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The topic is important and underexplored, while the approach taken in this paper is novel. In general, the presentation is also excellent. The experiments, while fairly simple, are appropriate given the topic. The work is highly related to and extends prior work on disentanglement in machine learning, which is referenced (though not especially explicitly discussed). It is also decently well-motivated and some of the tasks like the BDD dataset highlighted interesting failure cases.", "weaknesses": "Fundamentally, this paper is subject to many of the same challenges as prior work on disentanglement. That is, the task of identifying the \"correct\" latent variables is the task of disentanglement. While Locatello et al. (2019)'s \"Challenging common assumptions\" is cited for the definition of disentanglement (as [44]), the key lesson is never explicitly referenced (at least, not attributed): without supervision or inductive biases on the model and data, disentanglement is impossible. However, the authors highlight a similar point empirically, that \"Disentanglement is not enough under selection bias.\" Of course, this is not a particularly high bar, and indeed, the strategies taken to mitigate reasoning shortcuts in this paper do so with varying degrees of explicitness. For example, the paper's \"data-based mitigation\" explicitly provides supervision using a subset of the latent variables. However, in their objective-based approach, which draws inspiration from autoencoders, they could have plausibly also built on disentanglement-focused literature like InfoGAN (Chen et al. 2016) or $\\beta$-TCVAE (Chen et al. 2018). However, with that being said, it approaches many of these questions from a refreshing new perspective.\n\nThis leads to the second concern - to some extent, many of the proposed mitigation strategies are standard in the disentanglement literature. For example, \"On the relationship between disentanglement and multi-task learning\" (Maziarka et al. 2021) highlights the role of training on multiple tasks for learning disentangled representations -- in this paper, that is seemingly equivalent to knowledge-based mitigation. On the other hand, the data-based mitigation seemingly corresponds to the approach taken in \"Semi-Supervised StyleGAN for Disentanglement Learning\" (Nie et al. 2020). The objective-based mitigation (i.e., reconstruction loss) is, of course, central to many representation learning approaches. Then in the discussion of \"architecture-based mitigation,\" the connection to disentanglement work is made explicit. However, approaching these questions from the perspective of reasoning is fairly novel and is an important connection.\n\nUltimately, while the problem itself is well-motivated and novel, and the paper itself is excellent, and I believe it should likely be accepted based on the analysis alone, my primary reservation stems from the question of how reasoning, in particular, has shaped the mitigation strategies taken in this paper, beyond the datasets considered.\n\n---- Post-rebuttal update ----\nMost of my concerns have been addressed - I've raised my score to a 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments about our work, in particular for finding it excellent, novel, and well-presented. Below, we address the reviewer’s concerns.\n\n**Disentanglement vs. RSs**\n \nThank you for bringing up this interesting connection. There is a strong link between RSs and the problem of identifiability of discrete latent variables [1].  Identifiability is however different from (and stronger than) disentanglement.\n\nNotice also that, whereas most works on identifiability seek (im)possibility conditions, we go one step further and provide a count of the number of Reasoning Shortcuts, i.e., ways in which the model can fail to identify the right concepts.\nHence, we are not addressing conditions to achieve identifiability but, rather, we describe the causes for non-identifiability.\n\nAs for specific differences, notice that research on disentanglement focuses on continuous latent factors (e.g., in non-linear independent component analysis and disentangled representation learning via VAEs), does not consider symbolic knowledge, and typically allows factors to be permuted.  In contrast, in our work, we deal with discrete concepts learned from prior knowledge and do not allow permutations of factors.\n\nWe completely agree that techniques from causal representation learning provide useful tools for understanding neuro-symbolic integration, and we hope our work serves as a starting point for this research direction.\n\n**Strategies are not novel**\n\nOur paper aims to bring the issue of RSs - and their impact on trustworthiness - to the spotlight and to understand the root causes thereof.\n\nAs mentioned in the abstract, we study a set of **natural** mitigation strategies, which however only become obvious given our identified root causes.  We do not claim these are novel or technically advanced.  Rather, our contribution is making the impact they have on the number of reasoning shortcuts explicit (cf. Table 1).\n\nWe are aware that (weak) supervision has been used to encourage disentanglement.  The work of Maziarka et al. is however new to us;  we will reference it in the MTL section, thank you for the pointer.  However, these works seek disentanglement, while we are concerned with a stronger property, namely identifiability.\n\nNotice also that to estimate the effect of disentanglement it does not require to specify how it is achieved.  In fact, disentanglement on XOR and MNIST datasets can be enforced architecturally and tested empirically. In sections Q1 and Q2, we empirically investigate this point.  Regardless, the approaches indicated by the reviewer may affect different root causes and could in principle lead to a reduction of RSs.  We will include the suggested works in the discussion on how to achieve disentanglement in practice in Section 5.4.\n\n[1] Hyvärinen et al. \"Identifiability of latent-variable and structural-equation models: from linear to nonlinear.\" arXiv:2302.02672 (2023).\n"}, {"review_id": "Cm7psLjR6H", "reviewer": "Reviewer_p1H9", "summary": "This paper studies reasoning shortcuts (RS) in neuro-symbolic learning. RS refers to that the neural network does not learn a generalizable concept. This work provides a systematic characterization of RS, which not only gives a formal definition of RS, but also identifies key conditions of its occurrence. Several mitigation strategies are empirically or theoretically analyzed. ", "questions": "- The discussed neuro-symbolic learning is essentially in a weakly supervised learning setting (correct me if I'm wrong) [1]. Therefore, can the RS and its analysis be extended to general supervised learning problems?\n- From my understanding, using Shannon entropy loss is critical to avoid shortcuts. As mentioned in the last paragraph of section 5.4, entropy loss conflicts with NeSy prediction, but [1] proposes using an annealing strategy to gradually remove this entropy regularization. Furthermore, there are quite a few classic methods using maximal entropy-like regularization, e.g., mixup [2], label smoothing [3], focal loss [4], energy-based models [5], and Logit normalization [6]. I strongly recommend separating this part as an additional subsection to reveal this clue for alleviating RS.\n\n[1] Qing Li, Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, Song-Chun Zhu. Closed Loop Neural-Symbolic Learning via Integrating Neural Perception, Grammar Parsing, and Symbolic Reasoning.\n\n[1] Zenan Li, Yuan Yao, Taolue Chen, Jingwei Xu, Chun Cao, Xiaoxing Ma, Jian Lu. Softened Symbol Grounding for Neuro-symbolic Systems.\n\n[2] Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, Jean-Philippe Vert. On Mixup Regularization.\n\n[3] Rafael Müller, Simon Kornblith, Geoffrey Hinton. When Does Label Smoothing Help?\n\n[4] Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip Torr, Puneet Dokania. Calibrating Deep Neural Networks using Focal Loss. \n\n[5] Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Wang, Lise Getoor. NeuPSL: Neural Probabilistic Soft Logic.\n\n[6] Hongxin Wei, Renchunzi Xie, Hao Cheng, Lei Feng, Bo An, Yixuan Li. Mitigating Neural Network Overconfidence with Logit Normalization. ", "limitations": "No, the limitations of the method were not discussed. The work does not have negative social impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-motivated and well-written. I particularly appreciate the illustrative example in Figure 1. \n- The definition of RS is derived from causal representation learning, and it is quite reasonable.\n- Some promising theoretical results are presented, with proofs provided in the appendix.", "weaknesses": "- The paper focuses solely on probabilistic logic approaches like DPL, which limits its scope to a relatively narrow scope of neuro-symbolic learning. \n- This paper introduces too many concepts that may be unnecessary, such as NeSy predictors, unintended semantics, concept extractors, concept distributions, deterministic distributions, etc. Therefore, it may not be easily understood by readers who are unfamiliar with this subfield. \n- Some more experiments on other baseline methods are needed.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments about our work, in particular for finding it well-motivated and well-written. Below, we address the reviewer’s concerns.\n\n**Evaluated approaches are not exhaustive**  \n\nWe study reasoning shortcuts (RSs) in NeSy problems where knowledge is explicit and provided upfront.  This setting is very common in NeSy AI, as shown by the list of references we provided in the ``NeSy predictors’’ paragraph (other references were cut due to space constraints).  Within this setting, DPL, SL, and LTN are very representative.  DPL and SL are based on probabilistic logic: DPL introduces a specific layer on top of the concepts to perform logic combination, while SL uses a regularization loss to integrate logic. LTN is a representative of fuzzy logic, whereby it evaluates the satisfiability of the logical formula via fuzzy relaxation of the operators.\n\nWe completely agree that RSs in settings where the knowledge is learned are equally interesting, and we do plan to look into them in a follow-up work.\n\nWhile we do conjecture RSs to be a widespread phenomenon, as we noted in the Related Work section (page 8), NeSy approaches are far too heterogeneous to possibly experiment with them all in any given paper.  We plan on extending our evaluation in a longer version of the paper.\n\n**Notation heavy:** \nWe agree that the paper introduces several concepts, however, they are necessary to properly formalize our learning problem, even more so given this paper aims to lay the theoretical foundations of reasoning shortcuts.\n\n**Supervised vs weakly supervised** \n\nWe agree that our learning setup can be seen as a weakly-supervised setting according to the definition in [1]. That is (latent) concepts $C$ are learned with supervision on labels $Y$ and leveraging knowledge $K$.\nWe are not sure what the reviewer means by general supervised learning. Supervising also the concepts $C$ can be seen as a very effective mitigation strategy (concept supervision in the text) for which the count is reduced by the constraint in Prop. 5.\nOn the contrary, if the reviewer means regular neural classifiers in which the label $Y$ is predicted from the input $X$ without computing concepts $C$ explicitly, our results can be adapted when knowledge $K$ is used among labels. In fact, in this case, SL can be adapted to regularize the predictions $Y$ with the known logical constraints. If some of the labels are latent, reasoning shortcuts can appear, though, in a different form. We believe this constitutes an interesting extension of our present work.\n\n**Shannon Entropy**  \n\nThank you for the references.\nThese works focus on increasing the entropy of $p(Y | X)$.  This is insufficient to prevent reasoning shortcuts, which affect $p(C | X)$.  While it is possible to adapt these strategies - for instance, label smoothing - to $p(C | X)$, doing so might conflict with the objective of recovering the ground-truth concept distributions, that is, the ``correct semantics’’.  This is because, in general, there is no guarantee the ground-truth concepts themselves are high-entropy.  We will cite the provided works and discuss this point in our paper.  We will also convert the paragraph to a subsection as you suggested.\n\nPlease note that we did experiment with a strategy encouraging high entropy on $p(C)$, taken from [Manhaeve et al., 2021] and denoted +H in our tables.  As noted in the ``Other heuristics’’ paragraph on page 7, Shannon Entropy can be useful in practice to regularize the network’s prediction, but its learning objective can conflict with the original learning loss (e.g. maximum log-likelihood for DPL).  However, doing so means that it is no longer possible to explicitly count the number of deterministic RSs as in Eq. (6). Notice that imposing a Shannon entropy on the concepts $C$ is equivalent to minimizing the Jensen-Shannon divergence between the concept distribution $p(C)$ and the uniform distribution.  Since the data is often not distributed uniformly, optimizing the JS divergence conflicts with recovering the true concept distribution (especially if there are few concepts, like in our experiment Q2 bottom).  In practice, the +H strategy can help to prevent some RSs, but it is insufficient to avoid all of them, as shown in Table 3, top.\n"}]

Author rebuttal:
We are grateful to all reviewers for taking the time to evaluate our paper and appreciating the motivation (**p1H9**), the theoretical analysis (**Qpe9**), and the significance of our work (**yCW5**, **szNE**, **Qpe9**), as well as the quality of the presentation (**yCW5**, **szNE**, **Qpe9**, **p1H9**).  

We will address the points they raised in the detailed replies.  

We also attach to this comment a PDF containing additional empirical results for **Q1**.

Meta-review: This paper formally defines and studies reasoning shortcuts in Neuro-Symbolic predictive models and suggest different strategies to mitigate them. Reasoning shortcuts refer to solutions that achieve the best loss on the training set but don't match ground-truth concept distribution. This means models that use reasoning shortcuts will not be able to generalize to out-of-distribution cases where the same concepts are combined differently. Authors study this issue theoretically and empirically and suggest different mitigation strategies.

I think the paper could benefit from in-depth discussions that motivates this line of work for a larger audience and connects it to other areas. For example:

- Out-of-distribution generalization: This seems to be a particular case of out-of-distribution generalization. Would be nice to discuss connections.
- Disentanglement: It looks like disentanglement helps with removing reasoning shortcuts in some of the studies cases.
- Foundation Models: It seems that large vision language models trained on massive corpuses are more immune to these issues. One can think of vision language models + chain-of-thought as a symbolic reasoner. How does your work relate to this?

As for the final decision, all reviewers voted for acceptance and the paper seems to be valuable for understanding and improving Neuro-Symbolic models so I vote for acceptance.
Decision: Accept (poster)