An Analysis of E uclidean vs. Graph-Based Framing for Bilingual Lexicon Induction from Word Embedding Spaces (2021)

Abstract: Much recent work in bilingual lexicon induction (BLI) views word embeddings as vectors in Euclidean space. As such, BLI is typically solved by finding a linear transformation that maps embeddings to a common space. Alternatively, word embeddings may be understood as nodes in a weighted graph. This framing allows us to examine a node’s graph neighborhood without assuming a linear transform, and exploits new techniques from the graph matching optimization literature. These contrasting approaches have not been compared in BLI so far. In this work, we study the behavior of Euclidean versus graph-based approaches to BLI under differing data conditions and show that they complement each other when combined. We release our code at https://github.com/kellymarchisio/euc-v-graph-bli .

## introduction bilingual lexicons are useful in many natural language processing tasks including constrained decoding in machine translation, cross-lingual information retrieval, and unsupervised machine translation. there is a large literature inducing bilingual lexicons from cross-lingual spaces. "mapping" methods based on solving the orthogonal procrustes problem and its generalizations are popular, where languages are mapped to a common space from which a lexicon is extracted. this has been successful when word embedding spaces are roughly isomorphic, but fails as embedding spaces diverge @xcite . rather than word embeddings in euclidean space, we can work with weighted graphs derived from embeddings. graphs may be full-connected or sparse to capture the underlying data manifold. for instance, we may create a similarity graph with words as nodes and cosine distance between word vectors as edges. the use of graphs in nlp has a rich history, for tasks as varied as summarization, part-of-speech tagging, syntactic parsing, information extraction, measures of semantic similarity, and evaluation of cross-lingual word embeddings @xcite @xcite . graphs can also represent rich relationships like hyponym/hypernym, syntactic roles, synonymy such as in wordnet @xcite and freebase @xcite . we focus on fully-connected graphs derived from pairwise cosine similarities between word embeddings. the euclidean view, exemplified by methods solving the procrustes problem, works with embedding spaces and assumes the existence of a linear transform that maps the spaces. the graph-based view works with graphs for each language and directly performs matching on edge pairs based on neighborhood information. this view is exemplified by graph matching methods that solve the quadratic assignment problem from the combinatorial optimization literature. @xcite and @xcite incorporate related techniques for bilingual lexicon induction. we use seeded graph matching @xcite as representative of this class of approach. figure 1 illustrates the differences between the framings; while they both exploit the idea that words with similar neighbors (in euclidean or graph space) should be translations of one another, they implement the idea in very different ways. we explore these two different views of bli. our main contributions are (a) a thorough comparison of euclidean vs. graph-based framings to bli under varying data conditions, and (b) a method for combining both approaches that achieves better performance than either alone. we organize our work into three main experimental setup and results sections. first, we compare standard algorithms of performing bli via solutions to the orthogonal procrustes problem ("procrustes", for short) and sgm in section 4; we find that their performance varies depending on the number of seeds. sgm appears better when using less seeds. second, as it is common to improve results by bootstrapping, we compare iterative versions of procrustes and sgm in section 5. we find that iterative procrustes improves much more rapidly than iterative sgm. we also introduce stochastic variants of the iterative algorithms to improve robustness and experiment with active learning setups. finally, we present our combined system which outperforms individual procrustes and sgm approaches in section 6. ## background bli begins with two word embedding matrices: @xmath0, and @xmath1. we assume seeds {(x 1 , y 1 ), (x 2 , y 2 ), ...(x s , y s )} are given, which are supervised labels indicating translation correspondence between vocabulary items in the languages. we sort the corresponding submatrices of x and y so each row of @xmath2. usually, s is strictly smaller than both n and m and the goal is to find translation correspondences in the remaining words. procrustes and linear transforms: the popular procrustes-based methods for bli (e.g. @xcite @xcite match seeds by calculating a linear transformation w by a variant of the below: if w is required to be orthogonal, then distances between points are unchanged by the transform and a closed form solution can be computed by singular value decomposition @xcite . once languages are mapped to the same space by w, nearest neighbor search finds additional translation pairs. if w is known, one can find translations by optimizing over permutations π: to extract lexicons, one performs nearest neighbor search on the transformed embeddings. to mitigate the hubness problem (where some words are close to too many others) @xcite , @xcite modifies the similarity using cross-domain similarity local scaling (csls) to penalize hubs. for x, y in embedding space v : csls(x, y) = 2 cos(x, y)avg(x, k)avg(y, k) ## experimental setup because there are three methods and results sections, we detail the experimental setup first. we evaluate on @xmath3. ## discussion & future directions though much work in bli takes a euclidean view and elicits solutions via methods such as solutions to the generalized procrustes problem, bli may also be viewed as a graph-based problem. parts of the graph-based view have appeared in existing work, but no one has yet to compare the different framings in the context of bli. we perform this analysis for two high-resource language pairs with well-trained embeddings from wikipedia, in a restricted data context. under our experimental settings, we find that: the amount of available seeds), so either may be favorable given the specific data context. sgm appears favorable with less seeds. 2. sgm can be run iteratively, but does not improve as rapidly as iterative procrustes. both benefit from stochasticity, and active learning can provide strong improvement. 3. procrustes and sgm can be effectively combined to outperform either alone. our work has limitations which should be addressed by future analyses. we use clean, welltrained embeddings from the same domain. previous work has shown procrustes to struggle with poorly-trained and low-resource word embedding spaces, and for well-trained embeddings in mismatched domains (e.g., @xcite . in these cases, sgm might benefit from a different distance metric. a detailed analysis should be performed when data is many-to-many, as translation is naturally a many-to-many task. one might revisit word vectors based on co-occurrence statistics. the size of training and test sets should be increased, as the presence of more synonyms/antonyms and other "distractor" words may elicit different behavior. there are computational considerations as we scale-up, particularly for sgm. ## related work matching words using vector representations began with vectors based on co-occurrence statis-tics. @xcite and @xcite induce bilingual lexica based on the principle that words that frequently co-occur in one language have translations that co-occur frequently in another. @xcite extend this by measuring similarity between words based on co-occurrence vectors and matching words across language by preserving these similarities. @xcite are the first to perform bli over word embeddings, estimating the transformation matrix using stochastic gradient descent. most recent work solves a variation of the generalized procrustes problem (e.g., @xcite @xcite @xcite @xcite @xcite . zhang et al. (2020) 2020 ) form csls similarity matrices, iteratively extract cliques, and map with procrustes. @xcite create a weighted graph of translation candidates then create word vectors with node2vec @xcite . @xcite use graphs for a source, target, and pivot language to iteratively extract translation pairs based on heuristics. our active learning approach is inspired by @xcite . ## conclusion we perform the first detailed analysis of the consequences of framing bli either as a euclidean problem solved by the common procrustes solution with nearest-neighbor search, or as a graph-based matching problem solved with sgm. we show that each performs differently under different data contexts, with sgm preferred with low amounts of seeds. we compare iterative versions of sgm and procrustes, and find that stochasticity benefits both. finally, we create a combined system that outperforms individual procrustes and sgm approaches.