Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces

Steven Schockaert, Sanjiang LiIJCAI 2018 · OpenReview

TL;DR

This paper tackles the challenge of representing and reasoning about concepts using qualitative spatial constraints, specifically focusing on "betweenness" relationships within the RCC8 framework. The authors show that general reasoning with these constraints is computationally hard (PSPACE-hard) but identify a specific, practical fragment for which reasoning becomes tractable (NP-complete), paving the way for more robust qualitative spatial reasoning systems.

What Problem Does This Paper Address?

Representing knowledge about concepts is a fundamental problem in AI. Traditional ontology languages offer precision but struggle with inductive reasoning, while vector embeddings excel at induction but lack precise logical relationships. Conceptual spaces offer a geometric approach, modeling concepts as convex regions in a high-dimensional space, bridging this gap. However, learning these exact geometric representations from data is difficult.

This paper explores a middle ground: using qualitative abstractions of conceptual spaces. Instead of precise geometric definitions, they use spatial relationships like "A is contained in B" or "A is adjacent to B." A key addition is the concept of betweenness: if concept A is "between" concepts B and C, it implies a continuous transition from B to A to C. This is crucial for inductive reasoning, as seen in the example where knowing fine-dining and fast-food restaurants require licenses might lead us to infer bistros also need one, due to bistros being conceptually "between" them.

The core problem addressed is: can we determine if a set of qualitative spatial constraints, including betweenness, can be realized by actual convex, bounded regions in a Euclidean space? This is essential for ensuring the consistency and plausibility of our qualitative representations.

Methods

The paper introduces an extension of the Region Connection Calculus (RCC8) to handle betweenness constraints. RCC8 defines a set of primitive spatial relations (like Disjoint, Externally Connected, etc.) between regions. The authors extend this by allowing constraints involving convex hulls of unions of regions, specifically to model betweenness.

Their main contributions are:

  1. PSPACE-hardness: They prove that deciding whether a general RCC8 network with betweenness constraints can be realized by convex, bounded regions is PSPACE-hard. This is attributed to a recursive process where new constraints can be generated from existing ones, leading to complex dependencies.
  2. NP-complete Fragment: They identify a specific, "non-recursive" fragment of RCC8 networks. A network is non-recursive if it doesn't contain specific combinations of constraints (like u NTPP v and v EC w). For this fragment, they show that deciding realizability is NP-complete.
  3. Ranking-Based Models: A key insight is that for this NP-complete fragment, the realizability of a network by convex regions can be characterized by a set of "rankings." These rankings assign numerical values to variables, and their relative order captures the betweenness relationships. This is a significant simplification, as it allows for a more compact representation of complex spatial relationships.
  4. Constructing Convex Solutions: They provide a constructive method to build a convex solution (using hyperrectangles) when the ranking conditions are met. This demonstrates that the NP-complete fragment is not just theoretically tractable but also practically constructible.

Datasets

Not discussed in the paper. The paper focuses on theoretical reasoning and constraint satisfaction rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Betweenness is Key for Induction: The paper strongly emphasizes that betweenness is a crucial qualitative notion for enabling plausible inductive inferences, going beyond simple subsumption or disjointness.
  • The Cost of Generality: The general problem of realizing RCC8 networks with betweenness is computationally expensive (PSPACE-hard), highlighting the trade-off between expressiveness and tractability.
  • Simplification via Rankings: The discovery that realizability for a specific fragment can be reduced to checking a set of rankings is a major breakthrough. This transforms a geometric problem into a combinatorial one, which is often more amenable to efficient algorithms.
  • Compact Representation: The ranking-based models offer a compact way to represent complex betweenness relationships that would otherwise require exponentially many statements. This is highly valuable for practical applications.
  • Non-Recursiveness as a Tractability Condition: The identification of "non-recursive" networks as the key to NP-completeness provides a clear criterion for when efficient reasoning is possible.

Key Results

  • PSPACE-hardness: Deciding realizability of general RCC8 networks with betweenness constraints is PSPACE-hard.
  • NP-completeness: Deciding realizability for basic, non-recursive RCC8 networks with betweenness constraints is NP-complete.
  • Ranking Characterization: The paper establishes a necessary condition for realizability based on the existence of specific ranking functions, which is shown to be sufficient for the NP-complete fragment.
  • Constructive Proof: A method is provided to construct a convex solution (using hyperrectangles) from these rankings, demonstrating the practical relevance of the NP-complete fragment.

Limitations and Future Work

  • Convexity vs. Non-Convexity: The paper primarily focuses on convex solutions. A limitation is that the general problem of deciding satisfiability without the convexity requirement is still open and is noted as a direction for future work.
  • Boolean Region Terms: The authors suggest combining betweenness reasoning with Boolean region terms (like unions and intersections) as another important avenue for future research.
  • Learning from Text: A significant open question is how to learn these qualitative RCC8 encodings of conceptual knowledge directly from text, which would be a major step towards practical applications.
  • Generalization of Hyperrectangles: While the paper constructs solutions using hyperrectangles, it acknowledges that sometimes multiple hyperrectangles might be needed for a single variable, indicating potential complexity in the construction.

Summary updated

Abstract

Conceptual spaces are a knowledge representation framework in which concepts are represented geometrically, using convex regions. Motivated by the fact that exact conceptual spaces are usually difficult to obtain, we study the problem of spatial reasoning about qualitative abstractions of such representations. In particular, we consider the problem of deciding whether an RCC8 network extended with constraints about betweenness can be realized using bounded and convex regions in a high-dimensional Euclidean space. After showing that this decision problem is PSPACE-hard in general, we introduce an important fragment for which deciding realizability is NP-complete.
BibTeX
@inproceedings{schockaert2018reasoning,
  author = {Steven Schockaert and Sanjiang Li},
  title = {{Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=S1EPx4zdZS},
}
Figure