Unsupervised Parsing via Constituency Tests (2020)

Abstract: We propose a method for unsupervised parsing based on the linguistic notion of a constituency test. One type of constituency test involves modifying the sentence via some transformation (e.g. replacing the span with a pronoun) and then judging the result (e.g. checking if it is grammatical). Motivated by this idea, we design an unsupervised parser by specifying a set of transformations and using an unsupervised neural acceptability model to make grammaticality decisions. To produce a tree given a sentence, we score each span by aggregating its constituency test judgments, and we choose the binary tree with the highest total score. While this approach already achieves performance in the range of current methods, we further improve accuracy by fine-tuning the grammaticality model through a refinement procedure, where we alternate between improving the estimated trees and improving the grammaticality model. The refined model achieves 62.8 F1 on the Penn Treebank test set, an absolute improvement of 7.6 points over the previously best published result.

## introduction when developing a phrase structure grammar for a language, one powerful tool that linguists use is constituency tests. given a sentence and some span within it, one type of constituency test involves modifying the sentence via some transformation (e.g. replacing the span with a pronoun) and then judging the result (e.g. checking if it is grammatical). if a span passes constituency tests, then linguists have evidence that it is a constituent. motivated by this idea, as well as recent advancements in neural acceptability (grammaticality) models via pre-training @xcite @xcite , in this paper we propose a method for unsupervised parsing that operationalizes the way linguists use constituency tests. focusing on constituency tests that are judged via grammaticality, we begin by specifying a set of transformations that take as input a span within a sentence and output a new sentence (section 3). given these transformations, we then describe how to use a (potentially noisy) grammaticality model for parsing (section 4). specifically, we score the likelihood that a span is a constituent by applying the constituency tests and averaging their grammaticality judgments, i.e. the probability that the transformed sentence is grammatical under the model. we then parse via minimum risk decoding, where we score each binary tree by summing the scores of its contained spans, with the interpretation of maximizing the expected number of constituents. importantly, this scoring system accounts for false positives and negatives because it allows some spans in the tree to have low probability if the model is confident about the rest of the tree. to learn the grammaticality model, we note that given gold trees, we can train the model to accept constituency test transformations of gold constituents and reject those of gold distituents. on the other hand, given the model parameters, we can estimate trees via the parsing algorithm in section 4. therefore, we learn the model via alternating optimization. first, we learn an initial model by fine-tuning bert on unlabeled data to distinguish between real sentences and distractors produced by random corruptions like shuffling (section 5). then, we refine the model by alternating between (1) producing trees, and (2) maximizing/minimizing the scores of predicted constituents/distituents in those trees (section 6). to evaluate the effectiveness of our approach, we compare to existing methods for unsupervised parsing (section 7). our refined model achieves 62.8 f1 averaged over four random restarts on the penn treebank (ptb) test set, an absolute improvement of 7.6 points over the previous best published result, showing that constituency tests provide powerful inductive bias. analyzing our parser (section 8), we find that despite its strong numbers, it makes some mistakes that we might expect from the parser's reliance on this class of constituency tests, like attaching modifying phrases incorrectly. as one possible solution to these shortcomings, we use our method to induce the unsupervised recurrent neural network grammar (urnng) @xcite following the approach in @xcite , where we use our induced trees as supervision to initialize the rnng model and then perform unsupervised fine tuning via language modeling. the resulting model achieves 67.9 f1 averaged over four random restarts, approaching the supervised binary tree rnng with a gap of 4.9 points. ## related work grammar induction. there has been a long history of research on grammar induction. here, we touch on just a couple threads of work most related to our method. early works focused on building probabilistic context-free grammars (pcfgs) but found that inducing them with expectationmaximization (em) did not produce meaningful trees @xcite . we highlight some themes since then that have produced successful unsupervised parsers. directly modeling spans rather than mediating structure through a grammar: in contrast with previous work based on probabilistic grammars, the constituent-context model of @xcite proposed a different probabilistic formulation that modeled the constituency of each span directly, where each span yielded words conditioned on whether or not it was a constituent. parsing then proceeded via minimum risk decoding @xcite , where they chose the tree containing the maximum expected number of constituents. explicitly defining criteria for what it means to be a constituent: rather than designing a generative model over sentences and trees, @xcite proposed that constituents could be identified based on their span statistics, e.g. the mutual information between the left and right contexts of the span. ## constituency tests we begin by specifying a set of constituency tests. the constituency tests we focus on involve transformation functions c : (sent, i, j) → sent that take in a span and output a new sentence, and a judgment function g : @xmath0, 1} that judges the resulting transformed sentence. a span (sent, i, j) passes a constituency test if the judgment function approves of the transformed sentence, or g(c(sent, i, j)) = 1. then, parsing via constituency tests involves specifying a set of transformation functions (this section), learning the judgment function (sections 5 and 6), and aggregating these test results to produce a tree (section 4). we will focus on constituency tests that are judged via grammaticality because it is feasible to learn a grammaticality model using unlabeled data. we describe the set of transformations in because we specify constituency tests, while the parser is unsupervised in that it doesn't use labeled data, it is not tabula rasa in that we provide it with linguistically-inspired inductive bias, in contrast with past methods that may have less inductive bias or encode it more implicitly. to induce more and specify less, another interesting line of future work would involve inducing the tests as well. ## parsing algorithm with this set of transformations, in this section we describe how to parse sentences using a (potentially noisy) grammaticality model. in the supervised setting, @xcite and @xcite showed that independently scoring each span and then choosing the tree with the best total score produced a very accurate and simple parser, while @xcite showed a similar result in the unsupervised setting. therefore, we also use a span-based approach. we will use g θ : @xmath1, 1] to denote the grammaticality model with parameters θ, which outputs the probability that a given sentence is grammatical. first, we score each span by averaging the grammaticality judgments of its constituency tests, or ## initializing the grammaticality model in this section and the next, we describe how we learn the grammaticality model. given gold trees, we can train the model to accept constituency test transformations of gold constituents and reject those of gold distituents. on the other hand, given model parameters, we can estimate trees using the parsing algorithm in section 4. therefore, we first initialize the model (this section), and we then refine it via alternating optimization (section 6). previously, @xcite found that lstm grammaticality models trained with supervision versus those trained on a real/fake task achieved similar correlation with human judgments when evaluating on the corpus of linguistic acceptability (cola), a dataset with examples of acceptable and unacceptable taken from linguistic publications. given an unlabeled corpus of sentences and a set of corruptions, the real/fake task involves predicting whether a given sentence is real or corrupted. motivated by their result, we train our model via a real/fake task but a wider range of corruptions, as described in rather than training from scratch, we fine-tune the roberta model @xcite , a bert variant pre-trained on masked word prediction and next sentence prediction. as our unlabeled sentences, we use 5 million sentences from english gigaword @xcite , and we do not perform any early stopping. we report optimization hyperparameters in the appendix. comparing the real/fake roberta model to a supervised version, we find that the former achieves 0.21 mcc (matthews correlation coefficient) on the cola development set, while the latter achieves 0.73 mcc, in contrast with the finding in @xcite that real/fake and supervised lstms achieved similar accuracy (both around 0.2 to 0.3 mcc). foot_0 this gap is not totally surprising given how high the supervised roberta numbers are. however, when used for parsing via constituency tests, the real/fake roberta model outperforms the supervised model by about 6 f1 (before refinement), likely because invalid constituency tests look more like random corruptions than examples from the cola training set, which are taken from linguistics publications. ## refining the grammaticality model while the unrefined grammaticality model achieves 48.2 f1, which is in the range of current methods ( note that the span scores s θ (sent, i, j)) are derived from grammaticality judgments of constituency tests, so the only parameters are those in the grammaticality model. therefore, this step can be thought of as increasing the grammaticality judgment of every constituency test applied to every predicted constituent, while decreasing the judgments for predicted distituents. this step can be thought of as encouraging selfconsistency between the model's grammaticality judgments and the trees that result from them. for example, cky might choose a tree where a few of the spans are considered invalid if the model is confident about the other spans in the tree. the refinement procedure would then increase the probability of these initially invalid spans, which might help the model catch spans that it initially missed. we see evidence of this effect in section 8. in addition, there is an inherent mismatch between the real/fake task that the model was trained on and the constituency test judgment task it is being used for. for example, many of the sentences resulting from constituency tests are far out of distribution from sentences seen during training. therefore, this step can also be thought of as helping the grammar model adapt to its new setting. one problem, however, is that the loss function takes a gradient through the grammaticality judgments of all of the constituency tests for every span in the sentence. this computation takes up too much memory, given that a length-30 sentence has about 400 spans and thus about 3000 constituency tests. therefore, to reduce memory usage, for every sentence we only take the gradient through 16 of the constituency tests, chosen randomly. while early stopping would likely improve performance, we instead perform refinement for a ptb f1 model mean max prpn † @xcite 37.4 38.1 urnng @xcite -45.4 on † @xcite 47.7 49.4 neural pcfg † @xcite 50.8 52.6 diora @xcite -58.9 compound pcfg † @xcite 55.2 60.1 left branching 8.7 balanced 18.5 right branching 39.5 ours (before refinement) 48.2 ours (after refinement) oracle binary trees 84. 3 baseline numbers are taken from @xcite . after refinement, the parser outperforms the previous best method by 7.6 points. † denotes models trained without punctuation. ## conclusion in this paper, we showed that using constituency tests to parse sentences is an effective approach, achieving strong performance for unsupervised parsing. furthermore, we used the interpretability of constituency tests to highlight and explain the parser's strengths and shortcomings, like the "[ subject verb ]" and "adverb [ adjective noun ]" misbracketings, revealing potential next steps for improvement. therefore, we see parsing via constituency tests as a promising new approach with both strong results and many open questions.