Abstract
Dependency parsing often fails to respect linguistic constraints regarding the number and type of arguments a word can take, a property known as valency. This paper introduces a valency-augmented parsing framework that models these constraints as supertags and incorporates them into a joint decoding process using A* search. By forcing the parser to respect subcategorization frames, the authors achieve substantial improvements in core grammatical relation precision across 41 languages and establish a new state-of-the-art for Tree Adjoining Grammar (TAG) parsing.
Introduction
In dependency parsing, the goal is to map the syntactic structure of a sentence by identifying links between "head" words and their "dependents." Most modern parsers treat the decision of where to link a word and what label to assign as independent tasks. However, this ignores the fundamental linguistic constraint of valency. For example, a verb like "give" typically expects exactly one subject, one direct object, and one indirect object.
Standard parsers frequently "hallucinate" structures, such as assigning multiple subjects to a single verb, because they lack a mechanism to track a word's "budget" of dependents. This paper addresses this gap by forcing the parser to respect linguistically plausible subcategorization frames through a valency-augmented decoding process.
Methodology
The proposed approach consists of three main components:
- Valency Patterns as Supertags: A valency pattern is defined as an ordered sequence of syntactic relations (e.g.,
nsubj$\diamond$obj). To prevent data sparsity, these patterns are "relativized" to specific subsets of relations, such as "Core" arguments or "Functional" relations. - Probabilistic Supertagging: A Bi-LSTM feature extractor followed by a Multi-Layer Perceptron (MLP) assigns probabilities to potential valency patterns for every token in a sentence.
- Joint Decoding with A* Search: The authors adapt Eisner’s algorithm to include valency states. To manage the resulting search space explosion, an A* search algorithm is implemented using an "optimistic" heuristic to find the highest-scoring globally consistent tree that satisfies predicted valency constraints.
The model is trained using a multi-task learning (MTL) objective, jointly optimizing for head selection, relation labeling, and valency pattern prediction.
Evaluation and Results
The model was evaluated on the Universal Dependencies (UD) v2.0 dataset, covering 53 treebanks across 41 languages, and the Penn Treebank (PTB) converted into Tree Adjoining Grammar (TAG) derivation trees.
Key Findings
- Core Argument Precision: On the UD dataset, precision for core arguments (subjects and complements) improved significantly, rising from 80.87 to 85.43.
- State-of-the-Art Performance: On the TAG parsing task, the model achieved a Labeled Attachment Score (LAS) of 92.59, outperforming the previous state-of-the-art by 0.7 points.
- Broad Language Support: The improvements were consistent across a wide variety of languages, as shown in the cross-lingual evaluation.
Discussion
A pilot study revealed that state-of-the-art parsers frequently invent valency patterns that never appear in human-annotated data. By treating valency as a global constraint during decoding, the parser is forced to make globally consistent decisions. If a verb predicts an object in its valency frame, the parser is more likely to identify one, even if local evidence is weak.
Despite the complexity of language, valency patterns are highly learnable; only about 10% of patterns in the test sets were unseen during training. However, the current decoder is limited to projective dependency trees, which may impact performance on languages with free word order. Future work will explore extending this framework to non-projective parsing and Semantic Role Labeling (SRL).
Summary updated