Analysis of Stopping Active Learning based on Stabilizing Predictions

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 10–19, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics Analysis of Stopping Active Learning based on Stabilizing Predictions Michael Bloodgood Center for Advanced Study of Language University of Maryland College Park, MD 20740 meb@umd.edu John Grothendieck Raytheon BBN Technologies 9861 Broken Land Parkway, Suite 400 Columbia, MD 21046 jgrothen@bbn.com Abstract Within the natural language processing (NLP) community, active learning has been widely investigated and applied in or- der to alleviate the annotation bottleneck faced by developers of new NLP systems and technologies. This paper presents the first theoretical analysis of stopping active learning based on stabilizing predictions (SP). The analysis has revealed three ele- ments that are central to the success of the SP method: (1) bounds on Cohen’s Kappa agreement between successively trained models impose bounds on differences in F-measure performance of the models; (2) since the stop set does not have to be la- beled, it can be made large in practice, helping to guarantee that the results trans- fer to previously unseen streams of ex- amples at test/application time; and (3) good (low variance) sample estimates of Kappa between successive models can be obtained. Proofs of relationships between the level of Kappa agreement and the dif- ference in performance between consecu- tive models are presented. Specifically, if the Kappa agreement between two mod- els exceeds a threshold T (where T > 0), then the difference in F-measure perfor- mance between those models is bounded above by 4(1−T) T in all cases. If precision of the positive conjunction of the models is assumed to be p, then the bound can be tightened to 4(1−T) (p+1)T . 1 Introduction Active learning (AL), also called query learning and selective sampling, is an approach to reduce the costs of creating training data that has received considerable interest (e.g., (Argamon-Engelson and Dagan, 1999; Baldridge and Osborne, 2008; Bloodgood and Vijay-Shanker, 2009b; Bloodgood and Callison-Burch, 2010; Hachey et al., 2005; Haertel et al., 2008; Haffari and Sarkar, 2009; Hwa, 2000; Lewis and Gale, 1994; Sassano, 2002; Settles and Craven, 2008; Shen et al., 2004; Thompson et al., 1999; Tomanek et al., 2007; Zhu and Hovy, 2007)). Within the NLP community, active learning has been widely investigated and applied in order to alleviate the annotation bottleneck faced by devel- opers of new NLP systems and technologies. The main idea is that by judiciously selecting which examples to have labeled, annotation effort will be focused on the most helpful examples and less an- notation effort will be required to achieve given levels of performance than if a passive learning policy had been used. Historically, the problem of developing meth- ods for detecting when to stop AL was tabled for future work and the research literature was fo- cused on how to select which examples to have la- beled and analyzing the selection methods (Cohn et al., 1996; Seung et al., 1992; Freund et al., 1997; Roy and McCallum, 2001). However, to realize …

Content truncated to 500 words