Semantic Evaluation as Constraint Network Consistency

Nicholas J. HaddockAAAI 1992

Abstract

Resolving complex noun phrases, such as "the man who visits the town near the river," is a fundamental task in natural language processing known as referential evaluation. While general logic-based search is theoretically NP-complete, this paper demonstrates that the semantic structures of many natural language fragments are inherently "tree-like." By framing reference resolution as a Constraint Satisfaction Problem (CSP), the author proves that these structures can be solved efficiently in polynomial time using arc consistency algorithms, bridging the gap between theoretical complexity and the practical efficiency of human language processing.

Introduction: The Complexity of Reference

In natural language processing, referential evaluation involves identifying specific entities in a world model that satisfy a given description. For instance, given a database of entities, a system must find the unique individual corresponding to a complex description. Traditionally, this task was approached as a general search problem using techniques like backtrack search. However, because general CSPs are NP-complete, the computational cost could theoretically explode as sentences grow in length. This paper addresses the discrepancy between this theoretical "hardness" and the apparent ease with which such references are resolved in practice by analyzing the topology of linguistic constraints.

Methodology

The author bridges linguistics and constraint satisfaction theory through a three-step formalization:

  1. CSP Formulation: The discourse context is modeled as a set of first-order logic facts, while the noun phrase is treated as a set of variables and constraints.
  2. The NPG1 Fragment: A specific grammar fragment, NPG1, is defined to cover common structures like adjectival modification, relative clauses, and prepositional phrases.
  3. Graph Topology Analysis: The core contribution is the proof that the grammar rules of NPG1 naturally produce tree-structured constraint networks.

Graph Topology and Arc Consistency

In a constraint graph, nodes represent variables (entities) and edges represent the relationships between them. A "tree" structure implies the absence of cycles, which significantly simplifies the search space.

Figure 1: A tree-structured constraint network representing the phrase 'the man who visits the town near the river'.

By applying established theorems in CSP theory (notably from Montanari and Freuder), the author shows that tree-structured problems can be solved perfectly using "strong arc consistency." This is a local filtering process that ensures every value in a variable's domain has a compatible neighbor. For tree-like graphs, this local consistency is sufficient to reach a global solution without the need for exponential backtracking.

Key Insights

  • Structure-Dependent Complexity: The difficulty of a linguistic problem is determined by its topological "shape" rather than its size. The compositional nature of language often prevents the complex "cross-talk" that leads to NP-completeness.
  • Efficiency of Local Filtering: The paper demonstrates that local consistency checks reduce the complexity of reference resolution to $O(a^2e)$, where $a$ is the domain size and $e$ is the number of constraints. This provides a formal justification for why simpler, "low-power" consistency techniques used in earlier NLP systems were effective.
  • Identifying Cyclic Exceptions: The author identifies specific linguistic phenomena that break the tree-like assumption and introduce cycles, which may require more powerful algorithms:
  • Lexical Decomposition: Breaking a single word into multiple interdependent constraints.
  • Parasitic Gaps: Syntactic structures where a single variable is double-bound.
  • Bound-Variable Anaphora: Sentences like "a man who visits a town near his birthplace," where the pronoun creates a loop back to the initial subject variable.

Conclusion and Future Directions

This research provides a formal theoretical foundation for the efficiency of semantic evaluation. While the current model handles simple noun phrases effectively, future work is required to extend this framework to handle quantifiers (e.g., "each," "every"), plurals, and intensional expressions (e.g., "John believes..."). For structures containing cycles, the author suggests that higher-order techniques like path consistency may offer a polynomial-time solution, though this remains an area for further investigation.

Summary updated

BibTeX
@inproceedings{haddock1992semantic,
  author = {Nicholas J. Haddock},
  title = {{Semantic Evaluation as Constraint Network Consistency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure