TL;DR
This paper explores three variations of the Covington algorithm for non-projective dependency parsing, evaluating their performance across ten languages. The authors find that while the algorithm's flavor matters, a purely grammar-based feature model relying solely on the partially built dependency graph limits overall performance, suggesting the need for richer feature sets and potentially different approaches for different language typologies.
What Problem Does This Paper Address?
Dependency parsing aims to uncover the grammatical relationships between words in a sentence, representing them as a directed graph. A key challenge is handling "non-projective" dependencies, where arcs in the dependency graph can cross. Traditional parsers often struggle with this, and many algorithms implicitly or explicitly enforce projectivity. This paper investigates Covington's algorithm, a method designed for non-projective parsing that operates incrementally, building the dependency graph word by word. The authors specifically examine how different "flavors" of this algorithm, which enforce a single head for each word but don't guarantee projectivity, perform on a diverse set of languages from the CoNLL-X Shared Task. They also explore the impact of a restricted, "pure grammar-based" feature model that only uses information from the currently constructed dependency graph.
Methods
The core of the paper revolves around three variations of Covington's algorithm: Exhaustive Search Head First with Uniqueness (ESHU), Exhaustive Search Dependents First with Uniqueness (ESDU), and List-based search with Uniqueness (LSU). These algorithms process words sequentially and attempt to link them based on a HEAD? function, which checks grammatical compatibility according to a grammar G. The LINK procedure then establishes the dependency.
To implement the HEAD? function, the authors use TiMBL, a memory-based learner, acting as a classifier. During training, the parser has access to a fully parsed dependency graph to create feature vectors. In parsing mode, the HEAD? function calls the classifier with features derived from the partially built dependency graph (PG). The feature model used is described as "pure grammar-based," meaning it relies only on information from the graph, such as the head and daughters of words, and not on preceding or following words outside the current graph structure. This approach is motivated by an approximation of Data Oriented Parsing (DOP).
Datasets
The experiments were conducted on the ten languages provided for the CoNLL-X Shared Task. The paper does not introduce new datasets but utilizes existing treebanks for these languages.
Key Insights and Ideas
- Algorithm Flavor Matters: The choice between ESHU, ESDU, and LSU can lead to different performance levels, even when using the same feature model and classifier.
- Language Typology and Algorithm Preference: SOV (Subject-Object-Verb) languages like Hungarian, Basque, and Turkish showed a preference for dependent-first algorithms (ESDU and LSU), while SVO (Subject-Verb-Object) languages generally favored ESHU, with some exceptions like Italian.
- The "Pure Grammar-Based" Model is Restrictive: Relying solely on the partially built dependency graph for features significantly limits the parser's performance. This "pure incremental processing" approach, while conceptually simple, misses crucial contextual information.
- DOP Approximation Limitations: The attempt to approximate a Data Oriented Parsing (DOP) model by dynamically building tree fragments from the graph proved insufficient for achieving high performance due to the limited feature set.
- "NO" Class Dominance: The classification task is heavily skewed, with a large number of instances belonging to the "NO" class (no link possible), which likely impacts recall.
Key Results
The paper presents detailed results in Table 1, showing Labelled Attachment Score (LA) and Unlabelled Attachment Score (UA) for each language and algorithm variation. For example, for Catalan, ESHU achieved an LA of 69.56, ESDU 69.80, and LSU 69.42. The highest scores were generally achieved by the enhanced models (using more features) on languages like Catalan and Hungarian. The authors note that the optimized version of Covington's algorithm (from Nivre, 2007) was faster but showed a decrease in accuracy when using the same feature vector as the other algorithms.
Limitations and Future Work
The authors acknowledge several limitations:
- Restricted Feature Model: The primary limitation is the "pure grammar-based" feature model, which excludes information about words outside the current graph.
- Incremental Processing Pitfalls: The inherent limitations of incremental processing are cited as a contributing factor to poor performance.
- Classifier Choice: While TiMBL was used, the paper suggests that exploring other classifiers, like Support Vector Machines (SVMs), might yield different results (though SVM training was too time-consuming to include fully).
- Treebank Annotation: The possibility that treebank annotation differences might influence performance is raised.
Future work could involve:
- Richer Feature Models: Investigating parsers with more comprehensive feature sets.
- Different Classifiers: Further evaluation of alternative classifiers.
- Language-Specific Approaches: Determining if different algorithm flavors or feature models are indeed necessary for parsing different language typologies.
- Optimized Covington: Further exploration of optimized Covington algorithms.
Summary updated