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

Abstract: Word embeddings are one of the most fundamental technologies used in natural language processing. Existing word embeddings are high-dimensional and consume considerable computational resources. In this study, we propose WordTour, unsupervised one-dimensional word embeddings. To achieve the challenging goal, we propose a decomposition of the desiderata of word embeddings into two parts, completeness and soundness, and focus on soundness in this paper. Owing to the single dimensionality, WordTour is extremely efficient and provides a minimal means to handle word embeddings. We experimentally confirmed the effectiveness of the proposed method via user study and document classification.

## introduction word embeddings are one of the most thriving techniques in natural language processing and are used in various tasks, including word analogy @xcite ), text classification @xcite @xcite , and text similarity @xcite . existing word embeddings are in highdimensional 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 @xcite @xcite . (2) time inefficiency. the high dimensionality also increases the time consumption owing to many floating-point arithmetic operations. in this study, we propose wordtour, unsupervised 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 applications 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 similar words by simply looking up the surrounding words in a constant time and can efficiently compare documents using a blurred bag of words, as we will show in the experiments. these features are also advantageous in low resource environments. in addition, wordtour is interpretable owing to its single dimensionality. it is straightforward to visualize the one dimentional embeddings without any information loss. besides, we can always interpret the perturbed word embedding as we can interpret the perturbed image pixels. in brief, word-tour provides a minimal means to handle word embeddings. however, words are inherently highdimensional, and it is impossible to capture all semantics in one dimension. to tackle this challenge, we propose to decompose the desiderata of word embeddings into two components: soundness and completeness. wordtour gives up completeness, focuses on soundness, and thereby realizes meaningful one dimensional embeddings for some, if not all, applications. we formulate the optimization of sound word embeddings as the traveling salesman problem and solve it using a highly efficient solver. in the experiments, we confirm that wordtour provides high-quality embeddings via qualitative comparison, user studies, and document classification. reproducibility: our code and obtained embeddings are available at https:// github.com/joisino/wordtour . 2 backgrounds 2.1 notations let v be the set of words in a vocabulary, and @xmath0. let [n] = {1, 2, • • • , n} and let p([n]) be the set of permutations of [n]. ## word tour in this section, we introduce our proposed method, wordtour. ideally, we would like to preserve all the semantics in our one-dimensional embeddings. however, such ideal embeddings are unlikely to exist because the relations between words are inherently high-dimensional. indeed, although existing studies have attempted to reduce the dimensionality of word embeddings, they require at least tens of dimensions @xcite and several dimensions even in non-euclidean spaces @xcite . these results indicate that ideal 1d embeddings do not exist. therefore, we make a compromise. we decompose the desiderata of word embeddings into the following two categories: soundness close embeddings should have semantically similar meanings. completeness semantically similar words should be embedded closely. in wordtour, we give up the latter condition and focus on the former condition. for instance, the two red stars in figure 1 are distant in the order, although they are semantically similar. wordtour accepts such inconsistency. owing to the incompleteness, wordtour may fail some applications of word embeddings, such as word analogy and relation extraction. nevertheless, wordtour still has some other applications, such as word replacement and document retrieval. indeed, wordtour may overlook some relevant documents because they may embed relevant words far apart. however, the close documents found by wordtour are indeed close owing to soundness. these insights indicate that there exist one-dimensional embeddings that are useful for some, if not all, applications. a natural criterion for soundness is that consecutive words in the ordering should be close to one another in the original embedding space. we formulate the problem as follows: in formulation (1), we adopt the l 2 norm for simplicity. however, our formulation is agnostic to the distance function. when a corpus is at hand, we can also use the number of co-occurrences, i.e., i #co-occurrences of (σ i , σ i+1 ) , as the cost function. we leave investigating other modelings as future work and focus on the l 2 cost in this paper. the optimization problem (1) is an instance of the traveling salesman problem (tsp), which is nphard. as the problem size is relatively large in our case, for instance, @xmath1, it may seem impossible to solve the problem. however, in practice, highly efficient tsp solvers have been developed. among others, we employ the lkh solver (helsgaun, 2018), which implements the lin kernighan algorithm @xcite in a highly efficient and effective manner. the lkh solver performs a restricted local search based on a guide graph constructed using the dual problem. @xcite reported that the lkh solver exactly solved an instance with as many as 109 399 cities. in addition, several effective algorithms for computing lower bounds provide theoretical guarantees for the quality of a solution. we employ the one-tree lower bound @xcite implemented in the lkh solver to compute the lower bounds of the optimum value. as a tour is a special case of a one-tree, the minimum cost onetree is a provable lower bound of the tsp problem. the algorithm searches for a potential vector for a tight lower bound by gradient ascent. wordtour computes a near-optimal solution of problem (1) by the lkh solver and uses the solution as the word order, i.e., the word embeddings. ## experiments we experimentally validated the effectiveness of wordtour. we used a linux server with intel xeon e7-4830 v4 cpus in the experiments. ## conclusion in this study, we proposed wordtour, a 1d word embedding method. to realize 1d embedding, we decompose the requirement of word embeddings into two parts and impose only one constraint in which the consecutive words should be semantically similar. we formulate this problem using the tsp and solve it with a state-of-the-art solver. although the tsp is np-hard, the effective solver solves the optimization almost optimally and provides effective 1d embeddings. we confirmed its effectiveness via crowdsourcing and document classification.