# Interpretable Concept-Based Memory Reasoning

David Debot  Department of Computer Science, KU Leuven  Pietro Barbiero
Università della Svizzera Italiana  University of Cambridge  Francesco
Giannini  Faculty of Sciences, Scuola Normale Superiore, Pisa  Gabriele
Ciravegna  Department of Control and Computer Engineering, Politecnico di
Torino  Michelangelo Diligenti  Università di Siena  Giuseppe Marra
Department of Computer Science, KU Leuven

###### Abstract

The lack of transparency in the decision-making processes of deep learning
systems presents a significant challenge in modern artificial intelligence
(AI), as it impairs users’ ability to rely on and verify these systems. To
address this challenge, Concept Bottleneck Models (CBMs) have made significant
progress by incorporating human-interpretable concepts into deep learning
architectures. This approach allows predictions to be traced back to specific
concept patterns that users can understand and potentially intervene on.
However, existing CBMs’ task predictors are not fully interpretable,
preventing a thorough analysis and any form of formal verification of their
decision-making process prior to deployment, thereby raising significant
reliability concerns. To bridge this gap, we introduce Concept-based Memory
Reasoner (CMR), a novel CBM designed to provide a human-understandable and
provably-verifiable task prediction process. Our approach is to model each
task prediction as a neural selection mechanism over a memory of learnable
logic rules, followed by a symbolic evaluation of the selected rule. The
presence of an explicit memory and the symbolic evaluation allow domain
experts to inspect and formally verify the validity of certain global
properties of interest for the task prediction process. Experimental results
demonstrate that CMR achieves comparable accuracy-interpretability trade-offs
to state-of-the-art CBMs, discovers logic rules consistent with ground truths,
allows for rule interventions, and allows pre-deployment verification.

##  1 Introduction

The opaque decision process of deep learning (DL) systems represents one of
the most fundamental problems in modern artificial intelligence (AI). For this
reason, eXplainable AI (XAI) [1, 2, 3] is currently one of the most active
research areas in AI. Among XAI techniques, Concept Bottleneck Models (CBMs)
[4, 5, 6, 7, 8] represented a significant innovation that made DL models
explainable by design by introducing a layer of human-interpretable concepts
within DL architectures. In CBMs, first, a concept encoder maps low-level raw
features (e.g., an image’s pixels) to high-level interpretable concepts (e.g.,
“red” and “round”), then a task predictor uses the learned concepts to solve a
downstream task (e.g., “apple”). This way, each task prediction can be traced
back to a specific pattern of concepts, thus allowing CBMs to provide
explanations in terms of high-level interpretable concepts (e.g., concepts
“red” and “round” were both active when the model classified an image as
“apple”) rather than low-level raw features (e.g., there were 100 red pixels
when the model classified an image as “apple”). In other terms, a CBM’s task
predictor allows understanding what the model is seeing in a given input
rather than simply pointing to where it is looking [9].

However, state-of-the-art CBMs’ task predictors are either unable to solve
complex tasks (e.g., linear layers), non-differentiable (e.g., decision
trees), or black-box neural networks. The black-box nature of neural task
predictors prevents humans from understanding how the concepts are used to
predict the downstream task, as well as any chance of formally verifying the
task predictor decision-making process prior to deployment, thus raising
significant concerns in practical applications. As a result, a knowledge gap
persists in the existing literature: the definition of a CBM’s task predictor
whose behavior can be inspected, verified, and potentially intervened upon
_before_ the deployment of the system.

To address this gap, we propose Concept-based Memory Reasoner (CMR), a new CBM
where the behavior and explanations of the task predictor can be inspected and
verified before the model is deployed. Our key innovation is an attention
mechanism over a differentiable memory of learnable logic rules, which CMR
uses to map concepts to downstream classes. Once learned, this memory of logic
rules can be interpreted as a disjunctive theory, which can be used for
explaining and automatic verification. This verification can take place before
the model is deployed and, thus, for any possible input the model will face at
deployment time. The concept-based nature of CMR allows the automatic
verification of properties that are expressed in terms of high-level human-
understandable concepts (e.g., “the model should never predict class ‘apple’
when the concept ‘blue’ is active”) rather than raw features (e.g., “the model
should never predict class ‘apple’ when there are less than ten red pixels”).

Our experimental results show that CMR: (i) matches the accuracy and
interpretability performances of state-of-the-art CBMs, (ii) discovers logic
rules matching ground truths, (iii) enables rule interventions beyond concept
interventions, and (iv) allows verifying properties for their predictions and
explanations _before_ deployment.

##  2 Preliminary

##### Concept Bottleneck Models (CBMs)

[4, 10] are functions composed of (i) a concept encoder $g:X\to C$ mapping
each entity $x\in X\subseteq\mathbb{R}^{d}$ (e.g., an image) to a set of
$n_{C}$ concepts $c\in C$ (e.g., “red”, “round”), and (ii) a task predictor
$f:C\to Y$ mapping concepts to the class $y\in Y$ (e.g., “apple”) representing
a downstream task. For simplicity, in this paper, a single task class is
discussed, as multiple tasks can be encoded by instantiating multiple task
predictors. When sigmoid activations are used for concepts and task
predictions, we can consider $g$ and $f$ as parameterizing a Bernoulli
distribution of truth assignments to propositional boolean concepts and tasks.
For example, $g_{red}(x)=0.8$ means that there is an 80% probability for the
proposition “$x$ is red" to be true. During training, concept and class
predictions $(c,y)$ are aligned with ground-truth labels $(\hat{c},\hat{y})$.
This architecture and training allows CBMs to provide explanations for class
predictions indicating the presence or absence of concepts. Another main
advantage of these models is that, at test time, human experts may also
_intervene_ on mispredicted concept labels to improve CBMs’ task performance
and extract counterfactual explanations [4, 11]. However, the task prediction
$f$ is still often a black-box model to guarantee high performances, thus not
providing any insight into which concepts are used and how they are composed
to reach the final prediction.

##  3 Method

In this section, we introduce Concept-based Memory Reasoner (CMR), the first
deep learning model that is concept-based, globally interpretable and provably
verifiable. Like other CBMs, CMR consists of two main components: a concept
encoder and a task predictor. However, CMR’s task predictor differs
significantly from traditional CBMs. Instead of producing outputs through a
black-box process, CMR’s task predictor operates transparently by (1)
selecting a logic rule from a set of jointly-learned rules, and (2)
symbolically evaluating the chosen rule on the concept predictions. This
unique approach enables CMR not only to provide explanations by tracing class
predictions back to concept activations, but also to explain which concepts
are utilized and how they interact to make a task prediction. Moreover, the
set of learned rules remains accessible throughout the learning process,
allowing users to analyze the model’s behavior and automatically verify
whether some desired properties are being fulfilled at any time. The logical
interpretation of CMR’s task predictor, combined with its provably verifiable
behavior, distinguishes it sharply from existing CBMs’ task predictors.

###  3.1 CMR probabilistic graphical model

In Figure 1, we show the probabilistic graphical model of CMR. There are four
variables, three of which are standard in (discriminative) CBMs: the observed
input $x\in X$, the concepts encoding $c\in C$

$x$$c$$y$$r$ Figure 1: Probabilistic graphical model of CMR

and the task prediction $y\in\\{0,1\\}$. CMR adds an additional variable: the
rule $r\in\\{P,N,I\\}^{n_{C}}$. A rule is a conjunction in the concept set,
like $c_{1}\land\neg c_{3}$. A conjunction is uniquely identified when, for
each concept $c_{i}$, we know whether, in the rule, the concept is irrelevant
(I), positive (P) or negative (N). We call $r_{i}\in\\{P,N,I\\}$ the role of
the $i$-th concept in rule $r$. For example, given the three concepts
$c_{1},c_{2},c_{3}$, the conjunction $c_{1}\land\neg c_{3}$ can be represented
as $r_{1}=P,r_{2}=I,r_{3}=N$, since the role of $c_{1}$ is positive (P), the
role of $c_{2}$ is irrelevant (I) and the role of $c_{3}$ is negative (N).

This probabilistic graphical model encodes the joint conditional distribution
$p(y,r,c|x)$ and factorizes as:

$p(y,r,c|x)=p(y|c,r)p(r|x)p(c|x)$

Here, $p(c|x)$ is the concept encoder. For concept bottleneck encoders111In
case of encoders that provide additional embeddings other that concept logits,
they are modeled as Dirac delta, thus not modeling any uncertainty over them.,
it is simply the product of $n_{C}$ independent Bernoulli distributions
$p(c_{i}|x)$, whose logits are parameterized by any neural network encoder
$g_{i}:X\to\mathbb{R}$. Moreover, $p(r|x)$ is the rule selector, described in
Section 3.1.1. Given an input $x$, $p(r|x)$ models the uncertainty over which
conjunctive rule must be used. Lastly, $p(y|c,r)$ is the task predictor, which
will be described in Section 3.1.2. Given a rule $r\sim p(r|x)$ and an
assignment of truth values $c\sim p(c|x)$ to the concepts, the task predictor
evaluates the rule on the concepts. In all the cases described in this paper,
$p(y|c,r)$ is a deterministic degenerate distribution.

####  3.1.1 CMR rule selector

We model the rule selector $p(r|x)$ as a mixture of ${n_{R}}\in\mathbb{N}$
rule distributions. The selector "selects" a rule from a set of rule
distributions (i.e. the components of the mixture), which we call a rulebook.
The rulebook is jointly learned and can be inspected and verified at every
stage of the learning. Architecturally, this is akin to an attention mechanism
over a differentiable memory [12].

To this end, let $s\in[0,{n_{R}}]\subset\mathbb{N}$ be the indicator of the
selected component of the mixture, then:

$p(r|x)=\sum_{s}p(r|s)p(s|x)$

Here, $p(s|x)$ is the categorical distribution defining the mixing weights of
the mixture. It is parameterized by a neural network
$\phi^{\smash{(s)}}:X\to\mathbb{R}^{n_{R}}$, outputting one logit for each of
the ${n_{R}}$ components. Each $p(r|s)$ is modeled as a product of $n_{C}$
categorical distributions, i.e.
$p(r|s)=\smash{\prod_{i=1}^{n_{C}}}p(r_{i}|s)$. We assign to each component
$s=j$ a rule embedding $e_{j}\in\mathbb{R}^{q}$, and each categorical is then
parameterized by a neural network
$\phi^{\smash{(r)}}_{i}:\mathbb{R}^{q}\to\mathbb{R}^{3}$, mapping the
embedding to the logits of the categorical component. Intuitively, for each
concept $c_{i}$, the corresponding categorical distribution $p(r_{i}|s=j)$
decodes the embedding $e_{j}$ to the three possible roles
$r_{i}\in\\{P,N,I\\}$ of concept $c_{i}$ in rule $r$. Lastly, we define the
set $E$ of all the embeddings, i.e. $E=\\{e_{j}\\}_{j\in[0,n_{R}]}$, as the
encoded rulebook. The rulebook can be decoded at decision-time into a set of
symbolic rules by taking the argmax among the roles, i.e.
$r_{i}=\text{argmax}(\phi^{\smash{(r)}}_{i})$.

concept encoder$p(c\mid
x)$16383.9999816383.9999816383.99998RSTconcepts(A)$\sim$ Red=T, Square=F,
onTable=T logical eval$p(y\mid c,r)$$Apple=T$ (E)componentselector$p(s\mid
x)$$r$$r$16383.9999816383.99998(B)$r$$r$000000rule 1rule 2 _rulebook_
$\sim$$r$000rule 1(C)rule decoder$p(r\mid
s)$$r$$r$$r$16383.9999816383.9999816383.9999816383.9999816383.9999816383.9999816383.9999816383.9999816383.99998PNIRST
_decoded rule_(D)$\sim$ Red $\land$ $\neg$Square $\to$ Apple

Figure 2: Example prediction of CMR with a rulebook of two rules and three
concepts (i.e. $Red\,(R)$, $Square\,(S)$, $onTable\,(T)$). In this figure, we
sample ($\sim$) for clarity, but in practice, we compute every probability
exactly. Every black box is implemented by a neural network, while the purple
box is a pure symbolic logic evaluation. (A) The image is mapped to a concept
prediction. (B) The image is mapped by the component selector to a
distribution over rules. (C) This distribution is used to select a rule
embedding from the encoded rulebook. (D) The rule embedding is decoded into a
logic rule, by assigning to each of the concepts its role in the rule, i.e.
whether it is positive (P), negative (N), or irrelevant (I). Finally, (E) the
rule is evaluated on the concept prediction to provide the task prediction on
the task $Apple$.

####  3.1.2 CMR task predictor

The CMR task predictor $p(y|r,c)$ provides the final $y$ prediction given
concept predictions $c$ and the selected rule $r$. We model the task predictor
as a degenerate deterministic distribution, providing the entire probability
mass to the unique value $y$ which corresponds to the logical evaluation of
the rule $r$ on the concept predictions $c$. In particular, let
$r_{i}\in\\{P,N,I\\}$ be the role of the $i$-th concept in rule $r$. Then, the
symbolic task prediction $y$ obtained by evaluating rule $r$ on concept
predictions $c$ is:

$y\leftarrow\bigwedge_{i=1}^{n_{C}}(r_{i}=I)\lor(((r_{i}=P)\Rightarrow
c_{i})\land((r_{i}=N)\Rightarrow\neg c_{i})))$

Here, the $y$ prediction is equivalent to a conjunction of $n_{C}$ different
conjuncts, one for each concept. If a concept $i$ is irrelevant according to
the selected rule $r$ (i.e. $r_{i}=I$), the corresponding conjunct is ignored.
If $r_{i}=P$, then the conjunct is True if the corresponding concept is True.
Otherwise, i.e. if $r_{i}=N$, the conjunct is True if the corresponding
concept is False.

A graphical representation of the model is shown in Figure 2.

##  4 Expressivity, interpretability and verification

In this section, we will discuss the proposed model along three different
directions: expressivity, interpretability and verification.

###  4.1 Expressivity

An interesting property is that CMR is as expressive as a neural network
binary classifier.

######  Theorem 4.1.

CMR is a universal binary classifier [13] if $n_{R}\geq 3$.

###### Proof.

Recall that the rule selector is implemented by any neural network
$\phi^{(s)}:X\to\mathbb{R}^{n_{R}}$. Consider the following three rules,
easily expressible in CMR as showed on the right of each rule:

$\displaystyle y$ $\displaystyle\leftarrow True\enspace(\text{i.e.}\,\forall
i:r_{i}=I)$ $\displaystyle y$
$\displaystyle\leftarrow\bigwedge_{i=1}^{n_{C}}c_{i}\enspace(\text{i.e.}\,\forall
i:r_{i}=P)$ $\displaystyle y$
$\displaystyle\leftarrow\bigwedge_{i=1}^{n_{C}}\neg
c_{i}\enspace(\text{i.e.}\,\forall i:r_{i}=N)$

By selecting one of these three rules, the rule selector can always make a
desired $y$ prediction, regardless of the concepts $c$. In particular, to
predict $y=1$, the selector can select the first rule. To predict $y=0$ when
at least one concept is False in the concept predictions $c$ (i.e. $\exists
i:c_{i}=0$), it can select the second rule. Lastly, to predict $y=0$ when all
concepts are True in $c$ (i.e. $\forall i:c_{i}=1$), it can select the last
rule. ∎

###  4.2 Interpretability

CMR task prediction is the composition of a (neural) rule selector and the
symbolic evaluation of the selected rule. Therefore, we can always inspect the
whole rulebook to know exactly the global behavior of the task prediction. In
particular, let $s$ be the selected rule, $e_{j}$ the embedding of the $j$-th
rule, and $r^{\smash{(j)}}_{i}\in\\{P,N,I\\}$ the role of the $i$-th concept
in the $j$-th rule at decision time, i.e.
$r^{\smash{(j)}}_{i}=\text{argmax}(\phi^{\smash{(r)}}_{i}(e_{j}))$. Then,
CMR’s task predictor can be logically defined as the global rule obtained as
the disjunction of all decoded rules, each filtered by whether the rule has
been selected or not. That is:

$y\Leftrightarrow\bigvee_{j=1}^{n_{R}}(s=j)\land\left(\bigwedge_{i=1}^{n_{C}}(r^{(j)}_{i}=I)\lor(((r^{(j)}_{i}=P)\Rightarrow
c_{i})\land((r^{(j)}_{i}=N)\Rightarrow\neg c_{i}))\right)$ (1)

It is clear that if the model learns the three rules in the proof of Theorem
4.1, the selector simply becomes a proxy for $y$. It is safe to say that the
interpretability of the selector (and consequently of CMR) fully depends on
the interpretability of the learned rules.

Prototype-based rules. In order to develop interpretable rules, we focus on
standard theories in cognitive science [14] by looking at those rules that are
prototypical of the concept activations on which they are applied to.
Prototype-based models are often considered one of the main categories of
interpretable models [9] and have been investigated in the context of concept-
based models [15]. However, CMR distinguishes itself from prototype-based
models in two significant ways. First, in prototypical concept-based models,
prototypes are built directly in the input space, such as images [16] or on
part of it [17], and are often used to automatically build concepts. However,
this approach carries similar issues w.r.t. traditional input-based
explanations, like saliency maps (i.e. a prototype made by a strange pattern
of pixels can still remain unclear to the user). In contrast, in CMR,
prototypes (i.e. rules) are built on top of human-understandable concepts and
are therefore interpretable as well. Second, differently from prototype-based
models, CMR assigns a logical interpretation to prototypes as conjunctive
rules. Unlike prototype networks that assign class labels only based on
proximity to a prototype, CMR determines class labels through the symbolic
evaluation of prototype rules on concepts. Therefore, prototypes should be
representative of concept activations but also provide a correct task
prediction. This double nature of CMR prototypes, as both representative of
concept activations and conjunctive rules for task prediction, imposes an
additional constraint. In particular, only prototypes of positive task
instances (i.e. $y=1$) can behave as good classification rules. The
conjunctive nature of the rule makes that a positive evaluation is only
possible if all (relevant) conjuncts match with the corresponding concept
predictions. In contrast, a negative evaluation can simply be obtained if at
least one of the conjuncts does not match with the concept predictions.
Therefore, the rules selected for negative instances ($y=0$) will not be
required to be representative of the corresponding concept predictions.

Interventions. In contrast to existing CBMs, which only allow prediction-time
concept interventions, the global interpretability of CMR allows humans to
intervene also on the rules that will be exploited for task prediction. These
interactions may occur during the training phase to directly shape the model
that is being learned, and may come in various forms. A first approach
involves the manual inclusion of rules into the rule book, thereby integrating
expert knowledge into the model [18]. The selector mechanism within the model
learns to choose among the rules acquired through training and those manually
incorporated. As a result, the rules acquired through training can change
after adding expert rules. A second approach consists of modifying the learned
rules themselves, by altering the role $r_{i}$ of a concept within a rule. For
instance, setting the logit of $P_{i}$ to 0 ensures that $c_{i}$ cannot
exhibit a positive role in that rule, and setting the logits of both $P_{i}$
and $N_{i}$ to 0 ensures irrelevance. This type of intervention could be
exploited to remove (or prevent) biases and ensure counterfactual fairness
[19].

###  4.3 Verification

One of the main properties of CMR is that, at decision time, it explicitly
represents the task prediction as a set of conjunctive rules. Logically, the
mixture semantics of the selector can be interpreted as a disjunction, leading
to a standard semantics in stochastic logic programming [20, 21]. As the only
neural component is in the selection, task predictions generated using CMR’s
global formula (cf. Section 4.2) can be automatically verified by using
standard tools of formal verification (e.g. model checking), no matter which
rule will be selected. Being able to verify properties prior to deployment of
the model strongly sets CMR apart from existing models, where verification
tasks can only be applied at prediction time. In particular, given any
propositional logical formula $\alpha$ over the propositional language
$\\{c_{1},c_{2},...,c_{n_{C}}\\}\cup\\{r^{\smash{(j)}}_{i}\\}$, $\alpha$ can
be automatically verified to logically follow from Equation 1. In logical
terms, if the formula $\alpha$ is entailed by Equation 1, it means that
$\alpha$ must be true every time Equation 1 is used for prediction.

##  5 Learning problem

Learning in CMR follows the standard objective in CBM literature, where the
likelihood of the concepts and task observations in the data is maximized.
Formally, let $\Omega$ be the set of parameters of the probability
distributions, such that CMR’s probabilistic graphical model is globally
parameterized by $\Omega$, i.e. $p(y,r,c|x;\Omega)$. Let
$D=\\{(\hat{x},\hat{c},\hat{y})\\}$ be a concept-based dataset of i.i.d.
triples (input, concepts, task). Then, learning is the optimization problem:

$\max_{\Omega}\sum_{(\hat{x},\hat{c},\hat{y})\in D}\log
p(\hat{y},\hat{c}|\hat{x};\Omega)$ (2)

Due to the factorization of the mixture model in the rule selection, CMR has a
tractable likelihood computation. In particular, the following result holds.

######  Theorem 5.1 (Log-likelihood).

The maximum likelihood simplifies to the following $O(n_{C}\cdot n_{R})$
objective:

$\max_{\Omega}\sum_{(\hat{x},\hat{c},\hat{y})\in
D}\left(\sum_{i=1}^{n_{C}}\log
p(c_{i}=\hat{c}_{i}|\hat{x})\right)+\left(\log\sum_{\hat{s}=1}^{n_{R}}p(s=\hat{s}|\hat{x})\,p(y=\hat{y}|\hat{c},\hat{s})\right)$
(3)

with:

$p(y|c,s)=\prod_{i=1}^{n_{C}}\left(p(I_{i}|s)+p(P_{i}|s)\,\mathbbm{1}[c_{i}=1]+p(N_{i}|s)\,\mathbbm{1}[c_{i}=0]\right)$

where $\mathbbm{1}[\cdot]$ is an indicator function of the condition within
brackets.

###### Proof.

See Appendix A ∎

The maximum likelihood approach only focuses on the prediction accuracy of the
model. However, as discussed in Section 4.2, we look for the set of learned
rules $r$ to represent good prototypes of concept predictions, as in
prototype-based learning [15]. To drive the learning of representative
positive prototypes when we observe a positive value for the task, i.e. when
$y=1$, we add a regularization term to the objective. Intuitively, every time
a rule is selected for a given input instance $x$ with task label $y=1$, we
want the rule to be as close as possible to the observed concept prediction.
At the same time, since the number of rules is limited and the possible
concept activations are combinatorial, the same rule is expected to be
selected for different concept activations. When this happens, we will favor
rules that assign an irrelevant role to the inconsistent concepts in the
activations. The regularized objective is:

$\max_{\Omega}\sum_{(\hat{x},\hat{c},\hat{y})\in
D}\left(\sum_{i=1}^{n_{C}}\log
p(c_{i}=\hat{c}_{i}|\hat{x})\right)+\left(\log\sum_{\hat{s}=1}^{n_{R}}p(s=\hat{s}|\hat{x})\,p(y=\hat{y}|\hat{c},\hat{s})\underbrace{p_{reg}(r=\hat{c}|\hat{s})^{\hat{y}}}_{\text{Regularization
Term}}\right)$ (4)

and:

$p_{reg}(r=\hat{c}|s)=\prod_{i=1}^{n_{C}}(0.5\,p(r_{i}=I|s)+p(r_{i}=P|s)\,\mathbbm{1}[\hat{c}_{i}=1]+p(r_{i}=N|s)\,\mathbbm{1}[\hat{c}_{i}=0])$

This term favors the selected rule $r$ to reconstruct the observed $\hat{c}$
as much as possible. When such reconstruction is not feasible due to the
limited capacity of the rulebook, the term will favor irrelevant roles for
concepts. In this way, we will develop rules that have relevant terms (i.e.
$r_{i}\in\\{P,N\\}$) only if they are representative of all the instances in
which the rule is selected. Appendix B contains an investigation of the
influence of this regularization on the optima of the loss.

##  6 Experiments

Our experiments aim to answer the following research questions:

  * (1)

Generalization: Does CMR attain similar task and concept accuracy as existing
CBMs and black boxes? Does CMR generalize well when the concept set is
incomplete222Incomplete concept sets do not contain all the information
present in the input that is useful for task prediction. In other words,
models with a concept bottleneck cannot achieve black-box accuracy with them.?

  * (2)

Explainability and Intervenability: Can CMR recover ground truth rules? Can
CMR learn meaningful rules when the concept set is incomplete? Are concept
interventions and rule interventions effective in CMR?

  * (3)

Verifiability: Can CMR allow for post-training verification regarding its
behavior?

###  6.1 Experimental setting

This section describes essential information about experiments. We provide
further details in Appendix C.

Data & task setup. We base our experiments on four different datasets commonly
used to evaluate CBMs: MNIST+ [22], where the task is to predict the sum of
two digits; C-MNIST, where we adapted MNIST to the task of predicting whether
a colored digit is even or odd; MNIST+∗, where we removed the concepts for the
digits 0 and 1 from the concept set; CelebA [23], a large-scale face
attributes dataset with more than 200K celebrity images, each with 40 concept
annotations333We remove the concepts $Wavy\\_Hair$, $Black\\_Hair$ and $Male$
from the concept set and instead use them as tasks.; CUB [24], where the task
is to predict bird species based on bird characteristics; and CEBAB [25], a
text-based task where reviews are classified as positive or negative based on
different criteria (e.g. food, ambience, service, etc). These datasets range
across different concept set quality, i.e. complete (MNIST+, C-MNIST, CUB) vs
incomplete (CelebA, MNIST+∗), and different complexities of the concept
prediction task, i.e. easy (MNIST+, MNIST+∗, C-MNIST), medium (CEBAB) and hard
(CelebA, CUB).

Evaluation. To measure classification performance on tasks and concepts, we
compute subset accuracy and regular accuracy, respectively. For CUB, we
instead compute the Area Under the Receiver Operating Characteristic Curve
[26] for the tasks due to the large class imbalance. All metrics are reported
using the mean and the standard error of the mean over three different runs
with different initializations.

Baselines. In our experiments, we compare CMR with existing CBM architectures.
We consider Concept Bottleneck Models with different task predictors: linear,
multi-layer (MLP), decision-tree (DT) and XGBoost (XG). Moreover, we add two
state-of-the-art CBMs: Concept Embedding Models (CEM) [27] and Deep Concept
Reasoner (DCR) [11]. We employ hard concepts in CMR and our competitors,
avoiding the problem of input distribution leakage that can affect task
accuracy [28, 29] (see Appendix C for additional details).

Finally, we include a deep neural network without a concept bottleneck to
measure the effect of an interpretable architecture on generalization
performance.

###  6.2 Key findings & results

####  6.2.1 Generalization

CMR’s high degree of interpretability does not harm accuracy, which is similar
to or better than competitors’. In Table 1, we compare CMR with its
competitors regarding task accuracy. On all data sets, CMR achieves an
accuracy close to black-box accuracy, either beating its concept-based
competitors or obtaining similar results. In Table 5 of Appendix C, we show
that CMR’s training does not harm concept accuracy, which is similar to its
competitors.

Table 1: Task accuracy on all datasets. The best and second best for CBMs are shown in bold (black and purple, respectively). | mnist+ | mnist+∗ | c-mnist | celeba | cub | cebab
---|---|---|---|---|---|---
CBM+linear | $0.00{\scriptstyle\pm 0.00}$ | $0.00{\scriptstyle\pm 0.00}$ | $99.07{\scriptstyle\pm 0.31}$ | $49.07{\scriptstyle\pm 0.27}$ | $50.60{\scriptstyle\pm 0.69}$ | $45.15{\scriptstyle\pm 29.93}$
CBM+MLP | $\mathbf{97.41{\scriptstyle\pm 0.55}}$ | $72.51{\scriptstyle\pm 2.42}$ | ${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\mathbf{99.42{\scriptstyle\pm 0.11}}}$ | $49.92{\scriptstyle\pm 0.73}$ | $55.83{\scriptstyle\pm 0.33}$ | ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>0.30}}$
CBM+DT | $96.73{\scriptstyle\pm 0.39}$ | $77.63{\scriptstyle\pm 0.44}$ | $\mathbf{99.44{\scriptstyle\pm 0.03}}$ | $49.58{\scriptstyle\pm 0.29}$ | $51.83{\scriptstyle\pm 0.48}$ | $83.15{\scriptstyle\pm 0.15}$
CBM+XG | $96.73{\scriptstyle\pm 0.39}$ | $76.54{\scriptstyle\pm 0.54}$ | $\mathbf{99.44{\scriptstyle\pm 0.03}}$ | $50.24{\scriptstyle\pm 0.34}$ | ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>0.96}}}$ | $\mathbf{83.80{\scriptstyle\pm 0.01}}$
CEM | $92.44{\scriptstyle\pm 0.26}$ | $\mathbf{92.94{\scriptstyle\pm 1.15}}$ | $99.32{\scriptstyle\pm 0.11}$ | ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>0.66}}}$ | $57.03{\scriptstyle\pm 0.80}$ | $83.30{\scriptstyle\pm 1.59}$
DCR | $90.70{\scriptstyle\pm 1.21}$ | $92.24{\scriptstyle\pm 1.37}$ | $98.99{\scriptstyle\pm 0.08}$ | $39.32{\scriptstyle\pm 1.36}$ | $50.00{\scriptstyle\pm 0.00}$ | $67.30{\scriptstyle\pm 0.93}$
Black box | $83.26{\scriptstyle\pm 8.71}$ | $83.26{\scriptstyle\pm 8.71}$ | $99.19{\scriptstyle\pm 0.11}$ | $65.72{\scriptstyle\pm 0.70}$ | $64.07{\scriptstyle\pm 0.33}$ | $88.67{\scriptstyle\pm 0.19}$
CMR (ours) | $\mathbf{97.52{\scriptstyle\pm 0.30}}$ | $\mathbf{95.47{\scriptstyle\pm 0.47}}$ | $99.12{\scriptstyle\pm 0.04}$ | ${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\mathbf{63.56{\scriptstyle\pm 0.48}}}$ | ${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\mathbf{60.07{\scriptstyle\pm 1.70}}}$ | $\mathbf{85.14{\scriptstyle\pm 0.43}}$

CMR obtains accuracy competitive with black boxes even on incomplete concept
sets. We evaluate the performance of CMR on settings with increasingly more
incomplete concept sets. Firstly, as shown in Table 1, in MNIST+∗, CMR still
obtains task accuracy close to the complete setting, beating its competitors
which suffer from a concept bottleneck. Secondly, we run an experiment on
CelebA where we gradually decrease the number of concepts in the concept set.
Figure 3 shows the achieved task accuracies for CMR and the competitors. CMR’s
accuracy remains high no matter the size of the concept set, while the
performance of the competitors with a bottleneck (i.e. all except CEM)
strongly degrades.

####  6.2.2 Explanations and intervention

CMR discovers ground truth rules. We quantitatively evaluate the correctness
of the rules CMR learns on MNIST+ and C-MNIST. In the former, the ground truth
rules have no irrelevant concepts; in the latter, they do. In all runs of
these experiments, CMR finds all correct ground truth rules. In C-MNIST, CMR
correctly learns that the concepts related to color are irrelevant for
classifying the digit as even or odd (see Table 6.2.2).

CMR discovers meaningful rules in the absence of ground truth. While the other
datasets do not provide ground truth rules, a qualitative inspection shows
that they are still meaningful. Table 6.2.2 shows two examples for CEBAB, and
additional rules can be found in Appendix C.

Table 2: Selection of learned rules. For brevity in C-MNIST, negated concepts
are not shown and irrelevant concepts are shown between parentheses. We
abbreviate good to g, bad to b and unknown to u.

C-MNIST |  $y_{even}\leftarrow 0\land({red})\land({green})$
---|---
$y_{even}\leftarrow 2\land({red})\land({green})$
$y_{odd}\leftarrow 3\land({red})\land({green})$
CEBAB |  $y_{neg}\leftarrow\neg food_{g}\land\neg amb_{g}\land\neg noise_{g}$
$y_{pos}\leftarrow\neg food_{b}\land\neg amb_{b}\land noise_{u}\land\neg
noise_{b}\land\neg noise_{g}$

Figure 3: Task accuracy on CelebA with varying numbers of concepts.

Rule interventions during training allow human experts to improve the learned
rules. We show this by choosing a rulebook size for MNIST+ that is too small
to learn all ground truth rules. Consequently, CMR learns rules that differ
from the ground truth rules. After manually adding rules to the pool in the
middle of training, CMR (1) learns to select these new rules for training
examples for which they make a correct task prediction, and (2) improves its
previously learned rules by eventually converging to the ground truth rules.
This is the case for all runs. Table 3 gives some examples of how manually
adding rules affects the learned rules. Additionally, as concept interventions
are considered a core advantage of CBMs, we show in Appendix C that CMR is
equally responsive as competitors, consistently improving its accuracy after
concept interventions.

Table 3: Selection of rule interventions and their effect on learned rules. For brevity, negated concepts are not shown and irrelevant concepts are shown between parentheses. Learned rule before intervention | Added rule | Learned rule after intervention
---|---|---
$y_{8}\leftarrow(c_{0,3})\land(c_{1,5})\land(c_{0,4})\land(c_{1,4})$ | $y_{8}\leftarrow c_{0,3}\land c_{1,5}$ | $y_{8}\leftarrow c_{0,4}\land c_{1,4}$
$y_{9}\leftarrow(c_{0,8})\land(c_{1,1})\land(c_{0,1})\land(c_{1,8})$ | $y_{9}\leftarrow c_{0,8}\land c_{1,1}$ | $y_{9}\leftarrow c_{0,1}\land c_{1,8}$
$y_{9}\leftarrow(c_{0,0})\land(c_{1,9})\land(c_{0,2})\land(c_{1,7})$ | $y_{9}\leftarrow c_{0,0}\land c_{1,9}$ | $y_{9}\leftarrow c_{0,2}\land c_{1,7}$

###  6.3 Verification

CMR allows verification of desired global properties. In this task, we
automatically verify semantic consistency properties for MNIST+ and CelebA
whether CMR’s task prediction satisfies some properties of interest. For
verification, we exploited a naive model checker that verifies whether the
property holds for all concept assignments where the theory holds. When this
is not feasible, state-of-the-art model formal verification tools can be
exploited, as both the task prediction and the property are simply two
propositional formulas. For MNIST+, we can verify that, for each task $y$, CMR
never uses more than one positive concept (i.e. digit) per image, i.e.
$\forall y,i,j:c_{i}\rightarrow\neg c_{j}:i\neq j$). This is also easily
verifiable by simply inspecting the rules in Appendix C. Moreover, in CelebA,
we can easily verify that $Bald\Rightarrow\neg Wavy\\_Hair$ with the learned
rulebook for $n_{C}=12$ (see Table 10 in Appendix C), as $\neg Bald$ is a
conjunct in each rule that does not trivially evaluate to False.

##  7 Related works

In recent years, XAI techniques have been criticized for their vulnerability
to data modifications [30, 31], insensitivity to reparameterizations, [32],
and lacking meaningful interpretations for non-expert users [33]. To address
these issues, Concept-based methods [34, 35, 5, 10] have emerged, offering
explanations in terms of human-interpretable features, a.k.a. concepts.
Concept Bottleneck Models [4] take a step further by directly integrating
these concepts as explicit intermediate network representations. Concept
Embeddings Models (CEMs) [7, 8, 11] close the accuracy gap with black-box
models through vectorial concept representations. However, they still harm the
final interpretability, as it is unclear what information is contained in the
embeddings. In contrast, CMR closes the accuracy gap by exploiting a neural
rule selector coupled with learned symbolic logic rules. As a result, CMR’s
task prediction is fully transparent, allowing experts to see how concepts are
being used for task prediction, and allowing intervention and automatic
verification of desired properties. To the best of our knowledge, there is
only one other attempt at analyzing CBMs’ task prediction in terms of logical
formulae, namely DCR [11]. For a given example, DCR predicts and subsequently
evaluates a (fuzzy) logic rule. As rules are predicted on a per-example basis,
the global behavior of DCR cannot be inspected, rendering interaction (e.g.
manually adding expert rules) and verification impossible. In contrast, CMR
learns (probabilistic) logic rules in a memory, allowing for inspection,
interaction and verification.

The use of logic rules by CMR for interpretability purposes aligns it closely
with the field of neurosymbolic AI [36, 37]. Here, logic rules [38, 39, 18] or
logic programs [40, 22, 21] are used in combination with neural networks
through the use of neural predicates [22]. Concepts in CMR are akin to a
propositional version of neural predicates. However, in CMR, the set of rules
is learned instead of given by the human and concept direct supervision is
used for human alignment.

Finally, the relationships with prototype-based models in interpretable AI
have been already discussed in Section 4.2.

##  8 Conclusions

We propose CMR, a novel Concept Bottleneck Model that offers a human-
understandable and provably-verifiable task prediction process. CMR integrates
a neural selection mechanism over a memory of learnable logic rules, followed
by a symbolic evaluation of the selected rules. Our approach enables global
interpretability and verification of task prediction properties. Our results
show that (1) CMR achieves near-black-box accuracy, (2) discovers meaningful
rules, and (3) facilitates strong interaction with human experts through rule
interventions. The development of CMR can have significant societal impact by
enhancing the transparency, verifiability, and human-AI interaction, thereby
fostering trust and reliability in critical decision-making processes.

Limitations and future works. CMRs are still foundational models and several
limitations need to be explored further in future works. In particular, CMRs
are focusing on positive-only explanations, while negative-reasoning
explanations have not been explored yet. Moreover, the same selection
mechanism can be tested in non-logic, interpretable settings (like linear
models). Finally, the verification capabilities of CMR will be tested on more
realistic, safety critical domains, where the model can be verified against
safety specifications.

## Acknowledgments

DD has received funding from the KU Leuven Research Fund (STG/22/021). FG was
supported by TAILOR project funded by EU Horizon 2020 under GA No 952215, the
Partnership Extended PE00000013 - “FAIR - Future Artificial Intelligence
Research” - Spoke 1 “Human-centered AI”. PB acknowledges support from the SNSF
under grant agreement No 205121L-214991 and No 205121-197242.

## References

  * Guidotti et al. [2018] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi.  A survey of methods for explaining black box models.  _ACM computing surveys (CSUR)_ , 51(5):1–42, 2018\.
  * Adadi and Berrada [2018] Amina Adadi and Mohammed Berrada.  Peeking inside the black-box: a survey on explainable artificial intelligence (xai).  _IEEE access_ , 6:52138–52160, 2018.
  * Arrieta et al. [2020] Alejandro Barredo Arrieta, Natalia Díaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, et al.  Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai.  _Information fusion_ , 58:82–115, 2020.
  * Koh et al. [2020] 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.
  * Alvarez Melis and Jaakkola [2018] David Alvarez Melis and Tommi Jaakkola.  Towards robust interpretability with self-explaining neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Chen et al. [2020] Zhi Chen, Yijie Bei, and Cynthia Rudin.  Concept whitening for interpretable image recognition.  _Nature Machine Intelligence_ , 2(12):772–782, 2020.
  * Zarlenga et al. [2023] Mateo Espinosa Zarlenga, Pietro Barbiero, Zohreh Shams, Dmitry Kazhdan, Umang Bhatt, Adrian Weller, and Mateja Jamnik.  Towards robust metrics for concept representation evaluation.  _arXiv preprint arXiv:2301.10367_ , 2023.
  * Kim et al. [2023] Eunji Kim, Dahuin Jung, Sangha Park, Siwon Kim, and Sungroh Yoon.  Probabilistic concept bottleneck models.  _arXiv preprint arXiv:2306.01574_ , 2023.
  * Rudin [2019] Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  _Nature machine intelligence_ , 1(5):206–215, 2019.
  * Poeta et al. [2023] Eleonora Poeta, Gabriele Ciravegna, Eliana Pastor, Tania Cerquitelli, and Elena Baralis.  Concept-based explainable artificial intelligence: A survey.  _arXiv preprint arXiv:2312.12936_ , 2023.
  * Barbiero et al. [2023] Pietro Barbiero, Gabriele Ciravegna, Francesco Giannini, Mateo Espinosa Zarlenga, Lucie Charlotte Magister, Alberto Tonda, Pietro Lio’, Frederic Precioso, Mateja Jamnik, and Giuseppe Marra.  Interpretable neural-symbolic concept reasoning.  In _ICML_ , 2023.
  * Weston et al. [2014] Jason Weston, Sumit Chopra, and Antoine Bordes.  Memory networks.  _arXiv preprint arXiv:1410.3916_ , 2014.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Rosch [1978] Eleanor Rosch.  Principles of categorization.  In _Cognition and categorization_ , pages 27–48. Routledge, 1978\.
  * Rudin et al. [2022] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong.  Interpretable machine learning: Fundamental principles and 10 grand challenges.  _Statistic Surveys_ , 16:1–85, 2022.
  * Li et al. [2018] Oscar Li, Hao Liu, Chaofan Chen, and Cynthia Rudin.  Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Chen et al. [2019] Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su.  This looks like that: deep learning for interpretable image recognition.  _Advances in neural information processing systems_ , 32, 2019.
  * Diligenti et al. [2017] Michelangelo Diligenti, Marco Gori, and Claudio Sacca.  Semantic-based regularization for learning and inference.  _Artificial Intelligence_ , 244:143–165, 2017.
  * Kusner et al. [2017] Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva.  Counterfactual fairness.  _Advances in neural information processing systems_ , 30, 2017.
  * Cussens [2001] James Cussens.  Parameter estimation in stochastic logic programs.  _Machine Learning_ , 44:245–271, 2001.
  * Winters et al. [2022] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt.  Deepstochlog: Neural stochastic logic programming.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(9):10090–10100, Jun. 2022.  doi: 10.1609/aaai.v36i9.21248.  URL https://ojs.aaai.org/index.php/AAAI/article/view/21248.
  * Manhaeve et al. [2018] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  DeepProbLog: Neural Probabilistic Logic Programming.  In _NeurIPS_ , pages 3753–3763, 2018.
  * Liu et al. [2015] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In _ICCV_ , 2015.
  * Welinder et al. [2010] Peter Welinder, Steve Branson, Takeshi Mita, Catherine Wah, Florian Schroff, Serge Belongie, and Pietro Perona.  Caltech-ucsd birds 200.  Technical Report CNS-TR-201, Caltech, 2010.  URL /se3/wp-content/uploads/2014/09/WelinderEtal10_CUB-200.pdf,http://www.vision.caltech.edu/visipedia/CUB-200.html.
  * Abraham et al. [2022] Eldar D Abraham, Karel D’Oosterlinck, Amir Feder, Yair Gat, Atticus Geiger, Christopher Potts, Roi Reichart, and Zhengxuan Wu.  Cebab: Estimating the causal effects of real-world concepts on nlp model behavior.  _Advances in Neural Information Processing Systems_ , 35:17582–17596, 2022.
  * Hand and Till [2001] David J. Hand and Robert J. Till.  A simple generalisation of the area under the roc curve for multiple class classification problems.  _Mach. Learn._ , 45(2):171–186, oct 2001.  ISSN 0885-6125.  doi: 10.1023/A:1010920819831.  URL https://doi.org/10.1023/A:1010920819831.
  * Espinosa Zarlenga et al. [2022] Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian Weller, Pietro Lio, and Mateja Jamnik.  Concept embedding models: Beyond the accuracy-explainability trade-off.  _Advances in Neural Information Processing Systems_ , 35, 2022.
  * Marconato et al. [2022] Emanuele Marconato, Andrea Passerini, and Stefano Teso.  Glancenets: Interpretable, leak-proof concept-based models.  _Advances in Neural Information Processing Systems_ , 35:21212–21227, 2022.
  * Havasi et al. [2022] Marton Havasi, Sonali Parbhoo, and Finale Doshi-Velez.  Addressing leakage in concept bottleneck models.  _Advances in Neural Information Processing Systems_ , 35:23386–23397, 2022.
  * Kindermans et al. [2019] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim.  The (un) reliability of saliency methods.  _Explainable AI: Interpreting, explaining and visualizing deep learning_ , pages 267–280, 2019.
  * Ghorbani et al. [2019a] Amirata Ghorbani, Abubakar Abid, and James Zou.  Interpretation of neural networks is fragile.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 3681–3688, 2019a.
  * Adebayo et al. [2018] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim.  Sanity checks for saliency maps.  _Advances in neural information processing systems_ , 31, 2018.
  * Poursabzi-Sangdeh et al. [2021] Forough Poursabzi-Sangdeh, Daniel G Goldstein, Jake M Hofman, Jennifer Wortman Wortman Vaughan, and Hanna Wallach.  Manipulating and measuring model interpretability.  In _Proceedings of the 2021 CHI conference on human factors in computing systems_ , pages 1–52, 2021.
  * Kim et al. [2018] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al.  Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav).  In _International conference on machine learning_ , pages 2668–2677. PMLR, 2018.
  * Ghorbani et al. [2019b] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim.  Towards automatic concept-based explanations.  _Advances in neural information processing systems_ , 32, 2019b.
  * Garcez et al. [2022] Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illuminoo, Hoifung Poon, and COPPE Gerson Zaverucha.  Neural-symbolic learning and reasoning: A survey and interpretation.  _Neuro-Symbolic Artificial Intelligence: The State of the Art_ , 342(1):327, 2022.
  * Marra et al. [2024] Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve, and Luc De Raedt.  From statistical relational to neurosymbolic artificial intelligence: A survey.  _Artificial Intelligence_ , page 104062, 2024.
  * Xu et al. [2018] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck.  A semantic loss function for deep learning with symbolic knowledge.  In _International conference on machine learning_ , pages 5502–5511. PMLR, 2018.
  * Badreddine et al. [2022] Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger.  Logic tensor networks.  _Artificial Intelligence_ , 303:103649, 2022.
  * Sourek et al. [2018] Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezny, Steven Schockaert, and Ondrej Kuzelka.  Lifted relational neural networks: Efficient learning of latent relational structures.  _Journal of Artificial Intelligence Research_ , 62:69–100, 2018.
  * Lecun et al. [1998] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.  doi: 10.1109/5.726791.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Wolf et al. [2020] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online, October 2020. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library, 2019\.
  * Pedregosa et al. [2018] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Andreas Müller, Joel Nothman, Gilles Louppe, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay.  Scikit-learn: Machine learning in python, 2018.
  * Hunter [2007] J. D. Hunter.  Matplotlib: A 2d graphics environment.  _Computing in Science & Engineering_, 9(3):90–95, 2007.  doi: 10.1109/MCSE.2007.55.

##  Appendix A Maximum likelihood derivation

We show that the maximum likelihood problem in Equation 2 simplifies to:

$\log p(\hat{y},\hat{c}|\hat{x})=\left(\sum_{i=1}^{n_{C}}\log
p(c_{i}=\hat{c}_{i}|\hat{x})\right)+\left(\log\sum_{\hat{s}=1}^{n_{R}}p(s=\hat{s}|\hat{x})\,p(y=\hat{y}|\hat{c},\hat{s})\right)$

with:

$p(y|c,s)=\prod_{i=1}^{n_{C}}\left(p(I_{i}|s)+p(P_{i}|s)\,\mathbbm{1}[c_{i}=1]+p(N_{i}|s)\,\mathbbm{1}[c_{i}=0]\right)$

###### Proof.

Let $n:=n_{C}$. First, we express the likelihood as the marginalization of the
distribution over the unobserved variables

$p(y,c|x)=p(c|x)\sum_{s}p(s|x)\sum_{r_{1}}...\sum_{r_{n}}p(r_{1},...,r_{n}|s)p(y|r_{1},...,r_{n},c_{1},...,c_{n})$

Due to the independence of the individual components of the rule distribution:

$p(r_{1},...,r_{n}|s)=\prod_{i=1}^{n}p(r_{i}|s)$

The logical evaluation of a rule can be expressed in terms of indicator
functions over the different variables involved.

$p(y|r_{1},...,r_{n},c_{1},...,c_{n})=\prod_{i=1}^{n}\mathbbm{1}{[r_{i}=I]}+\mathbbm{1}{[r_{i}=P]}\mathbbm{1}{[c_{i}=1]}+\mathbbm{1}{[r_{i}=n]}\mathbbm{1}{[c_{i}=0]}$

Let us define
$f(r_{i},c_{i}):=\mathbbm{1}{[r_{i}=I]}+\mathbbm{1}{[r_{i}=P]}\mathbbm{1}{[c_{i}=1]}+\mathbbm{1}{[r_{i}=n]}\mathbbm{1}{[c_{i}=0]}$.

Then, the likelihood becomes:

$\displaystyle p(y,c|x)$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\sum_{r_{1}}...\sum_{r_{n}}\prod_{i=1}^{n}p(r_{i}|s)\,f(r_{i},c_{i})$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\left(\sum_{r_{1}}p(r_{1}|s)\,f(r_{1},c_{1})\right)\left(...\right)\left(\sum_{r_{n}}p(r_{n}|s)\,f(r_{n},c_{n})\right)$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\prod_{i=1}^{n}\sum_{r_{i}}p(r_{i}|s)\,f(r_{i},c_{i})$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\prod_{i=1}^{n}(p(I_{i}|s)\,f(I_{i},c_{i})+p(P_{i}|s)\,f(P_{i},c_{i})+p(N_{i}|s)\,f(N_{i},c_{i}))$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\prod_{i=1}^{n}(p(I_{i}|s)+p(P_{i}|s)\,\mathbbm{1}{[c_{i}=1]}+p(N_{i}|s)\,\mathbbm{1}{[c_{i}=0]})$
$\displaystyle=p(c|x)\sum_{s}p(s|x)\,p(y|c,s)$

Using $p(c|x)=\prod_{i=1}^{n_{C}}p(c_{i}|x)$, and applying the logarithm, we
find:

$\log p(y,c|x)=\left(\sum_{i=1}^{n_{C}}\log
p(c_{i}|x)\right)+\left(\log\sum_{s=1}^{n_{R}}p(s|x)\,p(y|c,s)\right)$

∎

##  Appendix B Implementation and optimization details

##### Selector re-initialization

To promote exploration, we re-initialize the parameters of $p(s|x)$ multiple
times during training, making it easier to escape local optima. The re-
initialization frequency is a hyperparameter that differs between experiments,
see Appendix C.

##### Effect of the regularization term

Figure 4 shows the probabilities to be maximized when the label $y=1$, for a
selected rule and a single concept, with respect to different roles $r$ for
that concept. Figures 4(a), 4(b) and 4(c) show the probabilities to be
maximized without the regularization. Figures 4(d), 4(e) and 4(f) show the
regularization probabilities (remember, we only have these if $y=1$). Figures
4(g), 4(h) and 4(i) show the probabilities when both are present. As mentioned
in the main text, when $c$ is True for all examples that select the rule, we
want that concept’s role to be $P$. However, when optimizing without
regularization, it is clear that e.g. $I$ is also an optimum (Figure 4(a)).
Because the regularization only has an optimum in $P$ (Figure 4(d)), adding
the regularization results in the correct optimum (Figure 4(g)). A similar
reasoning applies when $c$ is False for all examples that select the rule;
consider Figures 4(b), 4(e) and 4(h). It should be noted that the
regularization alone is insufficient to get the correct optima; indeed, when
examples with different $c$ select the rule, the regularization term has many
optima (Figure 4(f)), of which only $I$ is desired (as explained in the main
text). As the original loss only has an optimum in $I$ in this case (Figure
4(c)), the only optimum that remains is the correct one (Figure 4(i)). In
summary: the loss function we use has the desired optima (last row in Figure
4), dropping the regularization (first row in Figure 4) or only keeping the
regularization (middle row in Figure 4) both have cases where the optima are
undesired.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figure 4: Likelihoods to be maximized when $y=1$ w.r.t. the role $r$ of a
single concept in a selected rule, for different situations. As $P+N+I=1$,
irrelevance is the coordinate $(0,0)$. Likelihoods that cannot be achieved
(i.e. when $P+N>1$) are put to 0. In the first column, the concept label is 1.
In the second column, it is 0. In the third column, two examples with opposite
labels select the rule.

##### Passing predicted concepts

While probabilistic semantics require passing the ground truth $c$ to the task
predictor during training (as these are observed variables), CBMs typically
instead pass the concept predictions (opposite of teacher forcing) to make the
model more robust to its own errors. For this reason, we also employ this
technique in CMR in the experiments with CEBAB, CUB and CelebA. For
competitors, we always employ this technique. However, we pass hard concept
predictions in both CMR and the competitors, as to avoid leakage (see Appendix
C).

##### Weight in the loss

We introduce a weight $\beta$ in the regularized objective of Equation 4 (see
below). This adjustment helps to balance the regularization and the task loss.
For instance, if the regularization dominates, CMR might learn rules that can
only be used to predict $y=1$ in practice. Additionally, a larger $\beta$
might assist in settings where achieving high accuracy is difficult for some
concepts; in such cases, concepts with lower accuracy can be more easily
considered irrelevant by choosing a larger $\beta$, as they are unable to
reliably contribute to correct task prediction. The updated objective is as
follows:

$\max_{\Omega}\sum_{(\hat{x},\hat{c},\hat{y})\in
D}\left(\sum_{i=1}^{n_{C}}\log
p(c_{i}=\hat{c}_{i}|\hat{x})\right)+\left(\log\sum_{\hat{s}=1}^{n_{R}}p(s=\hat{s}|\hat{x})\,p(y=\hat{y}|\hat{c},\hat{s})^{\beta}\underbrace{p_{reg}(r=\hat{c}|s)^{\hat{y}}}_{\text{Regularization
Term}}\right)$ (5)

##  Appendix C Experiments

###  C.1 Datasets

##### MNIST+

This dataset [22] consists of pairs of images, where each image is an MNIST
image of a digit and the task is the sum of the two digits. For these tasks,
all concepts are relevant. There is a total of 30,000 training examples and
5,000 test examples.

##### MNIST+∗

We create this dataset as MNIST+ except that the concepts for digits 0 and 1
are removed from the concept set. This makes the concept set incomplete.

##### C-MNIST

We derive this dataset from MNIST [41], taking the MNIST training (60,000
examples) and test set (10,000 examples), randomly coloring each digit either
red or green, and adding these two colors as concepts. There are two tasks:
The first is whether the digit is even, and the second is whether it is odd.
For these tasks, the concepts related to color are irrelevant.

##### CelebA

This is a large-scale face attributes dataset with more than 200K celebrity
images [23]. Each image has 40 concept annotations. As tasks, we take the
concepts $Wavy\\_Hair$, $Black\\_Hair$, and $Male$, removing them from the
concept set.

##### CUB

In this dataset, the task is to predict bird species from images, where the
concepts are 112 bird characteristics such as tail color, wing pattern, etc
[24]. CUB originally consists of 200 tasks, of which we take the first 10.
Some concepts are strongly imbalanced (some are True in only $\pm 0.5\%$ of
examples, others in $40\%$, etc.) and there is a large task imbalance (each
task is True in only $\pm 0.5\%$ of examples).

##### CEBAB

This is a text-based dataset that consists of reviews, where the task is to
classify them as positive or negative [25]. There are 12 concepts (food,
ambience, service, noise, each either unknown, bad or good) and 2 tasks
(positive or negative review).

###  C.2 Training

##### Reproducibility

We seed all experiments using seeds 1, 2 and 3.

##### Soft vs hard concepts

When departing from pure probabilistic semantics, CBMs allow not only the use
of concepts as binary variables, but they allow for concepts to be passed to
the task predictor together with their prediction scores, which is called
employing soft concepts (vs hard concepts). While some CBMs use soft concepts
as this results in higher task accuracy, the downside of this is that the use
of soft concepts also comes with the introduction of input distribution
leakage: The concept probabilities encode much more information than what is
related to the concepts, severely harming the interpretability of the model
[28, 29]. For this reason, in our experiments, all models use hard concepts,
which is realized by thresholding the soft concept predictions at 50%.

##### Model input

For MNIST+, MNIST+∗ and C-MNIST, we train directly on the images. For CelebA
and CUB, instead of training on the images, we train the models on pretrained
ResNet18 embeddings [42]. Specifically, using the torchvision library, we
first resize the images to width and height 224 (using bi-linear
interpolation), then normalize them per channel with means
$(0.485,0.456,0.406)$ and standard-deviations $(0.229,0.224,0.225)$ (for
CelebA only). Finally, we remove the last (classification) layer from the
pretrained ResNet18 model, use the resulting model on each image, and flatten
the output, resulting in an embedding. For CEBAB, we use a pretrained BERT
model [43] to transform the input into embeddings. Specifically, using the
transformers library [44], we create a BERT model for sequence classification
from the pretrained model ’bert-base-uncased’ with 13 labels (1 per concept
and 1 representing both tasks). Then, we finetune this model for 10 epochs
with batch size 2, 500 warmup steps, weight decay 0.01 and 8 gradient
accumulation steps. After training, we use this model to transform each
example into an embedding by outputting the last hidden states for that
example.

##### General training information

In all experiments, we use the AdamW optimizer. All neural competitors are
optimized to maximize the log-likelihood of the data with a weight on the
likelihood of the task (1 if not explicitly mentioned below). After training,
for each neural model in CelebA, CEBAB, MNIST+ and MNIST+∗, we restored the
weights that resulted in the lowest validation loss. In CUB, C-MNIST and the
MNIST+ rule intervention experiment, we do not use a validation set, instead
restoring the weights that resulted in the lowest training loss. In CelebA, we
use a validation split of 8:2, a learning rate of 0.001, a batch size of 1000,
and we train for 100 epochs. In CEBAB, we use a validation split of 8:2, a
learning rate of 0.001, a batch size of 128, and we train for 100 epochs. In
CUB, we use a learning rate of 0.001, a batch size of 1280, and we train for
300 epochs. In MNIST+ and MNIST+∗, we use a validation split of 9:1. We use a
learning rate of 0.0001, a batch size of 512, and we train for 300 epochs. In
C-MNIST, we also use a learning rate of 0.0001, a batch size of 512, and we
train for 300 epochs.

##### General architecture details

In CMR, we use two hidden layers with ReLU activation to transform the input
into a different embedding. We use 3 hidden layers with ReLU activation and an
output layer with Sigmoid activation to transform that embedding into concept
predictions. The component $p(s|x)$ takes as input that embedding and is
implemented by a single hidden layer with ReLU activation and an output layer
outputting $n_{tasks}*n_{R}$ logits, which are reshaped to $(n_{tasks},n_{R})$
and to which a softmax is applied over the rule dimension. The rulebook is
implemented as an embedding module of shape $(n_{tasks}*n_{R},\text{rule emb
size})$ that is reshaped to $(n_{tasks},n_{R},\text{rule emb size})$. The rule
decoder is implemented by a single hidden layer with ReLU activation and an
output layer outputting $3*n_{concepts}$ logits, which are reshaped to
$(n_{concepts},3)$, after which a Softmax is applied to the last dimension;
the result corresponds to $p(r|s)$. At test time, we make $p(r|s)$
deterministic by setting the probability for the most likely role for each
concept to 1 and the others to 0 (effectively collapsing each rule
distribution to the most likely rule for that distribution). Then, exactly one
rule corresponds with each $s$.

The deep neural network is a feed-forward neural network consisting of some
hidden layers with ReLU activation and an output layer with Sigmoid
activation.

Both CBM+linear and CBM+MLP have a concept predictor that is a feed-forward
neural network using ReLU activation for the 3 hidden layers and a Sigmoid
activation for the output layer. For CBM+linear, the task predictor is a
single linear layer per task with Sigmoid activation. For CBM+MLP, this is a
feed-forward neural network using ReLU activation for the 3 hidden layers, and
a Sigmoid activation for the output layer.

For CEM, we use 4 layers with ReLU activation followed by a Concept Embedding
Module where the concept embeddings have a size of 30. The task predictor is a
feed-forward neural network using ReLU activation for the 3 hidden layers and
a sigmoid activation for the output layer.

For DCR, we also use 4 layers with ReLU activation to transform the input into
an embedding. Then, one layer with ReLU activation and one with Sigmoid
activation are used to transform the embedding into concept predictions. The
embedding and the concepts are fed to the task predictor, which is a Concept
Reasoning Layer using the product-t norm and a temperature of 10.

For CBM+DT and CBM+XGboost, we train a CBM+MLP and use its concept predictions
as training input to the trees.

In the MNIST+ and MNIST+∗ experiments, as mentioned earlier, we use as input
the two images instead of embeddings. Therefore, in all models, we use a CNN
(trained jointly with the rest of the model) to transform the images into an
embedding. This CNN consists of a Conv2d layer with 6 output channels and
kernel size 5, a MaxPool2d layer with kernel size and stride 2, ReLU
activation, a Conv2d layer with 16 output channels and kernel size 5, another
MaxPool2d layer with kernel size and stride 2, and another ReLU activation.
The result is flattened and a linear layer is used to output an embedding per
image (with size the same as the number of units in the hidden layers of the
rest of the models). This results in 2 embeddings (one per image), which are
combined using 10 linear layers, each with ReLU activation (except the last
one) and again the same number of units (except the first layer, which has
2*number of units). Additionally, the CNN can output concept predictions by
applying 3 linear layers with ReLU activation and a linear layer with a
Softmax to each image embedding. This results in 10 concept predictions per
image, which are concatenated. The final output of the CNN is the tuple of
concept predictions and embedding.

In the C-MNIST experiments, the input is a single image. We use a similar CNN
architecture as for MNIST+ but with two differences. Firstly, the activation
before the concept prediction is a Softmax on only the first 10 concepts
(related to the digits), while the activation on the last 2 concepts is
Sigmoid. Secondly, after the flattening operation, we use 3 linear layers with
ReLU activation and 1 linear layer without activation to transform the
embedding into a different one.

##### Hyperparameters per experiment

We use number of hidden units and embedding size interchangeably. In CelebA,
we always use 500 units in each hidden layer, except for CBM+linear and CMR
where we use 100 units instead. For the deep neural network, we use 10 hidden
layers. CMR uses a rule embedding size of 100, at most 5 rules per task, a
$\beta$ of 30, and we reset the selector every 35 epochs. The trained CBM+MLP
for CBM+DT and CBM+XGboost has a weight on the task of 0.01.

In CEBAB, we use 300 units in the hidden layers, except for CMR where we use
100 units instead. For the deep neural network, we use 10 hidden layers. We
additionally put a weight on the task loss of 0.01. For CMR, we use a rule
embedding size of 100, at most 15 rules per task, a $\beta$ of 4, and we reset
the selector every 10 epochs. For CBM+DT and CBM+XGboost, the trained CBM+MLP
has a weight on the task of 0.01.

In CUB. we use 100 units in the hidden layers, the deep neural network has 2
hidden layers, and we use a weight on the task loss of 0.01 for concept-based
competitors. For CMR, we use a $\beta$ of 3, and additionally down-weigh the
loss for negative instances with a weight of 0.005 to deal with the class
imbalance. We use a rule embedding size of 500, at most 3 rules per task, and
we reset the selector every 25 epochs. For CBM+XGBoost, we add a weight of 200
for the positive instances to deal with the class imbalance. For CBM+DT and
CBM+XGboost, we do not train a CBM+MLP, instead using CMR’s concept predictor.

In MNIST+ and MNIST+∗, we use the CNN as described earlier. We always use 500
units in the hidden layers, except for CBM+linear and CMR where we use 100
units. For the deep neural network, we use 10 hidden layers. For CMR, we use a
rule embedding size of 1000, at most 20 rules per task, we reset the selector
every 40 epochs, and $\beta$ is 0.1. In MNIST+ specifically, instead of
passing the CNN’s output embedding to the rule selector $p(s|x)$, we pass the
CNN’s concept predictions, showing that this alternative can also be used
effectively when using a complete concept set. For CBM+DT and CBM+XGboost, we
train a CBM+MLP with weight on the task of 0.01 and use its concept
predictions as input to the trees. For the rule intervention experiment on
MNIST+ (where we give CMR a rulebook size that is too small to learn all
ground truth rules), we allow it to learn at most 9 rules per task. Here, the
input to the selector is the CNN’s output embedding. In MNIST+∗, we pass the
CNN’s output embedding to the rule selector.

In C-MNIST, we use the second CNN described above. We always use 500 units in
the hidden layers, except for CBM+linear where we use 100 units. For the deep
neural network, we use 10 hidden layers. For DCR and CEM, we put a weight on
the task loss of 0.01. For CMR, the rule book has at most 6 rules per task,
with rule embeddings of size 1000. We use a $\beta$ of 1, reset the selector
every 40 epochs, and additionally put a weight on the concept reconstruction
relative to the concept counts. The CBM+MLP we train for CBM+DT and
CBM+XGboost has a weight of 0.01 on the task.

##### Hyperparameter search

For CBM+DT, we tune the maximum depth parameter, trying all values between 1
and $n_{C}$, and report the results with the highest validation accuracy
(training accuracy in absence of a validation set). Parameters for the neural
models were chosen that result in the highest validation accuracy (training
accuracy in absence of a validation set) (for CMR the $\beta$ parameter,
rulebook size and rule embedding size were also chosen based on the learned
rules). For $\beta$, we searched within the grid $[0.1,1,3,4,10,30]$, for the
embedding size within the grid $[10,100,300,500,1000]$, and for the rule
embedding size within $[100,500,1000]$. For the deep neural network’s number
of hidden layers, we searched within the grid $[2,10,20]$. For unmentioned
parameters in the competitors, we used the default values.

##### Remaining setup of the rule intervention experiment

We first train for 300 epochs. Then, we check in an automatic way for rules
that differ from the ground truth. A representative example is the rule
$y_{3}\leftarrow(c_{0,1})\land(c_{1,2})\land(c_{0,3})\land(c_{1,0})$444In this
notation, for brevity, we only show concepts with a role that is positive (of
which none are present in this rule example) or irrelevant (between
parentheses); concepts with negative roles are not shown and are the remaining
ones., which can be used by the selector for correctly predicting that $1+2=3$
and $3+0=3$. After this, we add each missing ground truth rule, except one,
and let CMR continue training for 100 epochs. Consequently, CMR improves its
originally learned rules that differed from ground truth to the ground truth
ones and learns to correctly select between the learned and manually added
rules. For instance, if CMR originally learned a rule
$y_{3}\leftarrow(c_{0,1})\land(c_{1,2})\land(c_{0,3})\land(c_{1,0})$, after
manually adding $y_{3}\leftarrow c_{0,1}\land c_{1,2}$ and finetuning, the
rule improves to $y_{3}\leftarrow c_{0,3}\land c_{1,0}$, and CMR will no
longer select this rule for the examples $3+0$, instead selecting the manually
added rule.

###  C.3 Additional Results

####  C.3.1 Concept interventions

To measure the effectiveness of concept interventions [4], we report task
accuracy before and after replacing the concept predictions with their ground
truth. In Table 4, we observe that CMR is responsive to concept interventions:
After the interventions, CMR achieves perfect task accuracy, outperforming CEM
and DCR. We leave a more extensive investigation of concept interventions for
CMR to future work.

Table 4: Task accuracy before and after concept interventions for MNIST+. | before | after
---|---|---
CBM+MLP | $97.41{\scriptstyle\pm 0.55}$ | $100.0{\scriptstyle\pm 0.00}$
CEM | $92.44{\scriptstyle\pm 0.26}$ | $94.68{\scriptstyle\pm 0.31}$
DCR | $90.70{\scriptstyle\pm 1.21}$ | $94.11{\scriptstyle\pm 0.83}$
CMR (ours) | $97.52{\scriptstyle\pm 0.30}$ | $100.0{\scriptstyle\pm 0.00}$

####  C.3.2 Concept accuracies

Table 5 gives the concept accuracy of CMR and the competitors on all datasets.
CMR’s concept accuracy is similar to its competitors across all datasets.

Table 5: Concept accuracies for all datasets. | mnist+ | mnist+∗ | c-mnist | celeba | cub | cebab
---|---|---|---|---|---|---
CBM+linear | $99.76{\scriptstyle\pm 0.02}$ | $99.73{\scriptstyle\pm 0.02}$ | $99.72{\scriptstyle\pm 0.03}$ | $87.61{\scriptstyle\pm 0.02}$ | $86.24{\scriptstyle\pm 0.05}$ | $92.69{\scriptstyle\pm 0.07}$
CBM+MLP | $99.75{\scriptstyle\pm 0.05}$ | $99.71{\scriptstyle\pm 0.06}$ | $99.80{\scriptstyle\pm 0.02}$ | $87.69{\scriptstyle\pm 0.00}$ | $86.32{\scriptstyle\pm 0.08}$ | $92.67{\scriptstyle\pm 0.07}$
CBM+DT | $99.69{\scriptstyle\pm 0.04}$ | $99.68{\scriptstyle\pm 0.01}$ | $99.81{\scriptstyle\pm 0.01}$ | $87.69{\scriptstyle\pm 0.01}$ | $85.95{\scriptstyle\pm 0.08}$ | $92.83{\scriptstyle\pm 0.02}$
CBM+XGB | $99.69{\scriptstyle\pm 0.04}$ | $99.68{\scriptstyle\pm 0.01}$ | $99.81{\scriptstyle\pm 0.01}$ | $87.69{\scriptstyle\pm 0.01}$ | $85.95{\scriptstyle\pm 0.08}$ | $92.83{\scriptstyle\pm 0.02}$
CEM | $99.26{\scriptstyle\pm 0.04}$ | $99.26{\scriptstyle\pm 0.13}$ | $99.77{\scriptstyle\pm 0.01}$ | $87.61{\scriptstyle\pm 0.01}$ | $85.82{\scriptstyle\pm 0.23}$ | $92.46{\scriptstyle\pm 0.13}$
DCR | $99.21{\scriptstyle\pm 0.09}$ | $99.74{\scriptstyle\pm 0.02}$ | $99.76{\scriptstyle\pm 0.02}$ | $85.27{\scriptstyle\pm 0.23}$ | $85.67{\scriptstyle\pm 0.15}$ | $92.66{\scriptstyle\pm 0.04}$
CMR (ours) | $99.76{\scriptstyle\pm 0.03}$ | $99.74{\scriptstyle\pm 0.02}$ | $99.82{\scriptstyle\pm 0.01}$ | $86.91{\scriptstyle\pm 0.17}$ | $85.95{\scriptstyle\pm 0.08}$ | $92.70{\scriptstyle\pm 0.08}$

####  C.3.3 Decoded rulebooks

In this section, we provide examples of the decoded rulebooks after training
with seed 1 for our experiments. We do not provide decoded rulebooks for
MNIST+, as these rules always correspond to the ground truth and are the same
over all seeds, i.e. for every task $i$, CMR learns a rule per possible pair
of digits that correctly sums to that number $i$. An example of such a rule is
$y_{3}\leftarrow c_{1,2}\land c_{2,1}\land D$ where $D$ is a conjunction of
$n_{C}-2$ conjuncts, where each conjunct is the negation of a different
concept. In the tables in this section, we provide the decoded rulebooks for
MNIST+∗, C-MNIST, CelebA (for all concept subsets, but not the complete
rulebook for $n_{C}=37$), CUB (not complete either) and CEBAB. Importantly,
for brevity, we use a different notation for the rules for C-MNIST, MNIST+∗
and CUB: We only show concepts in the rule with as role either positive (as
is) or irrelevance (between parentheses); we do not show concepts with
negative roles. For the other rulebooks, we use the standard notation.

##### C-MNIST

CMR has learned that the concepts red and green are irrelevant for predicting
even or odd, learning the (same) ground truth rules for all seeds. We show
these rules in Table 6.

##### MNIST+∗

For brevity, we drop the notation that shows whether the concept is related to
the first or second digit. Firstly, consider the tasks $y_{0}$ and $y_{1}$.
For these tasks, we are essentially missing all the concepts we need for the
ground truth rules; we can only predict True by learning the rule that is the
negation of all concepts (in the used rule notation, the empty rule), which
CMR does. Then, to be able to predict False, it learns some arbitrary rules.
Secondly, consider the tasks $y_{2}$ to $y_{10}$. As we are missing the
concepts for digits 0 and 1, we cannot learn all ground truth rules for these
tasks. For example, while CMR can (and does) still learn the rule
$y_{4}\leftarrow 2\land 2$, it is impossible to learn a rule like
$y_{4}\leftarrow 1\land 3$. Instead, CMR learns the rule $y_{4}\leftarrow 3$,
which can be selected in case it needs to predict that $1+3=4$. Lastly,
consider the tasks $y_{11}$ to $y_{18}$. CMR finds all ground truth rules, as
they can be found. We show the learned rules in Figure 5.

##### CEBAB

For predicting $negative$, CMR has learned as one of its rules the empty rule
(rule 1), signifying that the other rules (prototypes) it has learned are
unable to predict True for all training examples. Similarly, it has learned a
rule that always evaluates to False (rules 5, 6 and 7, as food has to be both
good and bad). The remaining rules are prototypes. For instance, rule 2
signifies that for some examples if food is bad and service is not good, even
though ambiance might not be bad and noise is unknown, the review is negative.
Rule 3 signifies that even when food, ambiance and noise are not bad, if
service is not good, the review can be negative. We show the learned rules in
Table 7.

##### CUB

We show some of the learned rules in Table 8 and some examples that satisfy
these rules in Figure 6.

##### CelebA

First consider the rules for $n_{C}=1$. For each task, it learns the empty
rule, which can always be used to predict True, and two rules that together
can always be used to predict False. As mentioned in the main text, these
rules cannot be considered meaningful, but since we only have one concept, it
makes sense that CMR learns these rules. Consider now the rules for
$n_{C}=12$. Rules 1, 4 and 7 are rules that always evaluate to False, as
$Bald$ and $Blond\\_Hair$ cannot be active at the same time. The remaining
rules form prototypes. For $n_{C}=37$, we also provide a part of the rulebook.
Similarly, rules 1, 2, 9 and 10 form rules that always evaluate False; the
others form prototypes. We show the learned rules in Tables 9, 10 and 11.

Table 6: Rulebook for C-MNIST. $even\leftarrow 0\land(r)\land(g)$
---
$even\leftarrow 2\land(r)\land(g)$
$even\leftarrow 4\land(r)\land(g)$
$even\leftarrow 6\land(r)\land(g)$
$even\leftarrow 8\land(r)\land(g)$
$odd\leftarrow 1\land(r)\land(g)$
$odd\leftarrow 3\land(r)\land(g)$
$odd\leftarrow 5\land(r)\land(g)$
$odd\leftarrow 7\land(r)\land(g)$
$odd\leftarrow 9\land(r)\land(g)$

$y_{0}\leftarrow$
---
$y_{0}\leftarrow 3\land 5$
$y_{0}\leftarrow 4\land 7$
$y_{0}\leftarrow 4\land 8$
$y_{0}\leftarrow 8\land 9\land 9$
$y_{1}\leftarrow$
$y_{1}\leftarrow 3\land 9$
$y_{1}\leftarrow 7$
$y_{1}\leftarrow 8$
$y_{2}\leftarrow$
$y_{2}\leftarrow 2$
$y_{3}\leftarrow 2$
$y_{3}\leftarrow 3$
$y_{4}\leftarrow 2\land 2$
$y_{4}\leftarrow 3$
$y_{4}\leftarrow 4$
$y_{5}\leftarrow 2\land 3$
$y_{5}\leftarrow 3\land 2$
$y_{5}\leftarrow 4$
$y_{5}\leftarrow 5$
$y_{6}\leftarrow 2\land 4$
$y_{6}\leftarrow 3\land 3$
$y_{6}\leftarrow 4\land 2$
$y_{6}\leftarrow 5$
(a)

$y_{6}\leftarrow 6$
---
$y_{7}\leftarrow 2\land 5$
$y_{7}\leftarrow 3\land 4$
$y_{7}\leftarrow 4\land 3$
$y_{7}\leftarrow 5\land 2$
$y_{7}\leftarrow 6$
$y_{7}\leftarrow 7$
$y_{8}\leftarrow 2\land 6$
$y_{8}\leftarrow 3\land 5$
$y_{8}\leftarrow 4\land 4$
$y_{8}\leftarrow 5\land 3$
$y_{8}\leftarrow 6\land 2$
$y_{8}\leftarrow 7$
$y_{8}\leftarrow 8$
$y_{9}\leftarrow 2\land 7$
$y_{9}\leftarrow 3\land 6$
$y_{9}\leftarrow 4\land 5$
$y_{9}\leftarrow 5\land 4$
$y_{9}\leftarrow 6\land 3$
$y_{9}\leftarrow 7\land 2$
$y_{9}\leftarrow 8$
$y_{9}\leftarrow 9$
$y_{10}\leftarrow 2\land 8$
$y_{10}\leftarrow 3\land 7$
(b)

$y_{10}\leftarrow 4\land 6$
---
$y_{10}\leftarrow 5\land 5$
$y_{10}\leftarrow 6\land 4$
$y_{10}\leftarrow 7\land 3$
$y_{10}\leftarrow 8\land 2$
$y_{10}\leftarrow 9$
$y_{11}\leftarrow 2\land 9$
$y_{11}\leftarrow 3\land 8$
$y_{11}\leftarrow 4\land 7$
$y_{11}\leftarrow 5\land 6$
$y_{11}\leftarrow 6\land 5$
$y_{11}\leftarrow 7\land 4$
$y_{11}\leftarrow 8\land 3$
$y_{11}\leftarrow 9\land 2$
$y_{12}\leftarrow 3\land 9$
$y_{12}\leftarrow 4\land 8$
$y_{12}\leftarrow 5\land 7$
$y_{12}\leftarrow 6\land 6$
$y_{12}\leftarrow 7\land 5$
$y_{12}\leftarrow 8\land 4$
$y_{12}\leftarrow 9\land 3$
$y_{13}\leftarrow 4\land 9$
$y_{13}\leftarrow 5\land 8$
$y_{13}\leftarrow 6\land 7$
(c)

$y_{13}\leftarrow 7\land 6$
---
$y_{13}\leftarrow 8\land 5$
$y_{13}\leftarrow 9\land 4$
$y_{14}\leftarrow 5\land 9$
$y_{14}\leftarrow 6\land 8$
$y_{14}\leftarrow 7\land 7$
$y_{14}\leftarrow 8\land 6$
$y_{14}\leftarrow 9\land 5$
$y_{15}\leftarrow 6\land 9$
$y_{15}\leftarrow 7\land 8$
$y_{15}\leftarrow 8\land 7$
$y_{15}\leftarrow 9\land 6$
$y_{16}\leftarrow 7\land 9$
$y_{16}\leftarrow 8\land 8$
$y_{16}\leftarrow 9\land 7$
$y_{17}\leftarrow 8\land 9$
$y_{17}\leftarrow 9\land 8$
$y_{18}\leftarrow 9\land 9$
(d)

Figure 5: Rulebook for MNIST+∗. Table 7: Rulebook for CEBAB. $(1)\quad
negative\leftarrow$
---
$(2)\quad negative\leftarrow\neg food\\_unknown\land food\\_bad\land\neg
food\\_good\land\neg ambiance\\_bad\land\neg service\\_good\land
noise\\_unknown\land\neg noise\\_bad\land\neg noise\\_good$
$(3)\quad negative\leftarrow\neg food\\_bad\land\neg ambiance\\_bad\land\neg
service\\_good\land noise\\_unknown\land\neg noise\\_bad\land\neg
noise\\_good$
$(4)\quad negative\leftarrow\neg food\\_unknown\land food\\_bad\land\neg
food\\_good\land\neg ambiance\\_good\land\neg service\\_good\land
noise\\_unknown\land\neg noise\\_bad\land\neg noise\\_good$
$(5)\quad negative\leftarrow food\\_unknown\land food\\_bad\land
food\\_good\land\neg ambiance\\_unknown\land ambiance\\_bad\land\neg
ambiance\\_good\land service\\_unknown\land service\\_bad\land
service\\_good\land\neg noise\\_unknown\land\neg noise\\_bad\land
noise\\_good$
$(6)\quad negative\leftarrow food\\_unknown\land food\\_bad\land
food\\_good\land\neg ambiance\\_unknown\land ambiance\\_bad\land\neg
ambiance\\_good\land service\\_unknown\land service\\_bad\land
service\\_good\land\neg noise\\_unknown\land noise\\_bad\land noise\\_good$
$(7)\quad negative\leftarrow food\\_unknown\land food\\_bad\land
food\\_good\land\neg ambiance\\_unknown\land\neg ambiance\\_bad\land\neg
ambiance\\_good\land service\\_unknown\land service\\_bad\land
service\\_good\land\neg noise\\_unknown\land\neg noise\\_bad\land
noise\\_good$
$(8)\quad positive\leftarrow$
$(9)\quad positive\leftarrow\neg food\\_bad\land\neg ambiance\\_bad\land
noise\\_unknown\land\neg noise\\_bad\land\neg noise\\_good$
$(10)\quad positive\leftarrow\neg food\\_unknown\land food\\_bad\land\neg
food\\_good\land\neg service\\_good\land noise\\_unknown\land\neg
noise\\_bad\land\neg noise\\_good$
$(11)\quad positive\leftarrow\neg food\\_unknown\land food\\_bad\land\neg
food\\_good\land\neg ambiance\\_bad\land noise\\_unknown\land\neg
noise\\_bad\land\neg noise\\_good$
$(12)\quad positive\leftarrow food\\_unknown\land food\\_bad\land
food\\_good\land\neg ambiance\\_unknown\land\neg ambiance\\_bad\land\neg
ambiance\\_good\land service\\_unknown\land service\\_bad\land
service\\_good\land noise\\_unknown\land\neg noise\\_bad\land noise\\_good$
Table 8: Rulebook for CUB (not complete).  $(1)\quad
Laysan\\_Albatross\leftarrow underparts\\_white\land breast\\_solid\land
breast\\_white\land throat\\_white\land eye\\_black\land
bill\\_length\\_about\\_the\\_same\\_as\\_head\land belly\\_white\land
back\\_solid\land
belly\\_solid\land(bill\\_hooked\\_seabird)\land(wing\\_grey)\land(wing\\_white)\land(upperparts\\_grey)\land(upperparts\\_black)\land(upperparts\\_white)\land(back\\_brown)\land(back\\_grey)\land(back\\_white)\land(upper\\_tail\\_white)\land(head\\_plain)\land(forehead\\_black)\land(forehead\\_white)\land(under\\_tail\\_black)\land(under\\_tail\\_white)\land(nape\\_white)\land(size\\_medium\\_(9\\_16\\_in))\land(tail\\_solid)\land(primary\\_grey)\land(primary\\_black)\land(primary\\_white)\land(bill\\_black)\land(bill\\_buff)\land(crown\\_black)\land(crown\\_white)\land(wing\\_solid)$
---
$(2)\quad Sooty\\_Albatross\leftarrow bill\\_hooked\\_seabird\land
wing\\_grey\land upperparts\\_grey\land breast\\_solid\land
upper\\_tail\\_grey\land throat\\_black\land eye\\_black\land
bill\\_length\\_about\\_the\\_same\\_as\\_head\land forehead\\_black\land
under\\_tail\\_grey\land under\\_tail\\_black\land
size\\_medium\\_(9\\_16\\_in)\land back\\_solid\land tail\\_solid\land
belly\\_solid\land leg\\_grey\land bill\\_black\land crown\\_black\land
wing\\_solid$
$(3)\quad Brewer\\_Blackbird\leftarrow wing\\_black\land
upperparts\\_black\land breast\\_solid\land eye\\_black\land
under\\_tail\\_black\land belly\\_solid\land
bill\\_black\land(bill\\_all\\_purpose)\land(wing\\_white)\land(underparts\\_black)\land(back\\_black)\land(upper\\_tail\\_black)\land(head\\_plain)\land(breast\\_black)\land(throat\\_black)\land(bill\\_length\\_about\\_the\\_same\\_as\\_head)\land(bill\\_length\\_shorter\\_than\\_head)\land(forehead\\_black)\land(nape\\_black)\land(belly\\_black)\land(wing\\_rounded\\_wings)\land(size\\_small\\_(5\\_9\\_in))\land(shape\\_perching\\_like)\land(back\\_solid)\land(tail\\_solid)\land(primary\\_black)\land(leg\\_black)\land(crown\\_black)\land(wing\\_solid)$

(a) $\quad Laysan\\_Albatross\leftarrow underparts\\_white\land
breast\\_solid\land breast\\_white\land throat\\_white\land eye\\_black\land
bill\\_length\\_about\\_the\\_same\\_as\\_head\land belly\\_white\land
back\\_solid\land
belly\\_solid\land(bill\\_hooked\\_seabird)\land(wing\\_grey)\land(wing\\_white)\land(upperparts\\_grey)\land(upperparts\\_black)\land(upperparts\\_white)\land(...)$

(b) $Sooty\\_Albatross\leftarrow bill\\_hooked\\_seabird\land wing\\_grey\land
upperparts\\_grey\land breast\\_solid\land upper\\_tail\\_grey\land
throat\\_black\land eye\\_black\land
bill\\_length\\_about\\_the\\_same\\_as\\_head\land forehead\\_black\land
under\\_tail\\_grey\land under\\_tail\\_black\land
size\\_medium\\_(9\\_16\\_in)\land back\\_solid\land tail\\_solid\land
belly\\_solid\land leg\\_grey\land bill\\_black\land crown\\_black\land
wing\\_solid$

(c) $Brewer\\_Blackbird\leftarrow wing\\_black\land upperparts\\_black\land
breast\\_solid\land eye\\_black\land under\\_tail\\_black\land
belly\\_solid\land
bill\\_black\land(bill\\_all\\_purpose)\land(wing\\_white)\land(underparts\\_black)\land(back\\_black)\land(upper\\_tail\\_black)\land(head\\_plain)\land(breast\\_black)\land(throat\\_black)\land(bill\\_length\\_about\\_the\\_same\\_as\\_head)\land(...)$

Figure 6: Selection of training examples satisfying learned rules for CUB. For
brevity, we drop some of the irrelevant concepts and replace them with
$(...)$. Table 9: Rulebook for CelebA ($n_{C}=1$). $(1)\quad\quad
Black\\_Hair\leftarrow$
---
$(2)\quad\quad Black\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow$
$(3)\quad\quad Black\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow$
$(4)\quad\quad Male\leftarrow$
$(5)\quad\quad Male\leftarrow 5\\_o\\_Clock\\_Shadow$
$(6)\quad\quad Male\leftarrow\neg 5\\_o\\_Clock\\_Shadow$
$(7)\quad\quad Wavy\\_Hair\leftarrow$
$(8)\quad\quad Wavy\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow$
$(9)\quad\quad Wavy\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow$
Table 10: Rulebook for CelebA ($n_{C}=12$). $(1)\quad\quad
Black\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow\land Arched\\_Eyebrows\land
Bags\\_Under\\_Eyes\land Bald\land Bangs\land Big\\_Lips\land Big\\_Nose\land
Blond\\_Hair\land Blurry\land Brown\\_Hair\land Bushy\\_Eyebrows\land Chubby$
---
$(2)\quad\quad Black\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land\neg
Bags\\_Under\\_Eyes\land\neg Bald\land\neg Blurry\land\neg
Bushy\\_Eyebrows\land\neg Chubby$
$(3)\quad\quad Black\\_Hair\leftarrow\neg Arched\\_Eyebrows\land\neg Blurry$
$(4)\quad\quad Male\leftarrow 5\\_o\\_Clock\\_Shadow\land
Arched\\_Eyebrows\land Bags\\_Under\\_Eyes\land Bald\land Bangs\land
Big\\_Lips\land Big\\_Nose\land Blond\\_Hair\land Blurry\land
Brown\\_Hair\land Bushy\\_Eyebrows\land Chubby$
$(5)\quad\quad Male\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land\neg
Bags\\_Under\\_Eyes\land\neg Bald\land\neg Blurry\land\neg
Brown\\_Hair\land\neg Chubby$
$(6)\quad\quad Male\leftarrow\neg Bald\land\neg Blurry$
$(7)\quad\quad Wavy\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow\land
Arched\\_Eyebrows\land Bags\\_Under\\_Eyes\land Bald\land Bangs\land
Big\\_Lips\land Big\\_Nose\land Blond\\_Hair\land Blurry\land
Brown\\_Hair\land Bushy\\_Eyebrows\land Chubby$
$(8)\quad\quad Wavy\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land\neg
Bags\\_Under\\_Eyes\land\neg Bald\land\neg Big\\_Nose\land\neg Blurry\land\neg
Bushy\\_Eyebrows\land\neg Chubby$
$(9)\quad\quad Wavy\\_Hair\leftarrow\neg Arched\\_Eyebrows\land\neg
Bald\land\neg Bangs\land\neg Blurry$
Table 11: Rulebook for CelebA ($n_{C}=37$) (not complete). $(1)\quad\quad
Black\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow\land Arched\\_Eyebrows\land
Bags\\_Under\\_Eyes\land Bald\land Bangs\land\neg Big\\_Lips\land
Big\\_Nose\land Blond\\_Hair\land Brown\\_Hair\land Bushy\\_Eyebrows\land
Chubby\land\neg Double\\_Chin\land Eyeglasses\land Goatee\land\neg
Gray\\_Hair\land Heavy\\_Makeup\land\neg Mouth\\_Slightly\\_Open\land
Mustache\land\neg Narrow\\_Eyes\land\neg No\\_Beard\land Oval\\_Face\land
Pale\\_Skin\land\neg Pointy\\_Nose\land Receding\\_Hairline\land
Rosy\\_Cheeks\land Sideburns\land Straight\\_Hair\land Wearing\\_Hat\land
Wearing\\_Lipstick\land Wearing\\_Necklace\land\neg Wearing\\_Necktie\land
Attractive\land\neg Young$
---
$(2)\quad\quad Black\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow\land
Bags\\_Under\\_Eyes\land Bald\land\neg Big\\_Lips\land Big\\_Nose\land
Blond\\_Hair\land Brown\\_Hair\land Bushy\\_Eyebrows\land Chubby\land\neg
Double\\_Chin\land Eyeglasses\land Gray\\_Hair\land Heavy\\_Makeup\land\neg
High\\_Cheekbones\land\neg Mouth\\_Slightly\\_Open\land Mustache\land
Narrow\\_Eyes\land\neg No\\_Beard\land\neg Oval\\_Face\land
Pale\\_Skin\land\neg Pointy\\_Nose\land Receding\\_Hairline\land\neg
Rosy\\_Cheeks\land Straight\\_Hair\land Wearing\\_Lipstick\land\neg
Wearing\\_Necklace\land\neg Wearing\\_Necktie\land\neg Young$
$(3)\quad\quad Black\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land\neg
Bald\land\neg Big\\_Lips\land\neg Chubby\land\neg Double\\_Chin\land\neg
Eyeglasses\land\neg Goatee\land\neg Gray\\_Hair\land\neg Mustache\land\neg
Narrow\\_Eyes\land\neg Pale\\_Skin\land\neg Pointy\\_Nose\land\neg
Receding\\_Hairline\land\neg Rosy\\_Cheeks\land\neg Sideburns\land\neg
Wearing\\_Necklace\land\neg Wearing\\_Necktie$
$(4)\quad\quad Black\\_Hair\leftarrow\neg Arched\\_Eyebrows\land\neg
Bangs\land\neg Blond\\_Hair\land\neg Blurry\land\neg Heavy\\_Makeup\land\neg
Narrow\\_Eyes\land\neg Pale\\_Skin\land\neg Pointy\\_Nose\land\neg
Rosy\\_Cheeks\land\neg Wearing\\_Earrings\land\neg Wearing\\_Necklace$
$(9)\quad\quad Wavy\\_Hair\leftarrow 5\\_o\\_Clock\\_Shadow\land
Arched\\_Eyebrows\land Bags\\_Under\\_Eyes\land Bald\land Bangs\land\neg
Big\\_Lips\land Big\\_Nose\land Blond\\_Hair\land Blurry\land\neg
Brown\\_Hair\land\neg Bushy\\_Eyebrows\land Chubby\land\neg Double\\_Chin\land
Eyeglasses\land\neg Gray\\_Hair\land Heavy\\_Makeup\land\neg
Mouth\\_Slightly\\_Open\land\neg Mustache\land\neg Narrow\\_Eyes\land\neg
No\\_Beard\land\neg Oval\\_Face\land Pale\\_Skin\land\neg Pointy\\_Nose\land
Receding\\_Hairline\land Rosy\\_Cheeks\land\neg Sideburns\land
Straight\\_Hair\land Wearing\\_Lipstick\land\neg Wearing\\_Necklace\land\neg
Wearing\\_Necktie\land Attractive\land\neg Young$
$(10)\quad\quad Wavy\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land
Arched\\_Eyebrows\land Bags\\_Under\\_Eyes\land Bald\land Bangs\land
Big\\_Lips\land Big\\_Nose\land Blond\\_Hair\land Brown\\_Hair\land
Bushy\\_Eyebrows\land Chubby\land\neg Double\\_Chin\land Eyeglasses\land
Goatee\land Heavy\\_Makeup\land\neg No\\_Beard\land\neg Oval\\_Face\land\neg
Pointy\\_Nose\land Receding\\_Hairline\land Rosy\\_Cheeks\land\neg
Sideburns\land\neg Smiling\land\neg Wearing\\_Earrings\land\neg
Wearing\\_Necklace\land\neg Wearing\\_Necktie\land\neg Young$
$(11)\quad\quad Wavy\\_Hair\leftarrow\neg 5\\_o\\_Clock\\_Shadow\land\neg
Bags\\_Under\\_Eyes\land\neg Bald\land\neg Big\\_Nose\land\neg Blurry\land\neg
Bushy\\_Eyebrows\land\neg Chubby\land\neg Double\\_Chin\land\neg
Eyeglasses\land\neg Goatee\land\neg Gray\\_Hair\land\neg Mustache\land\neg
Narrow\\_Eyes\land\neg Pale\\_Skin\land\neg Receding\\_Hairline\land\neg
Sideburns\land\neg Straight\\_Hair\land\neg Wearing\\_Hat\land\neg
Wearing\\_Necktie$
$(12)\quad\quad Wavy\\_Hair\leftarrow\neg Bald\land\neg Mustache\land\neg
Narrow\\_Eyes\land\neg Pale\\_Skin\land\neg Rosy\\_Cheeks$

##  Appendix D Code, licenses and resources

For our experiments, we implemented the models in Python 3.11.5 using open
source libraries. This includes PyTorch v2.1.1 (BSD license) [45], PyTorch-
Lightning v2.1.2 (Apache license 2.0), scikit-learn v1.3.0 (BSD license) [46]
and xgboost v2.0.3 (Apache license 2.0). We used CUDA v12.4. Plots were made
using Matplotlib v3.8.0 (BSD license) [47].

All datasets we used are freely available on the web with licenses:

  * •

MNIST - CC BY-SA 3.0 DEED,

  * •

CEBAB - CC BY 4.0 DEED,

  * •

CUB - MIT License
555https://huggingface.co/datasets/cassiekang/cub200_dataset,

  * •

CelebA - The CelebA dataset is available for non-commercial research purposes
only666https://mmlab.ie.cuhk.edu.hk/projects/CelebA.html.

We will not further distribute them.

The experiments for MNIST+, MNIST+∗, C-MNIST, CelebA and CEBAB were run on a
machine with an NVIDIA GeForce GTX 1080 Ti, Intel(R) Xeon(R) CPU E5-2630 v4 @
2.20GHz with 128 GB RAM. The experiment for CUB and the finetuning of the BERT
model used for the CEBAB embeddings were run on a machine with i7-10750H CPU,
2.60GHz × 12, GeForce RTX 2060 GPU with 16 GB RAM. Table 12 shows the
estimated total computation time for a single run per experiment.

Table 12: Estimated total computation time for a single run of each experiment. Experiment | Time (hours)
---|---
CelebA | 3.7
CUB | 1.8
CEBAB | 0.1
MNIST+ | 4.1
MNIST+ rule int. | 0.2
MNIST+∗ | 4.1
C-MNIST | 4.4