Controlled Active Procedures as a Tool for Linguistic Engineering

Heinz-Dirk Luckhardt, Manfred ThielCOLING 1986

TL;DR

This paper introduces Controlled Active Procedures (CAP), a novel grammar formalism and parsing strategy designed for efficient and robust natural language analysis, particularly for free-word-order languages like German. CAP aims to overcome limitations of traditional context-free grammars by integrating linguistic knowledge and control structures into a unified framework, enabling more flexible and linguistically motivated parsing.

What Problem Does This Paper Address?

Traditional context-free grammars (CFGs) struggle with the complexities of natural language, especially languages with flexible word order. While extensions like GPSG and LFG offer solutions, they often rely on complex mechanisms like meta-rules or separate structure representations. The authors highlight the difficulty of handling non-standard word orders and the need for a more integrated approach that directly represents linguistic knowledge and parsing strategies. They aim to develop an efficient parser for random natural language texts based on a sound theoretical foundation, drawing from years of experience in computational linguistics and machine translation.

Methods

CAP is built around a novel grammar formalism and a control structure that combines "scouts" and "missions."

  • S-graph Data Structure: CAP uses an S-graph, an acyclic directed graph, to represent the data structure. Arcs carry "decorations" which include morphosyntactic type, syntactic functions, semantic relations, and other properties.
  • Controlled Active Procedures (CAP): This is the core concept.
  • Missions: High-level linguistic tasks that are hierarchically organized. Missions select relevant sections of the data structure ("expectations") and delegate subproblems to other missions or scouts.
  • Scouts: Elementary tasks that select specific paths (sequences of arcs) from the S-graph and attempt to apply a set of rules. Scouts can operate in different modes: parallel, stratificational, preferential, and iterative.
  • Augmented CF-Rules: CAP rules are augmented, meaning they include conditions for application and assignments to the right-hand side, going beyond simple structure building.
  • Feature Propagation: Unlike unification-based systems, CAP uses explicit feature propagation mechanisms, allowing for more controlled and linguistically motivated feature sharing and inheritance, especially crucial for languages with complex agreement phenomena.
  • Transformations: While not central to the parsing strategy, transformations are possible in CAP and are used for "normalizing" surface structures to simplify rule writing or to reconstruct deep structures for disambiguation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Linguistic Engineering Focus: CAP is presented not just as a parsing theory but as a tool for "linguistic engineering," emphasizing the practical aspects of rule writing, parsing strategies, and representation of meaning.
  • Direct Representation of Linguistic Knowledge: The framework integrates linguistic knowledge (lexical, syntactic, semantic) directly into the rules and control structures, aiming for a more intuitive and efficient system.
  • Flexibility for Free-Word-Order Languages: The approach of accepting constituents where they are found in the utterance, rather than relying on transformations to move them to a canonical position, is a key advantage for languages like German.
  • Controlled Feature Propagation: Moving away from unification, CAP's explicit feature propagation allows for finer control over how features are inherited and matched, avoiding undesirable side effects often seen with unification.
  • Hierarchical Control Structure: The mission-scout hierarchy provides a clear and explicit control mechanism for the parser, allowing linguists to define sophisticated parsing strategies.

Key Results

The paper focuses on introducing the CAP formalism and its underlying principles rather than presenting extensive quantitative results. It describes how CAP can handle:

  • The ambiguity of phrases like "trouble with Max" through S-graph representations.
  • The direct representation of constituents in their actual positions, exemplified by "Wen liebst du?" (Whom do you love?).
  • The application of rules with conditions, such as valency-based restrictions.
  • The analysis of detached verbal prefixes in German.

The authors state that the CAP-parser for German (CAP-G) is currently being developed, suggesting ongoing work and validation.

Limitations and Future Work

  • Development Stage: The CAP-G parser is described as "currently being developed," indicating that it is not yet a fully mature system.
  • Feature Propagation Complexity: While advocating for explicit feature propagation over unification, the paper acknowledges that achieving this in a linguistically motivated way can be complex.
  • Future Work: The paper mentions that the interaction of these aspects (linguistic knowledge and strategies) is being formalized by Thiel in his NLPT (Natural Language Processing Theory). The development of CAP-G itself represents ongoing future work. The authors also suggest that CAP's methods can be applied to various linguistic phenomena, including normalization, agreement conditions, free word order, and complex coordination.

Summary updated

BibTeX
@inproceedings{luckhardt1986controlled,
  author = {Heinz-Dirk Luckhardt and Manfred Thiel},
  title = {{Controlled Active Procedures as a Tool for Linguistic Engineering}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1986},
}
Figure