Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem

Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2166 - 2172 July 10-15, 2022 ©2022 Association for Computational Linguistics Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem Ryoma Sato Kyoto University / RIKEN AIP r.sato@ml.ist.i.kyoto-u.ac.jp Abstract Word embeddings are one of the most fun- damental technologies used in natural lan- guage processing. Existing word embeddings are high-dimensional and consume consider- able computational resources. In this study, we propose WORDTOUR, unsupervised one- dimensional word embeddings. To achieve the challenging goal, we propose a decompo- sition of the desiderata of word embeddings into two parts, completeness and soundness, and focus on soundness in this paper. Ow- ing to the single dimensionality, WORDTOUR is extremely efficient and provides a minimal means to handle word embeddings. We ex- perimentally confirmed the effectiveness of the proposed method via user study and document classification. 1 Introduction Word embeddings are one of the most thriving tech- niques in natural language processing and are used in various tasks, including word analogy (Mikolov et al., 2013; Pennington et al., 2014), text classifi- cation (Kim, 2014; Kusner et al., 2015; Shen et al., 2018), and text similarity (Arora et al., 2017; Yokoi et al., 2020). Existing word embeddings are in high- dimensional spaces. Although high dimensionality offers representational power to word embeddings, it also has the following drawbacks: (1) Memory inefficiency. High-dimensional word embeddings require the storage of many floating-point values, and they consume considerable memory space. For instance, the 300-dimensional GloVe with 400k words consumes 1 GB of memory. This hinders the application of word embeddings in edge devices (Raunak et al., 2019; Jurgovsky et al., 2016; Joulin et al., 2016). (2) Time inefficiency. The high di- mensionality also increases the time consumption owing to many floating-point arithmetic operations. (3) Uninterpretability. It is not straightforward to visualize high-dimensional embeddings. Pro- jections to low dimensional spaces, e.g., by t-SNE and PCA, lose some information, and it is difficult to control and interpret the aspects that these pro- jections preserve. Besides, word embeddings are sparse in high-dimensional space, and for a small perturbation ε ∈ Rd, it is not clear what xcat + ε represents, e.g., when creating adversarial exam- ples (Lei et al., 2019) and data augmentation (Qu et al., 2021). In this study, we propose WORDTOUR, unsu- pervised one dimensional word embeddings. In contrast to high-dimensional embeddings, WORD- TOUR is memory efficient. It does not require storing even a single floating-point value; instead, it stores only the order of words. WORDTOUR with 40k words consumes only 300 KB memory, which is the same space as the space for storing a list of the words. Memory efficiency enables applica- tions in low-resource environments. WORDTOUR is time efficient as well. It can compare words in a single operation whereas traditional embeddings require hundreds of floating-point operations for a single comparison. In addition, it can retrieve sim- ilar words by simply looking up the surrounding words in a …

Content truncated to 500 words