An Algorithm for Functional Uncertainty

Ronald M. Kaplan, John T. Maxwell IiiCOLING 1988

TL;DR

This paper introduces and formalizes an algorithm for "functional uncertainty," a linguistic concept that elegantly handles long-distance dependencies in grammar without resorting to complex phrase-structure rules. The authors demonstrate that determining the satisfiability of grammatical descriptions with functional uncertainty is decidable, and they provide an algorithm to compute the relevant solutions, paving the way for more efficient and robust computational linguistics tools.

What Problem Does This Paper Address?

Traditional linguistic theories often struggle to capture "long-distance dependencies" – grammatical relationships where elements are separated by many words (e.g., "Who did you say that John saw?"). These theories typically rely on phrase-structure rules, which can become unwieldy when trying to account for unbounded dependencies. Kaplan and Zaenen proposed "functional uncertainty" as an alternative, using functional equations to describe these relationships. However, the computational implications of this approach, specifically how to efficiently determine if a grammatical description is valid and how to find the resulting grammatical structures, remained an open question. This paper tackles the challenge of developing a concrete algorithm to solve these computational problems for functional uncertainty.

Methods

The core of the paper is the development of an algorithm to handle "functional uncertainty" within the framework of Lexical-Functional Grammar (LFG). The authors build upon the concept of functional uncertainty, which allows for underspecified grammatical constraints expressed as regular expressions over grammatical functions.

Key methodological contributions include:

  • Verification Algorithm: They present an algorithm to determine if a given f-structure (a representation of grammatical information) satisfies a functional description containing uncertainty. This algorithm leverages the decidability of the membership problem for regular sets and uses finite-state automata to manage potentially infinite uncertainty languages. For cyclic f-structures, they employ automaton models to construct regular languages of application strings, enabling efficient verification.
  • Satisfiability Algorithm (Free Descriptions): For a subset of descriptions called "free descriptions" (where interactions between uncertainties are minimal), they show that satisfiability is decidable. This is achieved by transforming the description into a "canonical form" and then instantiating uncertainties with specific strings, allowing standard unification procedures to be applied.
  • Satisfiability Algorithm (General Descriptions): The main algorithmic contribution is a procedure to transform any functional description into an equivalent "free" description. This involves a recursive application of a "Free" operator that resolves interactions between non-free equations by converting them into disjunctions of free equations. This process is shown to terminate for descriptions with acyclic minimal models.
  • Performance Optimizations: The authors discuss several practical optimizations for implementing their algorithms, including using deterministic finite-state machines, handling overlapping cases in the "Free" operator, caching derivative languages, and postponing uncertainty processing until predicates are assigned.

Datasets

Not discussed in the paper. The paper focuses on the theoretical and algorithmic aspects of functional uncertainty and does not present empirical evaluations on specific linguistic datasets.

Key Insights and Ideas

  • Functional Uncertainty is Computationally Tractable: The paper demonstrates that despite the potentially infinite nature of uncertainty expressions (e.g., using Kleene star for unbounded repetition), the problem of determining grammatical satisfiability is decidable. This is a significant theoretical result for computational linguistics.
  • Bridging Theory and Computation: The authors provide a concrete algorithmic bridge between the theoretical linguistic concept of functional uncertainty and practical computational implementation. They show how to compute with these abstract linguistic constraints.
  • "Free" Descriptions Simplify Satisfiability: The concept of "free descriptions" is crucial. By identifying and transforming descriptions into this simpler form, the authors leverage existing, well-understood unification algorithms, making the problem manageable.
  • Interactions Drive Complexity: The core challenge in general descriptions lies in the "interactions" between different uncertainty expressions or between uncertainty and non-uncertainty equations. The "Free" operator elegantly decomposes these complex interactions into manageable disjunctions.
  • Cyclic Structures Pose a Challenge (but are manageable): While cyclic f-structures can lead to non-termination in the satisfiability algorithm, the authors propose methods for detecting these cycles and suggest that many linguistically relevant cyclic cases can still be handled.
  • Performance Gains from Linguistic Constraints: The paper highlights how linguistic constraints (like predicate subcategorization) can be leveraged to significantly improve the performance of uncertainty resolution algorithms, suggesting a tight coupling between linguistic theory and computational efficiency.

Key Results

  • Decidability of Verification: The paper proves that the verification problem for functional descriptions with regular uncertainties is decidable.
  • Decidability of Satisfiability for Acyclic Descriptions: The authors show that the satisfiability problem is decidable for functional descriptions that characterize acyclic structures.
  • Algorithm for Transforming to Free Form: A procedure is presented to convert any functional description into an equivalent "free" description, enabling satisfiability testing.
  • Identification of Linguistically Relevant Models: The paper argues that despite the potential for infinite models due to uncertainty, there is a finite set of "grammatically relevant" or "smallest" models, which can be systematically identified.

Limitations and Future Work

  • Termination with Cyclic Models and Infinite Uncertainties: The authors acknowledge that their satisfiability procedure may not terminate for descriptions with cyclic models that interact with infinite uncertainty languages. While they propose detection mechanisms, guaranteeing completeness in all such cases remains an open question.
  • Linguistic Significance of Lost Solutions: It is an open question whether the potential solutions that might be lost through early termination in cyclic cases are linguistically significant.
  • Generalization of the "Free" Operator: While the paper focuses on regular languages for uncertainty, the authors suggest that the "Free" operator could potentially be generalized to handle other types of languages.
  • Further Optimization: The paper outlines several performance considerations and optimizations, indicating that ongoing work in efficient disjunction processing is crucial for practical applications.
  • Broader Applicability: The authors suggest that the concept of functional uncertainty could be adapted to other unification grammar formalisms and applied to phenomena beyond typical long-distance dependencies, such as scope ambiguities.

Summary updated

BibTeX
@inproceedings{kaplan1988algorithm,
  author = {Ronald M. Kaplan and John T. Maxwell III},
  title = {{An Algorithm for Functional Uncertainty}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1988},
}
Figure