Introduction
The alignment of word embedding spaces across languages is a fundamental task in cross-lingual Natural Language Processing (NLP). By mapping disparate vector spaces—such as those generated by fastText for English and French—into a shared coordinate system, researchers can enable unsupervised machine translation and cross-lingual model transfer. Traditionally, this alignment is framed as a Procrustes problem, seeking an orthogonal transformation that minimizes the distance between corresponding words. In unsupervised settings, where no seed dictionary exists, this becomes a joint optimization of the transformation and the latent correspondence, often solved via Optimal Transport (OT).
The Sampling Bottleneck
The standard approach to unsupervised alignment involves the Wasserstein-Procrustes problem, which requires finding a permutation matrix (mapping words) and an orthogonal matrix (the rotation). However, solving the Optimal Transport problem is computationally intensive, typically scaling at $O(k^2)$ or $O(k^3)$. To maintain tractability, practitioners often resort to random sampling of a few thousand words.
This reliance on random sampling introduces a significant hurdle: the "curse of dimensionality." In high-dimensional embedding spaces (e.g., 300D), a small random sample rarely captures the underlying geometric structure of the full distribution. This leads to "noisy" alignments, where the resulting rotation is biased by the specific random points chosen rather than the global linguistic topology, ultimately limiting the accuracy of Bilingual Lexicon Induction (BLI).
Quantized Wasserstein Procrustes (qWP)
To address the limitations of random sampling, this paper introduces Quantized Wasserstein Procrustes (qWP). The core innovation lies in replacing stochastic sampling with a quantization-based "coreset" construction.
1. Coreset Construction via Quantization
Instead of selecting $k$ words at random, qWP employs a two-stage process. First, a large pool of $m$ samples is drawn from the vocabulary. Second, the algorithm applies $k$-means++ clustering to these samples to identify $k$ cluster centers (anchor points). These centers act as a high-quality summary of the embedding distribution, effectively filtering out local noise and focusing on the high-density regions of the language space.
2. Weighted Optimal Transport
The alignment is then performed on these $k$ weighted anchor points. By solving the OT problem on a representative coreset rather than raw, noisy samples, the algorithm produces a more robust permutation matrix. The authors utilize the Sinkhorn algorithm within a stochastic optimization framework, alternating between updating the alignment (permutation) and the rotation (Procrustes analysis).
3. Iterative Refinement
Once an initial alignment is established using the quantized points, the model undergoes a refinement phase. It generates a synthetic dictionary based on the closest neighbors in the aligned space and iteratively re-calculates the Procrustes rotation. This step polishes the mapping, moving from the coarse alignment of cluster centers to a fine-grained alignment of the entire vocabulary.
Experimental Results
The authors evaluated qWP using 300-dimensional fastText embeddings across several European language pairs (English, Spanish, French, German, Russian, and Italian) using the MUSE dataset.
Performance and Efficiency
The qWP method achieved state-of-the-art (SOTA) results for unsupervised BLI. On the English-Spanish (EN-ES) task, the model reached a Precision@1 of 83.9%. Across all tested language pairs, qWP consistently outperformed existing unsupervised baselines, including Gromov-Wasserstein (GW) and adversarial training methods.
Closing the Supervision Gap
One of the most striking findings is how closely qWP approaches the performance of supervised methods. While RCSLS—a leading supervised method—requires a 5,000-word seed dictionary to achieve an average accuracy of 77.3%, qWP reached 75.9% without any initial translation data. This suggests that the geometric structure of language is sufficiently consistent that quantization can recover nearly as much information as a medium-sized human-curated dictionary.
Discussion and Limitations
The success of qWP highlights the importance of data representation in geometric alignment. By treating quantization as a "denoising filter," the method ensures that the OT solver works on the structural backbone of the language rather than its outliers.
However, the method is not without limitations:
- Isometry Assumption: qWP assumes that the relative distances between words are preserved across languages (isometry). While this holds for closely related languages, it may fail for linguistically distant pairs (e.g., English and Chinese), where the conceptual "shapes" of the languages differ significantly.
- Unbalanced Transport: While the authors experimented with Unbalanced Optimal Transport to handle polysemy and non-existent translations, the empirical gains were marginal. This suggests that the standard balanced assumption is surprisingly resilient.
- Computational Scaling: Although more efficient than using massive random samples, the $O(k^2)$ complexity of the Sinkhorn solver still places a ceiling on the number of anchor points that can be practically utilized.
Conclusion
Quantized Wasserstein Procrustes represents a significant step forward in unsupervised cross-lingual learning. By leveraging $k$-means++ to create representative coresets, qWP overcomes the noise inherent in random sampling, providing a robust and efficient framework for aligning word embedding spaces that rivals supervised techniques.
Summary updated