Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces

1 Introduction

Knowledge about concepts can be represented in at least two radically different ways. On the one hand, ontology languages are often used for this purpose. Such languages allow us to describe, in a transparent and precise way, how different concepts are related, but they offer only limited means for supporting inductive inferences. On the other hand, in fields such as natural language processing (NLP) or machine learning, knowledge about concepts is usually encoded in the form of vector space embeddings. These embeddings typically encode both concepts and objects as vectors in a high-dimensional Euclidean space [Mikolov et al., 2013; Bordes et al., 2013]. They are very effective at supporting inductive inferences (e.g. generalizing a learned model to words not encountered during training in NLP applications), but are not able to encode exact logical relationships: vector representations of concepts can encode how similar two concepts are, but not e.g. whether one is subsumed by the other.

Conceptual spaces [G¨ardenfors, 2000] are geometric representations, in which the properties and concepts from a given domain are modeled as convex regions in a potentially highdimensional space 1 . In some sense, conceptual spaces combine the best of both worlds: their geometric nature allows for

1 A higher-level representation of concepts is sometimes assumed, in which concepts are seen as weighted sets of properties. Each of these properties then corresponds to a convex region, in the space that is associated with its corresponding domain. For simplic-

Sanjiang Li

Centre for Quantum Software and Information University of Technology Sydney, Australia sanjiang.li@uts.edu.au

elegant formalizations of inductive arguments, while the use of regions means that logical relationships such as disjointness and subsumption can be encoded in an exact way.

Unfortunately, conceptual space representations are difficult to learn from data. A promising alternative, which we consider in this paper, is to rely on qualitative abstractions of conceptual spaces to encode knowledge about concepts and properties. A standard taxonomy, viewed as a set of statements of the form "A is subsumed by B", written A ⊑ B, can be seen as a simple example of such a qualitative abstraction, if we view A ⊑ B as the spatial constraint reg(A) ⊆ reg(B), where we write reg(X) for the (unknown) conceptual space representation of the concept X. Similarly, the assertion that two concepts cannot share any instances corresponds to the spatial constraint that reg(A) and reg(B) should be disjoint.

By encoding knowledge using qualitative spatial constraints, we can also encode information that goes beyond what is normally considered in ontologies. One example is conceptual neighborhood [Freksa, 1991]. Two concepts A and B are called conceptual neighbors if there is a continuous transition from instances of A to instances of B, without having to go via a third concept. For example, the colors red and orange, the place types pub and restaurant, and the adjectives moderate and severe could all be regarded as conceptual neighbors. The assertion that A and B are conceptual neighbors naturally corresponds to the spatial constraint that reg(A) and reg(B) are adjacent (i.e. externally connected) to each other. This type of information is important in applications where information from multiple sources needs to be combined, as different sources may disagree about where exactly the boundary between two conceptual neighbors should be drawn [Schockaert and Prade, 2011]; e.g. a place which is regarded as a pub by one source might be regarded as a restaurant by another source, even if both sources agree on the fact that pub and restaurant are disjoint concepts.

So far, we have only considered qualitative spatial constraints that can be modeled in the well-known RCC8 calculus [Randell et al., 1992]. Such constraints are not sufficient for assessing the plausibility of inductive arguments. In particular, qualitative conceptual space representations should allow us to determine whether a given property P is likely to apply to instances of a given concept C, knowing only that it applies to instances of some other concepts C1, ..., Ck [Osherson et al., 1990]. For instance, knowing that fine-dining restaurants and fast-food restaurants in Sweden both need a license to sell alcohol, we can plausibly conclude that bistros would as well. Intuitively, this is plausible because bistros are conceptually in between fine-dining restaurants and fast-food restaurants. It was found in [Derrac and Schockaert, 2015] that this qualitative notion of conceptual betweenness is often sufficient to make highly accurate predictions.

ity, we will only consider a single Euclidean space, but our results directly generalize to such multi-domain representations.

To further enrich qualitative conceptual space representations, we can consider constraints that only refer to particular facets of concepts 2 (e.g. encoding that the price range of a bistro is in between that of fast-food and fine-dining restaurants). Moreover, concepts with gradual boundaries can be represented by considering nested sets of regions [G¨ardenfors andWilliams, 2001]. This would allow us, for instance, to express that the typical size of a bird is in between that of mice and dogs. However, as such modeling constructs do not affect our technical results, we will not explicitly consider them.

Qualitative conceptual spaces can be obtained in similar ways as traditional taxonomies, e.g. manually encoded by domain experts, extracted from text, or learned using Bayesian methods [Griffiths et al., 2008]. Approximate information about betweenness can furthermore be derived from vector space embeddings. However, as most of these methods are noisy, we need effective mechanisms for checking the consistency of the resulting representations, to allow repair mechanisms similar to the techniques which are used for taxonomy learning when cycles are detected [Merhej et al., 2014].

To this end, we study the problem of deciding whether a set of RCC8 constraints with betweenness information can be realized using convex regions. First, we show that this decision problem is PSPACE-hard in general. We then introduce an important fragment, and show that deciding realizability for this fragment is NP-complete. The basis of this result comes from the observation that the models of (atomic) sets of constraints from this fragment can be characterized using a number of rankings. This ranking representation is significant for applications, as it allows us to compactly encode which betweenness relations hold between arbitrary sets of regions, whereas naive encodings would be exponentially large.

The most closely related work is [Schockaert and Li, 2013], where an extension of RCC5 with betweenness constraints was proposed. However, while adding betweenness constraints to RCC5 networks only affects reasoning in a minimal way (e.g. most transitivity rules that we intuitively expect to hold for betweenness are only valid for disconnected regions). As we will see, the situation for RCC8 networks is entirely different. Beyond betweenness, a number of other works have considered forms of qualitative spatial reasoning that are important for reasoning about concepts. For example, [Wolter and Zakharyaschev, 2000] introduced an extension of RCC8 in which constraints can relate to unions and intersections of regions. In [Sheremet et al., 2007] a logic is introduced which can be used to reason about relative similarity (i.e. region A is closer to B than to C). The problem of realizing RCC8 networks using convex regions has been studied in [Davis et al., 1999] for two-dimensional spaces and in [Schockaert and Li, 2015] for general Euclidean spaces.

2 Note that is a direct counter-part to multi-domain conceptual space representations.

2 Preliminaries

In this section we recall some basic notions from the region connection calculus.

RCC8 is a constraint language based on the Region Connection Calculus [Randell et al., 1992]. Constraints are built from a set of 8 primitive relations R8 = {DC,EC, PO,EQ,TPP,TPP-1 ,NTPP,NTPP-1 } and a set of variables V . For each R ⊆ R8 and u, v ∈ V , the expression uRv is called an RCC8 constraint. An RCC8 network is a set of RCC8 constraints in which each pair of variables occurs in at most one constraint. If R = {R0} is a singleton then uRv is called an atomic RCC8 constraint, and we usually write u R0 v instead of u {R0} v. We will use some common abbreviations to denote particular non-atomic RCC8 relations: DR = {DC, EC}, PP = {TPP, NTPP}, P = PP ∪ {EQ} and O = R8 \ {DC, EC}. An RCC8 network Θ is called atomic if every constraint in Θ is atomic.

Let Regn be the set of non-empty regular closed 3 subsets of Rn . A mapping S from V to Regn is called an (ndimensional) interpretation. Table 1 lists the conditions under which S satisfies each of the atomic RCC8 constraints, except for uNTPP-1 v and uTPP-1 v, which are equivalent to vNTPPu and vTPPu respectively. When S satisfies an atomic RCC8 constraint uRv, we write S |= uRv. We have that S satisfies a non-atomic constraint uRv, written S |= uRv, if S |= R0 for some R0 ∈ R. An RCC8 network Θ is called satisfiable (or consistent or realizable) if there is an interpretation S that satisfies every constraint in Θ. In that case S is called an (RCC8) solution (or realization). While we only consider Euclidean spaces in this paper, it should be noted that any RCC8 network that can be realized in a topological space that satisfies the axioms of the Region Connection Calculus also has a Euclidean solution, even if we fix the number of dimensions [Renz, 2002].

3 RCC8⋊ ⋉

We now introduce the notion of RCC8⋊ ⋉network, which is the RCC8 analogue of the RCC5⋊ ⋉networks from [Schockaert and Li, 2013]. To encode betweenness information, we will use RCC8 constraints in which the arguments can be expressions of the form u⋊⋉w, denoting the convex hull of the union of u and w. For instance, the constraint v Pu⋊⋉w encodes that v is completely between u and w, while v POu⋊⋉w encodes that v is partially between u and w. In particular, let V ⋊ ⋉ = V ∪ {u⋊⋉v | u, v ∈ V }. An RCC8⋊ ⋉network over V is then defined as an RCC8 network over V ⋊ ⋉. An interpretation S is called an RCC8⋊ ⋉solution of an RCC8⋊ ⋉network Θ if (i) S is an RCC8 solution of Θ and (ii) for each u, v ∈ V it holds that S(u⋊⋉v) = CH(S(u) ∪ S(v)), where CH denotes the convex hull operator. Note that while ⋊⋉ is limited to two regions, we can consider the convex hull of an arbitrary number of regions by introducing fresh variables, e.g. in any RCC8⋊ ⋉solution of {xEQa1⋊⋉y1, y1 EQa2⋊⋉y2, ..., yn-2 EQan-1⋊⋉an} it holds that S(x) = CH(S(a1), ..., S(an)). We write Θ |= Φ, for Θ and Φ (sets of) RCC8⋊ ⋉constraints, to denote that every RCC8 solution of Θ is also an RCC8 solution of Φ. Note that this is different from requiring that every RCC8⋊ ⋉solution of Θ is an RCC8⋊ ⋉solution of Φ.

3A is regular closed if A is equal to the closure of its interior.

The problem we will focus on in this paper is deciding whether an RCC8⋊ ⋉has a convex and bounded solution, i.e. a solution in which every variable is mapped to a convex and bounded region. The reason why we require convexity stems from our motivation in terms of conceptual spaces. Furthermore, note that because we can always add constraints of the form aEQa⋊⋉a, encoding that a has to be convex, the hardness results we show in this paper remain valid even when convexity is not required. From a practical point of view, this also means that we need to understand how convex solutions can be found, before arbitrary solutions can be considered. The restriction to bounded regions is because the ⋊⋉ operator can otherwise lead to counterintuitive behaviour 4 .

We can show the following result 5 .

Theorem 1. Deciding whether a RCC8⋊ ⋉network has a convex and bounded solution is PSPACE-hard.

When an RCC8⋊ ⋉network Θ contains a constraint such as uECv, then in any solution S there is a hyperplane H separating S(u) from S(v). For each region v, let vH be a new variable corresponding to the (lower-dimensional and possibly empty) region S(v) ∩ H. The constraints in Θ can impose constraints between these new variables vH, and checking their satisfiability is similar to checking the satisfiability of the constraints between the initial set of variables. Moreover, these new constraints may induce further constraints, between intersections of the regions S(vH) with another separating hyperplane. Intuitively, it is this recursive process that causes the PSPACE-hardness.

3.1 Basic Networks

We call an RCC8⋊ ⋉network Θ basic if each constraint in Θ has one of the following forms:

• u R v, with R ∈ {DC, EC, NTPP, P} and u, v ∈ V
• vPu⋊⋉w, with u, v,w ∈ V

Note that any atomic RCC8⋊ ⋉network can be represented as a basic network by introducing fresh variables, e.g.

4 The fact that S(u) and S(v) are regular closed is not sufficient for CH(S(u), S(v)) to be regular closed, which leads to particular restrictions on that mappings S that we would be able to consider as interpretations.

5 The proofs of all results from this paper are available in an online appendix at:

http://users.cs.cf.ac.uk/S.Schockaert/reports/betweennessRCC8supplement.pdf

the constraint aPOb can be replaced by the set of constraints {xPa, xDCb, yPb, yDCa, zPa, zPb}, where x, y, z are fresh variables. Similarly, note that the condition that variables of the form u⋊⋉w can only occur in constraints of the form v Pu⋊⋉w is not a real restriction, since we can always replace occurrences of u⋊⋉v by a fresh variable xuv, and add the constraints xuv Pu⋊⋉v, uPxuv and vPxuv, which is equivalent to requiring xuv EQu⋊⋉v if only convex solutions are considered.

We thus have that an RCC8⋊ ⋉network Θ has a (convex and bounded) solution iff there exists a basic RCC8⋊ ⋉network Θ′ which has a (convex and bounded) solution and which is such that Θ′ |= Θ. Decide whether an RCC8⋊ ⋉network Θ has a (convex and bounded) solution can thus be reduced to guessing a corresponding basic network Θ′ and showing that it has a (convex and bounded) solution. For this reason, we can restrict ourselves in this paper to basic networks without loss of generality. Note, for instance, that the PSPACE-hardness result from Proposition 1 remains valid for basic networks. For the ease of presentation, in examples we will sometimes also use constraints of the form uPOv.

4 An NP-Complete Fragment

We now introduce a restriction on RCC8⋊ ⋉networks to prevent the aforementioned recursive process that is responsible for the PSPACE-hardness result.

Definition 1. An RCC8⋊ ⋉network Θ is non-recursive if there are no u, v, w ∈ V such that Θ |= {uNTPPv, v ECw}.

One straightforward way to guarantee non-recursiveness is by either disallowing EC constraints or NTPP constraints. In applications, EC constraints are important for modeling conceptual neighborhood, while NTPP relations are important for modeling concepts with gradual boundaries. However, we would normally only need one of these modeling constructs, as the notion of conceptual neighborhood is based on the assumption that there is a crisp (i.e. non-gradual) but ill-defined boundary between two concepts.

Next we show that checking if a basic non-recursive network has a convex and bounded solution is NP-complete.

4.1 Ranking-BasedModels

Let us assume that there are regions a1, ..., am, b1, ..., bm and some p ∈ {1, ..., m} satisfying the following assumptions:

• AB1 For each i ∈ {1, ..., p} it holds that Θ |= ai DCbi.
• AB2 For each i ∈ {p+1, ...,m} it holds that Θ |= ai ECbi.
• AB3 For every u, v ∈ V such that Θ |= uDCv (resp. Θ |= uECv) there exists an i ∈ {1, ..., p} (resp. i ∈ {p + 1, ...,m}) such that Θ |= {uPai, vPbi} or Θ |= {v P ai, u P bi}.

These assumptions do not affect generality, as we can always add fresh regions and guess the required constraints to make AB1-AB4 satisfied 6 . Note that while this process involves making a guess, it does not affect the NP-completeness result.

Let us write M = {a1, ..., am, b1, ..., bm}. We also write inv(ai) for bi and inv(bi) for ai. The following proposition introduces a necessary condition for RCC8⋊ ⋉networks to have a convex solution. In Section 4.3, we will see that this condition is also sufficient for basic non-recursive networks.

Proposition 1. Suppose that the RCC8⋊ ⋉network Θ has a convex and bounded RCC8⋊ ⋉solution. For each x ∈ M there exists a mapping ρx : V → {0, ..., |V | - 1} such that for every u, v, w ∈ V it holds that:

and for x, y ∈ M and u, v ∈ V such that Θ |= y DC inv(y):

The mappings ρx essentially define a set of rankings over the variables from V , as only the relative ordering of the ρx(v) values matters. Note that the existence of suitable rankings can be straightforwardly checked using integer linear programming. Because the existence of these rankings is equivalent to the realizability of Θ using convex and bounded regions (as we will show), we can effectively view them as models of RCC8⋊ ⋉networks. From an application point of view, this ranking based representation is also important, as it will allow us to easily determine for arbitrary variables v1, ..., vk, u whether S(u) ⊆ CH(S(v1) ∪ ... ∪ S(vk)), for S the solution that we will associate with the rankings, which will be the case iff ρx(u) ≥ min(ρx(v1), ..., ρx(vk)) holds for all x ∈ M. By encoding qualitative conceptual spaces in terms of such rankings, we can thus compactly encode exponentially many betweenness statements.

Example 1. It follows from Proposition 1 that the following set of constraints is not satisfiable:

Indeed, using (1) and (3) we find

It follows that ρb2 (a1) = ρb2 (b1), and thus by (5) (for y = u = b1) that ρa1 (a1) < ρa1 (a1), which is a contradiction.

Even for basic non-recursive networks, checking whether Proposition 1 is satisfied is NP-hard. In fact, we can show the following, stronger property.

6 This is shown in the online appendix.

Proposition 2. Let Θ be an RCC8⋊ ⋉network. The problem of checking whether Θ satisfies the conditions from Proposition 1 is NP-complete, even if Θ is a set of basic network and does not contain any occurrences of NTPP or EC.

4.2 Properties of Hyperrectangles

In Section 4.3, we will show that when the conditions from Proposition 1 are satisfied, and Θ is a basic non-recursive RCC8⋊ ⋉network, we can construct a convex and bounded solution from the mappings ρx. The main idea will be to realize variables using axis-aligned hyperrectangles, where ρai (v) and ρbi (v) respectively determine the lower and upper bound of the ith coordinate for the hyperrectangles associated with v. In this section, we first discuss how hyperrectangles can be chosen such that betweenness constraints can easily be satisfied. The main idea is illustrated in the following example.

Example 2. Let Θ contain the following constraints:

It can be verified that the following choices for ρx satisfy the conditions of Proposition 1:

A solution S is shown in Figure 1, which corresponds to the rankings ρx in the following sense: there are decreasing functions f1, f2, f3, f4 such that S(v) for any v ∈ V is given by:

As illustrated in Example 2, up to a monotonic transformation, the rankings ρx will determine a solution (although it will not always be possible to realize variables using a single hyperrectangle). In accordance with condition (1), we need to choose this monotonic transformation such that we are able to realize a region b as being between two other regions a and c, as soon as ρx(b) ≥ min(ρx(a), ρx(c)) for all x ∈ M. To this end we will use the {0, ..., η} → [0,+∞[ functions f and g defined as follows:

where η ∈ N will be assumed to be sufficiently large (see below for details).

The definition of S will be such that all points in S(ai) are positive in the ith coordinate and all points in S(bi) are negative in this coordinate (as in Figure 1). Furthermore, if ρai (u) < ρai (ai) then S(u) will overlap with S(bi), which means that the lower bound on the ith coordinate of the hyperrectangles defining S(u) will be negative. On the other hand, if ρai (u) ≥ ρai (ai) then S(u) will be included in S(ai) and thus this lower bound will be positive. This difference matters for the following reason. If the lower bound is negative, we can always make a constraint such as vPu⋊⋉w satisfied by making the lower bound of the ith coordinate of S(u) sufficiently small (and appropriately defining the other coordinates). In such cases we use the function f to define the lower bound. However, if the lower bound needs to be positive, a different strategy is needed, and we instead use the function g to define lower bounds that can be arbitrarily close to 1. For the ease of presentation, we will define upper bounds using the following abbreviation, for λ ∈ {0, ..., η}.

Similarly we will define lower bounds using the abbreviation h-λ (r), defined as -h+λ (r). Intuitively, we can think of h+ρbi (bi) (ρbi (v)) and h-ρai (ai) (ρai (v)) as the upper and lower bounds on the ith coordinate for the hyperrectangle corresponding to v. However, the actual construction in Section 4.3 will be slightly more complicated, among others because we will need more than one hyperrectangle for each variable.

We call a hyperrectangle×i [li, ui] regular if each li is of the form h-λ (r), and each ui is of the form h+λ (r). The main motivation for using regular hyperrectangles is that they allow us to easily determine which points are in between them. In particular, the construction in Section 4.3 will crucially rely on the following property about regular hyperrectangles.

Lemma 1. Let ×i [li, ui] and ×i [l′i , u′i ] be regular hyperrectangles. Furthermore, we consider the point (p1, ..., pm) where each pi is of the form f(r), -f(r), g(r) or -g(r). We have (p1, ..., pm) ∈ CH((×i [li, ui]) ∪ (×i [l′i , u′i ])) if the following holds for each i:

• min(li, l′i ) < pi or li = l′i = pi; and
• pi < max(ui, u′i ) or ui = u′i = pi

4.3 Constructing Convex Solutions

As already mentioned, it is not always possible to construct a solution in which each variable is realized as a single hyperrectangle. This is illustrated in the following example.

Example 3. Consider the following RCC8⋊ ⋉constraints:

A possible solution S is shown in Figure 2, where v is realized as the convex hull of the two rectangles that are labelled with v. The remaining variables are realized using single rectangles, as before. To see why it is not possible to realize v using a single rectangle, note that because of the constraints u P v⋊⋉w and v P u⋊⋉w, the points from S(u) that are at maximal distance from S(w) have to belong to S(v) and vice versa. In particular, this means that none of the points from S(v) that are at maximal distance from S(w) can belong to S(a2). Hence, with a single axis-aligned rectangle for v, we would not be able to also satisfy the constraint v1 Pv .

We will construct a solution S of the following form (v ∈ V ):

where Rx(v) is a hyperrectangle of the following form:

Next we explain how the lower bounds l(v, x, i) and upper bounds u(v, x, i) are chosen. Throughout the section, we will assume that η ≥ 3mn + 2m. Intuitively, we want the hyperrectangle Rai (v) to correspond to the set of points from S(v) whose ith coordinate is minimal. For i ≤ p, that minimal value value of the ith coordinate will be chosen as h-3mρai (ai) (3mρai (v)). The reason why we choose this bound in terms of 3mρai (v) rather than simply ρai (v) relates to the fact that we need to consider a number of additional hyperrectangles in the proof. For i > p, some additional care is needed to ensure that all EC relations are satisfied. To this end, if i > p, we will ensure that l(v, ai, i) ≤ 0 for all regions v. In other words, for x = ai we have:

The upper bound u(v, ai, i) is essentially irrelevant, as the rectangle Rai (v) is only aimed at encoding the set of points from S(v) whose ith coordinate is minimal. In principle, we could define Rx(v) as a degenerate hyperrectangle and choose l(v, ai, i) = u(v, ai, i). However, to be in accordance with the conditions of Lemma 1, if i < p, we will choose u(v, ai, i) as the lowest possible value that makes Rai (v) a regular hyperrectangle. For i ≥ p we can simply choose u(v, ai, i) = 0:

where

The values l(v, bi, i) and u(v, bi, i) are chosen in a similar way, but here it is rather the upper bound that matters:

where

κ-(x) = max({-f (r) | f (r) ≤ x} ∪ {g(r) | g(r) ≤ x) Finally, for x /∈ {ai, bi}, the bounds l(v, x, i) and u(v, x, i) are chosen such that Rx(v) = Rx(u) if ρx(u) = ρx(v): l(v, x, i) = max{l1(v′ , i) | ρx(v′ ) = ρx(v)} u(v, x, i) = min{u1(v′ , i) | ρx(v′ ) = ρx(v)}

where

We can then show the following result.

Theorem 2. Let Θ be a basic non-recursive set of RCC8⋊ ⋉ constraints. Let S(v) be defined as in (6) and S(u⋊⋉v) = CH(S(u) ∪ S(v)) for u, v ∈ V . If the mappings ρx used in the definition of the hyperrectangles Rx satisfy the conditions from Proposition 1, then S is a solution of Θ.

Corollary 1. Deciding whether a basic non-recursive RCC8⋊ ⋉network has a convex and bounded solution is NPcomplete.

The following example illustrates that non-recursiveness is indeed required to guarantee the existence of a solution.

Example 4. Consider the following RCC8⋊ ⋉constraints:

Despite the fact that these constraints satisfy the conditions from Proposition 1, they do not admit a convex solution. Figure 3 shows an interpretation which satisfies all of these constraints, except for aECd, which cannot be jointly satisfied with the other constraints. To see why this is the case, let us consider hyperplanes Hi separating ai and bi. The problem is that c cannot contain any point from H1 due to the constraint cNTPPc0 and similarly b cannot contain any point fromH2 due to the constraint bNTPPb0. As a result, given the constraint aPb⋊⋉c, a cannot contain any points that belong to H1 ∩ H2, which would be required to satisfy aECd.

5 Conclusions

We have studied the problem of reasoning about betweenness in the context of RCC8. Among others, we have shown that satisfiability checking in this setting is PSPACE-hard in general, and we have introduced a fragment for which satisfiability checking is NP-complete. As this fragment appears general enough for most applications, one of the most important questions for future work is how RCC8⋊ ⋉encodings of conceptual knowledge could be learned from text. Several interesting theoretical questions also remain. For example, it is still an open problem how consistency can be decided when convexity is not required. Another natural question is how betweenness could be combined with the Boolean region terms from [Wolter and Zakharyaschev, 2000].

Acknowledgments

Steven Schockaert was supported by ERC Starting Grant 637277. Sanjiang Li was partially supported by NSFC (No. 11671244).