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

We proposed one-dimensional word embeddings.

Paper: https://arxiv.org/abs/2205.01954

💡 How to Use

wordtour.txt is the trained embeddings. The i-th line shows the i-th word in the tour. Note that the embeddings are circular, and thus the first line and the last line are next to each other.

UPDATE: Optimal Solution (May 14, 2025)

William Cook and Keld Helsgaun optimally solved the Word Tour problem with 40000 words. The optimal tour is available in wordtour_opt.txt.

The computation went as follows.

1. Keld created the TSP instance using this GitHub code and data. He then found a tour of 236876.914.

2. Bill used Keld’s tour as a starting point for concorde. Computing an LP lower bound of value 236873.279. It was not able to continue with a branch-and-bound search, since the LP was not able to eliminate many of the edges in the graph (using the LKH tour as an upper bound).

3. Bill sent Keld the LP solution, which had 40352 non-zero components, with 39652 edges set to the value 1.0. Keld used the 1.0 edges in a FIXED_EDGES_SECTION and quickly found with LKH a tour of length 236873523.

4. Keld’s new tour was very close in value to the LP lower bound. This allowed concorde to reduce the edge set to 140185 edges. The branch-and-bound run then solved the problem in 7180 seconds.

📝 Results

Examples of segments

Each row represents a segment. (a--d) Segments around "cat." (e--h) Segments around "concept." (i--o) Random segments of WordTour. WordTour provides smooth orderings.

| | Methods | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | --- | -------- | ------------ | ----------- | ----------- | ------------- | ------------ | ------------- | ---------- | ----------- | ----------- | ------------ | ------------- | | (a) | WordTour | sniff | sniffing | sniffer | dogs | dog | cat | cats | pets | pet | stray | errant | | (b) | RandProj | loire | sayings | nn | trooper | referendum | cat | exceeded | traces | freestyle | mirrored | bloomberg | | (c) | PCA1 | mm | asylum | kohl | presents | expressed | cat | sichuan | denmark | counted | corporations | hewitt | | (d) | PCA4 | 1.46 | puzzles | 940 | coexist | locations | cat | att | winners | perth | colgate | sohail | | | | | | | | | | | | | | | | (e) | WordTour | assumption | assumptions | notions | notion | idea | concept | concepts | ideas | thoughts | feelings | emotions | | (f) | RandProj | entertaining | 42,000 | kursk | embarrassment | ingrained | concept | berezovsky | cg | guillen | excerpts | roofs | | (g) | PCA1 | neighboring | branches | argued | manhattan | 1998 | concept | share | pending | response | airlines | fort | | (h) | PCA4 | 2:00 | hksar | hashim | provider | straining | concept | inducing | fightback | unsettled | bavaria | sign | | | | | | | | | | | | | | | | (i) | WordTour | wireless | broadband | 3g | cdma | gsm | handset | handsets | smartphones | smartphone | blackberry | tablet | | (j) | WordTour | gun | weapon | weapons | arms | arm | leg | legs | limbs | limb | prosthetic | make-up | | (k) | WordTour | federalist | libertarian | progressive | liberal | conservative | conservatives | liberals | democrats | republicans | gop | republican | | (l) | WordTour | cordial | amicable | agreeable | mutually | beneficial | detrimental | harmful | destructive | disruptive | behaviour | behavior | | (m) | WordTour | 15th | 14th | 13th | 12th | 10th | 11th | 9th | 8th | 7th | 6th | 5th | | (n) | WordTour | suspicions | doubts | doubt | doubted | doubting | doubters | skeptics | skeptic | believer | believers | adherents | | (o) | WordTour | molten | magma | lava | basalt | sandstone | limestone | granite | marble | slab | slabs | prefabricated |

Crawdsourcing Evaluation

Each bar represents the number of times each method was selected by crowdworkers within 100 trials.

Document Classification

Each cell reports a kNN classification error. Lower is better. The time row reports the average time to compare the two documents. WordTour performs the best in the blurred BoW family.

| | ohsumed | reuter | 20news | amazon | classic | | -------- | ------------- | ------------- | ------------- | -------------- | ------------- | | BoW | 48.1 | 5.6 | 35.4 | 11.4 ± 0.4 | 5.1 ± 0.3 | | Time | 39 ns | 23 ns | 35 ns | 21 ns | 23 ns | | | | | | | | | WordTour | 47.2 | 4.6 | 34.1 | 10.1 ± 0.3 | 4.6 ± 0.1 | | RandProj | 47.9 | 5.4 | 35.4 | 11.3 ± 0.3 | 5.1 ± 0.3 | | PCA1 | 47.8 | 5.7 | 35.5 | 11.4 ± 0.6 | 5.1 ± 0.3 | | PCA4 | 48.1 | 5.6 | 35.4 | 11.6 ± 0.5 | 5.1 ± 0.4 | | Time | 206 ns | 142 ns | 312 ns | 185 ns | 150 ns | | | | | | | | | WMD | 47.5 | 4.5 | 30.7 | 7.6 ± 0.3 | 4.2 ± 0.3 | | Time | 3.5 x 10^6 ns | 2.2 x 10^6 ns | 5.1 x 10^6 ns | 1.2 x 10^7 ns | 1.9 x 10^6 ns |

⛏️ How to Build WordTour by Yourself

1. Install the dependencies.

$ sudo apt install wget unzip build-essential

2. Download the GloVe embeddings and LKH solver.

$ ./download.sh

3. Compile the generator.

$ make

4. Create the LKH config file.

$ ./make_LKH_file
Usage: ./make_LKH_file [embedding file path] [#words]
$ ./make_LKH_file ./glove.6B/glove.6B.300d.txt 400 > ./LKH-3.0.6/wordtour.tsp
$ cp wordtour.par ./LKH-3.0.6/wordtour.par

Here, 400 is used for an illustration purpose. 40000 words may take a few minutes and consume a few GB of strage.

5. Compile the LKH solver.

$ cd LKH-3.0.6
$ make

6. Run the LKH solver.

$ ./LKH wordtour.par

Note: The result is saved in wordtour.out.

Note: It may take several hourds to run the LKH solver with 40000 words.

7. Extract the word list.

$ cd ..
$ python generate_order_file.py
$ cat wordtour.txt

🧪 How to Evaluate

1. Download the Datasets.

You also need to run ./download.sh if you haven't yet.

$ ./download_datasets.sh

2. Preprocess.

$ python ./preprocess.py

3. Evaluate.

Be sure that the embeddings files, wordtour.txt, order_randproj.txt, order_pca1.txt, and order_pca4.txt, contain the embeddings you want to evaluate. It might contain only 400 words if you ran the "How to Build WordTour by Yourself" scripts.

$ python evaluate.py

🖋️ Citation

@inproceedings{sato2022wordtour,
  author    = {Ryoma Sato},
  title     = {Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem},
  booktitle = {Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, {NAACL-HLT}},
  year      = {2022},
}