Approximating CKY with Transformers (2023)

Abstract: We investigate the ability of transformer models to approximate the CKY algorithm, using them to directly predict a sentence’s parse and thus avoid the CKY algorithm’s cubic dependence on sentence length. We find that on standard constituency parsing benchmarks this approach achieves competitive or better performance than comparable parsers that make use of CKY, while being faster. We also evaluate the viability of this approach for parsing under random PCFGs. Here we find that performance declines as the grammar becomes more ambiguous, suggesting that the transformer is not fully capturing the CKY computation. However, we also find that incorporating additional inductive bias is helpful, and we propose a novel approach that makes use of gradients with respect to chart representations in predicting the parse, in analogy with the CKY algorithm being a subgradient of a partition function variant with respect to the chart.

## introduction parsers based on transformers @xcite currently represent the state of the art in constituency parsing @xcite , and recent work @xcite @xcite @xcite has found that transformers are capable of learning constituentlike representations of spans of text. given these successes, it is natural to wonder whether transformers capture the algorithmic processes we associate with constituency parsing, such as the cky algorithm @xcite @xcite . indeed, one might suspect that the layers of a transformer are building up phrase-level representations, much as the cky algorithm itself builds up its chart. such a hypothesis has become particularly compelling in light of recent work studying the ability of transformers, and graph neural networks more generally, to implement or approximate classical algorithms @xcite @xcite . if standard transformers were indeed approximating cky, there would be several implications. practically, such a finding might lead to faster neural parsers. whereas state-of-the-art parsers (e.g., that of @xcite and followup work @xcite ) tend to implement cky on top of transformerrepresentations, thus incurring a parsing timecomplexity that is cubic in the sentence length, we could conceivably extract a parse from simply running a transformer over the sentence; this would involve a time-complexity cost that is only quadratic in the sentence length. moreover, since there is significant academic and industrial effort aimed at making standard transformers faster (e.g., that of @xcite ), this progress could conceivably transfer automatically to the parsing case. in addition to more practical considerations, the task of producing cky parses with transformers provides an excellent opportunity for investigating whether endowing transformers with additional inductive bias can help them in implementing classical algorithms, a topic recently studied by @xcite and others. the results of such an investigation would also bear on recent results relating to the computational power of transformers trained in the standard way @xcite . accordingly, we first show that having a pretrained transformer simply predict an entire parse by independently labeling each span -an approach similar to that taken in a different context by @xcite only at training time -is sufficient to obtain competitive or better performance on standard constituency parsing benchmarks, while being significantly faster. while these constituency parsing results are en-1 14016 couraging, they do not imply that trained transformers are implementing the cky algorithm, because the transformer may simply be predicting a parse without it being highest-scoring under some grammar. we accordingly go on to investigate transformers' performance in predicting a cky parse under randomly generated pcfgs. given a randomly generated pcfg, it is of course easy to check whether a predicted parse is indeed highestscoring. in this setting we find that the performance of transformers negatively correlates with the ambiguity of the pcfg, suggesting that they are not in fact implementing something cky-like. at the same time, we find that incorporating additional inductive bias into the standard architecture is helpful, and we propose a novel approach, which makes use of gradients with respect to chart representations in predicting the parse. this inductive bias is inspired by the fact that the cky algorithm can be viewed as computing the gradient of the "max score" partition function @xcite , and we find that this improves performance on random pcfgs significantly. in summary, we show that: code for reproducing all experiments is available at https://github.com/ghazalkhalighinejad/ approximating-cky . ## background and notation the cky algorithm @xcite @xcite computes a highest scoring parse of a sentence under a probabilistic contextfree grammar (pcfg). let @xmath0, σ, r, s, w) be a pcfg, with n the set of non-terminals, σ the set of terminals, r the set of rules, s a start non-terminal, and w a set of probabilities per rule (which normalize over left-hand-sides). given a sentence @xmath1, the cky algorithm uses a dynamic program to compute a highest scoring parse of x under g, and it requires o(|r|t 3 ) computation time. following the notation in rush (2020), let ℓ @xmath2.g., log probabilities) associated with the rules in pcfg g, and let ℓ e (x) ∈ r t ×|n | represent the log potentials corresponding to each token in input sentence x. we can use these log potentials to compute the chart β ∈ r t ×t ×|n | for x, where β[i, j, a] represents the sum (under a particular semiring) of all weight associated with the a-th non-terminal yielding x i:j . these log potentials can also be used to compute a highest-scoring parse, which we will refer to as β * ∈ {0, 1} t ×t ×|n | ; this is the one-hot representation of a parse, with β * [i, j, a] = 1 iff @xmath3:j in the parse. cky as a subgradient recent work @xcite has emphasized that inference algorithms such as cky may be fruitfully viewed as a special case of calculating the gradient or a subgradient of a generalized log partition function with respect to (some function of) the log potentials associated with an input. in particular, the cky algorithm can be viewed as computing a subgradient of the "max score" variant of the log partition function with respect to an input sentence x's chart; see appendix a for details. thus, β * is relatively easily obtained with automatic differentiation frameworks. however, computing it in this way is exactly equivalent to running the traditional cky algorithm, and so still requires o(|r|t 3 ) time. ## predicting parses as described in section 2, we define β * ∈ {0, 1} t ×t ×|n | to be a chart-sized tensor representing a cky parse of a sentence x, with β * [i, j, a] = 1 if and only if nonterminal a yields x i:j . we will use a very simple approach to predict β * with a transformer. let h @xmath4, and let h i,:d/2 and h i,d/2: , both in r d/2 , be (respectively) the first and last d/2 elements in h i . we decoding note that forming β from the h i is only quadratic in sentence-length, and so if we can extract a parse from it in sub-cubic time we will improve (asymptotically) over cky. in practice, we simply take the highest-scoring label for each span, and ignore spans for which the highest-scoring label is non-constituent. we then sort the predicted spans, first in decreasing order of end-token and then (stably) in increasing order of start-token, and build up the tree from left to right. we thus incur only an o(t 2 (|n | + log 2 t )) decoding cost. 1 training given a gold (binarized) parse β * , we simply treat predicting the labels of each span as t (t + 1)/2 independent multi-class classifi-cation problems, and we use the standard crossentropy loss. note that corro (2020) proposes this independent-span-classification training approach in the context of discontinuous constituency parsing (though with a fixed zero-weight for the nonconstituent label). we note that concurrent work by @xcite also explores both training and decoding by making span predictions independently. ## constituency parsing experiments we conduct experiments in two main settings. we first consider modern neural constituency parsing on standard benchmark datasets. we then consider parsing under randomly generated pcfgs. we highlight several important differences between these two settings. first, modern constituency parsing is grammarless. as such, modern constituency parsers do not predict the highest scoring parse under some pcfg, and they use a simpler variant of cky which composes spans but has no notion of grammar-rules. while it is still interesting (at least from a computational efficiency perspective) to see if directly predicting parses is competitive with running this simpler cky variant, it is difficult to distinguish a transformer learning this cky variant from it simply learning to predict gold parses. this concern motivates our second setting, of randomly generated pcfgs, where there are well-defined highest-scoring parses under each pcfg, and where we can evaluate whether the transformer has predicted them. we consider this random pcfg setting in section 5. ## random pcfg experiments to generate random pcfgs, we follow the method used by @xcite . 4 their method involves first generating a synthetic context-free grammar (cfg) with a specified number of terminals, non-terminals, binary rules, and lexical rules. to assign probabilities to the rules, they then use an em-based estimation procedure @xcite to update the production rules such that the length distribution of the estimated pcfg is similar to that of the ptb corpus @xcite . ## related work modern neural constituency parsers typically fall into one of three camps: chart-based parsers @xcite @xcite @xcite @xcite @xcite , transitionbased parsers @xcite @xcite @xcite , or sequence-to-sequence-style parsers @xcite @xcite @xcite . our approach most closely resembles chartbased methods, in that we compute scores for all spans for all non-terminals. however, unlike chart-based parsers, we aim to only approximate, or amortize, running the cky algorithm. unlike transition-based or sequence-to-sequence-style methods, our approximation involves attempting to predict a parse jointly and independently, rather than incrementally. within the world of chart-based neural parsers, those of @xcite and @xcite have been enormously influential, and state-of-the-art constituency parsers, such as those of @xcite and @xcite , adapt this approach while improving it. the approach of employing an independent-span classification training objective along with greedy decoding for inference has also been explored by @xcite in the context of depen-dency parsing. it is worth emphasizing that while the @xcite work shows that a scoring model with quadratic complexity can approximate the also quadratic chu-liu-edmonds algorithm @xcite , used for decoding in dependency parsing, our work focuses on approximating a cubic complexity decoding algorithm using a scoring model with quadratic complexity. we are additionally motivated by recent work on neural algorithmic reasoning @xcite @xcite @xcite , some of which has endeavored to solve classical dynamic programs @xcite and mdps @xcite with graph neural networks and transformers, respectively. one respect in which learning to compute cky differs from many other algorithmic reasoning challenges (including other dynamic programs) is that in addition to its discrete sentence input, cky also consumes continuous log potentials. finally, the idea of training a model to produce the solution to an optimization problem is known as training an "inference network," and has been used famously in approximate probabilistic inference scenarios (kingma and welling, 2014) and in approximating gradient descent @xcite . most similar to our approach, @xcite train an inference network to do viterbistyle sequence labeling, although they do not consider parsing, and they require inference networks for both training and test-time prediction due to their large-margin approach. ## discussion and conclusion our findings on the ability of transformers to approximate cky are decidedly mixed. on the one hand, using transformers to independently predict spans in a constituency parse is competitive with using very strong neural chart parsers, and it is moreover much faster to predict parses in this independent, non-cky-based way. on the other hand, if transformers are capturing the cky computation, they ought to be able to parse even under random pcfgs, and it is clear that as the ambiguity of the grammar increases they struggle with this. we have also found that making a transformer's computation more closely resemble that of a classical algorithm, either by sharing computation layers as proposed by @xcite and @xcite , or by having it make use of the gradient with respect to a scoring function, is helpful. this finding both confirms previous results in this area, and also suggests that the inductive bias we seek to incorporate in our models may need to closely match the problem. there are many avenues for future work, and attempting to find a minimal general-purpose architecture that can in fact parse under random pcfgs is an important challenge. in particular, it is worth exploring whether other forms of pretraining (i.e., pre-training distinct from bert's) might benefit this task more. another important future challenge to address is whether it is possible to have a model consume both the input sentence as well as the parameters (as the cky algorithm does), rather than merely pretrain on parsed sentences generated using the parameters.