Unsupervised Parsing by Searching for Frequent Word Sequences among Sentences with Equivalent Predicate-Argument Structures (2024)

Abstract: Unsupervised constituency parsing focuses on identifying word sequences that form a syntactic unit (i.e., constituents) in target sentences. Linguists identify the constituent by evaluating a set of Predicate-Argument Structure (PAS) equivalent sentences where we find the constituent appears more frequently than non-constituents (i.e., the constituent corresponds to a frequent word sequence within the sentence set). However, such frequency information is unavailable in previous parsing methods that identify the constituent by observing sentences with diverse PAS. In this study, we empirically show that constituents correspond to frequent word sequences in the PAS-equivalent sentence set. We propose a frequency-based parser, span-overlap, that (1) computes the span-overlap score as the word sequence’s frequency in the PAS-equivalent sentence set and (2) identifies the constituent structure by finding a constituent tree with the maximum span-overlap score. The parser achieves state-of-the-art level parsing accuracy, outperforming existing unsupervised parsers in eight out of ten languages. Additionally, we discover a multilingual phenomenon: participant-denoting constituents tend to have higher span-overlap scores than equal-length event-denoting constituents, meaning that the former tend to appear more frequently in the PAS-equivalent sentence set than the latter. The phenomenon indicates a statistical difference between the two constituent types, laying the foundation for future labeled unsupervised parsing research.

## introduction unsupervised constituency parsing focuses on identifying the constituent structure for target sentences. the constituent structure consists of a set of we release the code and data at https://github.com/ junjiechen-chris/acl24-spanoverlap syntactically self-contained word sequences, commonly known as constituents. in addition to being syntactic units, those constituents encode semantic units in the sentence's semantic structure @xcite . among all possible word sequences that can arise in natural language, the constituent is one of the few word sequences that can describe the semantic unit. as a result, we would have a higher chance of repeatedly observing the constituent than random word sequences given the semantic unit. in other words, we can observe the constituent as a frequent word sequence among semantically equivalent sentences. we refer to the frequent word sequence as a word sequence pattern. in this paper, we empirically show a hypothesis: constituents correspond to frequent word sequences in the set of sentences with equivalent predicate-argument structures (pas). pas ab-penn treebank results were released after the market closed. markets stopped trading in many securities. mr. bandow is a cato institute fellow. ## background unsupervised constituency parsers seek to identify unlabeled constituents for any given sentence. a constituent in a sentence w := (w[1], ..., w[n]) is a consecutive word sequence w i,j := (w[i], ..., w[j]) that functions as an independent unit in the structure. the word sequence can be represented as a two-tuple (i, j), referred to as a span. we measure the parsing accuracy by the f1 score between the set of predicted spans and the set of gold spans @xcite . unsupervised parsers make predictions by (1) evaluating a span score for each word sequence and (2) finding a tree optimizing the span score. grammar-based unsupervised parsers @xcite ) compute the span score as the posterior span probability p g ((i, j)|w) with respect to a probabilistic grammar g (i.e., how likely the grammar selects (i, j) as a constituent). the grammar-based parsers predict constituents by maximizing the span score, seeking to maximize the probability of the prediction containing constituents. language model-based parsers @xcite @xcite compute the span score by whether the language model reacts to syntactic transformations involving the span. the language model-based parsers predict constituents by minimizing the span score, searching for constituents most independent of the remainder of the sentence. the language model-based unsupervised parsing methods have attracted much attention lately due to the language model's applicability in various syntactic @xcite and semantic tasks @xcite . given a word sequence w i,j , the method evaluates the span score as the distance d between w (the original sentence) and f (w, (i, j)) (the transformed sentence designed to test the constituency of w i,j ), as shown in equation 1. cao et al. (2020 ) measures the distance by the change in the acceptability between w and f (w, (i, j)) using an external acceptability model trained with synthetic data. @xcite and @xcite measure the difference by the distance in language model embeddings between w and f (w, (i, j)). score(w, (i, j)) := d(w, f (w, (i, j))) (1) recent advances in large language models (llm) have led to a surge in the application of llm-enhanced data to natural language processing systems @xcite @xcite . given an instruction (typically in the form of prompts), the llm iteratively generates its answer based on the instruction and partially generated answers. recent studies @xcite point out that state-of-theart llms can follow difficult instructions and generate the correct answer with over 90% accuracy. this excellent instruction-following capability enables us to sample pas-equivalent sentences from the llm. ## related works grammar-based unsupervised parsers @xcite @xcite learn probabilistic grammar by maximizing the likelihood of sentences observed in a corpus. however, these sentences have diverse pas to the degree that constituent word sequences can only be observed a limited number of times. the limited observation provides insufficient positive evidence on whether a word sequence is a constituent through the sequence's frequency. also, the grammar has to reject non-constituent but frequent word sequences tied to certain expressions. for example, the word sequence "it is" is a non-constituent but frequent word sequence in sentences like "(it (is (a book)))". the lack of positive evidence and the abundance of false-positive evidence make up the main challenges in unsupervised constituency parsing. the two issues likely contribute to the low performance of the grammar-based method in non-english languages (see previous language model-based methods conduct constituency tests by applying handcrafted templates to word sequences. however, different languages implement the syntactic transformation differently, requiring templates tailored to each language. to circumvent the problem, cao et al. (2020) limit the scope of languages to english, which results in an english-only parser. @xcite and li and lu (2023) limit the transformation to movement and standalone tests only, which limits their parser's performance. by leveraging llms for performing the transformation, our span-overlap method can cover a diverse set of transformations while being applicable to many languages. furthermore, the previous method has to perform the constituency test for every word sequence, incurring o(n 2 ) language model evaluations for sentences with n words. our method only generates a few dozen acceptable pas-equivalent sentences for each target sentence, incurring only o(1) evaluations of the llm. the low complexity allows for more efficient language model-based parsing. for example, our method takes 14 minutes to parse the development set of penn treebank @xcite whereas li and lu (2023)'s method takes about an hour. researchers have long pointed out that language models capture shallow syntax, such as subjectverb agreements @xcite and phrase segmentations @xcite . however, the shallow syntax covers only a small subset of information that hierarchical constituent structures provide. for example, knowing "a beautiful new york city" as an np does not provide any information about the np's internal structure (i.e., "(a (beautiful ((new york) city)))"). language model-based methods utilize the language model's ability to identify shallow syntax for reconstructing the hierarchical constituent structure. our span-overlap method represents an improvement over previous language model-based methods, as discussed in the above paragraph. as we will see in section 5, both our span-overlap parser and the baseline language model-based parser outperform the gpt-3.5 parser in all languages. this result indicates that llm alone cannot recover the full constituent structure, prompting further research on language model-based unsupervised parsing. ## method this section introduces the proposed span-overlap method (figure 2 ). given a target sentence w, the span-overlap method performs parsing in four steps: (1) generating a set of sentences @xmath0, s 2 , ...} where all s k are pas-equivalent to w; secondly, we normalize words in w and s @xmath1. we perform stemming and contraction normalization in this step. the stemming removes the inflectional suffixes in a word (e.g., @xmath2. the contraction normalization expands one contracted word to two separate words (e.g., didn'@xmath3, aligning with the treebank's tokenization. thirdly, we compute the span-overlap score as the frequency of the normalized w i,j within the normalized sentence set s (equation 2 ). the spanoverlap score is an exact matching score, requiring w i,j to be a substring of sentences s @xmath4. we also present results in appendix a.1 for a span-overlap variant using fuzzy matching scores. lastly, we decode the constituent structure by finding a tree with maximum span-overlap scores. we apply the viterbi algorithm @xcite for this purpose. ## conclusion in this paper, we approached the unsupervised constituency parsing problem by exploiting word sequence frequency information revealed in a set of pas-equivalent sentences. firstly, we empirically verified a hypothesis: constituents correspond to frequent word sequences in the pasequivalent sentence set. we proposed a frequencybased method span-overlap that computes the spanoverlap score as the word sequence's frequency in the pas-equivalent sentence set. the span-overlap parser outperformed state-of-the-art parsers in eight out of ten languages evaluated and significantly outperformed the gpt-3.5 parser in all languages. the span-overlap score can effectively separate constituents from non-constituents, especially for long constituents. these results highlight the effectiveness and applicability of the frequency information to unsupervised parsing. additionally, our study uncovers a multilingual phenomenon: participantdenoting constituents tend to have higher spanoverlap scores than equal-length event-denoting constituents, meaning that the former tend to appear more frequently in the pas-equivalent sentence set than the latter. the phenomenon indicates a statistical difference between the two constituent types, laying the foundation for future labeled unsupervised parsing research. finally, our ablation analysis shows a significant improvement by aggregating multiple pas-preserving transformations, indicating the necessity of the aggregation in comprehensively exposing the constituent structure.