Shift-Reduce CCG Parsing using Neural Network Models

Bharat Ram Ambati, Tejaswini Deoskar, Mark SteedmanNAACL 2016

TL;DR

This paper introduces the first neural network-based shift-reduce parser for Combinatory Categorial Grammar (CCG), achieving state-of-the-art results for greedy parsing and competitive performance with beam search. By leveraging neural networks for both tagging and parsing, they demonstrate significant speedups over traditional methods while maintaining or improving accuracy.

What Problem Does This Paper Address?

Parsing, the process of analyzing a sentence's grammatical structure, is crucial for many natural language processing (NLP) tasks. Combinatory Categorial Grammar (CCG) is a powerful formalism that excels at capturing complex grammatical phenomena like unbounded dependencies, making it valuable for tasks requiring deep linguistic understanding. However, traditional CCG parsers, especially those that aim for speed in real-world applications (like parsing the web), often sacrifice accuracy. Shift-reduce parsers offer linear time parsing, but greedy versions are less accurate than graph-based parsers, while beam-search versions are slower. This paper aims to bridge this gap by developing a neural network-based shift-reduce CCG parser that is both fast and accurate, addressing the trade-off between speed and performance in CCG parsing.

Methods

The authors propose a neural network-based shift-reduce CCG parser (NNPar) built upon the architecture of Chen and Manning (2014) for dependency parsing. Key methodological contributions include:

  • Neural Network Architecture: A standard feed-forward neural network with an input layer, a hidden layer (200 units), and an output layer using softmax.
  • Feature Representation: Discrete features (words, POS-tags, CCG supertags) are converted into continuous vector embeddings. The features considered include words, POS-tags, and CCG supertags from the top nodes of the stack, the next nodes in the input buffer, and children of the top stack nodes.
  • Structured Neural Network (Structured NNPar): To incorporate beam search effectively, they adapt a structured perceptron training approach (inspired by Weiss et al., 2015). This method pre-trains the neural network and then trains a structured perceptron on top of its hidden and output layers, allowing for beam search decoding during training.
  • Greedy vs. Beam Search: They compare the performance of their greedy parser (beam size 1) with a beam-search version.
  • Neural Network Taggers: The impact of using neural network-based POS and CCG supertaggers is investigated compared to maximum entropy taggers.

Datasets

The experiments were conducted on the CCGbank dataset, a widely used corpus for CCG parsing. The standard splits were used:

  • Development Data: Section 00
  • Test Data: Section 23

Key Insights and Ideas

  • Neural Networks for Speed and Accuracy: The core idea is that neural networks can provide a better trade-off between parsing speed and accuracy for shift-reduce CCG parsers, overcoming limitations of traditional methods.
  • Impact of Neural Network Taggers: Using neural network-based taggers (NNT) significantly improved the performance of their NNPar, whereas it had a less pronounced effect on the perceptron-based parser. This suggests that the benefits of neural tagging are more pronounced when integrated with a neural parsing model.
  • Structured Training for Beam Search: The structured neural network approach proved crucial for effectively leveraging beam search, leading to substantial accuracy gains over the greedy NNPar.
  • Greedy Parsing Achieves State-of-the-Art: Their greedy NNPar achieved the best reported results for greedy shift-reduce CCG parsing at the time, demonstrating that neural networks can push the boundaries even in simpler parsing paradigms.

Key Results

  • Greedy Parsing:
    • NNPar achieved an unlabeled F-score of 89.78% and a labeled F-score of 83.27% on the development data, outperforming a perceptron-based parser (Z&C*) by approximately 2.5% in both metrics.
  • NNPar was over three times faster than Z&C, parsing 350 sentences per second compared to Z&C's 110 sentences per second.
  • Beam Search Parsing:
    • The Structured NNPar achieved a labeled F-score of 85.57% on the development data, outperforming the structured perceptron counterpart (Z&C*) by 1.3%.
  • While beam search improved accuracy, it significantly slowed down parsing speed, with a beam size of 16 parsing around 10 sentences per second.
  • Overall: The paper presents the first neural network-based shift-reduce CCG parsers, setting new benchmarks for greedy parsing and offering a strong contender for beam-search CCG parsing.

Limitations and Future Work

  • Beam Size Trade-off: While increasing the beam size improved accuracy, it drastically reduced parsing speed. The authors note that a beam size of 128 gave a small improvement but slowed the parser by ten times.
  • Comparison to Other Parsers: While their Structured NNPar achieved competitive results, it had slightly lower category accuracy than Xu et al. (2014), though this was with a significantly smaller beam size.
  • Future Directions: The authors plan to explore more sophisticated neural network architectures, including deep neural networks, recurrent neural networks (RNNs), and bi-directional LSTMs, for shift-reduce CCG parsing.

Summary updated

BibTeX
@inproceedings{ambati2016shift,
  author = {Bharat Ram Ambati and Tejaswini Deoskar and Mark Steedman},
  title = {{Shift-Reduce CCG Parsing using Neural Network Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2016},
}
Figure