The Limitations of Limited Context for Constituency Parsing (2021)

Abstract: Incorporating syntax into neural approaches in NLP has a multitude of practical and scientific benefits. For instance, a language model that is syntax-aware is likely to be able to produce better samples; even a discriminative model like BERT with a syntax module could be used for core NLP tasks like unsupervised syntactic parsing. Rapid progress in recent years was arguably spurred on by the empirical success of the Parsing-Reading-Predict architecture of (Shen et al., 2018a), later simplified by the Order Neuron LSTM of (Shen et al., 2019). Most notably, this is the first time neural approaches were able to successfully perform unsupervised syntactic parsing (evaluated by various metrics like F-1 score). However, even heuristic (much less fully mathematical) understanding of why and when these architectures work is lagging severely behind. In this work, we answer representational questions raised by the architectures in (Shen et al., 2018a, 2019), as well as some transition-based syntax-aware language models (Dyer et al., 2016): what kind of syntactic structure can current neural approaches to syntax represent? Concretely, we ground this question in the sandbox of probabilistic context-free-grammars (PCFGs), and identify a key aspect of the representational power of these approaches: the amount and directionality of context that the predictor has access to when forced to make parsing decision. We show that with limited context (either bounded, or unidirectional), there are PCFGs, for which these approaches cannot represent the max-likelihood parse; conversely, if the context is unlimited, they can represent the max-likelihood parse of any PCFG.

## introduction neural approaches have been steadily making their way to nlp in recent years. by and large however, the neural techniques that have been scaled-up the most and receive widespread usage do not explicitly try to encode discrete structure that is natural to language, e.g. syntax. the reason for this is perhaps not surprising: neural models have largely achieved substantial improvements in unsupervised settings, bert @xcite being the defacto method for unsupervised pre-training in most nlp settings. on the other hand unsupervised syntactic tasks, e.g. unsupervised syntactic parsing, have long been known to be very difficult tasks @xcite . however, since incorporating syntax has been shown to improve language modeling @xcite as well as natural language inference @xcite @xcite , syntactic parsing remains important even in the current era when large pre-trained models, like bert @xcite , are available. arguably, the breakthrough works in unsupervised constituency parsing in a neural manner were @xcite , achieving f1 scores 42.8 and 49.4 on the wsj penn treebank dataset @xcite . both of these architectures, however (especially @xcite are quite intricate, and it's difficult to evaluate what their representational power is (i.e. what kinds of structure can they recover). moreover, as subsequent more thorough evaluations show @xcite , these methods still have a rather large performance gap with the oracle binary tree (which is the best binary parse tree according to f1-score) -raising the question of what is missing in these methods. we theoretically answer both questions raised in the prior paragraph. we quantify the representational power of two major frameworks in neural approaches to syntax: learning a syntactic distance @xcite and learning to parse through sequential transitions @xcite . to formalize our results, we con-sider the well-established sandbox of probabilistic context-free grammars (pcfgs). namely, we ask: when is a neural model based on a syntactic distance or transitions able to represent the maxlikelihood parse of a sentence generated from a pcfg? we focus on a crucial "hyperparameter" common to practical implementations of both families of methods that turns out to govern the representational power: the amount and type of context the model is allowed to use when making its predictions. briefly, for every position t in the sentence, syntactic distance models learn a distance d t to the previous token -the tree is then inferred from this distance; transition-based models iteratively construct the parse tree by deciding, at each position t, what operations to perform on a partial parse up to token t. a salient feature of both is the context, that is, which tokens is d t a function of (correspondingly, which tokens can the choice of operations at token t depend on)? we show that when the context is either bounded (that is, d t only depends on a bounded window around the t-th token) or unidirectional (that is, d t only considers the tokens to the left of the tth token), there are pcfgs for which no distance metric (correspondingly, no algorithm to choose the sequence of transitions) works. on the other hand, if the context is unbounded in both directions then both methods work: that is, for any parse, we can design a distance metric (correspondingly, a sequence of transitions) that recovers it. this is of considerable importance: in practical implementations the context is either bounded (e.g. in @xcite , the distance metric is parametrized by a convolutional kernel with a constant width) or unidirectional (e.g. in @xcite , the distance metric is computed by a lstm, which performs a left-to-right computation). this formally confirms a conjecture of htut et al. (2018), who suggested that because these models commit to parsing decision in a left-to-right fashion and are trained as a part of a language model, it may be difficult for them to capture sufficiently complex syntactic dependencies. our techniques are fairly generic and seem amenable to analyzing other approaches to syntax. finally, while the existence of a particular pcfg that is problematic for these methods doesn't necessarily imply that the difficulties will carry over to real-life data, the pcfgs that are used in our proofs closely track lin-guistic intuitions about difficult syntactic structures to infer: the parse depends on words that come much later in the sentence. ## overview of results we consider several neural architectures that have shown success in various syntactic tasks, most notably unsupervised constituency parsing and syntax-aware language modeling. the general framework these architectures fall under is as follows: to parse a sentence @xmath0...w n with a trained neural model, the sentence w is input into the model, which outputs o t at each step t, and finally all the outputs {o t } n @xmath1. given unbounded time and space resources, by a seminal result of @xcite , an rnn implementation of this framework is turing complete. in practice it is common to restrict the form of the output o t in some way. in this paper, we consider the two most common approaches, in which o t is a real number representing a syntactic distance (section 2.1) @xcite or a sequence of parsing operations (section 2.2) @xcite @xcite . we proceed to describe our results for each architecture in turn. ## related works neural models for parsing were first successfully implemented for supervised settings, e.g. @xcite @xcite . unsupervised tasks remained seemingly out of reach, until the proposal of the parsing-reading-predict network (prpn) by @xcite , whose performance was thoroughly verified by extensive experiments in @xcite . the follow-up paper @xcite introducing the on-lstm architecture simplified radically the architecture in @xcite , while still ultimately attempting to fit a distance metric with the help of carefully designed master forget gates. subsequent work by @xcite departed from the usual way neural techniques are integrated in nlp, with great success: they proposed a neural parameterization for the em algorithm for learning a pcfg, but in a manner that leverages semantic information as well -achieving a large improvement on unsupervised parsing tasks. 2 in addition to constituency parsing, dependency parsing is another common task for syntactic parsing, but for our analyses on the ability of various approaches to represent the max-likelihood parse of sentences generated from pcfgs, we focus on the task of constituency parsing. moreover, it's important to note that there is another line of work aiming to probe the ability of models trained without explicit syntactic consideration (e.g. bert) to nevertheless discover some (rudimentary) syntactic elements @xcite @xcite @xcite @xcite @xcite . however, to-date, we haven't been able to extract parse trees achieving scores that are close to the oracle binarized trees on standard benchmarks @xcite . methodologically, our work is closely related to a long line of works aiming to characterize the representational power of neural models (e.g. rnns, lstms) through the lens of formal languages and formal models of computation. some of the works of this flavor are empirical in nature (e.g. lstms have been shown to possess stronger abilities to recognize some context-free language and even some context-sensitive language, compared with simple rnns @xcite or grus @xcite ); some results are theoretical in nature (e.g. siegelmann and sontag (1992)'s proof that with unbounded precision and unbounded time complexity, rnns are turing-complete; related results investigate rnns with bounded precision and computation time @xcite , as well as 2 by virtue of not relying on bounded or unidirectional context, the compound pcfg @xcite eschews the techniques in our paper. specifically, by employing a bidirectional lstm inference network in the process of constructing a tree given a sentence, the parsing is no longer "left-to-right". memory @xcite . our work contributes to this line of works, but focuses on the task of syntactic parsing instead. ## preliminaries in this section, we define some basic concepts and introduce the architectures we will consider. ## representational power of neural syntactic distance methods in this section we formalize the results on syntactic distance-based methods. since the tree induction algorithm always generates a binary tree, we consider only pcfgs in chomsky normal form (cnf) (definition 4.4) so that the max likelihood parse of a sentence is also a binary tree structure. to formalize the notion of "representing" a pcfg, we introduce the following definition: definition 5.1 (representing pcfg with syntactic distance). let g be any pcfg in chomsky normal form. a syntactic distance function d is said to be able to p-represent g if for a set of sentences in l(g) whose total probability is at least p, d can correctly induce the tree structure of the max likelihood parse of these sentences without ambiguity. remark. ambiguities could occur when, for example, there exists t such that d @xmath2. in this case, the tree induction algorithm would have to break ties when determining the local structure for w t-1 w t w t+1 . we preclude this possibility in definition 5.1. in the least restrictive setting, the whole sentence w , as well as the position index t can be taken into consideration when determining each d t . we prove that under this setting, there is a syntactic distance measure that can represent any pcfg. theorem 1 (full context). let c @xmath3, t). for each pcfg g in chomsky normal form, there exists a syntactic distance measure proof. for any sentence @xmath4...s @xmath5, let t be its max likelihood parse tree. since g is in chomsky normal form, t is a binary tree. we will describe an assignment of {d t : 2 ≤ @xmath6. specifically, ∀@xmath7, n], let a t denote the lowest common ancestor of w t-1 and w t in t . let d t denote the shortest distance between a t and the root of t . finally, let d @xmath8. as a result, {d t : 2 ≤ @xmath9. remark. since any pcfg can be converted to chomsky normal form @xcite , theorem 1 implies that given the whole sentence and the position index as the context, the syntactic distance has sufficient representational power to capture any pcfg. it does not state, however, that the whole sentence and the position are the minimal contextual information needed for representability nor does it address training (i.e. optimization) issues. on the flipside, we show that restricting the context even mildly can considerably decrease the representational power. namely, we show that if context is bounded even in a single direction (to the left or to the right), there are pcfgs on which any syntactic distance will perform poorly foot_2 . (note in the implementation @xcite the context only considers a bounded window to the left.) theorem 2 (limitation of left-to-right parsing via syntactic distance). let w 0 = s be the sentence start symbol. let the context c @xmath10, w 1 , ..., w t+l ). for any @xmath11, consider the string l @xmath12,l ). note that in the parse tree of l k , the rule @xmath13. hence, a k and a k+1 are the unique pair of adjacent non-terminals in a 1 a 2 ...a m+1 whose lowest common ancestor is the closest to the root in the parse tree of l k . then, in order for the syntactic distance metric d to induce the correct parse tree for l k , d k must be the unique maximum in {d t : 2 ≤ @xmath14. note that ∀1 ≤ k 1 < k 2 ≤ m, the first m + 1 + l tokens of l k 1 and l k 2 are the same, which implies that the inferred syntactic distances {d t : 2 ≤ @xmath15. thus, it is impossible for d to induce the correct parse tree for both l k 1 and l k 2 . hence, d is correct on at most one l @xmath16,l ), which corresponds to probability at most 1/@xmath17. therefore, d cannot -represent g m,l . remark. in the counterexample, there are only m possible parse structures for the prefix a 1 a 2 ...a m+1 . hence, the proved fact that the probability of being correct is at most 1/m means that under the restrictions of unbounded look-back and bounded look-ahead, the distance cannot do better than random guessing for this grammar. remark. the above theorem 2 formalizes the intuition discussed in @xcite outlining an intrinsic limitation of only considering bounded context in one direction. indeed, for the pcfg constructed in the proof, the failure is a function of the context, not because of the fact that we are using a distance-based parser. note that as a corollary of the above theorem, if there is no context (c @xmath18, i.e. ## representational power of the ordered neuron architecture in this section, we formalize the results characterizing the representational power of the on-lstm architecture. the master forget gates of the on-lstm, { ft } n @xmath19, 1] d , encode the hierarchical structure of a parse tree, and @xcite proposes to carry out unsupervised constituency parsing via a reduction from the gate vectors to syntactic distances by setting: first we show that the gates in on-lstm in principle form a lossless representation of any parse tree. theorem 3 (lossless representation of a parse tree). for any sentence @xmath20...w n with parse tree t in any pcfg in chomsky normal form, there exists a dimensionality @xmath21, a sequence of vectors { ft } n @xmath22, 1] d , such that the estimated syntactic distances via (1) induce the structure of t . proof. by theorem 1, there is a syntactic distance measure {d t } n @xmath23, d @xmath24. for each @xmath25..n, set @xmath26, breaking ties arbitrarily. then, each @xmath27, n -1], and { dt } n @xmath28. let @xmath29. for each @xmath30..n, let @xmath31, ..., 0, 1, ..., 1) whose lower dt dimensions are 0 and higher d -dt dimensions are 1. then, therefore, the calculated { df t } n @xmath32. although theorem 3 shows the ability of the master forget gates to perfectly represent any parse tree, a left-to-right parsing can be proved to be unable to return the correct parse with high probability. in the actual implementation in @xcite , the (real-valued) master forget gate vectors { ft } n @xmath33...w n to a model trained with a language modeling objective. in other words, ft,j is calculated as a function of w 1 , ..., w t , rather than the entire sentence. as such, this left-to-right parser is subject to similar limitations as in theorem 2: theorem 4 (limitation of syntactic distance estimation based on on-lstm). for @xmath34, there exists a pcfg g in chomsky normal form, such that the syntactic distance measure calculated with (1), df t , cannot -represent g. proof. since by definition 4.5, ft,j is a function of w 1 , ..., w t , the estimated syntactic distance df t is also a function of w 1 , ..., w t . by theorem 2, even with unbounded look-back context w 1 , ..., w t , there exists a pcfg for which the probability that df t induces the correct parse is arbitrarily low. ## representational power of transition-based parsing in this section, we analyze a transition-based parsing framework inspired by @xcite @xcite . again, we proceed to say first that "full context" confers full representational power. namely, using the terminology of definition 4.6, we let the context c t at each position t be the whole sentence w and the position index t. note that any parse tree can be generated by a sequence of transitions defined in definition 4.7. indeed, @xcite describes an algorithm to find such a sequence of transitions via a "depth-first, left-to-right traversal" of the tree. proceeding to limited context, in the setting of typical left-to-right parsing, the context c t consists of all current and past tokens {w j } t @xmath35, ..., z j n j )} t @xmath36. we'll again prove even stronger negative results, where we allow an optional look-ahead to l input tokens to the right. theorem 5 (limitation of transition-based parsing without full context). for @xmath37, there exists a pcfg g in chomsky normal form, such that for any learned transition-based parser (definition 4.6) based on context c @xmath38, {(z j 1 , ..., z j n j )} t @xmath39, the sum of the probabilities of the sentences in l(g) for which the parser returns the maximum likelihood parse is less than . proof. let @xmath40. consider the pcfg g m,l in definition 2.1. note that ∀k, @xmath41. then in the parse tree of l k , a k and a k+1 are the unique pair of adjacent terminals in a 1 a 2 ...a m+1 whose lowest common ancestor is the closest to the root. thus, different l k requires a different sequence of transitions within the first m + 1 input tokens, i.e. {z t i } @xmath42, 1≤@xmath43. for each @xmath44,l ), before the last token w m+2+l is processed, based on the common prefix w 1 w 2 ...w m+1+@xmath45...a m+1+l , it is equally likely that @xmath46, ∀k, w. prob. 1/m each. moreover, when processing w m+1 , the bounded look-ahead window of size l does not allow access to the final input token a m+2+@xmath47. thus, ∀1 ≤ k 1 < k 2 ≤ m, it is impossible for the parser to return the correct parse tree for both l k 1 and l k 2 without ambiguity. hence, the parse is correct on at most one l @xmath48, which corresponds to probability at most 1/@xmath49. ## conclusion in this work, we considered the representational power of two frameworks for constituency parsing prominent in the literature, based on learning a syntactic distance and learning a sequence of iterative transitions to build the parse tree -in the sandbox of pcfgs. in particular, we show that if the context for calculating distance/deciding on transitions is limited at least to one side (which is typically the case in practice for existing architectures), there are pcfgs for which no good distance metric/sequence of transitions can be chosen to construct the maximum likelihood parse. this limitation was already suspected in @xcite as a potential failure mode of leading neural approaches like @xcite and we show formally that this is the case. the pcfgs with this property track the intuition that bounded context methods will have issues when the parse at a certain position depends heavily on latter parts of the sentence. the conclusions thus suggest re-focusing our attention on methods like @xcite which have enjoyed greater success on tasks like unsupervised constituency parsing, and do not fall in the paradigm analyzed in our paper. a question of definite further interest is how to augment models that have been successfully scaled up (e.g. bert) in a principled manner with syntactic information, such that they can capture syntactic structure (like pcfgs). the other question of immediate importance is to understand the interaction between the syntactic and semantic modules in neural architectures -information is shared between such modules in various successful architectures, e.g. @xcite @xcite , and the relative pros and cons of doing this are not well understood. finally, our paper purely focuses on representational power, and does not consider algorithmic and statistical aspects of training. as any model architecture is associated with its distinct optimization and generalization considerations, and natural language data necessitates the modeling of the interaction between syntax and semantics, those aspects of considerations are well beyond the scope of our analysis in this paper using the controlled sandbox of pcfgs, and are interesting directions for future work.