Cornell University llee@cs.cornell.edu Abstract Naturally-occurring bracketings, such as answer fragments to natural language questions and hyperlinks on webpages, can reflect human syntactic intuition regarding phrasal boundaries. Their availability and approximate correspondence to syntax make them appealing as distant information sources to incorporate into unsupervised constituency parsing. But they are noisy and incomplete; to address this challenge, we develop a partial-brackets-aware structured ramp loss in learning. Experiments demonstrate that our distantly-supervised models trained on naturally-occurring bracketing data are more accurate in inducing syntactic structures than competing unsupervised systems. On the English WSJ corpus, our models achieve an unlabeled F1 score of 68 . 9 for constituency parsing. 1 1 Introduction Constituency is a foundational building block for phrase-structure grammars. It captures the notion of what tokens can group together and act as a single unit. The motivating insight behind this paper is that constituency may be reflected in markups of bracketings that people provide in doing natural tasks. We term these segments naturally-occurring bracketings for their lack of intended syntactic annotation. These include, for example, the segments people pick out from sentences to refer to other Wikipedia pages or to answer semantically-oriented questions; see Figure 1 for an illustration. Gathering such data requires low annotation expertise and effort. On the other hand, these data are not necessarily suitable for training parsers, as they often contain incomplete, incorrect and sometimes conflicting bracketing information. It is thus an empirical question whether and how much we 1 Our code is publicly available at https://github. [ Republicans ] have been imploring the White House [ to compromise on [ the wage issue ] ] . A: Republicans A: To compromise on the wage issue A: The wage issue QA-SRL Wikipedia Science fiction (sometimes shortened to sci-fi or SF) is a genre of speculative fiction that typically deals with imaginative and futuristic concepts such as advanced science and technology, space exploration, time travel, parallel universes, and extraterrestrial life. Republicans have been imploring the White House to compromise on the wage issue. Context: Q&As: Corresponding bracketings: Figure 1: Two example types of naturally-occurring bracketings. Q: Who have been imploring something? Q: What have someone been imploring? Q: What will someone compromise on? could learn syntax from these naturally-occurring bracketing data. To overcome the challenge of learning from this kind of noisy data, we propose to train discriminative constituency parsers with structured ramp loss (Do et al., 2008), a technique previously adopted in machine translation (Gimpel and Smith, 2012). Specifically, we propose two loss functions to directly penalize predictions in conflict with available partial bracketing data, while allowing the parsers to induce the remaining structures. We experiment with two types of naturally-occurring bracketing data, as illustrated in Figure 1. First, we consider English question-answer pairs collected for semantic role labeling (QA-SRL; He et al., 2015). The questions are designed for non-experts to specify semantic arguments of predicates in the sentences. We observe that although no syntactic structures are explicitly asked for, humans tend to select constituents in their answers. Second, Wikipedia articles 2 are typically richly annotated with internal links to other articles. These links are marked on phrasal units that refer to standalone concepts, and similar to the QA-SRL data, they frequently coincide with syntactic constituents. Experiment results show that naturally-occurring bracketings across both data sources indeed help our models induce syntactic constituency structures. Training on the QA-SRL bracketing data achieves an unlabeled F1 score of 68 . 9 on the English WSJ corpus, an accuracy competitive with state-of-the-art unsupervised constituency parsers that do not utilize such distant supervision data. We find that our proposed two loss functions have slightly different interactions with the two data sources, and that the QA-SRL and Wikipedia data have varying coverage of phrasal types, leading to different error profiles. In sum, through this work, (1) we demonstrate that naturally-occurring bracketings are helpful for inducing syntactic structures, (2) we incorporate two new cost functions into structured ramp loss to train parsers with noisy bracketings, and (3) our distantly-supervised models achieve results competitive with the state of the art of unsupervised constituency parsing despite training with smaller data size (QA-SRL) or out-of-domain data (Wikipedia). Constituents are naturally reflected in various human cognitive processes, including speech production and perception (Garrett et al., 1966; Gee and Grosjean, 1983), reading behaviors (Hale, 2001; Boston et al., 2008), punctuation marks (Spitkovsky et al., 2011), and keystroke dynamics (Plank, 2016). Conversely, these externalized signals help us gain insight into constituency representations. We consider two such data sources: a) Answer fragments When questions are answered with fragments instead of full sentences, those fragments tend to form constituents. This phenomenon corresponds to a well-established constituency test in the linguistics literature (Carnie, 2012, pg. 98, inter alia). b) Webpage hyperlinks Since a hyperlink is a pointer to another location or action (e.g., mailto: links), anchor text often represents a conceptual unit related to the link destination. Indeed, Spitkovsky et al. (2010) first give empirical evidence that around half of the anchor text instances in their data respects constituent boundaries and Sgaard (2017) demonstrates that hyperlink data can help boost chunking accuracy in a multi-task learning setup. Both types of data have been considered in previous work on dependency-grammar induction (Spitkovsky et al., 2010; Naseem and Barzilay, 2011), and in this work, we explore their efficacy for learning constituency structures. For answer fragments, we use He et al.'s (2015) question-answering-driven semantic role labeling (QA-SRL) dataset, where annotators answer wh questions regarding predicates in sentences drawn from the Wall Street Jounal (WSJ) section of the Penn Treebank (PTB; Marcus et al., 1993). For hyperlinks, we used a 1% sample of 2020-05-01 English Wikipedia, retaining only within-Wikipedia links. 3 We compare our extracted naturally-occurring bracketings with the reference phrase-structure annotations: 4 Table 1 gives relevant statistics. Our results re-affirm Spitkovsky et al.'s (2010) finding that a large proportion of hyperlinks coin-3 See Appendix A for details. For ground-truth structures in the Wikipedia data, we apply a state-of-the-art PTB-trained constituency parser (Ki-taev et al., 2019). cide with syntactic constituents. We also find that 22 . 4% / 35 . 8% of the natural bracketings are single-word spans, which cannot facilitate parsing decisions, while 11 . 8% / 5 . 3% of QA-SRL/Wikipedia spans actually conflict with the reference trees and can thus potentially harm training. The QA-SRL data seems more promising for inducing better-quality syntactic structures, as there are more bracketings available across a diverse set of constituent types. Preliminaries The inputs to our learning algorithm are tuples ( w, B ) , where w = w 1 , . . . , w n is a lengthn sentence and B = { ( b k , e k ) } is a set of naturally-occurring bracketings, denoted by the beginning and ending indices b k and e k into the sentence w . As a first step, we extract BERT-based contextualized word representations (Devlin et al., 2019) to associate each token w i with a vector x i . 5 See Appendix B for details. Scoring Spans Based on the x i vectors, we assign a score s ij to each candidate span ( i, j ) in the sentence indicating its appropriateness as a constituent in the output structure. We adopt a biaffine scoring function (Dozat and Manning, 2017): s ij = [ l i ; 1] TW [ r j ; 1] , where [ v ; 1] appends 1 to the end of vector v , and l i = MLP left ( x i ) and r j = MLP right ( x j ) are the outputs of multi-layer perceptrons (MLPs) that take the vectors at span boundaries as inputs. 6 Decoding We define the score s ( y ) of a binary-branching constituency tree y to be the sum of scores of its spans. The best scoring tree among all valid trees Y can be found using the CKY algorithm (Cocke, 1969; Kasami, 1965; Younger, 1967). Learning Large-margin training (Taskar et al., 2005) is a typical choice for supervised training of constituency parsers. It defines the following 5 The use of pre-trained language models can mitigate the fact that our distant supervision data are either out-of-domain (Wikipedia) or small in size (QA-SRL). 6 This is inspired by span-based supervised constituency-parsing methods (Stern et al., 2017), which in turn was based on Wang and Chang (2016). These papers look at the difference vectors between two boundary points, while our scoring function directly uses the vectors at the boundaries (which is more expressive than only using difference vectors). loss function to encourage a large margin of at least ( y, y  ) between the gold tree y  and any predicted tree y : l = max y Y [ s ( y ) + ( y, y  )]  s ( y  ) , where ( y, y  ) is a distance measure between y and y  . We can reuse the CKY decoder for cost-augmented inference when the distance decomposes into individual spans with some function c : ( y, y  ) = (cid:80) span ( i,j ) in y c ( i, j, y  ) . In our setting, we do not have access to the gold-standard y  , but instead we have a set of bracketings  y . The scoring s ( y ) is not meaningful since  y is not a complete tree, so we adopt structured ramp loss (Do et al., 2008; Gimpel and Smith, 2012) and define l = (cid:18) max y Y [ s ( y ) + ( y,  y )]  s ( y ) (cid:19) + (cid:18) s ( y )  max y Y [ s ( y )  ( y,  y )] (cid:19) = max y Y [ s ( y ) + ( y,  y )]  max y Y [ s ( y )  ( y,  y )] , using a combination of cost-augmented and cost-diminished inference. This loss function can be understood as a sum of a convex and a concave large margin loss (Collobert et al., 2006), canceling out the term for directly scoring the gold-standard tree. We consider two methods for incorporating the partial bracketings into the cost functions: c loose ( i, j,  y ) = 1 ( span ( i, j ) conflicts with  y ) c strict ( i, j,  y ) = 1 ( span ( i, j ) not in  y ) , where 1 is an indicator function. c loose is more lenient than c strict as it does not penalize spans that do not conflict with  y . Both cost definitions promote structures containing bracketings in  y . 7 In the supervised setting where  y refers to a fully-annotated tree y  without conflicting span boundaries, c strict is equal to c loose and the resulting ( y, y  ) cost functions both correspond to the Hamming distance between y and y  . (section 23 as the test set). QA-SRL contains 1 , 241 sentences drawn from the training split (sections 02-21) of the PTB. For Wikipedia, we use a sample of 332 , 079 sentences that are within 100 tokens long and contain multi-token internal hyperlinks. We fine-tune the pretrained BERT base features with a fixed number of mini-batch updates and report results based on five random runs for each setting. See Appendix B for detailed hyper-parameter settings and optimization procedures. Evaluation We follow the evaluation setting of Kim et al. (2019a). More specifically, we discard punctuation and trivial spans (single-word and full-sentence spans) during evaluation and report sentence-level F1 scores as our main metrics. ratios for each constituent type. Our distantly-supervised models trained on QA-SRL are competitive with the state-of-the-art unsupervised results. When comparing our models with Cao et al. (2020), we obtain higher recalls on most constituent types except for VPs. Interestingly, QA-SRL data prefers c strict , while c loose gives better F1 score on Wikipedia; this correlates with the fact that QA-SRL has more bracketings per sentence (Table 1). Finally, our Wikipedia data has a larger relative percentage of ADJP bracketings, which explains the higher ADJP recall of the models trained on Wikipedia, despite their lower overall recalls. Unsupervised Parsing Our distantly-supervised setting is similar to unsupervised in the sense that it does not require syntactic annotations. Typically, lack of annotations implies that unsupervised parsers induce grammar from a raw stream of lexical or part-of-speech tokens (Clark, 2001; Klein, 2005) along with carefully designed inductive biases on parameter priors (Liang et al., 2007; Wang and Blunsom, 2013), language universals (Naseem et al., 2010; Martnez Alonso et al., 2017), cross-linguistic (Snyder et al., 2009; Berg-Kirkpatrick and Klein, 2010; Cohen and Smith, 2009; Han et al., 2019) and cross-modal (Shi et al., 2019) signals, structural constraints (Gillenwater et al., 2010; Noji et al., 2016; Jin et al., 2018), etc. The models are usually generative and learn from (re)constructing sentences based on induced structures (Shen et al., 2018, 2019; Drozdov et al., 2019; Kim et al., 2019a,b). Alternatively, one may use reinforcement learning to induce syntactic structures using rewards defined by end tasks (Yogatama et al., 2017; Choi et al., 2018; Havrylov et al., 2019). Our method is related to learning from constituency tests (Cao et al., 2020), but our use of bracketing data permits discriminative parsing models, which focus directly on the syntactic objective. Learning from Partial Annotations Full syntactic annotations are costly to obtain, so the alternative solution of training parsers from partially-annotated data has attracted considerable research attention, especially within the context of active learning for dependency parsing (Sassano, 2005; Sassano and Kurohashi, 2010; Mirroshandel and Nasr, 2011; Flannery et al., 2011; Flannery and Mori, 2015; Li et al., 2016; Zhang et al., 2017) and grammar induction for constituency parsing (Pereira and Schabes, 1992; Hwa, 1999; Riezler et al., 2002). These works typically require expert annotators to generate gold-standard, though partial, annotations. In contrast, our work considers the setting and the challenge of learning from noisy bracketing data, which is more comparable to Spreyer and Kuhn (2009) and Spreyer et al. (2010) on transfer learning for dependency parsing. We argue that naturally-occurring bracketings are a rich resource for inducing syntactic structures. They reflect human judgment of what constitutes a phrase and what does not. More importantly, they require low annotation expertise and effort; for example, webpage hyperlinks can be extracted essentially for free. Empirically, our models trained on QA-SRL and Wikipedia bracketings achieve competitive results with the state of the art on unsupervised constituency parsing. Structural probes have been successful in extracting syntactic knowledge from frozen-weight pre-trained language models (e.g., Hewitt and Manning, 2019), but they still require direct syntactic supervision. Our work shows that it is also feasible to retrieve constituency trees from BERT-based models using distant supervision data. Our models are limited to the unlabeled setting, and we leave it to future work to automatically cluster the naturally-occurring bracketings and to induce phrase labels. Our work also points to potential applications in (semi-)supervised settings including active learning and domain adaptation (Joshi et al., 2018). Future work can also consider other naturally-occurring bracketings induced from sources such as speech production, reading behavior, etc. We thank the anonymous reviewers for their constructive reviews. This work was supported in part by a Bloomberg Data Science Ph.D. Fellowship to Tianze Shi and a gift from Bloomberg to Lillian Lee.
abstain abstain abstain abstain objective objective result abstain abstain abstain method abstain abstain abstain abstain other objective objective objective objective objective objective objective abstain abstain objective method abstain abstain result abstain abstain result abstain abstain objective other abstain abstain method abstain abstain abstain abstain abstain method abstain method method abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain method abstain method abstain abstain abstain other abstain method abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain result result abstain abstain abstain other other other abstain other other abstain abstain abstain abstain result abstain result method abstain abstain other other other