HUNTER-GATHERER:
Applying Constraint Satisfaction, Branch-and-Bound and Solution Synthesis to Computational Semantics

Stephen Beale
MCCS-96-289
Computing Research Laboratory
Box 30001
New Mexico State University
Las Cruces, New Mexico 88003

The Computing Research Laboratory was established by the New Mexico State Legislature, under the Science and Technology Commercialization Commission as part of the Rio Grande Research Corridor.

Abstract:

This work integrates three related AI search techniques and applies the result to processing computational semantics, both in the analysis of source text to discover underlying semantics, as well as in the planning of target text using input semantics. We summarize the approach as ``Hunter-Gatherer:''

• Branch-and-Bound and Constraint Satisfaction allow us to ``hunt down'' non-optimal and impossible solutions and prune them from the search space.
• Solution Synthesis methods then ``gather together'' all optimal solutions while avoiding exponential complexity.

Each of these three general AI techniques will be described. We will look at how how they have been used to solve a variety of problems. These general techniques were extended or used in novel ways in this project. We will describe these extensions in detail and give examples of how they were applied to computational semantic processing. A major contribution of this work will also be in showing how and why Natural Language is a prime candidate for applying these methods, and how they can enable near-linear time processing. As part of this discussion, we will demonstrate the important result that by converting Text Planning to a constraint satisfaction problem, Means-End type planning can be replaced by an efficient constraint-based search through a complex tree. Finally, we will examine the results in the light of the Mikrokosmos Machine Translation project. This project is a large-scale Spanish-English MT system implemented at New Mexico State University. We will be able to evaluate the control mechanism presented here against a large corpus of sample texts. In particular, we will show that a search space in the billions (or in some cases ga-zillions) can be reduced to a few thousand or less, with a corresponding decrease in run-time.

• Contents
• Introduction
  • Hunters and Gatherers in AI: An introduction to constraint-based AI techniques
  • Hunters and Gatherers in Computational Semantics
    • Applying the AI techniques to Computational Semantics
    • Natural-Language - a ``Natural'' Constraint Satisfaction Problem
• Hunters and Gatherers in AI
  • Constraint Satisfaction Problems
  • Solution Synthesis
  • Branch-and-Bound
  • Other Strategies for CSPs
• Hunters and Gatherers in Computational Semantics
  • Constraint Satisfaction Hunters in Computational Semantics
    • Identifying ``Circles'' of Dependency
    • Setting Up Constraint Dependencies
  • Solution Synthesis Gatherers in Computational Semantics
  • Using Branch-and-Bound in an Uncertain World
    • Implementing Branch-and-Bound
    • Branch-and-Bound Results
  • Constraint Satisfaction in Natural Language Generation: The PICARD Text Planning System
    • Text Planning for Machine Translation
    • Using Constraint Satisfaction to Enable Abstractions
  • Natural Language - a ``Natural'' CSP
    • Local Dependency in Computational Semantics
    • Classes of Problems for which HUNTER-GATHERER is Beneficial
• Discussion
  • Planning and Island Processing
  • Formal Properties of HUNTER-GATHER: Soundness and Completeness
    • Soundness
    • Completeness
• Conclusion
• Acknowledgements
• References
• About this document ...