Clustering Comparable Corpora of Russian and Ukrainian Academic Texts: Word Embeddings and Semantic Fingerprints

Abstract: We present our experience in applying distributional semantics (neural word embeddings) to the problem of representing and clustering documents in a bilingual comparable corpus. Our data is a collection of Russian and Ukrainian academic texts, for which topics are their academic fields. In order to build language-independent semantic representations of these documents, we train neural distributional models on monolingual corpora and learn the optimal linear transformation of vectors from one language to another. The resulting vectors are then used to produce `semantic fingerprints' of documents, serving as input to a clustering algorithm. The presented method is compared to several baselines including `orthographic translation' with Levenshtein edit distance and outperforms them by a large margin. We also show that language-independent `semantic fingerprints' are superior to multi-lingual clustering algorithms proposed in the previous work, at the same time requiring less linguistic resources.

This research addresses the problem of representing the semantics of text documents in multi-lingual comparable corpora. We present a new approach to this problem, based on neural embeddings, and test it on the task of clustering texts into meaningful classes depending on their topics. The setting is unsupervised, meaning that one either does not have enough annotated data to train a supervised classifier or does not want to be limited with a pre-defined set of classes. There is a lot of sufficiently good approaches to this problem in the case of mono-lingual text collections, but the presence of multiple languages introduces complications.
When a text collection contains documents in several languages, it becomes impractical to simply represent the documents as vectors of words occurring in them ("bag-of-words"), as the words surface forms are different, even in closely-related languages. Thus, one has to invent means to cross the inter-lingual gap and bring all documents to some sort of shared representation, without losing information about their topics or categories.
Of course, one obvious way to solve this problem is to translate all documents into one language, and then apply any clustering algorithm. However, this requires either buying human/machine translation services (which can be expensive if you deal with large text collection) or training own statistical machine translation model (which as a rule requires big parallel corpus). This is the reason to search for other solutions.
In this paper, a novel way of reducing the problem of cross-lingual document representation to a monolingual setting is proposed. Essentially, we train Continuous Bag-of-Words models BIBREF0 on large comparable monolingual corpora for two languages our dataset consists of. This provides us with vector representations of words, allowing to measure their semantic similarity. Then, a linear transformation matrix from vectors of language A to vectors of language B is learned, using a small bilingual dictionary as training data. This matrix is then employed to `project' word and document representations from semantic space of language A to semantic space of language B. It allows not only quite accurate `translation' of words, but also of document `semantic fingerprints' (dense representations of document semantics, calculated as an average of the trained distributional vectors for all the words in document).
This approach is evaluated in a setting, where the input is a collection of documents in several languages and some number of topics to which these documents belong (we also have large monolingual corpora to train distributional models on). For each document, we are given its language, but not its topic. The task is to cluster this collection so that documents belonging to one topic were clustered together, independent of their language. Note that we are interested in clustering the collection as a whole, not each language separately (which is trivial).
Our evaluation data consists of comparable corpora of Russian and Ukrainian academic texts. On this material, we show that the `translated semantic fingerprints' method represents documents in different languages precisely enough to allow almost exact clustering according to document topics, with only 5% of incorrect assignments. It significantly outperforms both naive bag-of-words baseline and the not-so-naive method of `orthographic translation' based on Damerau-Levenshtein distance, even enriched with dictionary mappings. At the same time, it does not require large parallel corpora or a ready-made statistical machine translation model.
The rest of the paper is structured as follows. In Section "Related Work" we describe the foundations of our approach and the related work. Section "Academic texts as Comparable Corpora" introduces the employed corpora and the story behind them. Section "Learning to Translate: Ukrainian-to-Russian transformations" is dedicated to learning the transformation matrix, and Section "Experiment Design and Evaluation" describes our experimental setting and evaluation results. We discuss the findings in Section "Discussion" and conclude in Section "Conclusion and Future Work" , also suggesting directions for future work.
Clustering multi-lingual documents has received much attention in natural language processing. Among approaches not using some form of machine translation, one can mention BIBREF1 , who essentially employ a bilingual dictionary to bring some words in the documents to a language-independent form and then to perform clustering. In the section "Experiment Design and Evaluation" we show that our approach based on neural embeddings significantly outperforms their reported results.
 BIBREF2 proposed training joint multi-lingual neural embedding models. Theoretically, this can be used to achieve our aim of language-independent semantic representations for documents. Unfortunately, it demands a large word-aligned parallel corpus. This is not the case with the more recent Trans-gram approach introduced in BIBREF3 , also able to learn multi-lingual models. However, it still needs sentence-aligned corpora to train on (in the size of millions of paired sentences). Large parallel corpora (whether word- or sentence-aligned) are often a scarce resource, especially in the case of under-represented languages.
The approach described in this paper takes as an input only comparable monolingual corpora and bilingual dictionaries in the size of several thousand word pairs. Such resources are much easier to find and evaluate. We employ the idea of learning a linear transformation matrix to map or project word embeddings from the semantic space of one language to that of another. This idea was first proposed in BIBREF4 , who applied it to lexical translation between English, Spanish, Czech and Vietnamese. We extend it from continuous representations of single words or collocations to `semantic fingerprints' of documents as a whole.
The Russian and Ukrainian languages are mainly spoken in Russian Federation and the Ukraine and belong to the East-Slavic group of the Indo-European language family. They share many common morphosyntactic features: both are SVO languages with free word order and rich morphology, both use the Cyrillic alphabet and share many common cognates.
Both Russia and the Ukraine have common academic tradition that makes it easier to collect corpora, which are comparable in terms of both genre and strictly defined academic fields. We work with such a corpus of Russian and Ukrainian academic texts, initially collected for the purposes of cross-lingual plagiarism detection. This data is available online through a number of library services, but unfortunately cannot be republished due to copyright limitations.
The Ukrainian subcorpus contains about 60 thousand extended summaries (Russian and Ukrainian russian`автореферат', `avtoreferat') of theses submitted between 1998 and 2011. The Russian subcorpus is smaller in the number of documents (about 16 thousand, approximately the same time period), but the documents are full texts of theses, thus the total volume of the Russian subcorpus is notably larger: 830 million tokens versus 250 million tokens in the Ukrainian one. Generally, the texts belong to one genre that can be defined as post-Soviet expository academic prose, submitted for academic degree award process.
The documents were converted to plain text files from MS Word format in the case of the Ukrainian subcorpus and mainly from OCRed PDF files in the case of the Russian subcorpus. Because of this, the Russian documents often suffer from OCR artifacts, such as words split with line breaks, incorrectly recognized characters and so on. However, it does not influence the resulting model much, as we show below.
Both Ukrainian and Russian documents come with meta data allowing to separate them into academic fields, with economics, medicine and law being most frequent topics for the Ukrainian data and economics, history and pedagogy dominating the Russian data.
For evaluation, 3 topics were used, distant enough from each other and abundantly presented in both subcorpora: economics, law and history. We randomly selected 100 texts in each language for each topic. As an average length of Russian texts is significantly higher (them being full theses), we cropped them, leaving only the first 5 thousand words, to mimic the size of the Ukrainian summaries. These 600 documents in 3 classes are used as a test set (see Section "Experiment Design and Evaluation" for the description of the conducted experiments).
The corpora (including test set) were PoS-tagged. Each word was replaced with its lemma followed by a PoS-tag (`russianдиссертация_S', `russianдиссертацiя_N'). Functional parts of speech (conjunctions, pronouns, prepositions, etc.) and numerals were removed from the texts.
As already stated, our main proposal is using neural embedding models to `project' documents in one language into the semantic space of another language. For this, we first trained a Continuous Bag-of-Words (CBOW) and a Continuous SkipGram model BIBREF0 for each of our monolingual subcorpora. The models were trained with identical hyperparameters: vector size of 300 components, symmetric window of 2 words, negative sampling with 10 samples, 5 iterations over the corpus, no down-sampling. The only language-dependent difference was that for the Ukrainian model we ignored words with the corpus frequency less than 10 and for the Russian model this threshold was set to 15 (as the Russian corpus is 3 times larger). All in all, the final Ukrainian model recognizes 429 215 words and the Russian one 271 720 words. Training was performed using CBOW and SkipGram implementation in Gensim library BIBREF7 .
After the models were trained, we followed the path outlined in BIBREF4 to learn a linear transformation matrix from Ukrainian to Russian. First, we extracted all noun pairs from Russian-Ukrainian bilingual dictionary BIBREF8 , with the constraint that their frequency in our corpora was above the already mentioned thresholds 15 and 10 for Russian and Ukrainian words correspondingly. That made it a list of about 5 thousand pairs of nouns being translations of each other.
For all these words, their vectors were found in the models corresponding to the words' languages. It provided us with a matrix of 5 thousand of 300-dimensional Ukrainian vectors and the matrix of corresponding 5 thousand of 300-dimensional Russian vectors. This data served as a training set to learn an optimal transformation matrix. The latter is actually a 300x301 matrix of coefficients, such that when the initial Ukrainian matrix is multiplied by this transformation matrix, the result is maximally close to the corresponding Russian matrix. This transformation matrix has 301 (not 300) columns, because we add one component equal to 1 to each vector, as a bias term.
Producing the transformation matrix is a linear regression problem: the input is 301 components of Ukrainian vectors (including the bias term) and the output is 300 components of Russian vectors. As we need 300 values as an output, there are actually 300 linear regression problems and that's why the resulting matrix size is 300x301 (301 weights for each of 300 components).
There are two main ways to solve a linear regression problem: one can either learn the optimal weights in an iterative way using some variant of gradient descent, or one can solve it numerically without iteration, using normal equation. For English and Spanish, BIBREF4 used stochastic gradient descent. However, normal equation is actually less error-prone and is guaranteed to find the global optimum. Its only disadvantage is that it becomes very computationally expensive when the number of features is large (thousands and more). However, in our case the number of features is only 301, so computational complexity is not an issue.
Thus, we use normal equation to find the optimal transformation matrix. The algebraic solution to each of 300 normal equations (one for each vector component $i$ ) is shown in the Equation 3 : 
$$\beta _i = (\textbf {X}^\intercal * \textbf {X})^{-1} * \textbf {X}^\intercal * y_i$$   (Eq. 3) 
where $\textbf {X}$ is the matrix of 5 thousand Ukrainian word vectors (input), $y_i$ is the vector of the $i$ th components of 5 thousand corresponding Russian words (correct predictions), and $\beta _i$ is our aim: the vector of 301 optimal coefficients which transform the Ukrainian vectors into the $i$ th component of the Russian vectors.
After solving such normal equations for all the 300 components $i$ , we have the 300x301 linear transformation matrix which fits the data best.
This matrix basically maps the Ukrainian vectors into the Russian ones. It is based on the assumption that the relations between semantic concepts in different languages are in fact very similar (students are close to teachers, while pirates are close to corsairs, and so on). In continuous distributional models which strive to represent these semantic spaces, mutual `geometrical' relations between vectors representing particular words are also similar across models (if they are trained on comparable corpora), but the exact vectors for words denoting one and the same notion are different. This is because the models themselves are stochastic and the particular values of vectors (unlike their positions in relation to each other) depend a lot on technical factors, including the random seed used to initialize vectors prior to training. In order to migrate from a model A to another model B, one has to `rotate and scale' A vectors in a uniform linear way. To learn the optimal transformation matrix means to find out the exact directions of rotating and scaling, which minimize prediction errors.
Linguistically speaking, once we learned the transformation matrix, we can predict what a Russian vector would most probably be, given a Ukrainian one. This essentially means we are able to `translate' Ukrainian words into Russian, by calculating the word in the Russian model with the vector closest to the predicted one.
We had to choose between CBOW or Continuous SkipGram models to use when learning the transformation matrix. Also, there was a question of whether to employ regularized or standard normal equations. Regularization is an attempt to avoid over-fitting by trying to somehow decrease the values of learned weights. The regularized normal equation is shown in 4 : 
$$\beta _i = (\textbf {X}^\intercal * \textbf {X} + \lambda * L)^{-1} * \textbf {X}^\intercal * y_i$$   (Eq. 4) 
Comparing to 3 , it adds the term $\lambda * L$ , where $L$ is the identity matrix of the size equal to the number of features, with 0 at the top left cell, and $\lambda $ is a real number used to tune the influence of regularization term (if $\lambda = 0$ , there is no regularization).
To test all the possible combinations of parameters, we divided the bilingual dictionary into 4500 noun pairs used as a training set and 500 noun pairs used as a test set. We then learned transformation matrices on the training set using both training algorithms (CBOW and SkipGram) and several values of regularization $\lambda $ from 0 to 5, with a step of 0.5. The resulting matrices were applied to the Ukrainian vectors from the test set and the corresponding Russian `translations' were calculated. The ratio of correct `translations' (matches) was used as an evaluation measure. It came out that regularization only worsened the results for both algorithms, so in the Table 1 we report the results without regularization.
For reference, we also report the accuracy of `quazi-translation' via Damerau-Levenshtein edit distance BIBREF9 , as a sort of a baseline. As already stated, the two languages share many cognates, and a lot of Ukrainian words can be orthographically transformed into their Russian translations (and vice versa) by one or two character replacements. Thus, we extracted 50,000 most frequent nouns from our Russian corpora; then for each Ukrainian noun in the bilingual dictionary we found the closest Russian noun (or 5 closest nouns for @5 metric) by edit distance and calculated how often it turned out to be the correct translation. As the Table 1 shows, notwithstanding the orthographic similarity of the two languages, CBOW consistently outperforms this approach even on the test set. On the training set, its superiority is even more obvious.

Figure and table captions:
Table 1: Translation accuracy
Table 2: Clustering correspondence to document topics
Figure 1: Naive baseline clustering
Figure 2: Matrix translation clustering
Figure 3: Semantic fingerprints clustering

Questions about this paper:
What evaluation metric do they use?

Answers:
Accuracy