Deep Learning for Efficient Discriminative Parsing

Ronan CollobertAISTATS 2011 · OpenReview

Introduction

Natural language parsing has historically been dominated by generative models, such as Probabilistic Context-Free Grammars (PCFGs). While these models are effective, they often require complex "lexicalization" strategies to maintain accuracy. This paper introduces a fast, purely discriminative natural language parser that re-imagines parsing as a recursive sequence tagging task. By leveraging a deep convolutional neural network (CNN) and pre-trained word embeddings, the proposed system achieves performance comparable to state-of-the-art generative benchmarks while operating up to 35 times faster.

The Discriminative Challenge

Discriminative parsers model the boundaries between classes directly, offering a potentially more flexible alternative to generative models. However, they have traditionally faced two major hurdles:

  1. Scalability: Training and testing were often prohibitively slow due to the combinatorial complexity of chart parsing.
  2. Sentence Length: Many early discriminative models were limited to short sentences (e.g., fewer than 15 words) because their computational cost grew exponentially with sentence length.

The author, Ronan Collobert, explores how far discriminative parsing can go using minimal task-specific prior information, relying instead on learned representations and a deep architecture.

The GTN Architecture

The core of the proposed system is a Graph Transformer Network (GTN) architecture. Unlike traditional parsers that rely on thousands of hand-engineered features, this model uses a deep learning pipeline to extract features automatically.

The GTN architecture pipeline, from input sentence to structured inference.

The architecture consists of several key stages:

  • Lookup Table: Words and features (like Part-of-Speech tags) are mapped to dense vector representations (embeddings). These embeddings are often pre-trained on massive unlabeled datasets to capture semantic and syntactic similarities.
  • Convolution: A CNN slides over the sentence to extract local features. To handle long-range dependencies, the model incorporates a global max-pooling layer that creates a "global feature vector" representing the entire sentence.
  • Structured Inference: The final layer ensures that the predicted tags form a valid, consistent structure.

Parsing as Recursive Tagging

The "aha moment" of this research is the decomposition of a complex parse tree into a stack of "levels." Instead of predicting an entire tree in one pass, the model treats parsing as a sequence of tagging tasks.

Decomposition of a parse tree into levels for recursive tagging.

As shown in the figure above, Level 1 identifies the lowest-level "chunks" (e.g., basic noun phrases). Level 2 then identifies the next layer of the hierarchy based on the output of Level 1. This process continues until the root of the tree is reached. To ensure the resulting structure is a valid tree, the model enforces structural constraints: any "chunk" at a higher level must completely encompass any chunks it overlaps at a lower level and must be strictly larger.

Experimental Results

The model was evaluated on the standard Penn Treebank (Wall Street Journal corpus). The results highlight a significant breakthrough in efficiency without a substantial loss in accuracy.

Accuracy

On sentences of 15 words or fewer, the GTN parser achieved an $F_1$ score of 89.1, matching the performance of much more complex discriminative models. On the full Penn Treebank (sentences up to 100 words), the "sentence approach" achieved an $F_1$ of 87.9. While this is slightly lower than the most refined generative parsers of the era (which reached ~90-91), the GTN approach is significantly simpler and more "pure" in its discriminative nature.

Efficiency

Efficiency is the headline result of this work. The GTN parser processed the test set in just 76 seconds. In comparison, the Charniak parser took 1,020 seconds, and the Collins parser took 2,640 seconds. This represents a speedup of roughly 13x to 35x over established benchmarks.

Conclusion and Future Work

By framing parsing as a recursive tagging problem and utilizing deep learning, this paper demonstrates that discriminative parsers can be both accurate and highly efficient. The reliance on pre-trained embeddings and a CNN architecture reduces the need for hand-engineered grammar rules.

Future improvements could involve moving beyond the current "greedy" bottom-up approach by using $K$-best decoding to explore multiple possible tree paths. Additionally, incorporating "head words" (lexicalization) might bridge the remaining accuracy gap between this model and the most advanced generative parsers.

Summary updated

BibTeX
@inproceedings{collobert2011deep,
  author = {Ronan Collobert},
  title = {{Deep Learning for Efficient Discriminative Parsing}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=2S_S8HumN9o},
}
Figure