Template Kernels for Dependency Parsing

Hillel Taub-Tabib, Yoav Goldberg, Amir Globerson

TL;DR

This paper introduces a novel "template kernel" that efficiently learns parameters for dependency parsing features, overcoming the computational and statistical limitations of manually crafted templates. By integrating this kernel into a reranking system, they achieve state-of-the-art results on several languages, demonstrating a more scalable way to explore complex feature interactions.

What Problem Does This Paper Address?

Dependency parsing aims to build a syntactic tree representing grammatical relationships between words in a sentence. A common approach is to score potential parse trees using a linear function of features extracted from the tree. These features are typically generated by applying "templates" to different parts of the parse tree (like arcs, siblings, or grandparents). Manually designing these templates is labor-intensive and, more importantly, exploring all possible combinations of word properties within these templates quickly becomes computationally infeasible and statistically prone to overfitting. Existing methods either explore only a small subset of these combinations or use complex machinery like tensors or neural networks. This paper addresses the challenge of efficiently learning from a much richer set of feature combinations without the prohibitive computational cost.

Methods

The core contribution is a template kernel. Instead of explicitly defining and computing features for every possible combination of word properties within a template, this kernel allows us to compute the dot product between feature representations implicitly. The kernel operates on "parts" of the parse tree (e.g., an arc between a head and a modifier). It defines a similarity measure between two parts based on whether their corresponding properties match. By summing these pairwise similarities over all parts in two parse trees, the kernel effectively computes the dot product of their full feature representations, even if those representations are astronomically large. This kernel is then integrated into a passive-aggressive reranking algorithm. The reranker uses a linear model that combines manually constructed features with features implicitly learned by the kernel. The kernel's ability to handle a vast number of feature combinations without explicit instantiation is key to its effectiveness.

Datasets

The authors evaluated their system on four languages from the CoNLL 2006 shared task: Arabic, Slovene, Danish, and Bulgarian. These datasets are noted for their rich morphological features. For training the reranker, they used k-best lists generated by a base parser, created using a 20-fold jackknifing approach.

Key Insights and Ideas

  • Kernel Trick for Feature Explosion: The paper masterfully applies the kernel trick to a problem plagued by combinatorial explosion. Instead of building massive feature vectors, they compute similarity directly, making it computationally tractable to consider a much larger feature space.
  • Bridging Manual and Automatic Features: The approach elegantly combines the strengths of manually crafted features (often interpretable and effective) with the power of automatically discovered feature interactions via the kernel.
  • Reranking as a Practical Application: Demonstrating the kernel's utility within a reranking framework shows its immediate applicability to improving existing parsing systems without needing to overhaul the entire parsing pipeline.
  • Focus on Property Combinations: Unlike some tree kernels that focus on shared subtrees, this kernel specifically targets the combination of properties within defined "slots" of a template, which is directly relevant to feature engineering in parsing.

Key Results

The proposed kernel reranker significantly improves upon a baseline reranker that uses only manually constructed features. In Bulgarian and Danish, the kernel reranker even outperforms the base parser. The final system, which combines base parser scores with reranker scores, achieves state-of-the-art results, slightly trailing a sampling parser that uses additional global features and a tensor component. Training times are reported as reasonable, though prediction time can become slow for large datasets due to the growth of the "support set" (parts that contribute to the learned parameters).

Limitations and Future Work

The authors acknowledge that prediction can become slow for large datasets due to the size of the support set. They suggest that future work could explore techniques like feature maps or bounded online algorithms to address this. They also propose extending the kernel to higher-order parts and integrating it directly into a graph-based dependency parser, rather than solely using it in a reranking setup.

Summary updated

Abstract

A common approach to dependency parsing is scoring a parse via a linear function of a set of indicator features. These features are typically manually constructed from templates that are applied to parts of the parse tree. The templates define which properties of a part should combine to create features. Existing approaches consider only a small subset of the possible combinations, due to statistical and computational efficiency considerations. In this work we present a novel kernel which facilitates efficient parsing with feature representations corresponding to a much larger set of combinations. We integrate the kernel into a parse reranking system and demonstrate its effectiveness on four languages from the CoNLL-X shared task. 1
BibTeX
@inproceedings{taubtabib2015template,
  author = {Hillel Taub-Tabib and Yoav Goldberg and Amir Globerson},
  title = {{Template Kernels for Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.3115/v1/n15-1163},
}
Figure