=Paper=
{{Paper
|id=None
|storemode=property
|title=Abduction in Description Logics using Formal Concept Analysis and Mathematical Morphology: Application to Image Interpretation
|pdfUrl=https://ceur-ws.org/Vol-959/paper_short1.pdf
|volume=Vol-959
|dblpUrl=https://dblp.org/rec/conf/cla/AtifHB11
}}
==Abduction in Description Logics using Formal Concept Analysis and Mathematical Morphology: Application to Image Interpretation==
https://ceur-ws.org/Vol-959/paper_short1.pdf
Abduction in Description Logics using Formal Concept
Analysis and Mathematical Morphology: Application to
Image Interpretation
Jamal Atif1 , Céline Hudelot2, and Isabelle Bloch3
1. Université Paris Sud, LRI - TAO, Orsay, France jamal.atif@lri.fr
2. Ecole Centrale de Paris, France, celine.hudelot@ecp.fr
3. Telecom ParisTech - CNRS LTCI, Paris, France
isabelle.bloch@telecom-paristech.fr
Abstract. We propose an original way of enriching Description Logics with ab-
duction reasoning services by computing the best explanations of an observation
through mathematical morphology (using erosions) over the Concept Lattice of a
background theory. The intended application is scene understanding and spatial
reasoning.
Keywords: Abduction, Description Logics, FCA, Mathematical Morphology,
Scene Understanding.
1 Introduction and notations
Scene interpretation can benefit from prior knowledge expressed as ontologies and from
description logics (DL) endowed with spatial reasoning tools as illustrated in our pre-
vious work [5, 6]. The challenge in this work was to derive reasoning tools that are able
to handle in a unified way quantitative information supplied by the image domain and
qualitative pieces of knowledge supplied by the ontology level. Object recognition and
interpretation are seen as the satisfiability of a current situation (spatial configuration)
encoded in the ABox of the DL and its TBox part. However, when the expert knowledge
is not crisply consistent with the observations, which is common in image interpreta-
tion, then this approach does not apply or leads to inconsistent results. Adapting DL
reasoning tools to such situations can be performed using abduction. Our aim is thus to
compute the “best explanation” to the observed phenomena in such situations. Formally,
given a background theory K representing the expert knowledge and a formula C rep-
resenting an observation on the problem domain, abductive reasoning searches for an
explanation formula D such that D is satisfiable w.r.t. K and it holds that K |= D → C
(K ∪ D |= C). We propose to add abductive reasoning tools to DL by associating ingre-
dients from mathematical morphology, DL and Formal Concept Analysis (FCA), and
by computing the best explanations of an observation through algebraic erosion over
the concept lattice of a background theory which is efficiently constructed using tools
from FCA. We show that the defined operators satisfy important rationality postulates
of abductive reasoning.
Based on the TBox T and the ABox A parts of a knowledge base K, we consider
ABox abduction [3]: if for every a ∈ A it holds that K 6|= ¬a, an ABox Abduction Prob-
lem, denoted as hK, Ai, consists in finding a set of assertions γ such that K ∪ γ |= A.
2 Atif, Hudelot and Bloch
The set γ (consistent with K) is said to be an explanation of A. Explanatory reason-
ing is concerned with preferred explanations rather than just plain explanations. So,
explaining an observation requires that some formulas must be “selected” as preferred
explanations.
We also rely on classical notions of (FCA), and denote a formal context by K =
(G, M, I), where G is the set of objects, M the set of attributes and I ⊆ G × M a
relation between the objects and attributes. For X ⊆ G and Y ⊆ M , the derivation
operators are denoted by α and β, with α(X) = {m ∈ M | ∀g ∈ X, (g, m) ∈ I},
and β(Y ) = {g ∈ G | ∀m ∈ Y, (g, m) ∈ I}. The concept lattice is defined from the
classical partial ordering (X1 , Y1 ) ≤ (X2 , Y2 ) ⇔ X1 ⊆ X2 (⇔ Y2 ⊆ Y1 ).
Links between FCA and DL can be formalized via the notion of semantic context
KT := (G, M, I) defined as [1]: G := {(I, d) | I is a model of T and d ∈ ∆I }, M :=
{m1 , . . . , mn }, and I := {((I, d), m) | d ∈ mI }, where I = (∆I , .I ) denotes an
interpretation. The lattice can be constructed using the distributive concept exploration
algorithm [9].
2 Abduction Operators from Mathematical Morphology on
Complete Lattices
Let (L, ) and (L′ , ′ ) be two complete lattices (which do not need to be equal). An
operator δ : L → L′ is a dilation if it commutes with the supremum. An operator
ε : L′ → L is an erosion if it commutes with the infimum. Classical properties of
mathematical morphology operators on complete lattices can be found in [4, 8].
Here, with the aim of performing ABox abduction, we would like to reason on sub-
sets of G in order to find their best explanations (in G). Hence we consider the complete
lattice (P(G), ⊆) and operations from P(G) into P(G), where P(G) is the set of sub-
sets of G. Since the ordering on G is equivalent to the one of M , reasoning on G will di-
rectly lead to results on M . In order to define explicit operations on P(G), we will make
use of particular erosions and dilations, called morphological ones [8], which involve
the notion of structuring element, i.e. a binary relation b between elements of G. For
g ∈ G, we denote by b(g) the set of elements of G in relation with g. It can be typically
derived from a distance d: b(g) = {g ′ ∈ G | ∃X ∈ P(G), g ′ ∈ X, d({g}, X) ≤ 1}.
The morphological erosion of X is then expressed as εb (X) = {g ∈ G | b(g) ⊆ X}.
Defining b from a distance is particularly interesting in the context of abduction, where
the “most central” parts of models will have to be defined. Erosion is then expressed as
εn (X) = {g ∈ G | d(g, X C ) > n}, where X C denotes the complement of X in G.
Here G is a discrete finite space, and therefore only integer values of n are considered.
All classical properties of mathematical morphology hold in this framework.
Last Non-empty Erosion. As shown in [2] in the framework of propositional logic,
erosions can be used to find explanations. In this context, the idea was to find the most
central part of a formula as the best explanation. This approach was shown to have good
properties with respect to rationality postulates of abductive reasoning [7]. In this paper,
we propose similar ideas, but adapted to the context of concept lattices, using erosions
as defined above. For any X ⊆ G, we define its last erosion as εℓ (X) = εn (X) ⇔
Abduction in DL using FCA 3
εn (X) 6= ∅, and ∀m > n, εm (X) = ∅. This last non-empty erosion defines the subset
of models in G that are the furthest ones from the complement of X (according to the
distance d), i.e. the most central in X.
Definition 1 Let A be a set of ABox assertions. A preferred explanation γ of A is de-
def
fined from the last non-empty erosion as A⊲ℓne γ ⇔ γ I ⊆ εℓ (AI ). In this equation,
AI should be understood as the extent of the semantic concept associated with the DL
concept A. When a constraint (e.g. a set of hypotheses belonging to the backgroud the-
def
ory) H has to be introduced, then this definition is modified as A ⊲ℓne γ ⇔ γI ⊆
εℓ (HI ∩ AI ).
Starting from the subset to be explained, performing successive erosions amounts
to “go down” in the lattice as much as possible, in order to find a non-empty set of
interpretations.
Last Consistent Erosion. Another idea to introduce the constraint H is to erode it, as
soon as it remains consistent with A. This leads to a second explanatory relation.
Definition 2 A preferred explanation γ of A is defined from the last consistent erosion
def
as: A ⊲ℓc γ ⇔ γ I ⊆ εℓc (HI , AI ) ∩ AI , where AI corresponds to the extent of
the semantic context and εℓc is the last consistent erosion defined as εℓc (HI , AI ) =
εn (HI ) where n = max{k | εk (HI ) ∩ AI 6= ∅}.
Here we consider erosion of H (i.e. HI ) alone, which means that we are looking at the
subsets (submodels) of the models of A while being the most in the constraint.
Properties and interpretations. A first important property is that reasoning on G ac-
tually amounts to reason on the whole formal context. Here, explanations where defined
from ABox reasoning, leading to erosions of subsets of G (models). Let (X, Y ) be a
formal concept, with X ⊆ G and Y ⊆ M . From the definitions of explanations of X,
we can derive directly the corresponding concepts for Y , using the derivation opera-
tor, i.e. α(γ) = {m ∈ M | ∀g ∈ γ, (g, m) ∈ I}. Note that eroding X amounts to
dilate Y , which is in accordance with the correspondence between the Galois connec-
tion property between derivation operators and the adjunction properties of dilation and
erosion. Let us now consider the rationality postulates introduced in [7] for explanation
relations. It has been proved that most of them hold for explanations derived from last
non-empty erosion and from last consistent erosion [2]. These results extend to the DL
context as follows:
- Both ⊲ℓne and ⊲ℓc are independent of the syntax (since they are computed on
models).
- Definitions are consistent in the sense that K 6|= ¬A iff ∃γ, A ⊲ γ.
- A reflexivity property holds for both definitions: if A ⊲ γ, then γ ⊲ γ.
- Disjunctions of explanations: if A ⊲ γ and A ⊲ δ, then A ⊲ (γ ⊔ δ), for both defi-
nitions. This means that if there are several possible explanations, their disjunction
is an explanation as well, which is an expected result.
4 Atif, Hudelot and Bloch
- Disjunction on the left: if C⊲ℓc γ and D⊲ℓc γ, then (C ⊔ D)⊲ℓc γ (since the erosion
is always performed on HI ). However this property does not hold for ⊲ℓne since
erosion does not commute with the supremum.
- For the same reasons, we have the following property for ⊲ℓc : if C ⊲ℓc γ and
D ⊲ℓc δ, then (C ⊔ D) ⊲ℓc γ or (C ⊔ D) ⊲ℓc δ, but it does not hold for ⊲ℓne .
- For conjunctions, we have a monotony property for ⊲ℓc : if C ⊲ℓc γ and γ I ⊆ DI
(i.e. D |= γ), then (C ⊓ D) ⊲ℓc γ. For ⊲ℓne , only a weaker form holds: if C ⊲ℓne γ
and D ⊲ℓne γ, then (C ⊓ D) ⊲ℓne γ. Note that this weaker form is also very natural
and interesting.
Since both ⊲ℓne and ⊲ℓc operators perform erosion in the interpretation set ∆I ,
any solution belongs then to this set and K is a model of the obtained solution. Hence
we have the following theorems:
- Soundness: If ∃γ | A ⊲ γ then K |= γ.
- Completeness: K |= γ ⇒ ∃A | K |= A : A ⊲ γ.
3 Conclusion
With the aim of image interpretation, we have proposed abductive inference services
in DL based on mathematical morphology over concept lattices, whose construction is
based on exploiting the advances of using FCA in DL. The properties and interpreta-
tions of the introduced explanatory operators were analyzed, and the rational postulates
of abductive reasoning were stated and extended to our context. Future work will con-
cern the complexity analysis of these operators and associated algorithms, and a deeper
investigation of their applications to image interpretation.
References
1. F. Baader. Computing a minimal representation of the subsumption lattice of all conjunctions
of concepts defined in a terminology. In Knowledge Retrieval, Use and Storage for Efficiency:
1st International KRUSE Symposium, pages 168–178, 1995.
2. I. Bloch, R. Pino-Pérez, and C. Uzcátegui. Explanatory Relations based on Mathematical
Morphology. In ECSQARU 2001, pages 736–747, Toulouse, France, sep 2001.
3. C. Elsenbroich, O. Kutz, and U. Sattler. A case for abductive reasoning over ontologies. In
OWL: Experiences and Directions, Athens, Georgia, USA, 2006.
4. H. J. A. M. Heijmans and C. Ronse. The Algebraic Basis of Mathematical Morphology –
Part I: Dilations and Erosions. Computer Vision, Graphics and Image Processing, 50:245–
295, 1990.
5. C. Hudelot, J. Atif, and I. Bloch. Fuzzy spatial relation ontology for image interpretation.
Fuzzy Sets and Systems, 159(15):1929–1951, 2008.
6. C. Hudelot, J. Atif, and I. Bloch. Integrating bipolar fuzzy mathematical morphology in
description logics for spatial reasoning. In European Conference on Artificial Intelligence
ECAI 2010, pages 497–502, Lisbon, Portugal, August 2010.
7. R. Pino-Pérez and C. Uzcátegui. Jumping to Explanations versus jumping to Conclusions.
Artificial Intelligence, 111:131–169, 1999.
8. J. Serra. Image Analysis and Mathematical Morphology. Academic Press, New-York, 1982.
9. G. Stumme. Distributive concept exploration–a knowledge acquisition tool in formal concept
analysis. In KI-98: Advances in Artificial Intelligence, pages 117–128. Springer, 1998.