Recurrent Greedy Parsing with Neural Networks

Joël Legrand, Ronan CollobertECML/PKDD 2014 · DOI

TL;DR

This paper introduces a novel, purely discriminative neural network approach for syntactic parsing that achieves competitive accuracy with significantly faster inference speeds compared to existing methods. By leveraging continuous word embeddings and a greedy, bottom-up parsing strategy, the model effectively learns syntactic rules with a simplified feature set.

What Problem Does This Paper Address?

Syntactic parsing, the task of analyzing the grammatical structure of sentences, has traditionally been dominated by generative approaches like Probabilistic Context-Free Grammars (PCFGs). While effective, PCFGs face a dilemma: rules need to be specific enough to avoid ambiguity but not so specific that they appear too rarely in training data, leading to generalization issues. Discriminative methods have shown promise in NLP, but early attempts at discriminative parsing, while using rich features, often lagged behind the best generative parsers. More recent discriminative approaches have either relied on re-ranking external parsers or used complex feature sets. This paper aims to bridge this gap by proposing a simple, purely discriminative parser that is both accurate and fast, without relying on generative models or complex feature engineering.

Methods

The core of the proposed approach is a recurrent greedy parsing algorithm that builds the parse tree bottom-up. At each iteration, a neural network classifier is used to predict new tree nodes by considering a context of previously identified nodes (ancestors). This classifier is trained using an objective function similar to that of a Conditional Random Field (CRF), modeling the conditional distributions of context-aware syntactic rules.

Key methodological aspects include:

  • Continuous Word Vector Representations: Instead of discrete features, the parser uses continuous word embeddings (initialized with pre-trained embeddings from [27]) to represent words and headwords. This allows for natural generalization, as semantically similar words will have similar vector representations.
  • Greedy, Bottom-Up Approach: The parser iteratively constructs the tree by identifying and adding new nodes based on the current context. This contrasts with chart-based parsers that explore a larger search space.
  • BIOES Tagging Scheme: The neural network outputs scores for a BIOES (Begin, Intermediate, Other, End, Single) tagging scheme for each ancestor. These tags are then aggregated using a dynamic programming approach (similar to a CRF) to form new tree nodes.
  • Simplified Feature Set: The model relies on a limited set of features: words (or headwords for non-terminals), POS tags (for terminals), and parsing tags of ancestors (for non-terminals).

Datasets

The experiments were conducted using the standard English Penn Treebank dataset.

  • Sections 02-21 were used for training.
  • Section 22 was used for validation (hyper-parameter tuning).
  • Section 23 was used for testing.

The paper also mentions the use of pre-trained word embeddings obtained from [27], which were trained on large unlabeled corpora.

Key Insights and Ideas

  • Simplicity Can Be Powerful: The paper demonstrates that a surprisingly simple neural network architecture with a limited feature set can achieve competitive parsing performance. This challenges the notion that complex feature engineering is always necessary for state-of-the-art results.
  • Continuous Representations Enable Generalization: The use of continuous word embeddings is crucial for generalization. It allows the model to infer relationships between unseen words based on their semantic similarity, enabling it to handle rules with words not seen in the training data.
  • Greedy Parsing Can Be Fast and Accurate: By adopting a greedy, iterative approach, the parser achieves significantly faster inference times than traditional chart-based parsers, while still maintaining high accuracy. This is a key trade-off that the paper successfully navigates.
  • CRF-like Aggregation is Essential: While the neural network predicts BIOES tags, the paper emphasizes that a CRF-like aggregation step is essential for producing a consistent and coherent parse tree by combining these tags.

Key Results

  • The proposed model achieved an F1 score of 88.3 when using word embeddings, headwords, and POS tags.
  • This performance is competitive with state-of-the-art generative parsers and is among the best purely discriminative parsers.
  • The parser is significantly faster than generative parsers, with a reported time of 110 seconds to parse the full WSJ test corpus, compared to over 1200 seconds for some generative models.
  • A voting procedure using 10 models achieved an F1 score of 89.6, further improving performance.
  • The paper also shows that the model can predict all the rules of a sentence without explicit grammar rules, demonstrating its ability to learn syntactic structures directly.

Limitations and Future Work

  • Greedy Nature: While beneficial for speed, the greedy nature of the parsing process means that local decisions might not always lead to the globally optimal parse tree.
  • Head-word Procedure: The authors suggest revisiting Collins' head-word procedure, potentially by learning higher-level chunk representations, as a direction for improvement.
  • Re-ranking Approaches: Investigating re-ranking approaches, similar to some existing methods, is mentioned as a potential avenue for further enhancing accuracy.
  • Unlabeled Corpora: The use of unlabeled corpora for pre-training word embeddings is highlighted, and further exploration of their use in the parsing model is suggested.

Summary updated

BibTeX
@inproceedings{legrand2014recurrent,
  author = {Joël Legrand and Ronan Collobert},
  title = {{Recurrent Greedy Parsing with Neural Networks}},
  booktitle = {ECML/PKDD},
  year = {2014},
  doi = {10.1007/978-3-662-44851-9\_9},
}
Figure