Perturbation Based Learning for Structured NLP Tasks with Application to Dependency Parsing

Perturbation Based Learning for Structured NLP Tasks with Application to Dependency Parsing Amichay Doitch∗ Ram Yazdi∗ Tamir Hazan Roi Reichart Faculty of Industrial Engineering and Management, Technion, IIT {amichay.d|ramyazdi1012|tamir.hazan|roireichart}@gmail.com Abstract The best solution of structured prediction mod- els in NLP is often inaccurate because of limited expressive power of the model or to non-exact parameter estimation. One way to mitigate this problem is sampling candidate solutions from the model’s solution space, reasoning that effective exploration of this space should yield high-quality solutions. Unfortunately, sampling is often computation- ally hard and many works hence back-off to sub-optimal strategies, such as extraction of the best scoring solutions of the model, which are not as diverse as sampled solutions. In this paper we propose a perturbation-based approach where sampling from a probabilis- tic model is computationally efficient. We present a learning algorithm for the variance of the perturbations, and empirically demon- strate its importance. Moreover, while finding the argmax in our model is intractable, we propose an efficient and effective approxima- tion. We apply our framework to cross-lingual dependency parsing across 72 corpora from 42 languages and to lightly supervised depen- dency parsing across 13 corpora from 12 lan- guages, and demonstrate strong results in terms of both the quality of the entire solution list and of the final solution.1 1 Introduction Structured prediction problems are ubiquitous in Natural Language Processing (NLP) (Smith, 2011). Although in most cases models for such problems are designed to predict the highest quality structure of the input example (e.g., a sentence or a document), in many cases a diverse ∗Both authors contributed equally to this work. 1Our code is at: https://github.com/ramyazdi/ perturbations. list of meaningful structures is of fundamental importance. This can stem from several reasons. First, it can be a defining property of the task. For exam- ple, in extractive summarization (Nenkova and McKeown, 2011) good summaries are those that consist of a high quality and diverse list of sen- tences extracted from the text. In other cases the members of the solution list are exploited when solving an end goal application. For example, dependency forests were used in order to improve machine translation (Tu et al., 2010; Ma et al., 2018) and sentiment analysis (Tu et al., 2012). In yet other cases it is a first step towards learning a high quality structure that cannot be learned by the model through standard argmax inference.For example, in the well-studied rerank- ing setup (Collins, 2002; Collins and Koo, 2005; Charniak and Johnson, 2005; Son et al., 2012; Kalchbrenner and Blunsom, 2013), a K-best list of solutions is first extracted from a baseline learner, which typically has a limited feature space, and is then transferred to another feature-rich model that chooses the best solution from this list. Other examples include bagging (Breiman, 1996; Sun and Wan, 2013) and boosting (Bawden and Crabb´e, 2016) as well as other ensemble methods (Surdeanu and Manning, 2010; T¨ackstr¨om et al., 2013; Kuncoro et al., 2016) that are often applied when the data …

Content truncated to 500 words