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

Abstract: The Reading Machine, is a parsing framework that takes as input raw text and performs six standard nlp tasks: tokenization, pos tagging, morphological analysis, lemmatization, dependency parsing and sentence segmentation. It is built upon Transition Based Parsing, and allows to implement a large number of parsing configurations, among which a fully incremental one. Three case studies are presented to highlight the versatility of the framework. The first one explores whether an incremental parser is able to take into account top-down dependencies (i.e. the influence of high level decisions on low level ones), the second compares the performances of an incremental and a pipe-line architecture and the third quantifies the impact of the right context on the predictions made by an incremental parser.

## introduction syntactic parsers usually take as input text that has been processed at several levels. it has generally been segmented in sentences, tokenized, pos tagged, and possibly lemmatized and morphologically analyzed. all such steps are realized by other nlp modules that are usually organized in a sequential pattern, called a pipe-line. the pipe-line imposes a rational order on the modules: word boundaries, for example, have to be determined before a word can be associated to a pos tag and syntactic parsing usually comes after pos tagging, for pos tags group words that have close syntactic properties. the pipe-line architecture offers many advantages, among which, the independence of the modules that compose it. the only constraint for their inter-operability is the compatibility of their inputs and outputs. once this constraint is verified, each module can be built on any kind of model considered more suitable for the task to perform. besides, in a pipe-line architecture, every module narrows down the search space of the following modules: a parser, for example, does not have to consider different tokenization hypotheses nor different pos tags for a word. considering all such decisions can lead to a combinatorial explosion problem and yields huge search spaces. the pipe-line architecture nevertheless has its limits. it is well known that some low level decisions (made by early modules of the pipe-line) can benefit from high level ones (made by late modules). some tokenization decisions, for example, can depend on the syntactic structure of the sentence to parse, such as complex prepositions in french, as noted by @xcite . likewise, sentence segmentation can depend on syntactic structures, especially when punctuation is absent or unreliable, such as in speech transcriptions. such top down dependencies cannot be taken into account in a strict pipe-line architecture. but they are arguably less numerous than bottom up dependencies and this is the reason why the pipeline architecture usually yields good results. one aim of this paper is to propose a framework, called the reading machine (rm), that is flexible enough to define several patterns for combining different nlp modules and explore different ways to link decisions made by these modules. we use in this paper the rm framework to define and compare several non sequential machines that model top down dependencies. there is another, less immediate, reason for studying non sequential architectures, in link with human cognition. psycholinguistic studies have shown that human language processing is incremental, i.e., people do not wait to see the entire sentence before they start trying to understand it (see @xcite for more details). such findings have developed interest in using nlp tools to implement cognitively-plausible models of hu-man sentence processing (see @xcite for a review). various "linking hypotheses" have been proposed to relate the models' intermediate states when parsing a given sentence to the behavior of human subjects trying to understand that same sentence. the rm offers a framework to investigate such linking hypotheses by defining machines that implement them and observe their behaviour on human data. in this perspective, the rm has already been used for predicting eye-movements during reading: different rm architectures have been compared on their ability to accurately predict fixation time @xcite . in order to illustrate the kind of experiments that can be conducted in such a perspective, we will define and compare machines that model different perceptual fields and measure their influence on an incremental parsing process. technically, rm is an extension of the transitionbased parsing algorithm (tbp) @xcite . the reason for this choice is mainly that tbp implements an incremental parsing strategy @xcite . we propose to extend this model to define a complete incremental nlp parser that integrates six tasks: tokenization, pos tagging, morphological analysis, lemmatization, syntactic parsing and sentence segmentation. rm borrows from tbp the two key notions of configurations and actions (also called transitions), as well as a greedy algorithm that performs syntactic parsing. we extend these notions by defining an enriched version of a configuration and a richer set of actions. all linguistic decisions, such as word and sentence boundaries detection, pos tagging, lemmatization and, of course, syntactic parsing are realized by actions that are predicted based on configurations. the rm takes as input raw text and greedily predicts a sequence of actions that perform the six tasks mentioned above. ## related work solving the circular dependencies that exist between parsing and other pre-processing steps, is an active area of research in the parsing literature. the solution that has been mainly investigated consists in jointly performing syntactic parsing and other pre-parsing steps. if we restrict ourselves to recent approaches to dependency parsing, solutions have been proposed both for graph-based parsing @xcite @xcite @xcite and transition-based pars-ing @xcite @xcite @xcite @xcite . solutions to this problem differ vastly for these two approaches, mainly because of the different parsing strategies they adopt. this is why we have decided to restrict ourselves to tbp based papers in the remainder of this section. there have been many propositions to realize simultaneously several linguistic tasks in tbp. both @xcite and @xcite , for example, show how a transition system can be extended and trained to jointly predict pos tags and the dependency tree, improving both the accuracy of tagging and parsing. these systems are not strictly incremental across the tasks they realize for they process text that has already been segmented in words and sentences. besides, the text has been pre-tagged in order to limit the size of the search space. the closest approach to ours is @xcite , which is based on the work of @xcite . the authors propose an extension of the arc-standard transition system that is able to perform a fully joint prediction of word segmentation, pos tagging and dependency parsing. their system takes a queue of symbols as input, and process it in an incremental fashion, consuming one symbol at a time. they conducted their experiments on chinese, and were the first to use a neural network architecture using both word and character based embeddings to achieve fully joint prediction of these three tasks. they showed that their joint architecture was competitive with a pipeline architecture for word segmentation and pos tagging, but fell short on parsing. for their participation in the 2018 conll shared task ( zeman et al., 2018), wan et al. (2018) also defined an extension of tbp that is close to ours. it is based on the arc-standard system enriched with a swap transition @xcite , and is able to jointly perform word segmentation, pos tagging, morphological tagging and dependency parsing. they showed that such a system could get better scores than the shared task's baseline, while still being quite far from the top scoring systems. their paper focuses on low or even zero resources languages (what the shared task was mainly about), and did not test whether or not the joint prediction of multiple tasks was improving the performances. our model has the following characteristics that distinguishes it form the approaches cited above. the rm performs simultaneously six nlp tasks with the notable inclusion of sentence segmentation which is almost always pre-processed in parsing systems. the rm allows us to build a machine that is strictly incremental across the six tasks it realizes. there are two reasons for this choice. the first is theoretical, we are interested to know how much information is present in top-down dependencies and whether they can be captured in an incremental setup. the second is related to psycholinguistics: we believe that the definition of a fully incremental rm offers a useful model for simulating human behaviour during reading. the rm is flexible enough to design machines that implement different strategies in order to compare them. we propose, in section 5, a high-level description format that allows us to define machines that differ on a specific dimension and study the effect of this dimension on the performances of the machines. ## the reading machine as mentioned in the introduction, the reading machine is an extension of the tbp 1 framework. the details of this algorithm are well known and do not need to be repeated here. we will only introduce the terms that are important for the rest of the paper. tbp is an algorithm that predicts the dependency syntactic structure of sentences. this task can be viewed as selecting for each word w of a sentence its syntactic governor (another word w of the sentence) as well as its syntactic function f . a directed arc, referred to as a dependency, is built from w to w, labeled with function f . the graph built at the end of the parsing process is a tree. the tbp algorithm builds the dependency tree by scanning the sentence word by word, in reading order. at each step, an action, is predicted and applied to the current configuration of the parser and yields a new configuration. the prediction is realized by a classifier that takes as input a configuration and computes a score for every possible action. the parser makes use of a stack containing words that need to be linked to words yet undiscovered. four types of actions are defined: shift, pushes the current word on the stack, reduce, pops the 1 several sets of actions have been proposed in the literature, the one used here is known as arc eager. stack, left l , creates a left dependency, labeled l, whose governor is the current word and dependent is top element of the stack and right l , which creates a right dependency, labeled l, whose dependent is the current word and governor is the top element of the stack. before giving a precise definition of the rm, in section 3.1, we describe the directions in which the tbp has been extended. tapes: the rm has one input tape, which is a read tape and an arbitrary number of output tapes which are read/write tapes. the input tape contains the text to parse. it is character based: each cell of the tape contains a character. the text has not been linguistically preprocessed: it has not been segmented into sentences nor into words. the current position of the reading head of the input tape is called the character index. output tapes are word based: each cell of a tape refers to a word of the input text. output tapes are used to write the predictions made by the machine, typically one tape per type of prediction. these tapes are synchronized: at all times, the head is at the same position for all tapes. this position is called the word index. ## training the rm the training process of a rm is close to tbp training. it starts with a dependency tree that is decomposed into a sequence of (state, configuration, action) triples, by a static oracle. the difference with tbp is that the set of actions is considerably larger since it encompasses actions for all six tasks. this sequence is used to train the classifiers: every classifier receives examples corresponding to the states it is related to. the rm is trained using only correct examples, predicted by the oracle. in order to increase the robustness to error propagation, we use a dynamic oracle @xcite to extract a new set of training examples where the actions applied were the one predicted by the network. 3 the rm is therefore trained to predict the next action given potentially incorrect configurations. four epochs are devoted to the first part of the training process, followed by 26 more epochs in dynamic oracle regime. 4 at each epoch, the machine is used to decode the development set, and is saved if its score (mean score across all 6 levels) is the best so far. we used cross entropy as a loss function and adagrad @xcite for optimization. the classifiers used to predict the actions can be decomposed into three parts: the first part is devoted to feature extraction, it is composed of several encoders applied to different parts of the rm configuration. the output of these encoders are then concatenated yielding a dense vector representation of the current configuration, to which we apply a dropout of 0.5 and feed it into a multi layer perceptron (mlp) composed of 2 hidden layers of respective sizes 3200 and 1600 with dropout 0.4 and relu activation. the output of the mlp is then fed into a decision layer, producting a probability distribution over the possible actions. the most probable action is predicted then applied to the configuration. a classifier can have up to 6 decision layers, one for every task. a schematic representation of the classifier structure can be found in blstm blstm blstm configuration input 3200 1600 tok pos pars .... .... they take as input a configuration and predict an action for up to 6 tasks. figure 1 . the most complex part of the classifier is the transformation of the configuration into a vector: the input of the mlp. depending of its feature function, the classifier extracts from the configuration elements that can be of different natures: the current state of the rm, tags or words read from the tapes, characters read from the input tape, previous action present in the history and words from the stack. all these elements are fed to specific bi-lstm that produce contextual representations, as in @xcite , that are in turn concatenated in the mlp input layer. all feature values are represented by trainable embeddings of size 128. these embeddings are randomly initialized, except for word embeddings that are pretrained foot_3 exclusively on the train set, in order to produce an embedding for unknown words (using words occurring only once in the train set). the bi-lstm that take sequences of these embeddings as input are made of only one layer of size 64. ## designing reading machines the precise definition of rm, introduced in section 3, allows us to design a large number of machines. every machine is defined by a large number of features and comparing machines is not always easy. in this section we define a more abstract description that is based on four high-level features, and define seven machines that are compared in section 6. we first describe the four high-level features then give a description of the machines. ## experiments the experiments presented in this section aim at exploring three directions. the first one is the modelling of top-down dependencies. we have introduced two means for taking into account such dependencies in a rm: joint prediction of several tasks, using a single classifier, and the feature span of the classifiers. the two first experiments aim at studying whether these two techniques allow to effectively model such dependencies. the second direction compares the sequential and the incremental strategies and measure how much information a parser gets from the knowledge of the next words pendencies collection @xcite version 2.7. in the official distribution of this corpus, the train/dev/test split is of respective sizes 364,349/36,775/10,298 words. in preliminary experiments, we found out that the test split was way too small to meaningfully compare machines. that's why we decided to use 10 fold crossvalidation: we realized ten different 80%/10%/10% train/dev/test splits and trained ten copies of each of our machines on these splits. the ten test sets were then decoded by the corresponding copy of the machine and the predictions were concatenated. this technique allowed us to compare the machines on their predictions on a test set of 427,763 words. we tested the significance of our comparisons using paired bootstrap resampling foot_5 @xcite , and reported in our tables the corresponding p-value, estimating the probability that in a pair of models, the model that appear to perform better is in reality a worse model. unfortunately, the resampling script we used (the one used in the conll 2018 shared task) is not able to produce p-values for the task of sentence segmentation, that is why the corresponding cells in tables 5,6 and 7 are empty. ## conclusion and future work this paper introduced a versatile parsing framework, called the reading machine, that allows us to compare incremental parsers that implement different parsing configurations. we illustrated this with two cases. in the first one, we compared different ways to take into account top down dependencies across six tasks. in the second, we compared the effect of the look-ahead on the parsing performances. this work will be extended in several directions. the first one concerns the analysis of the results obtained in our two first experiments. more investigation is needed to explain the reason why using past high level predictions cannot help low level current ones. likewise, we would like to understand if the better results of multi task learning comes from the modelling of top down dependencies. two means will be used in order to answer this question: probing and the development of (small) specialized test sets that focus on such phenomena. the sequential machines that have been proposed are greedy: a local decision taken by a machine is never questioned even when contradicted by future events. this behaviour is not appealing from an nlp perspective nor from a psycholinguistic one. in order to tackle this problem, we will introduce in the reading machine a backtrack mechanism that can predict left movements leading to the re-analysis of a previously analyzed part of the text. the third direction consists in evaluating the model against human experimental data. the reading machine has already been used to predict reading time. we will continue further in this direction and use the reading machine to predict saccades. the strategies implemented in the rm described in this paper completely specify the order in which predictions are made. we plan to relax this constraint and let the rm learn strategies that optimize its performances. a rm would have the ability to decide the order in which to perform some tasks (specifically, pos tagging, lemmatization and morphological analysis).