Quantized W asserstein P rocrustes Alignment of Word Embedding Spaces (2022)

Abstract: Motivated by the widespread interest in the cross-lingual transfer of NLP models from high resource to low resource languages, research on Cross-lingual word embeddings (CLWEs) has gained much popularity over the years. Among the most successful and attractive CLWE models are the unsupervised CLWE models. These unsupervised CLWE models pose the alignment task as a Wasserstein-Procrustes problem aiming to estimate a permutation matrix and an orthogonal matrix jointly. Most existing unsupervised CLWE models resort to Optimal Transport (OT) based methods to estimate the permutation matrix. However, linear programming algorithms and approximate OT solvers via Sinkhorn for computing the permutation matrix scale cubically and quadratically, respectively, in the input size. This makes it impractical and infeasible to compute OT distances exactly for larger sample size, resulting in a poor approximation quality of the permutation matrix and subsequently a less robust learned transfer function or mapper. This paper proposes an unsupervised projection-based CLWE model called quantized Wasserstein Procrustes (qWP) that jointly estimates a permutation matrix and an orthogonal matrix. qWP relies on a quantization step to estimate the permutation matrix between two probability distributions or measures. This approach substantially improves the approximation quality of empirical OT solvers given fixed computational cost. We demonstrate that qWP achieves state-of-the-art results on the Bilingual lexicon Induction (BLI) task.

## introduction in natural language processing (nlp), the problem of aligning monolingual embedding spaces to induce a shared cross-lingual vector space has been shown not only to be useful in a variety of tasks such as bilingual lexicon induction (bli) @xcite @xcite , machine translation @xcite , cross-lingual information retrieval @xcite , but it plays a crucial role in facilitating the cross-lingual transfer of language technologies from high resource languages to low resource languages. cross-lingual word embeddings (clwes) represent words from two or more languages in a shared cross-lingual vector space in which words with similar meanings obtain similar vectors regardless of their language. there has been a flurry of work dominated by the so-called projection-based clwe models @xcite @xcite @xcite , which aim to improve clwe model performance significantly. projection-based clwe models learn a transfer function or mapper between two independently trained monolingual word vector spaces with limited or no cross-lingual supervision. famous among projection-based clwe models are the unsupervised projection-based clwe models (artetxe et al., 2017; lample et al., 2018; alvarez-melis & jaakkola, 2018; * work done while interning at visa research ## related work at the heart of cross-lingual nlp are clwe models. it has quickly evolved into a large subarea with a wide variety of approaches and perspectives, so we provide context by overviewing this work first. projection-based clwe models can be categorized into @xcite : 1) fully supervised projection-based clwe models, 2) weakly supervised projection-based clwe models, and 3) fully unsupervised projection-based clwe models. the main idea governing all clwe models is to independently train monolingual embeddings on large monolingual corpora in different languages or use pre-trained monolingual embeddings and then learn a transfer function to map them into a shared cross-lingual word vector space. the first fully supervised projection-based clwe model to learn a shared cross-lingual word vector space from monolingually-trained word embedding was proposed by @xcite . they learned a linear transform from the source embedding space to the target language by minimizing the sum of squared euclidean distance between the translation pairs of a seed dictionary based on the assumption that two embedding spaces exhibit similar geometric structures (i.e., approximately isomorphic). their model requires word-level supervision from several thousand seed translation dictionaries (dict). subsequent works by @xcite ; @xcite argued and proved that the quality of the learned clwes could be improved by modifying the objective function in @xcite . a more recent line of research has shown that the shared cross-lingual word vector space can be induced with weaker supervision from a small initial seed dictionary @xcite @xcite . weakly supervised projection-based clwe models start with a small initial seed dictionary; however, the initial seed dictionary is iteratively expanded through a self-learning procedure. for example, bootstrap procrustes (proc-b) @xcite is semi-supervised in that it starts with a small pairwise correspondence (of 500-1000 words), aligns those to infer a larger correspondence, and repeats applying procrustes alignment. the quest to eliminate cross-lingual supervision has led to the development of fully unsupervised projection-based clwe models. fully unsupervised projection-based clwe models use the topological similarities between monolingual embedding spaces to induce the shared cross-lingual vector space @xcite @xcite . the translation dictionaries are produced from scratch based on monolingual data only. ## background in this section, we describe the mathematical formulation of supervised projection-based clwe models and unsupervised projection-based clwe models. we also defined what the 2-wasserstein distance is and looked in detail at how the wasserstein-procrustes problem under the unsupervised clwe model is solved in practice. we define two monolingual embedding spaces as x, @xmath0, where n is the number of words, and d is the dimension of the monolingual word embeddings. supervised projection-based clwe models require word-level supervision from seed translation dictionaries such that word x i in x is the translation of word y i in y . the linear transformation, w * , from the source monolingual embedding space to the target monolingual embedding space is learned by solving the least square problem @xcite : @xcite , modified the objective function in eq. ( 1 ) to improve the quality of the learned clwes by unit length normalizing the word embeddings and imposing an orthogonality constraint on the linear transformation (w ) during training: unsupervised projection-based clwe models without any initial seed bilingual lexicon some unsupervised clwe models solves the wasserstein-procrustes problem (eq. 4) to jointly estimate the permutation matrix or alignment (p ) and linear transformation (w ) @xcite : the permutation matrix p * provides a one-to-one mapping or correspondence between the source and target samples. under unsupervised clwe models that solve the wasserstein-procrustes problem, we aim to estimate the two unknown variables w and p . one way to solve eq. ( 4 ) is by alternating the minimization of w and p . given p , we use the translation pairs obtained between the source and target spaces to learn the linear transformation, w * from eq. ( 2 ). similarly, given the linear transformation w * , eq. ( 4 ) is equivalent to minimizing the 2-wasserstein distance between xw and y to solve for the permutation matrix, p : equation ( 5 ) is the standard ot problem, and it can be solved using a linear programming solver, which has a computational cost of o n 3 log n . for a large n, a linear programming solver is impractical. another variant and approximation of the optimal transport problem were proposed by @xcite . this variant adds an entropic regularization term leading to the sinkhorn algorithm with a computational cost of o n 2 ϵ -2 : this section introduces our new unsupervised clwe model: quantized wasserstein procrustes (qwp). we use the previous stochastic algorithm framework and refinement procedure from @xcite and @xcite respectively in our model, but we rely on a quantization step to estimate the permutation matrix. ## experimental analysis we provide an evaluation of our proposed methods using english (en) and five languages embeddings pre-trained on wikipedia @xcite : spanish (es), french (fr), german (de), russian (ru), and italian (it). we use the 300-dimensional fasttext @xcite embeddings, and all vocabularies are trimmed to the 200k most frequent words. alignment evaluation tasks: bli we evaluate and compare our proposed clwe method mainly on the bilingual lexicon induction (bli) task, a word translation task. bli is more direct and has become the de facto evaluation task for clwe models. for words in the source language, this task retrieves the nearest neighbors in the target language after alignment to check if it contains the translation. we report two different translation accuracies: precision at 1 (p@1) and mean average precision (map) @xcite translation accuracy, which is equivalent to the mean reciprocal rank (mrr) of the translation. ## conclusion this paper presents an approach to aligning embeddings in high-dimensional space. while the overall problem is non-convex and computationally expensive, we present an efficient stochastic algorithm to solve the problem based on a refined sample set. this paper focuses on the matching procedure of the bli task. our key insight is that our quantization algorithm can outperform the current state-of-art unsupervised algorithm on both balanced and unbalanced settings of the loss function.