TL;DR
This paper introduces a unified computational architecture for natural language parsing and generation, treating both as instances of a single theorem-proving process. By parameterizing a deduction system with initial conditions, priority functions, and success criteria, the authors demonstrate how a single architecture can flexibly handle diverse processing strategies, including psycholinguistically motivated parsing models.
What Problem Does This Paper Address?
Traditionally, natural language processing systems for parsing (understanding) and generation (producing language) have been developed using separate, specialized architectures. This leads to duplicated effort and a lack of theoretical elegance. The core problem this paper addresses is the desire for a single, unified architecture that can perform both parsing and generation using the same underlying grammar and processing mechanism. The authors propose that viewing both parsing and generation as forms of logical deduction, where the grammar acts as a set of rules and the input/output are treated as premises or goals, allows for such unification.
Methods
The paper's central contribution is a parameterized theorem-proving architecture for language processing. This architecture is built upon the idea of parsing as deduction, where grammars are treated as logical theories. The key components are:
- Deductive Framework: The architecture uses two basic inference rules: prediction (instantiating grammar rules) and completion (resolving conditional expressions with non-conditional lemmas).
- Agenda-Based Tabular Theorem Prover: To manage the potentially redundant and nondeterministic nature of deduction, the system employs an agenda structured as a priority queue to store lemmas (intermediate results).
- Parameterization: The core novelty lies in parameterizing this theorem prover. The system can be configured by varying:
- Initial Conditions: What axioms are initially placed on the agenda (e.g., lexical items for parsing, grammar rules for generation).
- Priority Function: How lemmas are ordered on the agenda, influencing the search strategy (e.g., favoring items ending earlier for parsing, or items related to the goal meaning for generation).
- Success Criterion: What constitutes a successful proof (e.g., a complete parse of a string, or a generated phrase matching a target logical form).
This parameterization allows the same architecture to implement diverse processing strategies, including mimicking Earley's parsing algorithm, implementing shift-reduce parsing, and enabling goal-directed generation.
Datasets
Not discussed in the paper. The paper focuses on the architecture and its theoretical underpinnings, using illustrative examples with toy grammars and sentences rather than formal datasets.
Key Insights and Ideas
- Parsing and Generation as Duals of Deduction: The most significant insight is that parsing and generation can be viewed as two sides of the same deductive coin. Parsing seeks to prove a string's grammaticality given a meaning, while generation seeks to prove the existence of a string given a meaning.
- Unified Architecture through Parameterization: The paper demonstrates that a single, flexible architecture can achieve both parsing and generation by abstracting the core deductive process and parameterizing its control and initialization. This moves beyond simply using the same grammar formalism.
- Psycholinguistic Modeling: The architecture's ability to tune its priority function allows it to model psycholinguistic phenomena like right-association and minimal attachment, showing that theoretical elegance can align with empirical observations.
- Semantic Indexing for Generation: For generation, indexing by semantic content (rather than string position) is crucial for efficiency and goal-direction, especially when combined with the concept of semantic monotonicity in grammars.
Key Results
The paper presents the architecture and demonstrates its capabilities through examples:
- Parsing: The architecture successfully implements parsing strategies that mimic Earley's algorithm and shift-reduce parsing, including the ability to model psycholinguistic preferences for disambiguation.
- Generation: The architecture can be configured to generate sentences from logical forms. An example shows the generation of "Sonny loves Kait passionately" from the logical form
passionately(love(sonny, kait)). - Efficiency: The implemented generator is reported to be "more than an order of magnitude faster" than a previous PATR generator, attributed to the goal-directed nature enabled by semantic filtering.
Limitations and Future Work
- Semantic Monotonicity Constraint: The generation process relies on the assumption of "semantic monotonicity" in grammars, which ensures that subphrase semantics contribute to the overall meaning. Finding weaker constraints that still allow efficient processing is an important research objective.
- Indexing Efficiency: Indexing by highly structured logical forms in generation is less efficient than indexing by string positions in parsing. Techniques like partial match retrieval are suggested for improvement.
- Logical Form Equivalence: A fundamental challenge in generation is the many-to-one mapping from logical forms to natural language expressions. The paper discusses the problem of "intentional equivalence" and the need for canonical logical forms that precisely match the grammar's structure.
- Completeness of Generation: While the semantic filter aims for goal-direction, ensuring that all desired syntactic and semantic properties are realized in the generated sentence remains a challenge.
- Future Work: The authors suggest exploring weaker semantic constraints, improving indexing techniques, and addressing the logical form equivalence problem more deeply. They also note the potential for applying their architecture to more complex formalisms and for modeling phenomena like garden-path sentences.
Summary updated