Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing (2024)

Abstract: We address unsupervised discontinuous constituency parsing, where we observe a high variance in the performance of the only previous model in the literature. We propose to build an ensemble of different runs of the existing discontinuous parser by averaging the predicted trees, to stabilize and boost performance. To begin with, we provide comprehensive computational complexity analysis (in terms of P and NP-complete) for tree averaging under different setups of binarity and continuity. We then develop an efficient exact algorithm to tackle the task, which runs in a reasonable time for all samples in our experiments. Results on three datasets show our method outperforms all baselines in all metrics; we also provide in-depth analyses of our approach.

## introduction unsupervised parsing has been attracting the interest of researchers over decades @xcite @xcite @xcite . compared with supervised methods, unsupervised parsing has its own importance: (1) it reduces the reliance on linguistically annotated data, and is beneficial for low-resource languages and domains @xcite . (2) discovering language structures in an unsupervised way helps to verify theories in linguistics @xcite and cognitive science @xcite . (3) unsupervised parsing methods are applicable to other types of streaming data, such as motion-sensor signals @xcite . a constituency tree, a hierarchy of words and phrases shown in figure 1 , is an important parse structure @xcite . researchers have proposed various approaches to address unsupervised constituency parsing, such as latent-variable methods @xcite @xcite 1 code available at https://github.com/manga-uofa/ taa4eudcp (c) a discontinuous parse structure in german. interesting structures (binarity and fan-out) are illustrated. @xcite and rule-based systems @xcite . in our previous work @xcite , we reveal that different unsupervised parsers have low correlations with each other, and further propose an ensemble approach based on dynamic programming to boost performance. one limitation of most existing studies is that they only address continuous constituency parsing, that is, a constituent can only be a continuous span of words (figure 1a ). however, a constituent may be discontinuous @xcite . 2 in figure 1b , for example, it is linguistically arguable that wake and up form a constituent in the sentence "wake your friend up." such discontinuous constituents are more common in certain languages (such as german shown in figure 1c ) than in english @xcite ), but they have been less tackled in the literature. very recently, @xcite proposed an unsupervised parsing method based on a mildly context-sensitive grammar @xcite that allows discontinuous parse structures, known as discontinuous trees @xcite . as an early attempt, their performance appears to be low, and we find that their approach is noisy and exhibits low correlation in different runs with random seeds. in this work, we propose an ensemble method to discontinuous constituency parsing by tree averaging, following our previous work @xcite , in which we address the ensemble of continuous constituency parsing by cyk-like dynamic programming @xcite . however, the previous approach is not directly applicable to this paper because of the discontinuous structures in our setup. consequently, the seemingly small change in the setting (continuous vs. discontinuous) leads to a completely different landscape of problems, requiring advanced algorithmic analysis and development. specifically, we first analyze the computational complexity of tree averaging under different setups, such as binarity and continuity. we show certain problems are in the p category, whereas general tree averaging is np-complete. then, we develop an algorithm utilizing the meet-in-the-middle technique @xcite with effective pruning strategies, making our search practical despite its exponential time complexity. our experiments on german and dutch show that our approach largely outperforms previous work in terms of continuous, discontinuous, and overall f 1 scores. to the best of our knowledge, our algorithm is the first that can handle non-binary constituents in the setting of unsupervised constituency parsing. to sum up, our main contributions conclude: (1) proposing an ensemble approach to unsupervised discontinuous constituency parsing, (2) theoretically analyzing the computational complexity of various tree-averaging settings, and (3) conducting experiments on benchmark datasets to verify the effectiveness of our approach. ## related work constituency parsing carries a long history in natural language processing research @xcite @xcite . different setups of the task have been introduced and explored, including supervised and unsupervised, continuous and discontinuous constituency parsing @xcite @xcite @xcite @xcite @xcite . in the unsupervised setup, researchers typically define a joint distribution over the parse structure and an observable variable, e.g., the sentence itself, and maximize the observable variable's likelihood through marginalization @xcite . to the best of our knowledge, previous unsupervised parsing studies are all restricted to binary structures to squeeze the marginalization space, and we are the first to address non-binary unsupervised parsing and show non-binarity is beneficial to parsing performance. ensemble methods strategically combine multiple models to improve performance, rooted in the bagging concept where different data portions are used to train multiple models @xcite . to build an ensemble, straightforward methods include averaging and voting @xcite . for outputs with internal structures, minimum bayes risk decoding (mbr; bickel and doksum, 2015) can be used to build an ensemble, where the vote is the negative risk in mbr. however, existing mbr approaches are mostly selective, where the output is selected from a candidate set @xcite @xcite . @xcite formulate mbr for supervised constituency parsing and propose to search for the global optimum decoding when the risk allows for dynamic programming. @xcite extend the idea to non-projective dependency parsing. in our previous work @xcite , we formally introduce generative mbr and develop an algorithm that searches for a binary continuous tree. this paper extends our previous work and searches in the space of discontinuous constituency trees, leading to significant algorithmic design and theoretical analysis. ## conclusion in this work, we address ensemble-based unsupervised discontinuous constituency parsing by tree averaging, where we provide comprehensive complexity analysis and develop an efficient search algorithm to obtain the average tree. our experiments on dutch and german demonstrate the effectiveness of our ensemble method. to the best of our knowledge, we are also the first to address, and show the importance of, non-binary structures in unsupervised constituency parsing.