Bilingual dictionary generation and enrichment via graph exploration

2.1. Pivot-based methods

The simplest approach is to assume that the translation relation is transitive. This method assumes the existence of two bilingual dictionaries, one containing translations from language L 1 to another language L 2 , and another from L 2 to L 3 . Language L 2 acts as pivot language and a new set of translations from L 1 to L 3 is discovered through direct transitivity. For instance in Fig. 2, the translations banc to panchina and panchina to banquillo contained in a Catalan–Italian and Italian–Spanish dictionary, respectively, would lead to valid discovery of the translation banc (Catalan) to banquillo (Spanish). This method, despite its simplicity, is still quite effective in a scenario in which human supervision is assumed. Actually, this is the basis of the cross option provided in the Apertium framework as part of the apertium-dixtools tool,7

However, the translation relation is not always transitive, as polysemy in the pivot language could lead to wrong translations being inferred. For instance in Fig. 2, the Catalan ( L 2 ) noun banc is a translation of bank in English ( L 1 ) in one sense (‘financial institution’), while it translates to panchina in Italian ( L 3 ) in another sense (‘bench’). Clearly, Italian panchina is not a good translation for English bank, but simple transitive approaches will propose it.

In order to overcome this issue and identify incorrect translations when constructing bilingual dictionaries mediated by a third language, Tanaka and Umemura [32] proposed in 1994 a method called one-time inverse consultation (OTIC). In short, the idea of the OTIC method is, for each word w in L 1 , to assign a score to each candidate translation t i of w in L 3 based on the overlap of pivot translations in L 2 shared by both w and t i .

OTIC was later adapted for different purposes, such as the creation of multilingual lexicons from bilingual lists of words [22]. While OTIC is intended for generic dictionaries, similar methods have been developed for generation of domain-adapted bilingual dictionaries [18]. Other authors have enriched OTIC with the inclusion of semantic features, such as Bond and Ogura [5] for the creation of a Japanese–Malay dictionary. Saralegi et al. [31] studied how to use distributional semantics computed from comparable corpora to prune pivot-based translations.

The works referred so far illustrate techniques that take into account the existence of (at least) two language pairs connected through a common pivot. However, when dictionaries can be connected in a richer way as part of a larger graph, other algorithms based on graph exploration may come into play. That is the case, for instance, of the CQC algorithm, developed by Flati and Navigli [7], which exploits the notion of cycles and quasi-cycles (hence the acronym CQC) for the automated disambiguation of translations in a bilingual dictionary. Notice that, unlike our approach, this method is not intended for dictionary building but for dictionary validation. Another remarkable method based on graph exploration is the SenseUniformPaths algorithm proposed by Mausam et al. [25], which relies on probabilistic methods to infer lexical translations. SenseUniformPaths was used in the generation of PanDictionary [26], a massive translation graph built from 630 machine-readable dictionaries and Wiktionaries,8

The SenseUniformPaths algorithm served as the basis for the cycle density method proposed by Villegas et al. [34] that we explore and expand in this work. SenseUniformPaths also uses cycles to identify potential translation targets, but the method by Villegas et al. differs in that it uses the graph density of cycles to rate the confidence value. This cycle density algorithm does not need to identify ambiguous cycles, and is therefore computationally less expensive. Moreover, SenseUniformPaths exploits dictionary senses, as found in resources such as Wiktionary while the cycle density method can operate in dictionaries without such sense information, such as the Apertium bilingual dictionaries, and therefore solves a harder problem.

Other methods have also been proposed that do not rely on graph exploration for bilingual lexicon induction, but are based on distributional semantics. Initial approaches have been based on vector space models [30,35] or in leveraging statistical similarities between two languages [9,16]. More recent approaches that exploit distributional semantics rely on the inference and use of cross-lingual word embeddings. An initial contribution in that direction was made by Mikolov et al. [29]. Methods using word embeddings to infer new dictionary entries require an initial seed dictionary that is used to learn a linear transformation that maps the monolingual embeddings into a shared cross-lingual space. Then, the resulting cross-lingual embeddings are used to induce the translations of words that are missing in the seed dictionary [3].

Such ideas evolved and new embeddings-based methods appeared that did not need such initial training, such as the work by Lample et al. [21], who propose a method to develop a bilingual dictionary between two languages without the need of using parallel corpora. The method needs large monolingual corpora for the source and target languages and leverages adversarial training to learn a linear mapping between the source and target spaces. The software implementing the method and the ground-truth bilingual dictionaries used to test it are publicly available.9

Another remarkable method of this embeddings-based family of techniques was developed by Artetxe et al. [4]. In their work, instead of directly inducing a bilingual lexicon from cross-lingual embeddings as in [21], they use the embeddings to build a phrase table, combine it with a language model, and use the resulting machine translation system to generate a synthetic parallel corpus, from which the bilingual lexicon is extracted using statistical word-alignment techniques.

In contrast to graph-based methods, the embeddings-based approaches still need large corpora to operate, which limits, for example, their applicability for under-resourced languages. Moreover, they operate at the word representation level, and therefore do not take into account other lexical information such as the part of speech, which can be essential to disambiguate the semantic sense of the word.

The fact that inferring new translations is not a trivial problem has motivated the Translation Inference Across Dictionaries (TIAD)10

As the TIAD campaign has showed, the OTIC algorithm continues to be a powerful method for translation inference, and it has proven to be very effective even in comparison with more contemporary methods [12,19]. However, OTIC needs a pivot language to operate, while cycle-based systems can discover translations between more indirectly connected languages. For instance, out of 946 possible language pairs in Fig. 1, pivot-based methods are applicable to 145 pairs which have a pivot, whereas the cycle density method that we study in this article can be applied to any of the 414 connected pairs. As an example, OTIC cannot work for Sardinian (sc) – Galician (gl) whereas the cycle-based method is able to infer translations between them. On the other hand, there can be less connected parts of the graph where dense cycles are difficult to find, where OTIC performs better. For instance, English (en) – Russian (ru) in the Apertium RDF.

Cycle-based methods can be used for additional tasks, such as synonym generation (see Section 11.2), which OTIC is not able to address. Moreover, cycle-based procedures are more suitable for iterative dictionary enrichment, as the produced translations for a target language pair ( L 1 → L 2 ), once manually validated and integrated into the ground-truth input sets, can help produce more cycles. However, for the OTIC algorithm, the pivot dictionaries would also have to be enriched to be able to produce further entries. Lastly, the richer Apertium RDF gets in terms of language pair connections and number of translations, the more capable the cycle-based algorithm becomes as it can harness the entire graph, not just information from pivot dictionaries.

In parallel work, a recent contribution to TIAD [10] demonstrates that OTIC and the cycle density algorithm can be combined into a generalized Augmented Cycle Density (ACD) framework that leverages their complementary advantages. Built on top of our released open-source tool and insights, ACD is a state-of-the-art procedure, outperforming both the OTIC and cycle density algorithm individually. In particular, in the TIAD 2021 official evaluations,11

4.1. Cycles in the translation graph

As mentioned in Section 2, the original algorithm relies on simple cycles instead of transitive chains, following the idea of circuits introduced in [25]. A simple cycle is a sequence of vertices starting and ending in the same vertex with no repetitions of vertices and edges. For ease of explanation, we will be referring to simple cycles as just cycles.

For a sequence of words u 1 , u 2 … u n , u 1 to be in a cycle while simultaneously containing a pair of words that are not a valid translation, there needs to be a stronger condition than polysemy, which we will call correlated polysemy. This means that two words in the cycle, say, vertices u i and u j ( i < j without loss of generality) contain the same distinct set of possible senses. This may lead to u i , u i + 1 … u j and u j , u j + 1 … u n , u 1 , … u i being paths along two different senses, but still completing a cycle. For instance, in Fig. 2, ⟨ banc , cat , noun ⟩ and ⟨ banco , glg , noun ⟩ share the same 2 senses: ‘bench’ and ‘financial institution’. Thus, we get banc – panchina – banquillo – banco along the sense ‘bench’, and banco – bank – banc along the sense ‘financial institution’. We want to ensure that words from differing sense-paths such as bank and panchina/banquillo are not considered valid translation pairs, but this is not trivial considering the source data does not carry any sense information.

4.2. Confidence metric: Cycle density

There can be multiple instances of correlated polysemy in a single cycle. In fact, considering that many language pairs in Apertium are linguistically close, this is not unexpected. Therefore, approaches based on exploiting sparsely inter-connected partitions of cycles may not be fruitful, as our experience has shown. Accordingly, we stick to using cycle density as proposed in [34] as a metric to avoid invalid predictions due to correlated polysemy.

The density of a subgraph G ′ ( V ′ , E ′ ) here is defined as 2 | E ′ | | V ′ | ( | V ′ | − 1 ) , that is, as the ratio of the actual number of edges | E ′ | to the number of edges | V ′ | ( | V ′ | − 1 ) 2 that would be found in a fully connected graph (or clique). Cycle density is therefore the density of the subgraph induced by a cycle, that is, the subgraph made up of the vertices in the cycle and the edges between them.

A higher density implies that the nodes in a cycle are closer to forming a clique. Therefore, intuitively, for high-density cycles, completing the clique by predicting the pairs of words with no edge between them as possible translations becomes a useful strategy, one which we adopt. In cases with correlated polysemy, subsets of vertices corresponding to a different set of senses are unlikely to have any edges between them, leading to a lower cycle density. In Fig. 2, there are 5 edges out of a possible 10, giving a density of 0.5. Thus, a density threshold higher than 0.5 will prevent ( ⟨ bank , eng , noun ⟩ , ⟨ panchina , ita , noun ⟩ ) being wrongly predicted as a translation based on this cycle, despite correlated polysemy due to ⟨ banc , cat , noun ⟩ and ⟨ banco , glg , noun ⟩ . Moreover, one would hope to get valid new translations like ( ⟨ banc , cat , noun ⟩ , ⟨ banquillo , spa , noun ⟩ ) through a different cycle.

4.3. Original algorithm

The algorithm outlined in [34] is summarized in the following lines. For each word w do the following:

Find the D-context of w, which is the subgraph G D ( w ) ( V D ( w ) , E D ( w ) ) formed by vertices within a certain distance D from W; D is referred to as the context depth.

A biconnected graph is one in which no vertex exists such that removing it disconnects the graph. A biconnected component is a maximal biconnected subgraph.15

Different biconnected components can only share cut vertices, that is, vertices whose removal renders the graph disconnected. The decomposition of a graph G ( V , E ) to compute all its biconnected components can be done through a well-known algorithm with a time complexity in O ( | V | + | E | ) by Hopcroft and Tarjan [15]. Consider the following fundamental properties of a biconnected component:

Property 2 tells us that we can run the algorithm separately for each biconnected component without missing any cycle, and consequently any translation. Property 1 shows us that biconnected components are in some sense the minimal units such that decomposing them further would make us lose information. Finding all cycles takes a number of operation which is exponential on the number of edges; therefore, by splitting a graph into smaller subgraphs, we require much less computation. Mathematically, this follows from ∑ i ( x i ) k ⩽ ( ∑ i x i ) k (for x > 0 and k ⩾ 1 ), which comes from the multinomial theorem.

The empirical speed-up is demonstrated in Table 1. Note that the improvement on lexicon-wide experiments like in Table 1 is partially shadowed by the cycle finding algorithm we use (see Section 5.3), which already implicitly exploits the locality of the graph. The partition into biconnected components is more useful when searching for translations of specific words instead of the entire vocabulary in one go. A lookup table file mapping words to biconnected components can be maintained. This helps load only the biconnected components the word belongs to instead of the entire graph, which cuts both computation time and memory requirements.

Although it is not frequent, there might be cases in RDF dictionaries in which translations connect words with different POS. As shown in Table 2, by removing such cases, large biconnected components containing multiple POS can be further split into smaller ones with just one POS. Our method takes that step in order to reduce run-time, and to prevent potentially spurious inferred translations.

In Table 3 we present the distribution of number of biconnected components by size on our large set of 27 language pairs (see Section 8) after discarding the cross-POS translations.

While clearly most biconnected components are small, some are indeed quite large, which is evident from the size of the largest one as shown in Table 2.

There are situations, however, where users might need to keep such cross-POS translations. For instance, in Apertium one can find a translation of the English noun computer into the Spanish adjective informático. This allows for rules, in a machine translation system, that may translate noun modifiers such as computer engineer as adjectives to get fluent translations such as ingeniero informático by looking up these cross-POS entries in the dictionary. This is especially important when the target languages do not have the same set of POS, requiring changes in POS during translation. Therefore, any implementation of the method should make this filter optional.

Within each biconnected component, we iterate over all words as the source word and repeat the following procedure for finding possible target words: First, we find and store the context graph of depth D for word w, G D ( w ) using breadth-first search. Then, we launch a backtracking search maintaining a stack to find relevant cycles, using an algorithm originally described in [36]. While more efficient algorithms for generating cycles exist [17], the chosen one has a good balance between ease of modification and time response (see Section 10).

6.1. Removed hyperparameters

After a careful analysis, we found that a number of heuristics and hyperparameters proposed in [34] were not leading to better results, therefore we propose to discard them:

Language repetition: The intuition for removing cycles with language repetition as in [34] is that two words in the same language are likely to not have the exact same set of semantic senses. Example: pupil in English can mean the aperture of the iris, but will also come in cycles with student. This can become a breeding ground for correlated polysemy, leading to incorrect translations. But allowing language repetition is necessary to generate synonyms (see Section 11.2); this would necessitate making this optional by adding a binary hyperparameter.

Furthermore, we find that not allowing repetition reduces recall significantly, and the same higher precision can instead be achieved by increasing the confidence threshold for a lesser loss in recall. Handling correlated polysemy is exactly what measuring cycle density is aimed at, so it is a natural way to mitigate this issue. We therefore proceed to remove this hyperparameter.

Minimum cycle length: Notice that cycle density as defined in Section 4.2 would favour shorter cycles, as the denominator grows quadratically with cycle length. In particular, a 4-cycle without any other edges among its vertices would have a density of 4 4 ( 4 − 1 ) / 2 = 2 3 , which would mean a good chance of being selected unless the threshold is set very high. So essentially, being part of any 4-cycle (which can easily be 2 correlated polysemous senses) ensures a that a pair of words becomes a predicted translation.

This is why the original algorithm [34] requires a minimum cycle length. In fact, they require different minimum lengths for a large context and a small context because in relatively sparse areas of the graph, many cycles might be small and yet correct. This leads to having three hyperparameters that require tuning: the minimum length in small contexts, the minimum length in large contexts, and the threshold defining when a context becomes large.

However, we found that eliminating all three hyperparameters gives similar results on average, while simplifying the pipeline significantly. Allowing small cycles allows more translations to be produced, as ignoring them completely would also leave out the probably valid translations we could predict using the dense small cycles.

6.2. Used hyperparameters

Having eliminated four hyperparameters of the original cycle density method, we now justify why we need the remaining ones and find the most suitable range of values for them.

Maximum cycle length ( L m a x ): The cycle length was originally bounded above to reduce computation time. Our large-scale experiments reveal that increasing cycle length beyond a certain threshold does not even help much, because of two main reasons:

With increasing distance16

Context depth (D): Similarly to the cycle length, the original motivation for limiting context depth was to reduce computation time. We find that increasing it beyond a certain threshold is not helpful because of the following property:

This effectively sets an upper bound to the context depth based on the maximum cycle length. We recommend using int ( L max 2 ) as the value throughout experiments, as lowering it would lead to loss of information.

Target degree multiplier (M): Here, by the degree of a vertex, we refer to the number of edges from the vertex within the subgraph induced by the cycle. Originally, in [34], a fixed lower (0.5 instead of 0.7) confidence threshold (density) was required for cycles if the target word had degree > 2 . We model this as a tunable hyperparameter: the multiplier applied to the density of the given cycle when the degree of the target is > 2 . This allows its effect to scale relatively when changing the density thresholds used for final translation selection. But why is this multiplier important in the first place? If the target word has only degree 2, it means that, apart from the two edges on its vertex in the cycle itself, the target word is not connected to other words in the cycle. This points to a chance of the target word not sharing a sense with a large part of the cycle (if it does, it can still be detected through a different cycle).

Transitivity (T): While an essential premise to necessitate a cycle-based approach is that transitivity does not always hold for translations due to polysemy, we realized that it can still perform well for non-polysemous categories of words.17

Confidence threshold (C): For a given pair of words u, v, let S u , v be the set of all cycles that follow the constraints set by the first 2 hyperparameters D and L max . For a cycle c ∈ S u , v , let d c be the density of its induced subgraph. Let M c be the target degree multiplier M if the condition for target degree multiplication is satisfied, and 1 otherwise. We define the confidence score of a predicted translation between u and v as: argmax c ∈ S u , v min ( M c d c , 1 ) This effectively keeps the confidence score within the range [ 0 , 1 ] .

Note that we stick to only the cycle with the highest confidence. We prefer this over metrics that use aggregate statistics over all the cycles containing the two words, such as the number of cycles or their average density. These are more likely to be sensitive to some subgraphs or contexts being richer in the number of translations added during creation, leading to superfluously better aggregates than others. The maximum is more robust to these differences, as only one dense cycle is then sufficient.

For translations produced using transitivity ( T = 1 and T = 2 ) instead of the cycle density method, we assign a full confidence score of 1. This allows combining these methods so that they can be used for particular POS where effective, leading to the generation of a unified set of possible translations with their confidence scores. We expect the user to use transitivity only in cases where they are sure it is highly precise, considering the full confidence assigned.

This motivates the final choice the user makes, the confidence threshold C. Generated translations above this confidence threshold are all included in the final prediction set of the algorithm.

To conclude, we have a set of just four simple hyperparameters: context depth D, maximum cycle length L max , target degree multiplier M, and transitivity T, with guidelines for their tuning based on insights described above. This produces a set of possible translations along with their confidence scores, from which the user can select those above a certain confidence threshold C, based on whether they want a large set or a highly precise one.

We have shown that a fixed value for context depth relative to the maximum cycle length is optimal in most cases. Moreover, the procedure is not very sensitive to the target degree multiplier within a reasonable range of [ 1 , 1.5 ] .20

8.1. Datasets

For initial experimentation with metrics and hyperparameter tuning, we picked a development set of 11 language pairs across 6 languages: English, Catalan, Spanish, Esperanto, French, and Occitan (see Fig. 3). We leave out each language pair and use the remaining 10 to re-generate it. This allows us to measure average metrics across the 11 language pairs.

OPEN IN VIEWER

Fig. 3.

Fragment of the Apertium RDF graph taken as development set, containing 6 languages and 11 language pairs.

Since one of our goals in this research is to scale up the initial cycle density algorithm, it is important to validate that the method performs well even when more language pairs come into play. To that end, we define what we call the large evaluation set, by taking all 27 language pairs across the 13 languages which constitute the largest biconnected component in the RDF language graph (see Fig. 4).22

We use the same leaving-one-pair-out experiment as the development set in this new setting, reporting average metrics across the 27 language pairs.

OPEN IN VIEWER

Fig. 4.

Languages in the largest biconnected component in the Apertium RDF graph. It contains 13 languages and 27 language pairs.

In general, if a user wants to predict translations for a target language pair ( L 1 , L 2 ) , using all language pairs in the biconnected component containing both L 1 and L 2 is a good strategy. However, if L 1 and L 2 do not belong to a common biconnected component, then pivot-based methods like OTIC should be preferred over cycle-based procedures. This is because less cycles between words in L 1 and L 2 will be found, and those that are will rely strongly on having multiple words from X, Y or intermediate languages. As discussed earlier, this can lead to higher polysemy and hence lower quality predictions.

After experimenting with the development set, the final hyperparameter setting, used across the rest of the evaluation, is the following (unless otherwise specified): transitive closure ( T = 2 ) with D = 4 for proper nouns and numerals; and T = 0 , D = 3 , L max = 6 , M = 1.4 , C = 0.5 for other POS. See Section 10.1 for more details on the hyperparameter selection process.

8.3. Baseline

As mentioned earlier, one of the main usage scenarios of the cycle density algorithm is the generation of new bilingual dictionaries for the Apertium framework. The idea is to substitute the cross option provided as part of the apertium-dixtools in Apertium (see Section 2) which relies on transitive inference [33]. Therefore, we introduce in our experiments an explicit comparison with a method that is purely based on transitivity, which we emulate by running our system with two sets of hyperparameters: T = 2 and D = 2 (baseline 1) and T = 2 and D = 4 (baseline 2). The latter is expected to produce a higher number of candidate translations since it will traverse more vertices in the graph.

8.4. External dictionaries

In order to validate the enrichment of translations in already existent language pairs, we use the MUSE ground truth dictionaries23

We begin by defining some notation we will use throughout the following sections.

I denotes the input translation graph, which could include multiple bilingual dictionaries.

9.2. Metrics for automatic evaluation

The unavailability of a complete test dictionary makes it difficult to measure traditional metrics like precision ( | E ( P ) ∩ E ( T ) | | E ( P ) | ) and recall ( | E ( T ) ∩ E ( P ) | | E ( T ) | ). One might ask: is a translation produced by the algorithm that is not found in the test dictionary incorrect, or is it correct but missing from the test dictionary? Should the algorithm really be penalized for one of its main tasks, namely dictionary enrichment, generating valid translations that humans might have overlooked? The unequivocal answer to that should be no, and yet precision and recall as defined here (which we will call vanilla precision and recall in the remainder of this paper) do penalize the algorithm for this. For instance, an algorithm which covers, say, 90 of 100 test dictionary translations would end up being considered better (precision 0.9, recall 0.9) than one producing not only those 90, but 30 additional correct ones not in the test dictionary (precision: 0.75, recall: 0.9). Indeed, the precision only goes down with additional translations (which are all considered wrong in the vanilla precision formula). Clearly, using these vanilla metrics would move our algorithms away from the goal of enrichment.

9.3. Measuring dictionary enrichment with external data

While external corpora can be used for evaluating additional translations, they often have significantly different properties from the input and target sets. This can lead to erroneous conclusions due to noisy results.

However, evaluating against additional data is particularly important in the context of this paper for the following reasons:

We use the MUSE dictionaries (see Section 8.4) to evaluate the quality of additional translations.

9.4. Measuring dictionary enrichment with human assessment

As a final sanity check of our additional entries, we took random samples of 150 predicted dictionary entries that were not present in the test set T. These belonged to open POS categories, that is, nouns, adjectives, adverbs, verbs and proper nouns, and also numerals. This was done directly using Apertium bilingual dictionaries as input data with a rather liberal (recall-oriented) set of hyperparameters: T = 0 , D = 4 , L max = 8 , M = 1.4 , C = 0.1 . for five different language pairs (Spanish–English, Spanish–Catalan, French–Occitan, Esperanto–English, French–Catalan). We asked bilingual experts to evaluate them, obtaining a sort of gold standard for each language pair.26

As these sets were produced with a different version of the data and hyperparameters, we took an intersection between these sets and the additional translations produced by a different setting that need to be evaluated. While this is not directly a random sample of the additional translations, it is a good approximation.

Table 5 shows how decreasing the confidence threshold C while holding all hyperparameters constant leads to lower BWP and higher BWR, recall and prediction set size as expected. The end user can tune this precision-recall tradeoff to their liking (see Section 11.1 for a discussion in the context of Apertium), but we stick to maximizing the F 1 . Notice, however, the noisy trend in vanilla precision, which points to how it is not a reflective metric in many cases.

Table 6 shows that increasing the maximum allowed cycle length keeping all else constant leads to decreasing BWP, but increasing BWR, recall and time. We see diminishing returns in the F 1 score beyond cycle length 6, as expected.

Next, Table 7 shows the comparison for proper nouns and numerals between using the hyperparameter setting used for other POS and the chosen T = 2 , D = 4 one. Clearly, we achieve much higher BWR, and recall on using transitivity, with lower but decent enough BWP. Particularly, the high BWR shows that this method generates a large portion of the target set that it possibly could have with the given input data.

To demonstrate the extent of polysemy in the RDF Graph, we use the T = 2 , D = 4 transitive setting for all POS. The dismal results produced are shown in Table 8. Despite the extremely large prediction set produced, vanilla recall remains low. This illustrates a limitation of vanilla recall: it gives a pessimistic view of the algorithm performance. In that sense, BWR is more reflective of the actual performance, given the data provided.

Finally, we show in Table 9 that allowing language repetition actually improves performance, which led us to removing the hyperparameter.

In Table 10 we present the results of transferring the same hyperparameter setting derived in our development set to our large set, continuing the dictionary generation experiment but with a larger graph. It takes longer to run, but still within one minute for all language pairs. Once again, the accuracy metrics reported are averaged across the 27 language pairs that are left-out one by one.

The drop in the metrics on the large set compared to the development set is not necessarily a sign of overfitting. The large set has more less-connected, under-resourced language pairs, which bring down the averages.

In Table 11, we demonstrate a significant gain in relative size across POS when using the large set compared to Table 4 when using the development set. Similar trends are observed for BWR in Fig. 7. In Fig. 6 we show the variation in the metrics across the 27 languages in the large set. While a high BWP is maintained across all language pairs, the prediction set size varies greatly based on the richness of Apertium RDF entries in the input. Some of the language pairs with the lowest number of translations produced are: por–glg (6,044), spa–por (10,176), eus–spa (12,243). On the other hand, language pairs with the highest number of translations produced are: spa–cat (50,145), eng–cat (52,323), fra-cat (68,087). This is consistent with Catalan (cat) having some of the largest dictionaries in the Apertium RDF, whereas Portuguese (por) and Basque (eus) ones are much smaller.

We show a comparison between the cycle density algorithm and the transitive baselines in Table 12. We see that transitive closure tends to increase relative coverage and recall, but at the cost of a much lower precision (55% and 13% for the respective baselines vs. 84% for cycle density). Depending on the use case, a balance towards recall might be acceptable, but usually a decent level of precision is important, which the transitive procedures do not provide. As expected, baseline 2 produces many more candidate translations, leading to a much larger prediction set but dropping precision significantly.

In order to measure the impact of enriching the input graph towards improving results, in Table 13 we also restrict the averaged metrics to the 11 development set language pairs, still using the whole large set as input. There is a significant improvement in comparison with the original development set experiments (see Table 10). This demonstrates the advantages of adding more input data. Notice how in this scenario, due to the fact that language pairs are more connected, the cycle density algorithm beats the transitive baselines in terms of the F1-score as well.

OPEN IN VIEWER

Fig. 6.

Boxplot showing, left to right: BWP, recall, F 1 , and relative size across 27 languages being generated from scratch in the large set.

OPEN IN VIEWER

Fig. 7.

Breakdown by POS of BWP (left bars) and BWR (right bars), averaged across language pairs in the large set.

In conclusion, our produced translations are on average 71.39% the size of existing Apertium dictionaries at a high BWP of 84.07% across 27 language pairs over 13 languages.

OPEN IN VIEWER

Fig. 8.

Breakdown of the match between the predicted set P, the original test s, and the input set I. For all word classes (overall) and for words in each lexical category, each left bar is divided from bottom to top, to show overall precision (predicted word correspondences in P which are in the original apertium dictionary used as test set T), and then the percentages of additional predicted word correspondences with both words in the test set (both with original), with the left word in the test set (left with original), with the right word in the test set (right with original), and with neither word in the test set (neither with original). Also for all word classes (overall) and for words in each lexical category, each right bar is divided also from bottom to top, to show overall recall (word correspondences in the test set T which are in the predicted set P), and then the percentages of missed word correspondences in the test set T with both words in the input set I (both with input), with the left word in the input set (left in input), with the right word in the input set (right in input), and with neither word in the input set (neither in input). Refer to the discussion in Sections 10.3 and 9.2.

The coloured bar graph in Fig. 8 shows statistics about the predicted translations in P that match the test set T and contrasts it with those that do not match, which are further classified. These are average metrics reported over the 27 language pairs in the large set.

In particular, it classifies the additional translations in P (the left bar) in terms of how many words they have in common with the original Apertium dictionary used as a test set, T, and classifies the missed translations (the right bar) of T in terms of how many words they have in common with the input set I. This also provides a way to visualize the BWP and BWR metrics defined in Sections 9.2.1 and 9.2.2 respectively. From bottom to top, the BWP (resp. BWR) is the ratio of the height of the lowest sub-bar to the combined height of the lowest two sub-bars in the left (resp. right) bars.

As has been said, Fig. 8 shows the ratios of different additional (resp. missed) translations based on the words shared with the target original Apertium dictionaries used as test set T (resp. input Apertium dictionaries I) in the left (resp. right) bar of each POS. Almost 30% of predicted translations have neither word in the test set. This is particularly high due to the large relative size in proper nouns and numerals and demonstrates the incompleteness of original Apertium dictionaries, which implies there is a vast scope for enrichment. On the other hand, while the number of missed translations with neither word in the input data is just 10%, for over 30% of test set translations only one word is present in the input data. This demonstrates the scope for improving the algorithm’s recall by improving the coverage of the input data for specific languages. A similar analysis can be done on a more fine-grained level for each POS.

We now evaluate the additional translations for the 5 language pairs also present in MUSE (see Section 8.4). In Table 14, we calculate the overall BWP of our additional translation set with MUSE as test set. We further show the breakdown of the additional translations in terms of number of words shared with our original test set, that is, the left-out RDF dictionary. Particularly, n extra ( i ) denotes the number of additional translations with i words shared. BWP extra ( i ) denotes the BWP with respect to MUSE for these n extra ( i ) translations. Notice the declining trend of BWP with the increase in shared words with the test set. This confirms our hypothesis that many additional translations are actually correct, and if both words are present in the test set without a translation between them, the prediction is much less likely to be correct. This shows that BWP with respect to the test set is indeed a tight approximation, and a much more useful metric than vanilla precision. These results also show that our method produces a decent number of additional translations for many language pairs, with especially encouraging results for French–Spanish. Note that the BWP for these additional translations reported using MUSE would again be a lower bound, and many of those not counted could possibly be correct, just not present in MUSE.

Table 15 shows a comparison between BWR and recall with MUSE as the test set (T) using the algorithm’s output prediction sets (P) when given the large set as input (I). While the recall is dismal, the BWR is much higher, in fact somewhat similar to the BWR on the actual test sets in the large experiments, when we evaluate on the left-out dictionary instead of MUSE. This shows that the BWR is relatively insensitive to the dataset distributions and thus a robust metric for evaluation.

Finally, we report accuracy for the additional translations predicted during the large experiment on the human evaluation sets in Table 16. The precision obtained is encouraging, confirming that our procedure works well for enrichment. Note that the varying sample size is due to the dataset difference and intersection taken explained in Section 9.4.29

BWR should be used as a valuable test metric when the same input dataset is used, particularly by creators when tuning and improving a particular algorithm. It also signifies the data-effectiveness of any proposed algorithm. It gives a clear picture of the optimization landscape, growing more consistently than recall as the prediction set becomes more liberal, as shown in Table 8.

BWP can be used for comparison across systems to make evaluation of translation inference pipelines more accurate. A natural usage scenario for this metric is the TIAD shared task. In particular, the evaluation procedure in TIAD (until the 2020 edition) modified traditional precision metrics in the same direction as in this paper by limiting the output set for precision to translations for which the word in the source language is in the evaluation set. This is somewhat what we could call one-word-precision, but the key drawback is that it is asymmetric. The precision computed for language pair A → B can be different from language pair B → A , even though the choice of source and target is actually arbitrary. Moreover, as shown in Table 14, additional translations missed by one-word-precision are correct far more often than those missed by BWP. In fact, past TIAD results show relatively low precision values (up to a maximum of 0.7) [19], making bilingual dictionary inference seem a harder problem than it actually is. This is unlike our symmetric definition, which makes the evaluation process simpler and directly conveys an indicator of the performance of the algorithm that is independent of the setting.

11.1. Apertium

As mentioned above, Apertium30

It has to be noted though that the LMF and RDF dictionaries do not contain all the information present in the Apertium bilingual dictionaries, but just the orthographic representation (spelling) of the lemma and the POS; Apertium dictionaries may contain additional information, for instance, to inform of the fact that the gender of a word changes (so that, for instance, target-side gender agreement with adjectives is ensured by an appropriate rule), as in this Spanish–Catalan entry,

where in addition of the fact that the Spanish (left, l) lemma almohada(‘pillow’) is a noun (n) corresponding to the Catalan (right, r) lemma coixíwith the same part of speech, the entry also encodes the fact that almohadais a feminine (f) noun and coixíis a masculine (m) noun. In entries where the gender does not change, this is usually not indicated. Therefore, some of the bilingual correspondences predicted by our tool in its current form may need to be completed after being validated by an Apertium expert. Work is in progress to add this information to the RDF graphs and to improve the method described here to be able to transfer morphological information to predicted entries directly.

When Apertium experts process each predicted dictionary entry, they first validate its usefulness and then either discard it or adopt it, perhaps adapting it by inserting additional information (like gender), before adding it to the dictionary. The actual time required to do these operations may be used to inform the weight β that should be given to recall in an F β indicator, which can in turn be used to determine the confidence threshold. On one hand, if validating and discarding is much faster than validating, adopting and adapting, perhaps one could sacrifice precision to improve recall, selecting a higher value for β.33

We have until now discussed the usage of our algorithm for creating bilingual dictionaries. The same cycle density procedure however can also be used to generate edge predictions between words in the same language, that is, synonyms. This allows extending from generating just dictionaries to even creating thesauri.

In fact, some popular translation engines like Google Translate also provide synonyms to end users, unlike Apertium. Automatic synonym generation from Apertium data could thus help create a useful feature. Synonymy relations may also be useful represented as linguistic linked data.

The confidence score obtained in our method can also possibly be used as a measure for conceptual similarity. Traditional methods based on word co-occurrence suffer from several issues for this task, requiring further augmentation [24]. In-fact, it has even been shown that having translation information is one way to improve their performance [14]. Our method takes that hypothesis to the extreme, relying purely on translation graphs over documents. Some advantages of this are as follows:

We demonstrate here a preliminary experiment. We produce synonym pairs for English, Spanish and Catalan using the large set of 27 language pairs as input. Random samples of 150 words drawn from the 3 prediction sets are evaluated by 2 human annotators each, and we report the results in Table 17. To the evaluators, we pose a similar question as before: “Is there a context where the two words are replaceable?”.

Note that we took the same hyperparameters and confidence threshold as the translation setting (see 8.2). Modifications specific to synonym generation might be required for optimal results. The results demonstrated are just a proof of concept, more detailed studies and exact comparisons with existing methods are left for future work.