Source-linked AI summary
Gromov-Wasserstein Alignment of Word Embedding Spaces
David Alvarez-Melis, Tommi S. Jaakkola
TL;DR
Unsupervised cross-lingual alignment needs to work from monolingual embeddings without the multi-step heuristics used by existing methods. The paper directly optimizes a relational Gromov-Wasserstein optimal-transport objective, obtaining fast, stable, robust alignments with near state-of-the-art performance at much lower computational cost. Its pure formulation is best suited to small-to-moderate vocabularies, so large problems use a two-step scaling procedure.
Problem
Cross-lingual correspondence methods should operate on largely monolingual data, but existing unsupervised approaches rely on multiple processing steps, initialization, or postmapping refinement.
Method
The paper uses Gromov-Wasserstein distance in a relational optimal-transport formulation that compares pairwise relations between word embeddings across languages.
Results
Near state-of-the-art performance is achieved with a fast, stable, and robust alignment framework at computational cost orders of magnitude lower than alternative fully unsupervised methods.
Takeaways & Limitations
A direct, efficiently optimized objective can provide unsupervised word alignment without post-processing or heuristic adjustments, while matching state-of-the-art performance.
Takeaways & Limitations
Pure Gromov-Wasserstein optimization becomes prohibitive for very large vocabularies, requiring a two-step subset-matching and orthogonal-mapping approach for scaling.
Abstract
from arXiv · showhide
Cross-lingual or cross-domain correspondences play key roles in tasks ranging from machine translation to transfer learning. Recently, purely unsupervised methods operating on monolingual embeddings have become effective alignment tools. Current state-of-the-art methods, however, involve multiple steps, including heuristic post-hoc refinement strategies. In this paper, we cast the correspondence problem directly as an optimal transport (OT) problem, building on the idea that word embeddings arise from metric recovery algorithms. Indeed, we exploit the Gromov-Wasserstein distance that measures how similarities between pairs of words relate across languages. We show that our OT objective can be estimated efficiently, requires little or no tuning, and results in performance comparable with the state-of-the-art in various unsupervised word translation tasks.
1 Introduction
Cross-lingual and cross-domain correspondence learning supports many linguistic tasks, motivating methods that work from largely monolingual data. The paper replaces multi-step unsupervised alignment with a direct, efficient Gromov-Wasserstein optimal-transport formulation.
- Cross-lingual correspondences support tasks including machine translation, transfer across domains, POS tagging, dependency parsing, and bilingual lexical induction.
- Fully unsupervised embedding methods can match supervised performance, but typically require careful initialization or postmapping refinements.
- The paper formulates correspondence learning as relational optimal transport using Gromov-Wasserstein distance between pairwise word relations across languages.
- The proposed Gromov-Wasserstein approach is theoretically motivated, fully unsupervised, efficient, robust, single-step, and free of post-processing or heuristic adjustments.
- An extension maps words outside the vocabulary used in the original optimization problem, enabling scaling to large vocabularies.
- On benchmark word-translation tasks, the method performs on par with state-of-the-art neural methods while requiring less computational cost and/or hyperparameter tuning.
2 Problem Formulation
The formulation defines unsupervised alignment between two word-embedding spaces without parallel data, then contrasts supervised Procrustes and classic optimal transport approaches before motivating Gromov-Wasserstein alignment.
- 2 Problem Formulation: The task is to align two vocabularies represented by embedding sets without parallel data, typically assuming equal vocabulary sizes and dimensions for simplicity.
- 2.1 Supervised Maps: Procrustes: Supervised Procrustes learns a map T from source to target embeddings when known word correspondences are available.
- 2.1 Supervised Maps: Procrustes: Constraining T to orthonormal matrices yields rotations and reflections, with a closed-form SVD solution that preserves angles and distances.
- 2.1 Supervised Maps: Procrustes: Procrustes alone is supervised because it requires known correspondences, so unsupervised pipelines first generate pseudo-parallel data or use limited parallel data.
- 2.2 Unsupervised Maps: Optimal Transport: Classic optimal transport finds a minimum-cost plan between discrete embedding distributions, using a cost matrix and transport coupling with prescribed marginals.
- 2.2 Unsupervised Maps: Optimal Transport: Entropy regularization makes the optimal-transport problem more efficiently solvable through a strictly convex objective and Sinkhorn-Knopp matrix scaling.
- 2.2 Unsupervised Maps: Optimal Transport: Direct discrete OT is unsuitable for monolingual embeddings because arbitrary relative rotations can change cross-space vector costs and the resulting transport map.
- 2.2 Unsupervised Maps: Optimal Transport: Gromov-Wasserstein OT compares within-domain distances between point pairs, providing a theoretically motivated, efficient, single-step alignment without post-processing or heuristic adjustments.
3 Transporting across unaligned spaces
The Gromov-Wasserstein formulation aligns unpaired embedding spaces by comparing within-domain relational structure rather than requiring cross-domain distances. Its optimal coupling provides soft translation correspondences, while efficient first-order optimization and a two-step extension support larger vocabularies.
- 3.1 The Gromov Wasserstein Distance: Gromov-Wasserstein distance compares pairwise similarities within each domain, enabling alignment when cross-domain vector distances are unavailable.The formulation uses within-domain similarity matrices and a loss comparing corresponding similarity pairs.
- 3.1 The Gromov Wasserstein Distance: The optimization seeks a coupling that assigns transport mass between source and target points while minimizing relational discrepancy.The coupling specifies how much mass transfers between every pair of points, and the objective is defined over pairwise matches.
- 3.1 The Gromov Wasserstein Distance: Although the GW objective is non-linear, non-convex, and fourth-order, first-order optimization reduces the computation from naive fourth-order tensor complexity to a lower-order procedure.Each iteration solves a traditional optimal transport problem using a pseudo-cost matrix and projection onto the transport polytope.
- 3.1 The Gromov Wasserstein Distance: The optimal coupling directly yields probabilistic word translations, avoiding nearest-neighbor inference and heuristic hub-word corrections.The coupling entries provide translation likelihoods and are normalized by construction.
- 3.1 The Gromov Wasserstein Distance: Solving the GW problem also produces a distance between languages based on relational word-embedding structure.For suitable loss functions, these values are distances on metric measure spaces and can be compared across languages.
- 3.2 Scaling Up: For very large vocabularies, the method first aligns a subset with GW and then learns an orthogonal mapping to extend the correspondence out of sample.The projection is obtained in closed form through singular value decomposition and can map the remaining embeddings.
4 Experiments
The experiments evaluate Gromov-Wasserstein alignment across benchmark tasks, optimization settings, and qualitative language-distance analyses. The method shows stable optimization, benefits from cost-matrix normalization on a harder dataset, and yields relational language-distance patterns.
- 4 Experiments: The evaluation covers optimization dynamics, benchmark cross-lingual embedding tasks, and qualitative analysis of the learned distance between languages.Experiments use FASTTEXT embeddings and dictionaries from Conneau et al. (2018), plus a substantially harder dataset from Dinu et al. (2014).
- 4.1 Evaluation Tasks and Methods: The method is compared with supervised Procrustes and fully unsupervised approaches, using CSLS when nearest-neighbor retrieval is required.The comparison includes Zhang et al. (2017a), Artetxe et al. (2018), and Conneau et al. (2018).
- 4.2 Training Dynamics of G-W: Larger entropy regularization values produce smoother improvements and faster runtime per iteration, but reduce performance.The experiments also find faster convergence for closer language pairs such as EN–FR than for more distant pairs such as EN–RU.
- 4.2 Training Dynamics of G-W: The objective decreases monotonically, tracks translation quality, and avoids degradation from overtraining described for adversarial methods.These properties distinguish the optimization behavior from adversarial-training approaches.
- 4.3 Benchmark Results: Normalizing pairwise similarity matrices to the same range substantially improves results on the harder Dinu et al. dataset.The normalization addresses uneven cross-language distance matrices; tuning λ can also obviate the step, but normalization avoids tuning λ.
- 4.4 Qualitative Results: The learned Gromov-Wasserstein values act as distances between word-embedding spaces and reveal short distances among Romance languages, with classical Chinese most discrepant.The values are computed for the 2,000 most frequent words in each language and are scaled by 10^2 for visualization.
5 Related Work
Related work includes supervised or minimally supervised mappings, shared-space projections, and fully unsupervised adversarial or optimal-transport approaches. The paper positions Gromov-Wasserstein alignment as a concise alternative that directly produces correspondences.
- Methods with coarse or limited parallel data: Earlier methods learn mappings between embedding spaces or project both spaces into a common space, often using parallel data.Examples include least-squares and orthogonal transformations, as well as common-space projection methods.
- Fully Unsupervised methods: Fully unsupervised methods use adversarial training for initial alignment, followed by procedures such as Procrustes refinement or pseudo-match construction.The paper presents Gromov-Wasserstein as an alternative to these adversarial-training steps.
- Fully Unsupervised methods: A prior optimal-transport approach jointly optimizes transportation and Procrustes objectives, assumes invariance to unitary transformations, and repeatedly solves Procrustes problems.The paper contrasts this with its direct Gromov-Wasserstein formulation.
6 Discussion and future work
The paper concludes that Gromov-Wasserstein provides a direct, relational approach to cross-lingual word alignment that is efficient and robust. Scaling to large vocabularies remains a limitation because it requires an explicit Procrustes mapping.
- 6 Discussion and future work: Gromov-Wasserstein compares relational geometry across word-vector spaces rather than comparing word vectors directly.The resulting objective is concise and can be optimized efficiently.
- 6 Discussion and future work: The framework achieves near-state-of-the-art performance with computational cost orders of magnitude lower than alternative fully unsupervised methods.The authors characterize the resulting alignment as fast, stable, and robust.
- 6 Discussion and future work: Direct Gromov-Wasserstein optimization is feasible for reasonable sizes, but large vocabularies require learning an explicit Procrustes mapping.GPU computation or stochastic optimization may help avoid this secondary step.