Hunter-Gatherer: Three Search Techniques Integrated for Natural Language Semantics

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Semantics & Discourse

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.