# a_description_logic_for_analogical_reasoning__e4d9b12c.pdf

A Description Logic for Analogical Reasoning

Steven Schockaert , Yazm ın Ib a nez-Garc ıa , V ıctor Guti errez-Basulto Cardiff University, UK {schockaerts1,ibanezgarciay, gutierrezbasultov}@cardiff.ac.uk

Ontologies formalise how the concepts from a given domain are interrelated. Despite their clear potential as a backbone for explainable AI, existing ontologies tend to be highly incomplete, which acts as a signiﬁcant barrier to their more widespread adoption. To mitigate this issue, we present a mechanism to infer plausible missing knowledge, which relies on reasoning by analogy. To the best of our knowledge, this is the ﬁrst paper that studies analogical reasoning within the setting of description logic ontologies. After showing that the standard formalisation of analogical proportion has important limitations in this setting, we introduce an alternative semantics based on bijective mappings between sets of features. We then analyse the properties of analogies under the proposed semantics, and show among others how it enables two plausible inference patterns: rule translation and rule extrapolation.

1 Introduction The last decade has witnessed an increasing interest in methods for automated knowledge base completion. While most work has focused on predicting plausible missing facts in knowledge graphs [Bordes et al., 2013; Yang et al., 2015; Trouillon et al., 2017; Balazevic et al., 2019], some authors have also looked at the problem of predicting plausible missing rules in ontologies [Beltagy et al., 2013; Bouraoui and Schockaert, 2019]. The underlying principle of these latter approaches is to rely on external knowledge about the similarity structure of concepts, typically in the form of a vector space embedding of concept names. The main idea is that knowledge about concepts can often be extended to concepts with a similar representation in the given vector space. The same principle also lies at the basis of rule-based frameworks with a soft uniﬁcation mechanism [Medina et al., 2004; Rockt aschel and Riedel, 2017]. However, these similarity based reasoning methods can clearly only provide us with knowledge that is similar to what is already in the knowledge base. Humans, on the other hand, can also infer plausible knowledge in more creative ways, where a particularly prominent role is played by the idea of reasoning by analogy. This

phenomenon has been extensively studied in cognitive science and philosophy [Gentner, 1983; Hofstadter et al., 1995; Holyoak and Thagard, 1997], but to the best of our knowledge, the use of analogical reasoning for completing ontologies has not yet been considered1

Within Artiﬁcial Intelligence, the formalisation of analogical reasoning typically builds on analogical proportions, i.e. statements of the form A is to B what C is to D [Bayoudh et al., 2007; Prade and Richard, 2014; Barbot et al., 2019]. A key result in this area has been the development of analogical classiﬁers, which are based on the principle that whenever the features of four examples are in an analogical proportion, then their class labels should be in an analogical proportion as well [Bayoudh et al., 2007; Hug et al., 2016]. The same principle can be applied to infer plausible concept inclusions, i.e. concept inclusions which are not entailed from a given TBox, but which are likely to hold given additional background knowledge that we have about analogical relationships between different concepts. The resulting inference pattern, which we call rule extrapolation, is illustrated in the next example.

Example 1 (Rule extrapolation). Suppose we have an ontology with the following concept inclusions:

Young Cat Cute (1) Adult Wild Cat Dangerous (2) Young Dog Cute (3)

Suppose we are furthermore given that Cat is to Wild Cat what Dog is to Wolf . Trivially, we also have that Young is to Adult what Young is to Adult and Cute is to Dangerous what Cute is to Dangerous Using rule extrapolation, we can then infer the following:

Adult Wolf Dangerous (4)

Analogies can also be used to infer plausible knowledge by allowing us to transfer knowledge from one domain to another. This is illustrated in the following example.

1We note that the term analogical reasoning has been used in the literature to refer to a form of similarity-based ontology completion [d Amato et al., 2006]. In contrast, we reserve this term for methods that require drawing parallels between different domains.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Example 2 (Rule translation). Suppose we are given the following knowledge:

Program speciﬁes.Software (5)

and the fact that Program is to Plan what Software is to Building . Then we can plausibly infer:

Plan speciﬁes.Building (6)

Ontologies often use the same templates to encode knowledge from different domains (e.g. knowledge about different professions). The strategy from Example 2 then allows us to complete the ontology by introducing additional domains. Using analogies for identifying plausible missing knowledge is appealing, because they can be learned from text quite effectively. For instance, Turney [2006] proposed a method for identifying similarities between pairs of words (i.e. analogical proportions) using matrix factorization and ternary cooccurrence statistics, which approximated the performance of an average US college applicant. Moreover, the GPT-3 language model is able to identify analogical word pairs with even higher accuracy [Brown et al., 2020]. To a more limited extent, some types of analogical relationships can also be obtained from word embeddings [Mikolov et al., 2013]. The main aim of this paper is to propose a semantics for modelling analogies within the setting of description logics, which introduces a number of unique challenges (see Section 3). We focus in particular on an extension of EL . We start from the semantics proposed by Ib a nez-Garc ıa et al. [2020], which extends the EL semantics by assigning to each individual a set of features. Their aim was to support another form of plausible inference, called interpolation (see Section 2). We show that having access to these features in the semantics also allows us to formalise analogies.2

2 Background

We start by introducing the Description Logic (DL) EL , which is a straightforward extension of the logic EL that was proposed in [Ib a nez-Garc ıa et al., 2020] to formalise rule interpolation3. Our approach to analogical reasoning in this paper will build on EL . Rule interpolation is another inference pattern for obtaining plausible missing concept inclusions in a DL ontology. Interpolation is based on the notion of betweenness, where a concept B is said to be between concepts A and C if B has all the natural properties that A and C have in common. In such a case, knowledge that holds for both A and C seems likely to hold for B as well. This inference pattern is illustrated in the next example.

Example 3 (Rule interpolation). Suppose we have the following concept inclusions:

Cat X Wolf X (7)

2An appendix with proofs of all results, as well as counterexamples for some claims, is available at https://arxiv.org/abs/2105.04620 3We include because disjointness will play an important role in this paper.

As long as X is a natural concept , it seems plausible that the following concept inclusion also holds:

This is because all the common (natural) properties of Cat and Wolf are also satisﬁed by Dog. In such a case, we say that the concept Dog is between the concepts Cat and Wolf. The notion of naturalness plays an important role in most philosophical accounts of induction. Intuitively speaking, a natural concept or property is one that admits inductive inferences. The semantics from [Ib a nez-Garc ıa et al., 2020] is based on the common view that natural concepts are those which can be characterised as a set of features (i.e. a conjunction of elementary properties) [Tversky, 1977]. Syntax The logic EL extends the standard DL EL with in-between concepts of the form C D, describing the set of objects that are between the concepts C and D. Further, EL includes an inﬁnite set of natural concept names. More precisely, consider countably inﬁnite but disjoint sets of concept names NC and role names NR, where NC contains a distinguished inﬁnite set of natural concept names NNat C . The syntax of EL concepts C, D is deﬁned by the following grammar, where A NC, A NNat C and r NR:

C, D := | | A | C D | r.C | N

N, N := A | N N | N N

Concepts of the form N, N are called natural concepts. An EL TBox is a ﬁnite set of concept inclusions C D, where C, D are EL concepts. Semantics The semantics of EL is given in terms of feature-enriched interpretations, which extend standard ﬁrstorder interpretations by also specifying a mapping π from individuals to sets of features. Formally, a feature-enriched interpretation is a tuple I = (I, F, π) in which I = ( I, I) is a classical DL interpretation, F is a ﬁnite set of features, and π : I 2F, such that the following hold: 1. For each d I it holds that π(d) F; 2. for each F F there exists some individual d I such that π(d) = F. For an EL concept C, CI is deﬁned as a pair CI, ϕ(C) where CI I and ϕ(C) is the set of all features associated with a concept C, deﬁned as:

ϕ(C) = \ {π(d) | d CI}

Intuitively, the set of features ϕ(C) describes the concept C at a ﬁner-grained level that what may be possible in the language. This makes it possible to capture knowledge about what different concepts have in common, which is needed in EL to model the semantics of in-between concepts. For a standard EL concept C, CI is deﬁned as usual [Baader et al., 2017]. For in-between concepts, I is deﬁned as follows.

(N N )I = {d I | ϕ(N) ϕ(N ) π(d)}.

Intuitively, (N N )I contains all elements from the domain that have all the features that are common to both N and N .

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

A feature-enriched interpretation I = (I, F, π) satisﬁes a concept inclusion C D if CI DI. I is a model of an EL TBox T if it satisﬁes all CIs in T and for every natural concept N in T , it holds that

N I = {d I | ϕ(N) π(d)} (8)

i.e. N is fully speciﬁed by its features. It is easy to verify that (8) is satisﬁed for a complex natural concept, as soon as it is satisﬁed for its constituent natural concept names. A concept C is satisﬁable w.r.t. a TBox T , if there is a model I of T such that CI = , F . The purpose of introducing features in the semantics of EL is to make explicit what different concepts have in common, and to use this as the basis for enabling a particular kind of inductive inference (i.e. interpolation). For instance, in the case of Example 3, if the concept inclusions in (7) are complemented with Dog Cat Wolf, it can be veriﬁed that Dog X can indeed be inferred (assuming all concept names are natural). In applications, knowledge about inbetween concepts would typically be induced from a vector space embedding. See, for instance, [Bouraoui and Schockaert, 2019] for a practical application of rule interpolation based on pre-trained word embeddings. In this paper, we will build on the feature-enriched semantics to encode correspondences between analogous domains.

3 Analogical Concepts

Analogical proportions are a central notion in the formalisation of analogical reasoning, going back to Aristotle (see [Barbot et al., 2019] for a historical perspective). While they can be deﬁned more generally, here we will focus on analogical proportions between sets. In particular, the sets S1, S2, S3, S4 are said to be in an analogical proportion, denoted as S1:S2 :: S3:S4 if S1 and S2 differ in the same way that S3 and S4 differ. Formally, S1:S2 :: S3:S4 is satisﬁed if:

S1 \ S2 = S3 \ S4 S2 \ S1 = S4 \ S3 (9)

Some key properties of analogical proportions are as follows:

Reﬂexivity A:B :: A:B

Symmetry (A:B :: C:D) (C:D :: A:B)

Exchange of means (A:B :: C:D) (A:C :: B:D)

S-transitivity (A:B :: C:D) (A:B :: E:F) (C:D :: E:F)

C-transitivity (A:C :: D:B) (A:E :: F:B) (C:E :: F:D)

3.1 Analogical Proportions between DL Concepts In this paper, we are concerned with analogies between description logic concepts. We can deﬁne analogical proportions between EL concepts A, B, C, D as AI:BI :: CI:DI or as ϕ(A):ϕ(B) :: ϕ(C):ϕ(D). In general these two expressions are not equivalent, and there are advantages in requiring that both of them are satisﬁed at the same time, which has been studied in detail in [Barbot et al., 2019] within the setting of Formal Concept Analysis. However, if A, B, C, D are natural, then AI:BI :: CI:DI and ϕ(A):ϕ(B) :: ϕ(C):ϕ(D) are equivalent. Moreover, for natural concepts, the semantic

constraint ϕ(A):ϕ(B) :: ϕ(C):ϕ(D) can be modelled syntactically in EL . Indeed it holds that ϕ(A):ϕ(B) :: ϕ(C):ϕ(D) is satisﬁed iff the following conditions are satisﬁed4:

ϕ(A) ϕ(D) = ϕ(B) ϕ(C) (10) ϕ(A) ϕ(D) = ϕ(B) ϕ(C) (11)

The analogical proportion ϕ(A):ϕ(B) :: ϕ(C):ϕ(D) is thus satisﬁed if the following concept inclusions are satisﬁed:

A D B C B C A D A D B C B C A D

In the following, we will write A:B :: C:D as an abbreviation for these four concept inclusions. The fact that we can model A:B :: C:D within EL is an advantage, but as we will see below, modelling analogies between DL concepts in this way has a number of important limitations.

3.2 Desiderata for Modelling Analogies in DLs Our motivation for studying analogies is to enable plausible inferences. A clear requirement is thus that we want some form of the rule extrapolation and rule translation inference patterns, as illustrated in Examples 1 and 2, to be satisﬁed. Another important requirement comes from the fact that we usually only have access to information about analogical relationships between concept names (e.g. obtained from a language model). However, the aforementioned inference pattern may rely on analogical relationships between complex concepts. To enable non-trivial inferences in practice, it is thus important that analogies between concept names can be lifted to analogies between complex concepts. Let us now consider the suitability of analogical proportions, in light of these desiderata. First, rule translation is satisﬁed for analogical proportions. Proposition 1. Let I = (I, F, π) be a feature-enriched interpretation, and let A1, A2, B1, B2 be natural concepts in I. If ϕ(A1):ϕ(A2) :: ϕ(B1):ϕ(B2) holds and I satisﬁes A1 B1, then I also satisﬁes A2 B2. However, rule extrapolation is not valid for analogical proportions. Furthermore, analogical proportions between concept names cannot be lifted to complex concepts. For instance, from A1:B1 :: C1:D1 and A2:B2 :: C2:D2, in general we cannot infer (A1 A2):(B1 B2) :: (C1 C2):(D1 D2). Counterexamples are provided in the appendix.

4 The Logic ELana Given the limitations of analogical proportions that were highlighted in Section 3.2, we propose an alternative approach for modelling analogies between description logic concepts. This approach is based on the common view that analogies are mappings from one domain into another, which lies among others at the basis of the seminal Structure Mapping framework [Gentner, 1983]. In particular, we propose the logic ELana , which extends EL with two novel elements: analogy assertions and intra-domain roles. Analogy

4This follows immediately from the characterisation of Boolean analogical proportions in terms of conjunction and disjunction; see [Prade and Richard, 2013] for details.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

assertions are similar to analogical proportions, in that they encode a relationship of the form A is to B what C is to D , but their semantics is deﬁned in terms of mappings between different domains, where domains will be identiﬁed with sets of features. Intuitively, intra-domain roles are roles which preserve the structure of analogous domains.

4.1 Syntax Let NC, NNat C and NR be deﬁned as before. We assume that NR contains an inﬁnite set NInt R of distinguished intra-domain role names. The syntax of ELana concepts C, D is deﬁned by the following grammar, where A NC, A NNat C , r NR and r NInt R :

C, D := | | A | C D | r.C | N

N, N := A | N N | N N | r .N

ELana concepts extend EL concepts by allowing existential restrictions over intra-domain roles as natural concepts. An ELana TBox is a ﬁnite set containing two types of assertions: (i) ELana concept inclusions, and (ii) analogy assertions of the form C1 D1::C2 D2, where C1, C2, D1, D2 are natural ELana concepts.

4.2 Semantics Analogies intuitively involve transferring knowledge from one domain to another domain5, e.g. from software engineering to architecture in the case of Example 2. In our framework, these domains will be associated with subsets of F. In particular, we will require that interpretations specify a partition [F1, ..., Fk] of F, deﬁning the different domains of interest. Some of the partition classes will furthermore be viewed as being analogous, in the sense that there is some kind of structure-preserving mapping between them. Another extension of the feature-enriched semantics is aimed at improving how disjointess can be modelled. In the semantics from [Ib a nez-Garc ıa et al., 2020], no individual d I is allowed to have all the features from F, but all proper subsets F F are witnessed in the sense that there is some d such that π(d) = F. This limits how disjoint concepts can be modelled. For instance, B cannot be satisﬁed w.r.t. {B A C, A B , A C , B C } using a feature-enriched interpretation. Disjointness will play an important role in our semantics, as concepts from different domains will be required to be disjoint (see below). For this reason, we extend the feature-enriched semantics with sets of forbidden feature combinations. In particular, interpretations will specify a set X 2F such that for X X, it holds that no individual can have all the features from X. For the ease of presentation, we write C for the set of all consistent sets of features, i.e. F C iff F X for all X X. We also write Ci for the restriction of C to subsets of Fi. Deﬁnition 1. Let [F1, ..., Fk] be a partition of a non-empty ﬁnite set F. We call I = (I, [F1, ..., Fk], X, π, , S) a domain constrained interpretation if I = ( I, .I) is a classical DL interpretation, X 2F, F X, π : I

5In this paper, we use the term domain to refer to a particular thematic area. This should not be confused with the set I, which is often referred to as the domain of the interpretation I.

2F, is an equivalence relation over {1, ..., k} and S = {σ(s,t) | (s, t) }, with each σs,t a bijection from Fs to Ft, and we have: 1. for every d I and X X it holds that X π(d); 2. if X C then π(d) = X for some d I;

3. we have σ 1 (s,t) = σ(t,s) and σ(t,u) σ(s,t) = σ(s,u) for any (s, t), (t, u) ; 4. for F Ci and (i, j) , we have {σ(i,j)(f) | f F} C; 5. if f Fi and g Fj then {f, g} X, for all (i, j) with i = j. Intuitively, each of the sets Fi corresponds to a different domain. If (s, t) , it means that there is an analogy between the source domain Fs and the target domain Ft. In that case, there is a one-to-one mapping σ(s,t) between the features from Fs and those from Ft. The ﬁrst two conditions from Deﬁnition 1 capture the fact that a set of features X F is witnessed by some individual iff it is consistent, i.e. X C. The third condition ensures that the mappings σ(i,j) can be composed and reversed. The fourth condition encodes that the mapping σ(i,j) maps consistent feature combinations to consistent feature combinations. This is a natural requirement, given the intuition that analogous domains should have the same structure. The last condition captures the requirement that individuals cannot have features from two analogous domains. While analogies are normally indeed deﬁned between distinct domains, the reader may wonder at this point whether this restriction is necessary. We will come back to this question in Section 4.4. Domain Translations Before presenting the semantics of analogy assertions, we ﬁrst study how the bijections σ(i,j) can be combined to deﬁne mappings between the sets of features ϕ(C), ϕ(D) associated with two concepts. First, we deﬁne a domain assignment mapping δ, which maps each concept C to the set of domains on which it depends:

δ(C) = {i | Fi ϕ(C) = }

Next, we extend the mappings σ(i,j) to mappings between sets of domains. Let U = {(s1, t1), . . . , (sl, tl)}, with s1, . . . , sl all distinct and t1, . . . , tl all distinct. The mapping σU is deﬁned as follows:

σU(f) = σ(si,ti)(f) if f Fsi f otherwise

We call σU a domain translation, and write src(U) for the set {s1, . . . , sl} of source domains and tgt(U) for the set {t1, . . . , tl} of target domains. The source domains need to be distinct to ensure that the domain translation is uniquely deﬁned. Target domains are required to be distinct to allow domain translations to be reversible. For the ease of presentation, we will write σU(F) to denote the set {σU(f) | f F}. For a pair of concepts C and D, we write µ(C, D) for the set of domain translations σU such that:

ϕ(D) = σU(ϕ(C)) (12) src(U) δ(C) (13)

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

tgt(U) (δ(C) \ src(U)) = (14)

The ﬁrst condition states that the domain translations in µ(C, D) essentially translate the concept C to the concept D. The second condition ensures that µ(C, D) contains minimal domain translations only, in the sense that U should not contain any redundant pairs. The third condition is needed to ensure that domain translations are reversible. To see why this is needed, let ϕ(C) = {f1, g2}, ϕ(D) = {g1, g2}, F1 = {f1, f2}, F2 = {g1, g2}, σ(1,2)(fi) = gi. Then ϕ(D) = σ(1,2)(ϕ(C)), but there is no domain translation σU s.t. ϕ(C) = σU(ϕ(D)). As the following result shows, imposing (14) is enough to ensure reversibility. Proposition 2. Let U be a domain translation, and let U = {(t, s) | (s, t) U}. It holds that σ 1 U = σU . As the next result shows, the composition of two domain translations is also a valid domain translation. In particular, if there is some domain translation σU that maps C to D and some domain translation σV that maps D to E, then σU and σV can be composed to deﬁne a domain translation from C to E. Moreover, in such a case, any domain translation from C to E can be deﬁned as such a composition. Proposition 3. If µ(C, D) = and µ(D, E) = we have:

µ(C, E) = {σU V | σU µ(C, D), σV µ(D, E)}

U V ={(i, k) | (i, j) U, (j, k) V, i = k} {(i, j) | (i, j) U, j / src(V )} {(j, k) | (j, k) V, j / tgt(U)}

Semantics of Intra-Domain Roles We will need to put additional constraints on the interpretation of a role r to be able to infer ( r.A) ( r.B)::( r.C) ( r.D) or A B::( r.C) ( r.D) from A B::C D. To allow such lifting of analogy assertions, we will associate with each intradomain role r a mapping κr between sets of features, which satisﬁes a number of conditions. In particular, we introduce the following notion of intra-domain relation. Deﬁnition 2. Let I = (I, [F1, ..., Fk], X, π, , S) be a domain constrained interpretation and let r NR. We say that r is interpreted as an intra-domain relation if for every concept C, we have ( r.C)I = {d I | π(d) κr(ϕ(C)}, for a mapping κr satisfying: 1. κr(F) = κr(F F1) ... κr(F Fk), for all F C; 2. κr(F) Fi, for all i {1, ..., k} and F Ci; 3. κr(σ{(i,j)}(F)) = σ{(i,j)}(κr(F)), for all (i, j) and F Ci; 4. κr(F) = , for all i {1, ..., k} and F Ci \ { }. The ﬁrst two conditions in Deﬁnition 2 state that the features in κr(F) are determined per domain. The third condition captures the intuition that analogous domains should have the same structure. The last condition essentially encodes that whenever C depends on some domain i then r.C should also depend on domain i, i.e. if ϕ(C) contains at least one feature from Fi then the same should be true for

κr(ϕ(C)). Note that if r is interpreted as an intra-domain relation and C is a natural concept, then r.C is a natural concept, whose features are determined by the features in ϕ(C). We then have ϕ( r.C) = κr(ϕ(C)). The semantics of ELana concepts can now be deﬁned similarly to Section 2, but we additionally require that every r NInt R is interpreted as an intra-domain relation.

Semantics of TBoxes We now deﬁne the semantics of ELana TBoxes. We start with that of analogy assertions. We say that a domain constrained interpretation I satisﬁes the analogy assertion C1 C2::D1 D2 if:

µ(C1, C2) µ(D1, D2) = (15)

Clearly, C1 C2::D1 D2 is equivalent to D1 D2::C1 C2. One may wonder whether (15) is sufﬁcient, i.e. whether we should not require µ(C1, C2) = µ(D1, D2). However, as the following result shows, for non-empty concepts, µ(C1, C2) and µ(D1, D2) can have at most one element.

Proposition 4. Let I = (I, F, X, π, , S) be a domainconstrained interpretation. If CI = , DI = and µ(C, D) = , then |µ(C, D)| = 1.

We deﬁne the semantics of ELana TBoxes similarly to Section 2, but now including analogy assertions. A domain constrained interpretation I is a model of an ELana TBox T if I satisﬁes all CIs and analogy assertions in T ; every natural concept N T is fully speciﬁed by its features; and every intra-domain role is interpreted as an intra-domain relation. For a TBox T and CI or analogy assertion φ we write T |= φ to denote that every model of T satisﬁes φ. If T is a singleton of the form {ψ}, we also write this as ψ |= φ.

4.3 Properties of Analogy Assertions

Basic Properties Before returning to the desiderata from Section 3.2, we brieﬂy look at the properties of analogical proportions that were listed in Section 3. First, reﬂexivity is trivially satisﬁed. The symmetry property also holds for analogy assertions, thanks to the reversibility of domain translations.

Proposition 5. We have C1 C2::D1 D2 |= C2 C1::D2 D1.

Exchange of means is not satisﬁed. This can easily be seen from the fact that whenever C1 C2::D1 D2 is satisﬁed, we have |ϕ(C1)| = |ϕ(C2)| and |ϕ(D1)| = |ϕ(D2)| but not necessarily |ϕ(C1)| = |ϕ(D1)|. As a result of this, there are two variants of S-transitivity that can be considered. As the next proposition shows, both of these variants are satisﬁed.

Proposition 6. It holds that:

{C1 C2::D1 D2, D1 D2::E1 E2}|=C1 C2::E1 E2 (16) {C1 C2::D1 D2, C2 C3::D2 D3}|=C1 C3::D1 D3 (17)

We also have that C-transitivity is satisﬁed.

Proposition 7. It holds that:

{C1 D1::D2 C2, C1 E1::E2 C2} |= D1 E1::E2 D2

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Lifting analogy assertions As the next two results show, analogy assertions can indeed be lifted to (non-empty) conjunctions and existentially quantiﬁed concepts.

Proposition 8. Let I = (I, [F1, ..., Fk], X, π, , S) be a domain-constrained interpretation satisfying (Ci Di)I = for i {1..4}, C1 C2::C3 C4 and D1 D2::D3 D4. Then I also satisﬁes (C1 D1) (C2 D2)::(C3 D3) (C4 D4).

Proposition 9. Let r be an intra-domain role. It holds that:

C D::E F |= ( r.C) ( r.D)::( r.E) ( r.F) (18) C D::E F |= C D::( r.E) ( r.F) (19)

Analogy Based Inference Patterns We now return to the two considered analogy based inference patterns: rule translation and rule extrapolation. First, similar as for analogical proportions, we ﬁnd that rule translation is supported.

Proposition 10. Let I be a domain constrained interpretation. If I satisﬁes {C1 D1::C2 D2, C1 C2} then I also satisﬁes D1 D2.

Example 4. Suppose Program Plan::Software Building holds and assume that speciﬁes is an intra-domain role. Using Proposition 9 we can then infer:

Program Plan::( speciﬁes.Software) ( speciﬁes.Building)

If we are additionally given that the concept inclusion (5) is satisﬁed, we can infer (6) using Proposition 10.

A version of rule extrapolation is also supported.

Proposition 11. Let I = (I, [F1, ..., Fk], X, π, , S) be a domain constrained interpretation. Suppose that CI 1 = and that I satisﬁes the following TBox:

T = {C1 C2::C3 C4, D1 D2::D3 D4, D1 D3::D2 D4, C1 D1, C2 D2, C3 D3}

Then I also satisﬁes the assertion C4 D4.

Example 5. Suppose the concept inclusions (1) (3) are satisﬁed, as well as the following analogy assertions6:

Young Adult::Young Adult Cat Wild Cat::Dog Wolf Cute Dangerous::Cute Dangerous Cute Cute::Dangerous Dangerous

Assuming the intersections involved are all non-empty, using Proposition 8 we can infer (Young Cat) (Adult Wild Cat)::(Young Dog) (Adult Wolf). Finally, using Proposition 11 we can infer that (4) holds.

Note that both D1 D2::D3 D4 and D1 D3::D2 D4 are required for the above proposition to hold (see the appendix for a counterexample that shows this). For analogical proportions, adding both conditions makes no difference, as D1:D2 :: D3:D4 and D1:D3 :: D2:D4 are equivalent.

6Note that Cute Cute::Dangerous Dangerous is trivially satisﬁed, since σ µ(Cute, Cute) µ(Dangerous, Dangerous).

4.4 Alternative Semantics As shown in Section 4.3, the proposed semantics for analogy assertions satisﬁes the main desiderata from Section 3.2. We may wonder, however, whether all aspects of the semantics are necessary for this to hold. We return in particular to Condition 5 from Deﬁnition 1, which is perhaps the most restrictive condition. In particular, let us deﬁne the notion of weak domain constrained interpretation as a tuple (I, [F1, ..., Fk], X, π, , S) that satisﬁes all conditions from Deﬁnition 1, apart from Condition 5. One immediate consequence of dropping Condition 5 is that Proposition 4 is no longer valid. As a result, in addition to analogy assertions of the form A1 A2::B1 B2, with the semantics deﬁned in (15), we can now also consider strong analogy assertions, denoted as A1 A2::B1 B2, which are satisﬁed if (15) is satisﬁed and moreover: µ(A1, A2) = µ(B1, B2)

Under this weak semantics, C-transitivity (i.e. Proposition 7) is no longer satisﬁed, neither for the standard analogy assertions nor for strong analogy assertions (see the appendix for counterexamples). Regarding S-transitivity, the variant in (17) remains valid and is furthermore also valid for strong analogy assertions. However, the variant in (16) is no longer valid for standard analogy assertions, although it is satisﬁed for strong analogy assertions. In contrast, Proposition 9 remains valid for standard analogy assertions, but it is not satisﬁed for strong analogy assertions. Proposition 8 is neither satisﬁed for standard analogy assertions nor for strong analogy assertions. Finally, in terms of inference patterns, Proposition 10 remains valid, but Proposition 11 does not, neither for standard nor strong analogy assertions.

5 Conclusions

We have proposed a framework for analogy assertions of the form A is to B what C is to D that is suitable for analogical reasoning in description logics. The underlying assumption is that analogy assertions between concept names can be learned from text, and that we can then lift these to obtain analogy assertions between complex DL concepts. We have shown how the resulting semantics allows us to infer concept inclusions using two analogy based inference patterns. This complements other types of plausible inference patterns, such as interpolation and similarity based reasoning. There are two important lines for immediate future work. First, we plan to study the computational complexity of reasoning in ELana . Results from [Ib a nez-Garc ıa et al., 2020] provide a CONP lower bound for concept subsumption w.r.t. ELana TBoxes. For the upper bound, one key issue would be to relate the number of domains and features of concepts occurring in analogy assertions, as well of those of existential restrictions over intra-domain roles of such concepts. One would also need to establish a bound on the number of features and domains. From the practical side we need mechanisms to deal with the noisy nature of the available knowledge about betweenness and analogy assertions (which typically would be learned from data) and the inconsistencies that may introduce. To this end, we plan to study probabilistic or non-monotonic extensions of our framework.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

References [Baader et al., 2017] Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. An Introduction to Description Logic. Cambridge University Press, 2017. [Balazevic et al., 2019] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. In Proceedings EMNLP, pages 5184 5193, 2019. [Barbot et al., 2019] Nelly Barbot, Laurent Miclet, and Henri Prade. Analogy between concepts. Artiﬁcial Intelligence, 275:487 539, 2019. [Bayoudh et al., 2007] Sabri Bayoudh, Laurent Miclet, and Arnaud Delhay. Learning by analogy: A classiﬁcation rule for binary and nominal data. In Proceedings IJCAI, pages 678 683, 2007. [Beltagy et al., 2013] Islam Beltagy, Cuong Chau, Gemma Boleda, Dan Garrette, Katrin Erk, and Raymond Mooney. Montague meets Markov: Deep semantics with probabilistic logical form. In Proceedings of *SEM, pages 11 21, 2013. [Bordes et al., 2013] Antoine Bordes, Nicolas Usunier, Alberto Garc ıa-Dur an, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multirelational data. In Proceedings NIPS, pages 2787 2795, 2013. [Bouraoui and Schockaert, 2019] Zied Bouraoui and Steven Schockaert. Automated rule base completion as bayesian concept induction. In Proceedings AAAI, pages 6228 6235, 2019. [Brown et al., 2020] Tom B. Brown, Benjamin Mann, et al. Language models are few-shot learners. In Proceedings Neur IPS, 2020. [d Amato et al., 2006] Claudia d Amato, Nicola Fanizzi, and Floriana Esposito. Analogical reasoning in description logics. In Proceedings of the Second ISWC Workshop on Uncertainty Reasoning for the Semantic Web, 2006. [Gentner, 1983] Dedre Gentner. Structure-mapping: A theoretical framework for analogy. Cognitive science, 7(2):155 170, 1983. [Hofstadter et al., 1995] Douglas R Hofstadter, Melanie Mitchell, et al. The copycat project: A model of mental ﬂuidity and analogy-making. Advances in Connectionist and Neural Computation Theory, 2:205 267, 1995. [Holyoak and Thagard, 1997] Keith J Holyoak and Paul Thagard. The analogical mind. American psychologist, 52(1):35 44, 1997. [Hug et al., 2016] Nicolas Hug, Henri Prade, Gilles Richard, and Mathieu Serrurier. Analogical classiﬁers: A theoretical perspective. In Proceedings ECAI, pages 689 697, 2016. [Ib a nez-Garc ıa et al., 2020] Yazm ın Ib a nez-Garc ıa, V ıctor Guti errez-Basulto, and Steven Schockaert. Plausible reasoning about el-ontologies using concept interpolation. In Proceedings KR, pages 506 516, 2020.

[Medina et al., 2004] Jes us Medina, Manuel Ojeda-Aciego, and Peter Vojt as. Similarity-based uniﬁcation: a multiadjoint approach. Fuzzy Sets and Systems, 146(1):43 62, 2004. [Mikolov et al., 2013] Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig. Linguistic regularities in continuous space word representations. In Proceedings NAACL-HLT, pages 746 751, 2013. [Prade and Richard, 2013] Henri Prade and Gilles Richard. From analogical proportion to logical proportions. Logica Universalis, 7(4):441 505, 2013. [Prade and Richard, 2014] Henri Prade and Gilles Richard. From analogical proportion to logical proportions: A survey. In Computational Approaches to Analogical Reasoning: Current Trends, pages 217 244. 2014. [Rockt aschel and Riedel, 2017] Tim Rockt aschel and Sebastian Riedel. End-to-end differentiable proving. In Proc. NIPS, pages 3791 3803, 2017. [Trouillon et al., 2017] Th eo Trouillon, Christopher R. Dance, Eric Gaussier, Johannes Welbl, Sebastian Riedel, and Guillaume Bouchard. Knowledge graph completion via complex tensor factorization. J. Mach. Learn. Res., 18:130:1 130:38, 2017. [Turney, 2006] Peter D. Turney. Similarity of semantic relations. Comput. Linguistics, 32(3):379 416, 2006. [Tversky, 1977] Amos Tversky. Features of similarity. Psychological Review, 84(4):327 352, 1977. [Yang et al., 2015] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings ICLR, 2015.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)