The Reading Machine: A Versatile Framework for Studying Incremental Parsing Strategies

Franck Dary, Alexis NasrACL 2021

TL;DR

This paper introduces the "Reading Machine" (RM), a flexible framework for studying incremental natural language parsing. The RM allows researchers to build and compare various parsing configurations, including those that model top-down dependencies and human-like incremental processing, offering a novel way to investigate how different NLP modules interact and how humans process language.

What Problem Does This Paper Address?

Traditional Natural Language Processing (NLP) pipelines process text sequentially, with each module (like tokenization, POS tagging, parsing) operating on the output of the previous one. While this modularity is convenient, it can be suboptimal. For instance, decisions made early in the pipeline (e.g., tokenization) might benefit from information available later (e.g., syntactic structure). This "top-down dependency" is difficult to capture in a strict pipeline. Furthermore, human language processing is known to be incremental – we don't wait for an entire sentence to be processed before understanding begins. This paper addresses these limitations by proposing a framework that allows for more flexible, incremental, and potentially non-sequential processing of NLP tasks, enabling the study of these complex interactions and the development of more cognitively plausible NLP models.

Methods

The core of the Reading Machine (RM) is an extension of the Transition-Based Parsing (TBP) algorithm, specifically the "Arc Eager" strategy. The RM integrates six standard NLP tasks: tokenization, POS tagging, morphological analysis, lemmatization, dependency parsing, and sentence segmentation.

Key methodological innovations include:

  • Unified Framework: RM treats all six tasks as actions within a single state machine, allowing for joint prediction and flexible ordering.
  • Enriched Configurations and Actions: The framework extends the standard TBP configuration (stack, buffer) to include multiple output tapes for different linguistic predictions and defines a richer set of actions to handle all six tasks.
  • Flexible Strategies: RM allows for defining different "strategies" that dictate the order in which tasks are performed. This includes:
  • INCR (Incremental): Processes a word at a higher level before moving to the next word at a lower level.
  • SEQ (Sequential): Processes all tasks for a given word before moving to the next word.
  • Feature Spans: Classifiers can be configured with different "feature spans" (PA-HI, PA-LO, FU-LO) to control what information from previous predictions is accessible, enabling the explicit modeling of top-down dependencies.
  • Number of Classifiers: The framework allows for either a single classifier for all tasks (multi-task learning) or separate classifiers for each task (mono-task learning), enabling the study of their respective benefits.
  • Window Span: The input text is accessed via a sliding window, and the size of this window (e.g., [-5,10] characters) can be varied to study the impact of local context.

Datasets

The experiments were conducted on French data using the GSD corpora of the Universal Dependencies collection (version 2.7). The authors note that the standard test split was too small for meaningful comparison, so they employed a 10-fold cross-validation approach, resulting in a combined test set of 427,763 words.

Key Insights and Ideas

  • Top-Down Dependencies are Tricky: Counter-intuitively, the experiment comparing "PA-HI" (access to past high-level predictions) and "PA-LO" (no access to past high-level predictions) found that PA-HI performed worse. This suggests that simply providing more information from higher levels doesn't automatically improve lower-level tasks and might even introduce errors.
  • Multi-Task Learning Shows Promise: The comparison between a single multi-task classifier (C1) and separate mono-task classifiers (C6) indicated that the multi-task approach generally yielded better overall performance (MLAS) and was particularly beneficial for parsing, morphological, and POS tagging. This suggests that optimizing for all tasks simultaneously can lead to better representations.
  • Incremental vs. Sequential: The sequential (SEQ) machine, which mimics a pipeline with a look-ahead, outperformed the incremental (INCR) machine on parsing tasks (LAS, UAS). However, low-level tasks showed similar performance across both strategies, indicating that the benefits of sequential processing are primarily for higher-level tasks like parsing.
  • Window Span Matters, but Diminishing Returns: The window span significantly impacts performance, with [-5,10] (10 characters look-ahead) showing the best results. However, increasing the window span further (to [-5,15]) yielded diminishing returns, aligning with human reading span research.

Key Results

  • MLAS Scores: The best overall MLAS score achieved was 78.60% by the SEQ machine.
  • Feature Span Impact: PA-HI achieved MLAS of 77.30%, while PA-LO achieved 77.70%, with a p-value of 0.014, suggesting PA-LO was slightly better.
  • Multi-Task vs. Mono-Task: C1 (multi-task) achieved an MLAS of 77.93%, while C6 (mono-task) achieved 77.29% (p-value 0.001). C1 was significantly better for parsing, morphological, and POS tagging.
  • Sequential vs. Incremental: SEQ achieved an MLAS of 78.60%, while INCR achieved 77.93% (p-value 0.000). SEQ improved LAS and UAS by around one point.
  • Window Span: The [-5,10] window span achieved the highest MLAS (77.29%), outperforming smaller spans like [-5,2] (48.53%) and larger spans like [-5,15] (77.19%).

Limitations and Future Work

  • Explaining PA-HI Performance: The authors acknowledge the surprising result that PA-HI performed worse than PA-LO and suggest that errors in earlier predictions might propagate and negatively impact current predictions. Further investigation using probing and specialized test sets is planned.
  • Multi-Task Learning Nuances: While multi-task learning showed benefits, the authors caution that it's a complex process and more investigation is needed to definitively attribute the gains to modeling top-down dependencies.
  • Greedy Nature of Current Machines: The current RM machines are greedy, meaning they don't backtrack. The authors plan to introduce a backtracking mechanism to allow for re-analysis of previously processed parts of the text.
  • Learning Strategies: The current RM strategies are fixed. Future work will explore allowing the RM to learn optimal task ordering strategies.
  • Cognitive Plausibility: The RM has been used to predict reading times, and future work will extend this to predicting saccades and comparing against human experimental data more broadly.
  • Language Independence: While experiments were on French, the authors note that replicating these on other languages is a valuable but resource-intensive future direction.

Summary updated

BibTeX
@inproceedings{dary2021reading,
  author = {Franck Dary and Alexis Nasr},
  title = {{The Reading Machine: A Versatile Framework for Studying Incremental Parsing Strategies}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure