Random Manhattan Integer Indexing: Incremental L1 Normed Vector Space Construction

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1713–1723, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Random Manhattan Integer Indexing: Incremental L1 Normed Vector Space Construction Behrang Q. Zadeh† † Insight Centre National University of Ireland, Galway Galway, Ireland behrang.qasemizadeh@insight-centre.org Siegfried Handschuh†‡ ‡ Dept. of Computer Science and Mathematics University of Passau Bavaria, Germany siegfried.handschuh@uni-passau.de Abstract Vector space models (VSMs) are math- ematically well-defined frameworks that have been widely used in the distributional approaches to semantics. In VSMs, high- dimensional vectors represent linguistic entities. In an application, the similar- ity of vectors—and thus the entities that they represent—is computed by a distance formula. The high dimensionality of vec- tors, however, is a barrier to the perfor- mance of methods that employ VSMs. Consequently, a dimensionality reduction technique is employed to alleviate this problem. This paper introduces a novel technique called Random Manhattan In- dexing (RMI) for the construction of ℓ1 normed VSMs at reduced dimensionality. RMI combines the construction of a VSM and dimension reduction into an incre- mental and thus scalable two-step proce- dure. In order to attain its goal, RMI em- ploys the sparse Cauchy random projec- tions. We further introduce Random Man- hattan Integer Indexing (RMII): a compu- tationally enhanced version of RMI. As shown in the reported experiments, RMI and RMII can be used reliably to estimate the ℓ1 distances between vectors in a vec- tor space of low dimensionality. 1 Introduction Distributional semantics embraces a set of meth- ods that decipher the meaning of linguistic en- tities using their usages in large corpora (Lenci, 2008). In these methods, the distributional proper- ties of linguistic entities in various contexts, which are collected from their observations in corpora, are compared to quantify their meaning. Vector spaces are intuitive, mathematically well-defined frameworks to represent and process such infor- mation.1 In a vector space model (VSM), linguis- tic entities are represented by vectors and a dis- tance formula is employed to measure their distri- butional similarities (Turney and Pantel, 2010). In a VSM, each element ⃗si of the standard basis of the vector space (informally, each dimension of the VSM) represents a context element. Given n context elements, an entity whose meaning is be- ing analyzed is expressed by a vector ⃗v as a linear combination of ⃗si and scalars αi ∈ R such that ⃗v = α1⃗s1 +· · ·+αn⃗sn. The value of αi is derived from the frequency of the occurrences of the entity that ⃗v represents in/with the context element that ⃗si represents. As a result, the values assigned to the coordinates of a vector (i.e. αi) exhibit the cor- relation of entities and context elements in an n- dimensional real vector space Rn. Each vector can be written as a 1×n row matrix, e.g. (α1, · · · , αn). Therefore, a group of m vectors in a vector space is often represented by a matrix Mm×n. Latent semantic analysis (LSA) is a famil- iar technique …

Content truncated to 500 words