Unsupervised Discourse Constituency Parsing Using V iterbi EM (2020)

Abstract: In this paper, we introduce an unsupervised discourse constituency parsing algorithm. We use Viterbi EM with a margin-based criterion to train a span-based discourse parser in an unsupervised manner. We also propose initialization methods for Viterbi training of discourse constituents based on our prior knowledge of text structures. Experimental results demonstrate that our unsupervised parser achieves comparable or even superior performance to fully supervised parsers. We also investigate discourse constituents that are learned by our method.

## introduction natural language text is generally coherent @xcite and can be analyzed as discourse structures, which formally describe how text is coherently organized. in discourse structure, linguistic units (e.g., clauses, sentences, or larger textual spans) are connected together semantically and pragmatically, and no unit is independent nor isolated. discourse parsing aims to uncover discourse structures automatically for given text and has been proven to be useful in various nlp applications, such as document summarization @xcite @xcite , sentiment analysis @xcite , and automated essay scoring @xcite . despite the promising progress achieved in recent decades @xcite @xcite @xcite @xcite , discourse parsing still remains a significant challenge. the difficulty is due in part to shortage and low reliability of hand-annotated discourse structures. to develop a better-generalized parser, existing algorithms require a larger amounts of training data. however, manually annotating discourse structures is expensive, time-consuming, and sometimes highly ambiguous @xcite . one possible solution to these problems is grammar induction (or unsupervised syntactic parsing) algorithms for discourse parsing. however, existing studies on unsupervised parsing mainly focus on sentence structures, such as phrase structures @xcite @xcite or dependency structures @xcite @xcite , though text-level structural regularities can also exist beyond the scope of a single sentence. for instance, in order to convey information to readers as intended, a writer should arrange utterances in a coherent order. we tackle these problems by introducing unsupervised discourse parsing, which induces discourse structures for given text without relying on human-annotated discourse structures. based on rhetorical structure theory (rst) @xcite , which is one of the most widely accepted theories of discourse structure, we assume that coherent text can be represented as tree structures, such as the one in figure 1 . the leaf nodes correspond to non-overlapping clauselevel text spans called elementary discourse units @xcite . consecutive text spans are combined to each other recursively in a bottom-up manner to form larger text spans (represented by internal nodes) up to a global document span. these text spans are called discourse constituents. the internal nodes are labeled with both nuclearity statuses (e.g., nucleus-satellite or ns) and rhetorical figure 1 : an example of rst-based discourse constituent structure we assume in this paper. leaf nodes x i correspond to non-overlapping clause-level text segments, and internal nodes consists of three complementary elements: discourse constituents x i:j , discourse nuclearities (e.g., ns), and discourse relations (e.g., elaboration). in this paper, we especially focus on unsupervised induction of an unlabeled discourse constituent structure (i.e., a set of unlabeled discourse constituent spans) given a sequence of edus, which corresponds to the first tree-building step in conventional rst parsing. such constituent structures provide hierarchical information of input text, which is useful in downstream tasks @xcite . for instance, a constituent structure [x [y z]] indicates that text span y is preferentially combined with z (rather than x) to form a constituent span, and then the text span [y z] is connected with x. in other words, this structure implies that [x y] is a distituent span and requires z to become a constituent span. our challenge is to find such discourse-level constituentness from edu sequences. the core hypothesis of this paper is that discourse tree structures and syntactic tree structures share the same (or similar) constituent properties at a metalevel, and thus, learning algorithms developed for grammar inductions are transferable to unsupervised discourse constituency parsing by proper modifications. actually, rst structures can be formulated in a similar way as phrase structures in the penn treebank, though there are a few differences: the leaf nodes are not words but edus (e.g., clauses), and the internal nodes do not contain phrase labels but hold nuclearity statuses and rhetorical relations. the expectation-maximization (em) algorithm @xcite has been the dominating unsupervised learning algorithm for grammar induction. based on our hypothesis and this fact, we develop a span-based discourse parser (in an unsupervised manner) by using viterbi em (or ''hard'' em) @xcite @xcite @xcite with a margin-based criterion @xcite . 1 unlike the classic em algorithm using inside-outside re-estimation @xcite , viterbi em allows us to avoid explicitly counting discourse constituent patterns, which are generally too sparse to estimate reliable scores of text spans. the other technical contribution is to present effective initialization methods for viterbi training of discourse constituents. we introduce initial-tree sampling methods based on our prior knowledge of document structures. we show that proper initialization is crucial in this task, as observed in grammar induction @xcite . on the rst discourse treebank (rst-dt) @xcite , we compared our parse trees with manually annotated ones. we observed that our method achieves a micro f 1 score of 68.6% (84.6%) in the (corrected) rst-parseval @xcite , which is comparable with or even superior to fully supervised parsers. we also investigated the discourse constituents that can or cannot be learned well by our method. the rest of this paper is organized as follows: section 2 introduces the related work. section 3 gives the details of our parsing model and training algorithm. section 4 describes the experimental setting and section 5 discusses the experimental results. conclusions are given in section 6. ## related work the earliest studies that use em in unsupervised parsing are @xcite and @xcite , which attempted to induce probabilistic context-free grammars (pcfg) and probabilistic dependency grammars using the classic inside-outside algorithm @xcite . @xcite perform a weakened version of constituent tests @xcite by the constituent-context model (ccm), which, unlike a pcfg, describes whether a contiguous text span (such as dt jj nn) is a constituent or a distituent. the ccm uses em to learn constituenthood over part-of-speech (pos) tags and for the first time outperformed the strong right-branching baseline in unsupervised constituency parsing. @xcite proposed the dependency model with valence (dmv), which is a head automata model @xcite for unsupervised dependency parsing over pos tags and also relies on em. these two models have been extended in various works for further improvements @xcite @xcite . in general, these methods use the inside-outside (dynamic programming) re-estimation @xcite in the e step. however, @xcite showed that viterbi training @xcite , which uses only the best-scoring tree to count the grammatical patterns, is not only computationally more efficient but also empirically more accurate in longer sentences. these properties are, thus, suitable for ''document-level'' grammar induction, where the document length (i.e., the number of edus) tends to be long. 2 in addition, as ex-plained later in section 3, we incorporate viterbi em with a margin-based criterion @xcite ; this allows us to avoid explicitly counting each possible discourse constituent pattern symbolically, which is generally too sparse and appears only once. prior studies @xcite @xcite have shown that initialization or linguistic knowledge plays an important role in em-based grammar induction. @xcite demonstrated that properly initialized dmv achieves improvements in attachment accuracies by 20 ∼ 40 points (i.e., 21.3% → 64.3%), compared with the uniform initialization. naseem et al. (2010) also found that controlling the learning process with the prior (universal) linguistic knowledge improves the parsing performance of dmv. these studies usually rely on insights on syntactic structures. in this paper, we explore discourse-level prior knowledge for effective initialization of the viterbi training of discourse constituency parsers. our method also relies on recent work on rst parsing. in particular, one of the initialization methods in our em training (in section 3.3 (i)) is inspired by the inter-sentential and multisentential approach used in rst parsing @xcite @xcite . we also follow prior studies @xcite and utilize syntactic information, i.e., dependency heads, which contributes to further performance gains in our method. the most similar work to that presented here is @xcite , who propose unsupervised rst parsing algorithms in parallel with our work. their method builds an unlabeled discourse tree by using the cky dynamic programming algorithm. the tree-merging (splitting) scores in cky are defined as similarity (dissimilarity) between adjacent text spans. the similarity scores are calculated based on distributed representations using pre-trained embeddings. however, similarity between adjacent elements are not always good indicators of constituentness. consider tag sequences ''vbd in'' and ''in nn''. the former is an example of a distituent sequence, whereas the latter is a constituent. ''vbd'', ''in'', and ''nn'' may have similar distributed representations because these tags cooccur frequently in corpora. this implies that it is difficult to distinguish constituents and distituents if we use only similarity (dissimilarity) measures. in this paper, we aim to mitigate this issue by introducing parameterized models to learn discourse constituentness. ## methodology in this section, we first describe the parsing model we develop. next, we explain how to train the model in an unsupervised manner by using viterbi em. finally, we present the initialization methods we use for further improvements. ## results and discussion in this section we report the results of the experiments and discuss them. we first discuss the comparison results of our method with baselines and the fully supervised rst parsers, including the results published in literature (section 5.1). we then investigate the impact of initialization methods (section 5.2). finally, we provide our analysis on discourse constituents induced by our method (section 5.3). ## conclusion in this paper, we introduced an unsupervised discourse constituency parsing algorithm that uses viterbi em with a margin-based criterion to train a span-based neural parser. we also introduced initialization methods for the viterbi training of discourse constituents. we observed that our unsupervised parser achieves comparable or even superior performance to the baselines and fully supervised parsers. we also found that learned discourse constituents depend strongly on initialization used in viterbi em, and it is necessary to explore other initialization techniques to capture more diverse discourse phenomena. we have two limitations in this study. first, this work focuses only on unlabeled discourse constituent structures. although such hierarchical information is useful in downstream applications @xcite , both nuclearity statuses and rhetorical relations are also necessary for a more complete rst analysis. second, our study uses only english documents for evaluation. however, different languages may have different structural regularities. hence, it would be interesting to investigate whether the initialization methods are effective in different languages, which we believe gives suggestions on discourse-level universals. we leave these issues as a future work.