# Reduced Implication-bias Logic Loss for Neuro-Symbolic Learning

Hao-Yuan He, Wang-Zhou Dai, Ming Li, Yu Liu, Yong-Chang Ma

###### Abstract

Integrating logical reasoning and machine learning by approximating logical
inference with differentiable operators is a widely used technique in Neuro-
Symbolic systems. However, some differentiable operators could bring a
significant bias during backpropagation and degrade the performance of Neuro-
Symbolic learning. In this paper, we reveal that this bias, named Implication
Bias is common in loss functions derived from fuzzy logic operators.
Furthermore, we propose a simple yet effective method to transform the biased
loss functions into Reduced Implication-bias Logic Loss (RILL) to address the
above problem. Empirical study shows that RILL can achieve significant
improvements compared with the biased logic loss functions, especially when
the knowledge base is incomplete, and keeps more robust than the compared
methods when labelled data is insufficient.

## Introduction

Currently, machine learning methods are achieving significant success in
perception (Krizhevsky, Sutskever, and Hinton 2012; Vaswani et al. 2017; Li et
al. 2021). However, real-world learning tasks usually require not only the
perception ability but also the logical reasoning ability (Kahneman 2013). It
is reasonable to believe that the next generation of advanced artificial
intelligence will be seamlessly constructed by combining logical reasoning
with machine learning.

Neuro-Symbolic (NeSy) AI (Garcez et al. 2019; Raedt et al. 2020; Yang 2022)
aims to combine neural networks and symbolic reasoning. Some people try to
implement a hybrid system by implementing an interface between neural networks
and symbolic reasoning systems. For example, Dai et al. (2019); Zhou (2019)
introduce the Abductive Learning (ABL) framework to integrate first-order
logic with machine learning models and abductive reasoning. Manhaeve et al.
(2018) propose DeepProbLog, which integrates probabilistic logic programming
with deep learning by interfacing them with neural predicates. However, these
models are difficult to train because of the high complexity caused by the
joint optimisation of the neural and symbolic modules. Therefore, many
researchers propose to approximate logical reasoning with differentiable
operators, thereby making it possible to turn symbolic knowledge into loss
functions and train an end-to-end model by gradient descent (Xu et al. 2018;
Giannini et al. 2019; van Krieken, Acar, and van Harmelen 2022).

However, there might remain some problems when approximating the discrete
logical calculations naively (van Krieken, Acar, and van Harmelen 2022). In
the process of approximating implication rules such as $p_{1}\land
p_{2}\land\cdots\land p_{n}\rightarrow q$ with differentiable operations, a
phenomenon that we called Implication Bias could degrade the model
performance. Informally, this rule could be satisfied via vacuous truth
(Enderton 1972), i.e., by negating the premises $p_{1}\land
p_{2}\land\cdots\land p_{n}$. Under ideal circumstances, samples that do not
satisfy the rule premises, their loss values and gradients computed from this
rule should be zero. However, we found this is not the case for semantic loss
and many other widely used logic loss functions derived from fuzzy operators.
Furthermore, the shortcuts problem of neural network training (Geirhos et al.
2020) would amplify this bias and make the model tends to negate the premise
literals when the training data is insufficient.

We point out that the major problem behind this phenomenon is that the model
keeps inferring unwanted negations during training. In logic programming,
people employ Closed World Assumption and Negation As Failure (NAF) to prevent
this issue and guarantee the soundness of inference (Lloyd 2012).
Nevertheless, in NeSy systems, there lacks such a method to reduce this bias.

In this paper, we formally define _implication bias_ and provide a
straightforward explanation of the above-mentioned phenomenon. Experiments
verify that implication bias is widespread in NeSy logic loss functions
derived from fuzzy operators. We further propose a simple yet efficient
method, named Reduced Implication-bias Logic Loss (RILL), to transform logic
loss functions to reduce this bias. RILL adopts a similar idea as Clark’s
completion in logic programming, which prevents the model from inferring
negated ground fact when it is unnecessary. More specifically, RILL can reduce
the influence of vacuous truth and emphasis the truth values of both rule body
and rule head, making the model more robust and improving its performance.

Following are the two major contributions of this paper:

  * •

We analyse the phenomenon of implication bias caused by differentiable
implication operators and point out what kinds of loss functions will suffer
from this bias.

  * •

We propose a simple yet effective method that can reduce implication bias
named Reduced Implication-bias Logic Loss (RILL). Empirical study shows that
RILL can achieve significant improvements compared with other forms of logic
loss, especially when the knowledge base is incomplete or labelled data is
insufficient.

## Related Work

Some people try to design the structure of neural networks based on logical
rules. Such as (Towell and Shavlik 1994; Li and Srikumar 2019; Hoernle et al.
2022). These structures embedded with logical constraints can perform well in
specific tasks and satisfy their logic constraints. However, training such
kind of model needs a large amount of data.

Statistical Relational (StarAI) and Neural-Symbolic (NeSy) methods such as
DeepProbLog(Manhaeve et al. 2018), TensorLog(Cohen, Yang, and Mazaitis 2020)
Abductive Learning (ABL) (Zhou 2019; Dai et al. 2019)have been proposed to
combine neural networks and logical programming. However, most of these
approaches attempt to approximately perform logical reasoning using
distributed representations in neural networks, which usually requires a
tremendous amount of labelled data. Thus, in this work, differentiable
operators implemented by parameter models will not be involved for simplicity,
e.g. a neural network. Although a pre-trained neural network seems promising,
we remain this direction as future works.

A more straightforward way of interaction between the logical module and the
perception module is designing a logic loss which measures how
unsatisfiability the model’s output is. As the category in (Marra et al.
2021), there are two perspectives of approximating logical reasoning with
differentiable operations. From the perspective of probabilistic logic, Xu et
al. (2018) proposed a semantic loss function to get a logic loss. However, for
efficient computations, they need to encode logical rules in Sequential
Decision Diagram (SDD) (Darwiche 2011) which is an NP-Hard problem and
expensive for most real-world tasks. From the perspective of fuzzy logic,
Fischer et al. (2019); Roychowdhury, Diligenti, and Gori (2021); Giannini et
al. (2019); Badreddine et al. (2022) use fuzzy operators to design logic
losses. Using fuzzy logic to translate logical rules into loss functions is
natural. Our work is closely related to (van Krieken, Acar, and van Harmelen
2022), which analysed different kinds of fuzzy logic operators. Furthermore,
they discovered there exists a significant imbalance of gradient between
premises and consequents in the Reichenbach operator.

We revealed the cause and the negative effect of this kind of bias which we
called Implication Bias by formal definitions and experiments from the view of
machine learning. We found it seems hard to avoid implication bias if some
natural properties of logic are satisfied, indicating that this bias is
widespread and worth paying attention to.

## Preliminaries

### First Order Logic

A First Order Logic (FOL) $\mathcal{L}$ consists of a set $\mathcal{C}$ of
constant symbols, a set $\mathcal{F}$ of functional symbols, a set
$\mathcal{P}$ of predicates (relations) symbols, and a set $\mathcal{V}$ of
variable symbols, a set $\\{\neg,\land,\lor,\rightarrow,\leftrightarrow\\}$ of
connectives, a set $\\{\forall,\exists\\}$ of quantifiers.

The connectives set can be reduced to $\\{\neg,\rightarrow\\}$ because other
operations can be replaced with a combination of these two operations. For
example, $p\land q\equiv\neg(p\rightarrow\neg q),p\leftrightarrow
q\equiv\neg((p\rightarrow q)\rightarrow\neg(q\rightarrow p)),p\lor q\equiv\neg
p\rightarrow q$. Atom is the basic component of logic formulas, such as
$\text{BiggerThan}(x,\text{Add10}(y)),\text{Equal}(\text{Succ}(x),y)$. Denote
the set of atoms as $\mathcal{A}$, the set of formulas as $\mathbb{F}$.

Following contents about closed-world assumption are based on (Lloyd 2012) and
(Clark 1978).

### Closed World Assumption

The closed-world assumption (CWA) is a presumption that a true statement is
also known to be true. Conversely, what is not currently known to be true, is
false. The opposite of the closed-world assumption is the open-world
assumption (OWA), holding that lack of knowledge does not imply falsity. The
CWA is a very natural rule to use in a database context. Information not
explicitly presented in the database is taken to be false. For example:

> Statement: | Bob and Cam are students.
> ---|---
> Question: | Is Alice a student?
> Closed world answer: | No.
> Open world answer: | Unknown.

#### Negation as Failure

Suppose we wish to infer $\neg\textrm{A}$ from a program P. To use the CWA, we
have to show that A is not a logical consequence of P. Unfortunately, because
of the undecidability of the validity problem of first-order logic, there is
no algorithm which will take an arbitrary A as input and respond in a finite
amount of time with the answer whether A is or is not a logical consequence of
P. If A is not a logical consequence, it may loop forever.

To alleviate this problem, Clark (1978) proposed the negation as failure rule.
It states that if A is in the finite failure set of P, then infer
$\neg\textrm{A}$. We can see that the negation as a failure rule is less
powerful than the CWA. However, implementing anything beyond negation as a
failure rule is difficult in practice.

### Semantics of Continuous-valued Logic111For simplicity, here we only
discuss the case without quantifiers, extending to the case with quantifiers
is straightforward, which will be introduced in Appendix.

To transform logic rules into loss functions, we have to assign every
grounding term in logic rules a continuous value between 0 and 1. In most
cases, this assignment will be given by the machine learning model’s output.

######  Definition 1 (Valuation of Atom).

A valuation of atom is a function $G(\cdot):\mathcal{A}\rightarrow[0,1]$.

It is natural to define the valuation of negation of an atom $G(\neg A)$ as
$1-G(A)$.

######  Definition 2 (Implication Likelihood).

A function $I(\cdot,\cdot):[0,1]\times[0,1]\rightarrow[0,1]$ is implication
likelihood if it is differentiable.

Implication likelihood is a function that is used to estimate the degree of
satisfiability of implication rules, which is closely related to fuzzy t-norms
(Giannini et al. 2019). For example,
$I(G(\text{Raven}(x)),G(\text{Black}(x)))=0.95$ says the satisfiability of
this rule : $\text{Raven}(x)\rightarrow\text{Black}(x)$ is $0.95$.

Since computing the satisfiability of negation and implication rules being
available, as mentioned before, in FOL, $\\{\neg,\rightarrow\\}$ as
connectives are enough.222Although other operators’ likelihoods can be defined
independently with implication likelihood, for simplicity, we only discuss the
case that all the operators’ likelihoods are consistent. The inconsistent case
is easy to extend and will not change the main conclusion. It is easy to
calculate any logic rule’s satisfiability by $\rightarrow$ and $\neg$
recursively.

######  Definition 3 (Logic Likelihood).

Logic Likelihood $s(\cdot,\cdot):\mathbb{F}\times[0,1]^{n}\rightarrow[0,1]$ is
a function that used to estimate the degree of satisfiablity of logic formula.

$s(\cdot,\cdot)$ takes two inputs, the first one is a logic formula, and the
second one is the valuation vector of this logic formula. For example:

$\displaystyle s(P\rightarrow Q,(x,y))$ $\displaystyle=I(x,y)$

######  Definition 4 ($\delta$-Confidence Monotonic).

A Logic Likelihood is called $\delta$-Confidence Monotonic if its Implication
Likelihood satisfies:

  * •

For any $y\in[0,\delta)$, $I(x,y)$ is monotonically decreasing on $x$.

  * •

For any $x\in(1-\delta,1]$, $I(x,y)$ is monotonically increasing on $y$.

Functions with this property are commonly found in many literature such as
(Badreddine et al. 2022; Roychowdhury, Diligenti, and Gori 2021; van Krieken,
Acar, and van Harmelen 2022). For example, the Implication Likelihood used in
(Badreddine et al. 2022; Roychowdhury, Diligenti, and Gori 2021) is defined as
$I(x,y)=1-x+x\cdot y$. It is a $1$-Confidence Monotonic Implication
Likelihood.

An example for understanding this definition may be helpful. Suppose we have
an implication rule, $\text{Raven}(x)\rightarrow\text{Black}(x)$. When
$G(\text{Black}(x))$ is nearly 0, that is to say, $x$ is not black w.h.p., the
higher confidence we trust $\text{Raven}(x)$, the less satisfiability of this
rule, vice versa.

######  Definition 5 (Logic Loss).

A Logic Loss $\ell_{\mathrm{logic}}$ is a function that estimates the degree
of unsatisfiability of logic formula $r$. It is derived from a Logic
Likelihood:

$\ell_{\mathrm{logic}}(r,z)=g(s(r,z))$

where $g$ is a monotonically decreasing function. w.l.o.g., assume $g(1)=0$.

For example, $g$ can be a negative logarithm function , such as
$\ell_{\mathrm{logic}}(r,z)=1-\log(s(r,z)+1)$. In this paper, this function
will be chosen as the default.

######  Theorem 1.

Assume our knowledge base is accurate, and data space
$\mathcal{X}\times\mathcal{Y}$ is separable. Let
$R=R_{\mathrm{task}}(f)+\lambda\cdot R_{\mathrm{logic}}(f)$ with $\lambda\geq
0$ be the conic combination of logic risk
$R_{\mathrm{logic}}(f)=\mathbb{E}_{(\mathcal{X}_{L}\cup\mathcal{X}_{U})\times\mathrm{KB}}[\ell_{\mathrm{logic}}(r,\mathrm{dict}(f(x))]$
and task risk
$R_{\mathrm{task}}(f)=\mathbb{E}_{\mathcal{X}_{L}\times\mathcal{Y}}[\ell_{{\mathrm{task}}}(f(x),y)]$,
then $R$ is consistent with $R_{\mathrm{task}}$, that is to say, for any
measurable function sequence $\\{f^{(n)}(x)\\}_{n\geq 1}$, the following
proposition holds over all distributions on $\mathcal{X}\times\mathcal{Y}$:

$\mathrm{If}\quad R(f^{(n)})\to R^{*}\quad\mathrm{then}\quad
R_{\mathrm{task}}(f^{(n)})\to R_{\mathrm{task}}^{*}.$

This theorem suggests that the additional logic loss does not change the
optimal value of optimisation spaces. Proof of this theorem can be seen in
Appendix.

Combining logic loss with a task-specific loss for machine learning should be
mutually beneficial. In one way, the task-specific loss can direct the model
to achieve a pretty good performance so it can give out valid logic primitive
facts. In the other way, the logic loss can help shrink the empirical optimal
space that can make the model easier to achieve the optimum. However, a logic
loss with $\delta$-confidence monotonic implication likelihood may introduce
bias into NeSy systems during the training process.

## Proposed Method

### Implication Bias

######  Definition 6 ($\delta$-Implication Biased Loss).

A Logic Loss is Implication Biased if its Implication Likelihood $I(x,y)$
satisfies: $\forall x,y\in(0,\delta)$

$\displaystyle\frac{\partial I}{\partial x}<0$

For simplicity, a logic loss is called implication biased if there exists some
$\delta\in(0,1]$ that make this logic loss $\delta$-Implication Biased.

######  Theorem 2.

A Logic Loss $\ell_{\mathrm{logic}}$ with $\delta$-Confidence Monotonic Logic
Likelihood is also $\delta$-Implication Biased.

Implication biased means that when both the premise and the consequent are
close to zero, the gradient given by the logic loss will still be in the
direction of negating the premise. This suggests that implication-biased logic
loss tends to negate the premise of implication rules. The proof can be seen
in Appendix. Since logic likelihoods with $\delta$-confidence monotonic are
commonly used, logic loss functions with implication bias will be widespread.

### Implication Bias: Case Study

Figure 1: Case study of implication bias. These logic rules are both satisfied
subject to their logical constraints.

The following case is designed to illustrate the impact of implication bias
during the training process. In this case, the dataset is constructed from
four clusters. Each data point in this dataset has two attributes:

> colour | $\in$ | $\\{\text{Blue, Green, Red, Gray}\\}$
> ---|---|---
> shape | $\in$ | $\\{\text{Circle, Square, Triangle, Star}\\}$

There are relations between these attributes, which is represented by logic
rules:
$\text{Blue}(x)\leftrightarrow\text{Circle}(x),\text{Green}(x)\leftrightarrow\text{Square}(x),\text{Gray}(x)\leftrightarrow\text{Star}(x),\text{Red}(x)\leftrightarrow\text{Triangle}(x)$.

The training set is split from the whole dataset. It holds 25% data and only
contains the shape label. Two different knowledge bases shown in Fig.1 are
$\\{\text{Blue}(x)\rightarrow\text{Circle}(x)\\}$ and
$\\{\text{Circle}(x)\rightarrow\text{Blue}(x)\\}$.

Task-specific loss $\ell_{\mathrm{task}}$ is CrossEntropy and logic loss
$\ell_{\mathrm{logic}}$ derived from Reichenbach Implication Likelihood
$I(x,y)=1-x+x\cdot y$. Optimization object is
$R_{\mathrm{task}}(f)+\lambda\cdot R_{\mathrm{logic}}(f)$ as mentioned in
Thm.1. The Machine Learning model is a one-hidden-layers neural network with
two linear classification layers for shape and colour.

As the left bottom picture of Fig.1, when $\ell_{\mathrm{logic}}$ is
implication biased, the optimised model will refuse to predict any sample’s
colour as blue, although the initial model can predict colour-label right.
This phenomenon also happened in the right bottom picture of Fig.1. Both of
them negate their rule’s premise.

Figure 2: Distribution of different samples given by a trained model, which is
compute from rule $\text{Circle}(x)\rightarrow\text{Blue}(x)$.

This happens because most of the samples in the training set are irrelevant to
this single implication rule, i.e., neither blue nor circle. As shown in
Fig.2, there is a significant distribution distance of logic loss between
relevant and irrelevant samples against rule
$\text{Circle}(x)\rightarrow\text{Blue}(x)$. Although the irrelevant samples’
logic loss is relatively small, they still produce a non-negligible gradient
to negate this implication rule’s premise.

It may be confusing that our model failed to predict shape-label correctly in
the right bottom picture of Fig.1. This failure comes from the bias of logic
loss which tends to negate the premise (Circle). Although task-specific loss
should lead the model to predict shape right, it compromises such bias, thus
allowing for misclassification of some samples.

(a)  Reichenbach

(b) Semantic Loss

Figure 3: Scatter plot of logic loss value of implication rule $p\rightarrow
q$ and its gradient norm of $p$. $G(p),G(q)\sim\mathcal{U}(0,1)$.

Fig.3 presents the loss value versus gradient norm of 1-Implication Biased
logic loss derived from Reichenbach Implication Likelihood and Semantic Loss
(Xu et al. 2018).

In Fig.2, most of the samples are irrelevant to a single implication rule and
lie in a sensitive region 333Samples in this region are like hard samples in
the noisy label learning, both of them will bring bias. shown in Fig.3, which
is a region that can introduce bias into the training process, and we will
verify its existence experimentally later. Samples lie in this region mostly
satisfy $\neg p$ and will contribute gradients that negate $p$. However, in
the open world, the NeSy system is not able to ground negated premise well for
its undecidability.

##### Remark

From the perspective of deep learning, this bias comes from shortcuts in the
learning process (Geirhos et al. 2020), in this task, negating the premise of
implication rules is a shortcut. From the perspective of logic programming,
there are limitations that negating premise may be difficult to specify in an
open world with NeSy systems, which not being able to ground negated premise
well using a data-driven approach (Wagner and d’Avila Garcez 2022).

### Reduced Implication-bias Logic Loss

Let us analyse implication bias from two perspectives.

##### Optimisation of Machine Learning

Implication bias will induce neural networks to negate the premise of
implication rules, which is a shortcut in the learning process. Considering
neural networks tend to learn shortcuts, this bias will bring a nuisance to
the training process.

##### Logic Programming

Implication bias will induce the model to negate the premise of implication
rules. However, in an open world, negating a predicate is undecidable. For
example, if we have a statement
$\textrm{Raven}(x)\rightarrow\textrm{Black}(x)$. If we try to negate its
premise, that is to say, $\neg\textrm{Raven}(x)$. Since so many predicates can
be "not raven", we do not have an explicit target to improve the model.

##### Insight

Samples in the sensitive region should be assigned less importance to the
training process.

There are two reasons behind this insight.

First, samples in the sensitive region usually get a relatively small loss
value, thus having less importance to the optimisation process than others.
Furthermore, since these samples’ gradients can introduce nuisance into the
training process, it is natural to reduce their importance.

Second, samples in the sensitive region have lower confidence in the premise,
which will introduce undecidability into the training process. As Clark’s
completion try to handle the undecidability of negative predicates by
utilising information explicitly present in the knowledge base. It is natural
to reduce the information that is not explicitly present.

### Reduce Implication Bias by Transformation

Let us use the notation $\mathcal{R}(\cdot)$ to represent a mapping that
transforms a loss function into another loss function. Three different ways
were designed to reduce the implication bias, as shown in Fig.4.

(a) L2 smooth

(b) Hinge

(c) L2 Hinge

Figure 4: Different transformations of reducing.

#### L2 Smooth

Since we want to reduce the bias caused by samples’ gradients in the sensitive
region of biased logic loss, it is natural to smooth by multiplying itself.

$\mathcal{R}_{\textit{l2}}(\ell)=\ell^{2}$

This transformation smooths biased logic loss by multiplying itself. Samples
with lower loss values will be got a lower impact on the training process.

#### Hinge

Since the samples in the sensitive region are either irrelevant to this rule
or satisfy this rule, it is sensible to ignore these samples. One simple way
is to apply a hinge-like transformation.

$\mathcal{R}_{\textit{hinge}}(\ell)=\ell\cdot\mathbb{I}[\ell>\epsilon]$

$\epsilon$ is related to the sensitive region. This transformation is similar
to RAMP loss (Phoungphol, Zhang, and Zhao 2012), which only focuses on the
more relevant samples’ loss.

#### L2+Hinge

Kind of mixing the above transformations:

$\mathcal{R}_{\textit{l2+hinge}}(\ell)=\ell^{2}\cdot\mathbb{I}[\ell\leq\epsilon]+\ell\cdot\mathbb{I}[\ell>\epsilon]$

##### Remark

All these transformations are managing to reduce the sensitive region’s impact
on the training process. This approach will be very efficient as we only
transform a biased logic loss through one-dimension mapping.

Considering both RILL and Clark’s completion aim to reduce the undecidability
of negative information, RILL can be seen as a continuous logic loss with
Clark’s completion implicitly. RILL does not change the information of the
knowledge base and does an implicit completion by reducing the sensitive
region’s importance, thus leading the model to pay more attention to the
samples that are more irrelevant to this rule. A detailed discussion about
Clark’s completion and RILL can be found in Appendix.

## Empirical Study

Just as in the real world, the lack of sufficient labelling data is a common
occurrence, and so is the lack of a complete knowledge base. These situations
leave training our model becoming more challenging. For this reason, in this
section, two challenging situations incomplete knowledge base and insufficient
labelled data will be discussed.

### Settings of Experiments

Compared logic loss is chosen from the fuzzy logic perspective and
probabilistic logic perspective. From the fuzzy logic perspective444Limited by
space, a detailed empirical study on other kinds of fuzzy operators can be
seen in Appendix., the logic loss derived from Reichenbach operators, which is
best-performed in (van Krieken, Acar, and van Harmelen 2022). From the
probabilistic logic perspective, the semantic loss is chosen for its well-
defined and relatively efficient. In the optimisation process, the logic loss
will compute based on rules in the knowledge base and training data. The task-
specific loss will compute only based on labelled data in the training set.
Since this paper focuses on the loss-function-based NeSy systems, other types
of NeSy systems will not be involved. Details and configurations of these
experiments can be found in Appendix.

### Task1: Addition Equations

Inspired by (Hoernle et al. 2022), we construct a semi-supervised-like task,
which uses a few labelled data and many unlabelled while well-structured data
to train a machine learning model. More specifically, data are structured by
addition equations as Fig.5. This structure can not only be used in digital
datasets but all datasets which have ten classes. In this experiment, we
choose MNIST (Deng 2012), FashionMNIST (Xiao, Rasul, and Vollgraf 2017) and
CIFAR-10 (Krizhevsky, Hinton et al. 2009) as basic datasets, we will organize
them as pictures shown in Fig.5. Models used in MNIST/FMNIST are three-layers
Multi-layer Perceptron (MLP), and in CIFAR-10 is ResNet9 (He et al. 2016).
Task-specific loss in this task will be CrossEntropy.

Figure 5: Addition Equation Experiment, data are structured with equation
constraints. In this picture, $1+5=06$.

##### Knowledge Base

Addition equations with four digits have $10\times 10=100$ rules. For example,
rules $5+2=07,5+3=08$ can be represented as:

> $\text{1stD5}(x_{1})\land\text{2ndD2}(x_{2})\rightarrow$ | $\text{3thD0}(x_{3})\land\text{4thD7}(x_{4}).$
> ---|---
> $\text{1stD5}(x_{1})\land\text{2ndD3}(x_{2})\rightarrow$ | $\text{3thD0}(x_{3})\land\text{4thD8}(x_{4}).$

(a) Add-MNIST

(b) Add-FashionMNIST

(c) Add-CIFAR10

Figure 6: model using biased logic loss becomes more vulnerable when the
completeness of KB decreases.

Task1 is well-structured, so it is pretty suitable for exploring the
performance of logic loss functions under the guidance of different knowledge
bases. That is to say, knowledge bases range from complete to incomplete.
Moreover, because it is very flexible in the size of labelled data, it is also
suitable for exploring the performance of logic loss functions in different
scales of labelled datasets. This means we fix the completeness of the
knowledge base and let the labelled dataset change from sufficient to
insufficient.

### Task2: Hierarchical Classification

CIFAR-100(Krizhevsky, Hinton et al. 2009) consists of 100 classes and 20
super-classes (SC). For example, an image can be classified as class-label is
maple and super-class-label is trees. We would like to utilise the
relationships between classes and super-classes in this experiment. The
backbone model used in this task is WideResNet28-8 (Zagoruyko and Komodakis
2016) with two linear classification heads for class-label and super-class-
label separately. The task-specific loss will be CrossEntropy.

##### Knowledge Base

Knowledge rules in this task are relationships between classes and super-
classes, such as:

> $\text{Aquarium fish}(x)\rightarrow$ | $\text{Fishes}(x)$
> ---|---
> $\text{Shark}(x)\rightarrow$ | $\text{Fishes}(x)$

##### Remark

In this task, we still choose a semi-supervised-like setting, where we only
use a small part of class-labelled data, and all super-class labels are
available. Since this task’s knowledge base only restrict a single sample’s
behaviour at one time, an incomplete knowledge case may bring little impact on
the model’s performance. So this task mainly focuses on the effect of
insufficient labelled data, changing the labelled dataset from sufficient to
insufficient.

Both these two tasks are constructed as semi-supervised learning tasks.
However, the difference between these tasks and classical semi-supervised
learning tasks is that these tasks have knowledge bases that can improve
machine learning’s model performance without tremendous data.

Although this setting is like semi-supervised learning, we will not use any
technologies of semi-supervised learning. The only thing we want to show is
that an implication-biased logic loss can hardly help or even harm the machine
learning model’s performance, while this bias can be controlled by Reduced
Implication-bias Logic Loss.

### Incomplete Knowledge Base

In this situation, we are going to discuss the case when we do not have enough
knowledge. As mentioned before, in this setting, we only focus on
task1:Addition Equations.

The completeness of knowledge bases ranges from 100% to 40%. That is to say,
the number of rules in knowledge bases changes from 100 to 40. The size of the
labelled dataset in this task is 100 (MNIST and FashionMNIST) and 2000
(CIFAR10). Notice there are 50,000 data in the training set and 10,000 in the
testing set, which means we only use 1/500 and 2/50 labelled data to train the
model, respectively.

The results are presented in Fig.6. Details of this experiment’s results (raw
data) can be seen in Appendix. As we can see in the picture, when knowledge
bases’ incompleteness increases, the model’s performance tends to decrease.
However, RILL keeps more stable and well-performed.

##### Remark

Notice that the difference between biased logic loss (Fuzzy) and RILL (Hinge)
is only a truncation at the sensitive region controlled by hyper-parameter
$\epsilon$, that is to say, this sensitive region exists, and it is where the
bias comes from. The performance can be significantly improved even if just
applying a truncation on a $\epsilon$ region of a biased logic loss function.

### Insufficient labelled data

With a complete knowledge base, we can reduce the reliance on the labelled
data. However, different types of logic loss functions can bring different
benefits.

labelled data | 8 | 4 | 2 | 1
---|---|---|---|---
Fuzzy | .19$\pm$.001 | .19$\pm$.004 | .19$\pm$.003 | .19$\pm$.002
SL | .72$\pm$.006 | .72$\pm$.007 | .71$\pm$.029 | .57$\pm$.227
Vanilia | .29$\pm$.016 | .24$\pm$.025 | .18$\pm$.015 | .17$\pm$.012
$\text{RILL}_{l2}$ | .81$\pm$.008 | .82$\pm$.003 | .82$\pm$.004 | .83$\pm$.004
$\text{RILL}_{l2+hinge}$ |  .85$\pm$.003 |  .86$\pm$.004 | .84$\pm$.010 |  .86$\pm$.005
$\text{RILL}_{hinge}$ |  .85$\pm$.006 | .85$\pm$.007 |  .85$\pm$.005 |  .86$\pm$.004

Table 1: Task1 Add-CIFAR-10, accuracies that change the size of the labelled
dataset from eight per class to one per class. The process of getting this
table is similar to Tab.2.

labelled data | 1 | 3 | 5 | 10
---|---|---|---|---
Acc | SC-Acc | Acc | SC-Acc | Acc | SC-Acc | Acc | SC-Acc
Fuzzy | .2291$\pm$.004 | .7484$\pm$.014 | .3246$\pm$.011 | .7570$\pm$.020 | .3858$\pm$.005 |  .7661$\pm$.012 | .4449$\pm$.010 | .7585$\pm$.014
SL | .2281$\pm$.007 | .7384$\pm$.021 |  .3301$\pm$.011 |  .7590$\pm$.022 | .3787$\pm$.011 | .7502$\pm$.015 | .4310$\pm$.034 | .7462$\pm$.037
Vanilia | .2297$\pm$.007 | .7415$\pm$.014 | .3153$\pm$.015 | .7333$\pm$.026 | .3819$\pm$.007 | .7630$\pm$.009 | .4520$\pm$.004 | .7670$\pm$.010
$\text{RILL}_{l2+hinge}$ |  .2363$\pm$.009 |  .7575$\pm$.004 |  .3290$\pm$.005 | .7581$\pm$.007 | .3843$\pm$.013 | .7649$\pm$.016 | .4509$\pm$.002 | .7649$\pm$.008
$\text{RILL}_{l2}$ |  .2357$\pm$.010 | .7449$\pm$.014 | .3262$\pm$.010 |  .7585$\pm$.011 | .3803$\pm$.012 | .7593$\pm$.017 |  .4538$\pm$.003 | .7699$\pm$.005
$\text{RILL}_{hinge}$ | .2334$\pm$.006 | .7463$\pm$.014 | .3228$\pm$.012 | .7520$\pm$.008 |  .3851$\pm$.004 |  .7654$\pm$.006 |  .4562$\pm$.004 |  .7750$\pm$.006
Table 2: Task2-Hierarchical-Classification accuracy that changes the labelled
dataset size from ten per class to one per class. Experiments results
(mean$\pm$std of Acc/SC-Acc) repeat for five times with seed
$\\{2020,2021,2022,2023,2024\\}$. The boldfaces denote the best result in
terms of Acc/SC-Acc, according to the Wilcoxon test at the significance level
of 5%.

In task1, because MNIST/FashionMNIST is much easier compared with CIFAR-10, we
only choose CIFAR-10 to study. The size of labelled data decreases from eight
per class to one per class, which is challenging.

As shown in Tab.1, RILL performs way better than biased logic loss (Fuzzy),
semantic loss and vanilla (without logic loss). We can get pretty good
performance (86% accuracy) at CIFAR-10 using only one labelled data per class
with the complete knowledge base without using any semi-supervised learning
method.

We were surprised by the result that the performance improved as the size of
labelled data decreased. This phenomenon may be similar to smooth label as
discussed in (Müller, Kornblith, and Hinton 2019). It seems RILL can give back
guidance as the smooth label. This kind of smooth label may improve the
generalisation of the model.

In task2, the size of class-labelled data decreases from ten per class to one
per class. As shown in Tab.2, RILL can stay a relatively high performance
(both acc and sc-acc) versus other methods, especially when labelled data size
is small, which shows it is necessary to reduce implication bias.

### Sensitivity Analysis

$\text{RILL}_{hinge},\text{RILL}_{l2+hinge}$ both contain a hyper-parameter
$\epsilon$ in their transformation. In this section, the sensitivity of
$\epsilon$ is revealed. The relation between $\epsilon$ and the model’s
accuracy is shown in Fig.7, in the experiment of Add-MNIST when the
incompleteness of the knowledge base equals 40%.

(a)  $\text{RILL}_{hinge}$

(b)  $\text{RILL}_{l2+hinge}$

Figure 7: Sensitivity Analysis of the hyper-parameter $\epsilon$.

As the threshold $\epsilon$ decreases to a specific range, the model’s
performance falls off, suggesting that there exists a sensitive region of
logic loss, and this region could be the critical point in solving the problem
of implication bias.

## Discussions and Limitations

From the perspective of logic programming, implication bias is closely related
to fuzzy implication operators (van Krieken, Acar, and van Harmelen 2022), and
it seems interesting to discuss it under the closed-world assumption or the
open-world assumption (Wagner and d’Avila Garcez 2022). From the deep learning
perspective, implication bias produces a shortcut that induces neural networks
to overfit.

The limitations of this work are listed in three folds. First, this paper only
computes logic loss from each single logic rule of knowledge bases. It remains
future work to consider the more complex interaction ways between different
logic rules. It is promising to measure complex reasoning processes by loss
functions. Second, this paper’s analysis and formal definition may not be
suitable for probabilistic logic-based loss functions. However, it seems
complicated to use the probabilistic logic-based loss function for the high
complexity of compiling logic circuits, which remains a hard problem. Third,
discussion of the sensitive region is not enough. We do not give a formal
definition of this region which remains future work. This topic is closely
related to the field of Learning with Noisy Labels(Natarajan et al. 2013).
Samples in this sensitive region introduce implication bias into the training
process, which can be seen as the hard samples of learning with the noisy
label. Nevertheless, how to find these samples still remains a key problem in
this field.

## Conclusion

This paper discussed a phenomenon called Implication Bias which happened when
approximating the implication rule with differentiable functions in NeSy
systems. We revealed the cause and the negative effect of Implication bias
through formal definitions and verified its existence in experiments. A simple
yet effective approach is proposed to obtain a Reduced Implication-bias Logic
Loss (RILL) from the biased loss functions. Empirical study shows that RILL
can achieve significant improvements and keeps more robust compared with other
forms of logic loss, especially when the knowledge base is incomplete or the
number of labelled data is limited.

## References

  * Badreddine et al. (2022) Badreddine, S.; d’Avila Garcez, A.; Serafini, L.; and Spranger, M. 2022.  Logic Tensor Networks.  _Artificial Intellegence._ , 303: 103649.
  * Clark (1978) Clark, K. L. 1978.  Negation as failure.  In _Logic and data bases_ , 293–322. Springer.
  * Cohen, Yang, and Mazaitis (2020) Cohen, W.; Yang, F.; and Mazaitis, K. R. 2020.  Tensorlog: A probabilistic database implemented using deep-learning infrastructure.  _Journal of Artificial Intelligence Research_ , 67: 285–325.
  * Dai et al. (2019) Dai, W.; Xu, Q.; Yu, Y.; and Zhou, Z. 2019.  Bridging Machine Learning and Logical Reasoning by Abductive Learning.  In _Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019_ , 2811–2822.
  * Darwiche (2011) Darwiche, A. 2011.  SDD: A New Canonical Representation of Propositional Knowledge Bases.  In _Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona IJCAI 2011_ , 819–826. IJCAI/AAAI.
  * Deng (2012) Deng, L. 2012.  The mnist database of handwritten digit images for machine learning research.  _IEEE Signal Processing Magazine_ , 29(6): 141–142.
  * Enderton (1972) Enderton, H. B. 1972.  _A mathematical introduction to logic_.  Academic Press.  ISBN 978-0-12-238450-9.
  * Fischer et al. (2019) Fischer, M.; Balunovic, M.; Drachsler-Cohen, D.; Gehr, T.; Zhang, C.; and Vechev, M. T. 2019.  DL2: Training and Querying Neural Networks with Logic.  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019_ , volume 97 of _Proceedings of Machine Learning Research_ , 1931–1941. PMLR.
  * Garcez et al. (2019) Garcez, A. d.; Gori, M.; Lamb, L. C.; Serafini, L.; Spranger, M.; and Tran, S. N. 2019.  Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning.  _IfCoLog Journal of Logics and their Applications FLAP 2019_.
  * Geirhos et al. (2020) Geirhos, R.; Jacobsen, J.; Michaelis, C.; Zemel, R. S.; Brendel, W.; Bethge, M.; and Wichmann, F. A. 2020.  Shortcut learning in deep neural networks.  _Nat. Mach. Intell._ , 2(11): 665–673.
  * Giannini et al. (2019) Giannini, F.; Marra, G.; Diligenti, M.; Maggini, M.; and Gori, M. 2019.  On the relation between Loss Functions and T-Norms.  In _International Conference on Inductive Logic Programming_ , 36–45. Springer.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016_ , 770–778. IEEE Computer Society.
  * Hoernle et al. (2022) Hoernle, N.; Karampatsis, R.; Belle, V.; and Gal, K. 2022.  MultiplexNet: Towards Fully Satisfied Logical Constraints in Neural Networks.  In _Proceedings of the AAAI conference on artificial intelligence AAAI 2022_.
  * Kahneman (2013) Kahneman, D. 2013.  _Thinking, Fast and Slow_.  macmillan.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning multiple layers of features from tiny images.  _Technical Report TR 2009_.
  * Krizhevsky, Sutskever, and Hinton (2012) Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012.  ImageNet Classification with Deep Convolutional Neural Networks.  In _26th Annual Conference on Neural Information Processing Systems NIPS 2012_ , 1106–1114.
  * Li et al. (2021) Li, L. H.; Zhang, P.; Zhang, H.; Yang, J.; Li, C.; Zhong, Y.; Wang, L.; Yuan, L.; Zhang, L.; Hwang, J.; Chang, K.; and Gao, J. 2021.  Grounded Language-Image Pre-training.  _CoRR_ , abs/2112.03857.
  * Li and Srikumar (2019) Li, T.; and Srikumar, V. 2019.  Augmenting Neural Networks with First-order Logic.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics ACL 2019_ , 292–302. Association for Computational Linguistics.
  * Lloyd (2012) Lloyd, J. W. 2012.  _Foundations of logic programming_.  Springer Science & Business Media.
  * Maas et al. (2013) Maas, A. L.; Hannun, A. Y.; Ng, A. Y.; et al. 2013.  Rectifier nonlinearities improve neural network acoustic models.  In _Proceedings of the 30th International Conference on Machine Learning ICML 2013_ , volume 30, 3.
  * Manhaeve et al. (2018) Manhaeve, R.; Dumancic, S.; Kimmig, A.; Demeester, T.; and Raedt, L. D. 2018.  DeepProbLog: Neural Probabilistic Logic Programming.  In _Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018_ , 3753–3763.
  * Marra et al. (2021) Marra, G.; Dumancic, S.; Manhaeve, R.; and Raedt, L. D. 2021.  From Statistical Relational to Neural Symbolic Artificial Intelligence.  _ArXiv preprint_ , abs/2108.11451.
  * Müller, Kornblith, and Hinton (2019) Müller, R.; Kornblith, S.; and Hinton, G. E. 2019.  When does label smoothing help?  In _Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019_ , 4696–4705.
  * Natarajan et al. (2013) Natarajan, N.; Dhillon, I. S.; Ravikumar, P.; and Tewari, A. 2013.  Learning with Noisy Labels.  In _27th Annual Conference on Neural Information Processing Systems NIPS 2013_ , 1196–1204.
  * Phoungphol, Zhang, and Zhao (2012) Phoungphol, P.; Zhang, Y.; and Zhao, Y. 2012.  Robust multiclass classification for learning from imbalanced biomedical data.  _Tsinghua Science and technology_ , 17(6): 619–628.
  * Raedt et al. (2020) Raedt, L. D.; Dumancic, S.; Manhaeve, R.; and Marra, G. 2020.  From Statistical Relational to Neuro-Symbolic Artificial Intelligence.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , 4943–4950. ijcai.org.
  * Roychowdhury, Diligenti, and Gori (2021) Roychowdhury, S.; Diligenti, M.; and Gori, M. 2021.  Regularizing deep networks with prior knowledge: A constraint-based approach.  _Knowledge-Based Systems_.
  * Towell and Shavlik (1994) Towell, G. G.; and Shavlik, J. W. 1994.  Knowledge-based artificial neural networks.  _Artificial Intelligence_.
  * van Krieken, Acar, and van Harmelen (2022) van Krieken, E.; Acar, E.; and van Harmelen, F. 2022.  Analyzing Differentiable Fuzzy Logic Operators.  _Artificial Intelligence_.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention is All you Need.  In _Annual Conference on Neural Information Processing Systems 2017 NeurIPS 2017_ , 5998–6008.
  * Wagner and d’Avila Garcez (2022) Wagner, B.; and d’Avila Garcez, A. 2022.  Neural-Symbolic Reasoning Under Open-World and Closed-World Assumptions.  In _CEUR Workshop Proceedings_ , volume 3121. CEUR.
  * Xiao, Rasul, and Vollgraf (2017) Xiao, H.; Rasul, K.; and Vollgraf, R. 2017.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning.  _ArXiv preprint_ , abs/1708.07747.
  * Xu et al. (2018) Xu, J.; Zhang, Z.; Friedman, T.; Liang, Y.; and den Broeck, G. V. 2018.  A Semantic Loss Function for Deep Learning with Symbolic Knowledge.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , 5498–5507. PMLR.
  * Yang (2022) Yang, C. P., Joohyung Lee. 2022.  Injecting Logical Constraints into Neural Networks via Straight-Through Estimators.  In _Thirty-ninth International Conference on Machine Learning ICML 2022_.
  * Zagoruyko and Komodakis (2016) Zagoruyko, S.; and Komodakis, N. 2016.  Wide Residual Networks.  In _Proceedings of the British Machine Vision Conference 2016, BMVC 2016_. BMVA Press.
  * Zhou (2019) Zhou, Z.-H. 2019.  Abductive learning: towards bridging machine learning and logical reasoning.  _Science China Information Sciences_ , 62(7): 1–3.

## Appendix

## Properties of Logic Loss

######  Lemma 1.

Suppose that the Knowledge Base is accurate, and the data space
$\mathcal{X}\times\mathcal{Y}$ is separable. Denote the logic risk of both
labelled and unlabelled data as
$R_{\mathrm{logic}}(f)=\mathbb{E}_{(\mathcal{X}_{L}\cup\mathcal{X}_{U})\times\text{KB}}[\ell_{\mathrm{logic}}(r,\mathrm{dict}(f(x)))]$
and task-specific risk on labelled data as
$R_{\mathrm{task}}(f)=\mathbb{E}_{\mathcal{X}_{L}\times\mathcal{Y}}[\ell_{{\mathrm{task}}}(f(x),y)]$,
then the minimizer set of $R_{\mathrm{logic}}(f)$ and it of
$R_{\mathrm{task}}(f)$ have non-empty intersection, and points in this
intersection are also minimizers of the conic combination of
$R_{\mathrm{logic}}(f)$ and $R_{\mathrm{task}}(f)$.

###### Proof.

Since the Knowledge Base is accurate, i.e., there is no conflict between the
ground truth and the knowledge base, for some $x,y$, if
$\ell_{\mathrm{task}}(f(x),y)=0$, it follows that
$\ell_{\mathrm{logic}}(r,\mathrm{dict}(f(x)))=0$ for any knowledge $r$ in KB.

Due to the separability of $\mathcal{X}\times\mathcal{Y}$, there is at least
one model $f^{*}$ that separate spaces based on labels, i.e. it holds for any
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ that

$\ell_{\mathrm{task}}(f^{*}(x),y)=0$

Thus, we can obtain that

$\ell_{\mathrm{logic}}(r,\mathrm{dict}(f^{*}(x)))=0$

for any knowledge $r$ in KB.

As mentioned above, $f^{*}$ is an element in the intersection of the two
minimizer sets.

Because of the property of minima, $f$ is an element of the intersection
above, it is also a minimizer of the conic combination of
$R_{\mathrm{logic}}(f)$ and $R_{\mathrm{task}}(f)$. ∎

######  Theorem 1.

Assume our knowledge base is accurate, and data space
$\mathcal{X}\times\mathcal{Y}$ is separable. Let
$R=R_{\mathrm{task}}(f)+\lambda\cdot R_{\mathrm{logic}}(f)$ with $\lambda\geq
0$ be the conic combination of logic risk
$R_{\mathrm{logic}}(f)=\mathbb{E}_{(\mathcal{X}_{L}\cup\mathcal{X}_{U})\times\mathrm{KB}}[\ell_{\mathrm{logic}}(r,\mathrm{dict}(f(x))]$
and task risk
$R_{\mathrm{task}}(f)=\mathbb{E}_{\mathcal{X}_{L}\times\mathcal{Y}}[\ell_{{\mathrm{task}}}(f(x),y)]$,
then $R$ is consistent with $R_{\mathrm{task}}$, that is to say, for any
measurable function sequence $\\{f^{(n)}(x)\\}_{n\geq 1}$, the following holds
over all distributions on $\mathcal{X}\times\mathcal{Y}$:

$\mathrm{If}\quad R(f^{(n)})\to R^{*}\quad\mathrm{then}\quad
R_{\mathrm{task}}(f^{(n)})\to R_{\mathrm{task}}^{*}.$

###### Proof.

Let $\\{f^{(n)}(x)\\}_{n\geq 1}$ be any measurable function sequence satisfied
$R(f^{(n)})\to R^{*}$.

Then there exists an integer $N_{\delta}$ such that

$|R(f^{(n)})-R^{*}|<\delta,\ \text{for}\ n>N_{\delta}$

for $\forall\delta>0,\lambda\in(0,1)$.

As the definition of $R$, it follows

$\displaystyle|(R_{\mathrm{task}}(f^{(n)})+\lambda
R_{\mathrm{logic}}(f^{(n)}))-\min(R_{\mathrm{task}}+\lambda
R_{\mathrm{logic}})|$ $\displaystyle<\delta$

Due to Lemma 1, we can obtain

$\displaystyle|(R_{\mathrm{task}}(f^{(n)})+\lambda
R_{\mathrm{logic}}(f^{(n)}))-(R_{\mathrm{task}}^{*}+\lambda
R_{\mathrm{logic}}^{*})|<\delta$

Because of the non-negativity of $\lambda$, it follows

$|R_{\mathrm{task}}(f^{(n)})-R_{\mathrm{task}}^{*}|<\delta$

The inequality above shows that $R_{\mathrm{task}}(f^{(n)})\to
R_{\mathrm{task}}^{*}$. ∎

Figure 8:  task-specific loss shares the same minimiser with the conic
combination of logic loss and task-specific loss. That is to say, additional
logic loss with not change the optimal set.

######  Theorem 2.

A Logic Loss $\ell_{\mathrm{logic}}$ with $\delta$-Confidence Monotonic Logic
Likelihood $I$ is also $\delta$-Implication Biased.

###### Proof.

It’s easy to proof, because if $\ell_{\mathrm{logic}}$ has $\delta$-Confidence
Monotonic Logic Likelihood $I$, when $y\in[0,\delta)$, $I(x,y)$ is
monotonically decreasing on x, as $I$ is differentiable, thus

$\frac{\partial I}{\partial x}<0$

That is to say $\ell_{\mathrm{logic}}$ is $\delta$-Implication Biased. ∎

## Aggregation of Logic Loss

Let us make some examples to illustrate how to aggregate with quantifiers.

##### Forall

If we want to calculate the satisfiability of this rule: $\forall x,F(x)$. The
aggregation value of this rule can be calculated by

$\text{Agg}_{\forall}(F(x))=\text{All}_{\hat{x}\in\mathcal{V}}[s(F,\hat{x})]$

Where $\mathcal{V}$ is the set of valuations of $x$. The $\text{All}(\cdot)$
operator can be the mean value, geometric-mean, or any other operator that can
aggregate values. In this paper, we choose the mean operator as default.

##### Exists

If we want to calculate the satisfiability of this rule: $\exists x,F(x)$. The
aggregation value of this rule can be calculated by

$\text{Agg}_{\exists}(F(x))=\text{Select}_{\hat{x}\in\mathcal{V}}[s(F,\hat{x})]$

Where $\mathcal{V}$ is the set of valuations. The $\text{Select}(\cdot)$
operator can be min value or max value or random sample from set $\mathcal{V}$
or any other operators. In this paper, we choose the min operator as default.

## Details of Experiments

### Optimisation Object

The optimisation object consists of task-specific risk and logic risk.

$\hat{R}=\hat{R}_{\mathrm{task}}+\lambda\cdot\hat{R}_{\mathrm{logic}}$

where $\lambda\geq 0$ is a hyper-parameter, $\hat{R}_{\mathrm{task}}$ and
$\hat{R}_{\mathrm{logic}}$ are empirical risks

$\displaystyle\hat{R}_{\mathrm{task}}$
$\displaystyle=\frac{1}{|\mathcal{D}_{l}|}\sum_{(x,y)\in\mathcal{D}_{l}}\ell_{\mathrm{task}}(f(x),y)$
$\displaystyle\hat{R}_{\mathrm{logic}}$
$\displaystyle=\frac{1}{|\mathcal{D}|\cdot|\text{KB}|}\sum_{x\in\mathcal{D}}\sum_{r\in\text{KB}}\ell_{\mathrm{logic}}(r,\mathrm{dict}(f(x)))$

where $\mathcal{D}_{l}$ means labelled data sampled from
$\mathcal{X}_{L}\times\mathcal{Y}$, $\mathcal{D}$ means training data which
contains labelled and unlabelled data sampled from $\mathcal{X}$, $f(x)$ means
the pseudo label of $x$ predicted by the model, $\mathrm{dict}(f(x))$ means
the valuation of logic rules given $x$,e.g. the output of model organized to a
dictionary.

### Details of Addition Equations

The backbone of MNIST/FashionMNIST is a three-layers (Multilayer Perceptron)
MLP which width of each layer is [256,512,10], activation function is
Rectifier Linear Unit (ReLU) (Maas et al. 2013). Furthermore, the backbone of
CIFAR10 is ResNet9(He et al. 2016). $\lambda$ of logic loss is 0.7 for Fuzzy
and RILL. For semantic loss, $\lambda$ sample from
$\\{0.001,0.005,0.01,0.05,0.1,0.5\\}$, then pick the best one which is 0.5 in
this experiment. Learning rate equals 0.0001, learning rate decay rate equals
0.7, learning rate scheduler chooses StepLR, decay step equals 60. The
optimiser is AdamW as default, and the weight decay rate is set 5e-4.

#### Knowledge Bases

Knowledge base constructed from addition equations of two digits. For example,
0+0=00, 0+1=01,…,9+9=18. In total, there are $10\times 10=100$ probably
equations. Knowledge bases used in this experiment are sampled from these
equations at four different rates {0.4,0.6,0.8,1.0}. All knowledge base
configuration files can be found in the supplementary files.

#### Details of Fig.6

Incompleteness | .4 | .6 | .8 | 1.0
---|---|---|---|---
Fuzzy | .2532$\pm$.016 | .9671$\pm$.001 | .9679$\pm$.001 | .9676$\pm$.000
SL | .8809$\pm$.008 | .9258$\pm$.007 | .9628$\pm$.002 | .9656$\pm$.002
$\text{RILL}_{hinge}$ | .9613$\pm$.004 | .9645$\pm$.001 | .9662$\pm$.002 | .9640$\pm$.002
$\text{RILL}_{l2+hinge}$ | .9613$\pm$.004 | .9645$\pm$.001 | .9662$\pm$.002 | .9640$\pm$.002
$\text{RILL}_{l2}$ | .9573$\pm$.002 | .9594$\pm$.004 | .9592$\pm$.002 | .9572$\pm$.003
(a) Add-MNIST

Incompleteness | .4 | .6 | .8 | 1.0
---|---|---|---|---
Fuzzy | .7343$\pm$.255 | .8656$\pm$.003 | .8724$\pm$.001 | .8768$\pm$.003
SL | .7643$\pm$.009 | .8216$\pm$.014 | .8551$\pm$.002 | .8686$\pm$.002
$\text{RILL}_{hinge}$ | .8556$\pm$.002 | .8681$\pm$.003 | .8696$\pm$.004 | .8710$\pm$.003
$\text{RILL}_{l2+hinge}$ | .8556$\pm$.002 | .8665$\pm$.004 | .8708$\pm$.002 | .8714$\pm$.004
$\text{RILL}_{l2}$ | .8728$\pm$.003 | .8817$\pm$.002 | .8843$\pm$.001 | .8867$\pm$.001
(b) Add-FashionMNIST

Incompleteness | .4 | .6 | .8 | 1.0
---|---|---|---|---
Fuzzy | .2732$\pm$.025 | .7748$\pm$.010 | .7900$\pm$.006 | .7941$\pm$.007
SL | .5175$\pm$.027 | .6870$\pm$.008 | .7777$\pm$.005 | .8032$\pm$.004
$\text{RILL}_{hinge}$ | .6324$\pm$.025 | .7738$\pm$.006 | .7873$\pm$.009 | .7977$\pm$.005
$\text{RILL}_{l2+hinge}$ | .6397$\pm$.017 | .7744$\pm$.009 | .7909$\pm$.006 | .7950$\pm$.004
$\text{RILL}_{l2}$ | .5740$\pm$.018 | .7014$\pm$.011 | .7293$\pm$.003 | .7240$\pm$.003
(c) Add-CIFAR10

Table 3: Details of Fig.6

Here we present the raw data in Fig.6. As shown in Tab.3.

### Config of Hierarchical Classification

The backbone of this task is chosen as WideResNet-28-8(Zagoruyko and Komodakis
2016) with two classification heads, one for class classification, the other
is for super-class classification. $\lambda$ of logic loss equals 0.002 for
Fuzzy and RILL, and semantic loss still chooses 0.5 as default. Learning rate
equals 0.005, learning rate decay rate equals 0.9, decay steps equal 45. The
learning rate scheduler chooses StepWithWarmUp, the warmup epoch set as 5. The
optimiser is used as default, momentum set as 0.9.

#### Knowledge Base

Knowledge base of this experiment is construct from relations between class
and super-class. These relations are organised by (Krizhevsky, Hinton et al.
2009). For example, the relations between classes and super-class Fishes are
listed following.

$\displaystyle\forall x,\mathrm{SC}_{\mathrm{fish}}(x)\rightarrow$
$\displaystyle(\mathrm{C}_{\mathrm{aquariumfish}}(x)\lor\mathrm{C}_{\mathrm{flatfish}}(x)\lor\mathrm{C}_{\mathrm{ray}}(x)\lor\mathrm{C}_{\mathrm{shark}}(x)\lor\mathrm{C}_{\mathrm{trout}}(x))$
$\displaystyle\forall
x,\mathrm{C}_{\mathrm{aquariumfish}}(x)\rightarrow\mathrm{SC}_{\mathrm{fish}}(x)$
$\displaystyle\forall
x,\mathrm{C}_{\mathrm{flatfish}}(x)\rightarrow\mathrm{SC}_{\mathrm{fish}}(x)$
$\displaystyle\forall
x,\mathrm{C}_{\mathrm{ray}}(x)\rightarrow\mathrm{SC}_{\mathrm{fish}}(x)$
$\displaystyle\forall
x,\mathrm{C}_{\mathrm{shark}}(x)\rightarrow\mathrm{SC}_{\mathrm{fish}}(x)$

##### Remark

All experiments above are running with seed
$\in\\{2020,2021,2022,2023,2024\\}$ for five times and take the mean value.
More details can be seen in the supplement files.

## Discussion with other kinds of fuzzy operators

In this section, we discuss several kinds of different fuzzy operators to
experimentally verify these commonly wide used fuzzy operators and also keep
implication biased.

### Sigmoidal Implications

Figure 9:  Scatter plot of logic loss value of implication rule $p\rightarrow
q$ and its gradient norm of $p$. $G(p),G(q)\sim\mathcal{U}(0,1)$. Derived from
Sigmoidal Implication Likelihood.

van Krieken, Acar, and van Harmelen (2022), proposed an operator which is
smoothed Reichenbach operator by a sigmoid function. This implication
likelihood function is defined as:

$\displaystyle\sigma_{I}(p,q)=$
$\displaystyle\frac{1+e^{-s\left(1+b_{0}\right)}}{e^{-b_{0}s}-e^{-s\left(1+b_{0}\right)}}\cdot$
$\displaystyle\left(\left(1+e^{-b_{0}s}\right)\cdot\sigma\left(s\cdot\left(I(p,q)+b_{0}\right)\right)-1\right)$

where $s>0,b_{0}\in\mathbb{R},\sigma(\cdot)=\frac{1}{1+e^{x}}$ denotes the
sigmoid function.

Substituting
$d=\frac{1+e^{-s\left(1+b_{0}\right)}}{e^{-b_{0}s}-e^{-s\left(1+b_{0}\right)}},h=(1+e^{-s\cdot
b_{0}}),f=\sigma\left(s\cdot\left(I(p,q)+b_{0}\right)\right)$, we find:

$\frac{\partial\sigma_{I}(p,q)}{\partial I(p,q)}=d\cdot h\cdot s\cdot
f\cdot(1-f)>0$

that is to say when $I(p,q)$ is $\delta$-Confidence Monotonic,
$\sigma_{I}(p,q)$ will be $\delta$-Confidence Monotonic too. This means logic
loss derived from $\sigma_{I}$ will become implication biased. As shown in
Fig.9.

Figure 10:  Effect of hyper-param $s$, completeness of kb is 40%, hyper-param
$s$ ranging from 4 to 32.

#### Sensitivity Analysis of hyper-param $s$

We repeat the experiment of ADD-MNIST. Implication-bias still happens, as
shown in Fig.10. Following the hyper-parameter setting of (van Krieken, Acar,
and van Harmelen 2022), $b_{0}$ equals -1/2, $I(a,b)=1-a+a\cdot c$. All
experiments are repeated by seed $\in\\{2020,2021,2022,2023,2024\\}$ as well
as other experiments in the main text. As we can see in Fig.10, $s=8$ has the
best performance in $\\{4,8,16,32\\}$, thus we will choose $s=8$ as default.

### Łukasiewicz Implication

Figure 11:  Scatter plot of logic loss value of implication rule $p\rightarrow
q$ and its gradient norm of $p$. $G(p),G(q)\sim\mathcal{U}(0,1)$. Derived from
Łukasiewicz Implication Likelihood.

Łukasiewicz implication likelihood was defined as the following:

$I_{LK}(p,q)=\min(1-p+q,1)$

It is easy to calculate the gradient of this likelihood:

$\frac{\partial I_{LK}}{\partial p}=-1\cdot\mathbb{I}[p>q]$

### Empirical Study

#### Lacking Knowledge

As shown in Fig.12. Sigmoidal and Łukasiewicz implications both suffer
implication bias when the knowledge base becomes incomplete. This indicates
that this phenomenon is quite common in many kinds of fuzzy logic operators
when derived into a logic loss.

Figure 12:  Lacking Knowledge

##### Lacking labelled data

As shown in Fig.13. Sigmoidal and Łukasiewicz implications also both suffer
implication bias when lacking labelled data.

Figure 13:  Lacking labelled Data

### Conclusions

As we can see in the experiments, implication bias is a common phenomenon that
many fuzzy operators will suffer.

## Discussion about Clark’s Completion

Since RILL can be seen as a continuous logic loss with Clark’s completion
implicitly, what about explicitly Clark’s completion in the NeSy system?

However, explicitly Clark’s completion may not be helpful for two reasons.

First, a explicitly Clark’s completion need to replace $\rightarrow$ to
$\leftrightarrow$. For example:

$\displaystyle A\leftarrow A_{1}$ $\displaystyle A\leftarrow A_{2}$
$\displaystyle\cdots$ $\displaystyle A\leftarrow A_{n}$

will be replaced as $A\leftrightarrow(A_{1}\lor A_{2}\lor\cdots\lor A_{n})$.

The fuzzy operator is unsuitable for approximating a rule with many atoms
(Marra et al. 2021). An example is the n-ary Łukasiewicz strong disjunction
$F_{\lor}(x_{1},\cdots,x_{n})=\min(1,x_{1}+\cdots+x_{n})$. Although all
$x_{i}$ can be very small, this approximation of disjunction will give a value
near 1. Because Clark’s completion will increase the number of atoms in the
logical rule, the knowledge base may suffer from this problem after
completion.

Second, in a NeSy system, if knowledge base is incomplete, replace
$\rightarrow$ to $\leftrightarrow$ will change the information of knowledge
base, which may induce wrong information. In logic programming, Clark’s
completion will not change the soundness of the system, while in the NeSy
setting with a data-driven approach, it may not be promised.

As Thm.1 says, when the knowledge base is accurate, a logic loss can be an
addition to the optimisation object without changing the optimal set. It can
not be promised if the knowledge base changes to a probably inaccurate one. In
another words, it’s important to keep knowledge base always be correct if we
want to use $\ell_{\mathrm{task}}+\lambda\cdot\ell_{\mathrm{logic}}$ as
optimization object.

### Experiment

As shown in Fig.14, when the knowledge base becomes incomplete, completion of
the knowledge base will not help improve the model’s performance.

Figure 14:  Incomplete knowledge base: Add-MNIST Clark’s completion

##### Relation between RILL and Negation as Failure

RILL and Negation as Failure aim to reduce the undecidability when deriving
negative information from a logic program. RILL does not change the
information of the knowledge base and does an implicit completion by reducing
the sensitive region’s importance, thus leading the model to pay more
attention to the samples that are more relevant to this rule.


11institutetext: Kimia Lab, University of Waterloo, Waterloo, Canada
22institutetext: Vector Institute, MaRS Centre, Toronto, Canada
33institutetext: NICI Lab, Ontario Tech University, Oshawa, Canada

# Pay Attention with Focus: A Novel Learning Scheme for Classification of
Whole Slide Images

Shivam Kalra 1122 Mohammed Adnan 1122 Sobhan Hemati 11 Taher Dehkharghanian 33
Shahryar Rahnamayan 33 H.R. Tizhoosh 1122

###### Abstract

Deep learning methods such as convolutional neural networks (CNNs) are
difficult to directly utilize to analyze whole slide images (WSIs) due to the
large image dimensions. We overcome this limitation by proposing a novel two-
stage approach. First, we extract a set of representative patches (called
mosaic) from a WSI. Each patch of a mosaic is encoded to a feature vector
using a deep network. The feature extractor model is fine-tuned using
hierarchical target labels of WSIs, i.e., anatomic site and primary diagnosis.
In the second stage, a set of encoded patch-level features from a WSI is used
to compute the primary diagnosis probability through the proposed _Pay
Attention with Focus_ scheme, an attention-weighted averaging of predicted
probabilities for all patches of a mosaic modulated by a trainable focal
factor. Experimental results show that the proposed model can be robust, and
effective for the classification of WSIs.

###### Keywords:

Whole Slide Image, Classification, Multi-Instance Learning

##  1 Introduction

The success of deep learning has opened promising horizons for digital
pathology. AI experts and pathologists are now working together to design
novel image analysis algorithms. The last decade has witnessed the widespread
adoption of digital pathology, leading to the emergence of machine learning
(ML) models for analyzing whole slide images (WSIs). The major applications of
ML in digital pathology include (i) reducing the workload on pathologists, and
(ii) improving cancer treatment procedures [17]. The computational analysis of
WSIs offers various challenges in terms of image size and complexity. These
challenges necessitate the inquiry into more effective ways of analyzing WSIs.
CNNs are at the forefront of computer vision, showcasing significant
improvements over conventional methodologies for visual understanding [14].
However, CNNs can not be directly utilized for processing WSIs due to their
large image dimensions. The majority of the recent work analyzes WSIs at the
patch level that requires manual delineations from experts. These manual
delineations reduce the feasibility of such approaches for real-world
scenarios. Moreover, most of the time, labels are available for an entire WSI
and not for individual patches [2]. Therefore, to learn a WSI representation,
it is necessary to leverage the information present in all patches. Hence,
multiple instance learning (MIL) is a promising venue for vision-related tasks
for WSIs.

The paper’s contribution is three-fold (i) we propose a novel attention-based
MIL approach for the classification of WSIs, (ii) we fine-tune a feature
extractor model using multiple and hierarchically arranged target labels of
WSIs, and (iii) we present insights of the model’s decision making by
visualizing attention values. The method is tested on two large-scale datasets
derived from The Cancer Genomic Atlas (TCGA) repository provided by NIH [23].

##  2 Background

CNN based methods for analyzing histopathological images is well represented
in the literature [5, 4, 18, 6]. Deep learning methods generalize well across
patients, disease conditions, and are robust to the vendor or human-induced
variations, especially when a large amount of training data is available [5].

A WSI usually contains at least two target labels, anatomic site, and primary
diagnosis that are arranged in a hierarchy. The simplest way to deal with
multi-label classification with $k$ labels is to treat this as $k$ independent
binary classification. Although this approach may be helpful, it does not
capture label dependencies. This limitation can degrade the performance in
many applications where there is strong dependency among labels, for example,
in WSI classification. To address this limitation, two different approaches,
i.e., transformation and algorithm adaption methods, have been proposed [27].
In transformation-based methods, multi-label data is converted to new single
label data to apply regular single-label classification. On the other hand, in
the adaptation-based category, this is attempted to modify the basic single-
label algorithm to handle multi-label data [21].

There are two main methods for characterizing WSIs [3]. The first method is
called sub-setting, which considers a small section of a large WSI as an
essential region for analysis. On the other hand, the tiling method, segments
a WSI into smaller and controllable patches (i.e., tiles) [8]. The tiling or
patch-based methods can benefit from MIL. Isle et al. used MIL for digital
pathology and introduces a different variety of MIL pooling functions [10].
Sudarshan et al. used MIL for histopathological breast cancer image
classification [20]. Permutation invariant operator for MIL was introduced by
Tomczak et al. for WSIs processing [22]. Graph neural networks (GNNs) have
also been used for MIL applications because of their permutation invariant
characteristics [2].

##  3 Method

Figure 1: Training a Feature Extractor. A feature extractor is trained with
hierarchical target labels of a WSI. (a) A set of representative WSI patches
(called mosaic) is extracted [13]. (b) The patches are used to fine-tune a
deep network; each patch is assigned the parent WSI’s labels, i.e., anatomic
site and primary diagnosis.

There are two stages in the proposed method (i) bag preparation, and (ii)
multi-instance learning with FocAtt-MIL. In the first stage, representative
patches (called mosaic) are extracted from a WSI. The mosaic’s patches are
encoded to a set of feature vectors (called bag) using a deep network. The
feature extraction model can be a pre-trained network, or can be fined-tuned
to increase its effectiveness as shown in Figure 1. In the second stage, the
proposed MIL technique (called FocAtt-MIL) is trained to predict the primary
diagnosis for a given bag (a WSI). The schematic for the second stage is shown
in Figure 2.

Bag Preparation. A patch selection method proposed by Kalra et al. [13] is
used to extract the representative patches from a WSI. We removed non-tissue
regions using colour threshold. The remaining tissue-containing patches are
grouped into a pre-set number of categories through a clustering algorithm. A
portion of all clustered patches (e.g., 10%) are randomly selected within each
cluster, yielding a _mosaic_. The mosaic is transformed into a bag
$X=\\{x_{1},\dots,x_{n}\\}$, where $x_{i}$ is the feature vector of $i^{th}$
patch, obtained through a deep network (a feature extractor). The Figure 2
shows the bag preparation stage, the frozen network $f(x)$ represents a non-
trainable deep network used as a feature extractor.

Figure 2: Classification of WSIs with FocAtt-MIL. The two-stage method for the
classification of WSI. (a) The mosaic of a WSI is converted to a bag $X$
containing a set of feature vectors $\\{x_{1},\dots,x_{n}\\}$. (b) The feature
vectors in a bag $X$ are transformed to the primary diagnosis probability
through FocAtt-MIL. The prediction probability $p_{i}$ is computed for an
individual feature vector $x_{i}$. A WSI context $g_{X}$ is computed for the
entire bag $X$ using (1). The WSI context $g_{X}$ is used to compute the
attention value $a_{i}$ and the focal factor $\gamma$. The final prediction is
computed using (2).

Fine-tune a Feature Extractor using Hierarchical Labels. In MIL, robust
features enable weak learners to make better predictions thus improving the
final aggregated prediction. A WSI is generally associated with the following
two labels—anatomic site and primary diagnosis. These two labels are arranged
in hierarchy as shown in Figure 1. Consider, $y_{as}$ and $y_{pd}$ represent
anatomic site and primary diagnosis respectively. Then, instead of predicting
these labels independently, we predict $P(y_{as})$, and $P(y_{pd}|y_{as})$.
The conditional probability $P(y_{pd}|y_{as})$ helps in modelling the
dependent relationship. Using Bayes theorem, we get,
$P(y_{as}|y_{pd})={P(y_{pd}|y_{as})P(y_{as})}/{P(y_{pd})}$, where
$P(y_{as}|y_{pd})=1$, because of the dependence. We simplify
$P(y_{pd})=P(y_{pd}|y_{as})P(y_{as})$, and compute cross entropy losses for
the predictions of both $y_{as}$ and $y_{pd}$. We equally weight both the
losses towards the final loss of the network.

WSI Context Learning.  A single vector representation of a WSI (or a bag $X$)
is computed as,

$g_{X}=\phi(\theta(x_{1}),\dots,\theta(x_{n})),$ (1)

where, $\theta$ is a neural network and $\phi$ is a pooling function, such as
sum, mean, and max. It has been proven in [25] that (1) can approximate any
set function. The vector $g_{X}$ is used by the attention module and the focal
network.

The FocAtt-MIL Approach.  The FocAtt-MIL is a permutation-invariant model that
learns to predict a target label (primary diagnosis) $y_{pd}$ from a bag $X$
(a WSI). The approach is composed of four major components (Figure 2):

  1. 1.

Prediction MLP. A prediction $p_{i}$ is computed for each item $x_{i}$ in the
bag $X$, using a trainable deep network called Prediction MLP.

  2. 2.

WSI Context. It a deep network that computes a single vector representing an
entire bag $X$ using (1).

  3. 3.

Attention Module. The attention module is composed of two networks, a
transformation network $T$, and the Attention Network. The attention module
takes the $i^{th}$ patch $x_{i}\in X$, and the WSI context $g_{X}$ to compute
an attention value $a_{i}\in[0,1]$ for that patch.

  4. 4.

Focal Network. Another deep network that uses WSI context $g_{X}$ to compute a
focal factor $\gamma$ (a vector) that modulates the final prediction. The
length of $\gamma$ is same as the number of discrete values in the target
label, thus allowing the per dimension modulation.

The Final Prediction. The final output from the FocAtt-MIL is computed by
aggregating individual attention-weighted predictions modulated by the learned
focal factor, as follows

$y(j)=\sum_{i=1}^{n}{\mathbf{p_{i}}(j)^{\boldsymbol{\gamma}(j)}a_{i}}.$ (2)

The $\mathbf{p_{i}}$, and $\boldsymbol{\gamma}$ in (2) are both vectors. The
$y$ is converted to a probability distribution by dividing with $sum(y)$.

##  4 Results

We evaluated the proposed approach for two different WSI classification tasks.
All experiments are conducted with 4 Nvidia V100 GPUs (32 GB vRAM each). The
code has been written using the Tensorflow library [1].

Table 1: Performance comparison for LUAD/LUSC classification via transfer learning. Algorithm | Accuracy
---|---
Coudray et al. [4] | 0.85
Kalra & Adnan et al. [11] | 0.85
Khosravi et al. [15] | 0.83
Yu et al. [24] | 0.75
FocAtt-MIL (proposed method) | 0.88

LUAD vs LUSC Classification – Lung Adenocarcinoma (LUAD) and Lung Squamous
Cell Carcinoma (LUSC) are two main subtypes of non-small cell lung cancer
(NSCLC) that account for 65-70% of all lung cancers [26]. An automated
classification of these two main sub-types of NSCLC is a crucial step to
assist pathologists [7, 26]. For this task, we establish the efficacy of
FocAtt-MIL to differentiate between LUAD and LUSC. We obtained 2,580
hematoxylin and eosin (H&E) stained WSIs of lung cancer from TCGA repository
[23]. The data is split into 1,806 training, and 774 testing WSIs [11]. The
dataset is approximately 2 TB. We obtained mosaic for each WSI using the
approach in [13], and subsequently converted the mosaic to a bag $X$ of
features using a pre-trained DenseNet [9]. We did not fine-tune the feature
extraction model for this task in order have a fair comparison against other
transfer-learning based approaches in the literature. We trained the FocAtt-
MIL to classify bags between the two sub-types of lung cancer. We achieved the
accuracy of 88% on test WSIs (AUC of 0.92). The accuracy has been reported in
Table 1.

We conducted an ablation study to understand the effect of different model
parameters. Removing the WSI context $g_{X}$ from the attention module,
resulted in 4% reduction of the accuracy. Excluding the focal factor $\gamma$
and the global context $g_{X}$ from the final prediction, resulted in 6%
reduction in the accuracy. The ablation suggests that the model’s performance
is the most optimal by (i) incorporating the WSI context $g_{X}$ in the
attention computation, and (ii) allowing the focal factor to modulate the
final aggregated prediction.

We used the attention module of the trained model to visualize the attention
heat-map on the unseen WSIs (Figure 3). The visual inspection of these two
WSIs reveals that the model made its decision based on regions containing
malignant tissue and ignored non-cancerous regions. In the LUSC WSI (right),
regions with squamous formations are deemed the most important ones. For the
LUAD WSI (left), the salient regions are solely coming from the malignant
area, implying that the model differentiates between normal lung alveolar
tissue and LUAD. Therefore, one could say that attention heatmaps are
histopathologically meaningful. For LUAD samples, regions where cancerous
tissue meets non-cancerous structures are deemed the most important. Such
contrast makes cancerous glandular structures easier to recognize. However,
this phenomenon cannot be seen in LUSC samples, as the model is responsive to
regions that are completely composed of malignant squamous carcinoma.

Figure 3: Attention Visualization. The attention values augmented on the two
exemplar WSIs. Left Image (LUAD): Regions of the highest importance come from
the cancerous regions while sparing normal lung tissue, fibrosis, and mucin
deposition. Additionally, by inspecting important regions at a higher
magnification, it is noticeable that the malignant glandular formations border
with non-malignant areas. Right Image (LUSC): Regions that are considered to
be important for classification are composed of malignant squamous cells.
However, unlike LUAD, the attention model seems to be responsive to regions
with solid malignant structures.

Pan-cancer Analysis –  In the second experiment series, we evaluated the
approach against a large-scale pan-cancer classification of WSIs. The dataset
used for this task has been proposed by Riasatian et al. [19]. It comprises
more than 7 TB data, consisting of 7,097 training, and 744 test WSIs,
distributed across 24 different anatomic sites, and 30 different primary
diagnoses. All WSIs in the dataset are taken from a public repository of WSIs,
TCGA [23]. We obtained a mosaic for each WSI, and then applied a cellularity
filter [19] to further reduce the number of patches in each mosaic.
Subsequently, we obtained 242,202 patches for training WSIs and 116,088
patches for testing WSIs. Each patch is of the size 1000$\times$1000, but we
resized them to 256$\times$256 pixels.

We used three different feature extractors to validate the FocAtt-MIL. We
prepared a separate “bag” for each feature extractor. These three feature
extractors are: DenseNet (DN) [9], KimiaNet [19], and the fine-tuned DenseNet
(FDN). We fined-tuned the DenseNet on training patches using weak labels
obtained from their respective WSIs. The weakly labelled fine-tuning has shown
to be effective [19]. In our case, the weak labels are anatomic site, and
primary diagnosis, arranged in a hierarchy. This hierarchical arrangement of
labels is incorporated during the training using the approach outlined earlier
in the Section 3. For the fine-tuning, we used Adam optimizer [16] and a
learning rate of $10^{-5}$ were used for 20 epochs.

We trained the FocAtt-MIL model with the same architecture for all the three
different bags. We tested three different configurations of FocAtt-MIL, i.e.,
FocAtt-MIL-DN, FocAtt-MIL-KimiaNet, and FocAtt-MIL-FDN. For all the three
configurations, we used the SGD optimizer with a learning rate of 0.01, weight
decay of 10-6, and momentum of 0.9. We applied _gradient clipping_ of 0.01 and
dropout between layers to prevent the exploding gradients. We trained models
for 45 epochs. Figure 4 shows the validation loss and accuracy while training
the three different configurations. It is evident that FocAtt-MIL-FDN is
outperforming from the very early epochs. It is interesting to note that, both
FocAtt-MIL-FDN, and FocAtt-MIL-KimiaNet (feature extractors specialized for
histopathology) seems to have converged to an optimal validation accuracy
around 20-25 epochs.

(a) Validation Loss (b) Validation Accuracy

Figure 4: FocAtt-MIL Training. The loss and accuracy on validation dataset
during the training of three different configurations of FocAtt-MIL, i.e
FocAtt-MIL-DN, FocAtt-MIL-KimiaNet, and FocAtt-MIL-FDN.

The 30 unique primary diagnoses in the dataset can be further grouped into 13
tumor types. The type of tumour is generally known at the inference time, and
the objective is to predict the cancer sub-type. To validate the efficacy of
our model, we computed the cancer sub-type classification (i.e., primary
diagnosis) accuracy for the given tumour type. This type of classification is
called _vertical classification_. The vertical classification results are
reported in Table 2111For abbreviations GBM, LGG, ACC,…, see
_wiki.cancerimagingarchive.net_. The results show that FocAtt-MIL can elevate
the accuracy of pre-trained features; DenseNet features have shown to under-
perform compared to KimiaNet features [19, 12]. However, within the proposed
FocAtt-MIL scheme, DenseNet features become quite competitive. This applies to
the fine-tuned DenseNet (FocAtt-MIL-FDN) as well, whose results are on par
with the highly customized KimiaNet features when used within the FocAtt-MIL
framework.

Table 2: Pan-cancer vertical classification accuracy of FocAtt-MIL for
features from regular DenseNet (FocAtt-MIL-DN), KimiaNet (FocAtt-MIL-
KimiaNet), and DenseNet fine-tuned with hierarchical labels (FocAtt-MIL-FDN).

Tumor Type |  Primary Diagnosis |  FocatAtt-MIL-DN |  FocAtt-MIL-KimiaNet |  FocAtt-MIL-FDN
---|---|---|---|---
Brain |  GBM |  0.9714 |  0.9429 |  0.8571
LGG |  0.6410 |  0.7692 |  0.8205
Endocrine |  ACC |  0.6667 |  0.6667 |  0.6667
PCPG |  1.0000 |  1.0000 |  1.0000
THCA |  0.9608 |  1.0000 |  1.0000
Gastrointestinal tract |  COAD |  0.6875 |  0.4375 |  0.5000
ESCA |  0.5000 |  0.8571 |  0.5714
READ |  0.0833 |  0.5000 |  0.6667
STAD |  0.8333 |  0.7333 |  0.8333
Gynaecological |  CESC |  0.8824 |  0.9412 |  0.7647
OV |  0.5000 |  0.8000 |  1.0000
UCS |  0.6667 |  1.0000 |  0.3333
Liver, pancreaticobiliary |  CHOL |  0.2500 |  0.0000 |  0.5000
LIHC |  0.8857 |  0.9143 |  0.8571
PAAD |  1.0000 |  0.7500 |  0.8333
Melanocytic malignancies |  SKCM |  0.9167 |  0.8750 |  0.9167
UVM |  1.0000 |  0.2500 |  1.0000
Prostate/testis |  PRAD |  1.0000 |  0.9500 |  1.0000
TGCT |  1.0000 |  1.0000 |  1.0000
Pulmonary |  LUAD |  0.5789 |  0.8158 |  0.8947
LUSC |  0.9302 |  0.6977 |  0.7442
MESO |  0.6000 |  1.0000 |  1.0000
Urinary tract |  BLCA |  0.9118 |  1.0000 |  0.8529
KICH |  0.5455 |  0.6364 |  0.7273
KIRC |  0.9200 |  0.9000 |  0.9600
KIRP |  0.5714 |  0.6786 |  0.7143

Conclusions – The accelerated adoption of digital pathology offers a historic
opportunity to find novel solutions for major challenges in diagnostic
histopathology. In this study, we proposed a novel attention-based MIL
technique for the classification of WSIs. We introduced a focal factor,
computed using a global representation of WSI for modulating the individual
patch-level prediction, thus promoting more accurate aggregated final
prediction. We also proposed a novel fine-tuning approach to extract more
robust features from WSI patches. We fine-tune a feature extraction model
using patches and the hierarchical weak labels from their respective WSIs. We
validated the proposed framework on two large datasets derived from TCGA
repository [23]. The results suggest competitive performance on both the
datasets. Furthermore, the proposed method is explainable and transparent as
we utilized the attention values to visualize important regions.

## References

  * [1] Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al.: Tensorflow: A system for large-scale machine learning. In: 12th $\\{$USENIX$\\}$ symposium on operating systems design and implementation ($\\{$OSDI$\\}$ 16). pp. 265–283 (2016)
  * [2] Adnan, M., Kalra, S., Tizhoosh, H.R.: Representation learning of histopathology images using graph neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. pp. 988–989 (2020)
  * [3] Barker, J., Hoogi, A., Depeursinge, A., Rubin, D.L.: Automated classification of brain tumor type in whole-slide digital pathology images using local representative tiles. Medical image analysis 30, 60–71 (2016)
  * [4] Coudray, N., Ocampo, P.S., Sakellaropoulos, T., Narula, N., Snuderl, M., Fenyö, D., Moreira, A.L., Razavian, N., Tsirigos, A.: Classification and mutation prediction from non–small cell lung cancer histopathology images using deep learning. Nature medicine 24(10), 1559–1567 (2018)
  * [5] Dimitriou, N., Arandjelović, O., Caie, P.D.: Deep learning for whole slide image analysis: an overview. Frontiers in medicine 6, 264 (2019)
  * [6] Gao, F., Wu, T., Li, J., Zheng, B., Ruan, L., Shang, D., Patel, B.: Sd-cnn: A shallow-deep cnn for improved breast cancer diagnosis. Computerized Medical Imaging and Graphics 70, 53–62 (2018)
  * [7] Graham, S., Shaban, M., Qaiser, T., Koohbanani, N.A., Khurram, S.A., Rajpoot, N.: Classification of lung cancer histology images using patch-level summary statistics. In: Medical Imaging 2018: Digital Pathology. vol. 10581, p. 1058119\. International Society for Optics and Photonics (2018)
  * [8] Gutman, D.A., Cobb, J., Somanna, D., Park, Y., Wang, F., Kurc, T., Saltz, J.H., Brat, D.J., Cooper, L.A., Kong, J.: Cancer digital slide archive: an informatics resource to support integrated in silico analysis of tcga pathology data. Journal of the American Medical Informatics Association 20(6), 1091–1098 (2013)
  * [9] Huang, G., Liu, Z., Van Der Maaten, L., Weinberger, K.Q.: Densely connected convolutional networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 4700–4708 (2017)
  * [10] Ilse, M., Tomczak, J.M., Welling, M.: Deep multiple instance learning for digital histopathology. In: Handbook of Medical Image Computing and Computer Assisted Intervention, pp. 521–546. Elsevier (2020)
  * [11] Kalra, S., Adnan, M., Taylor, G., Tizhoosh, H.R.: Learning permutation invariant representations using memory networks. In: European Conference on Computer Vision. pp. 677–693. Springer (2020)
  * [12] Kalra, S., Tizhoosh, H.R., Shah, S., Choi, C., Damaskinos, S., Safarpoor, A., Shafiei, S., Babaie, M., Diamandis, P., Campbell, C.J., et al.: Pan-cancer diagnostic consensus through searching archival histopathology images using artificial intelligence. NPJ digital medicine 3(1), 1–15 (2020)
  * [13] Kalra, S., Tizhoosh, H., Choi, C., Shah, S., Diamandis, P., Campbell, C.J., Pantanowitz, L.: Yottixel–an image search engine for large archives of histopathology whole slide images. Medical Image Analysis 65, 101757 (2020)
  * [14] Khan, A., Sohail, A., Zahoora, U., Qureshi, A.S.: A survey of the recent architectures of deep convolutional neural networks. Artificial Intelligence Review 53(8), 5455–5516 (2020)
  * [15] Khosravi, P., Kazemi, E., Imielinski, M., Elemento, O., Hajirasouliha, I.: Deep convolutional neural networks enable discrimination of heterogeneous digital pathology images. EBioMedicine 27, 317–328 (2018)
  * [16] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [17] Madabhushi, A., Lee, G.: Image analysis and machine learning in digital pathology: Challenges and opportunities. Medical image analysis 33, 170–175 (2016)
  * [18] Mahmood, T., Arsalan, M., Owais, M., Lee, M.B., Park, K.R.: Artificial intelligence-based mitosis detection in breast cancer histopathology images using faster r-cnn and deep cnns. Journal of clinical medicine 9(3), 749 (2020)
  * [19] Riasatian, A., Babaie, M., Maleki, D., Kalra, S., Valipour, M., Hemati, S., Zaveri, M., Safarpoor, A., Shafiei, S., Afshari, M., et al.: Fine-tuning and training of densenet for histopathology image representation using tcga diagnostic slides. arXiv preprint arXiv:2101.07903 (2021)
  * [20] Sudharshan, P., Petitjean, C., Spanhol, F., Oliveira, L.E., Heutte, L., Honeine, P.: Multiple instance learning for histopathological breast cancer image classification. Expert Systems with Applications 117, 103–111 (2019)
  * [21] Tidake, V.S., Sane, S.S.: Multi-label classification: a survey. International Journal of Engineering and Technology 7(1045) (2018)
  * [22] Tomczak, J.M., Ilse, M., Welling, M.: Deep learning with permutation-invariant operator for multi-instance histopathology classification. arXiv preprint arXiv:1712.00310 (2017)
  * [23] Tomczak, K., Czerwińska, P., Wiznerowicz, M.: The cancer genome atlas (tcga): an immeasurable source of knowledge. Contemporary oncology 19(1A), A68 (2015)
  * [24] Yu, K.H., Zhang, C., Berry, G.J., Altman, R.B., Ré, C., Rubin, D.L., Snyder, M.: Predicting non-small cell lung cancer prognosis by fully automated microscopic pathology image features. Nature communications 7, 12474 (2016)
  * [25] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., Smola, A.: Deep sets. arXiv preprint arXiv:1703.06114 (2017)
  * [26] Zappa, C., Mousa, S.A.: Non-small cell lung cancer: current treatment and future advances. Translational lung cancer research 5(3), 288 (2016)
  * [27] Zhang, M.L., Zhou, Z.H.: A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering 26(8), 1819–1837 (2013)