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

Abstract

This work 1 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:" ffl branch-and-bound and constraint satisfaction allow us to "hunt down" non-optimal and impossible solutions and prune them from the search space. ffl 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 The number of possible semantic analyses in an average-sized sentence in the Spanish corpus used ...