2.1 Properties of dictionary definitions

We now introduce some lexicographical properties of dictionary definitions as a basis for our extraction methods. We will use some lexicographical terminology: the word being defined in a dictionary entry is called the definiendum, and words that define it are called its definientia. This subsection discusses special features of these elements in monolingual English dictionaries that facilitate synonym extraction.

Within the definientia, there is usually a word or phrase that is more closely related to the definiendum than the rest of the definition: the genus term. Usually, genus terms are either synonyms or hypernyms of the definiendum, as in the example of automobile: a motorcar (synonym) and summer: the second and warmestseason of the year (hypernym). Sometimes a genus term may include a quantifier. Such terms are known as empty heads; they preclude simple heuristics for identifying genus terms. An example is the word type in the definition arum: a tall, whitetype of lily (Guthrie et al. Reference Guthrie, Slator, Wilks and Bruce1990). Identifying genus terms or empty heads is itself a useful application in processing dictionary definitions. Nonetheless, the composition of definientia usually exhibits great regularity in terms of syntax, style, and sometimes, vocabulary. Amsler (Reference Amsler1980) showed that definitions of nouns and verbs in most dictionaries follow rigid stylistic patterns. In fact, this stylistic regularity goes beyond the definitions of nouns and verbs; as shown in Section 3.3, definitions of adjectives exhibit comparable or even greater regularity than those of nouns.

In monolingual English dictionaries, definition texts can often be decomposed into two parts: the interpretive part and the synonymous part. The former usually leads a definition in as a relatively lengthy description of the definiendum with simple vocabulary but complex syntax; many of these interpretive parts are followed by one or more synonymous parts, each consisting of a single word or phrase highly synonymous to the definiendum. When appearing together in the same definition, the two parts are usually separated by a special typographical format (e.g., capitalization) or delimiter (e.g., semicolons). Examples include the definition of look in Mish (Reference Mish2003) ‘to exercise the power of vision upon: EXAMINE’, and of looker-on: ‘one who looks on; a spectator’. Note that in the latter case, the synonymous part after the semicolon is, instead of being just one word, prefixed by an indefinite article. In terms of length and vocabulary, both examples conform with our observation on the differences between the interpretive and the synonymous parts.

For the interpretive part of a given definition, real synonyms, if any, could be identified only through syntactic and semantic knowledge of the definientia; many attempts have been made to automate such deep analysis of the definition language. It is the simpler cases of the synonymous parts in definitions that are mostly left uninvestigated. Semantically, as is shown in the previous examples, such parts of definitions are highly synonymous to the definienda, whereas terms extracted from the interpretive parts can often be hypernyms (even after successfully avoiding empty heads). Syntactically, synonymous parts can be identified by very simple typographical patterns. Although the patterns are dictionary-specific, their rigid nature usually necessitates minimal human intervention. The semantic relatedness between definienda and definientia validates the hypothesis that synonymy does exist in dictionary definitions, while the regularities in the composition of definientia make it possible to develop algorithms for synonym extraction.

2.2 Inverted index extraction

In this section, we propose a simple baseline algorithm as a first attempt to explore the relationship between definienda and definientia – by building an inverted index (hence the name Inverted Index Extraction (IIE)) on the dictionary.Footnote ² Each line l = (t, S) in the inverted index consists of a target word t, of which we want to extract the synonyms, followed by a set S = {w: t ∈ dfn(w)} of words with t in their definition texts. Here, dfn(w) refers to the set of words in the definientia of the word w. In IIE, such words are considered semantically related to t, regardless of the importance of t within their definitions. Consequently, semantic relatedness in IIE is built upon the occurrence of one word in the definition of another.

Table 1 shows the IIE result for look. Many near-synonyms of the target word look are successfully identified: see and watch as well as troponyms, such as ogle, gaze, inspect, and glance. Observe that words, such as gawp or rubberneck, though as synonymous to look as scrutinize and glance, are not listed in existing thesauri (e.g., Roget's Thesaurus, Roget Reference Roget1911), indicating that the results of IIE could indeed help improve the coverage of existing thesauri. More interestingly, when using The Macquarie Dictionary (of Australian origin), colloquial Australian expressions denoting the action of looking (such as dekko and the rhyming slang Captain Cook) appear in the list, which are missing from the results using Webster's Revised Unabridged Dictionary (or WRUD, of American origin). This partly provides evidence for the claim made in previous studies (e.g., that of Ho and Cédrick Reference Ho and Cédrick2004) that lexicon-based methods for synonym extraction exhibit portability between different domains and languages. To fully test the claim, however, requires comparison between synonyms extracted from a domain- (or language-)specific dictionary and those compiled in a thesaurus in the same domain (or language), which is beyond the scope of this study.

Table 1.

IIE result for the target word look

In contrast to the method used by Chodorow et al. (Reference Chodorow, Byrd and Heidorn1985), who distinguished genus terms from the rest of definition texts, IIE takes all definiens indiscriminately and thus defines a less-strict relatedness. The word independent, for example, is related to look by its definition ‘sufficient to support someone so that they do not have tolook for a living’, and optimism by ‘tendency tolook on the bright side of things’. This is especially problematic for common words, which are more likely to appear in the definition texts of (and thus be related to) many other words. A simple method to deal with false positives of this kind is to specify a part of speech (POS) for each target word. If, for example, we are interested in finding synonyms for the verb look, we might want to discard faraway: abstracted or dreamy, as alook from the IIE result, since we know that the entry faraway is an adjective and thus should not be a synonym of look (in its verb sense).

Another way to reduce the false positive rate is based on local connectivity of the dictionary graph. The word fear, for example, appears in many other words' definitions; among these, many with the suffix -phobia are essentially hyponyms rather than synonyms of fear. Such words, in contrast to synonyms of fear, do not seem to appear in each other's definition (i.e., disconnected in the dictionary graph). Using such difference in connectivity in the dictionary graph, we obtained the two subtables in Table 2.

Table 2.

Discriminating words by connectivity for the target word fear

It is interesting to see how words in the subtable on top tend to be more synonymous to fear than those on the bottom: all hyponyms with the suffix -phobia are eliminated, the only antonym (courage) is also eliminated, and most synonyms remain in the upper subtable (including phobia as a word instead of a suffix).

2.3 Pattern-based extraction

As stated earlier, the number of synonyms extracted by IIE largely depends on the frequency of the target word and is severely diminished if the target word is rare and thus less likely to appear in other words' definitions. Consequently, a new extraction strategy is proposed in this section to alleviate this problem. Specifically, for a given word w, the proposed approach tries to identify synonyms within the definition text of w according to certain patterns; we refer to this as Pattern-based Extraction (PbE). As a result, the frequency of w no longer matters, as long as its definition matches any of the extraction patterns. As is true with all existing lexicon-based methods, coverage remains an issue for PbE due to the limited patterns one can find in definition texts, but evaluation on all tasks in Section 3 shows significant improvement on PbE's coverage over that of IIE. The patterns in question are based on the synonymous parts of definitions discussed in Section 2.1. We aim at capturing the features distinguishing such parts from the rest of the definition texts.

In the distribution of definition text lengths of The Macquarie Dictionary and WRUD (Figure 1), there is a large number of very short definitions: 5,359 consisting of only one word and 9,672 of two words in The Macquarie Dictionary, 4,918 and 10,938, respectively, in WRUD.Footnote ³ The noun synset subset of WordNet has different absolute numbers but the distribution is very similar. Some of the one-word definitions are synonyms of the definienda, the other being expansions of abbreviations being defined (which could also be viewed as synonyms in a way). The two-word definitions are more complicated. Sometimes a synonym follows a function word, such as indefinite article in a noun definition (e.g., jailhouse: a jail) or infinitive to (e.g., damask: to damascene) in a verb definition. Sometimes both words are synonyms to the definiendum and are separated by a semicolon in between (e.g., maculate: spotted; stained). These two cases constitute a large proportion of the double-word definitions and are both useful for synonym extraction. There are also cases of a hypernym of the definiendum following a certain quantifier (e.g., madrigal: any song), with the genus terms being hypernyms rather than synonyms of the definienda.

Fig. 1.

Distribution of definition text length in The Macquarie Dictionary.

Note that despite the seemingly large numbers of one- and two-word definitions, they are still far from dominant, considering the size of most dictionaries; the majority of definitions are combinations of synonymous and interpretive parts; sometimes synonymous parts are not present at all. It is therefore necessary to discover patterns that can deal with longer and compounded definitions. Also, not all dictionaries have specific patterns for synonyms in definition texts. Definition texts in WordNet, for example, group together synonyms in the form of synsets. All of the general-purpose dictionaries we examinedFootnote ⁴ explicitly list synonymous parts in their definition texts.

2.3.1 The basic PbE algorithm

Our pattern-based method (Algorithm 1) discovers occurrence patterns of synonyms in definition texts. Given a set of patterns P = {p ₁,. . .,p _n}, PbE looks at each definition of a target word w and extracts words that follow any one of the patterns as synonyms. In practice, a pattern p _i takes the form of a regular expression, e.g., ‘^.*;(w+).$’. Table 3 shows the notation for regular expressions used in this paper. If a definition text matches this pattern, the word s corresponding to the regex group ‘(\w+)’ will be proposed as a synonym. For example, if the target word is w = ‘separate’, then one of its definitions ‘separate: to disconnect; disunite’ matches a pattern p = ‘^.*; (\w+)$’ and s = ‘disunite’ is proposed as a synonym to w. This scenario is to be referred to as ‘a definition matching a patternp on a words’, as in Line 1 in Algorithm 1.

Algorithm 1

Simple Pattern-based Extraction

Table 3.

Notation for regular expressions used in this paper

2.3.2 Incorporating IIE into PbE

As mentioned earlier, there are many definitions that do not contain a synonymous part, which again brings up the problem of diminished sizes of proposed synonym sets and, thus, low coverage of the extraction strategy. To address these two issues, after matching the definientia of w against the patterns, an improved version of PbE (Algorithm 2) scans the entire dictionary and looks at the definientia of other words; if, in this step, any word w' has a definition matching any pattern on w, then w' is extracted as a synonym to w. For example, for the target word w = ‘separate’, PbE first proposes s = ‘disunite’ as a result of Algorithm 1; in addition to this, as a result of Line 2 through 2 in Algorithm 2, PbE scans for definitions matching any patterns on the target word w = ‘separate’. To do so, PbE first plugs w into the pattern p, resulting in p _s=‘^.*; separate$’, and then finds and proposes the word w′=‘part’ whose definition ‘part: to put or keep asunder. . .; disunite; separate’ matches the plugged-in pattern p _s on ‘separate’ (Line 2, Algorithm 2).

Algorithm 2

Pattern-based Extraction with IIE-style Scanning

The process of scanning other words' definitions resembles that of IIE in Section 2.2, with a difference that now the algorithm makes distinctions on where and how w appears in the definition of w′.

On top of the synonym set resultSet extracted by Algorithm 1 for a target word w, Algorithm 2 can improve the coverage of PbE by the additional pass through the dictionary. Similar improvement can also be achieved by running Algorithm 1 for multiple iterations, but the quality of extracted synonyms will vary. Repeated execution of Algorithm 1 will result in a tree-like growth pattern for synonyms as shown in Figure 2(a), where every element in S = {s ₁,. . .,s _n} will serve as a target word; some of the elements in S (e.g., s ₁), however, are related to the target word under rare senses, for example, and the offspring of these elements (e.g., {s ₁₁,. . .,s _{1m 1}}) will be far less synonymous to the original target word w (more details on this in Section 2.3.4). In contrast, the IIE-style procedure in Algorithm 2 starts from the target word w instead of the elements in the extracted set S, and the resulting output of PbE grows ‘upwards’ as in Figure 2(b). It is obvious that words in {s′₁,. . .,s′_m} are more synonymous to w than those in {s _i1,. . .,s _{im i}}, i = 1,. . .,n.

Fig. 2.

Different growth patterns of result set size in Algorithm 1 and 2.

Here, a pass through the entire dictionary is required for extracting synonyms for every word, but various preprocessing steps can be used to improve the efficiency. For example, the search space could be reduced to only those definitions that follow at least one of the synonymous part patterns, which is less than 16% of the size of the entire dictionary. Algorithm 2 is used for PbE in all the experiments in Section 3.

2.3.3 Pattern bootstrapping

Note that the interpretive and synonymous parts are not intrinsic features of definition texts. Therefore, the number of definitions that follow synonymous-part patterns is limited. In addition, the hand-crafted definition texts usually exhibit many typographical variations: some definitions, for example, end with periods while others do not. It is therefore necessary to devise a pattern-finding mechanism that can both obtain new synonym patterns and accommodate variations with minimal hard-wiring or human intervention.

Bootstrapping can achieve both goals at the same time. Specifically, a bootstrapper is initialized with a word w as well as a seed regex pattern p, which could be some simple pattern for synonymous parts in a given dictionary (e.g., ‘.*;(\w+)$’ in The Macquarie Dictionary). The output is a set of regex patterns that synonyms follow within definition texts. By applying p on the definientia of w, the bootstrapper gets a set S of synonyms of w. Given the fact that dictionary definitions are often circular (Jurafsky and Martin Reference Jurafsky and Martin2008), it can be assumed that some elements of S are to appear in the definientia of others. If any of these occurrences follows pattern p′ other than p, p′ is then added to the resulting pattern set. Currently, p′ is identified manually, i.e., the bootstrapper would output any of the circular definitions among the set of words S, which provides a human user with potential patterns followed by synonyms.

Figure 3 gives an example of how patterns are bootstrapped from a seed word (split) and two seed patterns. Starting from the seed word split and the seed patterns ‘^(\w+)\.$’ and ‘^.*; (\w+)\.$’, cleft and divided are firstly extracted from the definition of split. Parted is also added to the synonym set since its inclusion of cleft follows one of the seed patterns. As the number of synonyms grows, it becomes more and more likely for some of the synonyms to appear in the definitions of others under patterns different from the seed patterns. In the second iteration, for example, split appears in the middle of one definition of cleft, resulting in a new pattern ‘^*;(\w+);.*$’. More synonyms could, in turn, be extracted using these new patterns. Examples of bootstrapped patterns are listed in Table 4.

Fig. 3.

An example of bootstrapping patterns. The three rounded rectangles in the horizontal layout represent three iterations of bootstrapping; the three vertically distributed rectangles within, from top to bottom, are the extracted synonyms, newly added regular expression patterns, and related definitions.

Table 4.

A list of patterns manually selected from those suggested by bootstrapping

In practice, the resulting synonym and pattern sets converge fairly quickly, since circular definitions within a dictionary are usually limited to a small number of entries. The resulting pattern set captures most of the patterns under which one synonym is used to define another; it also accommodates some of the typographical variations, such as the ending period in definitions (^.*; (\w+)\.$ versus ^.*; (\w+)$). It is also worth noting that, since there is no constraint on part of speech in this process, patterns that are apparently for verbs, e.g., ‘^to(\w+)\.$’, are mixed together with those for nouns, e.g., ‘^.*; a(\w+)\.$’. This might have some negative effects on the algorithm's efficiency, but not the performance, since POS constraints can always be easily imposed by checking the words' POS tags in the dictionary.

The seemingly simple seed patterns (e.g., ‘^.*; (\w+\)$’, ‘^.*; (\w+\)\.$’, and ‘^.*; \w+\;.*$’) can in fact match as many as 15,228 (7.45%) definition texts in The Macquarie Dictionary. By bootstrapping, 16 more patterns have been discovered, doubling the coverage of the seed patterns (32,208 or 15.75% definition texts).

2.3.4 Transitive closure on the dictionary graph

One important feature of synonymy is transitivity, i.e., if word a is synonymous to word b and b to c, then it is usually plausible to infer synonymy between a and c. Considering the common problem of dictionaries' low coverage on synonymy extraction, this property is especially useful since transitivity allows one to take c, and even synonyms of c, as synonyms of a.

On the other hand, the more the rule of transitivity is applied, the less synonymous the resulting synonyms will become to the target word. We can view the output of PbE as a tree structure, with the root of the tree being the target word w, and the immediate children the extracted synonyms in first round PbE (S = {s ₁,. . .,s _n}). When there is more than one iteration of PbE, each synonym s _i ∈ S is taken to be the root of a subtree, from which sprout more proposed synonyms. The degree of synonymy between w and a child node s will certainly decrease with the increasing depth of s. Nonetheless, due to the circular nature of dictionary definitions, there must be cases in which certain paths in the tree would return to w after several iterations. Here, we refer to a nonempty path p between w and itself as a transitive closure on the dictionary graph, and the intuition behind transitive closure filtering is that words on such paths should be more synonymous to the target word than those that ‘wander off’ and never come back. Thus, by finding these circles on the dictionary graph, transitive closure is an intuitively feasible way of dealing with the negative effect of polysemy on synonym transitivity.Footnote ⁵

Thus, to filter out false positives from PbE, only those words on transitive closures starting from the target word are proposed as synonyms. However, experiments show that transitive closure of only the target word is quite sparse; considering the fact that words extracted in the first round of PbE are usually highly synonymous to the target word, the filtering strategy is relaxed so as to include transitive closures of these words as well. Such relaxation has proved to be successful in that it increases the coverage at little cost to accuracy. In the example of fear, the extracted synonyms are: solicitude, anxiety, shock-horror, terror, and apprehend, while words, such as care, eagerness, jump, disease, understand, anticipate, conceit, and doubt, are filtered out (Figure 4). Both groups appeal well to intuition. When the extracted synonyms are compared with existing thesauri (Section 3.3), the precision of the filtered results increases by 18.3 percentage points on average, at a recall loss of about 7 percentage points.

Fig. 4.

Transitive closure filtering (bold for extracted synonyms, strikeout for the filtered words).

2.4 Extraction using maximum entropy

Although PbE exhibits excellent extraction precision (Section 3), coverage is still low due to the limited number of patterns. This motivates general learning methods that treat definition texts in a more generic manner. As an initial attempt at machine learning approaches for synonym extraction from definitions, we formulate the synonym extraction task as a labeling problem: each word in a piece of definition text is a decision point, and a maximum entropy (MaxEnt) classifier is trained to decide whether a word is a synonym of the corresponding definiendum.

The training data consist of 186,954 definition items (definiendum with corresponding definientia) in the Macquarie Dictionary. After POS-tagging,Footnote ⁶ any word in a given definition text is labeled as a synonym of the definiendum if the word is (1) of the same POS as the definiendum, and (2) in the same WordNet synset as the definiendum.

We choose the opennlp.maxent implementation of the classifier with generalized iterative scaling (GIS) capacity.Footnote ⁷ For each word in the definientia of a given target word, we use lexical features (previous, current, and next word), unigram POS features (previous, current, and next POS), and bigram POS features (previous and next POS bigrams). In addition, another group of features describes the position of each decision point by an integer counter starting from 1 to the length of a definition text. In order to capture the separators discussed in PbE (e.g., semicolons), a second position counter is included which resets to 1 whenever encountering any separators. For example, in the definition of abbreviation: ‘reduction in length; abridgment.’, the first counter assigns integers 1 to 6 to all definientia (including punctuation ‘;’ and ‘.’), whereas the second counter assigns 1 to 4 to definientia up to the semicolon but 1 and 2 to abridgment and the period.

As we can see, the features of choice are very ‘local’ to the target word. We tried incorporating larger windows of context as features, but this did not perform as well. This suggests that, unlike in semantic similarity tasks, words from a larger context bring in more noise than useful information in predicting synonyms within definition texts.

Note that in order to make fair comparisons with IIE and PbE in terms of coverage, it is necessary to incorporate the dictionary graph into the MaxEnt method. Specifically, given a target word t, after extracting synonyms from its own definientia, we again go through other words' definitions in the dictionary; if t appears in the definition of another word w and is classified as a synonym, then w is taken as a synonym of t.

2.5 Interpretation of the methods in terms of the dictionary graph

So far in our discussion, the dictionary graph has been assumed to be undirected. For IIE, if we are to take the graph as directed (with edges pointing from definienda to definientia), then the in-neighbors of a target word are those related by an inverted index, and the out-neighbors are simply all its definientia. We will see how these two types of relatedness perform differently in Section 3.

In contrast, PbE and MaxEnt make fine distinctions about which part of the definitions to relate a target word to. For out-neighbors (words in the definientia of the target word), PbE and MaxEnt choose words that follow specific patterns (either regular expression patterns or, implicitly, patterns learned by a classifier), as opposed to IIE, which takes all definientia indiscriminately; for in-neighbors, IIE relates them all regardless of how or where the target word appears in other words' definitions, while PbE and MaxEnt, again, follow their respective patterns.

3.1 The machine-readable dictionaries

The machine-readable dictionaries used in this study are an electronic version of Macquarie Dictionary (Delbridge Reference Delbridge1981) and the WRUD.Footnote ⁸The Macquarie Dictionary is contained in an SGML-tagged file of 63 MB with 78 types of tags. Information about each lexical entry, including pronunciation, part(s) of speech, definitions, related phrases, etc., is represented by a tree structure of tags, rooted at a tag named RECORD. There are altogether 106,964 such entries in the machine-readable dictionary. Figure 5 shows an example of the tree structure of SGML tags for the entry word dictionary.

Fig. 5.

The tree structure of SGML tags for the entry dictionary in The Macquarie Dictionary.

WRUD has 182,698 entries, each on a separate line in one of the 26 HTML-marked files corresponding to the English letter the entry word starts with. The main structure in each entry consists of the entry word form, its part of speech (if any), and the definition text. Multiple senses of the same word form occupy separate lines (and thus, only 115,773 distinct word forms are defined in the dictionary). Figure 6 shows an excerpt from the WRUD for the word dictionary.

Fig. 6.

Entries for the word dictionary in WRUD.

3.2 Solving TOEFL synonym questions

3.2.1 Experimental setup

Our first evaluation is to use the extracted synonyms to solve TOEFL synonym questions. TOEFL is a standardized test for assessing the English level of nonnative speakers. Part of the test is on synonymy, where each question consists of a question word and four candidates, one of which is a synonym to the question word and therefore the correct answer. Landauer and Dumais (Reference Landauer and Dumais1997) first compiled and used 80 of these questions, which have been frequently used as an evaluation benchmark in later lexical semantics studies.Footnote ⁹

In essence, this evaluation method is to establish a mapping between synonymy and semantic similarity. For any word pair w ₁ and w ₂, a similarity measure can be constructed by, for example, computing the overlap between the synonym sets of the pair S _i = {s _i1,. . .,s _{in i}}, i = 1, 2 (hence, a Jaccard similarity). The semantic similarity between w ₁ and w ₂ is then given by:

(1)

For a TOEFL synonym question, the similarity between the question word and each of the candidates can now be computed, and the candidate with the highest score is the proposed correct answer.

Under the question word fabricate, as an example, there are four choices construct, alter, select, and demonstrate. Each word is firstly associated with the synonym set proposed by a synonym extraction algorithm, say, IIE; the question word gets the set {fabricate, coin, trump up, prefabricate, mint, invent, forge, spin}, the first candidate construct gets {construct, fabricate, cantilever, improvise, laminate, . . .}, and so on. Note that a word is always considered a synonym to itself and thus included in the synonym set. In the above synonym question, the first candidate construct is the only one with a set that overlaps with the set of the question word, and consequently, it receives the highest score and is considered the correct answer.

Scores on this experiment are easy to interpret and are positively correlated to the degree of synonymy of the extracted synonyms to their target word and thus the similarity score by (1). However, this evaluation also bears several immediate problems. First, synonymy is sufficient but not necessary for achieving higher similarity scores. Suppose, as an extreme example, that the sets S _i consist of antonyms instead of synonyms to the corresponding target words w _i (i = 1, 2); two synonyms are likely to have similar antonyms, and the two sets S ₁ and S ₂ can also correlate well and achieve better scores in the same synonym questions. Consequently, higher scores in such tests are only necessary but not sufficient to infer synonymy between the target words and their corresponding extracted sets. Moreover, two choices might have exactly the same Jaccard similarity with the question word.Footnote ¹⁰ It is also possible that none of the choices overlap with the question word (i.e., none of them share any synonyms with the question word) or that the synonym set for the question word is empty. For IIE, for example, the number of extracted synonyms is very limited when the target word is uncommon. This turns out to be especially problematic in the TOEFL questions, since one of the characteristics of the exam is to test nonnative speakers on an advanced vocabulary with many uncommon words.

In contrast, similarity-based approaches usually assign nonzero scores to most word pairs. Consequently, results reported in such studies are only concerned with how many questions were correctly solved. Here, questions with ties are taken to be ‘unsolvable’ and no choice would be assigned. Thus, the results later presented borrow the notions of precision and recall from information retrieval. Recall, in this case, denotes the proportion of questions that have nonzero scores, and thus, are solvable by choosing the highest score among the four, while precision denotes how many are solved correctly among these solvable questions.

One way to break ties is to improve coverage by combining IIE or PbE synonym sets with definientia. Specifically, for two target words w ₁ and w ₂, we use v _i = S _i ∪ D _i, i = 1,2 as their feature sets, where D _i = {d _i1,. . .,d _{im i}} are words from their respective definientia. To differentiate two types of features, more weights are assigned to synonyms than to ordinary definientia: suppose w ₁ and w ₂ have two common elements v _1i and v _2j in the ith and jth positions of their feature vectors, and the weight is α for synonyms and β for ordinary definientia. If v _1i ∈ S ₁ and v _2j ∈ S ₂ (i.e., both from IIE/PbE results), then this overlapping is weighted by α²; if v _1i ∈ S ₁ while v _2j ∈ D ₂ (or the other way around, i.e., one from IIE/PbE the other from definientia), then the overlapping weight is α⋅β; if both are parts of the ordinary definientia, then the weight becomes β². In the current implementation, α = 5 and β = 1 (estimated by maximum likelihood using grid search on integer values).

We also compare to a baseline algorithm using only the definientia of each target word, which resembles the Lesk algorithm used in word sense disambiguation (Lesk Reference Lesk1986). The comparison is interesting in that IIE and PbE try to distinguish synonyms from the rest of the definientia, while the baseline uses them all indiscriminately; improvements over the baseline would thus reflect how well the discrimination is made.

3.2.2 Evaluation results

Table 5 shows the results of solving TOEFL synonym questions by the three models and some of their variants. IIE_in and IIE_out denote variants of IIE with in-neighbors only and out-neighbors only, respectively; IIE without subscripts corresponds to the original IIE method (with both in- and out-neighbors). Due to the low coverage, half of the questions have ties when using IIE. Nonetheless, for the solvable ones, IIE scores 100% in precision. PbE, on the other hand, exhibits higher recall although by a very small margin.

Table 5.

Evaluation of extracted synonyms on TOEFL synonym questions. Each cell contains two numbers from The Macquarie Dictionary and WRUD, respectively, separated by dashes

Error analysis on the tied questions reveals that they are due to diminished synonym sets that do not overlap with one another. For the question 〈functional: alternate; unknown; original; usable〉, for example, although all of the five words have nonempty synonym sets from The Macquarie Dictionary, none of them have any word in common, and thus, all four candidates receive a score of zero. For inflected words in the data, using base forms in IIE and PbE improves the coverage (recall) by a large margin (25.0 and 22.5 percentage points, respectively) even through a very simple lemmatization process.

When used ‘as-is’, WRUD has rather poor coverage compared to The Macquarie Dictionary. Error analysis reveals that the dictionary has no entries even for some not-so-rare words, such as expendable, unpredictable, and optimal. Some frequent senses of words, for example, the adjective sense of key meaning ‘important’, are missing from the dictionary too. Most of these words and senses, according to the Oxford English Dictionary, have come to frequent use only after the Webster's Revised Unabridged Dictionary (and thus entries in WRUD) were compiled (in 1913). We thus skipped all the words that are not defined in WRUD in the experiment.

The best F₁ score is achieved by the weighted PbE+Definientia approach on The Macquarie Dictionary, which, by including the definientia in the feature vectors, significantly improves the recall (20.0 percentage points) at a relatively smaller cost to precision (3.0 percentage points).

The percentage of correctly solved questions is equivalent to ‘accuracy’ in Table 5. We compare our results to the state-of-the-art results reported on the ACLweb wiki (see footnote 9). As of February 2011, the top six results listed there are achieved by either corpus- or Web-based approaches, ranging from 0.975 to 0.813 in accuracy. The best lexicon-based method ranks seventh at 0.788 (Jarmasz and Szpakowicz Reference Jarmasz and Szpakowicz2003), which is approximately 10 percentage points lower than PbE with definientia. When using only the extracted synonyms as feature vectors, PbE is still comparable to existing results. Due to its low coverage, however, it is still about 9 percentage points below the best performing hybrid model (0.975, Turney et al. Reference Turney, Littman, Bigham and Shnayder2003).

3.3 Comparison against a combined thesaurus

The experiment discussed in this section resembles that of Wu and Zhou (Reference Wu and Zhou2003). Target words are first selected from a corpus according to POS and frequency. A thesaurus is then constructed by combining WordNet synsets and an on-line version of Roget's Thesaurus (Roget Reference Roget1911).Footnote ¹¹ Note that this version of Roget's Thesaurus groups together synonyms and other related words of various POS. We only used those of the same POS as the target word. After synonym extraction algorithms are applied to the target words, the resulting synonym sets are compared against the combined thesaurus.

The corpus for choosing the target words is the 1987–1989 Wall Street Journal (WSJ). POS of these target words include nouns (NN), verbs (VB), and adjectives (JJ). Word frequencies range from approximately 8,000 (high) to 1,000 (medium), to 50 (low) occurrences in the corpus. The combined thesaurus is constructed in exactly the same manner as by Wu and Zhou (Reference Wu and Zhou2003), i.e., given a target word, its corresponding WordNet synsets and synonym sets from Roget's Thesaurus are extracted and combined into a larger synonym set. The resulting thesaurus is then used as a gold standard against which the extracted synonyms are compared. The final results are reported in terms of precision, recall, and F₁.

The results for PbE, IIE, and their variants are listed in Table 6. The letters H, M, and L stand for the high, medium, and low frequency of target words in the WSJ, and P, R, F₁, for precision, recall, and F₁, respectively. Due to the computational intensity of MaxEnt, it is implemented only on nouns to compare with the result by Wu and Zhou (Reference Wu and Zhou2003), which is shown in Figure 9.

Table 6.

Evaluation of extracted synonyms on the combined thesaurus

As is shown in Table 6, the output of IIE does not correlate well with the combined thesaurus. Precision is, in general, slightly better than recall, but F₁ seldom exceeds 5%. Also notice that IIE performs best on mid-frequency words, mainly because these words are neither too frequent to appear in many words' definitions (as are high-frequency words and hence their low precision), nor too rare to not appear at all (as are low-frequency words and hence their low recall).

In contrast, PbE exhibits significant improvements over IIE on both precision and recall (on average, twice as high in precision and five times in recall). It also appears more robust to variation in frequency. After the transitive closure filtering, the precision of PbE is almost tripled, which, at a relatively small cost of recall drop (6–7 percentage points), yields the best F₁ score among all proposed methods. A combination of the filtered versions of PbE and IIE is also shown, but the result (the last group of data) is rather disappointing.

Since POS is not of primary interest here, we average the results across the three different POS. Figure 7 shows how IIE compares with PbE across different target word frequencies. On average, PbE has slightly better precision and drastically better recall, resulting in F₁ scores approximately 3–5 times as high as those of IIE. The performance of IIE is apparently ‘spiked’ at medium target word frequency, confirming our previous hypothesis that IIE would underperform when the target word frequency is too low or too high. In contrast, PbE exhibits ‘smoother’ performance especially in precision and F₁ score.Footnote ¹²

Fig. 7.

Inverted index extraction versus pattern-based extraction when compared with existing thesauri. High, Medium, and Low refer to different frequencies of target words in the Wall Street Journal.

Precision of PbE increases as target word frequency decreases. We speculate that this is because the degree of polysemy of a word is approximately in proportion to its frequency; high-frequency words, being more polysemous, would have more chance of ‘digressing’ to various branches of different senses; they also tend to appear in many different words' definitions under different senses. This is especially true when transitivity of synonymy is applied with no constraints. We will show shortly how transitive closure on the dictionary graph helps alleviate this problem.

The drop of recall in PbE with respect to frequency can be explained by different in- and out-degree of target words of different frequencies. Words of higher frequency would not only have a higher out-degree (due to their polysemy), but also a higher in-degree since they are more likely to appear in other words' definitions. In contrast, low-frequency words would have fewer senses and thus smaller numbers of definitions; if they are too infrequent to appear in other words' definitions, then these few definitions of their own would be the only source for synonyms, which would, not surprisingly, result in lower recall.

We also compared PbE with transitive closure calculated using WRUD. The trends across POS and frequencies are similar to that obtained from The Macquarie Dictionary. Recall is significantly higher for WRUD results, but F₁ score, in general, is lower due to very low precision, which we think is due to the following reasons. First, the entries in WRUD are sometimes of low quality. Some words are defined in uncommon senses (e.g., countenance as ‘To make a show of; to pretend’ and ‘To encourage; to favor; to approve; to aid; to abet’), others are spelled in obscure or nonexistent variations (e.g., counttenance as ‘The face; the features’). Second, unlike The Macquarie Dictionary, WRUD does not have usage labels (e.g., archaic, agricultural) that can suppress paths along nontypical usage of word forms in the construction of transitive closure (and thus, it also explains the high recall).

Figure 8 shows the improvement in PbE performance by finding transitive closure as mentioned in Section 2.3.4. Recall drops to about half of the original values after using transitive closure (denoted PbE_tc in the graph), but meanwhile precision is more than tripled in all frequencies. It is interesting to observe how precision responds differently to frequency change before and after using transitive closure: without transitive closure, precision increases as frequency decreases, while after transitive closure is introduced, it varies in the opposite direction. This indicates that using transitive closure is most helpful for high-frequency target words. This is, again, due to their polysemy and better chances of ‘digression’, and thus, transitive closure indeed helps to effectively eliminate false positives introduced by such digressions; low-frequency words would already have relatively better precision due to their having fewer senses, and transitive closure appears less helpful in this case.

Fig. 8.

Performance before and after using transitive closure on pattern-based extraction (denoted PbE and PbE_tc, respectively). High, Medium, and Low refer to different frequencies of target words in the Wall Street Journal.

Figure 9 shows how our methods compare with other published results. IIE is outperformed by all other methods by large margins. PbE has the best precision (32.9%) but falls behind that of Wu and Zhou (Reference Wu and Zhou2003) in terms of F₁ due to low recall. MaxEnt has better recall than both IIE and PbE, but F₁ score is not as good as that of PbE. The results of Blondel and Senellart (Reference Blondel and Senellart2002) are included as an example of dictionary-based method for comparison, and Lin (Reference Lin1998) as an example of corpus-based approach.Footnote ¹³ Wu and Zhou (Reference Wu and Zhou2003) combined the methods of Blondel and Senellart (Reference Blondel and Senellart2002) and Lin (Reference Lin1998), as well as a novel method using bilingual resources, achieving the best F₁ score among all methods being compared here. Their experiments did not include adjectives; when comparing the results on nouns and verbs, however, the precision of PbE with transitive closure filtering is, on average, 6 percentage points higher than their best result on nouns and 14.3 percentage points higher on verbs. Coverage, however, still remains a major issue, with recalls of PbE_TC filtering on both nouns and verbs lower than that of Wu and Zhou (Reference Wu and Zhou2003) (11.3% and 16.1 percentage points, respectively). As one advantage of using a dictionary as a source for synonym extraction, PbE and IIE both exhibit robustness across different POS.

Fig. 9.

Comparing with published results on the combined thesaurus experiment.

3.4 Definition text labeling

This section describes an intrinsic task on identifying synonyms within definition texts. Recall that the MaxEnt model labels synonyms in a piece of definition text for a given target word; in fact, PbE and IIE could also be viewed as a synonym labeling processes in definition texts. The basic idea of this third experiment is to see how well each method performs in such a labeling task.

The construction of data was described in Section 2.4; it does not necessitate any human labeling, though at the cost of the quality of synonym labels (to be discussed below). The labeling criteria for the three methods follow the discussion in Section 2.5: IIE takes all definientia as synonyms, while PbE takes only those following prespecified patterns. MaxEnt makes predictions for each defining word based on training. We also introduce a baseline that chooses a defining word as a synonym as long as it has the same POS as that of the definiendum.

The results are presented in Figure 10. The baseline and IIE both have 100% recall by experimental design. IIE and PbE are both outperformed by the baseline. PbE has the highest precision and meanwhile, the lowest recall due to its dependence on specific patterns.

Fig. 10.

Performance on synonym labeling in definitions.

Due to the low quality of the training data, MaxEnt did not perform as well as expected. POS tags have many discrepancies, partly because the tagger is not trained on definition texts. On the other hand, using WordNet to create the gold standard in synonym labels also appears to be error-prone. For example, in the definition of ability (power or capacity to do or act. . .), power is labeled as a synonym of ability while capacity is not, since it is not in the same synset as that of ability. There are also cases where words in insignificant positions within the definition text happen to be in the same synset as that of the definiendum. All such cases will eventually confuse the learning process of MaxEnt.