Binary Encoded Word Mover’s Distance (2022)

Abstract: Word Mover’s Distance is a textual distance metric which calculates the minimum transport cost between two sets of word embeddings. This metric achieves impressive results on semantic similarity tasks, but is slow and difficult to scale due to the large number of floating point calculations. This paper demonstrates that by combining pre-existing lower bounds with binary encoded word vectors, the metric can be rendered highly efficient in terms of computation time and memory while still maintaining accuracy on several textual similarity tasks.

## introduction a textual distance metric which can be used to accurately and quickly quantify the semantic dissimilarity between documents is useful for many natural language processing (nlp) tasks including text classification, document clustering, and document retrieval. word mover's distance (wmd) proposed by @xcite is a variant of the earth mover's distance which measures the semantic distance between texts. earth mover's distance is a well-studied transportation problem for measuring the distance between two probability distributions and was originally proposed for image retrieval applications @xcite . wmd leverages semantic distance information from pre-trained neural word embeddings to calculate a minimum transportation cost needed to 'move' the words from one text to those of another @xcite . let c(i, j) represent the euclidean distance transport cost between word embeddings i and j in documents d and d ′ , respectively. the minimum cumulative (weighted) transport cost differentiating the two documents can then be summarized as, t ij c(i, j) subject to: kusner et al. and others have introduced several lower bounds to the wmd which reduce computations by relaxing constraints on the original transport problem, albeit with accompanying performance trade-offs. the relaxed word mover's distance (rwmd) is obtained by removing the second or third constraints from equation 1, reducing the number of distance calculations given that all probability mass for each word in document d is moved to its most similar word in d ′ . on the aforementioned knn classification task, the rwmd produces an average error of 0.56, compared to 0.42 for the original wmd @xcite . @xcite propose another lower bound which involves a preprocessing phase for computing real-value distances between vocabulary items. during this phase, distances are computed between each word's r nearest neighbors and stored in a distance matrix m (werner and laber, 2019). these precomputed vector distances are retrieved when calculating transport costs c(i, j) between words; if c(i, j) cannot be found in m , a default maximum value c max is used instead. the related relaxed word mover's distance (rel-rwmd), which combines the preprocessing phase with the relaxed conditions of the rwmd, is significantly faster to compute while suffering a modest drop in accuracy compared to the wmd on text similarity tasks. of final note is the word centroid distance (wcd), which is computed as the distance between the unweighted average of each text's word embedding vectors @xcite . although not an alignment-based distance metric, wcd is a competitive metric which likewise leverages neural word embedding vectors. one pain-point of the original wmd which motivates the use of lookup tables by werner et al. is the large amount of floating point calculations needed to resolve the underlying transport problem. floating point arithmetic cpu instructions are generally slower than integer or bit operations. tissier et al. @xcite have proposed an autoencoding methodology for computing binary embeddings as encoded representations of an original, real-valued embedding space. with normalized xor hamming distance calculations, these binary vectors allow one to circumvent cpuintensive floating point arithmetic while also reducing the working memory footprint of the word vectors by up to 97% @xcite . this paper contributes a methodology for integrating the binary vectors of tissier et al. with the existing rel-rwmd lower bound as the binary encoded word mover's distance (bewmd). it is hypothesized that by replacing the default c max value of the rel-rwmd with normalized binary vector hamming distances, the proposed metric will produce a more accurate lower-bound to the original wmd while maintaining competitive computation times and, importantly, low memory requirements. ## methodology the proposed lower bound is realized via neural network encoding of real-valued word vectors and manipulation of the rel-rwmd calculation. an autoencoder network is trained with resort to a novel regularization parameter, while the rel-rwmd calculation is modified to accommodate the binary-encoded vectors and render it bidirectional. ## results per the methodology of @xcite , bewmd performance on a downstream semantic-similarity task is evaluated via the stanford triplets wikipedia benchmark 1 . metrics are assessed according to their ability to distinguish for a triplet of documents d 1 , d 2 , d foot_0 , which pair of documents is most-related. success for a single triplet is achieved if a metric computes the lowest distance score for the most-related document pair, namely d 1 and d 2 . triplet documents are wikipedia articles which were preprocessed to remove non-alphanumeric characters and tokens which are not embedded under the attested models, in order to maintain computation time comparability across all tested metrics. the autoencoder model used to produce the encoded vectors was fitted to pretrained word vectors from fasttext @xcite (common crawl, 600b tokens) 2 . consequently, all other distance metrics which rely on pretrained word embeddings used the same vectors. the autoencoder is fitted to the first 300,000 word vectors, which, given that the vectors are sorted by frequency, are assumed to be highly-representative of the full vector space. training lasted for ten epochs with λ @xmath0. original real-valued vectors of 300 floating-point dimensions are encoded to 512-bit representations, per the register sizes of avx-512 cpus. although the wmd was originally defined with euclidean distances, cosine rather than euclidean distance is used to compute the cost c(i, j) for all metrics, so as to avoid spurious comparisons with bewmd. tables 1, 2, and 3 demonstrate metric performance in terms of test error, offline, and online computation time, respectively. additionally, this paper compares metric performance on three of the knn benchmarks from @xcite : bbc sport contains sports articles between 2004-2005, classic contains sets of sentences from academic papers, and ohsumed is a collection of medical abstracts categorized by disease groups. datasets are retrieved from the repository associated with the original paper 3 . each dataset is subsampled to 100 randomly-selected samples (80 train, 20 test) across 5 sampling iterations. ## discussion results on these limited tasks demonstrate that the proposed metric is competitive with the original wmd in terms of test error while offering respectable online computation time improvements and a lower memory footprint. comparing bewmd triplets performance to that of the other metrics, it can be ascertained that for this task it is the most accurate lower bound to the original wmd. notably, the bewmd offers a clear improvement upon the rel-rwmd, assumedly by utilizing normalized binary vector hamming distances as opposed to a default c max value @xcite . furthermore, be-wmd test error is highly-competitive with the original wmd, confirming the accuracy of the encoded vectors as compared to their real-valued counterparts. results for the three knn benchmark tasks further substantiate bewmd as a consistentlyeffective lower bound. bewmd consistenly outperforms rwmd, rel-rwmd, and even the original wmd. these results pose the hypothesis that the encoded vectors can offer a more-effective word representation for certain tasks. however, rigorous evaluation of the potential representation advantages offered by the encoded vectors is outside the scope of this paper. regarding computation and memory demands, bewmd compares favorably with rwmd and rel-rwmd, offering a reasonable computation time trade-off against the rel-rwmd when be-wmd's improved test error is considered. all metrics which employ the real-valued vectors demand some 4gb of memory, while bewmd and rel-rwmd benefit from the reduced memory footprint of precomputed lookup tables and binary encoded vectors. optimization of the bewmd calculation so as to remove the need for precomputed lookup tables altogether remains a promising next step for further reducing the memory demands of the proposed metric. it is worth noting the efficacy of wcd given that, in terms of triplets test error alone, this metric outperforms all wmd lower bounds except the bewmd. furthermore, knn benchmark evaluations place wcd consistently ahead of rwmd and rel-rwmd, even surpassing wmd on the bbc sport dataset. although wcd requires more memory than either bewmd or rel-rwmd, its low computation time coupled with a relatively low test error on several evaluations pose this metric as a pragmatic alternative to wmd and the proposed metric for many use-cases. these evaluations suggest that the bewmd offers a balanced alternative to the original wmd, improving speed up to 14x while achieving competitive test error on several tasks. furthermore, bewmd's reduced memory footprint makes it suitable for low-resource compute environments. the demonstrated benefits of the bewmd are, however, offset by its considerable offline computations, which demand, under the experimental parameters used in this paper, some 4 hours to compute both the encoded vectors and the nearest neighbor lookup table. for applications under constrained hardware where an upfront computation investment is tolerable, the bewmd offers a consistently optimal lower bound to the original wmd. as an ethical aside, it must be mentioned that optimized libraries for several of the lower bounds presented here outperform the evaluated bewmd python implementation in terms of online computation time, and it is not this paper's intent to evade these performance discrepencies. the evaluations presented here aim only to compare lower bound performance using comparable software implementations. this paper suggests that binary encoded word vectors are valuable towards improving the scalability of wmd-derived distance metrics. the presented lower bound may be enhanced by optimizing the distance calculation in order to circumvent wmd approximation or the need for precomputed lookup tables.