Interpolation is a strategy for deriving plausible conclusions based on background knowledge about a particular kind of conceptual relatedness. Specifically, we say that a concept B is between the concepts A1, ..., An if natural properties that hold for each of the concepts A1, ..., An are likely to hold for the concept B as well. In the context of description logics, such conceptual betweenness relations allow us to infer plausible concept inclusions. In previous work, two semantics have been proposed for characterising this interpolation mechanism: a feature-based semantics inspired by formal concept analysis and a geometric semantics inspired by conceptual spaces. While interpolation is sound under both semantics, their motivation has to some extent been ad hoc. Taking a di↵erent approach, in this paper we start from ternary betweenness relations, defined on triples of individuals, and we impose certain desirable properties on such relations. As our main result, we show a close correspondence between the feature based semantics and the proposed semantics based on betweenness relations.
Description logics are used to characterise concepts in terms of their logical
relationships to other concepts. Despite having many advantages, such logic-based
formalisations lack some of the flexibility of vector representations, especially
with respect to supporting inductive generalisation. For instance, suppose we
know that banana, apple and kiwi are types of fruit, and suppose we are given
vector representation of these entities, as well as vector representations of other
entities such as orange. By observing that the representation of orange is located
in the same region of the vector space as banana, apple and kiwi, we can then
infer that oranges are likely to be fruit as well. This view of inductive
generalization in terms of vector space similarity has been extensively studied in cognitive
science [
mechanism available for flexible reasoning with description logic ontologies. The
key idea is to rely on a type of conceptual relationship which we call conceptual
betweenness: we say that A is between the concepts B1 and B2, written A v
B1 ./ B2, if properties that are true for both B1 and B2 can be expected to be
true for A as well. We are concerned with defining a suitable semantics for ./ ,
such that from A v B1 ./ B2, B1 v C and B2 v C, we can derive A v C,
provided that C is natural in some sense. We refer to this inference pattern
as interpolation1. Note that the notion of naturalness is common in theories of
induction [
In [
tweenness relations, and we discuss a number of natural properties that such relations should ideally satisfy.
enriched semantics from [
The paper is structured as followed. In the next section, we recall the logic E L./
from [
with the aim of supporting interpolation.
concepts of the form C ./ D, describing the set of objects that are between the concepts C and D. Further, E L./ includes countably infinite but disjoint sets of concept names NC and role names NR, where NC contains a distinguished infinite set of natural concept names NCNat. The syntax of E L ./ concepts C, D is defined by the following grammar, where A 2NC, A0 2NCNat and r 2NR: C, D := > | A | C u D | 9 r.C | N N, N 0 := A0 | N u N 0 | N ./ N 0 (1) (2)
set of concept inclusions C v D, where C, D are E L ./ concepts.
Feature-Enriched Semantics The semantics of E L./ can be defined in terms of
feature-enriched interpretations, which extend standard first-order
interpretations by also specifying a mapping ⇡ from individuals to sets of features F . The
intuition is that these features characterise concepts at a suciently fine-grained
level to capture similarity in a way that is sucient for modelling inductive
generalisation. Note that this is a common approach for representing concepts in
cognitive science [
Formally, a feature-enriched interpretation is a tuple I = (I, F , ⇡ ) in which I = ( I , ·I ) is a classical DL interpretation, F is a non-empty finite set of features and ⇡ is a mapping assigning to every d 2 I a proper subset of F such that the following hold: 1. For each d 2 2. for each F ⇢ F
I it holds that ⇡ (d) ⇢ F ; there exists some individual d 2
I such that ⇡ (d) = F .
usual [
' I(C) = \{⇡ (d) | d 2CI }.
(N ./ N 0)I = {d 2
I | ' I(N ) \ ' I(N 0) ✓ ⇡ (d)}.
Intuitively, (N ./ N 0)I contains those elements from I that have all the features that N and N 0 have in common. Note that for any individual d we have required ⇡ (d) 6= F . This is useful because it implies that ' I(C) = F i↵ CI = ; . A feature-enriched interpretation I = (I, F , ⇡ ) satisfies a concept inclusion C v D if CI ✓ DI. I is a model of an E L ./ TBox T if it satisfies all CIs in T and for every natural concept N in T , it holds that
N I = {d 2
I | ' I(N ) ✓ ⇡ (d)} (3) i.e. N is fully specified by its features. If (3) is satisfied, we say that N is natural in I. It is easy to verify that (3) is satisfied for a complex natural concept, as soon as it is satisfied for its constituent natural concept names. Note that for natural concepts C and D we have that C v D is satisfied i↵ ' I(D) ✓ ' I(C). 3
extends E L. In the feature-enriched semantics, all proper subsets F ⇢ F are witnessed, in the sense that there is some d such that ⇡ (d) = F . As shown below, it turns out that this assumption is too restrictive when ? is added to the language. First, we define satisfiability: a concept C is satisfiable w.r.t. a TBox T if there is a model I of T such that CI 6= ; .
Example 1. The concept B cannot be satisfied w.r.t. {B v A ./ C, A u B v ? , B u C v ?} using a feature-enriched interpretation. Indeed, from A u B v ? and B u C v ? , we find ' I(A) [ ' I(B) = ' I(C) [ ' I(B) = F and thus (' I(A) \ ' I(C)) [ ' I(B) = F . However, from B v A ./ C we find ' I(A) \ ' I(C) ✓ ' I(B). Together we thus find ' I(B) = F or equivalently BI = ; .
concept B to be between the concepts A and C if all these concepts are disjoint.
Definition 1. An abstract feature-enriched interpretation is a tuple I = (I, F , ⇡ ) s.t. ( I , ·I ) is a classical DL interpretation, F is a finite set of features, and ⇡ : I ! 2F such that ⇡ (d) ⇢ F for all d 2 I .
Abstract feature-enriched interpretations thus generalise feature-enriched interpretations by no longer requiring that all subsets X of F are witnessed, in the sense that there is some individual x such that ⇡ (x) = X. The abstract featureenriched semantics is then defined as before, where abstract feature-enriched interpretations are used instead of feature-enriched interpretations. Notably, the following properties of the feature-enriched semantics, which are required for making some plausible inferences, remain satisfied for abstract feature-enriched interpretations.
Proposition 1 (Interpolation). Let I = (I, F , ⇡ ) be an abstract featureenriched interpretation, satisfying C v X and D v Y . Then I also satisfies C ./ D v X ./ Y . Proposition 2. For any abstract feature-enriched interpretation I and any concepts C and D it holds that
' I(C ./ D) = ' I(C) \ ' I(D)
are no longer satisfied for abstract feature-enriched interpretations. First, we no longer have that ' I(C u D) = ' I(C) [ ' I(D) in general, even when C and D are natural concepts, as the following counterexample illustrates. Example 2. Let the abstract feature-enriched interpretation I = (I, F , ⇡ ) be defined as I = {x1, x2, x3, x4}, F = {f1, f2, f3, f4, f5} and ⇡ (x1) = {f1, f2}
CI = {x1, x2} ⇡ (x2) = {f2, f3, f4}
DI = {x2, x3}
⇡ (x3) = {f3, f5}
Then we have ' I(C) = {f2}, ' I(D) = {f3} and ' I(C u D) = {f2, f3, f4}.
The fact that C uD may have features beyond those of C and D intuitively makes
sense. From a practical point of view, however, the fact that ' I(C u D) cannot
be determined from ' I(C) and ' I(D) limits the kinds of plausible inferences
we can make. For instance, this means that we can no longer infer B u X v Y
from A u X v Y , C u X v Y and B v A ./ C, with all concepts assumed to be
natural. This means in particular that a notion of non-interference, restricting
how X and A ./ C interact, would need to be added to the language, similar to
what was done for the geometric semantics in [
However, we still have that C u D is natural in I whenever C and D are natural.
Proposition 3. Let I = (I, F , ⇡ ) be an abstract feature-enriched interpretation. If N is a natural concept, as defined by (2), then it holds that N is natural in I, in the sense of (3).
which subsets of F are witnessed. First, let us consider the following condition, which intuitively states that for all individuals x and y there must be some individual that is in-between.
Definition 2 (Downward closure). An abstract feature-enriched interpretation I = (I, F , ⇡ ) satisfies downward closure if for all x, y 2 I there exists an individual z 2 I such that ⇡ (z) = ⇡ (x) \ ⇡ (y).
Definition 3 (Upward closure). An abstract feature-enriched interpretation I = (I, F , ⇡ ) satisfies upward closure if for all x, y 2 I there exists an individual z 2 I such that ⇡ (z) = ⇡ (x) [ ⇡ (y).
particular, requiring upward closure restores the equality between ' I(C u D) and ' I(C) [ ' I(D).
Proposition 4. Suppose that I = (I, F , ⇡ ) satisfies upward closure. Then for natural concepts C and D it holds that
' I(C u D) = ' I(C) [ ' I(D)
is satisfiable.2 For this reason, upward closure does not seem to be a desirable property. Downward closure, on the other hand, will play an important role in this paper. The main consequence of imposing downward closure is stated in the following proposition, which essentially says that each non-empty natural concept C has a prototype when downward closure is satisfied.
Proposition 5. Suppose that I = (I, F , ⇡ ) satisfies downward closure. If concept C is natural in I and CI 6= ; , then there exists some x 2 CI such that ⇡ (x) = ' I(C). (4) (5) 4
are between instances of C and instances of D. However, the feature-enriched semantics only captures this intuition indirectly, and it is unclear which unintended consequences this semantics might have (beyond the issue already identified in
directly built from a ternary betweenness relation over the set of individuals.
Definition 4. An abstract betweenness interpretation is a tuple I = (I, bet) such that ( I , ·I ) is a classical DL interpretation and bet ✓ I ⇥ I ⇥ I .
tions from Definition 4 as “abstract” interpretations, to highlight that we will need to impose some further conditions, in this case on the relation bet, to ensure that the semantics behaves in an intuitive way. The semantics of in-between concepts is now defined as follows: (C ./ D)I = CI [ DI [ { y 2
I | 9 x 2CI, z 2DI . bet(x, y, z)}
CI = (C ./ C)I
2 It also follows that there is some feature f such that f 2 / ⇡ (x) for all x 2 (5) can indeed be seen as capturing the idea of convexity: any individual which is between individuals from CI must itself also belong to CI. Satisfaction is defined as before. The following result follows trivially from the definition of the abstract betweenness semantics, without requiring any additional conditions. Proposition 6 (Interpolation). Let I = (I, bet) be an abstract betweenness interpretation satisfying T = {C1 v D1, C2 v D2}. Then I also satisfies (C1 ./ C2) v (D1 ./ D2).
Proposition 7. Let I = (I, bet) be an abstract betweenness interpretation. If C and D are natural in I then C u D is natural in I as well. 4.1
Conditions on Betweenness Relations
Definition 5. The pair ( I , bet) is called a betweenness space if the following
conditions are satisfied [
Left-reflexivity 8 x, y 2 I . bet(x, x, y).
Symmetry 8 x, y, z 2 I . bet(x, y, z) , bet(z, y, x).
Transitivity1 8 x, y, z, u 2 I . bet(x, y, z) ^ bet(x, z, u) ) bet(x, y, u). Transitivity2 8 x, y, z, u 2 I . bet(x, y, z) ^ bet(x, z, u) ) bet(y, z, u).
betweenness relations in [
Proposition 8. Let I = (I, bet) be an abstract betweenness interpretation. If bet satisfies symmetry, then for any concepts C and D, it holds that: (C ./ D)I = (D ./ C)I
Continuity 8 a1, a3, b1, b2, b3, c1, c3 2 I . bet(a1, b1, c1) ^ bet(a3, b3, c3) ^ bet(b1, b2, b3) ) 9 a2, c2 2 I . bet(a1, a2, a3) ^ bet(c1, c2, c3) ^ bet(a2, b2, c2).
Proposition 9. Let I = (I, bet) be an abstract betweenness interpretation such that bet satisfies continuity. If C and D are natural in I, it holds that C ./ D is natural in I as well.
Corollary 1. Let I = (I, bet) be an abstract betweenness interpretation such that bet satisfies continuity. If N is a natural concept, as defined by (2), it holds that N is natural in I, in the sense of (5).
Proposition 10. Let I = (I, bet) be an abstract betweenness interpretation such that bet satisfies left-reflexivity, symmetry and continuity. For all natural concepts A, B, C it holds that:
((A ./ B) ./ C)I = (A ./ (B ./ C))I
Corollary 2. Let I = (I, bet) be an abstract betweenness interpretation such that bet satisfies left-reflexivity, symmetry and continuity. For all natural concepts A, B, C, D it holds that:
I |= {B v A ./ C, C v A ./ D} )
I |= B v A ./ D
Non-triviality 8 x 2
I . 9 y 2
I . ¬bet(y, x, y).
Note that acyclicity implies non-triviality, provided that | I | 2. 5
Let I = (I, bet) be an abstract betweenness interpretation. In Section 5.1, we first introduce a construction for deriving an abstract feature-enriched interpretation K = (I, F , ⇡ ) from I. In 5.2 we then discuss under what conditions the interpretations I and K are equivalent, in the sense that CI = CK for every concept C. Throughout the section, we assume that I is finite. 5.1
Construction Definition 6. We call a set of individuals A ✓ bet) if
8 x, z 2A . bet(x, y, z) ) y 2A It is easy to see that for every set A ✓ I , there must exist a smallest convex set which contains A, i.e. the least fixpoint of the following sequence, where A0 = A: I convex (w.r.t. the relation Ai+1 = Ai [ { y | 9 x, z 2Ai . bet(x, y, z)} (6)
We say that A is convex if A = CH(A). Let C be the set of all convex subsets of I . We associate with each convex set A 2 Ca feature fA and we define: F = {fA | A 2 C} ⇡ (x) = {fA | x 2A} (7) The following result shows that K = (I, F , ⇡ ) is an abstract feature enriched interpretation, provided that bet is non-trivial.
Proposition 11. I = (I, bet) be an abstract betweenness interpretation such that bet satisfies non-triviality and let ⇡ be defined as in (7). For each x 2 I there exists a feature f 2 F such that f 2/⇡ (x). 5.2
Equivalence Let us fix an abstract betweenness interpretation I = (I, bet) and let K = (I, F , ⇡ ), with F and ⇡ defined as in (7). We now analyse what conditions we need to impose on bet such that CI = CK for every concept C. If C is a standard E L concept, then we trivially have CI = CK = CI , hence the main question is about the interpretation of in-between concepts. Before studying when (C ./ D)I = (C ./ D)K, we first show that the natural concepts in I are also natural in K.
Lemma 1. It holds that CI is convex i↵ C is natural in I.
Lemma 2. Let A be a concept name and suppose that bet satisfies non-triviality. If A is natural in I then A is natural in K.
We now analyse under what conditions it holds that (C ./ D)I = (C ./ D)K. Lemma 3. Suppose that bet satisfies continuity, symmetry and left-reflexivity, and let A and B be convex sets. Then it holds that
CH(A [ B) = A [ B [ { y | 9 x 2A, z 2B . bet(x, y, z)} Lemma 4. Suppose that bet satisfies continuity, symmetry and left-reflexivity, and let C and D be concepts that are natural in K. If CI = CK and DI = DK, it holds that (C ./ D)I = (C ./ D)K.
Proposition 12. Suppose that bet satisfies continuity, symmetry, left-reflexivity and non-triviality. It holds that CI = CK for every E L./ concept C. 6
In this section, we start from an abstract feature-enriched interpretation K = (I, F , ⇡ ), from which we derive an abstract betweenness interpretation I = (I, bet) such that CK = CI for all concepts C. We again assume that I is finite. 6.1
Construction To define I = (I, bet), we only need to specify the relation bet. This relation is defined in terms of ⇡ as follows: bet(x, y, z) ⌘ ⇡ (y) ◆ ⇡ (x) \ ⇡ (z) (8)
reflexivity and symmetry. Moreover, this relation also satisfies transitivity1, since bet(x, y, z) and bet(x, z, u) mean that ⇡ (y) ◆ ⇡ (x)\ ⇡ (z) ◆ ⇡ (x)\ (⇡ (x)\ ⇡ (u)) = ⇡ (x) \ ⇡ (u), and thus bet(x, y, u). On the other hand, acyclicity is clearly not satisfied. As the following counter example shows, transitivity2 is not satisfied either.
⇡ (x) = ⇡ (z) = {f } ⇡ (y) = ⇡ (u) = {f, g}
Lemma 5. If K satisfies downwards closure, then the betweenness relation defined by (8) satisfies continuity.
imposing that F = Sx2 I ⇡ (x), i.e. by assuming that all of the features in F are actually used in some way. 6.2
Equivalence Let K = (I, F , ⇡ ) be an abstract feature-enriched interpretation, and let I = (I, bet) be the corresponding abstract betweenness interpretation, with bet defined as in (8). We find that CK = CI for all concepts C, provided that K satisfies downward closure. In particular, we can show the following results. Lemma 6. If C is natural in K then C is natural in I.
Lemma 7. Assume that K satisfies downwards closure and suppose that C and D are natural in K. If CK = CI and DK = DI then we also have that (C ./ D)K = (C ./ D)I.
Proposition 13. Suppose that K satisfies downward closure. It holds that CI = CK for every E L./ concept C.
complementary approaches for reasoning about similarity in a qualitative way.
The problem of formally combining logics and similarity is addressed in [
porating some form of defeasible reasoning. For example, Giordano et al. [
description logics with ideas from cognitive science, although their focus is on modelling typicality e↵ects and compositionality, e.g. inferring the meaning of pet fish from the meanings of pet and fish, which is a well-known challenge for cognitive systems since typical pet fish are neither typical pets nor typical fish. 8
We have provided a new semantics of in-between concepts, in terms of an abstract
ternary betweenness relation, and we have shown how this semantics is closely
related to the feature-enriched semantics from [