The CQC Algorithm: Cycling in Graphs to Semantically Enrich and Enhance a Bilingual Dictionary: Extended abstract

1 Introduction

Lexical knowledge resources, such as thesauri, machinereadable dictionaries, computational lexicons and encyclopedias, have been enjoying increasing popularity over the last few years. Among such resources we cite Roget's Thesaurus, the Macquarie Thesaurus, the Longman Dictionary of Contemporary English [Proctor, 1978, LDOCE], WordNet [Fellbaum, 1998] and Wikipedia. These knowledge resources have been utilized in many applications, including Word Sense Disambiguation (WSD) [Yarowsky, 1992; Nastase and Szpakowicz, 2001; Mart´ınez et al., 2008, cf. Navigli, 2009b, 2012 for a survey], Semantic Information Retrieval [Krovetz and Croft, 1992; Mandala et al., 1998; Sanderson, 2000, inter alia], Question Answering [Lita et al., 2004] and knowledge acquisition [Navigli and Ponzetto, 2012].

Most of these applications exploit the structure provided by the adopted lexical resources in a number of different ways. For instance, lexical and semantic relations encoded in computational lexicons such as WordNet have been shown to be very useful in graph-based WSD [Mihalcea, 2005; Agirre and Soroa, 2009; Navigli and Lapata, 2010; Ponzetto and Navigli, 2010] and semantic similarity [Pedersen et al., 2005]. Interestingly, it has been reported that the higher the amount of structured knowledge, the higher the disambiguation performance [Navigli and Lapata, 2010].

∗This paper is an extended abstract of the JAIR publication [Flati and Navigli, 2012].

Unfortunately, not all the semantics are made explicit within lexical resources. Even WordNet, the most widely-used computational lexicon of English, provides explanatory information in the unstructured form of textual definitions, i.e., strings of text which explain the meaning of concepts using possibly ambiguous words (e.g., "motor vehicle with four wheels" is provided as a definition of the most common sense of car). Still worse, while computational lexicons like WordNet contain semantically explicit information such as is-a and part-of relations, machine-readable dictionaries (MRDs) are often just electronic transcriptions of their paper counterparts. Thus, for each entry they mostly provide implicit information in the form of free text, which cannot be immediately utilized in Natural Language Processing applications. Over recent years various approaches to the disambiguation of monolingual dictionary definitions have been investigated [Harabagiu et al., 1999; Litkowski, 2004; Castillo et al., 2004; Navigli and Velardi, 2005; Navigli, 2009a], and results have shown that they can, indeed, boost the performance of difficult tasks such as WSD [Cuadros and Rigau, 2008; Agirre and Soroa, 2009]. However, little attention has been paid to the disambiguation of bilingual dictionaries, which would be capable of improving popular applications such as Machine Translation.

In this paper we present a graph-based algorithm which aims at disambiguating translations in bilingual machinereadable dictionaries. Taken as input a bilingual MRD, our method transforms the dictionary into a graph whose nodes are word senses and edges encode translation relations. Next, we introduce a novel notion of cyclic and quasi-cyclic graph paths that we use to select the most appropriate sense for a translation w′ of a source word w.

2 Preliminaries

Goal. The general form of a bilingual dictionary entry is:

where: (i) wip is the i-th sense of the word w with part of speech p in the source language (e.g., play2v is the second sense of the verb play); (ii) each vj is a translation in the target language for sense wip (e.g., suonarev is a translation for play2v ). Note that each vj is implicitly assumed to have the same part of speech p as wp. Importantly, no sense is explicitly associated with vj .

Our objective is to associate, in a systematic and automatic way, each target word vj with one of its senses so that the concepts expressed by wp and vj match.

Bilingual Dictionary. We define a bilingual machinereadable dictionary (BiMRD) as a quadruple D = (L, Senses, T ,M), where L is the bilingual lexicon (i.e., L includes all the lexical items for both languages), Senses is a mapping such that, given a lexical item w ∈ L, returns the set of senses for w in D, T is a translation function which, given a word sense s ∈ Senses(w), provides a set of (possibly ambiguous) translations for s. Typically, T (s) ⊂ L, that is, the translations are in the lexicon. However, it might well be that some translations in T (s) are not in the lexicon. Finally, M is a function which, given a word sense s ∈ Senses(w), provides the set of all words representing meta-information for sense s (e.g., M(phoneme1n ) = {linguistics}).

The dictionary also provides usage examples and compound translations , lexical variants (e.g., acknowledgement vs. acknowledgment) and references to other entries (e.g., frommotorcar to car).

Noisy Graph. Given a BiMRD D, we define a noisy dictionary graph G = (V, E) as a directed graph where:

1. V is the set of senses in the dictionary D (i.e., V = ⋃w∈L Senses(w));
2. For each word w ∈ L and a sense s ∈ Senses(w), an edge (s, s′ ) is in E if and only if s′ is a sense of a translation of s in the dictionary (i.e., s′ ∈ Senses(w′ ) and w′ ∈ T (s)), or s′ is a sense of a meta-word m in the definition of s (i.e., if s′ ∈ Senses(m) for some m ∈ M(s)).

Graph Cycles and Quasi-Cycles. We now recall the definition of graph cycle. A cycle for a graph G is a sequence of edges of G that form a path v1 → v2 → · · · → vn (vi ∈ V ∀i ∈ {1, . . . , n}) such that the first node of the path corresponds to the last, i.e., v1 = vn. The length of a cycle is given by the number of its edges.

We further provide the definition of quasi-cycle as a sequence of edges in which the reversal of the orientation of one or more consecutive edges creates a cycle [Bohman and Thoma, 2000].

It can be seen that the reversal of an edge of a quasi-cycle creates a cycle. Since the direction of this edge is opposite to that of the cycle, we call it a reversed edge. Finally, we say that a path is (quasi-)cyclic if it forms a (quasi-)cycle. Note that we do not consider paths going across senses of the same word.

3 The CQCAlgorithm

We are now ready to introduce the Cycles & Quasi-Cycles (CQC) algorithm, whose pseudocode is given in Table 1. The algorithm takes as input a BiMRD D = (L, Senses, T ,M), and a sense s of a word w in its lexicon (i.e., w ∈ L and s ∈ Senses(w)). The algorithm aims at disambiguating each of the word's ambiguous translations w′ ∈ T (s), i.e., to assign it the right sense among those listed in Senses(w′ ).

The algorithm outputs a mapping µ between each ambiguous word w′ ∈ T (s) and the sense s′ of w′ chosen as a result of the disambiguation procedure that we illustrate hereafter.

First, for each sense s′ of our target translation w′ ∈ T (s), the algorithm performs a search of the noisy graph associated with D and collects the following kinds of paths:

where s is our source sense, s′ is our candidate sense for w′ ∈ T (s), si is a sense listed in D (i ∈ {1, . . . , n-2}), sn-1 = s, and n is the length of the path. Note that both kinds of path start and end with the same node s, and that the algorithm searches for quasi-cycles whose reversed edges connecting sk to sj are consecutive. To avoid redundancy we require (quasi-)cycles to be simple, that is, no node is repeated in the path except the start/end node (i.e., si ̸= s, si ̸= s′ , si ̸= si′ ∀i, i′ s. t. i ̸= i′ ).

The second phase of the CQC algorithm (lines 5-10 of Table 1) computes a score for each sense s′ of w′ based on the paths collected for s′ during the first phase. Let p be such a path, and let l be its length. Then the contribution of p to the score of s′ is given by:

where: (i) ω(l) is a monotonically non-increasing function of its length l; in our experiments, we tested three different weight functions ω(l), namely a constant, a linear and an inversely exponential function 1 ; (ii) the normalization factor NumPaths(all paths, l) calculates the overall number of collected paths of length l among all the target senses.

1 Experiments showed the inversely exponential function to be the best performing one.

As a result of the systematic application of the algorithm to each sense in our BiMRD D, a new graph G′ = (V,E′ ) is output, where V is again the sense inventory of D, and E′ is a subset of the noisy edge set E such that each edge (s, s′ ) ∈ E′ is the result of our disambiguation algorithm run with input D and s. In this pruned graph, each sense links to only one sense of each of its translations.

4 Evaluation: Dictionary Disambiguation

Dictionary. We performed our dictionary disambiguation experiments on the Ragazzini-Biagi [Ragazzini and Biagi, 2006], a popular bilingual English-Italian dictionary, which contains over 90,000 lemmas and 150,000 word senses.

Dataset. Our datasets for tuning and test consist of dictionary entries, each containing translations of a source sense into a target language. Each translation item was manually disambiguated according to its sense inventory in the bilingual dictionary.

We report statistics for the two datasets in Table 2, including the number of polysemous translations and the average polysemy of each translation. We note that for 44 of the translations in the test set (i.e., 4.1% of the total) none of the senses listed in the dictionary is appropriate (including monosemous translations). The last column in the table shows the number of translations for which a sense exists that translates back to the source lemma.

Algorithms. We compared the following algorithms in our experimental framework, since they represent the most widespread graph-based approaches and are used in many NLP tasks with state-of-the-art performance:

• CQC: we applied the CQC algorithm as described in Section 3.
• Cycles, a variant of the CQC algorithm which searches for cycles only (i.e., quasi-cycles are not collected).
• DFS, which applies an ordinary DFS algorithm and collects all paths between s and s′ .
• Random walks, which performs a large number of random walks starting from s′ , collecting those paths that lead to s.
• Markov chains, which calculates the probability of arriving at a certain source sense s starting from the initial translation sense s′ averaged over n consecutive steps. The initial Markov chain is initialized so that the outgoing edges of a node have equal probabilities.
• Personalized PageRank (PPR): a popular variant of the PageRank algorithm [Brin and Page, 1998] where the original Markov chain approach to node ranking is modified by perturbating the initial probability distribution on nodes. We concentrate all the probability mass on s′ , apply PPR and select the best translation sense as the one which maximizes the PPR value of the source word.
• Lesk algorithm [Lesk, 1986]: we apply an adaptation of the Lesk algorithm in which, given a source sense s of word w and a word w′ occurring as a translation of s, we determine the right sense of w′ on the basis of the (normalized) maximum overlap between the entries of each sense s′ of w′ and that of s.

We also compared the performance of our algorithms with three baselines: (i) the First Sense (FS) Baseline, that associates the first sense listed by the dictionary with each translation to be disambiguated; (ii) the Random Baseline, which selects a random sense for each target translation; (iii) the Degree Baseline, that chooses the translation sense with the highest out-degree.

Parameters. We used the tuning dataset to fix the parameters of each algorithm that maximized the performance (see Flati and Navigli, 2012 for details).

Measures. To assess the performance of our algorithms, we calculated precision (the number of correct answers over the number of items disambiguated by the system), recall (the number of correct answers over the number of items in the dataset), and F1 (a harmonic mean of precision and recall, given by 2PR P+R ). Note that precision and recall do not consider those items in the test set for which no appropriate sense is available in the dictionary. In order to account for these items, we also calculated accuracy as the number of correct answers divided by the total number of items in the test set.

Results. In Table 3 we report the results of our algorithms on the test set. CQC, PPR and Cycles are the best performing algorithms, achieving around 83%, 81% and 75% accuracy respectively. CQC outperforms all other systems in terms of F1 by a large margin. The results show that the mere use of cyclic patterns does not lead to state-of-the-art performance, which is obtained when quasi-cycles are also considered. Including quasi-cycles leads to a considerable increase in recall, while maintaining a high level of precision. The DFS is even more penalizing because it does not get backward support as happens for cycling patterns. Markov chains consistently outperform Random walks. We hypothesize that this is due to the higher coverage of Markov chains compared to the number of random walks collected by a simulated approach. PPR outperforms the two other probabilistic approaches, but lags behind CQC by 3 points in F1 and 2 in accuracy. This result confirms previous findings concerning the high performance of PPR, but also corroborates our hunch about quasi-cycles being the determining factor in the detection of semantic connections. Finally, Lesk achieves high precision, but low recall, due to the lack of a lookahead mechanism.

The random baseline represents our lowerbound and is much lower than all other results. Compared to the first sense baseline, CQC, PPR and Cycles obtain better performance. This result is consistent with previous findings for tasks such as the Senseval-3 Gloss Word Sense Disambiguation [Litkowski, 2004]. However, at the same time, it is in contrast with results on all-words WSD [Navigli, 2009b], where the first or most frequent sense baseline generally outperforms most disambiguation systems. Nevertheless, the nature of these two tasks is very different, because in dictionary entries senses tend to be equally distributed, whereas in open text they have a single predominant meaning that is determined by context. As for the Degree Baseline, it yields results below expectations, and far worse than the FS baseline. The reason behind this lies in the fact that the amount of translations and translation senses does not necessarily correlate with mainstream meanings.

5 RelatedWork

Since the late 1970s much work on the analysis and disambiguation of dictionary glosses has been done. This includes methods for the automatic extraction of taxonomies from lexical resources [Litkowski, 1978; Amsler, 1980], the identification of genus terms [Chodorow et al., 1985] and the extraction of explicit information from machine-readable dictionaries ([Nakamura and Nagao, 1988; Ide and V´eronis, 1993], as well as the construction of ambiguous semantic networks from glosses [Kozima and Furugori, 1993].

More recently, a set of heuristics has been proposed to semantically annotate WordNet glosses, leading to the release of the eXtended WordNet [Harabagiu et al., 1999; Moldovan and Novischi, 2004]. Among the heuristics, the cross reference heuristic is the closest technique to our notion of (quasi-)cyclic patterns in which cycles of length 2 are sought. Recently, it has been proposed that probabilistic translation circuits can be used to automatically acquire a multilingual dictionary [Mausam et al., 2009].

Based on the eXtended WordNet, a gloss disambiguation task was organized at Senseval-3 [Litkowski, 2004]. Most notably, the best performing systems, namely the TALP system [Castillo et al., 2004], and SSI [Navigli and Velardi, 2005], are knowledge-based and rely on rich knowledge resources: respectively, the Multilingual Central Repository [Atserias et al., 2004], and a proprietary lexical knowledge base (cf. Navigli and Lapata, 2010).

However, the literature in the field of gloss disambiguation is focused only on monolingual dictionaries, such as WordNet and LDOCE, while, to our knowledge, CQC is the first algorithm aimed at disambiguating the entries of a bilingual dictionary. Moreover, in contrast to many disambiguation methods in the literature [Navigli, 2009b], our approach does not exploit lexical and semantic relations, such as those available in computational lexicons like WordNet.

6 Conclusions

In this paper we presented a novel algorithm, called Cycles and Quasi-Cycles (CQC), for the disambiguation of bilingual machine-readable dictionaries. The algorithm is based on the identification of (quasi-)cycles in the noisy dictionary graph, i.e., circular edge sequences (possibly with some consecutive edges reversed) relating a source word sense to a target one.

We show that our notion of (quasi-)cyclic patterns enables state-of-the-art performance to be attained in the disambiguation of dictionary entries, surpassing all other disambiguation approaches, as well as a competitive baseline such as the first sense heuristic. Crucially, the introduction of reversed edges allows us to find more semantic connections, substantially increasing recall while keeping precision very high. The strength of our approach lies in its weakly supervised nature: the CQC algorithm relies exclusively on the structure of the input bilingual dictionary and, unlike others, no further resource is required.

Acknowledgments

The authors gratefully acknowledge the support of the ERC Starting Grant MultiJEDI No. 259234.

The authors wish to thank Zanichelli for making the Ragazzini-Biagi dictionary available for research purposes.