Unsupervised Multilingual Alignment using Wasserstein Barycenter

Many natural language processing tasks, such as part-of-speech tagging, machine translation and speech recognition, rely on learning a distributed representation of words. Recent developments in computational linguistics and neural language modeling have shown that word embeddings can capture both semantic and syntactic information. This led to the development of the zero-shot learning paradigm as a way to address the manual annotation bottleneck in domains where other vector-based representations must be associated with word labels. This is a fundamental step to make natural language processing more accessible. A key input for machine translation tasks consists of embedding vectors for each word. Mikolov et al. (2013b) were the first to release their pre-trained model and gave a distributed representation of words. After that, more software for training and using word embeddings emerged.

The rise of continuous word embedding representations has revived research on the bilingual lexicon alignment problem Rapp (1995); Fung (1995), where the initial goal was to learn a small dictionary of a few hundred words by leveraging statistical similarities between two languages. Mikolov et al. (2013a) formulated bilingual word embedding alignment as a quadratic optimization problem that learns an explicit linear mapping between word embeddings, which enables us to even infer meanings of out-of-dictionary words Zhang et al. (2016); Dinu et al. (2015); Mikolov et al. (2013a). Xing et al. (2015) showed that restricting the linear mapping to be orthogonal further improves the result. These pioneering works required some parallel data to perform the alignment. Later on, Smith et al. (2017); Artetxe et al. (2017, 2018a) reduced the need of supervision by exploiting common words or digits in different languages, and more recently, unsupervised methods that rely solely on monolingual data have become quite popular Gouws et al. (2015); Zhang et al. (2017b, a); Lample et al. (2018); Artetxe et al. (2018b); Dou et al. (2018); Hoshen and Wolf (2018); Grave et al. (2019).

Encouraged by the success on bilingual alignment, the more ambitious task that aims at simultaneously and unsupervisedly aligning multiple languages has drawn a lot of attention recently.

A naive approach that performs all pairwise bilingual alignment separately would not work well, since it fails to exploit all language information, especially when there are low resource ones. A second approach is to align all languages to a pivot language, such as English Smith et al. (2017), allowing us to exploit recent progresses on bilingual alignment while still using information from all languages.

More recently, Chen and Cardie (2018); Taitelbaum et al. (2019b, a); Alaux et al. (2019); Wada et al. (2019) proposed to map all languages into the same language space and train all language pairs simultaneously. Please refer to the related work section for more details.

In this work, we first show that the existing work on unsupervised multilingual alignment (such as Alaux et al. (2019)) amounts to simultaneously learning an arithmetic “mean” language from all languages and aligning all languages to the common mean language, instead of using a rather arbitrarily pre-determined input language (such as English). Then, we argue for using the (learned) Wasserstein barycenter as the pivot language as opposed to the previous arithmetic barycenter, which, unlike the Wasserstein barycenter, fails to preserve distributional properties in word embeddings. Our approach exploits available information from all languages to enforce coherence among language spaces by enabling accurate compositions between language mappings. We conduct extensive experiments on standard publicly available benchmark datasets and demonstrate competitive performance against current state-of-the-art alternatives. The source code is available at https://github.com/alixxxin/multi-lang. ¹¹1Preliminary results appeared in first author thesis Lian, Xin (2020).

In this section we set up the notations and define our main problem: the multilingual lexicon alignment problem.

Given $m$ languages $\mathcal{L}_{1},\ldots,\mathcal{L}_{m}$, each represented by a vocabulary $\mathcal{V}_{i}$ consisting of $n_{i}$ respective words. Following Mikolov et al. (2013a), we assume a monolingual word embedding $\mathbf{X}_{i}=[\mathbf{x}_{i,1},\ldots,\mathbf{x}_{i,n_{i}}]^{\top}\in\mathds{R}^{n_{i}\times d_{i}}$ for each language $\mathcal{L}_{i}$ has been trained independently on its own data. We are interested in finding all pairwise mappings $\mathsf{T}_{i\to k}:\mathds{R}^{d_{i}}\to\mathds{R}^{d_{k}}$ that translate a word $\mathbf{x}_{i,j_{i}}$ in language $\mathcal{L}_{i}$ to a corresponding word $\mathbf{x}_{k,j_{k}}=\mathsf{T}_{i\to k}(\mathbf{x}_{i,j_{i}})$ in language $\mathcal{L}_{k}$. In the following, for the ease of notation, we assume w.l.o.g. that $n_{i}\equiv n$ and $d_{i}\equiv d$. Note that we do not have access to any parallel data, i.e., we are in the much more challenging unsupervised learning regime.

Our work is largely inspired by that of Alaux et al. (2019), which we review below first. Along the way we point out some crucial observations that motivated our further development. Alaux et al. (2019) employ the following joint alignment approach that minimizes the total sum of mis-alignment costs between every pair of languages:

where $Q_{i}\in\mathfrak{O}_{d}$ is a $d\times d$ orthogonal matrix and $P_{ik}\in\mathcal{P}_{n}$ is an $n\times n$ permutation matrix²²2Alaux et al. (2019) also introduced weights $\alpha_{ik}>0$ to encode the relative importance of the language pair $(i,k)$.. Since $Q_{i}$ is orthogonal, this approach ensures transitivity among word embeddings: $Q_{i}$ maps the $i$-th word embedding space $\mathbf{X}_{i}$ into a common space $\mathbf{X}$, and conversely $Q_{i}^{-1}=Q_{i}^{\top}$ maps $\mathbf{X}$ back to $\mathbf{X}_{i}$. Thus, $Q_{i}Q_{k}^{\top}$ maps $\mathbf{X}_{i}$ to $\mathbf{X}_{k}$, and if we transit through an intermediate word embedding space $\mathbf{X}_{t}$, we still have the desired transitive property $Q_{i}Q_{t}^{\top}\cdot Q_{t}Q_{k}^{\top}=Q_{i}Q_{k}^{\top}$.

The permutation matrix $P_{ik}$ serves as an “inferred” correspondence between words in language $\mathcal{L}_{i}$ and language $\mathcal{L}_{k}$. Naturally, we would again expect some form of transitivity in these pairwise correspondences, i.e., $P_{ik}\cdot P_{kt}\approx P_{it}$, which, however, is not enforced in (1). A simple way to fix this is to decouple $P_{ik}$ into the product $P_{i}^{\top}P_{k}$, in the same way as how we dealt with $Q_{i}$. This leads to the following variant:

where Eq. 3 follows from the definition of variance and $\bar{\mathbf{X}}$ in Eq. 4 admits the closed-form solution:

Thus, had we known the arithmetic “mean” language $\bar{\mathbf{X}}$ beforehand, the joint alignment approach of Alaux et al. (2019) would reduce to a separate alignment of each language $\mathbf{X}_{i}$ to the “mean” language $\bar{\mathbf{X}}$ that serves as the pivot. An efficient optimization strategy would then consist of alternating between separate alignment (i.e., computing $Q_{i}$ and $P_{i}$) and computing the pivot language (i.e., (5)).

We now point out two problems in the above formulation. First, a permutation assignment is a 1-1 correspondence that completely ignores polysemy in natural languages, that is, a word in language $\mathcal{L}_{i}$ can correspond to multiple words in language $\mathcal{L}_{k}$. To address this, we propose to relax the permutation $P_{i}$ into a coupling matrix that allows splitting a word into different words. Second, the pivot language in (5), being a simple arithmetic average, may be statistically very different from any of the $m$ given languages, see Figure 1 and below. Besides, intuitively it is perhaps more reasonable to allow the pivot language to have a larger dictionary so that it can capture all linguistic regularities in all $m$ languages. To address this, we propose to use the Wasserstein barycenter as the pivot language.

The advantage of using Wasserstein barycenter instead of the arithmetic average is that the Wasserstein metric gives a natural geometry for probability measures supported on a geometric space. In Figure 1, we demonstrate the difference between Wasserstein Barycenter and arithmetic average of two input distributions.

It is intuitively clear that the Wasserstein barycenter preserves the geometry of the input distributions.

We take a probabilistic approach, treating each language $\mathcal{L}_{i}$ as a probability distribution over its word embeddings:

where $p_{ij}$ is the probability of occurrence of the $j$-th word $\mathbf{x}_{j}^{i}$ in language $\mathcal{L}_{i}$ (often approximated by the relative frequency of word $\mathbf{x}_{j}^{i}$ in its training documents), and $\delta_{\mathbf{x}^{i}_{j}}$ is the unit mass at $\mathbf{x}_{j}^{i}$. We project word embeddings into a common space through the orthogonal matrix $Q_{i}\in\mathfrak{O}_{d}$. Taking a word $\mathbf{x}^{i}$ from each language $\mathcal{L}_{i}$, we associate a cost $c(Q_{1}\mathbf{x}^{1},\ldots,Q_{m}\mathbf{x}^{m})\in\mathds{R}_{+}$ for bundling these words in our joint translation. To allow polysemy, we find a joint distribution $\pi$ with fixed marginals $\pi_{i}$ so that the average cost

is minimized. If we fix $Q_{i}$, then the above problem is known as multi-marginal optimal transport Gangbo and Świkech (1998).

To simplify the computation, we take the pairwise approach of Alaux et al. (2019), where we set the joint cost $c$ as the total sum of all pairwise costs:

Interestingly, with this choice, we can significantly simplify the numerical computation of the multi-marginal optimal transport.

We recall the definition of Wasserstein barycenter $\nu$ of $m$ given probability distributions $\pi_{1},\ldots,\pi_{m}$:

where $\lambda\geq 0$ are the weights, and the (squared) Wasserstein distance $\mathsf{W}_{2}^{2}$ is given as:

The notation $\Gamma(\pi_{i},\mu)$ denotes all joint probability distributions (i.e. couplings) $\Pi_{i}$ with (fixed) marginal distributions $\pi_{i}$ and $\mu$. As proven by Agueh and Carlier (2011), with the pairwise distance (8), the multi-marginal problem in (7) and the barycenter problem in (9) are formally equivalent. Hence, from now on we will focus on the latter since efficient computational algorithms for it exist. We use the push-forward notation $(Q_{i})_{\#}\pi_{i}$ to denote the distribution of $Q_{i}\mathbf{x}^{i}$ when $\mathbf{x}^{i}$ follows the distribution $\pi_{i}$. Thus, we can write our approach succinctly as:

where the barycenter $\mu$ serves as the pivot language in some common word embedding space. Unlike the arithmetic average in (5), the Wasserstein barycenter can have a much larger support (dictionary size) than the $m$ given language distributions.

We can again apply the alternating minimization strategy to solve (11): fixing all orthogonal matrices $Q_{i}$, we find the Wasserstein barycenter using an existing algorithm of Cuturi and Doucet (2014) or Claici et al. (2018); fixing the Wasserstein barycenter $\mu$, we solve each orthogonal matrix $Q_{i}$ separately:

For fixed coupling $\Pi_{i}\in\mathds{R}^{n\times s}$, where $s$ is the dictionary size for the barycenter $\mu$, the integral can be simplified as:

Thus, using the well-known theorem of Schönemann (1966), $Q_{i}$ is given by the closed-form solution $U_{i}V_{i}^{\top}$, where $U_{i}\Sigma_{i}V_{i}^{\top}=\mathbf{X}_{i}^{\top}\Pi_{i}\mathbf{Y}$ is the singular value decomposition. Our approach is presented in Algorithm 1.

We evaluate our algorithm on two standard publicly available datasets: MUSE Lample et al. (2018) and XLING Glavas et al. (2019). The MUSE benchmark is a high-quality dictionary containing up to 100k pairs of words and has now become a standard benchmark for cross-lingual alignment tasks Lample et al. (2018). On this dataset, we conducted an experiment with 6 European languages: English, French, Spanish, Italian, Portuguese, and German. The MUSE dataset contains a direct translation for any pair of languages in this set. We also conducted an experiment with the XLING dataset with a more diverse set of languages: Croatian (HR), English (EN), Finnish (FI), French (FR), German (DE), Italian (IT), Russian (RU), and Turkish (TR). In this set of languages, we have languages coming from three different Indo-European branches, as well as two non-Indo-European languages (FI from Uralic and TR from the Turkic family) Glavas et al. (2019).

We briefly describe related work on supervised and unsupervised techniques for bilingual and multilingual alignment.

In this paper, we discussed previous attempts to solve the multilingual alignment problem, compared similarity between the approaches and pointed out a problem with existing formulations. Then we proposed a new method using the Wasserstein barycenter as a pivot for the multilingual alignment problem. At the core of our algorithm lies a new inference method based on an optimal transport plan to predict the similarity between words. Our barycenter can be interpreted as a virtual universal language, capturing information from all languages. The algorithm we proposed improves the accuracy of pairwise translations compared to the current state-of-the-art method..

We thank the reviewers for their critical comments and we are grateful for funding support from NSERC and Mitacs.