Active Learning with Sampling by Uncertainty and Density for Word Sense Disambiguation and Text Classification

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 1137–1144 Manchester, August 2008 Active Learning with Sampling by Uncertainty and Density for Word Sense Disambiguation and Text Classification Jingbo Zhu Huizhen Wang Tianshun Yao Natural Language Processing Laboratory Northeastern University Shenyang, Liaoning, P.R.China 110004 zhujingbo@mail.neu.edu.cn wanghuizhen@mail.neu.edu.cn Benjamin K Tsou Language Information Sciences Research Centre City University of Hong Kong HK, P.R.China rlbtsou@cityu.edu.hk Abstract This paper addresses two issues of active learning. Firstly, to solve a problem of uncertainty sampling that it often fails by selecting outliers, this paper presents a new selective sampling technique, sam- pling by uncertainty and density (SUD), in which a k-Nearest-Neighbor-based density measure is adopted to determine whether an unlabeled example is an out- lier. Secondly, a technique of sampling by clustering (SBC) is applied to build a representative initial training data set for active learning. Finally, we implement a new algorithm of active learning with SUD and SBC techniques. The experi- mental results from three real-world data sets show that our method outperforms competing methods, particularly at the early stages of active learning. 1 Introduction Creating a large labeled training corpus is expen- sive and time-consuming in some real-world ap- plications (e.g. word sense annotation), and is often a bottleneck to build a supervised classifier for a new application or domain. Our study aims to minimize the amount of human labeling ef- forts required for a supervised classifier (e.g. for automated word sense disambiguation) to achieve a satisfactory performance by using ac- tive learning. Among the techniques to solve the knowledge bottleneck problem, active learning is a widely used framework in which the learner has the abil- ity to automatically select the most informative © 2008. Licensed under the Creative Commons Attri- bution-Noncommercial-Share Alike 3.0 Unported license (http://creativecommons.org/licenses/by-nc- sa/3.0/). Some rights reserved. unlabeled examples for human annotation. The ability of the active learner can be referred to as selective sampling. Uncertainty sampling (Lewis and Gale, 1994) is a popular selective sampling technique, and has been widely studied in natural language processing (NLP) applications such as word sense disambiguation (WSD) (Chen et al., 2006; Chan and Ng, 2007), text classification (TC) (Lewis and Gale, 1994; Zhu et al., 2008), statistical syntactic parsing (Tang et al., 2002), and named entity recognition (Shen et al., 2004). Actually the motivation behind uncertainty sampling is to find some unlabeled examples near decision boundaries, and use them to clarify the position of decision boundaries. However, uncertainly sampling often fails by selecting out- liers (Roy and McCallum, 2001; Tang et al., 2002). These selected outliers (i.e. unlabeled ex- amples) have high uncertainty, but can not pro- vide much help to the learner. To solve the out- lier problem, we proposed in this paper a new method, sampling by uncertainty and density (SUD), in which a K-Nearest-Neighbor-based density (KNN-density) measure is used to deter- mine whether an unlabeled example is an outlier, and a combination strategy based on KNN- density measure and uncertainty measure is de- signed to select the …

Content truncated to 500 words