A Graph-based Coarse-to-fine Method for Unsupervised Bilingual Lexicon Induction (2020)

Abstract: Unsupervised bilingual lexicon induction is the task of inducing word translations from monolingual corpora of two languages. Recent methods are mostly based on unsupervised cross-lingual word embeddings, the key to which is to find initial solutions of word translations, followed by the learning and refinement of mappings between the embedding spaces of two languages. However, previous methods find initial solutions just based on word-level information, which may be (1) limited and inaccurate, and (2) prone to contain some noise introduced by the insufficiently pre-trained embeddings of some words. To deal with those issues, in this paper, we propose a novel graph-based paradigm to induce bilingual lexicons in a coarse-to-fine way. We first build a graph for each language with its vertices representing different words. Then we extract word cliques from the graphs and map the cliques of two languages. Based on that, we induce the initial word translation solution with the central words of the aligned cliques. This coarse-to-fine approach not only leverages clique-level information, which is richer and more accurate, but also effectively reduces the bad effect of the noise in the pre-trained embeddings. Finally, we take the initial solution as the seed to learn cross-lingual embeddings, from which we induce bilingual lexicons. Experiments show that our approach improves the performance of bilingual lexicon induction compared with previous methods.

## introduction bilingual lexicon induction (bli) is an important task of machine translation and becomes an essential part of recent unsupervised machine translation approaches @xcite @xcite @xcite . previous methods for bli are * contribution during internship at msra. mostly based on unsupervised cross-lingual word embeddings @xcite @xcite @xcite @xcite , the goal of which is to find a mapping function, typically a linear transformation @xcite , to map the source embeddings into the target embedding spaces. to do this, they first build a seed dictionary (known as the initial solution) with different methods and then learn the optimal mapping function that fits the seed dictionary. based on the mapping function, a new dictionary of higher quality is inferred from the cross-lingual word embeddings by finding nearest neighbors in the target embedding space. with the new dictionary, the mapping function is further refined to fit it. the inference of the dictionary and the refinement of the mapping function are iteratively done until the final convergence. during the whole procedure, the initialization stage is important and heavily focused in previous work. previous methods for finding the initial solution fall into three categories. the first one is heuristic rules such as treating identical words as the seed @xcite , but this kind of method is restricted to languages sharing the alphabet. the second category is adversarial methods @xcite @xcite , but suffering from the drawbacks of generative adversarial models, i.e., the sensitivity of hyper-parameters, long training time, etc. the third category is structurebased methods @xcite , which is more flexible and robust than other categories, and achieve the state-of-the-art bli performance. in @xcite , they first compute a similarity matrix of all words in the vocabulary, and then represent each word with the distribution of the similarity values, while in @xcite , they project the word vectors to the top 50 principal components of the embedding spaces. after that, both of them directly use the word representation of two languages to retrieve the initial bilingual lexicons by computing the cosine distances of source and target word representations. however, directly finding word alignments from scratch has some demerits. (1) the information that a word can provide is limited and independent of each other. (2) according to our observation, there is some noise in the pre-trained embeddings even for high-frequency words so that the initial word alignments derived from them are not accurate. those mistakes in the initial wordlevel alignments can hurt the performance in the following iteration steps. to solve those issues, we propose a novel graphbased coarse-to-fine paradigm to generate initial solutions for learning cross-lingual word embeddings, from which we induce bilingual lexicons. specifically, given source and target languages, our method first uses pre-trained monolingual embeddings to construct a graph for each language, with the vertices representing different words, so that the mutual relationship between words is preserved. next, we use the bron-kerbosch algorithm @xcite to extract cliques (a subset of vertices in which every two distinct vertices are adjacent) in the source and target graphs. after that, we calculate the clique embeddings and map the cliques from two graphs. we then treat the central words of the aligned cliques as the seeds to learn the mapping of the two word embedding spaces. our contributions are threefold. ## background unsupervised bilingual lexicon induction (bli) is the task of inducing word translations from monolingual corpora of two languages. recently proposed methods follow the same procedure, i.e., first learning cross-lingual embeddings in an unsupervised way ( §2.1) and then inducing bilingual lexicons from the embedding spaces ( §2.2). ## methodology as is mentioned before, recent work on bilingual lexicon induction (bli) is mostly based on unsupervised cross-lingual embeddings, whose key point is to find initial solutions to learn the mapping function. however, previous methods find initial solutions just based on word-level information, which may be limited and inaccurate due to the noise in pre-trained monolingual embeddings. therefore, we exploit the information provided by word cliques and figure out a coarse-to-fine procedure to denoise and find the initial solution of higher quality. based on that, we learn the cross-lingual embeddings and induce word translations. as shown in figure 1 , our method for bli can be roughly divided into several steps. given the source and target languages, we first build a graph for each language. the graph vertex represents the word. next, we extract word cliques from the graphs and map the cliques of two languages in an unsupervised way. then, we induce the seed dictionary from the bilingual cliques by choosing the respective central words of the aligned cliques. after that, we learn cross-lingual embeddings with the help of the induced seed dictionary. the above steps can be iteratively done until the final convergence. by building word graphs, we can use the clique-level information which is richer and more accurate than what a single word provides. besides, the whole coarse-to-fine procedure also reduces the bad effect of the noise in the pre-trained embeddings, because the clique-level alignment (coarse) is more accurate at the beginning and the word alignments inferred from it (fine) are more reasonable. we will next introduce each step. ## related work bilingual lexicon induction (bli) is an important task of machine translation. recent methods for bilingual lexicon induction are mostly based on unsupervised cross-lingual word embeddings @xcite @xcite @xcite @xcite . they follow the same procedure that is first building initial solutions (a seed dictionary) and then learning a mapping function be-tween the two word embedding spaces. during inference, for a given source word, they find the target word via the nearest neighbors search by calculating the distance of the mapped source embedding and all target word embeddings. the main focus of the previous methods is how to find the initial solution, which is the most important part. their methods can be divided into three categories according to the way of finding the initial solution. the first category is using heuristic rules such as treating identical words as the seed @xcite , but this kind of method is restricted to languages sharing the vocabulary or at least the notation of numbers. the second category is adversarial methods @xcite @xcite . they train a generator to finish mapping between the two word embedding spaces, and a discriminator to distinguish the mapped embeddings from the target embeddings. however, they suffer from the drawbacks of generative adversarial models, i.e., the sensitivity of hyper-parameters, long training time and lack of interpretability @xcite . the third category is structure-based methods, which achieve the state-of-the-art performance on bli. they either leverage the intra-linguistic word similarity information @xcite or principal components of monolingual word embeddings @xcite , but their methods infer initial solutions just based on word-level information which is limited and prone to contain some noise due to the insufficient training of pre-trained embeddings. different from their methods, ours leverages clique-level information which is richer and more accurate, and uses a coarse-to-fine procedure to reduce the adverse effect of the noise mentioned above. ## conclusion in this paper, we propose a novel graph-based coarse-to-fine paradigm for unsupervised bilingual lexicon induction. our method uses clique-level information and reduces the bad effect of noise in the pre-trained embeddings. the experiments show that our method can significantly improve the bilingual word induction performance after several iterations compared with strong baselines, even for distant language pairs. in the future, we will consider combining our method with graph neural networks to update the word graphs we build.