Qualitative Reasoning about Directions in Semantic Spaces

1 Introduction

High-dimensional Euclidean spaces play a prominent role in areas such as computational linguistics, information retrieval and cognition [Turney and Pantel, 2010; Deerwester et al., 1990; G¨ardenfors, 2000]. These Euclidean spaces, often called semantic or conceptual spaces, are typically learned from large text corpora, using dimensionality reduction methods such as singular value decomposition or multidimensional scaling [Turney and Pantel, 2010]. In the resulting representations, points or vectors are used to encode the meaning of words, documents, concepts or entities.

The coordinates of the points or vectors in such a semantic space are essentially arbitrary; what matters is their spatial relationship. For example, the relative distance between points in a semantic space is used to discover synonymous words [Turney and Pantel, 2010] or to find the documents that best satisfy a query [Deerwester et al., 1990]. The extent to which four points approximately form a parallelogram can be used to discover analogical proportions [Miclet et al., 2008; Schockaert and Prade, 2011; Mikolov et al., 2013]; e.g. the approach from [Mikolov et al., 2013] was able to learn that "king is to queen what man is to woman". Geometric betweenness has been used for implementing a form of commonsense reasoning called interpolation. For example, the approach from [Derrac and Schockaert, 2014b] discovered that "candy store is conceptually between grocery store and toy store", meaning that natural properties that are true

Jae Hee Lee

Australian National University Canberra, Australia jae-hee.lee@anu.edu.au

for both grocery stores and toy stores tend to be true for candy stores as well. Finally, it is possible to identify directions in a semantic space that correspond to interpretable semantic relations, such as e.g. "more violent than" in a space of films [Vig et al., 2012; Kovashka et al., 2012; Derrac and Schockaert, 2014a].

In this paper, we focus on qualitative reasoning about the latter type of direction relations. To date, semantic spaces have only received limited attention from the spatial reasoning community. Some authors have looked at logics of comparative similarity [Williamson, 1988; Sheremet et al., 2010] in semantic spaces (including non-Euclidean spaces). Furthermore, [Davis et al., 1999] discusses a language for expressing betweenness, collinearity and parallelism. Although the results in [Davis et al., 1999] are proven for points in R2 , they are relevant for higher-dimensional spaces (see Section 3). To the best of our knowledge, qualitative reasoning about directions has not yet been considered for high-dimensional spaces.

Although we only focus on reasoning aspects in this paper, our overall aim is to improve methods for extracting semantic relations from large text corpora. Most relation extraction approaches in the literature are based on lexical or syntactic patterns [Hearst, 1992; Carlson et al., 2010; Nakashole et al., 2012], which typically leads to high-recall, low-precision results. To increase precision while keeping recall high, implausible assertions are usually removed based on some form of constraint reasoning [Carlson et al., 2010; Nakashole et al., 2011], e.g. based on learned constraint rules such as "city X can only be the capital of country Y if X is located in Y ". In this paper, we are specifically interested in relations that encode relative properties between entities of the same type, e.g. relations such as "funnier than" for films, for which suitable constraint rules are difficult to find. As an alternative to constraint rules, we propose to measure the plausibility of such relational facts in terms of the consistency of an associated set of spatial constraints. In particular, we consider relational facts plausible if they can be interpreted as direction relations in a semantic space. An important advantage of our approach is that it allows us to use existing semantic space representations of entities (as points) and relative properties (as directions) to help assess the plausibility of relational facts about entities or properties for which no such representation can be obtained (e.g. because they are too infrequent in the text corpus).

The remainder of this paper is structured as follows. In the next section, we introduce EER, a formalism for reasoning about directions in high-dimensional spaces. Section 3 subsequently shows how reasoning in several existing calculi can be reduced to the consistency problem for EER and characterises the computational complexity of the main decision problem. Then, in Section 4, we propose an efficient, but incomplete method for finding models of consistent sets of EER formulas, after which we provide experimental results in Section 5. In addition to evaluating the feasibility of reasoning about EER instances, we show how our implementation can be used to find solutions to problem instances of existing calculi such as LR, based on the reductions from Section 3. To the best of our knowledge, this constitutes the first practical method that can find solutions for these calculi.

2 Euclidean Embedding of Rankings

Several authors have proposed to model relative properties as directions in a suitable semantic space. For example, [Kovashka et al., 2012] learns directions modelling relations such as "shinier than" and "more formal than" in a semantic space of shoes (based on visual features), while [Derrac and Schockaert, 2014a] learns directions modelling relations such as "more gripping than" in a semantic space of films (based on textual features). The latter approach is illustrated in Figure 1, which shows directions corresponding to the relations "more gripping than" and "more hilarious than". Given these directions, we can rank films according to how much they have these properties by comparing the orthogonal projections of the corresponding points. For example, in the case of Figure 1, the Hangover is considered to be more hilarious than Fight Club, which is in turn considered more hilarious than Terminator 2. Note that while Figure 1 illustrates the principle for R2 , semantic spaces will typically be of higher dimension.

Formally, each relative property, modelled as a vector v ∈ Rd , induces a total preorder ⪯v on Rd , ranking points based on the relative position of their orthogonal projections on the directed line λv, λ ∈ R. We define:

We also use p ∼v q as an abbreviation for (p ⪯v q) ∧ (q ⪯v p). Similarly, a strict partial order ≺v is defined as follows:

Definition 1. Let a set of variables {x1, ..., xn} and a positive integer m be given. An EER-formula 1 is a statement of the form xi ⪯ℓ xj or a statement of the form xi ≺ℓ xj, with 1 ≤ i, j ≤ n and 1 ≤ ℓ ≤ m. We call the pair (π, ρ) a d-dimensional solution of a set of EER-formulas Θ, with π : {x1, ..., xn} →Rd and ρ : {1, ...,m} →Rd , if for every formula in Θ of the form

it holds that

which means that π(xi) is (strictly) before π(xj) when projected orthogonally on the directed line λρ(ℓ), λ ∈ R (cf. (1) and (2)). If such a d-dimensional solution exists, we say that Θ is realisable in Rd . The problem of deciding whether an EER-formula is realisable is called REER.

In the following, we will use abbreviations such as p ≺ℓ q ∼ℓ r, which corresponds to the set {p ≺ℓ q, q ⪯ℓ r, r ⪯ℓ q}.

Definition 2. We say that a set of EER formulas Θ contains a cycle if there are formulas α1, ..., αr in Θ, with each αi of the form yi ≺ℓ yi+1 or yi ⪯ℓ yi+1, such that yr+1 = y1 and at least one of the formulas αi is of the form yi ≺ℓ yi+1.

The following proposition is easy to show.

Proposition 3. Let Θ be defined as in Definition 1. For d ≥ m, it holds that Θ is realisable in Rd iff Θ does not contain any cycles.

Example 4. The EER-formulas

Terminator 2 ≺hilarious Fight Club ≺hilarious Hangover Hangover ≺gripping Terminator 2 ≺gripping Fight Club

are realisable for d = 2. A solution is depicted in Figure 1.

Given a set of EER-formulas Θ, we write dim(Θ) for the lowest d ∈ N such that Θ is realisable in Rd , where we define dim(Θ) = +∞ if Θ is not realisable for any d ∈ N (i.e. if Θ contains a cycle). Intuitively, dim(Θ) reflects the degree to which the set of assertions encoded by Θ is regular. To identify implausible assertions, we can impose a level of regularity by treating a set Θ as inconsistent if dim(Θ) > d∗ , for some d∗ ∈ N. Such inconsistencies can be restored in the usual way, e.g. by choosing a maximal subset Θ∗ for which dim(Θ∗ ) ≤ d∗ based on confidence scores for each of the assertions in Θ. The view that dim(Θ) reflects the regularity of Θ could also be used to identify plausible conclusions which are missing from Θ: we say that an EER-formula x ≺i y is a plausible consequence of Θ if dim(Θ ∪ {x ≺i y}) <

1 EER stands for Euclidean Embedding of Rankings.

dim(Θ ∪ {y ⪯i x}), and similarly for formulas of the form x ⪯i y.

In this way, our approach supports a form of commonsense reasoning about relational facts based on dimensionality reduction, similar in spirit to how singular value decomposition was used for automatically extending ConceptNet in [Speer et al., 2008] or how tensor decomposition was used for automatically extending YAGO in [Nickel et al., 2012]. However, due to its geometric nature, our approach also allows us to combine qualitative knowledge with existing semantic space representations: given a set of EER-formulas, one merely needs to find a solution (π, ρ) in which the maps π and ρ are fixed for objects and rankings with a known semantic space representation.

3 Reductions fromExisting Calculi

In this section, we first show how the realisability problem for atomic LR-formulas can be reduced to REER in R2 , which will enable us to apply the implementation from Section 4 for checking the consistency of sets of atomic LR-formulas. Subsequently, in Section 3.2 we will show how reasoning about betweenness, collinearity and parallelism can be reduced to REER in Rd for any d. This will allow us to characterise the computational complexity of REER, and could again be useful for using EER reasoners to check the consistency of constraints about betweenness, collinearity and parallelism.

3.1 Reduction fromLR

The LR calculus [Ligozat, 1993; Scivos and Nebel, 2005] is based on a set of 9 jointly exhaustive and pairwise disjoint relations between triples of points: l (left), r (right), b (behind), c (closer), f (further), e12, e13, e23 and eq. The main relations are l and r, where intuitively l(p1, p2, p3) holds if p3 is located left of the oriented line defined by --→ p1p2 and r(p1, p2, p3) holds if p3 is right of this line. Formally:

where ang(-→pq, -→pr) is the oriented angle between -→pq and -→pr. The remaining relations cover the cases where the three points are collinear or coincide:

Definition 5. An LR-formula is an expression of the form ∨ki=1 ξi(x1, x2, x3) with ξi ∈ {l, r, b, c, f, e12, e13, e23, eq} and x1, x2, x3 are taken from a set of variables X. An LRformula is called atomic, if k = 1. We call an X → R2 mapping π a solution of a set of LR-formulas Ψ if the constraint ξ(π(x1), π(x2), π(x3)) is satisfied for every formula of the form ξ(x1, x2, x3) in Ψ. If such a solution exists, we say that Ψ is satisfiable.

The satisfiability problem for LR is ∃R-complete and the satisfiability problem for atomic LR-formulas NP-hard [Lee, 2013], where ∃R is the class of problems that can be reduced in polynomial time to the problem of checking the consistency of a set of algebraic equations over the real numbers [Schaefer, 2010]. The class ∃R is known to be in PSPACE and to contain NP, but its exact relationship with the polynomial hierarchy is still unknown.

We now show that for every set of atomic LR-formulas Ψ, in polynomial time we can construct a set of EER formulas Θ such that Ψ is satisfiable iff Θ is realisable in R2 . For a formula in Ψ of the form eq(x1, x2, x3), we add the following formulas to Θ:

where fresh rankings i and j and fresh variables y and z are used for every formula. Note that x3 ≺i y ≺i z and x3 ≺j z ≺j y imply that rankings i and j will correspond to different lines in any two-dimensional solution, in which case x1 ∼i x2 ∼i x3 and x1 ∼j x2 ∼j x3 implies that x1, x2 and x3 coincide. For a formula in Ψ of the form e12(x1, x2, x3), we add the following formulas to Θ:

where i and j are again fresh rankings for every formula. The formulas x2 ∼i x3 and x2 ≺j x3 are sufficient to guarantee that the lines corresponding to rankings i and j cannot coincide and that x3 cannot coincide with x2. From x1 ∼i x2 and x1 ∼j x2 we then find that x1 and x2 will coincide in any two-dimensional solution. Formulas of the form e23(x1, x2, x3) and e13(x1, x2, x3) are treated in an entirely analogous way.

For a formula in Ψ of the form b(x1, x2, x3) we add the following EER formulas to Θ:

with i and j fresh rankings. Indeed, x1 ∼i x2 ∼i x3 guarantees that x1, x2 and x3 are collinear in any two-dimensional solution, while x3 ≺j x1 ≺j x2 guarantees that the points appear in the correct order. Formulas of the form c(x1, x2, x3) and f(x1, x2, x3) are treated entirely analogously.

For a formula in Ψ of the form l(x1, x2, x3) we add the following EER formulas to Θ:

Similarly, for a formula of the form r(x1, x2, x3) we add:

where each time, i and j are fresh rankings. These formulas alone are not sufficient, as the following lemma reveals.

Lemma 6. Suppose Θ contains the EER formulas in (3). In any solution (π, ρ) of Θ in R2 it holds that:

Similarly, if Θ contains the formulas in (4) then for any solution (π, ρ) it holds that:

This lemma is illustrated in Figure 2(a), showing a solution of (3) where sin(ang(ρ(i), ρ(j))) > 0, which implies l(π(x1), π(x2), π(x3)). Unfortunately, there is no obvious way to enforce sin(ang(ρ(i), ρ(j))) > 0 using additional EER formulas. We can overcome this issue by fixing the rankings 0 and 1 and adding EER constraints to Θ that impose that sin(ang(ρ(0), ρ(1))) > 0 iff sin(ang(ρ(i), ρ(j))) > 0. We say that a vector v is between the vectors u and w if µv = λu + (1 - λ)v for some µ > 0 and 0 < λ < 1.

Lemma 7. Suppose Θ contains the following constraints:

Then it holds that ρ(j) is between ρ(i) and ρ(k) in any twodimensional solution (π, ρ) of Θ.

Using this lemma, we can show the following result.

Lemma 8. Suppose Θ contains the following constraints:

In any solution (π, ρ) of Θ it holds that:

As illustrated in Figure 2(b), the reason we need five instances of (5) in (6)-(10) is to ensure that the constraints have a solution for every choice of ρ(i) and ρ(j) such that sin(ang(ρ(i), ρ(j))) > 0 iff sin(ang(ρ(0), ρ(1))) > 0, provided that ρ(i) is not between ρ(0) and ρ(1). As we will see below, we can always ensure that the latter requirement is satisfied in our construction.

Hence, for every LR-formula of the form l(x1, x2, x3) in Ψ, we add the formulas in (3) to Θ, in addition to the formulas in (6)-(10), where a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3, e1, e2, e3 are fresh variables and r, s, t, i, j are fresh rankings for every LR-formula; for every LRformula of the form r(x1, x2, x3) in Ψ we similarly add the formulas in (4) and (6)-(10).

Let (π, ρ) be a solution of Θ. It is clear that π satisfies all formulas of the form ξ(x1, x2, x3) from Ψ with ξ ∈ {b, c, f, e12, e13, e23, eq}. From Lemma 6 and 8 it follows that:

1. either r(π(x1), π(x2), π(x3)) holds for every formula r(x1, x2, x3) ∈ Ψ and l(π(x1), π(x2), π(x3)) holds for every formula l(x1, x2, x3) ∈ Ψ; or
2. l(π(x1), π(x2), π(x3)) holds for every formula r(x1, x2, x3) ∈ Ψ and r(π(x1), π(x2), π(x3)) holds for every formula l(x1, x2, x3) ∈ Ψ.

In the former case, we find that the restriction of π to X is a solution of Ψ. In the latter case, we define a new solution (π′ , ρ′ ) by reflecting all points and vectors over the Y-axis. It is easy to see that (π′ , ρ′ ) is a solution of Θ and that the restriction of π′ to X is a solution of Ψ. In each case, we have that if Θ is realisable in R2 then Ψ is satisfiable.

Conversely, if π is a solution of Ψ, we need to construct a solution (π, ρ) of Θ. For a formula of the form l(x1, x2, x3), it is easy to verify that we can always find rankings i and j such that (3) is satisfied and sin(ang(ρ(i), ρ(j))) > 0. For formulas of the form r(x1, x2, x3) we can similarly find rankings i and j such that (4) is satisfied and sin(ang(ρ(i), ρ(j))) > 0. Once these vectors have been fixed, we choose ρ(0) and ρ(1) such that none of the other vectors ρ(i) is between ρ(0) and ρ(1). Then π and ρ can always be extended such that the formulas (6)-(10) are satisfied. For formulas of the form ξ(x1, x2, x3) with ξ ∈ {b, c, f, e12, e13, e23, eq} it is straightforward to see how ρ needs to be extended to ensure that (π, ρ) is a solution of Θ. Hence we obtain the following proposition.

Proposition 9. Let Ψ be a set of atomic LR-formulas and let Θ be the corresponding set of EER formulas. It holds that Ψ is satisfiable iff Θ is realisable in R2 .

3.2 Betweenness, Collinearity and Parallelism

In this section, we will consider the following spatial relations between points in Rd :

• Col(x, y, z) iff x, y and z are distinct and collinear.
• Bet(x, y, z) iff Col(x, y, z) and y is between x and z.
• Gen(x, y, z) iff x, y and z are in general linear position (i.e. distinct and not collinear).
• Par(w, x, y, z) iff the line wx is distinct from and parallel to yz, with w ̸= x and y ̸= z.

These relations are studied in [Davis et al., 1999], with the exception of Gen. They are of particular interest in the context of semantic spaces, as they form the basis for commonsense reasoning methods such as interpolation and analogical reasoning [Miclet et al., 2008; Schockaert and Prade, 2013; Derrac and Schockaert, 2014b].

Definition 10. An L-formula is an expression of the form ξ(x, y, z), with ξ ∈ {Col, Bet, Gen}, or Par(w, x, y, z). Let Ψ be a set of L-formulas over the set of variables X. An X → Rd mapping π which satisfies each of the L-formulas in Ψ is called a solution of Ψ. If such a solution exists, we say that Ψ is realisable in Rd .

It follows from Lemma 1 in [Davis et al., 1999] that checking the realisability in R2 of a set of L-formulas is ∃R-hard (even when only the predicates Col and Par are considered). We can extend this result to Rd for any d > 2.

Proposition 11. The problem of checking whether a set of L-formulas is realisable in Rd is ∃R-hard for any d ≥ 2.

Proof. Let Ψ1 be a set of L-formulas over X and let d ≥ 2. We define a new set of L-formulas, imposing that every x in X is in the convex hull of three fresh variables a, b, c:

where dx is a fresh variables for every x ∈ X. It is easy to see that Ψ1 is realisable in R2 iff Ψ2 is realisable in Rd .

We now show how the realisability problem for a set of Lformulas Ψ can be reduced to the realisability problem for a corresponding set of EER-formulas Θ. To express that x, y and z are collinear, we will use EER formulas that encode that they are located on the intersection of d - 1 linearly independent hyperplanes. In particular, for every formula in Ψ of the form Col(x, y, z) or Bet(x, y, z), we add the following EER formula to Θ for every i ∈ {1, ..., d - 1}

where ri is a fresh ranking. To impose that the directions corresponding to rankings r1, ..., rd-1 are linearly independent, we also add the following EER-formulas to Θ:

where a1, ..., ad are fresh variables. For a formula of the form Col(x, y, z) we finally add three additional EER-formulas to Θ, to impose that x, y, z need to be distinct:

with rd, rd+1, and rd+2 fresh rankings. For a formula of the form Bet(x, y, z), instead of (17), we add x ≺rd y ≺rd z. For a formula of the form Gen(x, y, z), we only need to add the following three formulas to Θ:

with r1, r2 and r3 fresh rankings. Finally, for a formula of the form Par(w, x, y, z), we add the following formulas to Θ (i ∈ {1, ..., d - 1}):w ∼ri x ≺ri y ∼ri z

as well as w ≺rd x and y ≺rd+1 z. We can show the following result.

Proposition 12. Let Ψ be a set of L-formulas and let Θ be the corresponding set of EER-formulas. For any d ≥ 2 it holds that Ψ is realisable in Rd iff Θ is realisable in Rd .

From (1) and (2) it immediately follows that REER can be formulated as checking the consistency of a set of polynomial inequalities, and thus belongs to ∃R. From Propositions 11 and 12, also it follows that REER in Rd is ∃R-hard for d ≥ 2. Hence we have the following result.

Corollary 13. For any d ≥ 2, REER in Rd is ∃R-complete.

4 An Iterative Method for Finding Solutions

Let Θ be a set of EER constraints without cycles. Finding a solution of Θ (or deciding that no solution exists) in Rd boils down to solving a set of inequalities of the form vT (q -p) ≥ 0 or vT (q - p) > 0. While this can be accomplished, in principle, using generic solvers for polynomial inequalities over the reals, initial experiments revealed that solvers such as QEPCAD 2 and Redlog 3 do not scale beyond trivial instances.

Instead we propose a heuristic method, based on the observation that the inequalities can be efficiently solved using linear programming if either all direction vectors or all points are known. This gives rise to a procedure, inspired by the well-known Expectation-Maximisation method, which alternatingly (1) fixes the points and estimates optimal coordinates for the direction vectors, and then (2) fixes the direction vectors and estimates optimal coordinates for the points. Note that this procedure can only be used to find solutions of consistent problem instances (or approximate solutions of inconsistent instances), which is what is usually needed in applications. We now discuss the method in more detail.

Initialisation: A simple method for initialising the coordinates (c1, ...., cd) of a point π(xi) is to sample each cj from a uniform distribution. As a more informed alternative, we also consider a method which uses multi-dimensional scaling to assign the coordinates such that two points π(xi) and π(xj) are close to each other iff they appear in similar positions in the rankings. Specifically, we use topological sort to obtain a complete ranking of the variables x1, ..., xn for each direction (assuming there are no cycles). This allows us to define a distance on the set of variables as dist(xi, xj) = √∑ℓ (rank(xi, ℓ) - rank(xj , ℓ))2 , where rank(xi, ℓ) is the position of variable xi in the ℓth ranking. Multi-dimensional scaling (MDS) is then used to find coordinates π(x1), ..., π(xn) in Rd such that the Euclidean distance between π(xi) and π(xj) best approximates dist(xi, xj) for each xi and xj. Finally, we also consider a hybrid method, where we generate an initialisation using MDS as well as 49 random initialisations. For each of these 50 initialisations, we estimate the corresponding directions and we select the initialisation which satisfies most of the given EER formulas.

Estimating directions/coordinates: Assume the coordinates of π(x1), ..., π(xn) are fixed, and let us write π(xi) = (ci1 , ..., cid ). Then we can use linear programming (LP) to find suitable values for the coordinates of ρ(1), ..., ρ(m), by minimizing ∑i,j,k ei,j k s.t.:

2 http://www.usna.edu/CS/qepcadweb

3 http://redlog.eu

It is easy to show that the objective function reaches its optimal value of 0 iff (π, ρ) is a d-dimensional solution of Θ, where π(xi) is defined as before and ρ(i) = (λi1 , ..., λid ). In the same way, we can estimate the coordinates of π(x1), ..., π(xn) by taking the values λkl as constants and the values cil as variables.

We have experimented with a few variations of this approach. One possibility is to require that ei,j k ∈ {0, 1} and use a Mixed Integer Programming (MIP) solver instead. This has the advantage that the solution of the linear program would explicitly maximise the number of satisfied EER formulas. However, MIP has a higher complexity than LP, and accordingly this approach was found not to be competitive in initial experiments. We will, however, consider a variant in which the objective function is replaced by

where each constant µi,j k is sampled from a uniform distribution over [0, 1] and N ≥ 1 is a parameter. Because in each step new values µi,j k are used, the method will prioritise different EER formulas each time and thus avoid getting stuck in local optima. The parameter N controls the exploitation-exploration trade-off by determining to what extent the method prioritises a small number of EER formulas.

Finally, in some variants we reset the values of π(xi) to the best values encountered so far if there has not been any improvement for T consecutive iterations (we used T = 250).

5 Experimental Results

We have used CBC 4 for solving the linear programs, with a timeout of 300 seconds; all reported values are the median of 50 executions. In Figures 3 and 4, we write rand, MDS and hyb to denote configurations where the initialisation used random values, MDS, or the hybrid method. We write uni, rand1 and rand2 to indicate whether the uniform objective or the randomised objective (18) was used, and in the latter case, whether we set N = 1 or N = 2. Finally, names ending with -R denote configurations where we reset the values of π(xi) after 250 iterations without improvement.

For the results in Figure 3, we have considered a 20dimensional space of films, for which 40 directions have been obtained using the method from [Derrac and Schockaert, 2014a]. From this space, we generate EER instances with 40 rankings and a variable number of objects. In Figure 3 we observe that (i) MDS substantially outperforms random initialisations and performs better than the hybrid method for sufficiently small problem instances, (ii) N = 1 is better than N = 2, and (iii) the uniform objective outperforms the randomised objective. We found that resetting the values of π(xi) after 250 iterations makes no difference (results not shown).

4 https://projects.coin-or.org/Cbc

Figure 4: Results for the LR-LEFT-ALL benchmark.

Figure 4 illustrates the effectiveness of our reduction from the LR calculus. The problem we consider is the LR-LEFTALL benchmark problem that was proposed in [Lee and Wolter, 2011]. To the best of our knowledge, our method is the first that can find solutions for problem sizes larger than 5 (e.g. Mathematica, QEPCAD and Redlog could not find a solution for size 6, even when given several hours). Interestingly, [van Delden and Mossakowski, 2013] presents a heuristic method that can derive inconsistencies in sets of LR-formulas. This means that a general purpose LR solver could be obtained by combining our method with the method from [van Delden and Mossakowski, 2013] in a portfolio solver.

In Fig. 4, we observe that N = 2 leads to better results than N = 1, and that using the hybrid initialisation and resetting the values of π(xi) after 250 iterations makes a substantial difference. The different conclusions we can draw from Figures 3 and 4 reflect the different nature of the problem instances: the problems in Figure 3 involve a larger number of variables 5 and dimensions, while the problems from Figure 4 appear computationally harder.

6 Conclusions

We have studied the problem of reasoning about direction relations in high-dimensional spaces. Our primary motivation was to support a form of commonsense reasoning about relative properties, based on the view that relative properties such as 'more romantic than' correspond to direction relations in a suitable semantic space. Even though the proposed framework is quite simple, we have shown that several types of qualitative spatial relations can be reduced to our framework, including LR relations and relations that express betweenness, collinearity and parallelism. As a result we obtained that the consistency problem in our framework is ∃Rcomplete. Finally, we have proposed a heuristic method for finding solutions, based on linear programming, and experimentally showed that it scales sufficiently well to be useful in practice.

5 Note however that Fig. 4 only refers to the number of LR objects, not including the variables introduced in the translation.

7 Acknowledgment

Steven Schockaert has been supported by an ERC Starting Grant (637277).