Navigating the Semantic Horizon using Relative Neighborhood Graphs

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2451–2460, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Navigating the Semantic Horizon using Relative Neighborhood Graphs Amaru Cuba Gyllensten and Magnus Sahlgren Gavagai Bondegatan 21 116 33 Stockholm Sweden {amaru|mange}@gavagai.se Abstract This paper introduces a novel way to nav- igate neighborhoods in distributional se- mantic models. The approach is based on relative neighborhood graphs, which uncover the topological structure of local neighborhoods in semantic space. This has the potential to overcome both the problem with selecting a proper k in k-NN search, and the problem that a ranked list of neighbors may conflate several different senses. We provide both qualitative and quantitative results that support the viabil- ity of the proposed method. 1 Introduction Nearest neighbor search is a fundamental opera- tion in data mining, in which we are interested in finding the closest points to some given reference point. Formally, if we have a reference point r and a set of other points P in a metric space M with some distance function d, the nearest neigh- bor search task is to find the point p ∈ P that min- imizes d(p, r). In k-Nearest Neighbor search (k- NN), we want to find the k closest points to some given reference point. Nearest neighbor search is a well-studied task, and in particular the com- plexity of the task (a linear search has a running time of O(Ni) where N is the cardinality of P and i the complexity of the distance function d) has generated a lot of research; suggestions for re- ducing the complexity of linear nearest neighbor searches include using various types of space par- titioning techniques like k-d trees (Bentley, 1975), or various techniques for doing approximate near- est neighbor search (Arya et al., 1998), of which one of the most well-known is locality-sensitive hashing (Indyk and Motwani, 1998). The problem we are concerned with in this paper is not the complexity of nearest neighbor search, but the question of how to identify the in- ternal structure of neighborhoods defined by the nearest neighbors. The problem with a normal k- NN is that the result — a sorted list of the k nearest neighbors — does not say anything about the inter- nal structure of the neighborhood. It is quite pos- sible for two neighborhoods with widely different internal structures to produce identical k-NN re- sults. In the context of Distributional Semantic Models (DSMs), which collect and represent co- occurrence statistics in high-dimensional vector spaces, such structural differences may carry sig- nificant semantic information, e.g. about the dif- ferent senses of terms. We argue that the inability of standard k-NN to account for structural prop- erties has been misinterpreted as a shortcoming of the distributional representation (Erk and Pad´o, 2010). We will demonstrate in this paper that this is not a shortcoming of the distributional represen- tation, but of the mode of querying the DSM. We argue that information about …

Content truncated to 500 words