A non-DNN Feature Engineering Approach to Dependency Parsing - FBAML at CoNLL 2017 Shared Task

Xian Qian, Yang Liu

Abstract

In the CoNLL 2017 Shared Task on Universal Dependency (UD) parsing, the FBAML team demonstrated that a traditional pipeline of structured linear classifiers and Conditional Random Fields (CRFs) remains competitive against modern deep neural network (DNN) approaches. By leveraging extensive manual feature engineering, k-means clustering for word embedding discretization, and efficient "Hogwild!" training, the system achieved a 15th-place finish out of 33 teams. This work highlights the effectiveness of sparse features and domain expertise in multilingual NLP tasks, providing a robust alternative to end-to-end neural architectures.

Introduction

The challenge of Universal Dependency (UD) parsing involves transforming raw text into a structured tree where nodes represent words and edges represent grammatical relationships. While the prevailing trend in NLP has shifted toward end-to-end deep learning models that learn dense feature representations automatically, the FBAML system explores the efficacy of a classical pipeline. This approach relies on a modular series of structured linear classifiers and millions of sparse features to handle the linguistic diversity of over 40 languages, including "surprise" languages with minimal training data.

System Architecture

The authors developed a modular pipeline from scratch in C++, intentionally avoiding third-party toolkits to maintain control over the feature space. The process flows through several distinct stages, from initial segmentation to final relation classification.

The modular pipeline architecture for dependency parsing from raw text to labeled output.
  1. Sentence Segmentation & Tokenization: Character-level linear classifiers and CRFs were employed. A three-label scheme (N, E, O) was implemented to mitigate the data imbalance between sentence-ending characters and other text.
  2. Morphological Analysis & POS Tagging: These tasks were treated as sequence labeling problems using linear chain CRFs.
  3. Unlabeled Parsing: A second-order graph-based parser determined the tree structure. The system utilized a pseudo-projective parser for standard treebanks and a "1-endpoint-crossing" parser for languages with complex non-projective structures.
  4. Relation Classification: Finally, a linear tree CRF assigned grammatical labels to the established edges.

Feature Engineering and Discretization

The core strength of the FBAML system lies in its extensive feature engineering. The authors found that character-type features alone improved sentence segmentation by an absolute F1 score of 13%.

Examples of character and word-level features used in the linear classifiers to capture linguistic context.

To bridge the gap between linear classifiers and continuous word embeddings, the team utilized a discretization trick. By applying k-means clustering (with $k$ values of 2048 and 10,000) to official word embeddings, they converted dense vectors into discrete cluster IDs. These IDs served as features that allowed the model to recognize semantic similarities—such as the relationship between "cat" and "kitten"—without requiring a neural architecture. This technique provided a 0.15% boost in POS tagging accuracy.

Results and Discussion

The system achieved an official averaged macro F1 score of 67.87%, placing 15th out of 33 participants. On the English development set, the system reached 94.78% UPOS accuracy and an Unlabeled Attachment Score (UAS) of 81.63%.

Training efficiency was a priority; the authors utilized the "Hogwild!" strategy for asynchronous stochastic gradient descent across 30 threads. This enabled the English model to be trained in just 2.5 hours—a 5x speedup over serial training—with only a negligible 0.1% loss in accuracy. However, the pipeline approach showed sensitivity to early-stage errors; for instance, a model selection error for Norwegian Nynorsk significantly impacted overall performance, illustrating the "brittleness" inherent in sequential processing compared to end-to-end models.

Conclusion

The FBAML entry proves that "classical" NLP techniques remain highly relevant. While deep learning automates feature discovery, manual feature engineering combined with clever discretization of embeddings can still produce competitive results. Future work may involve hybridizing these structured linear classifiers with neural feature learning to combine the interpretability of sparse features with the representational power of DNNs.

Summary updated

BibTeX
@inproceedings{qian2017non,
  author = {Xian Qian and Yang Liu},
  title = {{A non-DNN Feature Engineering Approach to Dependency Parsing - FBAML at CoNLL 2017 Shared Task}},
  booktitle = {CoNLL Shared Task},
  year = {2017},
  doi = {10.18653/v1/k17-3015},
}
Figure