Adapting Unsupervised Syntactic Parsing Methodology for Discourse Dependency Parsing (2021)

Abstract: One of the main bottlenecks in developing discourse dependency parsers is the lack of annotated training data. A potential solution is to utilize abundant unlabeled data by using unsupervised techniques, but there is so far little research in unsupervised discourse dependency parsing. Fortunately, unsupervised syntactic dependency parsing has been studied by decades, which could potentially be adapted for discourse parsing. In this paper, we propose a simple yet effective method to adapt unsupervised syntactic dependency parsing methodology for unsupervised discourse dependency parsing. We apply the method to adapt two state-of-the-art unsupervised syntactic dependency parsing methods. Experimental results demonstrate that our adaptation is effective. Moreover, we extend the adapted methods to the semi-supervised and supervised setting and surprisingly, we find that they outperform previous methods specially designed for supervised discourse parsing. Further analysis shows our adaptations result in superiority not only in parsing accuracy but also in time and space efficiency.

## introduction discourse parsing, aiming to find how the text spans in a document relate to each other, benefits various down-stream tasks, such as machine translation evaluation @xcite , summarization @xcite , sentiment analysis @xcite and automated essay scoring @xcite . researchers have made impressive progress on discourse parsing from the constituency perspective, which presents discourse structures as constituency trees @xcite @xcite . however, as demonstrated by @xcite , discourse structure can also be formulated as a dependency structure. besides that, there might exist ambiguous parsing in terms of the constituency perspective @xcite . all of these suggest that dependency discourse parsing is a different promising approach for discourse parsing. one of the main bottlenecks in developing discourse dependency parsing methods is the lack of annotated training data since the labeling effort is labor-intensive and time-consuming, and needs well-trained experts with linguistic knowledge @xcite . this problem can be tackled by employing unsupervised and semisupervised methods that can utilize unlabeled data. however, while unsupervised methodology has been studied for decades in syntactic dependency parsing, there is little attention paid to the counterpart in discourse dependency parsing. considering the similarity between syntactic and discourse dependency parsing, it is natural to suggest such methodology can be adapted from the former to the latter. in this paper, we propose a simple yet effective adaptation method that can be readily applied to different unsupervised syntactic dependency parsing approaches. adaptation from syntactic dependency parsing to discourse dependency parsing has two challenges. first, unlike syntactic parsing which has a finite vocabulary, in discourse parsing, the number of elementary discourse units (edus) is unlimited. this makes it difficult if not impossible to directly apply syntactic approaches requiring enumeration of words or word categories to discourse parsing. second, in a discourse dependency parse tree, the dependencies within a sentence or a paragraph often form a complete subtree. there is no correspondence to this constraint in syntactic parsing approaches. to address these two chal-lenges, we cluster the edus to produce clusters resembling part-of-speech (pos) tags in syntactic parsing and we introduce the hierarchical eisner algorithm that finds the optimal parse tree conforming to the constraint. we applied our adaptation method to two stateof-the-art unsupervised syntactic dependency parsing models: neural conditional random field autoencoder (ncrfae, @xcite tu (2020) 2019 ). in our experiments, the adapted models performs better than the baseline on both rst discourse treebank (rst-dt, @xcite ) and scidtb @xcite in the unsupervised setting. when we extend the two models to the semi-supervised and supervised setting, we find they can outperform previous methods specially designed for supervised discourse parsing. further analysis indicates that the hierarchical eisner algorithm shows superiority not only in parsing accuracy but also in time and space efficiency. its empirical time and space complexity is close to o(n 2 ) with n being the number of edus, while the unconstrained algorithm adopted by most previous work has a complexity of o(n 3 ). the code and trained models can be found at: https://github. com/ehaschia/discoursedependencyparsing . ## related work unsupervised syntactic dependency parsing unsupervised syntactic dependency parsing is the task to find syntactic dependency relations between words in sentences without guidance from annotations. the most popular approaches to this task are dependency model with valences (dmv, @xcite ), a generative model learning the grammar from pos tags for dependency predictions, and its extensions. @xcite employ neural networks to capture the similarities between pos tags ignored by vanilla dmv and @xcite further amend the former with discriminative information obtained from an additional encoding network. besides, there are also some discriminative approaches modeling the conditional probability or score of the dependency tree given the sentence, such as the crf autoencoder method proposed by @xcite . ## adaptation we propose an adaptation method that can be readily integrated with different unsupervised syntactic dependency parsing approaches. first, we cluster the element discourse units (edu) to produce clusters resembling pos tags or words used in syntactic parsing. this is necessary because many unsupervised syntactic parsers require enumeration of words or word categories, typically in modeling multinomial distributions as we shall see in section 4. while edus, which are sequences of words, cannot be enumerated, its clusters can. during parsing, we apply the hierarchical eisner algorithm used for parse tree, a novel modified ver- figure 1: [the financial account-ing standards board's coming rule on disclosure] e1 [involving financial instruments] e2 [will be effective for financial statements with fiscal years] e3 [ending after june 15, 1990.] e4 [the date was misstated in friday's edition .] e5 [(see: "fasb plans rule on financial risk of instruments"] e6 [-wsj oct. 27, 1989)] e7 ## analysis 6.1 eisner vs. hierarchical eisner in the left part of figure 4 we show the curves of the time cost of the hierarchical and traditional eisner algorithms against the rst-dt document length. clusters 10 30 50 100 uas 52.7 53.9 54.6 53.5 4 demonstrates a similar phenomenon where we illustrate the memory usage of the hierarchical and traditional eisner algorithms against the training document length in the same computing environment. from the curves of these two figures we can conclude that our hierarchical eisner algorithm has advantage over the traditional one in both time and space efficiencies. besides the superiority in computational efficiency, our experiments also indicate that our hierarchical eisner algorithm can achieve better performance than the traditional one. with other conditions fixed, the uas produced by hierarchical eisner is 79.1 in the task of supervised discourse parsing on the scidtb dataset while the corresponding result of the eisner algorithm is 78.6. ## conclusion in this paper, we propose a method to adapt unsupervised syntactic parsing methods for discourse dependency parsing. first, we cluster the element discourse units (edu) to produce clusters resembling pos tags. second, we modify the eisner algorithm used for finding the optimal parse tree with hierarchical constraint. we apply the adaptations to two unsupervised syntactic dependency parsing methods. experimental results show that our method successfully adapts the two models for discourse dependency parsing, which demonstrate advantages in both parsing accuracy and running efficiency. a experimental details for our ncrfae and v-dndmv