TL;DR
This paper introduces LFG-DOP, a novel probabilistic model that extends Data-Oriented Parsing (DOP) to Lexical-Functional Grammar (LFG) representations. By integrating LFG's richer, context-sensitive syntactic and functional structures, LFG-DOP offers a more linguistically adequate approach to parsing and provides a corpus-driven notion of grammaticality that favors more specific interpretations.
What Problem Does This Paper Address?
Traditional Data-Oriented Parsing (DOP) models, while effective, have primarily relied on surface phrase-structure trees. This approach is limited because it struggles to capture the full complexity of natural language, particularly phenomena that require deeper syntactic and semantic analysis beyond what a simple tree can represent. Many linguistic theories, like Lexical-Functional Grammar (LFG), propose more articulated representations that include both c-structures (surface syntax) and f-structures (grammatical relations and semantic roles), along with a mapping between them. However, these LFG representations are known to be beyond the capabilities of context-free grammars, making them challenging to integrate into probabilistic parsing models. This paper aims to bridge this gap by developing a DOP model that leverages the richer representational power of LFG.
Methods
The core contribution is the development of the LFG-DOP model, which adapts the Data-Oriented Parsing framework to Lexical-Functional Grammar representations. This involves defining new decomposition and composition operations that respect the correspondence between c-structures and f-structures.
- Representations: The model uses LFG's tripartite representation: c-structure (surface tree), f-structure (attribute-value matrix for grammatical relations), and a correspondence function ($\phi$) mapping c-structure nodes to f-structure units.
- Decomposition Operations:
- Root: Selects a node in a c-structure, erases nodes outside its subtree, removes corresponding $\phi$ links, and prunes f-structure units not accessible from the remaining c-structure.
- Frontier: Similar to Root, but also removes subtrees dominated by selected frontier nodes, while retaining f-structure accessibility.
- Discard: A generalization operation that deletes attribute-value pairs from f-structures, provided their values don't correspond to remaining c-structure nodes. This allows for creating more abstract or generalized fragments.
- Composition Operation: Fragments are combined via left-most substitution of c-structures, followed by recursive unification of their corresponding f-structures.
- Probability Models: The paper proposes three probability models (M1, M2, M3) that differ in how they define competition sets during the stochastic derivation process. These models incorporate category matching and, in M2 and M3, unifiability and coherence conditions, while the Completeness Condition is handled via off-line sampling.
Datasets
The paper mentions experiments with the Penn Treebank and the OVIS corpus for Tree-DOP. For LFG-DOP, it refers to the development of corpora with LFG representations at XRCE France and Xerox PARC, and mentions that experiments with these corpora will be presented later. The paper uses a small, illustrative corpus of two sentences ("Kim eats" and "People ate") to demonstrate the model's properties.
Key Insights and Ideas
- LFG-DOP offers a more linguistically adequate representation: By incorporating f-structures and the $\phi$ mapping, the model can capture deeper syntactic and semantic dependencies that surface trees alone cannot.
- Corpus-driven grammaticality: LFG-DOP defines grammaticality based on the existence of valid derivations using only Root and Frontier fragments (i.e., no Discard fragments). This provides a data-driven way to assess well-formedness.
- Preference for specificity: The probability models inherently favor more specific representations (those with fewer generalized features from Discard) because they tend to have more derivations. This is crucial for interpreting ill-formed input, where specific features (like plural agreement) can accumulate evidence.
- Handling of ill-formed strings: The model can assign probabilities to representations of intuitively ungrammatical strings by using generalized fragments, but the definition of grammaticality correctly excludes derivations relying heavily on these generalizations.
- Left-to-right bias in probability models: Model M2, by considering unifiability at each step, exhibits a left-to-right bias, potentially reflecting psycholinguistic processing.
Key Results
- The paper demonstrates that LFG-DOP can produce valid LFG representations for sentences.
- It shows how different probability models (M1, M2) assign different probabilities to representations, with M2 exhibiting a preference for specific subject number features (SG over PL) due to its left-to-right processing.
- The models consistently assign higher probabilities to more specific representations.
- The paper outlines the computational challenge of finding the most probable representation, noting it's NP-hard even for simpler Tree-DOP.
Limitations and Future Work
- Computational Complexity: Finding the most probable representation is NP-hard, even for Tree-DOP. The paper suggests Monte Carlo sampling or Viterbi n-best derivations as potential solutions.
- Completeness Condition: The Completeness Condition of LFG representations cannot be enforced on-line during the derivation process due to its non-monotonic nature. It must be evaluated off-line during validity sampling.
- Future Work: The authors mention that LFG-DOP implementations are operational or under development, and experiments with newly developed LFG corpora are planned. Further exploration of different combinations of well-formedness conditions in probability models is also suggested.
Summary updated