Randomized Deep Structured Prediction for Discourse-Level Processing (2021)

Abstract: Expressive text encoders such as RNNs and Transformer Networks have been at the center of NLP models in recent work. Most of the effort has focused on sentence-level tasks, capturing the dependencies between words in a single sentence, or pairs of sentences. However, certain tasks, such as argumentation mining, require accounting for longer texts and complicated structural dependencies between them. Deep structured prediction is a general framework to combine the complementary strengths of expressive neural encoders and structured inference for highly structured domains. Nevertheless, when the need arises to go beyond sentences, most work relies on combining the output scores of independently trained classifiers. One of the main reasons for this is that constrained inference comes at a high computational cost. In this paper, we explore the use of randomized inference to alleviate this concern and show that we can efficiently leverage deep structured prediction and expressive neural encoders for a set of tasks involving complicated argumentative structures.

## introduction many discourse-level nlp tasks require modeling complex interactions between multiple sentences, paragraphs or even documents. for example, analyzing opinions in online conversations @xcite requires modeling the dependencies between the opinions in individual posts, the disagreement between posts in long conversational threads and the overall view of users, given all their posts. learning in these settings is extremely challenging. it requires highly expressive models that can capture the claims made in each document, either by using a rich, manually crafted feature set, or by * contributed equally to this work as first authors using neural architectures to learn an expressive representation @xcite . in addition, reasoning about the interaction between these decisions is often computationally challenging, as it requires incorporating domain-specific constraints into the search procedure, making exact inference intractable. as a result, most current work relies on highly engineered solutions, which are difficult to adapt. instead of training structured predictors that model the interaction between decisions during training, they combine locally trained classifiers at test time @xcite . our goal in this paper is to study realistic settings, in which discourse-level problems can be learned efficiently when leveraging deep structured prediction, a framework for combining rich neural representation with an inference-layer, forcing consistency between them @xcite . these models were applied successfully to simpler nlp tagging tasks @xcite , in which inference is tractable. however, as shown in a recent argumentation mining work @xcite , their applicability to more complex learning tasks is not guaranteed. randomized inference algorithms have been proposed for structured nlp tasks, such as tagging and dependency parsing, in the context of linear models @xcite @xcite . this approach offers an efficient alternative to exact inference. instead of finding the optimal output state, the algorithm makes greedy updates to a randomly initialized (or locally initialized) output assignment state. our main contribution is to explore these ideas in the context of deep structured models composed of expressive text encoders, where theoretical guarantees are weak or nonexistent. moreover, we do this for discourse-level tasks involving a rich set of domain constraints. to do this, we consider two variations of this approach. in the first, the algorithm samples and traverses only legal states (i.e., consistent with the constraints imposed by domain knowledge). in the second, these restrictions are ignored and only applied at test time. adapting the sampling procedure to the specific constraints imposed by each domain is difficult, motivating the second approach as a generic alternative. we focus on two discourse-level tasks, stance prediction in discussion forums, described above, and parsing argumentation structures in essays @xcite . the latter consists of constructing an argumentation tree that represents the type-of, and relation-between, the arguments made in the essay. models for both tasks typically employ declarative inference for incorporating domain knowledge. our experiments are designed to quantify the trade-off between different modeling choices, both in terms of task performance and computational cost. we compare exact ilp models, approximate inference based on the popular ad 3 algorithm @xcite and the two randomized inference algorithms. our experiments show that in all cases, deep structured prediction outperforms traditional shallow approaches, structured learning outperforms inference over locally trained models, and generic randomized inference performs competitively to exact inference. ## related work using deep structured prediction for nlp has been studied in previous work, typically on traditional sentence-level tasks such as dependency parsing @xcite , transition systems @xcite , named entity recognition @xcite and sequence labeling systems @xcite . in most of these cases, inference is tractable. more recently, some efforts have started to look at incorporating deep structured prediction to discourse tasks such as argument mining @xcite , event and temporal relation extraction @xcite and discourse representation parsing @xcite . in all of these cases, constrained inference is formulated as an integer linear program and solved either using off-the-shelf optimizers or approximation algorithms like ad 3 (martins et al., 2015). randomized approximation has been introduced as an alternative to exact inference. @xcite suggest a simple randomized greedy inference algorithm and empirically demonstrate its effectiveness for dependency parsing and other traditional nlp tasks @xcite . the theoretical results in @xcite , based on the probably approximately correct bayes framework, characterize these findings by providing generalization bounds. more recently, @xcite extended the work of @xcite to structured prediction tasks with large structured outputs by leveraging local classifiers to find good starting solutions and improve the accuracy of search. all of these methods were evaluated on linear structured models. in this paper, we focus on two tasks: mining argumentative structures in essays and stance prediction in online debates. @xcite approach argumentative essays using an exhaustive set of hand-crafted features, linear local classifiers and ilp at test time. @xcite jointly learn to score multiple decisions while enforcing domain constraints. they explore structured svms and rnns, using the ad 3 inference algorithm @xcite . on the other hand, there are several works on predicting user stances in online debates. some approaches model the problem as a text classification task @xcite , while other approaches take a collective approach to model user behavior and interactions @xcite @xcite . in the latter case, inference procedures include maxcut, ilp and probabilistic soft logic @xcite . ## modeling we look at two challenging structured prediction problems that deal with long texts where dependencies span across different paragraphs, documents and authors. to deal with these setups, we define neural factor graphs @xmath0. in this section, we introduce the tasks in detail. ## learning we learn a joint neural model that uses inference during training to ensure consistency across all decisions. let ψ be a factor graph with potentials ψ @xmath1. let x i be the input vector to potential ψ i . let θ = {θ i } be a set of parameter vectors associated with a set of neural networks ρ = {ρ i }, and ρ i (x i , y i ; θ i ) is the score for potential ψ i resulting from a forward pass. here @xmath2: where c is a set of domain-specific constraints defined over the factor graph ψ, and x c , y c indicates inputs and variables relevant to the constraints. in this work, we experiment with different algorithms to obtain or approximate the arg max, including the randomized procedures outlined in section 5. to learn θ, we use the structured hinge loss l(x, y, ŷ; θ) defined as: where ∆(y, ŷ) is the hamming loss. to introduce the hamming loss into the objective, we perform loss augmented inference. the pseudo-code for the structured learning procedure can be observed in algorithm 1. we implemented our models using drail (pacheco and goldwasser, 2020), a declarative deep structured prediction framework built on pytorch, and extended it to support our randomized inference procedures foot_0 . ## randomized inference in this section, we describe the randomized inference procedure used for each task. we define the for each ψ ∈ g train do 7: ## experiments we learn our models using four different inference procedures: (1) ilp defines the inference problem as an integer linear program and uses the gurobi solver 2 to perform exact inference, (2) ad 3 /ilp translates the ilp program into an ad 3 instance to perform approximate inference, (3) rand-c uses the randomized method with domain constraints, and (4) rand uses the randomized method without domain constraints. note that we always use exact inference to evaluate on both the development and test sets. for completeness, we add an entry ad 3 where we use ad 3 for both training and testing. when using ilp or ad 3 , the domain constraints are expressed declaratively. ## summary we studied the effectiveness of randomized inference for deep structured prediction and obtained positive results for two challenging discourse-level tasks. we showed that, in practice, we can train complex structured models, using expressive neural architectures, and get competitive results at a lower computational cost. moreover, we saw that combining expressive representations and inference is a promising direction for modeling discourse-level structures. future directions include expanding the discussion to other tasks involving more complex structures, as well as exploring shared representations across different sub-tasks.