A Locally Linear Procedure for Word Translation (2020)

Abstract: Learning a mapping between word embeddings of two languages given a dictionary is an important problem with several applications. A common mapping approach is using an orthogonal matrix. The Orthogonal Procrustes Analysis (PA) algorithm can be applied to find the optimal orthogonal matrix. This solution restricts the expressiveness of the translation model which may result in sub-optimal translations. We propose a natural extension of the PA algorithm that uses multiple orthogonal translation matrices to model the mapping and derive an algorithm to learn these multiple matrices. We achieve better performance in a bilingual word translation task and a cross-lingual word similarity task compared to the single matrix baseline. We also show how multiple matrices can model multiple senses of a word.

## introduction continuous word embeddings are a standard component in many nlp applications. the embedding spaces can exhibit similar structures across languages. several studies @xcite have exploited this similarity by learning a linear mapping from a source to a target embedding space, and demonstrated this approach on word translation tasks. @xcite showed that using orthogonal matrices can significantly improve performance. since then, several studies have aimed at improving these bilingual word embeddings by using bilingual word dictionaries generated in either supervised or unsupervised manner. a multi-sense word in the source language can be translated into several different words in the target language. studies have shown that for the multi-lingual translation problem, enforcing the transformation to be strictly orthogonal is too restrictive and performance can be improved by relaxing this constraint. it was shown that using orthogonalization as regularization rather than a strict constraint @xcite , yields matrices that are close to orthogonal but are not necessarily exactly orthogonal, and improves performance @xcite . a single matrix however, whether orthogonal or not, cannot model the case of translating a multi-sense word. in this study, motivated by the multi-sense word situation, we investigated another way to relax the common modeling assumption that a single orthogonal transformation is suitable for translating all the words of a source language into a target language. in our approach, the word translation procedure is modeled by a set of orthogonal matrices where each word is translated by one of the matrices. the words are grouped according to their associated matrix. this grouping is determined by applying a clustering procedure on the vocabulary words. next, for each cluster we learn a separate orthogonal matrix. the word mapping function is thus modeled by a local orthogonal transformation. when translating a new word, we select the most suitable matrix for this specific translation task. we illustrate our approach on several standard word translation tasks and we show performance improvement compared to translation based on a single matrix. previous studies @xcite have found that there is a linear correlation between the vector spaces of the two languages, thus, it is best to use a linear mapping. @xcite and @xcite showed that restricting the linear mapping q to be orthogonal improves performance. the optimal mapping is found by minimizing the following cost function (f denotes the frobenius norm): the solution to eq. ( 1 ) is well-established and is known as the procrustes analysis (pa) algorithm @xcite . the optimal orthogonal mappings is obtained by @xmath0. this method has been used in many recent cross-lingual studies @xcite @xcite . however, it was shown that using one orthogonal matrix to map a vector space into another one can be too restrictive in some cases @xcite . we hypothesized that using multiple matrices would improve translation by relaxing the restrictive assumption of the ordinary pa solution (single matrix). the goal is to model the word translation by a set of matrices q 1 , ..., q k . the proposed algorithm is an extension of the single-matrix pa algorithm that was described above where the optimization goal remains minimizing the mean square error. the objective function we want to minimize is thus: by minimizing the score (2) the aim is to simultaneously cluster the word pairs into k groups and assign the optimal translation matrix to each group separately. there is no closed form solution for this minimization problem. instead we use an iterative procedure that resembles the k-means algorithm. each iteration consists of two stages. in the first step we reassign each word pair to one of the clusters: in the second step we re-estimate the translation matrices. the updated matrix q i is obtained by minimizing the following score. the minimization of eq. ( 4 ) can be efficiently computed by the pa algorithm. the alternate minimization procedure guarantees a monotone improvement of the score (2) until convergence to a local minima. for alternate minimization algorithms, a good initialization is crucial for fast convergence. in our case it is reasonable to assume that two words whose embedding vectors are close should be translated by the same matrix. thus, in order to find the initial cluster we can apply standard a k-means procedure on a transformation of the word embedding vectors. we adapt a dense transformation of the word vectors based on an auto-encoder representation. the autoencoder foot_0 is trained to minimize the reconstruction loss over the concatenation of source and target word embedding pairs. then, k-means is applied on the latent representation of the word embedding vectors. note that the k-means algorithm is also sensitive to the initialization. however, this problem is well-studied and there are good stable algorithms for k-means optimization such as k-means++ @xcite . our training algorithm is summarized in algorithm 1. ## experiments experimental setup. in this experiment we empirically tested the advantages of using multiple matrices for the word translation task. we used the publicly available muse dictionaries @xcite foot_1 for supervised mapping learning and evaluation. we used 300-dimensional pre-trained fasttext word vectors, trained on wikipedia @xcite foot_2 . the vectors were normalized to unit length and then zero centered @xcite . we conducted several experiments, all with english (en) as either the source or the target language. we report word translation results for de, es, fr, it, pt in both directions. compared methods. we compared the following translation methods in our experiments: ## conclusion in this paper, we presented a natural extension of the procrustes analysis algorithm that relaxes the current single-matrix modeling assumption. we empirically demonstrated the superiority of our method on two standard word translation tasks. our proposed method based on multiple matrices can also be applied as a natural extension to several other related settings. in the future, we plan to investigate an unsupervised dictionary setting using our algorithm in the refinement steps @xcite .