Efficient Parameterizable Type Expansion for Typed Feature Formalisms

Hans-Ulrich Krieger, Ulrich Schäfer

Introduction

In modern computational linguistics, Typed Feature Structures (TFS) serve as a foundational method for representing complex linguistic knowledge, such as grammar rules and lexical entries. A "type" acts as a class-like shorthand, encapsulating a set of grammatical constraints. However, for these structures to be computationally actionable—for instance, in parsing or generation—the system must perform Type Expansion (TE). This process involves "unfolding" these shorthands to make all inherited and specific constraints explicit.

Type expansion faces three primary challenges: computational efficiency, the management of recursive definitions (e.g., nested lists), and the need for flexible expansion strategies that can adapt to different Natural Language Processing (NLP) tasks. This paper presents an algorithm designed to address these hurdles through lazy expansion and a novel memoization technique.

Methodology

The proposed approach utilizes a destructive depth-first expansion algorithm characterized by several key innovations:

  • Separation of Logic and Control: The system decouples grammatical information from control knowledge. Users can parameterize expansion via a separate layer of instructions, such as setting maximum depths or prioritizing specific attributes.
  • Indexed Prototype Memoization: To eliminate redundant computations, the system stores "prototypes"—partially or fully expanded versions of types. When a previously encountered type is reached, the system copies the stored prototype instead of re-calculating constraints.
  • Lazy Expansion and Recursion Detection: The algorithm supports delayed expansion, making constraints explicit only when necessary. To handle recursive loops safely, it employs a stack-based approach to identify strongly connected components (SCCs) within type definitions.
Table showing the step-by-step expansion process and recursion handling via the expand stack.

Experimental Evaluation

The algorithm was evaluated within the TDC (Typed Feature Formalism) project, a component of the large-scale Verbmobil speech-to-speech translation project. The test environment consisted of a grammar with approximately 900 type definitions and 250 additional lexicon entries, resulting in a search space of roughly 9,000 nodes that expanded to approximately 50,000 nodes. The system was implemented in Common LISP.

Key Results and Insights

The implementation of Indexed Prototype Memoization led to significant performance gains. As shown in the experimental data, the number of unifications required for expansion dropped from 155,888 to 27,207 when memoization was enabled. This reduction in overhead resulted in a nearly 5x speedup, reducing processing time from 216 seconds to approximately 45 seconds.

Performance comparison of different expansion algorithms with and without memoization, highlighting reductions in time and unifications.

Beyond raw speed, the system provides an "anytime" property. Because expansion is parameterizable and interruptible, it can return useful, albeit incomplete, results at any point—a critical feature for real-time translation systems. Furthermore, by working with type names or partially expanded structures, the system significantly reduces the memory footprint required for large-scale lexicons.

Conclusion

While type expansion with recursion is technically undecidable, this research demonstrates that practical "brute force" controls (like depth limits) and lazy strategies can make these formalisms viable for real-world applications. Future work remains in refining "fair" expansion strategies to ensure termination during local failures and exploring how anytime modules can better manage the theoretical limits of recursive structures.

Summary updated

BibTeX
@inproceedings{krieger1995efficient,
  author = {Hans-Ulrich Krieger and Ulrich Schäfer},
  title = {{Efficient Parameterizable Type Expansion for Typed Feature Formalisms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure