Centering Similarity Measures to Reduce Hubs

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 613–623, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Centering Similarity Measures to Reduce Hubs Ikumi Suzuki National Institute of Genetics Mishima, Shizuoka, Japan suzuki.ikumi@gmail.com Kazuo Hara National Institute of Genetics Mishima, Shizuoka, Japan kazuo.hara@gmail.com Masashi Shimbo Nara Institute of Science and Technology Ikoma, Nara, Japan shimbo@is.naist.jp Marco Saerens Universit´e catholique de Louvain Louvain-la-Neuve, Belgium marco.saerens@uclouvain.be Kenji Fukumizu The Institute of Statistical Mathematics Tachikawa, Tokyo, Japan fukumizu@ism.ac.jp Abstract The performance of nearest neighbor methods is degraded by the presence of hubs, i.e., ob- jects in the dataset that are similar to many other objects. In this paper, we show that the classical method of centering, the transforma- tion that shifts the origin of the space to the data centroid, provides an effective way to re- duce hubs. We show analytically why hubs emerge and why they are suppressed by cen- tering, under a simple probabilistic model of data. To further reduce hubs, we also move the origin more aggressively towards hubs, through weighted centering. Our experimental results show that (weighted) centering is effec- tive for natural language data; it improves the performance of the k-nearest neighbor classi- fiers considerably in word sense disambigua- tion and document classification tasks. 1 Introduction 1.1 Background The k-nearest neighbor (kNN) algorithm is a sim- ple nonparametric method of classification. It has been applied to various natural language process- ing (NLP) tasks such as document classification (Masand et al., 1992; Yang and Liu, 1999), part- of-speech tagging (Søgaard, 2011), and word sense disambiguation (Navigli, 2009). To apply the kNN algorithm, data is typically rep- resented as a vector object in a feature space, and (dis)similarity between data is measured by the dis- tance between the vectors, their inner product, or co- sine of the angle between them (Jurafsky and Mar- tin, 2008). With such a (dis)similarity measure, the unknown class label of a test object is predicted by a majority vote of the classes of its k most similar objects in the labeled training set. Recent studies (Radovanovi´c et al., 2010a; Radovanovi´c et al., 2010b) have shown that if the feature space is high-dimensional, some objects in the dataset emerge as hubs; i.e., these objects fre- quently appear in the k nearest neighbors of other objects. The emergence of hubs may deteriorate the per- formance of kNN classification and nearest neighbor search in general: • If hub objects exist in the training set, they have a strong chance to be a kNN of many test ob- jects. Because the class of a test object is pre- dicted by a majority vote from its k nearest neighbors, prediction is biased toward the la- bels of the hubs. • In information retrieval, nearest neighbor search finds objects in the database that are most relevant, or similar, to user-provided queries. If particular objects, such as hubs, are nearly always returned for any query, the re- trieved results are probably not very useful. …

Content truncated to 500 words