TL;DR
This paper introduces the Binary Encoded Word Mover's Distance (BEWMD), a novel metric that significantly speeds up text similarity calculations by using binary representations of word embeddings. BEWMD achieves competitive accuracy with the original Word Mover's Distance (WMD) while drastically reducing computation time and memory usage, making it more practical for real-world applications.
What Problem Does This Paper Address?
Quantifying the semantic similarity between documents is crucial for many Natural Language Processing (NLP) tasks like text classification and document retrieval. The Word Mover's Distance (WMD) is a powerful metric that excels at this by measuring the minimum "transport cost" to match word embeddings between two documents. However, WMD is computationally expensive, requiring a large number of floating-point calculations, which hinders its scalability in production environments, especially with large vocabularies. Existing methods to speed up WMD often involve approximations that sacrifice accuracy. This paper aims to bridge this gap by developing a faster WMD variant that maintains high accuracy.
Methods
The core innovation of this paper is the integration of binary encoded word vectors with a relaxed version of WMD.
- Binary Encoding: The authors leverage a methodology proposed by Tissier et al. (2019) to create binary embeddings. This involves training a neural autoencoder to compress real-valued word embeddings into binary representations. A key aspect of their autoencoder training is a novel correlation-based regularization term added to the loss function. This term, denoted as
rs, helps preserve the semantic relationships present in the original vector space, which is crucial for maintaining accuracy. - Modified Relaxed Word Mover's Distance (Rel-RWMD): The paper adapts the Rel-RWMD, which already relaxes some constraints of the original WMD to reduce computations. Instead of using a default maximum cost (
Cmax) when a direct distance between two word embeddings isn't precomputed, BEWMD uses the normalized binary vector Hamming distance. - Bidirectional Calculation: The proposed BEWMD calculates two relaxed solutions (one for each direction of transport) and combines them via summation, making the distance calculation bidirectional. This approach is inspired by fusion methodologies.
Datasets
- Training: The autoencoder model was trained using pre-trained word vectors from FastText (Common Crawl, 600B tokens). The model was fitted to the first 300,000 word vectors, assumed to be representative of the overall vocabulary.
- Evaluation:
- Stanford Triplets Wikipedia benchmark: Used to evaluate the metric's ability to distinguish the most related pair of documents within a triplet. Wikipedia articles were preprocessed to remove non-alphanumeric characters and tokens not present in the embedded models.
- kNN benchmarks: Three datasets from Kusner et al. (2015) were used:
- BBC Sport: Sports articles from 2004-2005.
- Classic: Sentences from academic papers.
- Ohsumed: Medical abstracts categorized by disease groups. These datasets were subsampled to 100 samples (80 train, 20 test) across 5 iterations for evaluation.
Key Insights and Ideas
- Binary Embeddings for Efficiency: The paper strongly suggests that binary encoded word vectors are a powerful tool for improving the scalability of WMD-derived metrics. The shift from floating-point arithmetic to bit operations (Hamming distance) is a significant source of speedup and memory reduction.
- Correlation-Based Regularization is Key: The novel correlation-based regularization term (
rs) in the autoencoder's loss function is critical for preserving semantic information. This highlights that simply compressing vectors isn't enough; maintaining their relational structure is paramount for downstream task performance. - Hamming Distance as a Viable
CmaxReplacement: Replacing the defaultCmaxvalue in Rel-RWMD with normalized binary Hamming distances leads to more accurate lower bounds without significantly compromising speed. This suggests that the Hamming distance between binary embeddings can effectively capture semantic relatedness in this context. - Bidirectional Calculation Improves Robustness: Combining the two relaxed solutions (forward and backward) provides a more robust and comprehensive distance measure.
Key Results
- Accuracy: BEWMD achieved a test error of 0.393 on the Stanford Triplets benchmark, outperforming RWMD (0.594) and Rel-RWMD (0.641), and was highly competitive with the original WMD (0.389). On the kNN benchmarks, BEWMD consistently outperformed RWMD, Rel-RWMD, and even the original WMD in several cases.
- Speed: BEWMD offered significant online computation time improvements. For instance, it took only 1.68 seconds per iteration compared to 23.18 seconds for WMD. This represents a speedup of approximately 14x.
- Memory: BEWMD benefited from a reduced memory footprint, requiring 790 MB compared to 4409 MB for WMD and other real-valued vector methods.
Limitations and Future Work
- Offline Computation Cost: The paper acknowledges that the autoencoder training and the creation of nearest neighbor lookup tables (offline computations) can take a considerable amount of time (around 4 hours in their experimental setup).
- Optimization of Distance Calculation: A promising future direction is to optimize the distance calculation further to potentially circumvent the need for WMD approximation or precomputed lookup tables altogether, which could further reduce memory demands.
- Ethical Consideration: The authors note that optimized libraries for some lower bounds might outperform their Python implementation of BEWMD in online computation time, emphasizing that their evaluations focused on comparable software implementations.
- Representation Advantages: While BEWMD's encoded vectors show promise, a rigorous evaluation of their general representation advantages across various tasks is outside the scope of this paper.
Summary updated