Title: EMPIRICAL OBSERVATIONS ON THE INSTABILITY OF ALIGNING WORD VECTOR SPACES WITH GANS

Abstract: Unsupervised bilingual dictionary induction (UBDI) is useful for unsupervised machine translation and for cross-lingual transfer of models into low-resource languages. One approach to UBDI is to align word vector spaces in different languages using Generative Adversarial Networks (GANs) with linear generators, achieving state-of-the-art performance for several language pairs. For some pairs, however, GAN-based induction is unstable or completely fails to align the vector spaces. We focus on cases where linear transformations provably exist, but the performance of GAN-based UBDI depends heavily on the model initialization. We show that the instability depends on the shape and density of the vector sets, but not on noise; that it is the result of local optima, but neither over-parameterization nor changing the batch size or the learning rate consistently reduces instability. Nevertheless, we can stabilize GAN-based UBDI through best-of-N model selection, based on an unsupervised stopping criterion.

1. INTRODUCTION:

A word vector space -also sometimes referred to as a word embedding -associates similar words in a vocabulary with similar vectors. Learning a projection of one word vector space into another, such that similar words -across the two word embeddings -are associated with similar vectors, is useful in many contexts, with the most prominent example being the alignment of vocabularies of different languages. This is a key step in machine translation of low-resource languages (Lample et al., 2018 ). An embedding of English words may associate thoughtful, considerate, and gracious with similar vectors, for example, but for English-Icelandic translation, it would be useful to have access to a cross-lingual word embedding space in which hugulsamur (lit.: 'thoughtful') was also associated with a similar vector. Such joint embeddings of words across languages can also be used to extract bilingual dictionaries.

Projections between word vector spaces have typically been learned from dictionary seeds. In seminal papers such as Mikolov et al. (2013) and Faruqui and Dyer (2014) , these seeds would comprise thousands of words, but Vulić and Korhonen (2016) showed that we can learn reliable projections from as little as 50 words. Smith et al. (2017) and Hauer et al. (2017) subsequently showed that the seed can be replaced with just words that are identical across languages; and Artetxe et al. (2017) showed that numerals can also do the job, in some cases; both proposals removing the need for an actual dictionary. Even more recently, a handful of papers have proposed an entirely unsupervised approach to projecting word vector spaces onto each other, based on Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) . We present the core idea behind such approaches in §3, but briefly put, GANs are used to learn a linear transformation to minimize the divergence between a target distribution (say the Icelandic embeddings) and a source distribution (the English embeddings projected into the Icelandic space).

The possibility of unsupervised bilingual dictionary induction (UBDI) has seemingly removed the data bottleneck in machine translation, evoking the idea that we can now learn to translate without human supervision (Lample et al., 2018 ). Yet, it remains an open question whether the initial, positive results extrapolate to real-world scenarios of learning translations between low-resource language pairs. Søgaard et al. (2018) recently presented results suggesting that UBDI is challenged by some language pairs exhibiting very different morphosyntactic properties, as well as when the monolingual corpora are very different. In this paper, we identify easy, hard, and impossible instances Under review as a conference paper at ICLR 2019 of GAN-based UBDI, and apply a simple test for discriminating between them. The hard cases exhibit instability, i.e. their success depends heavily on initialization. We set up a series of experiments to investigate these hard cases.

Our contributions:

We introduce a distinction between easy, hard, and impossible alignment problems over pairs of word vector spaces and show that a simple linearity test can be used to tell these cases apart. We show that the impossible cases are caused not necessarily by linguistic differences, but rather by properties of the corpora and the embedding algorithms. We also show that in the hard cases, the likelihood of being trapped in local minima depends heavily on the shape and density of the vector sets, but not on noise. Changes in the number of parameters, batch size, and learning rate do not alleviate the instability. Yet, using an unsupervised model selection method over N different initializations to select the best generators, leads to a 6.74% average error reduction over standard MUSE.

Structure of the paper §2 presents MUSE (Conneau et al., 2018) , an approach to GAN-based UBDI. Here we also discuss theoretical results from the GAN literature, relevant to our case, and show a relation to a common point set registration method. In §3, we use a test based on Procrustes Analysis to discriminate between easy, hard, and impossible cases, discussing its relation with tests of isomorphism and isospectrality. We then focus on the hard cases, where linear transformations provably exist, but GANs exhibit considerable instability. Through a series of experiments, we analyze what affects the instability of GAN-based UBDI. §4 presents our unsupervised best-of-N model selection method for stabilizing GAN-based UBDI.

2. UNSUPERVISED ALIGNMENT USING GANS:

In this section, we discuss the dynamics of GAN-based UBDI and how the training behavior of GANs can help us understand their limitations as applied to UBDI. Two families of approaches to UBDI exist: using GANs (Barone, 2016; Conneau et al., 2018; Zhang et al., 2017) and using iterative closest point (Hoshen and Wolf, 2018) . We focus on GAN-based UBDI, and more specifically on MUSE (Conneau et al., 2018) , but at the end of this section we establish a relation between the two families of algorithms.

A GAN consists of a generator and a discriminator. The generator G is trained to fool the discriminator D. The generator can be any differentiable function; in MUSE, it is a linear transform Ω. Let e ∈ E be an English word vector, and f ∈ F a French word vector, both of dimensionality d. The goal of the generator is then to choose Ω ∈ R d×d such that ΩE has a distribution close to F . The discriminator is a map D w : X → {0, 1}, implemented in MUSE as a multi-layered perceptron. The objective of the discriminator is to discriminate between vector spaces F and ΩE. During training, the model parameters Ω and w are optimized using stochastic gradient descent by alternately updating the parameters of the discriminator based on the gradient of the discriminator loss and the parameters of the generator based on the gradient of the generator loss, which, by definition, is the inverse of the discriminator loss. The loss function used in MUSE and in our experiments below is cross-entropy. In each iteration, we sample N vectors e ∈ E and N vectors f ∈ F and update the discriminator parameters w according to

w → w + α N i=1 ∇[log D w (f i ) + log(1 -D w (G Ω (e i )]

Theoretically, the optimal parameters are a solution to the min-max problem:

min Ω max w E[log(D w (F )) + log(1 -D w (G Ω (E)))], which reduces to min Ω JS (P F | P Ω ).

If a generator wins the game against an ideal discriminator on a very large number of samples, then F and ΩE can be shown to be close in Jensen-Shannon divergence, and thus the model has learned the true data distribution. This result, referring to the distributions of the data, p data , and the distribution, p g , G is sampling from, is from Goodfellow et al. (2014) : If G and D have enough capacity, and at each step of training, the discriminator is allowed to reach its optimum given G, and p g is updated so as to improve the criterion

E x∼p data [log D * G (x)] + E x∼pg [log(1 -D * G (x))]

then p g converges to p data . This result relies on a number of assumptions that do not hold in practice. The generator in MUSE, which learns a linear transform Ω, has very limited capacity, for example, and we are updating Ω rather than p g . In practice, therefore, during training, MUSE alternates between k steps of optimizing the discriminator and one step of optimizing the generator. Another common problem with training GANs is that the discriminator loss quickly drops to zero, when there is no overlap between p g and p data (Arjovsky et al., 2017) ; but note that in our case, the discriminator is initially presented with IE and F , for which there is typically no trivial solution, since the embedding spaces are likely to overlap. We show in §4 that discriminator and generator loss are poor model selection criteria, however; instead we propose a simple criterion based on cosine similarities between nearest neighbors in the learned alignment.

From ΩE and F , we can extract a bilingual dictionary using nearest neighbor queries, i.e., by asking what is the nearest neighbor of ΩE in F , or vice versa. MUSE uses a normalized nearest neighbor retrieval method to reduce the influence of hubs (Radovanović et al., 2010; Dinu et al., 2015) . The method is called cross-domain similarity local scaling (CSLS) and used to expand high-density areas and condense low-density ones. The mean similarity of a source language embedding Ωe to its k nearest neighbors in the target language (k = 10 suggested) is defined as

µ k E (Ω(e)) = 1 k k i=1 cos(e, f i ),

where cos is the cosine similarity. µ F (f i ) is defined in an analogous manner for every i. CSLS(e, f i ) is then calculated as 2cos(e, f i ) -µ E (Ω(e)) -µ F (f i ). MUSE uses an unsupervised validation criterion based on CSLS. The translations of the top 10k most frequent words in the source language are obtained with CSLS and average pairwise cosine similarity is computed over them. This metric is considered indicative of the closeness between the projected source space and the target space, and is found to correlate well with supervised evaluation metrics. After inducing a bilingual dictionary, E d and F d , by querying ΩE and F with CSLS, MUSE performs a refinement step based on the Procrustes algorithm (Schönemann, 1966) , whereby the singular value decomposition of F T d E d , computed as U ΣV T , gives Ω = U V T . The idea of minimizing nearest neighbor similarity for unsupervised model selection is also found in point set registration and lies at the core of iterative closest point (ICP) optimization (Besl and McKay, 1992) . ICP typically minimizes the λ 2 distance (mean squared error) between nearest neighbor pairs. The ICP optimization algorithm works by assigning each transformed vector to its nearest neighbor and then computing the new relative transformation that minimizes the cost function with respect to this assignment. ICP can be shown to converge to local optima (Besl and McKay, 1992) , in polynomial time (Ezra et al., 2006) . ICP easily gets trapped in local optima, however, exact algorithms only exist for two-and three-dimensional point set registration, and these algorithms are slow (Yang et al., 2016) . Generally, it holds that the optimal solution to the GAN min-max problem is also optimal for ICP. To see this, note that a GAN minimizes the Jensen-Shannon divergence between F and ΩE. The optimal solution to this is F = ΩE. As sample size goes to infinity, this means the L 2 loss in ICP goes to 0. In other words, ICP loss is minimal if an optimal solution to the UBDI min-max problem is found. ICP was independently proposed for UBDI in Hoshen and Wolf (2018) . They report their method only works using PCA initialization. We explored PCA initialization for MUSE, but observed the opposite effect, namely that PCA initialization leads to a degradation in performance.

3. WHEN AND WHY IS UNSUPERVISED ALIGNMENT HARD?:

A function Ω from E to F is a linear transformation if Ω(f + g) = Ω(f ) + Ω(g) and Ω(kf ) = kΩ(f ) for all elements f, g of E, and for all scalars k. An invertible linear transformation is called an isomorphism. The two vector spaces E and F are called isomorphic, if there is an isomorphism from E to F . Equivalently, if the kernel of a linear transformation between two vector spaces of the same dimensionality contains only the zero vector, it is invertible and hence an isomorphism. Most work on supervised or unsupervised alignment of word vector spaces relies on the assumption that they are approximately isomorphic, i.e., isomorphic after removing a small set of vertices (Mikolov et al., 2013; Barone, 2016; Zhang et al., 2017; Conneau et al., 2018) . In this section, show that word vector spaces are not necessarily approximately isomorphic. We will refer to cases of non-approximately isomorphic word vector spaces as impossible cases. The possible cases can be further divided into easy and hard cases; corresponding to the cases where GAN-based UBDI is stable and unstable (i.e., performance is highly dependent on initialization), respectively. It is not difficult to see why hard cases may arise when using GANs for unsupervised alignment of vector spaces. One example of a hard (but not impossible) problem instance is the case of two smoothly populated vector spaces on unit spheres. In this case, there is an infinite set of equally good linear transformations (rotations) that achieve the same training loss. Similarly, for two binary-valued, n-dimensional vector spaces with one vector in each possible position. Here the number of local optima would be 2 n , but since the loss is the same in each of them the loss landscape is highly non-convex, and the basin of convergence is therefore very small (Yang et al., 2016) . The chance of aligning the two spaces using gradient descent optimization would be1 2 n . In other words, minimizing the Jensen-Shannon divergence between the word vector distributions, even in the easy case, is not always guaranteed to uncover an alignment between translation equivalents. From the above, it follows that alignments between linearly alignable vector spaces cannot always be learned using UBDI methods. In §3.1 , we test for approximate isomorphism to decide whether two vector spaces are linearly alignable. §3.2-3.3 are devoted to analyzing when alignments between linearly alignable vector spaces can be learned.

In our experiments in §3 and 4, Bengali and Cebuano embeddings are pretrained by FastText; 1 all others are trained using FastText on Polyglot. 2 In the experiments in §5, we use FastText embeddings pretrained on Wiki and Common Crawl data. 3 If not indicated otherwise, we use MUSE with default parameters (Conneau et al., 2018) .

3.1. LINEAR ALIGNABILITY AND GRAPH SIMILARITY:

Procrustes fit (Kementchedjhieva et al., 2018) is a simple linearity test, which, as we find, captures the dynamics of GAN-based UBDI well. Compared to isomorphism and isospectrality tests, Procrustes fit is inexpensive and can be run with bigger dictionary seeds. Procrustes fit The idea behind this test is to apply a Procrustes analysis (see §2) on a sizeable dictionary seed (5000 tokens), to measure the training fit. Since U V T E = F if and only if E and F are isomorphic, the Procrustes fit tests the linear alignability between two embedding spaces exists. We can correlate the Procrustes fit measure with the performance of UBDI. While UBDI is motivated by cases where dictionary seeds are not available, and Procrustes fit relies on dictionary seeds, a strong correlation can act as a sanity check on UBDI, as well as a tool to help us understand its limitations. The relationship between Procrustes fit and UBDI performance is presented in Figure 1 and shows a very strong correlation. One immediate conclusion is that the poor UBDI performance on languages such as Bengali and Cebuano is not a result of GANs being a poor estimator of the linear transforms, but rather a result of there not being a good linear transform from English into these languages. 4Isomorphism and isospectrality We briefly compare Procrustes fit to two similarity measures for nearest neighbor graphs of vector spaces, introduced in Søgaard et We say that the nearest neighbor graphs are k-subgraph isomorphic if the nearest neighbor graphs for the most frequent k words (in the source language and their translations) are isomorphic. There are exact algorithms, e.g., VF2 (Cordella et al., 2001) , for checking whether two nearest neighbor graphs are graph isomorphic. These algorithms do not scale easily to graphs with hundreds of thousands of nodes, however. Also, the algorithms do not identify approximate isomorphism, unless run on all subgraphs with k vertices removed. Such tests are therefore impractical. Søgaard et al. (2018) instead introduce a spectral metric based on eigenvalues of the Laplacian of the nearest neighbor graphs, similar to metrics used for graph matching problems in computer vision (Reuter et al., 2005) and biology (Lewitus and Morlon, 2016) . The metric quantifies to what extent the nearest neighbor graphs are isospectral. Note that (approximately) isospectral graphs need not be (approximately) isomorphic, but (approximately) isomorphic graphs are always (approximately) isospectral. Let A 1 and A 2 be the adjacency matrices of the nearest neighbor graphs G 1 and G 2 of our two word embeddings, respectively. Let L 1 = D 1 -A 1 and L 2 = D 2 -A 2 be the Laplacians of the nearest neighbor graphs, where D 1 and D 2 are the corresponding diagonal matrices of degrees.

We then compute the eigensimilarity of the Laplacians of the nearest neighbor graphs, L 1 and L 2 .

For each graph, we find the smallest k such that the sum of the k largest Laplacian eigenvalues is <90% of the Laplacian eigenvalues. We take the smallest k of the two, and use the sum of the squared differences between the largest k Laplacian eigenvalues

∆: ∆ = k i=1 (λ 1i -λ 2i ) 2 , where k is chosen s.t. min j { k i=1 λj i n i=1 λji > 0.

9}. Note that ∆ = 0 means the graphs are isospectral, and the metric goes to infinite. Thus, the higher ∆ is, the less similar the graphs (i.e., their Laplacian spectra). Isospectrality varies with Procrustes fit; to see this, we show that

k i=1 (λ Ei -λ Fi ) 2 varies with fi∈F d ,ei∈U V T (E d ) |f i = CSLS (e i )|. If E = F , it holds that k i=1 (λ 1i -λ 2i ) 2 = 0. Since U V T = arg min Ω ||ΩE -F || 2

F , in this case Ω = I. Two isomorphic graphs also have the same set of sorted eigenvalues, i.e., k i=1 (λ 1i -λ 2i ) 2 = 0. In general, it holds that if we add an edge to a graph G, to form G , its spectrum changes monotonically (So, 1999) . Since the Procrustes fit evaluates the nearest neighbor graph, it follows that a change in the nearest neighbor graph leading to a drop in Procrustes fit will also lead to a drop in eigenvector similarity. However, isomorphism and isospectrality tests are computationally expensive, and in practice, we have to sample subgraphs and run the tests on multiple subgraphs, which leads to a poor approximation of the similarities of the two embedding graphs.

In practice, Procrustes fit, k-subgraph isomorphism, and k-subgraph isospectrality thus all rely on a dictionary. The tests are therefore not diagnostic tools, but means to understand the dynamics of UBDI. Procrustes fit is more discriminative (since vector space isomorphism entails nearest neighbor graph isomorphism, not vice versa) and computationally more efficient. In our experiments, it also correlates much better with UBDI performance (MUSE in Table 2 ; the correlation coefficient is 96%, compared to 0% for k-subgraph isomorphism (not listed in Table 2 ), and -27% for k-subgraph isospectrality with k = 10.

Observation 1 Impossible cases are not (solely) the result of linguistic differences, but also of corpus characteristics. English-Bengali and English-Cebuano are not linearly alignable according to our Procrustes fit tests. There can be two explanations for such an observation: linguistic differences between the two languages or variance in the monolingual corpora for Bengali and Cebuano, i.e. noise and little support per word. We test for this by applying the Procrustes fit test to the word vector spaces of Bengali and a higher resource related language, Hindi. The Procrustes fit for Bengali-Hindi is even lower than for compared to 46.25, respectively) . This finding is surprising as we would expect Bengali and Hindi to align well due to their relatedness. The result thus suggests that the Bengali embeddings are of insufficient quality, which can largely explain the poor alignment found by the GAN. This is further supported by follow-up experiments we ran aligning a word vector space for English and a word vector space induced from scrambled English sentences (learned on two different 10% samples of Wikipedia), which can be thought of as a sample from a synthetic language that completely diverges from English in its syntactic properties.5 GAN-based UBDI was able to near-perfectly recover the word identities without supervision, showing that its success is not easily impeded by linguistic differences.

Observation 2 Impossible cases can also be the result of the inductive biases of the underlying word embedding algorithms. One observation made in Conneau et al. (2018) is that the performance of MUSE degrades a little when using alternative embedding algorithms, but that alignment is still possible. We, however, observe that this is not the case if using different, monolingual embedding algorithms, i.e., if using FastText for English and Hyperwords for Spanish. While such embeddings are still linearly alignable (as verified by computing their Procrustes fits), GAN-based UBDI consistently fails on such cases. This also holds for the case of aligning FastText for English and Hyperwords for English, as observed in Hartmann et al. (2018) .

3.2. ABLATION TRANSFORMATIONS:

In order to better understand the dynamics of GAN-based UBDI in hard cases, i.e., when the GAN suffers from local minima, we introduce three ablation transformations, designed to control for properties of the word vector spaces: unit length normalization, PCA-based pruning, and noising. The results of GAN-based UBDI after applying these transforms are reported in Table 2 .

Observation 3 GAN-based UBDI becomes more unstable and performance deteriorates with unit length normalization. This ablation transform performs unit length normalization (ULN) of all vectors x, i.e., x = x ||x|| 2 , and is often used in supervised bilingual dictionary induction (Xing et al., 2015; Artetxe et al., 2017) . We use this transform to project word vectors onto a sphere -to control for shape information. If vectors are distributed smoothly over two spheres, there is no way to learn an alignment in the absence of dictionary seed; in other words, if UBDI is unaffected by this transform, UBDI learns from density information alone. While supervised methods are insensitive to or benefit from ULN, we find that UBDI is very sensitive to such normalization (see Table 2 , M-unit). We verify that supervised alignment is not affected by ULN by checking the Procrustes fit ( §3.1), which remains unchanged under this transformation.

Observation 4 GAN-based UBDI becomes more unstable and performance deteriorates with PCA pruning. In order to control for density, we apply PCA to our word vector spaces, reducing them to 25 dimensions, and prune our vocabularies to remove density clusters by keeping all but one of the nearest neighbors vectors on an integer grid. This removes about 10% of our vocabularies. We then apply UBDI to the original vectors for the remaining words. This smoothening of the embeddings results in highly unstable and reduced performance (see Table 2 , M-PCA). In other words, density information, while less crucial than shape information, is important for the stability of UBDI, possibly by reducing the chance of getting stuck in local optima. This is in contrast with the results on using ICP for UBDI in Hoshen and Wolf (2018) , who report significant improvements EASY HARD IMPOSSIBLE es el et fi hu pl bn ceb P@1 fail P@1 fail P@1 fail P@1 fail P@1 fail P@1 fail P@1 fail P@1 fail MUSE (a) Discriminator loss (green), P@1 (blue) and mean cosine similarity (red) for generators along the line segment from the (failed) unsupervised GAN solution to the supervised Procrustes fit. α is the interpolation parameter.

el hu P@1 P@1 fail P@1 P@1 fail ( 10 using PCA initialization with 50 dimensions. We ran experiments with 25, 50, and 100 dimensions, with or without pruning, observing significant drops in performance across the board.

Observation 5 GAN-based UBDI is largely unaffected by noise injection. We add 25% random vectors, randomly sampled from a hypercube bounding the vector set. GAN-based UBDI results are not consistently affected by noise injection (see Table 2 , M-noise). This is because the injected vectors rarely end up in the seed dictionaries used for the Procrustes analysis step.

3.3. OVER-PARAMETERIZATION, BATCH SIZE, AND LEARNING RATE:

In follow-up experiments on Greek and Hungarian, we find that GAN-based UBDI gets stuck in local optima in hard cases, and over-parameterization, increasing batch size or decreasing learning rate does not help.

Observation 6 In the hard cases, GAN-based UBDI gets stuck in local optima. In cases where linear alignment is possible, but UBDI is unstable, the model might get stuck in a local optimum, which is the result of the discriminator loss not increasing in the region around the current discriminator model. We analyze the discriminator loss in these areas by plotting it as a function of the generator parameters for the failure cases of two of the hard alignment cases, namely English-Greek and English-Hungarian. We plot the loss surface along its intersection with a line segment connecting two sets of parameters (Goodfellow et al., 2015; Li et al., 2018) . In our case, we interpolate between the model induced by GAN-based UBDI and the (oracle) model obtained using supervised Procrustes analysis. Result are shown in Figure 2a . The green loss curves represent the current discriminator's loss along all the generators between the current generator and the generator found by Procrustes analysis. In all cases, we see that while performance (P@1 and mean cosine similarity) goes up, there is an initial drop in the discriminator loss, which suggests there is no learning signal in this direction for GAN-based UBDI. This is along a line segment representing the shortest path from the failed generator to the oracle generator, of course; linear interpolation provides no guarantee there are no almost-as-short paths with plenty of signal. A more sophisticated sampling method is to sample along two random direction vectors Goodfellow et al. (2015) ; Li et al. (2018) . We used an alternative strategy of sampling from normal distributions with fixed variance that were orthogonal to the line segment. We observed the same pattern, leading us to the conclusion that instability is caused by local optima.

Observation 7 Over-parameterization does not consistently help in the hard cases. Recent work has observed that over-parameterization leads to smoother loss landscapes and makes optimization easier (Brutzkus et al., 2018) . We experiment with widening our discriminators to smoothen the loss landscape, but results are inconsistent: for Hungarian, this made GAN-based UBDI more stable; for Greek, less stable (see Figure 2b ).

Observation 8 Changing the batch size or the learning rate to hurt the discriminator also does not help. Previous work has shown that large learning rate and small batch size contribute towards SGD finding flatter minima (Jastrzebski et al., 2018) , but in our experiments, we are interested in the discriminator not ending up in flat regions, where there is no signal to update the generator. We therefore experiment with smaller learning rate and larger batch sizes. The motivation behind both is decreasing the scale of random fluctuations in the SGD dynamics (Smith and Le, 2017; Balles et al., 2017) , enabling the discriminator to explore narrower regions in the loss landscape. See Figure 2b for results. Increasing the batch size or varying the learning rate (up or down) clearly comes at a cost, and it seems the MUSE default hyperparameters are close to optimal.

4. UNSUPERVISED MODEL SELECTION:

In this section, we compare two unsupervised model selection criteria. We train three models with different random seeds in parallel and use the selection criterion to select one of these models to train for the remaining epochs. The first criterion is the discriminator loss during training, which is used in Daskalakis et al. (2018) , for example. In contrast, we propose to use the mean cosine similarity between all translations predicted by the CSLS method (see §2), which was used as an unsupervised stopping criterion by Conneau et al. (2018) .

Observation 9 In the hard cases, model selection with cosine similarity can stabilize GAN-based UBDI. As we see in Table 2 , the selection criterion based on discriminator loss (M-discr) increases the instability of UBDI, leading to 4/10 failed alignments for Greek compared to 2/10 without model selection, for example. Cosine similarity (M-cosine) in contrast leads to perfectly stable UBDI. Note that if the probability of getting stuck in a local optimum that leads to a poor alignment is β, using n random restarts and oracle model selection we increase the probability of finding a good alignment to 1 -(1 -β) n . In our experiments, n = 3.

5. CONCLUSIONS:

Some pairs of word vector spaces are not alignable based on distributional information alone. For other pairs, GANs can be used to induce such an alignment, but the degree of instability is very susceptible to the shape and density of the word vector spaces, albeit not to noise. Instability is caused by local optima, but not remedied by standard techniques such as over-parameterization, increasing the batch size or decreasing the learning rate. We propose an unsupervised model selection criterion that enables stable learning, leading to a ~7% error reduction over MUSE, and present further observations about the alignability of word vector distributions.

:

https://github.com/facebookresearch/MUSE

https://polyglot.readthedocs.io/

https://fasttext.cc/docs/en/crawl-vectors.html

We also experimented with learning non-linear alignment using GANs with non-linear generators, specifically, a generator with two hidden layers connected by a non-linearity. Our results on Spanish were much poorer than with linear generators, as expected: 35.9 with tanh; 0.0 with sigmoid; 21.4 with relu. On Cebuano, where the linear generator failed, we observed the same result with all three non-linear approaches: P@1 = 0.0 (All numbers are averaged

over 5 runs).

The context window for learning the embeddings is smaller than the average sentence length, which ensures that words in scrambled English are seen in different contexts than in regular English.

Figures and Tables:

Figure 1: Correlation of UBDI performance (P@1; x-axis) with Procrustes fit (y-axis)

Figure 2: Follow-up experiments on Greek (el) and Hungarian (hu)

Dataset properties. See §3.1 for Procrustes fit. k-Isospectrality is k-subgraph isospectrality ( §3.1). Directionality is the variance in the inner products with means(Mimno and Thompson, 2017). Languages are Spanish (es), Greek (el), Estonian (et), Finnish (fi), Hungarian (hu), Polish (pl), Bengali (bn), and Cebuano (ceb). Directionality scores for Bengali and Cebuano are not comparable. graph of a word vector space is obtained by adding edges between any word vertex and its nearest neighbor. Note that only cycles of length 2 are possible in a nearest neighbor graph. Two nearest neighbor graphs are graph isomorphic if they contain the same number of vertices connected in the same way. Two isomorphic vector spaces have isomorphic nearest neighbor graphs, but not vice versa.

Table content: <table><tr><td>al. (2018). The nearest neighbor</td></tr></table>

Main experiments; average performance and stability across 10 runs. We consider a P@1 score below 1% a fail. MUSE is the MUSE system with default parameters. Ablation transforms: M-unit uses unit length normalization to evaluate the impact of shape; M-PCA uses PCA-based pruning to evaluate the impact of density; M-noise uses 25% random vectors injected in the target language space to evaluate the impact of noise. M-discr uses discriminator loss for model selection, as a baseline for M-cosine; M-cosine uses our model selection criterion. The macro-averaged error reduction of M-cosine over MUSE for the HARD languages is 7%; and 4% across all language pairs.

Table content: <table/>

Peer review (iclr2019):
 The recent methods on learning cross-lingual word embeddings without any bilingual supervision (i.e., in a fully unsupervised way) have generated a lot of traction in NLP and beyond. Follow-up papers from Artetxe et al. (ICLR 2018), and Lample et al. (ICLR 2018, EMNLP 2018) have shown that such cross-lingual word embeddings can seed unsupervised (neural and statistical) machine translation, and other applications are also possible (e.g., unsupervised cross-lingual retrieval). This paper in particular focuses on further empirical analyses related to previously observed instability of unsupervised mapping-based approaches for learning unsupervised cross-lingual word embeddings, but remains focused on the task of unsupervised bilingual dictionary induction (UBDI). The paper is largely a continuation of the preliminary paper which focuses on the same problem and research question: the paper of Sogaard et al. (ACL 2018). In fact, this paper reads a lot like a more elaborated (or incremental) version of the preliminary paper of Sogaard et al. (ACL 2018), with the paper structure and some descriptions borrowed from the previous work (e.g., the focus on the MUSE algorithm, the description of k-isospectrality), with two main enhancements compared to the prior work: 1) The introduction of Procrustes fit as a means to diagnose and anticipate (im)possibility of unsupervised embedding learning. Arguably, the proposed diagnostic tool is more efficient than the alternatives; 2) A very simple method for unsupervised model selection (Section 4) based on the mean cosine similarity predicted by the CSLS method. Although some of the listed empirical observations are very straightforward if the reader knows anything about the entire procedure, it is good to see them empirically supported and presented in a very organised fashion. However, the two main methodological contributions of the paper seem quite thin to me. First, the method for unsupervised model selection is based on the unsupervised stopping criterion of Conneau et al. (2018) and it is a very simple (even simplistic) idea which happens to work well in practice already. Second, I am not fully bought by the Procrustes fit test and its comparison to two other tests has to be further examined, especially its relation to two similarity measures from Sogaard et al. For instance, k-subgraph isospectrality in the work of Sogaard et al also displayed a very strong correlation with UBDI performance (>0.9), while the authors in this paper claim that the correlation coefficient with their data in this paper is -27% for the same method. Could the authors explain the discrepancy? The authors claim that the Procrustes fit is much less computationally demanding as a test than the two alternative tests. However, I would like to see this claim empirically validated by running some actual tests and measuring test times. How are the two alternative tests impractical if they were used previously by Sogaard et al.? Some observations have been already confirmed in prior work. For instance, Observation 2 is already analysed in the work of Sogaard et al. Observation 3 and Observation 5 are also straightforward given the technicalities and hyper-parameter setup of the MUSE procedure. I wonder if the authors are aware of the more recent work on UBDI from Artetxe et al. (ACL 2018). A crucial analysis for this paper should focus on Artetxe*s more recent work rather than the MUSE algorithm. I acknowledge the fact that this field in particular is moving rapidly, but the paper would be much more impactful by focusing on the more recent and more appropriate starting ground rather than recycling the ideas already covered in prior work (e.g., in Sogaard et al.*s paper). The paper operates only in the fully unsupervised setting, which is, in my opinion, an artificial (even "artistic" setting). As Artetxe et al. (ACL 2017) showed and Sogaard et al. verified: relying on some sort of supervision (identical words, cognates, even numerals for languages with different scripts) already mitigates the problems of instability to a large extent. Why would we want to tie our analysis only to the fully unsupervised setting and go about it at length when it seems obvious that some sort of (cheap) supervision can already help the mapping-based algorithms to a large extent? I would like to see more experiments in such weakly-supervised settings. I would also like to see if the model selection criterion is applicable to this more real-life setting. Although I am happy to see a clear division into possible and impossible UBDI setups, the paper also does not provide any solutions (or rules of thumb) on how to proceed if we end up having an impossible setup. What are the alternatives to the fully unsupervised BDI? I am also missing explanations to some empirical observations: e.g., while the discrepancy between this work and the original work of Hoshen and Wolf has been reported, there is no insight on what causes the discrepancy and how this could be theoretically justified. In simple words, it is just observed, without getting a proper explanation supporting it. The paper is very well written and easy to follow, but my impression is that, as an empirically driven paper, it could contribute from further experimentation as well as from linking key empirical findings to theoretical justifications. Also, the two main contributions of the work are not so substantial and overall the paper mostly proves an already established fact: that fully unsupervised models for cross-lingual word embedding learning are very unstable and their success relies on a large spectrum of design choices and hyper-parameters. I would also like to see the analysis expanded beyond UBDI to other (more downstream) tasks where such low-resource representation learning regimes might be useful.