HUNTER-GATHERER TUTORIAL

Welcome to the Mikrokosmos Semantic Analyzer Tutorial. This tutorial is taken from a talk at AAAI96 describing the new control architecture, HUNTER-GATHERER, and how it can be applied to computational semantics.

Here's the abstract from the technical report which describes the system in more detail:

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.

• HUNTER-GATHERER Intro
• What in the world does HUNTER-GATHERER mean??
• The problem to be solved
• How do we figure out which combination is best?
• Noun Phrase Complexity
• Clause Complexity
• Exponential Explosion
• OPTIONS
• AI Search Techniques
  • Constraint Satisfaction
  • Solution Synthesis
  • Branch-and-Bound
• Applying the AI Techniques to Computational Semantics
• Using HG - An Example
• Constraint Graph
• Creating ``Circles''
• How does this help?
• Where does Branch-and-Bound come in?
• Applying Branch-and-Bound to Circle 1
• Applying Branch-and-Bound to Circle 2
• Applying Branch-and-Bound to Circls 2 and 3
• Applying Branch-and-Bound to Circles 1 and 4
• What are the results for real texts?
• Conclusion
• References
• About this document ...