Graph-based Analysis of Semantic Drift in Espresso-like Bootstrapping Algorithms

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 1011–1020, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Graph-based Analysis of Semantic Drift in Espresso-like Bootstrapping Algorithms Mamoru Komachi NAIST, Japan mamoru-k@is.naist.jp Taku Kudo Google Inc. taku@google.com Masashi Shimbo NAIST, Japan shimbo@is.naist.jp Yuji Matsumoto NAIST, Japan matsu@is.naist.jp Abstract Bootstrapping has a tendency, called seman- tic drift, to select instances unrelated to the seed instances as the iteration proceeds. We demonstrate the semantic drift of bootstrap- ping has the same root as the topic drift of Kleinberg’s HITS, using a simplified graph- based reformulation of bootstrapping. We confirm that two graph-based algorithms, the von Neumann kernels and the regularized Laplacian, can reduce semantic drift in the task of word sense disambiguation (WSD) on Senseval-3 English Lexical Sample Task. Proposed algorithms achieve superior perfor- mance to Espresso and previous graph-based WSD methods, even though the proposed al- gorithms have less parameters and are easy to calibrate. 1 Introduction In recent years machine learning techniques be- come widely used in natural language processing (NLP). These techniques offer various ways to ex- ploit large corpora and are known to perform well in many tasks. However, these techniques often re- quire tagged corpora, which are not readily available to many languages. So far, reducing the cost of hu- man annotation is one of the important problems for building NLP systems. To mitigate the problem of hand-tagging re- sources, semi(or minimally)-supervised and unsu- pervised techniques have been actively studied. Hearst (1992) first presented a bootstrapping method which requires only a small amount of instances (seed instances) to start with, but can easily mul- tiply the number of tagged instances with mini- mal human annotation cost, by iteratively apply- ing the following phases: pattern induction, pattern ranking/selection, and instance extraction. Boot- strapping has been widely adopted in NLP applica- tions such as word sense disambiguation (Yarowsky, 1995), named entity recognition (Collins and Singer, 1999) and relation extraction (Riloff and Jones, 1999; Pantel and Pennacchiotti, 2006). However, it is known that bootstrapping often ac- quires instances not related to seed instances. For example, consider the task of collecting the names of common tourist sites from web corpora. Given words like “Geneva” and “Bali” as seed instances, bootstrapping would eventually learn generic pat- terns such as “pictures” and “photos,” which also co-occur with many other unrelated instances. The subsequent iterations would likely acquire frequent words that co-occur with these generic patterns, such as “Britney Spears.” This phenomenon is called semantic drift (Curran et al., 2007). A straightforward approach to avoid semantic drift is to terminate iterations before hitting generic patterns, but the optimal number of iterations is task dependent and is hard to come by. The recently pro- posed Espresso (Pantel and Pennacchiotti, 2006) al- gorithm incorporates sophisticated scoring functions to cope with generic patterns, but as Komachi and Suzuki (2008) pointed out, Espresso still shows se- mantic drift unless iterations are terminated appro- priately. Another deficiency in bootstrapping is its sensi- tivity to many …

Content truncated to 500 words