Sample Selection for Statistical Parsers: Cognitively Driven Algorithms and Evaluation Measures

Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL), pages 3–11, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Sample Selection for Statistical Parsers: Cognitively Driven Algorithms and Evaluation Measures Roi Reichart ICNC Hebrew University of Jerusalem roiri@cs.huji.ac.il Ari Rappoport Institute of computer science Hebrew University of Jerusalem arir@cs.huji.ac.il Abstract Creating large amounts of manually annotated training data for statistical parsers imposes heavy cognitive load on the human annota- tor and is thus costly and error prone. is hence of high importance to decrease theIt human efforts involved in creating training data without harming parser performance. For constituency parsers, these efforts are tradi- tionally evaluated using the total number of constituents (TC) measure, assuming uniform cost for each annotated item. In this paper, we introduce novel measures that quantify aspects of the cognitive efforts of the human annota- tor that are not reflected by the TC measure, and show that they are well established in the psycholinguistic literature. We present a novel parameter based sample selection approach for creating good samples in terms of these measures. We describe methods for global op- timisation of lexical parameters of the sam- ple based on a novel optimisation problem, the constrained multiset multicover problem, and for cluster-based sampling according to syn- tactic parameters. Our methods outperform previously suggested methods in terms of the new measures, while maintaining similar TC performance. 1 Introduction State of the art statistical parsers require large amounts of manually annotated data to achieve good performance. Creating such data imposes heavy cognitive load on the human annotator and is thus costly and error prone. Statistical parsers are ma- jor components in NLP applications such as QA (Kwok et al., 2001), MT (Marcu et al., 2006) and SRL (Toutanova et al., 2005). These often oper- ate over the highly variable Web, which consists of texts written in many languages and genres. Since the performance of parsers markedly degrades when training and test data come from different domains (Lease and Charniak, 2005), large amounts of train- ing data from each domain are required for using them effectively. Thus, decreasing the human efforts involved in creating training data for parsers without harming their performance is of high importance. In this paper we address this problem through sample selection: given a parsing algorithm and a large pool of unannotated sentences S, select a sub- set S1 ⊂ S for human annotation such that the hu- man efforts in annotating S1 are minimized while the parser performance when trained with this sam- ple is maximized. Previous works addressing training sample size vs. parser performance for constituency parsers (Section 2) evaluated training sample size using the total number of constituents (TC). Sentences differ in length and therefore in annotation efforts, and it has been argued (see, e.g, (Hwa, 2004)) that TC re- flects the number of decisions the human annotator makes when syntactically annotating the sample, as- suming uniform cost for each decision. In this paper we posit that important aspects of the …

Content truncated to 500 words