Qualitative Reasoning about Directions in Semantic Spaces

Steven Schockaert, Jae Hee LeeIJCAI 2015 · OpenReview

Abstract

We introduce a framework for qualitative reasoning about directions in high-dimensional spaces, called EER, where our main motivation is to develop a form of commonsense reasoning about semantic spaces. The proposed framework is, however, more general; we show how qualitative spatial reasoning about points with several existing calculi can be reduced to the realisability problem for EER (or REER for short), including LR and calculi for reasoning about betweenness, collinearity and parallelism. Finally, we propose an efficient but incomplete inference method, and show its effectiveness for reasoning with EER as well as reasoning with some of the aforementioned calculi.

Introduction

In computational linguistics, entities such as films or cities are frequently represented as points in high-dimensional Euclidean spaces. Within these "semantic spaces," directions often correspond to interpretable properties—for instance, a specific vector might represent the concept of being "more violent" or "more hilarious." While methods for extracting these relations from text are abundant, robust mechanisms for reasoning about them have been lacking.

A 2D semantic space of movies where directions represent properties like 'gripping' and 'hilarious'.

Consider a system that asserts "Movie A is funnier than Movie B" and "Movie B is funnier than Movie C," but also "Movie C is funnier than Movie A." Such a set of assertions is geometrically inconsistent. This paper addresses the challenge of checking the consistency of relational assertions in high-dimensional spaces, a task that is computationally prohibitive using traditional logic-based or exact algebraic methods.

The EER Framework

The authors introduce EER (Euclidean Embedding of Rankings), a framework designed for reasoning about directions in high-dimensional spaces. An EER formula specifies that the projection of one point onto a specific direction vector must be less than or equal to the projection of another point.

The paper establishes three major technical contributions:

  1. Reductions: It is proven that several existing spatial calculi—including the $\mathcal{LR}$ calculus (dealing with left/right/betweenness) and constraints like collinearity and parallelism—can be reduced to the EER realisability problem.
  2. Complexity Analysis: Deciding the realisability of a set of EER formulas in $\mathbb{R}^d$ is shown to be $\exists\mathbb{R}$-complete, placing it between NP and PSPACE in terms of complexity.
  3. Iterative Heuristic Solver: Because exact solvers like QEPCAD fail on even small instances, the authors propose an iterative method inspired by Expectation-Maximization (EM). This solver alternates between fixing point coordinates to find optimal direction vectors via Linear Programming (LP) and fixing direction vectors to find optimal point coordinates.

Experimental Evaluation

The approach was evaluated using two primary datasets: a 20-dimensional Film Semantic Space with 40 property directions, and the $\mathcal{LR}$-LEFT-ALL Benchmark, a standard for spatial reasoning consistency checking.

A key finding was that the choice of initialization for the iterative solver significantly impacts performance. Using Multi-Dimensional Scaling (MDS) to initialize point coordinates based on their topological sort in the rankings proved far more effective than random initialization.

Computation time comparison for different initialization strategies as the number of objects increases.

Key Results and Insights

  • Scalability: The iterative solver successfully processed instances of the $\mathcal{LR}$-LEFT-ALL benchmark where exact solvers (such as QEPCAD and Redlog) timed out after several hours.
  • Dimensionality as Regularity: The authors suggest that the minimum dimension $d$ required to satisfy a set of constraints serves as a measure of "plausibility." A set of facts requiring a very high-dimensional space to be consistent may be less regular or plausible than one fitting in a lower-dimensional space.
  • Noise Reduction: The ultimate utility of these geometric checks lies in filtering out "implausible" assertions generated by automated relation extraction tools, which often suffer from low precision despite high recall.

Conclusion

The EER framework provides a practical bridge between natural language processing and spatial reasoning. While the iterative method is a heuristic and thus "incomplete" (it cannot strictly prove inconsistency), its efficiency makes it a viable tool for high-dimensional semantic reasoning. Future work includes integrating this framework into live text-processing pipelines and extending it to handle more complex, higher-order qualitative relationships.

Summary updated

Abstract

We introduce a framework for qualitative reasoning about directions in high-dimensional spaces, called EER, where our main motivation is to develop a form of commonsense reasoning about semantic spaces. The proposed framework is, however, more general; we show how qualitative spatial reasoning about points with several existing calculi can be reduced to the realisability problem for EER (or REER for short), including LR and calculi for reasoning about betweenness, collinearity and parallelism. Finally, we propose an efficient but incomplete inference method, and show its effectiveness for reasoning with EER as well as reasoning with some of the aforementioned calculi.
BibTeX
@inproceedings{schockaert2015qualitative,
  author = {Steven Schockaert and Jae Hee Lee},
  title = {{Qualitative Reasoning about Directions in Semantic Spaces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=S14wt7GOZB},
}
Figure