Bilingual Lexicon Induction for Low-Resource Languages using Graph Matching via Optimal Transport (2022)

Abstract: Bilingual lexicons form a critical component of various natural language processing applications, including unsupervised and semisupervised machine translation and crosslingual information retrieval. In this work, we improve bilingual lexicon induction performance across 40 language pairs with a graph-matching method based on optimal transport. The method is especially strong with low amounts of supervision.

## introduction bilingual lexicon induction (bli) from word embedding spaces is a popular task with a large body of existing literature (e.g. @xcite @xcite @xcite . the goal is to extract a dictionary of translation pairs given separate language-specific embedding spaces, which can then be used to bootstrap downstream tasks such as cross-lingual information retrieval and unsupervised/semi-supervised machine translation. a great challenge across nlp is maintaining performance in low-resource scenarios. a common criticism of the bli and low-resource mt literature is that while claims are made about diverse and under-resourced languages, research is often performed on down-sampled corpora of highresource, highly-related languages on similar domains @xcite . such corpora are not good proxies for true low-resource languages owing to data challenges such as dissimilar scripts, domain shift, noise, and lack of sufficient bitext @xcite . these differences can lead to dissimilarity between the embedding spaces (decreasing isometry), causing bli to fail @xcite @xcite @xcite @xcite . there are two axes by which a language dataset is considered "low-resource". first, the language itself may be a low-resource language: one for which little bitext and/or monolingual text exists. even for high-resource languages, the long tail of words may have poorly trained word embeddings due rarity in the dataset @xcite . in the data-poor setting of true low-resource languages, a great majority of words have little representation in the corpus, resulting in poorly-trained embeddings for a large proportion of them. the second axis is low-supervision. here, there are few ground-truth examples from which to learn. for bli from word embedding spaces, lowsupervision means there are few seeds from which to induce a relationship between spaces, regardless of the quality of the spaces themselves. we bring a new algorithm for graph-matching based on optimal transport (ot) to the nlp and bli literature. we evaluate using 40 language pairs under varying amounts of supervision. the method works strikingly well across language pairs, especially in low-supervision contexts. as lowsupervision on low-resource languages reflects the real-world use case for bli, this is an encouraging development on realistic scenarios. ## background the typical baseline approach for bli from word embedding spaces assumes that spaces can be mapped via linear transformation. such methods typically involve solutions to the procrustes problem (see @xcite for a review). alternatively, a graph-based view considers words as nodes in undirected weighted graphs, where edges are the distance between words. methods taking this view do not assume a linear mapping of the spaces exists, allowing for more flexible matching. bli from word embedding spaces assume separately-trained monolingual word embedding spaces: @xmath0, @xmath1. we build the matrices x and y of seeds from x and y, respectively, such that given s seed pairs (x 1 , y 1 ), (x 2 , y 2 ), ...(x s , y s ), the first row of x is x 1 , the second row is x 2 , etc. we build y analogously for the y-component of each seed pair. the goal is to recover matches for the x \ x and/or y \ y non-seed words. procrustes many bli methods use solutions to the procrustes problem (e.g. @xcite @xcite . these compute the optimal transform w to map seeds: once solved for w, then xw and y live in a shared space and translation pairs can be extracted via nearest-neighbor search. constrained to the space of orthogonal matrices, equation 1 has a simple closed-form solution @xcite : graph view here, words are nodes in monolingual graphs g x , g @xmath2, and cells in g x , g y are edge weights representing distance between words. as is common in nlp, we use cosine similarity. the objective function is equation 2, where π is the set of permutation matrices. 1 intuitively, pg y p t finds the optimal relabeling of g y to align with g x . this "minimizes edge-disagreements" between g x and g y . this graph-matching objective is np-hard. equation 3 is equivalent. ex. take source words x 1 , x 2 . we wish to recover valid translations y x 1 , y x 2 . if distance(x 1 , x 2 ) = distance(y x 1 , y x 2 ), a solution p can have an edgedisagreement of 0 here. we then extract y x 1 , y x 2 as translations of x 1 , x 2 . in reality, though, it is unlikely that distance(x 1 , x 2 ) = distance(y x 1 , y x 2 ). because equation 2 finds the ideal p to minimize edge disagreements over the entire graphs, we hope that nodes paired by p are valid translations. if g x and g y are isomorphic and there is a unique solution, then p correctly recovers all translations. graph-matching is an active research field and is computationally prohibitive on large graphs, 1 a permutation matrix represents a one-to-one mapping: there is a single 1 in each row and column, and 0 elsewhere. but approximation algorithms exist. bli involves matching large, non-isomorphic graphs-among the greatest challenges for graph-matching. ## experimental setup we run procrustes, sgm, and goat on 40 language pairs. we also run system combination experiments similar to @xcite . we evaluate with the standard precision@1 (p@1). we induce lexicons using (1) the closed-form solution to the orthogonal procrustes problem of equation 1, extracting nearest neighbors using csls @xcite , (2) sgm, solving the seeded version of equation 2, and (3 ## discussion we have seen goat's strength in low-resource scenarios and in non-isomorphic embedding spaces. as the major use case of low-resource bli and mt is dissimilar languages with low supervision, goat's strong performance is an encouraging result for real-world applications. furthermore, goat outperforms sgm. as the graph-matching objective is np-hard so all algorithms are approximate, goat does a better job by making a better calculation of step direction. chinese↔english and japanese↔english are outliers, which is worthy of future investigation. notably, these languages have very poor isomorphism scores in relation to english. ## conclusion we perform bilingual lexicon induction from word embedding spaces of 40 language pairs, utilizing the newly-developed goat algorithm for graph-matching. performance is strong across all pairs, especially on dissimilar languages with lowsupervision. as the major use case of low-resource bli and mt is dissimilar languages with low supervision, the strong performance of goat is an encouraging result for real-world applications.