HUNTER-GATHERER: Three Search Techniques Integrated for Natural Language Semantics

Stephen Beale, Sergei Nirenburg - Kavi Mahesh
Computing Research Laboratory
Box 30001
New Mexico State University
Las Cruces, New Mexico 88003
sb,sergei,mahesh@crl.nmsu.edu

In Proc. AAAI-96, Portland, OR. 1996

Abstract:

This work integrates three related AI search techniques -- constraint satisfaction, branch-and-bound and solution synthesis -- and applies the result to semantic processing in natural language (NL). 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'' all optimal solutions avoiding exponential complexity.

Each of the three techniques is briefly described, as well as their extensions and combinations used in our system. We focus on the combination of solution synthesis and branch-and-bound methods which has enabled near-linear-time processing in our applications. Finally, we illustrate how the use of our technique in a large-scale MT project allowed a drastic reduction in search space.

• Introduction
• Hunters and Gatherers in AI
  • Constraint Satisfaction Hunters in NL
  • Solution Synthesis Gatherers in NL
  • Using Branch-and-Bound in an Uncertain World
    • Branch-and-Bound Results
• Conclusion
• References
• About this document ...