We consider the task of aligning two sets of points in high dimension, which
has many applications in natural language processing and computer vision. As an
example, it was recently shown that it is possible to infer a bilingual
lexicon, without supervised data, by aligning word embeddings trained on
monolingual data. These recent advances are based on adversarial training to
learn the mapping between the two embeddings. In this paper, we propose to use
an alternative formulation, based on the joint estimation of an orthogonal
matrix and a permutation matrix. While this problem is not convex, we propose
to initialize our optimization algorithm by using a convex relaxation,
traditionally considered for the graph isomorphism problem. We propose a
stochastic algorithm to minimize our cost function on large scale problems.
Finally, we evaluate our method on the problem of unsupervised word
translation, by aligning word embeddings trained on monolingual data. On this
task, our method obtains state of the art results, while requiring less
computational resources than competing approaches.

本文旨在提出一种新的基于正交矩阵和置换矩阵联合估计的点集对齐算法，并应用在自然语言处理和计算机视觉领域的单语数据的无监督单词翻译问题中，实现了比竞争对手更先进效果却需要更少的计算资源