Unsupervised Discovery of Negative Categories in Lexicon Bootstrapping

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 356–365, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Unsupervised discovery of negative categories in lexicon bootstrapping Tara McIntosh NICTA Victoria Research Lab Dept of Computer Science and Software Engineering University of Melbourne nlp@taramcintosh.org Abstract Multi-category bootstrapping algorithms were developed to reduce semantic drift. By ex- tracting multiple semantic lexicons simultane- ously, a category’s search space may be re- stricted. The best results have been achieved through reliance on manually crafted negative categories. Unfortunately, identifying these categories is non-trivial, and their use shifts the unsupervised bootstrapping paradigm to- wards a supervised framework. We present NEG-FINDER, the first approach for discovering negative categories automat- ically. NEG-FINDER exploits unsupervised term clustering to generate multiple nega- tive categories during bootstrapping. Our al- gorithm effectively removes the necessity of manual intervention and formulation of nega- tive categories, with performance closely ap- proaching that obtained using negative cate- gories defined by a domain expert. 1 Introduction Automatically acquiring semantic lexicons from text is essential for overcoming the knowledge bottle- neck in many NLP tasks, e.g. question answer- ing (Ravichandran and Hovy, 2002). Many of the successful methods follow the unsupervised itera- tive bootstrapping framework (Riloff and Shepherd, 1997). Bootstrapping has since been effectively ap- plied to extracting general semantic lexicons (Riloff and Jones, 1999), biomedical entities (Yu and Agichtein, 2003) and facts (Carlson et al., 2010). Bootstrapping is often considered to be minimally supervised, as it is initialised with a small set of seed terms of the target category to extract. These seeds are used to identify patterns that can match the tar- get category, which in turn can extract new lexicon terms (Riloff and Jones, 1999). Unfortunately, se- mantic drift often occurs when ambiguous or erro- neous terms and/or patterns are introduced into the iterative process (Curran et al., 2007). In multi-category bootstrapping, semantic drift is often reduced when the target categories compete with each other for terms and/or patterns (Yangarber et al., 2002). This process is most effective when the categories bound each other’s search space. To ensure this, manually crafted negative categories are introduced (Lin et al., 2003; Curran et al., 2007). Unfortunately, this makes these algorithms substan- tially more supervised. The design of negative categories is a very time consuming task. It typically requires a domain ex- pert to identify the semantic drift and its cause, fol- lowed by a significant amount of trial and error in or- der to select the most suitable combination of nega- tive categories. This introduces a substantial amount of supervised information into what was an unsuper- vised framework, and in turn negates one of the main advantages of bootstrapping — the quick construc- tion of accurate semantic lexicons. We show that although excellent performance is achieved using negative categories, it varies greatly depending on the negative categories selected. This highlights the difficulty of crafting negative cate- gories and thus the necessity for tools that can au- tomatically identify them. …

Content truncated to 500 words