Next: Problem Statement
DEPENDENCY-DIRECTED TEXT GENERATION
Stephen Beale
MCCS-94-272
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.
This research represents the author's ``Master's Project in
Computational Linguistics'' completed at Carnegie Mellon University.
Special thanks to my committee members Barbara Di Eugenio and David
Evans. I would particularly like to thank Sergei Nirenburg, my
principal advisor, without whom this work would not have been possible.
Abstract:
This paper describes an experimental text generation system that recognizes
and takes advantage of the inter-dependencies present among the decision
points in a typical text planning instance. The following are the main
contributions of this work, each of which will be discussed in detail:
- ISLAND DRIVEN: takes advantage of ``islands of certainty'' in input,
along with islands created as the planner further constrains problem
- OPPORTUNISTIC: ``looks ahead'' for information as needed;
prevents needless backtracking
- SOUNDNESS: keeps track of pre-conditions, automatically detects
when a rule's pre-conditions can no longer be satisfied, automatically detects
pre-condition ``clobbering'' (Chapman 87)
- OPTIMIZED: rule set dependencies pre-analyzed to the point where
all effects of instantiating a rule are known beforehand, and processing is reduced to
a trip through a tree of 0's and 1's
- MODIFIED RECURSIVE DESCENT ALGORITHM: takes advantage
of above features to eliminate greater than 80 percent of processing in the example
text
A sample text of 26 input propositions was encoded in a specially developed
interlingual language, and, using a set of about 70 text structure rules along
with about 500 lexical rules to cover the input concepts and differing levels of
formality and simplicity, text plans were produced. A simple surface generator
was also created to display the resulting text.
Results
A large improvement over basic recursive descent planning algorithms was
obtained. This improvement came in two areas:
- ability to prune the search space
- number of rules in tree before processing: 715
- number of rules after ``look-ahead'': 305
- number of rules after initial island processing: 156 (of which only 62 represent
non-island rules)
- extent of backtracking
- To find the first 10 answers in example text:
- nodes traversed using soundness, island processing, optimization: 41
- nodes traversed without these: 55 (34 percent increase)
The text will describe how each of these results were obtained and what kind
of improvement can be expected in general text generation applications. Further
research needed and possible additional applications of this method are also
discussed.
Table of Contents
- Problem Statement 4
- Significance to Computational Linguistics 5
- Literature Review 7
- Project Walk-Through 34
- Discussion of Main Features 56
- Island Driving 56
- Opportunistic Abilities 56
- Soundness 57
- Optimization 59
- Modified Recursive Descent Algorithm 59
- Evaluation 61
- Future Research 65
- Bibliography 66
Next: Problem Statement
Steve Beale
Tue Oct 1 12:13:07 MDT 1996