Word-Order Variation in Natural Language Generation

Aravind K. JoshiAAAI 1987

Abstract

Word-order variation in natural language generation (NLG) is often treated as a peripheral adjustment. This paper argues for its inclusion as a core grammatical feature. By leveraging Tree Adjoining Grammars (TAGs) and separating structural relationships from linear precedence within "elementary trees," the author demonstrates a flexible framework that accommodates complex word-order phenomena, such as scrambling, while supporting incremental sentence generation.

Introduction

In the late 1980s, a significant challenge in Natural Language Generation (NLG) was the interface between planning (determining what to say) and realization (determining how to say it). Word-order variation—the way different languages or contexts shift words for emphasis or focus—posed a major hurdle. Most existing frameworks treated word order as a post-processing step or a simple permutation of tree nodes. However, the author argues that this approach is cognitively and computationally unsatisfying, especially for languages where "scrambling" can move words across long distances. The challenge was to find a grammatical formalism that could handle this flexibility while maintaining the underlying semantic dependencies.

Methodology: Tree Adjoining Grammars (TAG)

The paper leverages the Tree Adjoining Grammar (TAG) formalism, pioneered by Aravind Joshi. Unlike standard grammars that generate strings, TAG generates trees. It uses a finite set of "elementary trees"—initial trees for basic structures and auxiliary trees for recursion—and a single composition operation called adjoining.

The Adjoining Operation

Adjoining allows an auxiliary tree to be inserted into another tree at a specific node, effectively "stretching" the structure. This operation is crucial because it allows the grammar to handle recursion while maintaining the local dependencies defined within the original elementary trees.

The adjoining operation in TAG, showing how an auxiliary tree β is inserted into an initial tree γ.

Elementary Structures and Extended Locality

A key innovation of TAG is the "Extended Domain of Locality." Dependencies, such as a verb requiring a specific object, are defined within the elementary trees themselves. The author proposes viewing these as "Elementary Structures" composed of two parts:

  1. Domination Structure: The hierarchical parent-child relationships.
  2. Linear Precedence (LP) Statements: Rules defining the order of nodes across the entire tree.

By defining LP statements over the whole elementary tree—rather than just between immediate siblings—TAG can handle non-local variations. When trees are adjoined, their LP statements merge, naturally producing complex, interleaved word orders.

Examples of elementary trees (auxiliary trees β1, β2, β5) for English verbs, demonstrating how dependencies are localized.

Key Insights

  • Word Order as Pragmatics: Word order is not merely a surface feature; it conveys pragmatic information (e.g., topic vs. focus). Thus, the generator's planner must influence word order early in the realization process.
  • Factoring Recursion: By separating recursion (via adjoining) from basic dependencies, TAG maintains local constraints like subject-verb agreement even when constituents are separated by intervening clauses.
  • Mild Context-Sensitivity: TAGs are "mildly context-sensitive," providing the necessary power to model "scrambling" in languages like Finnish without the complexity of fully context-sensitive systems.
  • Incremental Generation: The compositional nature of TAG—building sentences from small, self-contained structures—is inherently suited for incremental generation, allowing a system to begin outputting a sentence before the entire plan is finalized.

Results and Discussion

The paper provides a formal proof of concept, showing how TAG can generate "moved" constituents simply by adjusting LP statements within an elementary structure. It successfully models complex Finnish scrambling examples, where verbs and complements are separated by multiple words, through standard adjoining processes rather than specialized "movement" rules. Furthermore, the author demonstrates that TAG offers a more powerful and flexible domain of locality compared to other frameworks like the ID/LP format in Generalized Phrase Structure Grammar (GPSG), specifically because TAG's domain of locality is larger.

Conclusion

While the theoretical framework is sound, several areas remain for future exploration. Implementation details for high-performance generators and the specific algorithms for choosing between valid LP statements based on pragmatic goals need further development. Additionally, the computational trade-offs of using mildly context-sensitive grammars in real-time generation warrant more detailed study.

Summary updated

BibTeX
@inproceedings{joshi1987word,
  author = {Aravind K. Joshi},
  title = {{Word-Order Variation in Natural Language Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure