11institutetext: University of Bergen, Norway
11email<EMAIL_ADDRESS>
# On the Complexity of Learning
Description Logic Ontologies††thanks: Supported by the University of Bergen.

Ana Ozaki  0000-0002-3889-6207

###### Abstract

Ontologies are a popular way of representing domain knowledge, in particular,
knowledge in domains related to life sciences. (Semi-) automating the process
of building an ontology has attracted researchers from different communities
into a field called “Ontology Learning”. We provide a formal specification of
the exact and the probably approximately correct learning models from
computational learning theory. Then, we recall from the literature complexity
results for learning lightweight description logic (DL) ontologies in these
models. Finally, we highlight other approaches proposed in the literature for
learning DL ontologies.

###### Keywords:

Description Logic Exact Learning Complexity Theory

##  1 Introduction

Ontologies have been used to build concept and role hierarchies mapping and
integrating the vocabulary of data sources, to model definitional sentences in
a domain of interest, to support the inference of facts in knowledge graphs,
among others. However, modelling an ontology that captures in a precise and
clear way the relevant knowledge of a domain can be quite time-consuming. To
imagine this, consider the task of writing a text on a particular topic. The
writer needs to select the right words, think about their meaning, delineate
the scope, and the essential information she or he wants to convey. The
knowledge of the writer needs to be clearly represented in a language, using
the vocabulary and the constructs available in it. In this way, building an
ontology can be seen as a similar process but often there is the additional
challenge that the ontology needs to capture the knowledge of a domain in
which the ‘writer’—an ontology engineer—is not familiar with. The information
in an ontology may need to be validated by a domain expert. Because building
and maintaining ontologies are demanding tasks, several researchers have
worked on developing theoretical results and practical tools for supporting
this process [33, 36].

Here we consider two learning models that were applied to model the process of
building an ontology. The first is the exact learning model [2]. In the exact
learning model, a learner attempts to communicate with a teacher in order to
identify an abstract target concept. When instantiating the exact learning
model to capture the process of building an ontology, one can consider that
the teacher is a domain expert who knows the domain but cannot easily
formulate it as an ontology [27]. On the other side, the role of the learner
is played by an ontology engineer. The abstract target that the ontology
engineer wants to identify is an ontology that reflects the knowledge of the
domain expert (the teacher).

Although the teacher in the exact learning model is often described as a human
(potentially a domain expert), it can also be a batch of examples [7], an
artificial neural network [52, 51], a Tsetlin machine [24] or any another
formalism that can be used to simulate the teacher. The most studied
communication protocol is based on _membership_ and _equivalence_ queries. A
membership query gives to the learner the ability to formulate an example and
ask for its classification (“does X hold in the domain?”). This mode of
learning is called _active learning_. In an equivalence query, the learner
asks whether a certain hypothesis is equivalent to the target. There are
various results in the literature showing that the combination of these two
types of queries allows the learner to correctly identify the target concept
in polynomial time, with hardness results for the case in which one of the two
queries is disallowed [2, 4, 3, 25, 40].

The second model we study is the classical probably approximately correct
(PAC) learning model [46]. In the PAC model, a learner receives classified
examples according to a probability distribution. Then, the learner attempts
to build a hypothesis that is consistent with the examples. This mode of
learning is called _passive learning_ because, in contrast with the active
learning mode, the learner has no control of which examples are going to be
classified. One can instantiate this model to the problem of learning
ontologies by considering that the ontology engineer starts attempting to
collect information about the domain at random (instead of interacting with
the domain expert). One can also consider the case in which, in addition to
the search at random, the ontology engineer can pose membership queries to the
expert. Equivalence queries are not considered in the PAC model because of a
general result showing that learners that can pose equivalence queries to
learn a certain target are also able to accomplish this task within the PAC
model [2] (the combination is not interesting because one problem setting is
‘easier’ than the other, more details in Subsection 3.3).

Having these models in mind, we first present the syntax and the semantics of
the ontology language ${\cal E\\!LH}$ [10, 13]. This is a prototypical
lightweight ontology language based on description logic (DL). Then, we
formalise the exact and the PAC learning models using notions from the theory
of computation. We recall from the literature complexity results for learning
lightweight DL ontologies in these models and provide intuitions about these
results. Finally, we point out other approaches that have been applied for
learning DL ontologies.

##  2 Description Logic

We introduce ${\cal E\\!LH}$ [10, 13], a classical lightweight DL which
features existential quantification ($\exists$) and conjunction ($\sqcap$).
Let ${\sf N_{C}}$, ${\sf N_{R}}$, and ${\sf N_{I}}$ be countably infinite and
disjoint sets of _concept_ and _role_ names. An ${\cal E\\!LH}$ ontology (or
_TBox_) is a finite set of _role inclusions_ (RIs) $r\sqsubseteq s$ with
$r,s\in{\sf N_{R}}$ and _concept inclusions_ (CIs) $C\sqsubseteq D$ with $C,D$
${\cal E\\!L}$ _concept expressions_ built according to the rule

$\displaystyle C,D::=A\mid\top\mid C\sqcap D\mid\exists r.C$

with $A\in{\sf N_{C}}$ and $r\in{\sf N_{R}}$. An ${\cal E\\!LH}$ _TBox_ is a
finite set of RIs and CIs $C\sqsubseteq D$, with $C,D$ being ${\cal E\\!L}$
concept expressions. We denote by ${\cal E\\!LH}_{lhs}$ and ${\cal
E\\!LH}_{rhs}$ the fragments of ${\cal E\\!LH}$ that allow only a concept name
on the right-hand side and on the left-hand side, respectively. That is,
${\cal E\\!LH}_{lhs}$ is the language that allows _complex_ ${\cal E\\!L}$
expressions on the left-hand side and the same idea applies for ${\cal
E\\!LH}_{rhs}$. An ${\cal E\\!L}$ TBox is an ${\cal E\\!LH}$ TBox that does
not have RIs. We may write $C\equiv D$ as a short hand for having both
$C\sqsubseteq D$ and $D\sqsubseteq C$. An _assertion_ is an expression of the
form $r(a,b)$ or of the form $A(a)$, where $A\in{\sf N_{C}}$, $r\in{\sf
N_{R}}$, and $a,b\in{\sf N_{I}}$. An _ABox_ is a finite set of assertions. An
${\cal E\\!LH}$ _instance query_ (IQ) is of the form $C(a)$ or $r(a,b)$ with
$C$ an ${\cal E\\!L}$ concept expression, $r\in{\sf N_{R}}$, and $a,b\in{\sf
N_{I}}$.

We now present the usual semantics of ${\cal E\\!LH}$, which is based on
_interpretations_. An interpretation $\mathcal{I}$ is a pair
$(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$ where $\Delta^{\mathcal{I}}$ is a
non-empty set, called the _domain of $\mathcal{I}$_, and $\cdot^{\mathcal{I}}$
is a function mapping each $A\in{\sf N_{C}}$ to a subset $A^{\mathcal{I}}$ of
$\Delta^{\mathcal{I}}$, each $r\in{\sf N_{R}}$ to a subset $r^{\mathcal{I}}$
of $\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$, and each $a\in{\sf
N_{I}}$ to an element in $\Delta^{\mathcal{I}}$. The function
$\cdot^{\mathcal{I}}$ extends to arbitrary ${\cal E\\!L}$ concept expressions
as follows:

$\displaystyle(\top)^{\mathcal{I}}$ $\displaystyle:={}\Delta^{\mathcal{I}}$
$\displaystyle(C\sqcap D)^{\mathcal{I}}$ $\displaystyle:={}C^{\mathcal{I}}\cap
D^{\mathcal{I}}$ $\displaystyle(\exists r.C)^{\mathcal{I}}$
$\displaystyle:={}\\{d\in\Delta^{\mathcal{I}}\mid\exists e\in
C^{\mathcal{I}}\text{ such that }(d,e)\in r^{\mathcal{I}}\\}$

The interpretation $\mathcal{I}$ _satisfies_ an RI $r\sqsubseteq s$ iff
$R^{\mathcal{I}}\subseteq s^{\mathcal{I}}$. It satisfies a CI $C\sqsubseteq D$
iff $C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$. It satisfies a TBox
$\mathcal{T}$ iff $\mathcal{I}$ satisfies all RIs and CIs in $\mathcal{T}$. We
write $\mathcal{I}\models\alpha$ if $\mathcal{I}$ satisfies an RI, a CI, or a
TBox $\alpha$. A TBox $\mathcal{T}$ _entails_ a CI $\alpha$ (or a TBox
$\mathcal{T}^{\prime}$), written $\mathcal{T}\models\alpha$ (or
$\mathcal{T}\models\mathcal{T}^{\prime}$), iff all interpretations satisfying
$\mathcal{T}$ also satisfy $\alpha$ (or $\mathcal{T}^{\prime}$). Two TBoxes
$\mathcal{T}$ and $\mathcal{T}^{\prime}$ are _equivalent_ , written
$\mathcal{T}\equiv\mathcal{T}^{\prime}$, iff
$\mathcal{T}\models\mathcal{T}^{\prime}$ and
$\mathcal{T}^{\prime}\models\mathcal{T}$. These notions can be adapted as
expected for defining satisfaction and entailment of assertions, ABoxes, and
IQs [10]. Given a TBox $\mathcal{T}$, the _signature_ $\Sigma_{\mathcal{T}}$
of $\mathcal{T}$ is the set of concept and role names occurring in it.

######  Example 1.

Although ${\cal E\\!LH}$ is a very simple language, it is already useful to
represent certain kinds of static knowledge. One can express in ${\cal
E\\!LH}$ that ‘Penicillamine nephropathy is a renal disease’ with the
CI111This example follows modelling guidelines and terms found in the ontology
from the medical domain SNOMED CT [45]. :

${\sf PenicillamineNephropathy}\sqsubseteq{\sf RenalDisease}$

The definitional sentence ‘Penicillamine nephropathy is a renal disease of the
kidney structure caused by penicillamine’ can be expressed as:

${\sf PenicillamineNephropathy}\equiv{\sf RenalDisease}\ \sqcap$ $\exists{\sf
findingSite}.{\sf KidneyStructure}\sqcap\exists{\sf causativeAgent}.{\sf
Penicillamine}.$

An important advantage of representing domain knowledge in an ontology is that
ambiguities found in natural language can be removed. For example, one can
distinguish when ‘is’ should mean a subset relation (represented syntactically
with ‘$\sqsubseteq$’) from when it means an equivalence (represented with the
symbol ‘$\equiv$’).

In the next section, we introduce notions from the theory of computation that
are relevant to define learnability and complexity classes in the exact and
PAC learning models.

##  3 The Complexity of Learning

Complexity classes are defined in terms of a model of computation, a type of
problem, and bounds on the resources (usually time and memory) needed to solve
a problem [44]. In this section, we formally define complexity classes for
_learning problems_ (Subsection 3.3). Before that, we define a general model
of computation that represents the communication of a learner and a teacher
via queries (Subsection 3.1). This model can be specialised for learning
problems in the exact and the PAC learning models. For the exact learning
model, we assume that the learner can pose membership and equivalence queries.
In the PAC learning model, the learner can pose sampling queries. We describe
the queries in detail in Subsection 3.2.

###  3.1 Model of Computation

The main advantage of defining the model of computation is that this opens the
possibility of analysing the learning phenomenon in light of the theory of
computation. Our model of computation for learning problems is based on
_learning systems_ [50]. Learning systems are formulated using the notion of a
pair $(L,T)$ of multitape Turing machines (MTM), one for the learner, $L$, and
one for the teacher, $T$. There are four kinds of tape:

  * •

$L,T$ share a read-only _input tape_ ;

  * •

$L,T$ share a read-write _communication tape_ ;

  * •

$T$ has a read-only tape, called _oracle tape_ , not accessed by $L$; and

  * •

$L$ has a write-only _output tape_ , not accessed by $T$.

Intuitively, the computation of the two MTMs represents the interaction of the
learner and the teacher via queries, where posing a query to the teacher means
writing down the input of the query in the communication tape and entering the
corresponding query state. Then the teacher computes the answer, writes it in
the communication tape (if the computation of the answer terminates), and
enters the corresponding answer state. The learner reads the answer in the
communication tape and continues its computation. This process may continue
forever or halt when the learner writes its final hypothesis in the output
tape and enters the final state. It is assumed that the teacher never enters
the final state (only the learner can enter the final state).

In the definition of a learning system $(L,T)$, we consider that $L$ is a
deterministic MTM (DMTM) with three tapes (input, communication, and output
tapes) and that the set of states contains special elements called _query
states_ , one for each type of query. The teacher $T$ is a non-deterministic
MTM (NMTM) with three tapes (input, communication, and oracle tapes) and the
set of states contains special elements called _answer states_ , one for each
type of query. We describe the types of queries for the exact and PAC learning
models in Subsection 3.2.

A DMTM with $k$ tapes can be defined as a tuple
$\mathcal{M}=(Q,\Sigma,\Theta,q_{0},q_{\sf f})$ where: $Q$ is a finite set of
_states_ ; $\Sigma$ is a finite _alphabet_ containing the _blank symbol_ `␣` ;
$\Theta:(Q\setminus\\{q_{\sf f}\\})\times\Sigma^{k}\rightarrow
Q\times\Sigma^{k}\times\\{l,r\\}^{k}$ is the _transition function_ ; and
$\\{q_{0},q_{\sf f}\\}\subseteq Q$ are the _initial_ and _final_ states. The
expression
$\Theta(q,a_{1},\ldots,a_{k})=(q^{\prime},b_{1},\ldots,b_{k},D_{1},\ldots,D_{k})$,
with $D_{i}\in\\{l,r\\}$, means that if $\mathcal{M}$ is in state $q$ and
heads $1$ through $k$ are reading the symbols $a_{1}$ through $a_{k}$ (resp.)
then $\mathcal{M}$ goes to state $q^{\prime}$, the symbols
$b_{1},\ldots,b_{k}$ are written in tapes $1,\ldots,k$ (resp.) and each head
$i$ moves to the direction corresponding to $D_{i}$. An NMTM is defined in the
same way as a DMTM except that $\Theta:(Q\setminus\\{q_{\sf
f}\\})\times\Sigma^{k}\rightarrow\mathcal{P}(Q\times\Sigma^{k}\times\\{l,r\\}^{k})$.
That is, $\Theta(q,a_{1},\ldots,a_{k})$ is now a _set_ of expressions of the
form $(q^{\prime},b_{1},\ldots,b_{k},D_{1},\ldots,D_{k})$.

A _configuration_ of a MTM with $k$ tapes is a $k$-tuple
$(w_{1}qw^{\prime}_{1},\ldots,w_{k}qw^{\prime}_{k})$ with
$w_{i},w^{\prime}_{i}\in\Sigma^{\ast}$ and $q\in Q$, meaning that the tape $i$
contains the word $w_{i}w^{\prime}_{i}$, the machine is in state $q$ and the
head is on the position of the left-most symbol of $w^{\prime}_{i}$. The
notion of _successive configurations_ is defined as expected in terms of the
transition relations of $L$ and $T$. Whenever $L$ enters a query state, the
transition relation of $T$ is used to define a successive configuration (it
may not be unique due to non-determinism of $T$) and whenever $T$ enters again
in an answer state then the transition relation of $L$ defines the (unique)
successive configuration ($L$ resumes its execution). A _computation_ of
$(L,T)$ on an input word $w_{0}$ is a tree whose paths are sequences of
successive configurations $\alpha_{0},\alpha_{1},\ldots$, where
$\alpha_{0}=q_{0}w_{0}$ is the _initial configuration_ for the input
$w_{0}\in(\Sigma\setminus\\{\leavevmode\hbox{\set@color\ignorespaces\verb*!␣!
}\\})^{\ast}$ and $q_{0}$ is the initial state of $L$. The branches of the
tree correspond to the different possibilities for $T$ to move from one state
to another.

The model of computation that we presented can be generalised to the case in
which there are multiple learners and multiple teachers. For our purposes, it
suffices to consider only one learner and one teacher. In the following, we
explain how the computational model we described can be tailored to the exact
and the PAC learning models, as well as some variants of these models.

###  3.2 Learning Frameworks and Queries

To define the learnability in the exact and PAC models (Subsection 3.3), we
use the notion of a _learning framework_ and three types of queries
(membership and equivalence queries for the exact learning model and sample
queries for the PAC learning model). A learning framework $\mathfrak{F}$ is a
triple $(\mathcal{E},\mathcal{L},\mu)$ where

  * •

$\mathcal{E}$ is a set of examples,

  * •

$\mathcal{L}$ is a set of concept representations222In Machine Learning, a
concept representation is a way of representing a set of examples. This
differs from the notion of a concept in DL., called _hypothesis space_ ,

  * •

and $\mu$ is a function that maps each element of $\mathcal{L}$ to a set of
examples in $\mathcal{E}$.

We call _target_ a fixed but arbitrary element of $\mathcal{L}$ that the
learner wants to acquire. A _hypothesis_ is an element of $\mathcal{L}$ that
represents the ‘idea’ of the learner about the target. This element is often
updated during the computation of a learning system $(L,T)$ until $L$ reaches
its final state (if ever). Given a target $t\in\mathcal{L}$, we say that an
example $e$ is _positive_ for $t$ if $e\in\mu(t)$, and _negative_ otherwise.
Given a hypothesis $h$ and a target $t$ in $\mathcal{L}$ and an example
$e\in\mathcal{E}$, we say that $e$ is a _counterexample_ for $t$ and $h$ if
$e\in\mu(t)\oplus\mu(h)$ (where $\oplus$ denotes the symmetric difference). We
may omit ‘for $t$’ and ‘for $t$ and $h$’ if this is clear from the context.

######  Remark 1.

Given a DL $\mathfrak{L}$, we denote by $\mathfrak{F}(\mathfrak{L})$ the
learning framework $(\mathcal{E},\mathcal{L},\mu)$ where $\mathcal{E}$ is the
set of CIs and RIs that can be formulated in $\mathfrak{L}$ (using symbols
from ${\sf N_{C}}$ and ${\sf N_{R}}$), $\mathcal{L}$ is the set of all
$\mathfrak{L}$ TBoxes, and

$\mu(\mathcal{T})=\\{\alpha\mid\mathcal{T}\models\alpha,\text{ with $\alpha$ a
CI or an RI in }\mathfrak{L}\\}.$

This setting is called _learning from entailments_. In the learning framework
$\mathfrak{F}({\cal E\\!LH}_{rhs})=(\mathcal{E},\mathcal{L},\mu)$ we have that
$\mathcal{T}=\\{A\sqsubseteq\exists r.A\\}\in\mathcal{L}$ and, for all
$n\in\mathbb{N}$, the CI $A\sqsubseteq\exists r^{n}.A$ is in
$\mu(\mathcal{T})$, where $\exists r^{n+1}.A:=\exists r.\exists r^{n}.A$ and
$\exists r^{1}.A:=\exists r.A$.

One could define a more general notion of a learning framework, where the
hypothesis space for the hypothesis of the learner differs from the hypothesis
space that contains the target. Also, the mapping function $\mu$ could be
adapted to represent fuzzy sets of examples. We keep the version introduced
above because it is general enough for our purposes and covers classical
problems in the literature [2, 46]. We now describe in detail the queries that
the learner can pose and how the teacher answers these queries. Consider a
learning framework $\mathfrak{F}=(\mathcal{E},\mathcal{L},\mu)$, and a
learning system $(L,T)$ with a fixed but arbitrary target $t\in\mathcal{L}$ in
the oracle tape.

  * •

A membership query happens whenever $L$ writes an example $e$ in the
communication tape and enters the membership query state. In this case, $T$
resumes the execution and (if the computation terminates) writes ‘yes’ in the
communication tape if $e\in\mu(t)$, otherwise, it writes ‘no’ (assume such
answers can be formulated using symbols from the alphabets of $L$ and $T$).

  * •

An equivalence query happens whenever $L$ writes a hypothesis
$h\in\mathcal{L}$ in the communication tape and enters the equivalence query
state. The teacher $T$ resumes its execution and (if the computation
terminates) writes some $e\in\mu(t)\oplus\mu(h)$ in the communication tape, or
‘yes’ if $\mu(t)=\mu(h)$.

  * •

A sample query happens whenever $L$ enters the sample query state. In this
case, the teacher $T$ resumes its execution and (if the computation
terminates) writes some $(e,\ell_{t}(e))$ in the communication tape, where the
choice of $e\in\mathcal{E}$ is according to a fixed but arbitrary probability
distribution on $\mathcal{E}$ (unknown to the learner) and $\ell_{t}(e)=1$, if
$e\in\mu(t)$, and $0$ otherwise.

We write $(L_{\mathfrak{F}},T_{\mathfrak{F}}(t))$ to indicate that $t$ is in
the oracle tape and queries/answers are as just described for a learning
framework $\mathfrak{F}$ (we may omit the subscript $\mathfrak{F}$ if this is
clear from the context). For some learning frameworks and some types of
queries, it can be assumed that the computation of answers by the teacher
always terminates independently of which $t\in\mathcal{L}$ happens to be in
the oracle tape. One example is when the $\mu$ function encodes the entailment
relation and the entailment problem of the logic represented in $\mathcal{L}$
is decidable (e.g., entailment in ${\cal E\\!LH}$ is decidable in polynomial
time [9]). However, if the entailment problem is undecidable this assumption
cannot be made independently of the content of the oracle tape (e.g.,
entailment in first-order logic).

Even if there is a teacher that always terminates depending on the content of
the oracle tape, naturally, one cannot assume that all of them will terminate.
So we define the following notion. Let $T(t)$ be a teacher with
$t\in\mathcal{L}$ in the oracle tape. We say that $T(t)$ is _terminating for
membership queries_ if for every possible membership query (within a learning
framework) the teacher $T(t)$ always terminates the computation of the answer.
This notion can be easily adapted for other types of queries.

The multiple ways of choosing $e\in\mu(t)\oplus\mu(h)$ in an equivalence query
and an example $e\in\mathcal{E}$ in a sample query is captured by the non-
determinism of $T$ (see Subsection 3.1). For representing sample queries, one
can consider the special case in which the NMTM is a multitape probabilistic
Turing machine [44]. We may write $T_{\mathcal{D}}$ to indicate that, whenever
a sample query is posed by $L$, we have that $T$ chooses an example according
to the (same) probability distribution $\mathcal{D}$, with the events of
drawing examples being mutually independent (see e.g. [43] for more details on
sample queries and [36] for a presentation using this notation).

###  3.3 Learnability and Complexity Classes

We are ready to define the notion of learnability and complexity classes for
learning problems. We write $Y\in(L,T(t))(X)$ if there is a finite computation
of the learning system $(L,T(t))$ with $X$ in the input tape, $t$ in the
oracle tape, and the content written by the learner in the output tape, $L$,
is $Y$. We first define learnability for the exact learning model.

Let $\mathfrak{F}=(\mathcal{E},\mathcal{L},\mu)$ be a learning framework.
Assume that the learner can pose membership and equivalence queries and these
are truthfully replied by the teacher, as described in Subsection 3.2. We say
that $\mathfrak{F}$ is _exactly learnable_ if there is a learner $L$ such
that, for every $t\in\mathcal{L}$, there is a terminating $T(t)$ (for
membership and equivalence queries). Moreover,

  * •

every learning system $(L,T^{\prime}(t))$ with a terminating $T^{\prime}(t)$
halts and every $h\in(L,T^{\prime}(t))(\Sigma_{t})\cap\mathcal{L}$ satisfies
$\mu(h)=\mu(t)$, where $\Sigma_{t}$ is the signature of $t$.

If the number of steps made by $L$ in each path of the computation tree is
always bounded by a polynomial $p(|t|,|e|)$, where $t\in\mathcal{L}$ is the
target and $e\in\mathcal{E}$ is the largest counterexample written so far in
the communication tape by $T^{\prime}(t)$ (in the corresponding path), then
$\mathfrak{F}$ is _exactly learnable in polynomial time_.

We denote by $\textsc{El}({\sf MQ},{\sf EQ})$ and $\textsc{ElP}({\sf MQ},{\sf
EQ})$ the classes of all learning frameworks that are, respectively, exactly
learnable and exactly learnable in polynomial time with membership and
equivalence queries. One can easily adapt this notation to the case in which
the learner is allowed to make an exponential number of steps, denoted
$\textsc{ElExp}({\sf MQ},{\sf EQ})$, or to the case in which the learner can
only pose one type of query. For representing this, we simply drop ${\sf MQ}$
or ${\sf EQ}$ from the class name (e.g., $\textsc{ElP}({\sf EQ})$ is the class
of all learning frameworks that are exactly learnable in polynomial time with
only equivalence queries). One can also consider other types of queries, such
as subset and superset queries [2], or queries that take into account the
history of previous queries [38]. It follows from these definitions that
$\textsc{ElP}({\sf MQ},{\sf EQ})\subseteq\textsc{ElExp}({\sf MQ},{\sf
EQ})\subseteq\textsc{El}({\sf MQ},{\sf EQ})$.

We now define learnability in the PAC model. Let
$\mathfrak{F}=(\mathcal{E},\mathcal{L},\mu)$ be a learning framework. Assume
that the learner can pose sample queries and these are replied by the teacher
as in Subsection 3.2. The goal is to build a hypothesis such that ‘with high
probability there is not much difference between the hypothesis and the
target’. A parameter $\epsilon$ quantifies the error of the hypothesis w.r.t.
the target (how different they are). Another parameter $\delta$ is used to
quantify the confidence of meeting the error requirement (whether this has
high probability). Both parameters are real numbers ranging between $0$ and
$1$. Formally, we say that $\mathfrak{F}$ is _PAC learnable_ if there is a
function $f:(0,1)^{2}\to\mathbb{N}$ and a learner $L$ such that, for every
$(\epsilon,\delta)\in(0,1)^{2}$, every probability distribution $\mathcal{D}$
on $\mathcal{E}$, and every target $t\in\mathcal{L}$, there is a terminating
$T_{\mathcal{D}}(t)$ (for sample queries). Moreover,

  * •

every $(L,T^{\prime}(t)_{\mathcal{D}})$ with a terminating
$T^{\prime}(t)_{\mathcal{D}}$ halts after $L$ poses $m\geq f(\epsilon,\delta)$
samples queries and, with probability at least $(1-\delta)$ (over the choice
of sets of $m$ examples),
$h\in(L,T^{\prime}(t)_{\mathcal{D}})(\Sigma_{t})\cap\mathcal{L}$ satisfies
$\mathcal{D}(\mu(h)\oplus\mu(t))\leq\epsilon$.

If the number of steps made by $L$ in each path of the computation tree is
always bounded by a polynomial function
$\mathit{p}(|t|,|e|,1/\epsilon,1/\delta)$, where $e$ is the largest example
written in the communication tape by $T^{\prime}(t)_{\mathcal{D}}$ (in the
corresponding path), then $\mathfrak{F}$ is _PAC learnable in polynomial
time_. We can easily extend these notions to the case in which the learner can
also pose membership queries (with a terminating teacher for both sample and
membership queries). We denote by Pl and $\textsc{PlP}({\sf SQ})$ the classes
of all learning frameworks that are, respectively, PAC learnable and PAC
learnable in polynomial time with sample queries. Also, we write
$\textsc{PlP}({\sf MQ},{\sf SQ})$ for the case the learner can also pose
membership queries.

######  Remark 2.

There is an important difference between the polynomial bound for the exact
and the PAC learning models. In the exact model, $e$ is the largest
counterexample written _so far_ by the teacher in the path of computation,
while in the PAC model $e$ is the largest example written by the teacher (at
any point of the path). The more strict requirement of the exact model is to
avoid a loophole in the definition [3]. Whenever the hypothesis of the learner
is not equivalent, the teacher needs to provide a _counterexample_. Since this
depends on both the target and the hypothesis, there could be a case in which
the learner spends an exponential amount of time (in the size of the target)
to discover a hypothesis that would force the teacher to provide an
exponential counterexample. Then the learner would have spent a polynomial
amount of time in the size of the largest counterexample but not in the size
of the largest example given _so far_. This requirement is not necessary in
the PAC model because the teacher does not need to provide an example that
depends on the hypothesis of the learner, so there is no way the learner can
‘force’ the teacher to return a large example.

Theorem 3.1 states that positive results for the exact learning model with
only equivalence queries are transferable to the PAC model and this also holds
if both models allow membership queries.

######  Theorem 3.1.

The following holds [2]:

  * •

$\textsc{El}({\sf EQ})\subseteq\textsc{Pl}({\sf SQ})$;

  * •

$\textsc{ElP}({\sf EQ})\subseteq\textsc{PlP}({\sf SQ})$;

  * •

$\textsc{ElP}({\sf MQ},{\sf EQ})\subseteq\textsc{PlP}({\sf MQ},{\sf SQ})$.

The intuition for Theorem 3.1 is that the learner can pose sample queries
instead of equivalence queries. By posing sample queries, the learner can
obtain a set of classified examples, drawn according to a fixed but arbitrary
probability distribution. If the current hypothesis of the learner
misclassifies one of the examples of this set then the learner has found a
counterexample. So it can proceed as if it had posed an equivalence query and
the teacher had returned the counterexample. Otherwise, it is shown in the
proof of the theorem that if the sample is large enough then any hypothesis
consistent with the sample satisfies the criteria for PAC learnability.

For presentation purposes, we have presented only _time_ complexity classes
for the exact and the PAC learning models. One can also consider classes that
capture other ways of measuring the resources used by the learner and/or the
teacher [6]. For example, one can measure the number and size of queries posed
by the learner. In this way, _query_ complexity classes could also be defined
[5, 27].

##  4 Learning DL Ontologies

We provide some and examples and intuitions about the notions presented so far
(Subsection 4.1). Then, in Subsection 4.2, we recall results on learning DL
ontologies in the exact and PAC learning models.

###  4.1 An Example

To illustrate the ideas for learning DL ontologies in the exact and the PAC
learning models, we start by considering the problem of exactly learning an
ontology in a toy language that allows only concept inclusions of the form
$A\sqsubseteq B$ with $A,B\in{\sf N_{C}}$.

$L$$T(\mathcal{T})$Input TapeOracle
Tape$\Sigma_{\mathcal{T}}$$\mathcal{T}$$A\sqsubseteq
B$writesreadsyeswritesreadsCommunication Tape Figure 1: Membership Query in a
Learning System

Consider the learning framework $\mathfrak{F}_{\sf
toy}=(\mathcal{L},\mathcal{E},\mu)$ with $\mathcal{L}$ and $\mathcal{E}$ being
the set of all TBoxes and the set of all CIs that can be formulated in the toy
language, respectively. The $\mu$ function maps TBoxes $\mathcal{T}$ in
$\mathcal{L}$ to CIs in $\mathcal{E}$ entailed by $\mathcal{T}$. Suppose the
target $\mathcal{T}\in\mathcal{L}$ is $\\{A\sqsubseteq B,B\sqsubseteq C\\}$
and let $(L,T(\mathcal{T}))$ be a learning system such that on the input
$\Sigma_{\mathcal{T}}=\\{A,B,C\\}$ (the signature of $\mathcal{T}$) returns
$\mathcal{H}\equiv\mathcal{T}$. In symbols,
$\mathcal{H}\in(L,T(\mathcal{T}))(\Sigma_{\mathcal{T}})$. Clearly, for all
$\mathcal{T}^{\prime}\in\mathcal{L}$, there is a terminating
$T(\mathcal{T}^{\prime})$ for membership, equivalence, and sample queries.

Figure 1 illustrates part of a computation of $(L,T(\mathcal{T}))$ on the
input $\Sigma_{\mathcal{T}}=\\{A,B,C\\}$ where $L$ poses the membership query
$A\sqsubseteq B\in\mu(\mathcal{T})$ and receives ‘yes’ as an answer. A simple
strategy for $L$ is to formulate all CIs within $\Sigma_{\mathcal{T}}$ and
pose membership queries with each such CI, one at a time. The CI is added to
$\mathcal{H}$ if, and only if, the answer is ‘yes’. With this strategy, the
hypothesis $\mathcal{H}$ computed by the learner is $\\{A\sqsubseteq
B,A\sqsubseteq C,B\sqsubseteq C\\}$. At most $|\Sigma_{\mathcal{T}}|^{2}$
membership queries are needed. Thus, $\mathfrak{F}_{\sf
toy}\in\textsc{ElP}({\sf MQ})$.

####  4.1.1 Adding Conjunctions

Now, consider an extension of the toy language that allows conjunctions of
concept names in CIs. We denote the underlying learning framework as
$\mathfrak{F}^{\sqcap}_{\sf toy}$. In this case, the strategy of posing
membership queries for each possible CI formulated within the signature
$\Sigma_{\mathcal{T}}$ of a target $\mathcal{T}$ still terminates (since
$\Sigma_{\mathcal{T}}$ is finite). However, its does not terminate in
polynomial time in $|\Sigma_{\mathcal{T}}|$ because with conjunctions one can
formulate an exponential number of CIs.

In the following, we provide a simple argument showing that there is no
strategy that guarantees polynomial time learnability with only membership
queries. In other words, $\mathfrak{F}^{\sqcap}_{\sf
toy}\not\in\textsc{ElP}({\sf MQ})$.

The main idea is to define a superpolynomial set $S$ of TBoxes in this
extension of the toy language and show that any membership query can
distinguish at most polynomially many elements of $S$. Let
$\Sigma=\\{A_{1},\ldots,A_{n},\overline{A}_{1},\ldots,\overline{A}_{n},M\\}$.
For any sequence ${{\boldsymbol{\sigma}}}=\sigma^{1}\ldots\sigma^{n}$ with
$\sigma^{i}\in\\{A_{i},\overline{A}_{i}\\}$ the expression
${{\boldsymbol{\sigma}}}\sqsubseteq M$ stands for the CI
$(\sigma^{1}\sqcap\ldots\sqcap\sigma^{n}\sqsubseteq M)$. For every such
sequence ${{\boldsymbol{\sigma}}}$ (of which there are $2^{n}$ many), consider
the TBox $\mathcal{T}_{{\boldsymbol{\sigma}}}$ defined as:

$\begin{array}[]{rcl}\mathcal{T}_{{\boldsymbol{\sigma}}}&=&\left\\{{{\boldsymbol{\sigma}}}\sqsubseteq
M\right\\}\cup\mathcal{T}_{0}\;\text{ with }\\\\[2.84526pt]
\mathcal{T}_{0}&=&\left\\{A_{i}\sqcap\overline{A}_{i}\sqsubseteq M\mid 1\leq
i\leq n\right\\}\end{array}$

The CI ${{\boldsymbol{\sigma}}}\sqsubseteq M$ represents a unique binary
sequence for each $\mathcal{T}_{{\boldsymbol{\sigma}}}$, ‘marked’ by the
concept name $M$. The CIs in $\mathcal{T}_{0}$ are shared by all
$\mathcal{T}_{{\boldsymbol{\sigma}}}$ in $S$.

######  Lemma 1.

For any CI $\alpha$ in the extended toy language over $\Sigma$ either:

  * •

for every $\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$, we have
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$; or

  * •

$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$, for at most one
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$.

###### Proof.

Suppose there is $\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$ such that
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$ (otherwise we are done).
Assume the CI $\alpha$ is $C\sqsubseteq D$. If $D$ is $M$ then either $\alpha$
is a tautology or there is no $\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$ such
that $\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$. In both cases, we
have that $\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$ for at most one
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$. Then, we can assume that $D$ is
$M$. Regarding $C$ (the concept on the left side of the CI $\alpha$), we make
a case distinction:

  * •

there is $1\leq i\leq n$ such that $A_{i},\overline{A}_{i}$ are conjuncts in
$C$. In this case, by definition of $\mathcal{T}_{0}$, we have that
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$, for every
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$.

  * •

there is no $1\leq i\leq n$ such that $A_{i},\overline{A}_{i}$ are conjuncts
in $C$. This means that $\mathcal{T}_{0}\not\models\alpha$. If $\alpha$ is of
the form ${{\boldsymbol{\sigma}}}\sqsubseteq M$ then there is exactly one
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$ such that
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$. Otherwise, there is no
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$ such that
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$. So,
$\mathcal{T}_{{\boldsymbol{\sigma}}}\models\alpha$, for at most one
$\mathcal{T}_{{\boldsymbol{\sigma}}}\in S$.

∎

Since any membership query can eliminate only polynomially many elements from
$S$ (in our case at most one), the learner cannot distinguish between the
remaining elements from our initial superpolynomial set $S$ in polynomial
time. Thus, $\mathfrak{F}^{\sqcap}_{\sf toy}\not\in\textsc{ElP}({\sf MQ})$.

This language can be easily translated into propositional Horn. It is known
that propositional Horn expressions are exactly learnable in polynomial time
if equivalence queries are also allowed [4, 20]. That is,
$\mathfrak{F}^{\sqcap}_{\sf toy}\in\textsc{ElP}({\sf MQ},{\sf EQ})$.

####  4.1.2 Adding Existentials

We discuss here a further extension the toy language that also allows
existential quantification. This language coincides with ${\cal E\\!L}$,
defined in Section 2. Our first observation is that in ${\cal E\\!L}$ there is
an infinite number of CIs that can be formulated with a finite signature
$\Sigma_{\mathcal{T}}$ of a target $\mathcal{T}$. This happens because
existential quantifiers can be nested in concept expressions. Moreover, due to
cyclic references between concepts in an ${\cal E\\!L}$ TBox, an infinite
number of CIs can be entailed by a (finite) TBox (see Remark 1). This means
that the strategy of posing membership queries for each possible CI formulated
with the signature $\Sigma_{\mathcal{T}}$ of a target $\mathcal{T}$ does not
terminate in this case. If equivalence queries are allowed then one can still
enumerate all TBoxes of size $n$ that can be formulated with
$\Sigma_{\mathcal{T}}$ (up to logical equivalence) and ask equivalence queries
with such TBoxes, one by one. Then one can increase $n$ until it reaches the
size of $\mathcal{T}$ (which is finite). This strategy is guaranteed to
terminate, although not in polynomial time. In the next subsection, we discuss
further results for ${\cal E\\!L}$ extended with role inclusions (that is,
${\cal E\\!LH}$) and its fragments ${\cal E\\!LH}_{lhs}$ and ${\cal
E\\!LH}_{rhs}$, introduced in Section 2.

###  4.2 Complexity Results

We now recall from the literature polynomial time complexity results for
learning DL ontologies in the exact and the PAC learning models. Figure 2
illustrates some of these results (some results and complexity classes have
been omitted to simplify the presentation). Dashed lines are for the classes
associated with the PAC learning model. In what follows, we give an overview
of the complexity results and provide additional explanations for the
complexity classes.

Figure 2: Learning Frameworks and Complexity Classes

Konev et al. (2018) have shown that ${\cal E\\!LH}$ (in fact already ${\cal
E\\!L}$) TBoxes are not exactly learnable from entailments in polynomial time
while ${\cal E\\!LH}_{lhs}$ and ${\cal E\\!LH}_{rhs}$ are polynomially
learnable [27]. In symbols, $\mathfrak{F}({\cal
E\\!LH})\not\in\textsc{ElP}({\sf MQ},{\sf EQ})$ but $\mathfrak{F}({\cal
E\\!LH}_{lhs}),\mathfrak{F}({\cal E\\!LH}_{rhs})\in\textsc{ElP}({\sf MQ},{\sf
EQ})$. Similar results also hold for a variant of this problem setting where
the examples are pairs of the form $(\mathcal{A},q)$ (instead of being CIs and
RIs), where $\mathcal{A}$ is an ABox and $q$ is an (${\cal E\\!LH}$) IQ [28].
In this setting, $(\mathcal{A},q)$ is a positive example for $\mathcal{T}$ iff
$(\mathcal{T},\mathcal{A})\models q$. We denote these learning frameworks with
$\mathfrak{F}(\mathfrak{L},IQ)$, where $\mathfrak{L}$ is the DL. In both
problem settings, if the return of an equivalence query is ‘yes’ then this
means that the hypothesis of the learner and the target are logically
equivalent. Recently, it has been shown that if the ABox is fixed and one only
aims at preserving IQ results w.r.t. the fixed ABox (not logical equivalence
between the hypothesis and the target) then there is a polynomial time
algorithm for ${\cal E\\!LH}$ terminologies [37]. We denote this learning
framework by $\mathfrak{F}({\cal E\\!LH},\mathcal{A},IQ)$ where $\mathcal{A}$
is the fixed ABox. The intuition for why the problem is ‘easier’ in this case
is because, since the ABox is fixed, the possible counterexamples the teacher
can give are constrained. The fixed ABox setting avoids the difficult scenario
described in the hardness proof for the learning framework $\mathfrak{F}({\cal
E\\!LH},IQ)$ [28, Page 29 of the full version], where the teacher can give
counterexamples of the form $(\mathcal{A}_{{{\boldsymbol{\sigma}}}},A(a))$,
with ${{\boldsymbol{\sigma}}}=\sigma^{1},\ldots,\sigma^{n}$, for
$\sigma^{i}\in\\{A_{i},\overline{A_{i}}\\}$, and
$\mathcal{A}_{{{\boldsymbol{\sigma}}}}$ an ABox of the form
$\\{\sigma^{1}(a),\ldots,\sigma^{n}(a)\\}$.

By Theorem 3.1, positive results in the exact learning model are transferable
to the PAC model extended with membership queries. We point out that the
complexity class $\textsc{PlP}({\sf SQ})$ is _not_ contained in
$\textsc{ElP}({\sf MQ},{\sf EQ})$. This has been discovered by Blum in 1994
[14]. He constructed an artificial counterexample to prove the result and the
argument relies on cryptographic assumptions. Another (artificial)
counterexample appears in the work by Ozaki et al. (2020) [37]. The argument
in this case does not rely on cryptographic assumptions. Apart from these
carefully constructed learning frameworks, in many cases, learning frameworks
in $\textsc{PlP}({\sf SQ})$ are also in $\textsc{ElP}({\sf MQ},{\sf EQ})$.

We now explain why $\mathfrak{F}({\cal E\\!LH})$ and $\mathfrak{F}({\cal
E\\!LH},IQ)$ appear in $\textsc{ElExp}({\sf MQ},{\sf EQ})$. In fact, they are
already in $\textsc{ElExp}({\sf EQ})$. The reason is that, as explained at the
end of Subsection 4.1, since the learning system receives the (finite)
signature $\Sigma_{\mathcal{T}}$ of the target $\mathcal{T}$ as input, it can
enumerate all TBoxes (up to logical equivalence) of a certain size and ask
whether any of them is equivalent to $\mathcal{T}$, one by one, increasing
this size until a TBox equivalent to $\mathcal{T}$ is found. This naive
procedure clearly requires an exponential number of steps in the size of
$\mathcal{T}$. The same holds for other DL languages more expressive than
${\cal E\\!LH}$, as long as TBoxes can also be enumerated in this way. An
exponential (but non-trivial) algorithm for ${\cal E\\!L}$ terminologies and
its implementation is provided by Duarte et al. (2018) [17]

It remains to explain the $\mathfrak{F}(\text{DL-Lite}_{\mathcal{R}})$ case.
$\text{DL-Lite}_{\mathcal{R}}$ is a member of a well-known family of DLs [8].
What we would like to explain is that, for some ontology languages, such as
$\text{DL-Lite}_{\mathcal{R}}$, the number of RIs and CIs that can be
formulated within the (finite) signature $\Sigma_{\mathcal{T}}$ of a target
$\mathcal{T}$ is polynomial in the size of $\Sigma_{\mathcal{T}}$. Since
$\Sigma_{\mathcal{T}}$ is given as input to the learning system, this means
that the learner can identify the target with only membership queries (see toy
example in Subsection 4.1), and moreover, in polynomial time in the size of
$\Sigma_{\mathcal{T}}$. Therefore, $\mathfrak{F}(\text{DL-
Lite}_{\mathcal{R}})$ belongs to $\textsc{ElP}({\sf MQ})$. Learning an
equivalent $\text{DL-Lite}_{\mathcal{R}}$ TBox with only equivalence queries
is also easy. This happens because there are only polynomially many
counterexamples that can be given. The learner can start by posing an
equivalence query with an empty hypothesis. Then, the teacher is obliged to
return a positive counterexample (unless the target is equivalent to the empty
hypothesis and we are done). All the learner needs to do is to add this
positive counterexample to its hypothesis and then proceed by posing another
equivalence query. After polynomially many equivalence queries, the learner
will terminate with an equivalent hypothesis. So $\mathfrak{F}(\text{DL-
Lite}_{\mathcal{R}})\in\textsc{ElP}({\sf EQ})$ also holds.

##  5 Related Work

We now highlight some other approaches from the literature for learning DL
ontologies, when the focus is on finding how terms of an ontology should
relate to each other using the expressivity of the ontology language at hand.
These approaches are mainly based on association rule mining, formal concept
analysis, inductive logic programming, and neural networks [36].

Formal concept analysis [23] has been applied to mine ${\cal E\\!L}$ CIs [15]
(see also [41, 12, 11]). In this setting, a learner receives a finite
intepretation $\mathcal{I}$ as input and attempts to build a finite ontology
$\mathcal{T}$ such that, for all ${\cal E\\!L}$ CIs formulated in a finite
signature, $\mathcal{T}\models C\sqsubseteq D$ if, and only if,
$\mathcal{I}\models C\sqsubseteq D$. This ontology, called _base_ , should
also satisfy certain minimality conditions. It is known that, given a finite
interpretation $\mathcal{I}$, a finite base (expressed within a finite
signature) always exists for the ${\cal E\\!L}$ ontology language. However,
this may not be the case for other ontology languages. The main difficulty in
applying formal concept analysis for building ontologies is that, as
originally proposed, it cannot build CIs one may expect to hold when the data
is (even just slightly) incorrect. If a certain CI holds in practice but there
is an element that violates it in the interpretation then the CI will not be
included in the base. One could argue that this method is then useful to find
such errors but the application for mining CIs has this issue.

When there is a certain threshold for tolerating errors, then association rule
mining offers an interesting solution. This method is based on the measures of
support and confidence [1]. The support is a metric for measuring statistical
significance, while confidence measures the ‘strength’ of a rule, in this
case, expressed as a CI in an ontology language. Many authors have already
employed this method for building DL ontologies [49, 19, 48] (see also [42])
and for finding relational rules in knowledge graphs [22]. The usual approach
is to fix the depth of the CIs in order to restrict the search space.

There is a vast literature on algorithms and techniques for learning DL
_concepts_ based on inductive logic programming [21, 18, 26, 29, 31, 32,
30](see [34] for learning logical rules also based in inductive logic
programming). One of the most well known tools for supporting the construction
of DL concepts is the DL-Learner [29]. In this approach, the learner receives
as input examples of assertions classified as positive and negative and the
goal is to construct a DL concept expression that ‘fits’ the classified
examples.

Deep learning has also been applied for learning DL ontologies [39]. In the
mentioned work, the authors use definitional sentences labelled with their DL
translation to train a recurrent neural network (see also [35] for more work
on definitional sentences in a DL context). It is an interesting approach that
deals extremely well with data variability. The main difficulties pointed out
by the authors are how to find large amounts of classified examples to train
the neural network (the authors have trained it using synthetic data) and how
to capture the semantics of the ontology. The neural network could capture the
syntax, for example, map the word ‘and’ to the logical operator ‘$\sqcap$’.
However, as reported by the authors, the method does not really capture the
semantics of the sentences and how they relate to each other. There is an
extensive literature on learning assertions using neural networks [16, 53] but
not many works on building DL ontologies with complex concept expressions.

##  6 Conclusion

We have presented a formalisation of the exact and the PAC learning models and
defined learning complexity classes. This opens the possibility of
investigating other questions such as the problem of deciding whether a
learning framework is PAC or exactly learnable. Some authors have already
investigated this problem for the PAC model, with a different formalisation of
PAC learnability [47].

An interesting application of exact learning algorithms is to verify neural
networks, as in the already mentioned works by Weiss et al. [52, 51]. These
works are based on Angluin’s exact learning algorithm for learning regular
languages represented by deterministic finite automata with membership and
equivalence queries (an abstraction of the automata is used to find
counterexamples). One of the goals of this strategy is to find _adversarial
inputs_ : examples neither present in the training nor in the test set which
were misclassified by a neural network [52, 51]. It would be interesting to
investigate whether algorithms for exactly learning ontologies can also be
applied to verify if a neural network captures certain rules.

## References

  * [1] Agrawal, R., Imieliński, T., Swami, A.: Mining association rules between sets of items in large databases.  Special Interest Group on Management Of Data SIGMOD 22(2), 207–216 (1993)
  * [2] Angluin, D.: Queries and concept learning.  Machine Learning 2(4), 319–342 (1988)
  * [3] Angluin, D.: Negative results for equivalence queries.  Machine Learning 5, 121–150 (1990)
  * [4] Angluin, D., Frazier, M., Pitt, L.: Learning conjunctions of horn clauses.  Mach. Learn. 9, 147–164 (1992)
  * [5] Arias, M.: Exact learning of first-order expressions from queries.  Ph.D. thesis, Citeseer (2004)
  * [6] Arias, M., Khardon, R.: Complexity parameters for first order classes.  Machine Learning 64(1-3), 121–144 (2006)
  * [7] Arias, M., Khardon, R., Maloberti, J.: Learning horn expressions with LOGAN-H.  Journal of Machine Learning Research 8, 549–587 (2007)
  * [8] Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The dl-lite family and relations.  CoRR abs/1401.3487 (2014)
  * [9] Baader, F., Brandt, S., Lutz, C.: Pushing the $\mathcal{EL}$ envelope.  In: L. Kaelbling, A. Saffiotti (eds.) Proc. 19th Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 364–369. Professional Book Center (2005)
  * [10] Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications, second edn.  Cambridge University Press (2007)
  * [11] Baader, F., Distel, F.: Exploring finite models in the description logic.  In: ICFCA, pp. 146–161 (2009)
  * [12] Baader, F., Ganter, B., Sertkaya, B., Sattler, U.: Completing description logic knowledge bases using formal concept analysis.  In: IJCAI, vol. 7, pp. 230–235 (2007)
  * [13] Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic.  Cambridge University Press (2017)
  * [14] Blum, A.L.: Separating distribution-free and mistake-bound learning models over the boolean domain.  SIAM J. Comput. 23(5) (1994)
  * [15] Borchmann, D., Distel, F.: Mining of $\mathcal{EL}$-GCIs.  In: The 11th IEEE International Conference on Data Mining Workshops. Vancouver, Canada (2011)
  * [16] Bordes, A., Usunier, N., García-Durán, A., Weston, J., Yakhnenko, O.: Translating embeddings for modeling multi-relational data.  In: Advances in Neural Information Processing Systems. NeurIPS, pp. 2787–2795 (2013)
  * [17] Duarte, M.R.C., Konev, B., Ozaki, A.: Exactlearner: A tool for exact learning of EL ontologies.  In: KR, pp. 409–414 (2018)
  * [18] Fanizzi, N., d’Amato, C., Esposito, F.: DL-FOIL concept learning in description logics.  In: ILP, pp. 107–121 (2008)
  * [19] Fleischhacker, D., Völker, J., Stuckenschmidt, H.: Mining RDF data for property axioms.  In: On the Move to Meaningful Internet Systems: OTM 2012, pp. 718–735. Springer (2012)
  * [20] Frazier, M., Pitt, L.: Learning from entailment: An application to propositional Horn sentences.  In: International Conference on Machine Learning, ICML, pp. 120–127 (1993)
  * [21] Funk, M., Jung, J.C., Lutz, C., Pulcini, H., Wolter, F.: Learning description logic concepts: When can positive and negative examples be separated?  In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 1682–1688 (2019)
  * [22] Galárraga, L., Teflioudi, C., Hose, K., Suchanek, F.M.: Fast rule mining in ontological knowledge bases with AMIE+.  VLDB J. 24(6), 707–730 (2015)
  * [23] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.  Springer (1997)
  * [24] Granmo, O.: The tsetlin machine - A game theoretic bandit driven approach to optimal pattern recognition with propositional logic.  CoRR abs/1804.01508 (2018)
  * [25] Hermo, M., Ozaki, A.: Exact learning: On the boundary between horn and CNF.  TOCT 12(1), 4:1–4:25 (2020)
  * [26] Iannone, L., Palmisano, I., Fanizzi, N.: An algorithm based on counterfactuals for concept learning in the semantic web.  Appl. Intell. 26, 139–159 (2007)
  * [27] Konev, B., Lutz, C., Ozaki, A., Wolter, F.: Exact learning of lightweight description logic ontologies.  JMLR 18(201), 1–63 (2018)
  * [28] Konev, B., Ozaki, A., Wolter, F.: A model for learning description logic ontologies based on exact learning.  In: AAAI, pp. 1008–1015 (2016)
  * [29] Lehmann, J.: DL-learner: learning concepts in description logics.  JMLR 10, 2639–2642 (2009)
  * [30] Lehmann, J.: Learning OWL class expressions, vol. 6.  IOS Press (2010)
  * [31] Lehmann, J., Haase, C.: Ideal downward refinement in the EL description logic.  In: ILP, pp. 73–87 (2009)
  * [32] Lehmann, J., Hitzler, P.: Concept learning in description logics using refinement operators.  Machine Learning 78(1-2), 203–250 (2010)
  * [33] Lehmann, J., Völker, J.: Perspectives on Ontology Learning, vol. 18.  IOS Press (2014)
  * [34] Lisi, F.A.: Al-quin: An onto-relational learning system for semantic web mining.  Int. J. Semantic Web Inf. Syst. 7, 1–22 (2011)
  * [35] Ma, Y., Distel, F.: Learning formal definitions for Snomed CT from text.  In: AIME, pp. 73–77 (2013)
  * [36] Ozaki, A.: Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?  KI pp. 1610–1987 (2020)
  * [37] Ozaki, A., Persia, C., Mazzullo, A.: Learning query inseparable ELH ontologies.  CoRR abs/1911.07229 (2019).  To appear in the proceedings of AAAI 2020.
  * [38] Ozaki, A., Troquard, N.: Learning ontologies with epistemic reasoning: The EL case.  In: F. Calimeri, N. Leone, M. Manna (eds.) JELIA, pp. 418–433 (2019)
  * [39] Petrucci, G., Ghidini, C., Rospocher, M.: Ontology learning in the deep.  In: EKAW, pp. 480–495 (2016)
  * [40] Pitt, L., Valiant, L.G.: Computational limitations on learning from examples.  J. ACM 35(4), 965–984 (1988)
  * [41] Rudolph, S.: Exploring relational structures via FLE.  In: ICCS. Springer (2004)
  * [42] Sazonau, V., Sattler, U.: Mining hypotheses from data in OWL: advanced evaluation and complete construction.  In: ISWC, pp. 577–593 (2017)
  * [43] Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press (2014)
  * [44] Sipser, M.: Introduction to the Theory of Computation, international edition of second edn.  Thomson Course Technology (2005)
  * [45] Spackman, K.A., Campbell, K.E., Côté, R.A.: SNOMED RT: A reference terminology for health care.  In: D.R. Masys (ed.) Proc. 1997 AMIA Annual Fall Symposium, J. of the American Medial Informatics Association, Symposium Supplement, pp. 640–644. Hanley & Belfus (1997)
  * [46] Valiant, L.G.: A theory of the learnable.  Commun. ACM 27(11), 1134–1142 (1984)
  * [47] Venkatraman, S., Balasubramanian, S., Sarma, R.R.: Pac-learning is undecidable.  CoRR abs/1808.06324 (2018)
  * [48] Völker, J., Fleischhacker, D., Stuckenschmidt, H.: Automatic acquisition of class disjointness.  Journal of Web Semantics 35, 124–139 (2015)
  * [49] Völker, J., Niepert, M.: Statistical schema induction.  In: The Semantic Web: Research and Applications, pp. 124–138. Springer (2011)
  * [50] Watanabe, O.: A formal study of learning via queries.  In: ICALP, pp. 139–152 (1990)
  * [51] Weiss, G., Goldberg, Y., Yahav, E.: Extracting automata from recurrent neural networks using queries and counterexamples.  In: ICML, pp. 5244–5253 (2018)
  * [52] Weiss, G., Goldberg, Y., Yahav, E.: Learning deterministic weighted automata with queries and counterexamples.  In: H.M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E.B. Fox, R. Garnett (eds.) NeurIPS, pp. 8558–8569 (2019)
  * [53] Yang, B., Yih, W., He, X., Gao, J., Deng, L.: Embedding entities and relations for learning and inference in knowledge bases.  In: ICLR (2015)