A Semi-Supervised Feature Clustering Algorithm with Application to Word Sense Disambiguation

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 907–914, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics A Semi-Supervised Feature Clustering Algorithm with Application to Word Sense Disambiguation Zheng-Yu Niu, Dong-Hong Ji Institute for Infocomm Research 21 Heng Mui Keng Terrace 119613 Singapore {zniu, dhji}@i2r.a-star.edu.sg Chew Lim Tan Department of Computer Science National University of Singapore 3 Science Drive 2 117543 Singapore tancl@comp.nus.edu.sg Abstract In this paper we investigate an applica- tion of feature clustering for word sense disambiguation, and propose a semi- supervised feature clustering algorithm. Compared with other feature clustering methods (ex. supervised feature cluster- ing), it can infer the distribution of class labels over (unseen) features unavailable in training data (labeled data) by the use of the distribution of class labels over (seen) features available in training data. Thus, it can deal with both seen and unseen fea- tures in feature clustering process. Our ex- perimental results show that feature clus- tering can aggressively reduce the dimen- sionality of feature space, while still main- taining state of the art sense disambigua- tion accuracy. Furthermore, when com- bined with a semi-supervised WSD algo- rithm, semi-supervised feature clustering outperforms other dimensionality reduc- tion techniques, which indicates that using unlabeled data in learning process helps to improve the performance of feature clus- tering and sense disambiguation. 1 Introduction This paper deals with word sense disambiguation (WSD) problem, which is to assign an appropriate sense to an occurrence of a word in a given context. Many corpus based statistical methods have been proposed to solve this problem, including supervised learning algorithms (Leacock et al., 1998; Towel and Voorheest, 1998), weakly supervised learning algo- rithms (Dagan and Itai, 1994; Li and Li, 2004; Mi- halcea, 2004; Niu et al., 2005; Park et al., 2000; Yarowsky, 1995), unsupervised learning algorithms (or word sense discrimination) (Pedersen and Bruce, 1997; Sch¨utze, 1998), and knowledge based algo- rithms (Lesk, 1986; McCarthy et al., 2004). In general, the most common approaches start by evaluating the co-occurrence matrix of features ver- sus contexts of instances of ambiguous word, given sense-tagged training data for this target word. As a result, contexts are usually represented in a high- dimensional sparse feature space, which is far from optimal for many classification algorithms. Further- more, processing data lying in high-dimensional fea- ture space requires large amount of memory and CPU time, which limits the scalability of WSD model to very large datasets or incorporation of WSD model into natural language processing sys- tems. Standard dimentionality reduction techniques in- clude (1) supervised feature selection and super- vised feature clustering when given labeled data, (2) unsupervised feature selection, latent semantic in- dexing, and unsupervised feature clustering when only unlabeled data is available. Supervised fea- ture selection improves the performance of an ex- amplar based learning algorithm over SENSEVAL- 2 data (Mihalcea, 2002), Naive Bayes and deci- sion tree over SENSEVAL-1 and SENSEVAL-2 data (Lee and Ng, 2002), but feature selection does not improve SVM and …

Content truncated to 500 words