Vol-3197/short6
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3197/short6 |
| wikidataid | →Q117341686 |
| title | Rational Defeasible Subsumption in DLs with Nested Quantifiers: the Case of ELI⊥ |
| pdfUrl | https://ceur-ws.org/Vol-3197/short6.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/CamaraT22 |
| volume | Vol-3197→Vol-3197 |
| session | → |
Rational Defeasible Subsumption in DLs with Nested Quantifiers: the Case of ELI⊥
Rational Defeasible Subsumption in DLs with Nested
Quantifiers: the Case of ELI ⊥
(Extended Abstract)
Igor de Camargo e Souza Câmara1,∗ , Anni-Yasmin Turhan2
1 University of São Paulo, Brazil
2 Dresden University of Technology, Germany
Abstract
Defeasible description logics (DDLs) support nonmonotonic reasoning by admitting defeasible concept inclusions in the
knowledge base. Early reasoning methods for subsumption did not always use defeasible information for objects in the scope
of nested quantifiers and thus neglected un-defeated information. The reasoning approach employing typicality models for
the DDL EL⊥ overcomes this effect for existentially quantified objects.
In this extended abstract we report on how to lift typicality model-based reasoning to the DDL ELI ⊥ , which extends
EL⊥ with inverse roles. These can capture a form of universal quantification and extend expressivity of the DDL substantially.
Reasoning in DDLs often employs rational closure according to the propositional KLM postulates. We can show that the
proposed subsumption algorithm yields more entailments than rational propositional entailment.
Keywords
Description Logics, defeasible reasoning, Non-monotonic reasoning, Typicality
Description logics (DLs) are knowledge representation relation. For certain applications monotone reasoning
formalisms that are designed to model terminological can be a short-coming and variants of DLs with non-
knowledge. Important notions from an application do- monotonic reasoning have been investigated by the re-
main are modeled by concepts, which are essentially search community. A popular nonmonotonic variant are
unary first-order logic predicates. Each DL offers a set of defeasible description logics (DDLs) which can express
concept constructors which can be used to build complex knowledge that holds until it is defeated by contradictory
concepts. The so-called roles correspond to binary rela- information. DDLs can express what properties typical
tions and can be used in concept constructors to relate members of a concept fulfill by the use of defeasible con-
members of one concept to members of another. The use cept inclusions (DCIs) . A finite set of GCIS is a DBox D .
of roles and the quantification over the role-successors is A defeasible knowledge base (DKB) is a pair of a TBox and
what sets DLs apart from propositional logic. Concepts a DBox: K = (T , D).
can be related to each other by so-called general concept There are several proposals for semantics of defeasible
inclusions (GCIs), which state material implications for a DLs in the literature, such as [1, 2, 3, 4, 5, 6]. Many of them
pair of (complex) concepts. A finite set of GCIS is called use a kind of preferential semantics that often relies on
a TBox T . a preference relation on the interpretation domain. An-
Reasoning in description logics is usually the classical, other well-investigated approach is supply the semantics
monotone first-order reasoning. Two prominent reason- by materialization-based reasoning, where essentially the
ing problems are satisfiability of a concept w.r.t. an ontol- information from the DCIs is used in conjunction with
ogy and to decide subsumption for two given concepts the (potential) subsumee. This approach has the severe
w.r.t. an ontology. The latter is to test whether mem- short-coming of quantification neglect which means that
bership to the first concept implies membership to the defeasible information is not used for all the elements
second w.r.t. to the GCIs in T and is a classical entailment in the relational neighborhood of the subsumee. Thus
even un-defeated defeasible information can be omitted
NMR’22: 20th International Workshop on Non-Monotonic Reasoning, when performing reasoning over existentially quantified
August 07-09, 2022, Haifa, Israel objects—as it was observed in [5] and later and indepen-
∗ Corresponding author.
dently in [7, 6].
" igorcsc@ime.usp.br (I. d. C. e. S. Câmara);
anni-yasmin.turhan@tu-dresden.de (A. Turhan) One approach that alleviates quantification neglect
~ https://igorcsc.github.io/ (I. d. C. e. S. Câmara); and does not rely on a preference relation over the do-
https://lat.inf.tu-dresden.de/~turhan/ (A. Turhan) main is defeasible reasoning by typicality models. These
� 0000-0002-1831-1750 (I. d. C. e. S. Câmara); 0000-0001-6336-335X models were introduced for the DL EL⊥ and provide a
(A. Turhan)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
supraclassical inference relation. The classical DL EL⊥
Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
CEUR Workshop Proceedings (CEUR-WS.org)
Proceedings
http://ceur-ws.org
ISSN 1613-0073
provides conjunction and a form of existential quantifica-
159
�tion called existential restrictions as concept constructors. Horn rules and Horn-ALC enjoys the canonical model
It can also state disjointness of concepts by the use of ⊥. property. To lift the method for EL⊥ to Horn-ALC two
EL⊥ has the canonical model property, i.e. there always extensions of the logic need to be addressed:
exists a model that can be embedded into all other mod-
els. Thus testing whether α is entailed (i.e. holds in all • the more general form of negation and
models) can be done by computing the canonical model • forall quantification
and test whether α is satisfied in it. Reasoning in EL⊥
can be done in polynomial time [8]. We address the latter by investigating ELI ⊥ , which ex-
To compute the canonical model in classical EL⊥ , the tends EL⊥ by inverse roles which, in turn, can express
ontology is normalized such that complex concepts get value restrictions as consequences.
assigned a name. The domain of the canonical model con- The goal of this paper is to develop a characterization
sists of a representative for each of the named concepts. of defeasible entailment (and thus of defeasible subsump-
The canonical models are a main building block of the tion) that alleviates quantification neglect and provides
typicality model used for to characterize the semantics reasoning of rational strength. To that end we proceed
of defeasible reasoning in EL⊥ . as it was done in [6] for EL⊥ . First we develop a char-
Typicality interpretations used for defeasible reason- acterization of entailment under rational strength and
ing have 2-dimensional domains. One dimension is the propositional coverage. From this we develop a char-
representative domain, which coincides with the domain acterization of entailment under rational strength and
of the classical canonical model. The other dimension is nested coverage.
determined by which subsets of the DBox D are “applied”
to the elements. Each element of the typicality domain Entailment under rational strength and proposi-
for EL⊥ is a pair of a concept name and a subset of D . tional coverage in ELI ⊥ . The first step to lift the
Now, the use of different collections of subsets from technique from [6] to ELI ⊥ is to adapt the typicality
D induces different strengths of reasoning. The use domain. We use for the first dimension the representa-
of a chain of subsets given by the exceptionality chain tive domain for ELI ⊥ . The classical canonical model for
computed according to [9] gives reasoning of rational ELI ⊥ uses sets of concept names as domain elements,
strength. This chain would always include the empty since the combination of existential restrictions and value
set indicating that no defeasible information needs to restrictions can cause conjunctions for which no name
be satisfied. (To achieve reasoning of relevant strength exists in the DKB. For instance, when ∃r.E and ∀r.F get
the whole lattice of subsets of D is used.) Besides the combined, there need not be a name for the concept E ⊓ F
parameter for strength of reasoning, the semantics is also that the r-successor belongs to. This extended represen-
determined by the parameter of coverage. Coverage of tative domain makes several of the technical construc-
reasoning, which determines whether defeasible infor- tions for EL⊥ more involved for ELI ⊥ . It also incurs an
mation is only “applied” to the root object of a concept increase of computational complexity from polynomial
(and not necessarily to the objects in its relational neigh-
time to ExpTime for reasoning already in for classical
borhood) or to all objects in the relational neighborhood reasoning [8].
of a concept. The first is called propositional strength The second dimension of the typicality domain for
ELI ⊥ is—as before—the exceptionality chain computed
and the latter is called nested strength. Different forms of
coverage of reasoning are induce by the relational struc- according to [9]. This gives the domain for rational
ture on the domain, i.e. by forcing successors to be as strength reasoning in ELI ⊥ in general. It is the rela-
typical as possible or not forcing this. tional structure on the typicality domain that determines
Reasoning of propositional strength is mainly of inter- the coverage of reasoning. In case of propositional cov-
est to us to be able to compare the resulting inference erage, we extend the minimal typicality models for EL⊥
relation to materialization-based reasoning. Reasoning to the use of inverse roles.
under nested coverage results in an inference relation In minimal typicality models, the root element belong-
that does not cause quantification neglect. ing to a named concept can have any degree of typicality
admitted by the domain, i.e. it can satisfy any subset of
The results presented in this extended abstract are DCIs available in the (second dimension of the) typicality
initial steps on a longer research path. We want to inves- domain. The elements that are in the relational neighbor-
tigate defeasible reasoning by means of typicality models hood of this root element, however, do not need to satisfy
for defeasible Horn-ALC . This DDL is fairly expressive, any of the defeasible information. Therefore every role
as (non-Horn) ALC is propositionally complete and ad- successor necessitated by existential restrictions for roles
mits the use of both quantifiers. For all quantification or their inverse, are elements from the typicality domain,
can be captured by the concept constructor called value where the second component is empty, i.e. where no DCI
restriction. Horn-ALC restricts ALC to GCIs that are needs to be satisfied.
160
� We show that defeasible subsumption w.r.t. a ELI ⊥ and that does not omit defeasible information unless a
DKB and under rational strength and propositional cov- contradiction is encountered.
erage can be decided by testing satisfaction of it in the
Currently we are working on typicality models that can
rational minimal typicality model alone.
achieve reasoning of relevant strength. We need to
see whether a mere change of the underlying typical-
Entailment under rational strength and nested cov- ity domain—the full lattice P (D) instead of the excep-
erage in ELI ⊥ . The characterization of nested ratio- tionality chain—is enough to for this or whether new
nal reasoning for EL⊥ is achieved by means of maximal techniques in comparison to [6] are required. Also, a
typicality models. The idea for this kind of models is that comparison between the resulting inference relations for
not only the root element of a concept is as typical as it ELI would be a asset to understand defeasible reason-
⊥
gets, but that also all the elements that the root element ing in DDLs better. In the long run, it is interesting to
is connected to via (inverse) roles are. Maximal typicality extend these results to the DDL Horn-ALC .
models use the same typicality domain as their minimal
counterparts. The generation of maximal typicality mod-
els is done by a fixed-point construction starting from the
minimal typicality model. It successively makes elements Acknowledgments
that a role edge starts from or ends in more typical, i.e.
reconnects at an element in the typicality domain that This study financed in part by the Coordenação de
represents the same set of named concepts, but is coupled Aperfeiçoamento de Pessoal de Nível Superior – Brasil
with a bigger subset of D . The fixed-point construction (CAPES) – Finance Code 001 and also by the Conselho
proceeds in two steps in every round: Nacional de Desenvolvimento Científico e Tecnológico
(CNPq) and by the AI competence center ScaDS.AI Dres-
1. identify an edge in the active set of models that den/Leipzig.
can be upgraded to a more typical successor or
predecessor and upgrade that edge
References
2. for the obtained interpretation, restore it to be a
model of the DKB again [1] L. Giordano, V. Gliozzi, N. Olivetti, G. L. Pozzato,
Preferential description logics, in: N. Dershowitz,
This construction operates on a set of models, where
A. Voronkov (Eds.), Logic for Programming, Artifi-
only the ones with elements that are maximally typical
cial Intelligence, and Reasoning, 14th International
are kept. From this set the maximal typicality model
Conference, LPAR, 2007, Proceedings, volume 4790
is obtained as the one model capturing the information
of LNCS, Springer, 2007, pp. 257–272.
common to all models in the set.
[2] L. Giordano, V. Gliozzi, N. Olivetti, G. L. Pozzato,
The major technical challenge for defining an upgrade
Reasoning about typicality in preferential descrip-
method for ELI ⊥ is that here the element that causes an
tion logics, in: European Workshop on Logics in
edge in the model and the role predecessor of that edge
Artificial Intelligence, Springer, 2008, pp. 192–205.
need no longer coincide as it is the case in EL⊥ . This
[3] K. Britz, J. Heidema, T. Meyer, Modelling object
required a much more elaborate technique for upgrading
typicality in description logics, in: Australasian Joint
the models.
Conference on Artificial Intelligence, Springer, 2009,
Our main result is that defeasible subsumption w.r.t.
pp. 506–516.
a ELI ⊥ DKB and under rational strength and nested
[4] K. Britz, T. Meyer, I. Varzinczak, Semantic foundation
coverage can be decided by testing satisfaction of it in
for preferential description logics, in: Australasian
the rational maximal typicality model alone. This es-
Joint Conference on Artificial Intelligence, Springer,
tablishes the computation of rational maximal typicality
2011, pp. 491–500.
models as the main step in the decision procedure for
[5] P. A. Bonatti, M. Faella, I. M. Petrova, L. Sauro, A
entailment (and subsumption) for ELI ⊥ that does not
new semantics for overriding in description logics,
commit quantification neglect.
Artificial Intelligence 222 (2015) 1–48.
We also investigate the relationship between the
[6] M. Pensel, A.-Y. Turhan, Reasoning in the defeasible
materialization-based semantics and the one given by
description logic E L⊥ —computing standard infer-
nested rational reasoning realized by maximal typicality
ences under rational and relevant semantics, Interna-
models. We show that the latter semantics indeed yields
tional Journal of Approximate Reasoning (IJAR) 103
consequences that are a superset of the consequences
(2018) 28–70. doi:https://doi.org/10.1016/j.
obtained by the materialization-based semantics.
ijar.2018.08.005.
By these results we have provided a method to decide
entailment in DDLs that admit the use of both quantifiers
161
�[7] M. Pensel, A.-Y. Turhan, Including quantification in
defeasible reasoning for the description logic E L⊥ ,
in: M. Balduccini, T. Janhunen (Eds.), Proceedings
of the 14th International Conference on Logic Pro-
gramming and Nonmonotonic Reasoning - LPNMR,
Springer, 2017, pp. 78–84. doi:https://doi.org/
10.1007/978-3-319-61660-5_9.
[8] F. Baader, S. Brandt, C. Lutz, Pushing the E L
envelope, in: L. P. Kaelbling, A. Saffiotti (Eds.),
IJCAI-05, Proceedings of the Nineteenth Interna-
tional Joint Conference on Artificial Intelligence,
Professional Book Center, 2005, pp. 364–369. URL:
http://ijcai.org/Proceedings/05/Papers/0372.pdf.
[9] G. Casini, T. Meyer, K. Moodley, R. Nortjé, Rele-
vant closure: A new form of defeasible reasoning for
description logics, in: Proceedings of the 14th Euro-
pean Conference on Logics in Artificial Intelligence
(JELIA’14), 2014, pp. 92–106.
162
�