TL;DR
This paper proposes a new, computationally efficient "Binding rule" for natural language parsing, framed within the Government-binding (GB) theory. It aims to improve upon existing GB parsing approaches by offering a more psychologically plausible and practical method for identifying pronoun and anaphor references, avoiding the inefficiencies of "generate-and-test" methods.
What Problem Does This Paper Address?
Understanding how pronouns and anaphors (like "himself" or "her") refer to other noun phrases (NPs) in a sentence is crucial for natural language processing. This is known as anaphora resolution. The Government-binding (GB) theory, a prominent linguistic framework, attempts to define the syntactic rules governing these coreference relations. However, existing GB parsing implementations based on Chomsky's original Binding theory face significant computational challenges. Specifically, the "generate-and-test" approach, where potential interpretations are generated and then checked against well-formedness conditions (axioms), is highly inefficient. This paper addresses the need for a more practical and computationally feasible method to implement the Binding theory within a parser, making it suitable for real-world applications. It also aims to handle certain linguistic phenomena, like crossover binding, more elegantly.
Methods
The paper proposes a new "Binding rule" specified using attribute grammar rules. This rule directly assigns referential indices to NPs in a syntactic tree, ensuring that the Binding axioms are satisfied by construction, rather than being checked post-hoc. This procedural approach avoids the "generate-and-test" problem.
Key aspects of the method include:
- Attribute Grammar: The rule is defined as a set of attribution rules associated with productions in the base grammar. This allows for the incremental definition of attributes at each node of the parse tree.
- AAS and PAS Attributes: Two crucial attributes are introduced:
- AAS (Anaphoric Antecedent Set): For a given NP, this set contains c-commanding NPs within its local domain that are potential antecedents for an anaphor.
- PAS (Pronominal Antecedent Set): This set contains NPs that do not c-command the current NP or are outside its local domain, serving as potential antecedents for pronouns.
- Procedural Assignment: The rule directly computes these AAS and PAS sets and uses them to assign a referential index to each NP. If no valid antecedent can be found according to the rules, the parsing process for that branch is blocked, indicating an ill-formed structure.
- Handling of Movement: The proposed rule is designed to account for phenomena like crossover binding (e.g., "Which picture of himself does John like?") without resorting to the complex "reconstruction" mechanism often used in GB theory. This is achieved by considering traces of moved phrases when defining AAS and PAS.
Datasets
Not discussed in the paper. The paper focuses on theoretical linguistic principles and their implementation in a parsing framework, using example sentences for illustration rather than formal datasets.
Key Insights and Ideas
- Procedural Binding is More Efficient: The core insight is that by defining a procedural rule that constructs valid bindings rather than generating and testing them, significant computational efficiency gains can be achieved. This moves from an abstract specification to a practical implementation.
- AAS/PAS as a Unified Mechanism: The introduction of AAS and PAS attributes provides a unified way to represent potential antecedents for both anaphors and pronouns, simplifying the rule's logic.
- Handling Crossover Without Reconstruction: The paper demonstrates that phenomena like crossover binding can be handled by extending the notion of antecedent search to include traces of moved elements, thereby avoiding the need for the problematic "reconstruction" rule.
- Psychological Plausibility: The authors argue that this procedural approach is more psychologically plausible as a model of linguistic performance and parsing than the abstract, generate-and-test model.
Key Results
The paper argues that the proposed procedural Binding rule is:
- Computationally More Sensible: It avoids the exponential complexity of the generate-and-test approach, leading to a parsing algorithm with linear time complexity with respect to the input string length.
- Empirically Adequate: It accounts for phenomena like crossover binding without recourse to reconstruction.
- A Plausible Candidate for Parsers: The efficiency and elegance of the rule make it suitable for incorporation into natural language parsers that handle anaphora.
Limitations and Future Work
- Backward Reference Only: The presented rule is initially limited to cases of backward reference. Assignment of forward coreference (where an antecedent precedes the pronoun/anaphor) is not fully covered by the rule as presented.
- Ignoring Certain Cases: The rule, in its current form, ignores cases where referential expressions (like names) might be used anaphorically.
- Future Work: The authors suggest that the rule could be refined to handle forward coreference and other complex cases. They also note that the exact reformulation of the attribution rules for AAS and PAS could be done in different ways, with one promising approach involving a two-pass computation or delaying anaphora resolution until the end of a movement chain. The potential for optimizing storage use with global storage cells is also mentioned.
Summary updated