11institutetext:  University of Bergen
Department of Informatics
<EMAIL_ADDRESS>
# Learning Description Logic Ontologies

Five Approaches. Where Do They Stand?

Ana Ozaki

###### Abstract

The quest for acquiring a formal representation of the knowledge of a domain
of interest has attracted researchers with various backgrounds into a diverse
field called ontology learning. We highlight classical machine learning and
data mining approaches that have been proposed for (semi-)automating the
creation of description logic (DL) ontologies. These are based on association
rule mining, formal concept analysis, inductive logic programming,
computational learning theory, and neural networks. We provide an overview of
each approach and how it has been adapted for dealing with DL ontologies.
Finally, we discuss the benefits and limitations of each of them for learning
DL ontologies.

##  1 Introduction

The quest for acquiring a formal representation of the knowledge of a domain
of interest has attracted researchers with various backgrounds and both
practical and theoretical inquires into a diverse field called _ontology
learning_ [33, 30]. In this work, we focus on approaches for building
description logic (DL) ontologies assuming that the vocabulary and the
language of the ontology to be created are known. The main goal is to find how
the symbols of the vocabulary should be related, using the logical constructs
available in the ontology language. Desirable goals of an ontology learning
process include:

  1. 1.

the creation of ontologies which are _interpretable_ ; expressions should not
be overly complex, redundancies should be avoided;

  2. 2.

the support for learnability of DL expressions formulated in _rich ontology
languages_ ;

  3. 3.

_efficient_ algorithms for creating ontologies, requiring a _small amount of
time and training data_ ;

  4. 4.

_limited or no human intervention_ requirement;

  5. 5.

the support for learning in _unsupervised_ settings;

  6. 6.

handling of _inconsistencies and noise_.

Other properties such as explainability and trustability may also be relevant
for some approaches. Moreover, once the ontology has been created, it needs to
be checked, be maintained, and evolve. This means that other reasoning tasks
should also be feasible.

Nearly 20 years after the term “ontology learning” was coined by Maedche and
Staab [33], it is not a surprise that no approach could accomplish such
ambitious and conflicting goals. However, different approaches have addressed
some of these goals. We highlight five approaches coming from machine learning
and data mining which have been proposed for (semi-)automating the creation of
DL ontologies. These are based on association rule mining (ARM) [1], formal
concept analysis (FCA) [19], inductive logic programming (ILP) [35],
computational learning theory (CLT) [46], and neural networks (NNs) [34].

The adaptations of the approaches to the problem of learning DL ontologies
often come with the same benefits and limitations as the original approach. To
show this effect, for each of the five approaches, we start by presenting the
original proposal and then explain how it has been adapted for dealing with DL
ontologies. Before presenting them, we introduce some basic notions.

##  2 Definitions

Here we present the syntax and semantics of DLs and basic definitions useful
to formalise learning problems.

###  2.1 Description Logic Ontologies

We introduce ${\cal ALC}$ [3], a prototypical DL which features basic
ingredients found in many DL languages. Let ${\sf N_{C}}$ and ${\sf N_{R}}$ be
countably infinite and disjoint sets of _concept_ and _role_ names. An ${\cal
ALC}$ ontology (or _TBox_) is a finite set of expressions of the form
$C\sqsubseteq D$, called _concept inclusions_ (CIs), where $C,D$ are ${\cal
ALC}$ _concept expressions_ built according to the grammar rule

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

with $A\in{\sf N_{C}}$ and $r\in{\sf N_{R}}$. An ${\cal E\\!\\!\>L}$ concept
expression is an ${\cal ALC}$ concept expression without any occurrence of the
negation symbol ($\neg$). An ${\cal E\\!\\!\>L}$ TBox is a finite set of CIs
$C\sqsubseteq D$, with $C,D$ being ${\cal E\\!\\!\>L}$ concept expressions.

The semantics of ${\cal ALC}$ (and of the ${\cal E\\!\\!\>L}$ fragment) 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}}$ and each $r\in{\sf N_{R}}$ to a subset
$r^{\mathcal{I}}$ of $\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$. The
function $\cdot^{\mathcal{I}}$ extends to arbitrary ${\cal ALC}$ concept
expressions as follows:

$\displaystyle(\neg C)^{\mathcal{I}}$
$\displaystyle:={}\Delta^{\mathcal{I}}\setminus C^{\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}}\\}$

An interpretation $\mathcal{I}$ _satisfies_ a CI $C\sqsubseteq D$, in symbols
$\mathcal{I}\models C\sqsubseteq D$, iff $C^{\mathcal{I}}\subseteq
D^{\mathcal{I}}$. It satisfies a TBox $\mathcal{T}$, in symbols
$\mathcal{I}\models\mathcal{T}$, iff $\mathcal{I}$ satisfies all CIs in
$\mathcal{T}$. A TBox $\mathcal{T}$ _entails_ a CI $\alpha$, in symbols
$\mathcal{T}\models\alpha$, iff all interpretations satisfying $\mathcal{T}$
satisfy $\alpha$.

###  2.2 Learning Frameworks

By _learning_ we mean the process of acquiring some desired kind of knowledge
represented in a well-defined and machine-processable form. _Examples_ are
pieces of information that characterise such knowledge, given as part of the
input of a learning process. We formalise these relationships as follows.

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 representations111In the Machine Learning
literature, a _concept_ is often defined as a set of examples and a concept
representation is a way of representing such set. This differs from the notion
of a concept in the DL literature and a formal concept in FCA., called
_hypothesis space_ , and $\mu$ is a function that maps each element of
$\mathcal{L}$ to a set of (possibly classified) examples in $\mathcal{E}$. If
the classification is into $\\{1,0\\}$, representing positive and negative
labels, then $\mu$ simply associates elements $l$ of $\mathcal{L}$ to all
examples labelled with $1$ by $l$. Each element of $\mathcal{L}$ is called a
_hypothesis_. The _target representation_ (here simply called _target_) is a
fixed but arbitrary element of $\mathcal{L}$, representing the kind of
knowledge that is aimed for in the learning process.

###### Example 1

To formalise the problem of learning DL ontologies from entailments, one can
define the learning framework for a given DL $L$ as
$(\mathcal{E},\mathcal{L},\mu)$ where $\mathcal{E}$ is the set of all CIs
$C\sqsubseteq D$ with $C,D$ being $L$ concept expressions; $\mathcal{L}$ is
the set of all $L$ TBoxes; and $\mu$ is a function that maps every $L$ TBox
$\mathcal{T}$ to the set $\\{C\sqsubseteq
D\in\mathcal{E}\mid\mathcal{T}\models C\sqsubseteq D\\}$. In this case, we
consider that $C\sqsubseteq D$ is labelled with $1$ by $\mathcal{T}$ iff
$\mathcal{T}\models C\sqsubseteq D$.

In the next five sections, we highlight machine learning and data mining
approaches which have been proposed for (semi-)automating the creation of DL
ontologies. As mentioned, for each approach, we first describe the original
motivation and application. Then we describe how it has been adapted for
dealing with DL ontologies.

##  3 Association Rule Mining

###  3.1 Original Approach

Association rule mining (ARM) is a data mining method frequently used to
discover patterns, correlations, or causal structures in transaction
databases, relational databases, and other information repositories. We
provide basic notions, as it was initially proposed [1].

######  Definition 1 (Association Rule)

Given a set $I=\\{i_{1},i_{2},\ldots,i_{n}\\}$ of _items_ , and a set
$\mathbb{D}=\\{t_{1},t_{2},\ldots,t_{m}\\}$ of _transactions_ (called
_transaction database_) with each $t_{i}\subseteq I$, an _association rule_ is
an expression of the form $A\Rightarrow B$ where $A,B$ are sets of items.

The task of mining rules is divided into two parts: (i) mining sets of items
which are frequent in the database, and, (ii) generating association rules
based on frequent sets of items. To measure the frequency of a set $X$ of
items in a transaction database $\mathbb{D}$, one uses a measure called
_support_ , defined as:

${\sf supp}_{\mathbb{D}}(X)=\frac{|\\{t_{i}\in\mathbb{D}:X\subseteq
t_{i}\\}|}{|\mathbb{D}|}$

If a set $X$ of items has support larger than a given threshold then it is
used in the search of association rules, which have the form $A\Rightarrow B$,
with $X=A\cup B$. To decide whether an implication $A\Rightarrow B$ should be
in the output of a solution to the problem, a confidence measure is used. The
confidence of an association rule $A\Rightarrow B$ w.r.t. a transaction
database $\mathbb{D}$ is defined as:

${\sf conf}_{\mathbb{D}}(A\Rightarrow B)=\frac{{\sf supp}_{\mathbb{D}}(A\cup
B)}{{\sf supp}_{\mathbb{D}}(A)}$

Essentially, support measures statistical significance, while confidence
measures the ‘strength’ of a rule [1].

We parameterize the ARM learning framework $\mathfrak{F}_{\sf ARM}$ with the
confidence threshold $\delta\in[0,1]\subset\mathbb{R}$. $\mathfrak{F}_{\sf
ARM}(\delta)$ is $(\mathcal{E},\mathcal{L},\mu)$ where $\mathcal{E}$ is the
set of all database transactions $\mathbb{D}$; $\mathcal{L}$ is the set of all
sets $\mathcal{S}$ of association rules; and

$\mu(\mathcal{S})=\\{\mathbb{D}\in\mathcal{E}\mid\forall\alpha\in\mathcal{S}\text{
we have that }{\sf conf}_{\mathbb{D}}(\alpha)\geq\delta\\}.$

ARM Problem: Given $\delta$ and $\mathbb{D}$, let $\mathfrak{F}_{\sf
ARM}(\delta)$ be $(\mathcal{E},\mathcal{L},\mu)$. Find
$\mathcal{S}\in\mathcal{L}$ with $\mathbb{D}\in\mu(\mathcal{S})$.

###### Example 2

Consider the transaction database in Table 1. It contains $5$ transactions.
For example, the first transaction, $t_{1}$, has ${\sf Product1},{\sf
Product3}$ and ${\sf Product4}$ (first row of Table 1). Assume that the
support and confidence thresholds are resp. $60\%$ and $70\%$. ARM gives the
rules: $\\{{\sf Product3},{\sf Product4}\\}\Rightarrow\\{{\sf Product1}\\}$
(conf. $75\%$) and $\\{{\sf Product2}\\}\Rightarrow\\{{\sf Product1}\\}$
(conf. $100\%$), among others.

Table 1: Transaction Database  ID | Product 1 | Product 2 | Product 3 | Product 4
---|---|---|---|---
1 | ✓ |  | ✓ | ✓
2 |  |  | ✓ | ✓
3 | ✓ | ✓ | ✓ | ✓
4 | ✓ | ✓ | ✓ |
5 | ✓ | ✓ | ✓ | ✓

###  3.2 Building DL ontologies

An immediate way of adapting the ARM approach to deal with DL ontologies is to
make the correspondence between a _finite_ interpretation and a transaction
database. Assume $\mathcal{I}$ is a finite interpretation then the notions of
support and confidence can be adapted to:

${\sf
supp}_{\mathcal{I}}(C)=\frac{|C^{\mathcal{I}}|}{|\Delta^{\mathcal{I}}|}\quad\quad\
{\sf conf}_{\mathcal{I}}(C\sqsubseteq D)=\frac{{\sf
supp}_{\mathcal{I}}(C\sqcap D)}{{\sf supp}_{\mathcal{I}}(C)}$

The problem of giving logical meaning to association rules is that it may
happen that $C\sqsubseteq D$ and $D\sqsubseteq E$ have confidence values above
a certain threshold while $C\sqsubseteq E$ _does not_ have a confidence value
that is above the threshold, even though it is a logical consequence of the
first two CIs [7]. This problem also occurs in the original ARM approach if
the association rules are interpreted as Horn rules in propositional logic. To
see this effect, consider Example 2. We have that both $\\{{\sf Product3},{\sf
Product4}\\}\Rightarrow\\{{\sf Product1}\\}$ and $\\{{\sf
Product1}\\}\Rightarrow\\{{\sf Product2}\\}$ have confidence $75\%$ but the
confidence of $\\{{\sf Product3},{\sf Product4}\\}\Rightarrow\\{{\sf
Product2}\\}$ is only $50\%$. Another difficulty in this adaptation for
dealing with DLs is that the number of CIs with confidence value above a given
threshold may be infinite (consider e.g. ${\cal E\\!\\!\>L}$ CIs in an
interpretation with a directed cycle) and a finite set which implies such CIs
may not exist.

The learning framework here is parameterized with a DL $L$ and a confidence
threshold $\delta\in[0,1]\subset\mathbb{R}$. Then, $\mathfrak{F}^{\sf DL}_{\sf
ARM}(L,\delta)$ is $(\mathcal{E},\mathcal{L},\mu)$ with $\mathcal{E}$ the set
of all finite interpretations $\mathcal{I}$; $\mathcal{L}$ the set of all $L$
TBoxes $\mathcal{T}$; and

$\mu(\mathcal{T})=\\{\mathcal{I}\in\mathcal{E}\mid\forall\alpha\in\mathcal{T}\text{
we have that }{\sf conf}_{\mathcal{I}}(\alpha)\geq\delta\\}.$

ARM+DL Problem: Given $\mathcal{I}$, $L$, and $\delta$, let $\mathfrak{F}^{\sf
DL}_{\sf ARM}(L,\delta)$ be $(\mathcal{E},\mathcal{L},\mu)$. Find
$\mathcal{T}\in\mathcal{L}$ with $\mathcal{I}\in\mu(\mathcal{T})$.

ARM is an effective approach for extracting CIs with concept expressions of
fixed length from RDF datasets. Using this technique, e.g., ${\sf
DeputyDirector}\sqsubseteq{\sf CivilServicePost}$ and ${\sf
MinisterialDepartment}\sqsubseteq{\sf Department}$ were extracted from
data.gov.uk [48, 14, 47] (see also [43] for expressive DLs with fixed length).

More recently, ARM has been applied to mine relational rules in knowledge
graphs [16]. This approach, born in the field of data mining, is relevant for
the task of building DL ontologies, as it can effectively find interesting
relationships between concept and role names. However, it lacks support for
mining CIs with existential quantifiers on the right-hand side [45].

##  4 Formal Concept Analysis

###  4.1 Original Approach

Formal Concept Analysis (FCA) is a mathematical method of data analysis which
describes the relationship between objects and their attributes [19] (see also
[18] for an introduction to this field). In FCA, data is represented by formal
contexts describing the relationship between finite sets of objects and
attributes. The notion of a transaction database (Definition 1) is similar to
the notion of a formal context (Definition 2).

######  Definition 2 (Formal Context)

A _formal context_ is a triple $(G,M,I)$, where $G$ is a set of objects, $M$
is a set of attributes, and $I\subseteq G\times M$ is a binary relation
between objects and attributes.

A _formal concept_ is a pair $(A,B)$ consisting of a set $A\subseteq G$ of
objects (the ‘extent’) and a set $B\subseteq M$ of attributes (the ‘intent’)
such that the extent consists of all objects that share the given attributes,
and the intent consists of all attributes shared by the given objects. A
formal concept $(A_{1},B_{1})$ is less or equal to a formal concept
$(A_{2},B_{2})$, written $(A_{1},B_{1})\leq(A_{2},B_{2})$ iff $A_{1}\subseteq
A_{2}$. The set of all formal concepts ordered by $\leq$ forms a complete
lattice.

###### Example 3

$(\\{\heartsuit,\diamondsuit\\},\\{\text{Attribute 1, Attribute 2}\\})$ is a
formal concept in the formal context shown in Table 2.

Table 2: Formal context  Objects | Attribute 1 | Attribute 2 | Attribute 3
---|---|---|---
$\square$ | ✓ |  | ✓
$\heartsuit$ | ✓ | ✓ |
$\bigcirc$ |  |  | ✓
$\diamondsuit$ | ✓ | ✓ |
$\triangle$ |  |  | ✓

In FCA, dependencies between attributes are expressed by _implications_ —a
notion similar to the notion of an association rule (Definition 1). An
implication is an expression of the form $B_{1}\rightarrow B_{2}$ where
$B_{1},B_{2}$ are sets of attributes. An implication $B_{1}\rightarrow B_{2}$
holds in a formal context $(G,M,I)$ if every object having all attributes in
$B_{1}$ also has all attributes in $B_{2}$. A subset $B\subseteq M$ respects
an implication $B_{1}\rightarrow B_{2}$ if $B_{1}\not\subseteq B$ or
$B_{2}\subseteq B$. An implication $i$ _follows_ from a set $\mathcal{S}$ of
implications if any subset of $M$ that respects all implications from
$\mathcal{S}$ also respects $i$. In FCA, one is essentially interested in
computing the implications that hold in a formal context. A set $\mathcal{S}$
of implications that hold in a formal context $\mathbb{K}$ is called an
_implicational base_ for $\mathbb{K}$ if every implication that holds in
$\mathbb{K}$ follows from $\mathcal{S}$. Moreover, there should be no
redundancies in $\mathcal{S}$ (i.e., if $i\in\mathcal{S}$ then $i$ does not
follow from $\mathcal{S}\setminus\\{i\\}$). Implicational bases are not
unique. A well-studied kind of implicational base (with additional properties)
is called _stem_ (or _Duquenne-Guigues_) base [25, 18].

The learning framework for FCA is $\mathfrak{F}_{\sf
FCA}=(\mathcal{E},\mathcal{L},\mu)$ with $\mathcal{E}$ the set of all formal
contexts $\mathbb{K}$; $\mathcal{L}$ the set of all implicational bases
$\mathcal{S}$; and

$\mu(\mathcal{S})=\\{\mathbb{K}\in\mathcal{E}\mid\mathcal{S}\text{ is an
implicational base for }\mathbb{K}\\}.$

FCA Problem: Given $\mathbb{K}$, let $\mathfrak{F}_{\sf FCA}$ be
$(\mathcal{E},\mathcal{L},\mu)$. Find $\mathcal{S}\in\mathcal{L}$ with
$\mathbb{K}\in\mu(\mathcal{S})$.

###  4.2 Building DL ontologies

Approaches to combine FCA and DL have been addressed by many authors [42, 5,
4, 7, 41]. A common way of bridging the gap between FCA and DL [10] is the one
that maps a finite interpretation
$\mathcal{I}=(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$ and a finite set $S$
of concept expressions into formal context $(G,M,I)$ in such a way that:

  * •

each $d\in\Delta^{\mathcal{I}}$ corresponds to an object $o$ in $G$;

  * •

each concept expression $C\in S$ corresponds to an attribute $a$ in $M$; and

  * •

$d\in C^{\mathcal{I}}$ if, and only if, $(o,a)\in I$.

The notion of an implication is mapped to the notion of a CI in a DL. Just to
give an idea, if the formal context represented by Table 2 is induced by a DL
interpretation then the CI ${\sf Attribute2}\sqsubseteq{\sf Attribute1}$ would
be a candidate to be added to the ontology. The notion of an implicational
base is adapted as follows. Let $\mathcal{I}$ be a finite interpretation and
let $L$ be a DL language with symbols taken from a finite vocabulary. An
_implicational base for $\mathcal{I}$ and $L$_ [10] is a non-redundant set
$\mathcal{T}$ of CIs formulated in $L$ (for short L-CIs) such that for all
$L$-CIs

  * •

$\mathcal{I}\models C\sqsubseteq D$ if, and only if, $\mathcal{T}\models
C\sqsubseteq D$.

We parameterize the learning framework $\mathfrak{F}^{\sf DL}_{\sf FCA}$ with
a DL $L$. Then, $\mathfrak{F}^{\sf DL}_{\sf FCA}(L)$ is
$(\mathcal{E},\mathcal{L},\mu)$, where $\mathcal{E}$ is the set of all finite
interpretations $\mathcal{I}$, $\mathcal{L}$ is the set of all implicational
bases $\mathcal{T}$ for $\mathcal{I}\in\mathcal{E}$ and $L$, and

$\mu(\mathcal{T}){=}\\{\mathcal{I}\in\mathcal{E}\mid\mathcal{T}\text{ is an
implicational base for }\mathcal{I}\text{ and }L\\}.$

FCA+DL Problem: Given $\mathcal{I}$ and $L$, let $\mathfrak{F}^{\sf DL}_{\sf
FCA}(L)$ be $(\mathcal{E},\mathcal{L},\mu)$. Find $\mathcal{T}\in\mathcal{L}$
with $\mathcal{I}\in\mu(\mathcal{T})$.

Similar to the difficulty described for the DL adaptation of the ARM approach,
there may be no finite implicational base for a given interpretation and DL.

$e_{1}$$e_{2}$$e_{4}$$B$$A$$A,B$$e_{3}$$r$$r$ Figure 1:
$\\{A\sqsubseteq\exists r.(A\sqcap B)\\}$ is a base for ${\cal
E\\!\\!\>L}_{\sf rhs}$ [22].

###### Example 4

Consider the interpretation in Figure 1. An implicational base for ${\cal
E\\!\\!\>L}_{\sf rhs}$—the ${\cal E\\!\\!\>L}$ fragment that allows only
conjunctions of concept names on the left-side of CIs—is
$\\{A\sqsubseteq\exists r.(A\sqcap B)\\}$ [22]. However, if we remove $e_{3}$
from the extension of $A,B$ then, for all $n\in\mathbb{N}$, the CI
$A\sqsubseteq\exists r^{n}.\top$ holds and there is no ${\cal E\\!\\!\>L}_{\sf
rhs}$ finite base that can entail all such CIs. More expressive languages can
be useful for the computation of finite bases. It is known that, for ${\cal
E\\!\\!\>L}$ with greatest fixpoints semantics, a finite implicational base
always exists [10].

Classical FCA and ARM assume that all the information about the individuals is
known and can be represented in a finite way. A ‘✓’ in a table representing a
formal context means that the attribute holds for the corresponding object and
the absence means that the attribute does not hold. In contrast, DL makes the
‘open-world’ assumption, and so, the absence of information indicates a lack
of knowledge, instead of negation. To deal with the lack of knowledge, the
authors of [5] introduce the notion of a partial context, in which affirmative
and negative information about individuals is given as input and an expert is
required to decide whether a given concept inclusion should hold or not.

The need for a finite representation of objects and their attributes hinders
the creation of concept inclusions expressing, for instance, that ‘every human
has a parent that is a human’, in symbols

${\sf Human}\sqsubseteq\exists{\sf hasParent}.{\sf Human}$

or ‘every natural number has a successor that is a natural number’, where
elements of a model capturing the meaning of the relation are linked by an
infinite chain. This limitation is shared by all approaches which mine CIs
from data, including ARM, but in FCA this difficulty is more evident as it
requires 100% of confidence. This problem can be avoided by allowing the
system to interact with an expert who can assert domain knowledge that cannot
be conveyed from the finite interpretation given as input [42].

##  5 Inductive Logic Programming

###  5.1 Original Approach

ILP is an area between logic programming and machine learning [35]. In the
general setting of ILP, we are given a logical formulation of background
knowledge and some examples classified into positive and negative [35]. The
background knowledge is often formulated with a _logic program_ —a non-
propositional version of Horn clauses where all variables in a clause are
universally quantified within the scope of the entire clause. The goal is to
extend the background knowledge $\mathcal{B}$ with a hypothesis $\mathcal{H}$
in such a way that all examples in the set of positive examples can be deduced
from the modified background knowledge and none of the elements of the set of
negative examples can be deduced from it.

We introduce the syntax of function-free first-order Horn clauses. A term $t$
is either a variable or a constant. An _atom_ is an expression of the form
$P(\vec{t})$ with $P$ a predicate and $\vec{t}$ a list of terms
$t_{1},\ldots,t_{a}$ where $a$ is the arity of $P$. An atom is _ground_ if all
terms occurring in it are constants. A _literal_ is an atom $\alpha$ or its
negation $\neg\alpha$. A first-order clause is a universally quantified
disjunction of literals. It is called _Horn_ if it has at most one positive
literal. A _Horn expression_ is a set of (first-order) Horn clauses. A
_classified example_ in this setting is a pair $(e,\ell(e))$ where $e$ is a
ground atom and $\ell(e)$ (the label of $e$) is $1$ if $e$ is a positive
example or $0$ if it is negative.

######  Definition 3 (Correct Hypothesis)

Let $\mathcal{B}$ be a Horn expression and $S$ a set of pairs $(e,\ell(e))$
with $e$ a ground atom and $\ell(e)\in\\{1,0\\}$. A Horn expression
$\mathcal{H}$ is a _correct hypothesis for $\mathcal{B}$ and $S$_ if

$\forall(e,1)\in S,\ \mathcal{B}\cup\mathcal{H}\models e\text{ and
}\forall(e,0)\in S,\ \mathcal{B}\cup\mathcal{H}\not\models e.$

###### Example 5

Suppose that we are given as input the background knowledge $\mathcal{B}$
222We use the equivalent representation of Horn clauses as implications. and a
set $S$ of classified examples presented in Table 3. In this example, one
might conjecture a hypothesis $\mathcal{H}$ which states that:

$\forall xy({\sf isExpert}(x,y)\wedge{\sf Domain}(y)\rightarrow{\sf
DomainExpert}(x)).$

Table 3: Background knowledge and classified examples  Background Knowledge
---
$\forall x({\sf MedicalDomain}(x)\rightarrow{\sf Domain}(x))$
${\sf Person}({\sf John})$, ${\sf MedicalDomain}({\sf Allergy})$
${\sf isExpert}({\sf John}$, ${\sf Allergy})$
Classified Examples
$({\sf DomainExpert}({\sf John}),1)$
$({\sf DomainExpert}({\sf Allergy}),0)$

This form of inference is not sound in the logical sense since $\mathcal{H}$
does not necessarily follow from $\mathcal{B}$ and $S$. Another hypothesis
considered as correct by this approach would be

$\forall x({\sf Person}(x)\rightarrow{\sf DomainExpert}(x)),$

even though one could easily think of an interpretation with a person not
being a domain expert. One could also create a situation in which there are
infinitely many hypotheses suitable to explain the positive and negative
examples. For this reason, it is often required a non-logical constraint to
justify the choice of a particular hypothesis [35]. A common principle is the
Occam’s razor principle which says that the simplest hypothesis is the most
likely to be correct (simplicity can be understood in various ways, a naive
way is to consider the length of the Horn expression as a string).

We parameterize the learning framework for ILP with the background knowledge
$\mathcal{B}$, given as part of the input of the problem. We then have that
$\mathfrak{F}_{\sf ILP}(\mathcal{B})$ is the learning framework
$(\mathcal{E},\mathcal{L},\mu)$ with $\mathcal{E}$ the set of all ground
atoms; $\mathcal{L}$ the set of all Horn expressions $\mathcal{H}$; and

$\mu(\mathcal{H})=\\{e\in\mathcal{E}\mid\mathcal{B}\cup\mathcal{H}\models
e\\}.$

Classified examples help to distinguish a target unknown logical theory
formulated as a Horn expression from other Horn expressions in the hypothesis
space. In the learning framework $\mathfrak{F}_{\sf ILP}(\mathcal{B})$,
positive examples for a Horn expression $\mathcal{H}$ are those entailed by
the union of $\mathcal{H}$ and the background theory $\mathcal{B}$.

ILP Problem: Given $\mathcal{B}$ and $S$ (as in Definition 3), let
$\mathfrak{F}_{\sf ILP}(\mathcal{B})$ be $(\mathcal{E},\mathcal{L},\mu)$. Find
$\mathcal{H}\in\mathcal{L}$ such that $\mathcal{H}$ is a correct (and simple)
hypothesis for $\mathcal{B}$ and $S$. That is, for all $(e,\ell(e))\in S$,
$e\in\mu(\mathcal{H})$ iff $\ell(e)=1$.

###  5.2 Building DL Ontologies

In the DL context, ILP has been applied for learning DL concept expressions
[12, 13, 21, 26, 29, 27] and for learning logical rules for ontologies [31].
We describe here the problem setting for learning DL _concept expressions_ ,
which can help the designer to formulate the concept expressions in an
ontology. As in the classical ILP approach, the learner receives as input some
background knowledge, formulated as a _knowledge base_
$\mathcal{K}=(\mathcal{T},\mathcal{A})$, where $\mathcal{T}$ is a TBox and
$\mathcal{A}$ is a set of _assertions_ , that is, expressions of the form
$A(a)$, $r(a,b)$ where $A\in{\sf N_{C}}$, $r\in{\sf N_{R}}$, and $a,b$ are
taken from a set ${\sf N_{I}}$ of individual names. Assertions can be seen as
ground atoms and $\mathcal{A}$, in DL terms, is called an _ABox_. A set $S$ of
pairs $(e,\ell(e))$ with $e$ an assertion and $\ell(e)\in\\{1,0\\}$ is also
given as part of the input. In the mentioned works, $e$ is of the form ${\sf
Target}(a)$, with ${\sf Target}$ a concept name in ${\sf N_{C}}$ not occurring
in $\mathcal{K}$ and $a\in{\sf N_{I}}$.

As in the original ILP approach, given $\mathcal{K}=(\mathcal{T},\mathcal{A})$
and $S$, a concept expression $C$ (in the chosen DL) is _correct_ for
$\mathcal{K}$ and $S$ if, for all $({\sf Target}(a),\ell({\sf Target}(a)))\in
S$, we have that $(\mathcal{T}\cup\\{{\sf Target}\equiv
C\\},\mathcal{A})\models{\sf Target}(a)$ iff $\ell({\sf Target}(a))=1$.

###### Example 6

The background knowledge in Table 3 can be translated into
$(\mathcal{T},\mathcal{A})$, with

$\mathcal{T}=\\{{\sf MedicalDomain}\sqsubseteq{\sf Domain}\\}$

and $\mathcal{A}$ the set of ground atoms given as background knowledge in
Table 3. Assuming that the target concept name is ${\sf DomainExpert}$ and the
set $S$ of classified examples is the one in Table 3, correct concept
expressions would be $\exists{\sf isExpert}.{\sf Domain}$ and ${\sf Person}$.

The learning framework and problem statement presented here is for learning
${\cal ALC}$ and ${\cal E\\!\\!\>L}$ concept expressions based on the ILP
approach [28, 29]. Here the learning framework is parameterized by a knowledge
base $(\mathcal{T},\mathcal{A})$ and a DL $L$. Then, $\mathfrak{F}^{\sf
DL}_{\sf ILP}((\mathcal{T},\mathcal{A}),L)$ is $(\mathcal{E},\mathcal{L},\mu)$
where $\mathcal{E}$ is the set of all ground atoms; $\mathcal{L}$ is the set
of all $L$ concept expressions $C$ such that ${\sf Target}$ does not occur in
it; and

$\mu(C)=\\{e\in\mathcal{E}\mid(\mathcal{T}\cup\\{{\sf Target}\equiv
C\\},\mathcal{A})\models e\\}.$

ILP+DL Problem: Given $\mathcal{K}$, $L$, and $S$ (the classified examples),
let $\mathfrak{F}^{\sf DL}_{\sf ILP}(\mathcal{K},L)$ be
$(\mathcal{E},\mathcal{L},\mu)$. Find $C\in\mathcal{L}$ such that $C$ is
correct (and simple) for $\mathcal{K}$ and $S$. That is, for all
$(e,\ell(e))\in S$, $e\in\mu(C)$ iff $\ell(e)=1$.

##  6 Learning Theory

###  6.1 Original Approach

We describe two classical learning models in CLT which have been applied for
learning DL concept expressions and ontologies. We start with the classical
PAC learning model and then describe the exact learning model333The expression
“Probably Approximately Correct” was coined by Angluin in the paper [2], where
she shows the connection between the two learning models..

In the PAC learning model, a learner receives classified examples drawn
according to a probability distribution and attempts to create a hypothesis
that approximates the target. The aim is to bound the probability that a
hypothesis constructed by the learner misclassifies an example. This approach
can be applied to any learning framework. Within this model, one can
investigate the complexity of learning an abstract target, such as a DL
concept, an ontology, or the weights of a NN.

We now formalise this model. Let $\mathfrak{F}=(\mathcal{E},\mathcal{L},\mu)$
be a learning framework. A _probability distribution_ $\mathcal{D}$ over
$\mathcal{E}$ is a function mapping events in a $\sigma$-algebra $E$ of
subsets of $\mathcal{E}$ to $[0,1]\subset\mathbb{R}$ such that
$\mathcal{D}(\bigcup_{i\in I}X_{i})=\sum_{i\in I}\mathcal{D}(X_{i})$ for
mutually exclusive $X_{i}$, where $I$ is a countable set of indices, $X_{i}\in
E$, and $\mathcal{D}(\mathcal{E})=1$. Given a target $t\in\mathcal{L}$, let
${\sf EX}^{\mathcal{D}}_{\mathfrak{F},t}$ be the oracle that takes no input,
and outputs a _classified example_ $(e,\ell_{t}(e))$, where $e\in\mathcal{E}$
is sampled according to the probability distribution $\mathcal{D}$,
$\ell_{t}(e)=1$, if $e\in\mu(t)$, and $\ell_{t}(e)=0$, otherwise. An _example
query_ is a call to the oracle ${\sf EX}^{\mathcal{D}}_{\mathfrak{F},t}$. A
_sample_ generated by ${\sf EX}^{\mathcal{D}}_{\mathfrak{F},t}$ is a
(multi-)set of indexed classified examples, independently and identically
distributed according to $\mathcal{D}$, sampled by calling ${\sf
EX}^{\mathcal{D}}_{\mathfrak{F},t}$.

A learning framework $\mathfrak{F}$ is _PAC learnable_ if there is a function
$f:(0,1)^{2}\to\mathbb{N}$ and a deterministic algorithm such that, for every
$\epsilon,\delta\in(0,1)\subset\mathbb{R}$, every probability distribution
$\mathcal{D}$ on $\mathcal{E}$, and every target $t\in\mathcal{L}$, given a
sample of size $m\geq f(\epsilon,\delta)$ generated by ${\sf
EX}^{\mathcal{D}}_{\mathfrak{F},t}$, the algorithm always halts and outputs
$h\in\mathcal{L}$ such that with probability at least $(1-\delta)$ over the
choice of $m$ examples in $\mathcal{E}$, we have that
$\mathcal{D}(\mu(h)\oplus\mu(t))\leq\epsilon$. If the number of computation
steps used by the algorithm is bounded by a polynomial function
$\mathit{p}(|t|,|e|,1/\epsilon,1/\delta)$, where $e$ is the largest example in
the sample generated by ${\sf EX}^{\mathcal{D}}_{\mathfrak{F},t}$, then
$\mathfrak{F}$ is _PAC learnable in polynomial time_.

###### Example 7

Let $\mathcal{E}=\\{\square,\heartsuit,\bigcirc,\diamondsuit,\triangle\\}$ and
let $\mathcal{D}$ be a probability distribution on $\mathcal{E}$, defined,
e.g., by the pairs

$(\\{\square\\},0.2),(\\{\heartsuit\\},0.1),(\\{\bigcirc\\},0.3),(\\{\diamondsuit\\},0.2),(\\{\triangle\\},0.2).$

Assume $h,t\in\mathcal{L}$, $\mu(h)=\\{\heartsuit,\bigcirc\\}$, and
$\mu(t)=\\{\heartsuit,\triangle\\}$. Then, the probability
$\mathcal{D}(\mu(h)\oplus\mu(t))$ that $h$ misclassifies an example according
to $\mathcal{D}$ is $0.5$.

PAC Problem: Given a learning framework decide whether it is PAC learnable in
polynomial time.

In the classical PAC approach, the probability distribution $\mathcal{D}$ is
unknown to the learner. The algorithm should provide a probabilistic bound for
any possible $\mathcal{D}$. We now describe the exact learning model. In this
model, a learner tries to identify an abstract target known by a teacher, also
called an _oracle_ , by interacting with the teacher [2]. The most successful
protocol is based on _membership_ and _equivalence_ queries. As it happens
with the PAC learning model, this model can be used to formulate learning
problems within the context of any kind of learning framework.

We formalise these notions as follows. Given a learning framework
$\mathfrak{F}=(\mathcal{E},\mathcal{L},\mu)$, we are interested in the exact
identification of a _target_ concept representation $t\in\mathcal{L}$ by
posing queries to oracles. Let ${\sf MQ}_{\mathfrak{F},t}$ be the oracle that
takes as input some $e\in\mathcal{E}$ and returns ‘yes’ if $e\in\mu(t)$ and
‘no’ otherwise. A membership query is a call to the oracle ${\sf
MQ}_{\mathfrak{F},t}$. For every $t\in\mathcal{L}$, we denote by ${\sf
EQ}_{\mathfrak{F},t}$ the oracle that takes as input a _hypothesis_ concept
representation $h\in\mathcal{L}$ and returns ‘yes’ if $\mu(h)=\mu(t)$ and a
_counterexample_ $e\in\mu(h)\oplus\mu(t)$ otherwise, where $\oplus$ denotes
the symmetric set difference. There is no assumption regarding which
counterexample in $\mu(h)\oplus\mu(t)$ is chosen by the oracle. An equivalence
query is a call to the oracle ${\sf EQ}_{\mathfrak{F},t}$. In this model, if
examples are interpretations or entailments, the notion of ‘equivalence’
coincides with _logical_ equivalence.

A learning framework $\mathfrak{F}$ is _exactly learnable_ if there is a
deterministic algorithm such that, for every $t\in\mathcal{L}$, it eventually
halts and outputs some $h\in\mathcal{L}$ with $\mu(h)=\mu(t)$. Such algorithm
is allowed to call the oracles ${\sf MQ}_{\mathfrak{F},t}$ and ${\sf
EQ}_{\mathfrak{F},t}$. If the number of computation steps used by the
algorithm is bounded by a polynomial $p(|t|,|e|)$, where $t\in\mathcal{L}$ is
the target and $e\in\mathcal{E}$ is the largest counterexample seen so far,
then $\mathfrak{F}$ is _exactly learnable in polynomial time_.

Exact Problem: Given a learning framework decide whether it is exactly
learnable in polynomial time.

In Theorem 6.1, we recall an interesting connection between the exact learning
model and the PAC model extended with membership queries. If there is a
polynomial time algorithm for a learning framework $\mathfrak{F}$ that is
allowed to make membership queries then $\mathfrak{F}$ is _PAC learnable with
membership queries in polynomial time_.

###### Theorem 6.1

[2] If a learning framework is exactly learnable in polynomial time then it is
PAC learnable with membership queries in polynomial time. If only equivalence
queries are used then it is PAC learnable (without membership queries) in
polynomial time.

The converse of Theorem 6.1 does not hold [6]. That is, there is a learning
framework that is PAC learnable in polynomial time (even without membership
queries) but not exactly learnable in polynomial time.

###  6.2 Building DL Ontologies

The PAC learning model has been already applied to learn DL concept
expressions formulated in DL CLASSIC [9, 15] (see also [36]). The main
difficulty in adapting the PAC approach for learning DL ontologies is the
complexity of this task. In the PAC learning model, one is normally interested
in _polynomial time_ complexity, however, many DLs, such as ${\cal ALC}$, have
superpolynomial time complexity for the entailment problem and entailment
checks are often important to combine the information present in the
classified examples.

It has been shown that the ${\cal E\\!\\!\>L}$ fragments ${\cal
E\\!\\!\>L}_{\sf lhs}$ and ${\cal E\\!\\!\>L}_{\sf rhs}$—the ${\cal
E\\!\\!\>L}$ fragments that allow only conjunctions of concept names on the
right-side and on the left-side of CIs, respectively—are polynomial time
exactly learnable from entailments [23, 24, 38, 37]444The result for ${\cal
E\\!\\!\>L}_{\sf rhs}$ (allowing conjunctions of concept names on the left-
side of CIs) appears in [23, Section 4], however, this is not the case for
${\cal E\\!\\!\>L}$. The learning framework is the one in Example 1 and the
problem statement is the same as in the original approach. By Theorem 6.1, the
results for ${\cal E\\!\\!\>L}_{\sf lhs}$ and ${\cal E\\!\\!\>L}_{\sf rhs}$
are transferable to the PAC learning model extended with membership queries.
The results show how changes in the ontology language can impact the
complexity of searching for a suitable ontology in the hypothesis space. The
main difficulty of implementing this model is that it is based on oracles, in
particular, on an equivalence query oracle. Fortunately, as already mentioned,
such equivalence queries can be simulated by the sampling oracle of the PAC
learning model to achieve PAC learnability (Theorem 6.1)[2].

##  7 Neural Networks

###  7.1 Original Approach

NNs are widespread architectures inspired by the structure of the brain [34].
They may differ from each other not only regarding their weight and activation
functions but also structurally, e.g., feed-forward NNs are acyclic while
recurrent NNs have cycles. One of the simplest models is the one given by
Definition 4.

######  Definition 4 (Neural Network)

An NN is a triple $(G,\sigma,w)$ where $G=(V,E)$ is a graph, with $V$ a set of
nodes, called _neurons_ , and $E\subseteq V\times V$ a set of (directed)
edges; $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ is the _activation_ function;
and $w:E\rightarrow\mathbb{R}$ is the _weight_ function.

Other parameters that can be part of the definition of an NN are the
propagation function and biases. A widely used propagation function is the
weighted sum. The propagation function specifies how the outputs of the
neurons connected to a neuron $n$ are combined to form the input of $n$. Given
an input to a neuron, the activation function maps it to the output of the
neuron. In symbols, the input ${\sf in}(n)$ of a neuron $n$ is

$\sum_{m:(m,n)\in E}\sigma({\sf in}(m))\cdot w((m,n)).$

The structure of an NN is organized in _layers_ , basically, an _input_ , an
_output_ , and (possibly several) _hidden_ layers. The input of an NN is a
vector of numbers in $\mathbb{R}$, given as input to the neurons in the input
layer. The output of the NN is also a vector of numbers in $\mathbb{R}$,
constructed using the outputs of the neurons in the output layer. The
dimensionality of the input and output of an NN varies according to the
learning task. One can then see an NN as a function mapping an input vector
$\vec{x}$ to an output vector $\vec{y}$. In symbols,
$(G,\sigma,w)(\vec{x})=\vec{y}$.

The main task is to find a weight function that minimizes the _risk_ of the NN
$\mathcal{N}$, modelled by a function $L_{\mathcal{D}}(\mathcal{N})$, with
$\mathcal{D}$ a probability distribution on a set of pairs $(\vec{x},\vec{y})$
of input/output vectors [44]. The risk of an NN represents how well we expect
the NN to perform while predicting the classification of unseen examples.

The learning framework can be defined in various ways. Here we parameterize it
by a graph structure and an activation function $\sigma$. We have that
$\mathfrak{F}_{\sf NN}(G,\sigma)$, with $G=(V,E)$, is
$(\mathcal{E},\mathcal{L},\mu)$ where $\mathcal{E}$ is a set of pairs
$(\vec{x},\vec{y})$ representing input and output vectors of numbers in
$\mathbb{R}$ (respectively, and with appropriate dimensionality);
$\mathcal{L}$ is the set of all weight functions $w:E\rightarrow\mathbb{R}$;
and

$\mu(w)=\\{(\vec{x},\vec{y})\in\mathcal{E}\mid(G,\sigma,w)(\vec{x})=\vec{y}\\}.$

One can formulate the NN problem as follows.

NN Problem: Given $G$ and $\sigma$, let $\mathfrak{F}_{\sf NN}(G,\sigma)$ be
$(\mathcal{E},\mathcal{L},\mu)$. Find $w\in\mathcal{L}$ that minimizes the
risk $L_{\mathcal{D}}(\mathcal{N})$ of $\mathcal{N}=(G,\sigma,w)$, where
$\mathcal{D}$ is a fixed but arbitrary and unknown probability distribution on
$\mathcal{E}$.

Classified examples for training and validation can be obtained by calling the
sampling oracle ${\sf EX}^{\mathcal{D}}_{\mathfrak{F},t}$ (recall ${\sf
EX}^{\mathcal{D}}_{\mathfrak{F},t}$ from Section 6), where $t\in\mathcal{L}$
is the (unknown) target weight function. One of the main challenges of this
approach is that finding an optimal weight function is computationally hard.
Most works apply a heuristic search based on the gradient descent algorithm
[44].

###  7.2 Building DL Ontologies

NNs have been applied to learn CIs from sentences expressing definitions,
called _definitorial sentences_ [39] (see also [32] for more work on
definitorial sentences in a DL context, and, e.g. [8, 50], for work on
learning assertions based on NNs). More specifically, the work on [39] is
based on _recurrent_ NNs, which are useful to process sequential data. The
structure of the NN, in this case, takes the form of a grid. The authors learn
${\cal ALCQ}$ CIs, where ${\cal ALCQ}$ is the extension of ${\cal ALC}$ with
qualified number restrictions. For example, “A car is a motor vehicle that has
$4$ tires and transport people.” corresponds to

${\sf Car}\sqsubseteq{\sf MotorVehicle}\ \sqcap=4{\sf has}.{\sf Tires}\
\sqcap\ \exists{\sf transport}.{\sf People}.$

The main benefits of this approach is that NNs can deal with natural language
variability. The authors provide an end-to-end solution that does not even
require natural language processing techniques. However, the approach is based
on the _syntax_ of the sentences, not on their semantics, and they cannot
capture portions of knowledge across different sentences [39]. Another
difficulty of adapting this approach for learning DL ontologies is the lack of
datasets available for training. Such dataset should consist of a large set of
pairs of definitorial sentences and their corresponding CI. The authors
created a synthetic dataset to perform their experiments.

The learning framework and problem statement for learning DL CIs based on the
NN approach [39] can be formulated as follows. The learning framework for a DL
$L$ can be defined as $\mathfrak{F}^{\sf DL}_{\sf
NN}(G,\sigma,L)=(\mathcal{E},\mathcal{L},\mu)$ where $\mathcal{E}$ is a set of
pairs $(\vec{x},\vec{y})$ with $\vec{x}$ a vector representation of a
definitorial sentence and $\vec{y}$ a vector representation of an $L$ CI; and
$\mathcal{L}$ and $\mu$ are as in the original NN approach.

NN+DL Problem: Given $G$, $L$ and $\sigma$, let $\mathfrak{F}^{\sf DL}_{\sf
NN}(G,\sigma,L)$ be $(\mathcal{E},\mathcal{L},\mu)$. Find $w\in\mathcal{L}$
that minimizes the risk $L_{\mathcal{D}}(\mathcal{N})$ of
$\mathcal{N}=(G,\sigma,w)$, where $\mathcal{D}$ is a fixed but arbitrary and
unknown probability distribution on $\mathcal{E}$.

##  8 Where Do They Stand?

We now discuss the main benefits and limitations of ARM, FCA, ILP, CLT, and
NNs for building DL ontologies, considering the goals listed in the
Introduction.

Interpretability. refers to the easiness of understanding the learned DL
ontology/concept expressions and obtaining insights about the domain. In ARM,
the requirement for computing CIs with high support often results in highly
interpretable CIs (at the cost of fixing the length of concept expressions).
The FCA approach classically deals with redundancies, which is often not
considered in ARM approaches. However, the CIs generated with this approach
can be difficult to interpret [7]. The ILP approach follows the Occam’s razor
principle, which contributes to the generation of interpretable DL
expressions, although there is no guarantee for the quality of the
approximation. Such guarantees can be found in CLT, where the goal is to
approximate or exactly identify the target. However, the focus of these
approaches is on accuracy rather than interpretability. Regarding NNs, the
complex models can deal with high variability in the data but may lose on
interpretability.

Expressivity. refers to the expressivity of the DL language supported by the
learning process. As we have seen, many previous approaches for learning DL
ontologies focus on Horn fragments such as ${\cal E\\!\\!\>L}$ [23, 24, 11,
28, 4, 7] (or Horn-like fragments such as ${\cal F\\!LE}$ [42]). Non-horn
fragments have been investigated for learning DL ontologies [48, 43] and
concept expressions [13, 21, 29] (fixing the length of concept expressions).
As mentioned, ${\cal ALCQ}$ CIs can be learned with NNs [39] (see also [51]).

Efficiency. refers to the amount of time and memory consumed by algorithms in
order to build a DL ontology (or concept expressions) in the context of a
particular approach or a learning model. In CLT one can formally establish
complexity results for learning problems. In ARM the search space is heavily
constrained by the support function, which means that usually large portions
of the search space can be eliminated in this approach. The Next-closure
algorithm used in FCA is polynomial in the output and has polynomial delay,
meaning that from the theoretical point of view it has interesting properties
regarding efficiency. However, in practice, there may be difficulties in
processing large portions of data provenient of knowledge graphs, such as
DBpedia [7].

Human interactions. may be required to complete the information given as input
or to validate the knowledge that cannot be represented in a finite dataset or
in a finite interpretation (recall the case of an infinite chain of objects in
Subsection 4.2). Since the input is simply a database or an interpretation,
the ARM and FCA approaches require limited or no human intervention. It is
worth to point out that some DL adaptations of the FCA approach depend on an
expert which resembles a membership oracle. The difference is that in the
exact learning model the membership oracle answers with ‘yes’ or ‘no’, whereas
in FCA the oracle also provides a counterexample if the answer is ‘no’ [42].
In ILP, examples need to be classified into positive and negative, which may
require human intervention to classify the examples before learning takes
place. The same happens with the CLT models presented. The exact learning
model is purely based on interactions with an oracle, which can be an expert
(or even a neural network [49]).

Unsupervised learning. is supported by the ARM and FCA approaches, as well as
some NNs (but not by the DL adaptation we have seen in the literature [39]).
As already mentioned, the approaches based on ILP and CLT fall in the
supervised setting. That is, examples receive some sort of (usually binary)
classification.

Inconsistencies and noise. are often present in the data. The ARM approach
deals with them by only requiring that the confidence of the CI is above a
certain threshold (instead of requiring that the CI is fully satisfied, as in
FCA). ILP and CLT classically do not support inconsistencies and noise,
though, the PAC model has an agnostic version in which it may not be possible
to construct a hypothesis consistent with the positive and negative examples
(due e.g. to noise in the classification). NNs can deal very well with data
variability, including cases in which there are inconsistencies and noise.

##  9 Conclusion

We discussed benefits and limitations of, namely, ARM, FCA, ILP, CLT, and NNs
for DL settings. Not many authors have applied NNs for learning DL ontologies
(when the focus is on building the logical expressions), even though NNs are
widespread in many areas. We believe that more works exploring this approach
are yet to come. One of the challenges is how to capture the _semantics_ of
the domain. Promising frameworks for capturing the semantics of logical
expressions [17, 40] and modelling logical rules [20] have been recently
proposed.

Finally, we have seen that each approach addresses some of the desired
properties of an ontology learning process. An interesting question is whether
they can be combined so as to obtain the best of each approach. Indeed, recent
works have proposed ways of combining FCA with the exact and PAC learning
models [36]. Moreover, the support and confidence measures from ARM could also
be applied in FCA for dealing with noisy and incomplete data [7].

Acknowledgements. This work is supported by the Free University of Bozen-
Bolzano through the projects PACO and MLEARN.

## 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] 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)
  * [4] Baader, F., Distel, F.: Exploring finite models in the description logic.  In: ICFCA, pp. 146–161 (2009)
  * [5] 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)
  * [6] Blum, A.L.: Separating distribution-free and mistake-bound learning models over the boolean domain.  SIAM J. Comput. 23(5) (1994)
  * [7] Borchmann, D., Distel, F.: Mining of $\mathcal{EL}$-GCIs.  In: The 11th IEEE International Conference on Data Mining Workshops. Vancouver, Canada (2011)
  * [8] 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)
  * [9] Cohen, W.W., Hirsh, H.: Learning the CLASSIC description logic: Theoretical and experimental results.  In: KR, pp. 121–133 (1994)
  * [10] Distel, F.: Learning description logic knowledge bases from data using methods from formal concept analysis.  Ph.D. thesis, Dresden University of Technology (2011)
  * [11] Duarte, M.R.C., Konev, B., Ozaki, A.: Exactlearner: A tool for exact learning of EL ontologies.  In: KR, pp. 409–414 (2018)
  * [12] Funk, M., Jung, J.C., Lutz, C., Pulcini, H., Wolter, F.: Learning description logic concepts: When can positive and negative examples be separated?  In: IJCAI, pp. 1682–1688 (2019)
  * [13] Fanizzi, N., d’Amato, C., Esposito, F.: DL-FOIL concept learning in description logics.  In: ILP, pp. 107–121 (2008)
  * [14] 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)
  * [15] Frazier, M., Pitt, L.: Classic learning.  Machine Learning 25(2-3), 151–193 (1996)
  * [16] 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)
  * [17] Galliani, P., Kutz, O., Porello, D., Righetti G., and Troquard, N.: On Knowledge Dependence in Weighted Description Logic  In: GCAI, pp. 68–80 (2019)
  * [18] Ganter, B., Rudolph, S., Stumme, G.: Explaining data with formal concept analysis.  In: RW, pp. 153–195 (2019)
  * [19] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.  Springer (1997)
  * [20] Gutiérrez-Basulto, V., Schockaert, S.: From knowledge graph embedding to ontology embedding? an analysis of the compatibility between vector space representations and rules.  In: KR, pp. 379–388 (2018)
  * [21] Iannone, L., Palmisano, I., Fanizzi, N.: An algorithm based on counterfactuals for concept learning in the semantic web.  Appl. Intell. 26, 139–159 (2007)
  * [22] Klarman, S., Britz, K.: Ontology learning from interpretations in lightweight description logics.  In: ILP (2015)
  * [23] Konev, B., Lutz, C., Ozaki, A., Wolter, F.: Exact learning of lightweight description logic ontologies.  JMLR 18(201), 1–63 (2018)
  * [24] Konev, B., Ozaki, A., Wolter, F.: A model for learning description logic ontologies based on exact learning.  In: AAAI, pp. 1008–1015 (2016)
  * [25] L., G.J., V., D.: Familles minimales d’implications informatives résultant d’un tableau de données binaires.  Mathématiques et Sciences Humaines 95, 5–18 (1986)
  * [26] Lehmann, J.: DL-learner: learning concepts in description logics.  JMLR 10, 2639–2642 (2009)
  * [27] Lehmann, J.: Learning OWL class expressions, vol. 6.  IOS Press (2010)
  * [28] Lehmann, J., Haase, C.: Ideal downward refinement in the EL description logic.  In: ILP, pp. 73–87 (2009)
  * [29] Lehmann, J., Hitzler, P.: Concept learning in description logics using refinement operators.  Machine Learning 78(1-2), 203–250 (2010)
  * [30] Lehmann, J., Völker, J.: Perspectives on Ontology Learning, vol. 18.  IOS Press (2014)
  * [31] Lisi, F.A.: Al-quin: An onto-relational learning system for semantic web mining.  Int. J. Semantic Web Inf. Syst. 7, 1–22 (2011)
  * [32] Ma, Y., Distel, F.: Learning formal definitions for Snomed CT from text.  In: AIME, pp. 73–77 (2013)
  * [33] Maedche, A., Staab, S.: Ontology learning for the semantic web.  IEEE Intelligent Systems 16, 72–79 (2001)
  * [34] McCulloch, W.S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity.  In: Neurocomputing: Foundations of Research, pp. 15–27. MIT Press (1988)
  * [35] Muggleton, S.: Inductive logic programming.  New generation computing 8(4), 295–318 (1991)
  * [36] Obiedkov, S., Sertkaya, B., Zolotukhin, D.: Probably approximately correct completion of description logic knowledge bases.  In: DL, (2019)
  * [37] Ozaki, A.: On the Complexity of Learning Description Logic Ontologies  In: RW, (2020)
  * [38] Ozaki, A., Persia, C., Mazzullo, A.: Learning Query Inseparable ELH Ontologies  In: AAAI, (2020)
  * [39] Petrucci, G., Ghidini, C., Rospocher, M.: Ontology learning in the deep.  In: EKAW, pp. 480–495 (2016)
  * [40] Porello, D., Kutz, O., Righetti, G., Troquard, N., Galliani, P., Masolo, C.: A Toothful of Concepts: Towards a Theory of Weighted Concept Combination.  In: DL (2019)
  * [41] Guimarães, R., Ozaki, A., Persia, C., Sertkaya, B.: Mining EL Bases with Adaptable Role Depth.  In: AAAI, (to appear) (2021)
  * [42] Rudolph, S.: Exploring relational structures via FLE.  In: ICCS. Springer (2004)
  * [43] Sazonau, V., Sattler, U.: Mining hypotheses from data in OWL: advanced evaluation and complete construction.  In: ISWC, pp. 577–593 (2017)
  * [44] Shalev-Shwartz, S., Ben-David, S.: Understanding machine learning: From theory to algorithms.  Cambridge university press (2014)
  * [45] Stepanova, D., Gad-Elrab, M.H., Ho, V.T.: Rule induction and reasoning over knowledge graphs.  In: RW, pp. 142–172 (2018)
  * [46] Valiant, L.G.: A theory of the learnable.  Commun. ACM 27(11), 1134–1142 (1984)
  * [47] Völker, J., Fleischhacker, D., Stuckenschmidt, H.: Automatic acquisition of class disjointness.  Journal of Web Semantics 35, 124–139 (2015)
  * [48] Völker, J., Niepert, M.: Statistical schema induction.  In: The Semantic Web: Research and Applications, pp. 124–138. Springer (2011)
  * [49] Weiss, G., Goldberg, Y., Yahav, E.: Extracting automata from recurrent neural networks using queries and counterexamples.  In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 5244–5253 (2018)
  * [50] Yang, B., Yih, W., He, X., Gao, J., Deng, L.: Embedding entities and relations for learning and inference in knowledge bases.  In: ICLR (2015)
  * [51] Zhu, M., Gao, Z., Pan, J.Z., Zhao, Y., Xu, Y., Quan, Z.: Tbox learning from incomplete data by inference in belnet${}^{\mbox{+}}$.  Knowl.-Based Syst. 75, 30–40 (2015)


###  5.5 Calculable approximations of $\sigma$, u, and $p$

Once Newton’s iteration is over, we can use the discrete operators described
in previous sections to find non-virtual approximations of all the unknowns
(see [27, Sections 5.3 and 5.4]). Indeed, given
$(\text{\boldmath$\sigma$}_{h}^{(s)},\text{\rm u}_{h}^{(s)})\in\mathbb{X}_{h}$
the final approximation of the solution of (5.8), we consider, for each
$K\in\mathcal{T}_{h}$, the vector
$\left(\begin{smallmatrix}\text{\boldmath$\alpha$}^{K}\\\
\text{\boldmath$\beta$}^{K}\\\ \xi_{h}\end{smallmatrix}\right)$ containing the
local degrees of freedom of $\text{\boldmath$\sigma$}_{h}^{(s)}$, $\text{\rm
u}_{h}^{(s)}$ and $\xi_{h}^{(s)}$, respectively, sorted as indicated in Figure
4.1. More precisely, following (5.15), we have

$\text{\boldmath$\sigma$}^{(s)}_{h}\big{|}_{K}\ =\
\sum_{i=1}^{2n_{k}^{H}}\alpha_{i}^{K}\,\vec{\text{\boldmath$\Psi$}}^{K}_{i}{\qquad\hbox{and}\qquad}\text{\rm
u}^{(s)}_{h}\big{|}_{K}\ =\
\sum_{i=1}^{2n_{k}^{V}}\beta_{i}^{K}\,\vec{\text{\boldmath$\psi$}}^{K}_{i}\,,$

where
$\text{\boldmath$\alpha$}^{K}=(\alpha_{1}^{K},\ldots,\alpha_{2n_{k}^{H}}^{K})^{\text{\tt
t}}$ and
$\text{\boldmath$\beta$}^{K}=(\beta_{1}^{K},\ldots,\beta_{2n_{k}^{V}}^{K})^{\text{\tt
t}}$. Now, according to [27, eq. (5.32)]), we introduce the fully computable
local approximations of $\text{\boldmath$\sigma$}_{h}^{(s)}$ and $\text{\rm
u}_{h}^{(s)}$ given by

$\widehat{\text{\boldmath$\sigma$}}_{h}\big{|}_{K}\ :=\
\text{\boldmath$\mathcal{P}$}_{k}^{K}(\text{\boldmath$\sigma$}^{(s)}_{h}\big{|}_{K})\
=\ \sum_{i=1}^{4m}a_{i}^{K}\,\Phi_{i}^{K}\,,$

and

$\widehat{\text{\rm u}}_{h}\big{|}_{K}\ :=\ \mathcal{P}_{k}^{K}(\text{\rm
u}^{(s)}_{h}\big{|}_{K})\ =\
\sum_{i=1}^{2m}b_{i}^{K}\,\text{\boldmath$\varphi$}_{i}^{K}\,,$

respectively. Moreover, it is quite simple to see that

$\text{\boldmath$a$}^{K}\ =\ \text{\rm
P}^{K}\text{\boldmath$\alpha$}^{K}{\qquad\hbox{and}\qquad}\text{\boldmath$b$}^{K}\
=\ \textrm{kron}(\text{\rm I}_{2},\,\text{\rm
R}^{K})\,\text{\boldmath$\beta$}^{K}\,,$

where $\text{\boldmath$a$}^{K}=(a_{1}^{K},\ldots,a_{4m}^{K})^{\text{\tt t}}$
and $\text{\boldmath$b$}^{K}=(b_{1}^{K},\ldots,b_{2m}^{K})^{\text{\tt t}}$. In
addition, we now present the following computable approximation of the
pressure:

$\widehat{p}_{h}\big{|}_{K}\ :=\ -\frac{1}{2}\,\text{\rm
tr}\Big{(}\widehat{\text{\boldmath$\sigma$}}_{h}\big{|}_{K}\,+\,\widehat{c}_{h}\,\text{\rm
I}_{2}\,+\,\widehat{\text{\rm u}}_{h}\big{|}_{K}\otimes\widehat{\text{\rm
u}}_{h}\big{|}_{K}\Big{)}\,,$

with $\widehat{c}_{h}:=-\frac{1}{2|\Omega|}\,\|\widehat{\text{\rm
u}}_{h}\|_{0,\Omega}^{2}$. Finally, in [27, Section 5.4], a second
approximation $\widetilde{\text{\boldmath$\sigma$}}_{h}$ of the pseudostress
$\sigma$, which yields optimal rate of convergence in the broken
$\mathbb{H}(\textrm{\bf div};\Omega)$-norm is presented. Here, the calculation
of $\widetilde{\text{\boldmath$\sigma$}}_{h}$ is not presented, since it
follows similarly as the previous operators described before.

###  5.6 Numerical results

In this section we present a numerical experiment in order to illustrate the
performance of the mixed virtual element scheme (5.8) employing the Newton’s
iteration introduced in (5.10). It allows us to validate the operators
introduced in Section 4, together with the numerical experiments presented in
recent papers about mixed-VEM schemes, which utilized our implementation
approach (see [15, 17, 16, 26, 25, 32]). We begin by recalling from (5.12)
that $N$ stands for the total number of degrees of freedom (unknowns) of
(5.10). In addition, the individual errors are defined by

${\tt e}(\text{\boldmath$\sigma$})\ :=\
\|\text{\boldmath$\sigma$}-\widehat{\text{\boldmath$\sigma$}}_{h}\|_{0,\Omega}\,,\qquad{\tt
e}(\text{\rm u})\ :=\ \|\text{\rm u}-\widehat{\text{\rm
u}}_{h}\|_{0,\Omega}\,,\qquad{\tt e}(\widehat{\text{\rm u}})\ :=\
\Bigg{\\{}\sum_{K\in\mathcal{T}_{h}}\|\text{\rm u}-\widehat{\text{\rm
u}}_{h}\|_{1,K}^{2}\Bigg{\\}}^{1/2}\,,$ ${\tt e}(p)\ :=\
\|p-\widehat{p}_{h}\|_{0,\Omega}\,,{\qquad\hbox{and}\qquad}{\tt
e}(\widetilde{\text{\boldmath$\sigma$}})\ :=\
\Bigg{\\{}\sum_{K\in\mathcal{T}_{h}}\|\text{\boldmath$\sigma$}-\widetilde{\text{\boldmath$\sigma$}}_{h}\|_{\textrm{\bf
div};K}^{2}\Bigg{\\}}^{1/2}\,,$

where $\widehat{\text{\boldmath$\sigma$}}_{h}$, $\widehat{\text{\rm u}}_{h}$,
$\widehat{p}_{h}$, and $\widetilde{\text{\boldmath$\sigma$}}_{h}$ are
introduced in Section 5.5. In turn, the associated experimental rates of
convergence are given by

${\tt r}(\cdot)\ :=\ \displaystyle\frac{\log\big{(}{\tt e}(\cdot)\,/\,{\tt
e}^{\prime}(\cdot)\big{)}}{\log(h\,/\,h^{\prime})}\,,$

where ${\tt e}$ and ${\tt e}^{\prime}$ denote the corresponding errors for two
consecutive meshes with sizes $h$ and $h^{\prime}$, respectively.

The Newton method (5.10) is solved by using a tolerance of $10^{-6}$ and
taking as initial iteration the solution of the associated linear Stokes
problem, where four iterations were required to achieve the given tolerance.
On the other hand, the numerical results presented below were obtained using a
MATLAB code, where the corresponding linear systems were solved using its
instruction “\” as main solver.

Next, we consider $\Omega:=(-0.5,1.5)\times(0,2)$, $\mu=0.1$, and choose the
data f and g so that the exact solution is given by the flow from [30], that
is,

$\text{\rm u}(\text{\rm x})\ =\ \left(\begin{array}[]{c}\displaystyle
1-\exp(\lambda x_{1})\cos(2\pi x_{2})\\\\[4.30554pt]
\displaystyle\frac{\lambda}{2\pi}\exp(\lambda x_{1})\sin(2\pi
x_{2})\end{array}\right){\qquad\hbox{and}\qquad}p(\text{\rm x})\ =\
\frac{1}{2}\exp(2\lambda
x_{1})\,-\,\frac{1}{8\lambda}\big{\\{}\exp(3\lambda)-\exp(-\lambda)\big{\\}}\,,$

for all $\text{\rm x}:=(x_{1},x_{2})^{\text{\tt t}}\in\Omega$, where
$\lambda:=\frac{Re}{2}-\sqrt{\frac{Re^{2}}{4}+4\pi^{2}}$ and $Re:=\mu^{-1}=10$
is the Reynolds number. Moreover, according to [27, Theorem 2.1], we set the
parameters $\kappa_{1}=\kappa_{2}=\kappa_{3}=0.1$. In addition, we employ
polynomial degrees $k\in\\{0,1,2\\}$, and for the decompositions of $\Omega$
used in our computations, we consider triangles, distorted squares and
distorted hexagons, as illustrated in the Figure 5.2.

Figure 5.2: Examples of the meshes to be used in the calculations.

In Tables 5.1, 5.2 and 5.3, we summarize the convergence history of the mixed
virtual element scheme (5.8) as applied to the present example. It follows
from [27, Theorem 5.6] that the rate of convergence $O(h^{k+1})$ is attained
by ${\tt e}(\text{\boldmath$\sigma$})$, ${\tt e}(\text{\rm u})$, ${\tt e}(p)$,
and ${\tt e}(\widetilde{\text{\boldmath$\sigma$}})$, whereas the rate of
convergence $O(h^{k})$ is attained by ${\tt e}(\widehat{\text{\rm u}})$ in
this smooth example, for triangular as well as for quadrilateral and hexagonal
meshes. Hence, the results validate the suitable behavior of our computational
implementation, along with the analysis carried out in [27]. Finally, in
Figures 5.3 and 5.4 we display some components of the approximate solutions
obtained in this section. They all correspond to those obtained with the last
mesh of each kind (triangles, quadrilaterals and hexagons, respectively) and
for the polynomial degree $k=2$.

We end this paper by remarking some possible future directions. It would be
interesting to explain some computational aspects about the adaptivity and the
a posteriori error estimates for mixed virtual element schemes (see, e.g.,
[20, 32]). In addition, in this work we used direct solvers for solving each
lineal system. However, we are interesting to develop an algebraic or semi-
algebraic multilevel preconditioner in order to employ iterative solvers (see,
e.g., [21, 28]).

$k$ | $h$ | $N$ | ${\tt e}(\text{\boldmath$\sigma$})$ | ${\tt r}(\text{\boldmath$\sigma$})$ | ${\tt e}(\text{\rm u})$ | ${\tt r}(\text{\rm u})$ | ${\tt e}(\widehat{\text{\rm u}})$ | ${\tt r}(\widehat{\text{\rm u}})$ | ${\tt e}(p)$ | ${\tt r}(p)$ | ${\tt e}(\widetilde{\text{\boldmath$\sigma$}})$ | ${\tt r}(\widetilde{\text{\boldmath$\sigma$}})$
---|---|---|---|---|---|---|---|---|---|---|---|---
| 0.1230 | 4419 | 3.02e+00 | $--$ | 4.99e-01 | $--$ | 1.43e+01 | $--$ | 1.39e+00 | $--$ | 6.90e+00 | $--$
| 0.0943 | 7443 | 2.24e+00 | 1.13 | 3.50e-01 | 1.34 | 1.43e+01 | 0.00 | 9.76e-01 | 1.33 | 5.28e+00 | 1.00
0 | 0.0488 | 27379 | 1.05e+00 | 1.15 | 1.44e-01 | 1.34 | 1.43e+01 | 0.00 | 3.98e-01 | 1.36 | 2.70e+00 | 1.02
| 0.0354 | 51843 | 7.36e-01 | 1.10 | 9.63e-02 | 1.25 | 1.43e+01 | 0.00 | 2.65e-01 | 1.26 | 1.95e+00 | 1.01
| 0.0283 | 80803 | 5.79e-01 | 1.07 | 7.40e-02 | 1.18 | 1.43e+01 | 0.00 | 2.03e-01 | 1.19 | 1.56e+00 | 1.01
| 0.1230 | 19415 | 2.19e-01 | $--$ | 2.29e-02 | $--$ | 2.19e+00 | $--$ | 9.98e-02 | $--$ | 4.55e-01 | $--$
| 0.0943 | 32883 | 1.29e-01 | 1.98 | 1.29e-02 | 2.15 | 1.68e+00 | 1.00 | 5.85e-02 | 2.01 | 2.69e-01 | 1.97
1 | 0.0488 | 122035 | 3.52e-02 | 1.98 | 3.35e-03 | 2.05 | 8.71e-01 | 1.00 | 1.56e-02 | 2.00 | 7.27e-02 | 1.99
| 0.0354 | 231683 | 1.86e-02 | 1.98 | 1.76e-03 | 2.01 | 6.32e-01 | 1.00 | 8.23e-03 | 2.00 | 3.83e-02 | 1.99
| 0.0283 | 361603 | 1.19e-02 | 1.98 | 1.12e-03 | 2.00 | 5.05e-01 | 1.00 | 5.27e-03 | 2.00 | 2.45e-02 | 1.99
| 0.1230 | 40759 | 1.85e-02 | $--$ | 1.07e-03 | $--$ | 1.75e-01 | $--$ | 7.84e-03 | $--$ | 2.52e-02 | $--$
| 0.0943 | 69123 | 8.39e-03 | 2.98 | 4.72e-04 | 3.07 | 1.03e-01 | 2.00 | 3.54e-03 | 2.99 | 1.14e-02 | 2.98
2 | 0.0488 | 257059 | 1.16e-03 | 3.00 | 6.45e-05 | 3.02 | 2.75e-02 | 2.00 | 4.86e-04 | 3.01 | 1.59e-03 | 2.99
| 0.0354 | 488323 | 4.43e-04 | 3.00 | 2.46e-05 | 3.00 | 1.45e-02 | 2.00 | 1.84e-04 | 3.02 | 6.07e-04 | 3.00
| 0.0283 | 762403 | 2.27e-04 | 3.00 | 1.26e-05 | 3.00 | 9.27e-03 | 2.00 | 9.38e-05 | 3.02 | 3.11e-04 | 3.00
Table 5.1: History of convergence using triangles. $k$ | $h$ | $N$ | ${\tt e}(\text{\boldmath$\sigma$})$ | ${\tt r}(\text{\boldmath$\sigma$})$ | ${\tt e}(\text{\rm u})$ | ${\tt r}(\text{\rm u})$ | ${\tt e}(\widehat{\text{\rm u}})$ | ${\tt r}(\widehat{\text{\rm u}})$ | ${\tt e}(p)$ | ${\tt r}(p)$ | ${\tt e}(\widetilde{\text{\boldmath$\sigma$}})$ | ${\tt r}(\widetilde{\text{\boldmath$\sigma$}})$
---|---|---|---|---|---|---|---|---|---|---|---|---
| 0.1008 | 6403 | 3.03e+00 | $--$ | 5.44e-01 | $--$ | 1.43e+01 | $--$ | 1.79e+00 | $--$ | 6.30e+00 | $--$
| 0.0787 | 10417 | 2.20e+00 | 1.30 | 3.85e-01 | 1.39 | 1.43e+01 | 0.00 | 1.25e+00 | 1.45 | 4.88e+00 | 1.03
0 | 0.0404 | 39043 | 8.69e-01 | 1.39 | 1.49e-01 | 1.42 | 1.43e+01 | 0.00 | 4.25e-01 | 1.61 | 2.40e+00 | 1.06
| 0.0307 | 66993 | 6.04e-01 | 1.34 | 1.02e-01 | 1.40 | 1.43e+01 | 0.00 | 2.73e-01 | 1.63 | 1.81e+00 | 1.04
| 0.0229 | 120417 | 4.16e-01 | 1.27 | 6.89e-02 | 1.32 | 1.43e+01 | 0.00 | 1.71e-01 | 1.58 | 1.33e+00 | 1.03
| 0.1008 | 23043 | 1.57e-01 | $--$ | 1.81e-02 | $--$ | 1.82e+00 | $--$ | 5.86e-02 | $--$ | 3.16e-01 | $--$
| 0.0787 | 37641 | 9.59e-02 | 2.00 | 1.10e-02 | 2.00 | 1.42e+00 | 0.99 | 3.50e-02 | 2.08 | 1.95e-01 | 1.95
1 | 0.0404 | 142083 | 2.49e-02 | 2.02 | 2.88e-03 | 2.01 | 7.29e-01 | 1.00 | 8.78e-03 | 2.07 | 5.12e-02 | 2.00
| 0.0307 | 244233 | 1.44e-02 | 2.02 | 1.67e-03 | 2.00 | 5.56e-01 | 1.00 | 5.04e-03 | 2.04 | 2.97e-02 | 2.01
| 0.0229 | 439641 | 7.95e-03 | 2.01 | 9.28e-04 | 2.00 | 4.14e-01 | 1.00 | 2.77e-03 | 2.03 | 1.65e-02 | 2.00
| 0.1008 | 45827 | 1.34e-02 | $--$ | 8.58e-04 | $--$ | 1.30e-01 | $--$ | 4.55e-03 | $--$ | 1.60e-02 | $--$
| 0.0787 | 74951 | 6.41e-03 | 2.98 | 4.08e-04 | 3.00 | 7.96e-02 | 1.99 | 2.17e-03 | 3.00 | 7.69e-03 | 2.96
2 | 0.0404 | 283523 | 8.55e-04 | 3.02 | 5.45e-05 | 3.01 | 2.09e-02 | 2.00 | 2.81e-04 | 3.05 | 1.03e-03 | 3.01
| 0.0307 | 487623 | 3.77e-04 | 3.01 | 2.41e-05 | 3.00 | 1.21e-02 | 2.00 | 1.23e-04 | 3.04 | 4.54e-04 | 3.01
| 0.0229 | 878151 | 1.55e-04 | 3.00 | 9.96e-06 | 3.00 | 6.74e-03 | 2.00 | 5.08e-05 | 3.00 | 1.88e-04 | 3.00
Table 5.2: History of convergence using quadrilaterals. $k$ | $h$ | $N$ | ${\tt e}(\text{\boldmath$\sigma$})$ | ${\tt r}(\text{\boldmath$\sigma$})$ | ${\tt e}(\text{\rm u})$ | ${\tt r}(\text{\rm u})$ | ${\tt e}(\widehat{\text{\rm u}})$ | ${\tt r}(\widehat{\text{\rm u}})$ | ${\tt e}(p)$ | ${\tt r}(p)$ | ${\tt e}(\widetilde{\text{\boldmath$\sigma$}})$ | ${\tt r}(\widetilde{\text{\boldmath$\sigma$}})$
---|---|---|---|---|---|---|---|---|---|---|---|---
| 0.0959 | 10535 | 2.42e+00 | $--$ | 4.43e-01 | $--$ | 1.43e+01 | $--$ | 1.27e+00 | $--$ | 5.24e+00 | $--$
| 0.0732 | 17897 | 1.83e+00 | 1.05 | 3.22e-01 | 1.18 | 1.43e+01 | 0.00 | 8.92e-01 | 1.31 | 4.07e+00 | 0.94
0 | 0.0527 | 34143 | 1.16e+00 | 1.39 | 1.98e-01 | 1.48 | 1.43e+01 | 0.00 | 5.15e-01 | 1.67 | 2.92e+00 | 1.01
| 0.0390 | 61887 | 7.77e-01 | 1.34 | 1.32e-01 | 1.36 | 1.43e+01 | 0.00 | 3.17e-01 | 1.62 | 2.17e+00 | 0.99
| 0.0301 | 103495 | 5.66e-01 | 1.22 | 9.56e-02 | 1.23 | 1.43e+01 | 0.00 | 2.12e-01 | 1.54 | 1.67e+00 | 1.01
| 0.0959 | 31707 | 1.55e-01 | $--$ | 1.90e-02 | $--$ | 1.87e+00 | $--$ | 5.23e-02 | $--$ | 2.84e-01 | $--$
| 0.0732 | 53681 | 9.10e-02 | 1.97 | 1.12e-02 | 1.97 | 1.44e+00 | 0.97 | 3.02e-02 | 2.03 | 1.68e-01 | 1.94
1 | 0.0527 | 102623 | 4.76e-02 | 1.98 | 5.84e-03 | 1.97 | 1.04e+00 | 0.99 | 1.55e-02 | 2.04 | 9.00e-02 | 1.90
| 0.0390 | 185651 | 2.64e-02 | 1.97 | 3.23e-03 | 1.98 | 7.72e-01 | 0.99 | 8.46e-03 | 2.01 | 5.02e-02 | 1.94
| 0.0301 | 310827 | 1.56e-02 | 2.01 | 1.93e-03 | 1.99 | 5.97e-01 | 0.99 | 4.99e-03 | 2.03 | 2.98e-02 | 2.01
| 0.0959 | 59263 | 1.55e-02 | $--$ | 9.46e-04 | $--$ | 1.39e-01 | $--$ | 5.96e-03 | $--$ | 1.78e-02 | $--$
| 0.0732 | 100199 | 7.20e-03 | 2.85 | 4.30e-04 | 2.93 | 8.18e-02 | 1.95 | 2.79e-03 | 2.82 | 8.22e-03 | 2.88
2 | 0.0527 | 191707 | 2.75e-03 | 2.93 | 1.61e-04 | 2.98 | 4.25e-02 | 1.99 | 1.04e-03 | 2.99 | 3.17e-03 | 2.90
| 0.0390 | 346543 | 1.14e-03 | 2.94 | 6.57e-05 | 2.99 | 2.34e-02 | 1.99 | 4.36e-04 | 2.91 | 1.31e-03 | 2.94
| 0.0301 | 580463 | 5.26e-04 | 2.98 | 3.03e-05 | 2.99 | 1.39e-02 | 1.99 | 2.01e-04 | 2.97 | 6.02e-04 | 2.99
Table 5.3: History of convergence using hexagons.

Figure 5.3: Example 2, $\widehat{\sigma}_{h,11}$ (top),
$\widehat{\sigma}_{h,21}$ (center) and $\widehat{\sigma}_{h,22}$ (bottom),
using $k=2$ and the fifth mesh of triangles (left column), quadrilaterals
(center column) and hexagons (right column).

Figure 5.4: Example 2, $\widehat{u}_{h,1}$ (top), $\widehat{u}_{h,2}$ (center)
and $\widehat{p}_{h}$ (bottom), using $k=2$ and the fifth mesh of triangles
(left column), quadrilaterals (center column) and hexagons (right column).

## Acknowledgements

The authors would like to thank Gabriel N. Gatica, CI2MA and Departamento de
Ingeniería Matemática, Universidad de Concepción, Chile, for his suggestions
that significantly influenced the organization of this paper. On the other
hand, the work of Filánder A. Sequeira was partially supported by Universidad
Nacional, Costa Rica, through the project 0103-18.

## References

  * [1] B. Ahmad, A. Alsaedi, F. Brezzi, L.D. Marini, and A. Russo.  Equivalent projectors for virtual element methods.  Computers & Mathematics with Applications, 66(3):376–391, 2013\.
  * [2] P.F. Antonietti, L. Beirão da Veiga, D. Mora, and M. Verani.  A stream virtual element formulation of the Stokes problem on polygonal meshes.  SIAM Journal on Numerical Analysis, 52(1):386–404, 2014.
  * [3] L. Beirão da Veiga, F. Brezzi, A. Cangiani, L.D. Marini, G. Manzini, and A. Russo.  Basic principles of virtual elements methods.  Mathematical Models and Methods in Applied Sciences, 23(1):199–214, 2013.
  * [4] L. Beirão da Veiga, F. Brezzi, L. Marini, G. Manzini, and A. Russo.  $h(\textrm{div})$ and $h(\textrm{curl})$-conforming virtual element method.  Numerische Mathematik, 133(2):303–332, 2016.
  * [5] L. Beirão da Veiga, F. Brezzi, L. Marini, and A. Russo.  Mixed virtual element methods for general second order elliptic problems on polygonal meshes.  ESAIM Mathematical Modelling and Numerical Analysis, 50(3):727–747, 2016.
  * [6] L. Beirão da Veiga, F. Brezzi, L. Marini, and A. Russo.  Serendipity face and edge VEM spaces.  Preprint, arXiv: 1606.01048v1, 2016.
  * [7] L. Beirão da Veiga, F. Brezzi, L. Marini, and A. Russo.  Virtual element method for general second-order elliptic problems on polygonal meshes.  Mathematical Models and Methods in Applied Sciences, 26(4):729–750, 2016.
  * [8] L. Beirão da Veiga, F. Brezzi, L. D. Marini, and A. Russo.  The hitchhiker’s guide to the virtual element method.  Mathematical Models and Methods in Applied Sciences, 24(8):1541–1573, 2014.
  * [9] L. Beirão da Veiga, F. Brezzi, and L.D. Marini.  Virtual elements for linear elasticity problems.  SIAM Journal on Numerical Analysis, 51(2):794–812, 2013.
  * [10] L. Beirão da Veiga, C. Lovadina, and G. Vacca.  Virtual elements for the Navier-Stokes problem on polygonal meshes.  SIAM Journal on Numerical Analysis, 56(3):1210–1242, 2018.
  * [11] F. Brezzi, R.S. Falk, and L.D. Marini.  Basic principles of mixed virtual element methods.  ESAIM Mathematical Modelling and Numerical Analysis, 48(4):1227–1240, 2014.
  * [12] F. Brezzi and L.D. Marini.  Virtual element methods for plate bending problems.  Computer Methods in Applied Mechanics and Engineering, 253:455–462, 2013.
  * [13] E. Cáceres.  Mixed Virtual Element Methods. Applications in Fluid Mechanics.  Thesis leading to the professional title of Mathematical Civil Engineer, Universidad de Concepción, Chile, 2015.
  * [14] E. Cáceres and G. N. Gatica.  A mixed virtual element method for the pseudostress-velocity formulation of the Stokes problem.  IMA Journal of Numerical Analysis, 37(1):296–331, 2017.
  * [15] E. Cáceres, G.N. Gatica, and F.A. Sequeira.  A mixed virtual element method for the Brinkman problem.  Mathematical Models and Methods in Applied Sciences, 27(4):707–743, 2017.
  * [16] E. Cáceres, G.N. Gatica, and F.A. Sequeira.  A mixed virtual element method for quasi-Newtonian Stokes flows.  SIAM Journal on Numerical Analysis, 56(1):317–343, 2018.
  * [17] E. Cáceres, G.N. Gatica, and F.A. Sequeira.  A mixed virtual element method for a pseudostress-based formulation of linear elasticity.  Applied Numerical Mathematics, 135:423–442, 2019.
  * [18] J. Camaño, G.N. Gatica, R. Oyarzúa, and G. Tierra.  An augmented mixed finite element method for the Navier-Stokes equations with variable viscosity.  SIAM Journal on Numerical Analysis, 54(2):1069–1092, 2016.
  * [19] J. Camaño, R. Oyarzúa, and G. Tierra.  Analysis of an augmented mixed-FEM for the Navier-Stokes problem.  Mathematics of Computation, 86(304):589–615, 2017.
  * [20] A. Cangiani, E.H. Georgoulis, T. Pryer, and O.J. Sutton.  A posteriori error estimates for the virtual element method.  Numerische Mathematik, 137:857–893, 2017.
  * [21] P.E. Castillo and F.A. Sequeira.  Computational aspects of the local discontinuous Galerkin method on unstructured grids in three dimensions.  Mathematical and Computer Modelling, 57(9-10):2279–2288, 2013.
  * [22] E.B. Chin, J.B. Lasserre, and N. Sukumar.  Numerical integration of homogeneous functions on convex and nonconvex polygons and polyhedra.  Computational Mechanics, 56(6):967–981, 2015.
  * [23] E. Colmenares, G.N. Gatica, and R. Oyarzúa.  Analysis of an augmented mixed-primal formulation for the stationary Boussinesq problem.  Numerical Methods for Partial Differential Equations, 32(2):445–478, 2016.
  * [24] A.L. Gain, C. Talischi, and G.H. Paulino.  On the virtual element method for three-dimensional linear elasticity problems on arbitrary polyhedral meshes.  Computer Methods in Applied Mechanics and Engineering, 282:132–160, 2014.
  * [25] G.N. Gatica, M. Munar, and F.A. Sequeira.  A mixed virtual element method for the Boussinesq problem on polygonal meshes.  Journal of Computational Mathematics, to appear.
  * [26] G.N. Gatica, M. Munar, and F.A. Sequeira.  A mixed virtual element method for a nonlinear Brinkman model of porous media flow.  Calcolo, 55(2):21, 2018.
  * [27] G.N. Gatica, M. Munar, and F.A. Sequeira.  A mixed virtual element method for the Navier-Stokes equations.  Mathematical Models and Methods in Applied Sciences, 28(14):2719–2762, 2018.
  * [28] H. Guillén-Oviedo, J. Ramírez, E. Segura, and F.A. Sequeira.  Description and implementation of an algebraic multigrid preconditioner for ${H}^{1}$-conforming finite element schemes.  Uniciencia, 34(2):55–81, 2020.
  * [29] H. Guillén-Oviedo and F.A. Sequeira.  Una implementación computacional del método VEM mixto para el problema de Brinkman en 2D.  Revista de Matemática: Teoría y Aplicaciones, 26(2):215–251, 2019.
  * [30] L.I.G. Kovasznay.  Laminar flow behind a two-dimensional grid.  Mathematical Proceedings of the Cambridge Philosophical Society, 44:58–62, 1948.
  * [31] S.E. Mousavi and N. Sukumar.  Numerical integration of polynomials and discontinuous functions on irregular convex polygons and polyhedrons.  Computational Mechanics, 47(5):535–554, 2011.
  * [32] M. Munar and F.A. Sequeira.  A posteriori error analysis of a mixed virtual element method for a nonlinear Brinkman model of porous media flow.  Computers & Mathematics with Applications, 80(5):1240–1259, 2020\.
  * [33] A. Sommariva and M. Vianello.  Product Gauss cubature over polygons based on Green’s integration formula.  BIT Numerical Mathematics, 47(2):441–453, 2007.
  * [34] O.J. Sutton.  The virtual element method in 50 lines of MATLAB.  Numerical Algorithms, 75(4):1141–1159, 2017.