2.1.1 Path based measures

Path based measures determine the length of the path between nodes representing concepts in a semantic graph structure (e.g., a wordnet, a thesaurus, or the Wikipedia category graph). The shorter the path, the higher the relatedness between concepts.

Rada et al. (Reference Rada, Mili, Bicknell and Blettner1989) use the path length l between two nodes to compute semantic relatedness. This measure (Rad89) can either be a SemSim or SemRel measure depending on the type of edges that are allowed in a path. For example, if only edges corresponding to classical lexical semantic relations are allowed, Rad89 is a SemSim measure. However, if also edges corresponding to nonclassical relations are allowed, it is a SemRel measure. Rad89 can be computed as follows:

where dist means that the measure returns a distance value instead of a relatedness value, and l(c ₁, c ₂) returns the number of edges on the path from c ₁ to c ₂. The distance value can be easily transformed into a relatedness value by subtracting it from the maximum path length of the graph, rel _Rad89(c ₁, c ₂) = l _max − l(c ₁, c ₂).

Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003) (JS03) adapt the Rad89 measure to Roget's thesaurus as a knowledge source based on the work of McHale (Reference McHale1998) (McH98). JS03 is also a relatedness measure as the relations in Roget's thesaurus are not restricted to classical lexical semantic relations.

As polysemous words may have more than one corresponding concept in a lexical semantic resource, the resulting semantic relatedness score between two words w ₁ and w ₂ can be calculated as

where C(w _i) is the set of concepts that represent senses of word w _i. That means, the relatedness of two words is equal to the score of the least distant/most related pair of concept nodes, depending on whether the measure returns a relatedness rel(c ₁, c ₂) or a distance dist(c ₁, c ₂) value.

Leacock and Chodorow (Reference Leacock and Chodorow1998) (LC98) normalize the path length with the depth of the graph,

where depth is the length of the longest path from the root node of the taxonomy to a leaf node. The prefix sim means that the measure is a similarity measure in its original definition, as it was defined on WordNet using only taxonomic links. The scaling factor 2⋅depth assumes a tree-like structure, where the longest possible path runs from a leaf to the root node and back to another leaf node. The length of the path l(c ₁, c ₂) is measured in nodes.

These simple path length methods do not take into account that concepts higher in the taxonomy are more abstract, i.e., that a path with a length of 1 between abstract concepts near the top of the taxonomy should yield a lower similarity value than a path of the same length between specific concepts on the leaf level of the taxonomy. Many measures have been proposed to overcome this limitation. For example, Wu and Palmer (Reference Wu and Palmer1994) introduce a measure (WuP94) that uses the notion of a lowest common subsumer of two concepts lcs(c ₁, c ₂). A lcs is the first shared concept on the paths from the concepts to the root concept of the hierarchy.

WuP94 is a similarity measure, as a lcs is only defined in a taxonomy.

Hirst and St-Onge (Reference Hirst, St-Onge and Fellbaum1998) adapt a measure (HSO98) originally described by Morris and Hirst (Reference Morris and Hirst1991) (MH91) to work with WordNet instead of Roget's Thesaurus (Roget Reference Roget, Berrey and Carruth1962). Using the HSO98 measure, two words have the highest relatedness score, if (i) they are in the same synset, (ii) they are antonyms, or (iii) one of the words is part of the other (e.g., car and car park). In all other cases, relatedness depends on the path between the concepts, where long paths and direction changes (upward, downward, horizontally) are penalized. The resulting formula is

where C and k are constants, len is the length of the path and turns counts the number of direction changes in the path. The HSO98 measure is a relatedness measure as paths are not restricted to taxonomic links.

2.1.2 Information content based measures

Information content (IC) approaches are based on the assumption that the similarity of two concepts can be measured by the amount of information they share. In a taxonomy, the shared properties of two concepts are expressed by their lowest common subsumer lcs. Consequently, Resnik (Reference Resnik1995) defines semantic similarity (Res95) between two nodes as the information content value of their lcs:

The information content of a concept can be computed as

where p(c) is the probability of encountering an instance of c in a corpus. The probability p(c) can be estimated from the relative corpus frequency of c and the probabilities of all concepts that c subsumes. This definition of IC is bound to the availability of a large corpus, and the obtained IC values are relative to that corpus. Hence, Seco et al. (Reference Seco and Hayes2004) introduce the intrinsic information content which is computed only from structural information of the taxonomy and yields better results on some English datasets. It is defined as:

where hypo(c) is the number of all hyponyms of a concept c and |C| is the total number of concepts in the taxonomy.Footnote ⁴

Jiang and Conrath (Reference Jiang and Conrath1997) define a measure (JC97) derived from Res95 by additionally using the information content of the concepts. The original formula returns a distance value, but can be easily transformed to return a relatedness value instead.

Lin (Reference Lin1998) defines a universal measure (Lin98) derived from information theory.

The WuP94 measure is a special case of this formulation.

2.1.3 Gloss based measures

Dictionaries or wordnets usually contain short glosses for each concept that are used by gloss based measures to determine the relatedness of concepts.

Lesk (Reference Lesk1986) introduces a measure (Les86) based on the amount of word overlap in the glosses of two concepts, where higher overlap means that two terms are more related.

where gloss(c _i) returns the multiset of words in a concept's gloss.

Banerjee and Pedersen (Reference Banerjee and Pedersen2002) propose a more sophisticated text overlap measure (BP02) that additionally takes into account the glosses of related concepts forming an extended gloss extGloss. This overcomes the problem that glosses in WordNet are very short. The measure is defined as:

where extGloss(c _i) returns the multiset of content words in the extended gloss.

Mihalcea and Moldovan (Reference Mihalcea and Moldovan1999) take a similar approach in their word sense disambiguation system. They construct a linguistic context for each noun or verb sense c _i by concatenating the nouns found in the glosses of all WordNet synsets in the subhierarchy of c _i. The relatedness between two senses is then computed as the number of overlapping nouns in the corresponding contexts.

Gloss based measures cannot be used directly with semantic graph structures without textual definitions of concepts such as the German wordnet GermaNet (Kunze Reference Kunze, Carstensen, Ebert, Endriss, Jekat, Klabunde and Langer2004). Therefore, Gurevych (Reference Gurevych2005) constructed pseudo glosses (Gur05) by concatenating concepts that are in close relation (synonymy, hypernymy, meronymy, etc.) to the original concept. This is based on the observation that most content words in glosses are in close relation to the described concept. For example, the pseudo gloss for the concept tree (plant) would be ‘woody plant, ligneous plant, stump, tree stump, crown, treetop, limb, tree branch, trunk, tree trunk, bole, burl, ...’ showing a high overlap with its WordNet gloss ‘a tall perennial woody plant having a main trunk and branches forming a distinct elevated crown’. The measure can be formalized as follows:

where pseudoGloss(c _i) returns the multiset of content words in the pseudo gloss.

2.1.4 Vector based measures

In this section, we focus only on SemRel measures where concept vectors are derived from a knowledge source, rather than on distributional vectors derived from cooccurrence counts. Thus, we use the term vector based measure interchangeably with concept vector based measure.

Patwardhan and Pedersen (Reference Patwardhan and Pedersen2006) represent a concept by a second-order gloss vector using WordNet glosses (PP06). They start with first-order context vectors, i.e., a vector of cooccurrence counts for each content word in a corpus. In this case, the corpus is the set of WordNet glosses. A second-order gloss vector glossVector(c _i) is then constructed from the gloss of the target concept c _i by combining the first-order gloss vectors of words that appear in that gloss. For example, from the gloss of tree (plant) ‘a tall perennial woody plant having a main trunk and branches forming a distinct elevated crown’, the algorithm would construct a second-order gloss vector from the first-order gloss vectors of plant, trunk, branches, crown, etc. The relatedness of two concepts is then computed as the cosine of the second-order gloss vectors.Footnote ⁵

Patwardhan and Pedersen (Reference Patwardhan and Pedersen2006) also introduce a variant of this algorithm to compensate for short glosses, where a gloss is augmented with glosses of concepts that are in close relation to the original concept. This is conceptually close to the extended BP02 measure described in the previous section.

Gabrilovich and Markovitch (Reference Gabrilovich and Markovitch2007) introduce another vector based measure (GM07), where the meaning of a word w is represented as a high-dimensional concept vector (w) = (d ₁,. . ., d _N). Each element d _i represents a document, and the value of d _i depends on the occurrence of the word w in this document. This is very similar to the approach by Qiu and Frei (Reference Qiu and Frei1993) for constructing a similarity thesaurus used in information retrieval.

Gabrilovich and Markovitch (Reference Gabrilovich and Markovitch2007) derive the concept vector from Wikipedia articles a ₁,. . ., a _N, as each article focuses on a certain topic, and can thus be viewed as expressing a concept. The dimension of the concept vector is the number of Wikipedia articles N. Each element of the concept vector is associated with a certain Wikipedia article a _i. If the word w can be found in this article, the word's tf.idf score (Salton and McGill Reference Salton and McGill1983) in the article a _i is assigned to the concept vector element d _i. Otherwise, 0 is assigned.

As a result, the vector (w) represents the word w in concept space. Semantic relatedness of two words can then be computed as the cosine of their corresponding concept vectors:

Generalizing the GM07 measure The GM07 measure relies on Wikipedia articles. However, the measure can be generalized to each knowledge source containing textual descriptions of concepts. WordNet contains glosses that can be seen as very short ‘articles’ describing the concepts expressed by WordNet synsets. For example, the term car is contained in more than 250 glosses of WordNet concepts including nouns (e.g., polishing, ‘every Sunday he gave his car a good polishing’), verbs (e.g., damage, ‘She damaged the car when she hit the tree’), and adjectives (e.g., unfastened, ‘the car door was unfastened’). Each of these concepts leads to a nonzero entry in the resulting concept vector for car. When computing semantic relatedness, the whole vector is taken into account, and so are all the implicit relations to car-related concepts encoded in the glosses. In the case of GermaNet, that contains only few glosses, we need to construct pseudo glosses (as described in the context of the Gur05 measure) as a proxy for textual descriptions of a concept.

In general, we can define a concept vector based measure (ZG07) (Zesch and Gurevych Reference Zesch and Gurevych2007) that can also be applied to WordNet (by using glosses), GermaNet (by using pseudo glosses), or to any other knowledge source where we can retrieve or construct a textual description for each concept. In very recent work, the ZG07 measure was also adapted to entries in the wiki dictionary Wiktionary (Zesch et al. Reference Zesch, Müller and Gurevych2008). Wiktionary combines a collaborative construction approach with explicitly encoded lexical semantic relations, glosses, translations, etc. Thus, it provides a rich set of focused additional knowledge associated with each concept.

3.1.1 Evaluation measures

Semantic relatedness measures can be evaluated using two different correlation methods. The first method is to correlate the scores computed by a measure with the numeric judgments of semantic relatedness provided by humans. For example, on a 0–4 scale, where 4 is maximum relatedness, the pair ‘car–automobile’ might get a human judgment of 3.9 and a score of 3.7 from a measure. A second pair ‘car–garden’ only gets 1.1 (human) and 0.4 (machine). The Pearson product-moment correlation coefficient r can be employed as an evaluation measure. It indicates how well the results of a measure resemble human judgments, where a value of 0 means no correlation and a value of 1 means perfect correlation.

The second method is correlating word pair rankings. In a ranking task, a human and a measure would simply rank the pair ‘car–automobile’ higher than ‘car–garden’. The ranking produced on the basis of the measure is compared to the one produced on the basis of human judgments. The quality of such a ranking is quantified by the Spearman rank order correlation coefficient ρ, where a value of 0 means no correlation and a value of 1 means perfect correlation.

Existing work on computing SemRel often employed Pearson correlation. However, this suffers from some limitations: First, Pearson correlation is very sensitive to outliers. Even a single outlier might yield fundamentally different results. This is visualized by Anscombe's quartet (Anscombe Reference Anscombe1973), a set of four scatterplots showing relationships with exactly the same mean, standard deviation, regression line and Pearson correlation of r=0.81 (see Figure 6). In the bottom figures, a single outlier is sufficient to disturb a perfect correlation (bottom left) or produce a high correlation in a fully nonlinear relationship (bottom right).

Fig. 6.

‘Anscombe's quartet’ showing relationships with exactly the same mean, standard deviation, regression line, and Pearson correlation of r=0.81. (Adapted from http://en.wikipedia.org/wiki/Image:Anscombe.svg)

Second, Pearson correlation measures the strength of the linear relationship between human judgment and SemRel scores computed by a measure. If a relationship is not linear, results are flawed. For example, the upper right chart in Figure 6 shows a nonlinear relation that cannot be correctly measured using Pearson correlation.

Third, Pearson correlation requires the two random variables (the vectors) to be normally distributed and measured on interval scales. In Figure 6 only the variables in the upper left plot fulfill the prerequisite of being normally distributed. However, the real distribution of relatedness values is largely unknown. The values of most samples (small subsets of word pairs judged by humans) are not normally distributed. Recent findings (Budanitsky and Hirst Reference Budanitsky and Hirst2006; Zesch and Gurevych Reference Zesch and Gurevych2007) even indicate that the relatedness values as perceived by humans are not interval scaled.

In contrast to these limitations, Spearman's rank correlation coefficient is robust against outliers, and can also measure the strength of nonlinear relationships. It does not pose the assumption of interval scales, i.e., it can be used for variables measured on the ordinal level. Additionally, Spearman's ρ does not make any assumptions about the distribution of the vectors being compared. However, there are also some disadvantages of using Spearman rank correlation to evaluate the performance of SemRel measures. From the statistical literature, it is known that Spearman's ρ tends to give higher values than Pearson's r for datasets with many tied ranks. For some applications, that rely on thresholding SemRel values, a measure that yields a perfect ranking might be of little use, if the differences between SemRel scores are too small to be sensibly thresholded.

For comparison with previous results, we report both Pearson's r and Spearman's ρ. Still, we recommend using Spearman rank correlation in future experiments, as this evaluation is more objective, if the performance of SemRel measures has to be evaluated intrinsically. As Pearson correlation and Spearman correlation are not directly comparable and might yield very different results under certain conditions, special care must be taken when comparing and interpreting such results.

3.1.2 Datasets

Evaluation datasets for correlation analysis are created by asking human annotators to judge the relatedness of presented word pairs. The gold standard score assigned to a word pair is the average score over all human judges (see Section 5.1 for a more detailed discussion on the creation of such datasets). For evaluation, a gold standard dataset is then correlated with the SemRel values computed by a particular measure.

An upper bound for the performance of a measure on a dataset is the inter-annotator agreement (InterAA), i.e., the amount of mutual agreement between human judges. InterAA is computed as the average pairwise Pearson correlation between human judges. As the distribution of Pearson's r is left-skewed, we cannot simply average the correlations, but have to use a Fisher Z-value transformation. In contrast to InterAA, the intra-annotator agreement (IntraAA) measures the agreement of a judge with herself over time. It is computed analogously to the inter-annotator agreement. Unfortunately, only very few experiments with intra-annotator agreement have been performed so far. Table 1 gives an overview of the datasets for evaluating SemRel described below. Table 2 reports the InterAA and IntraAA values for those datasets.

Table 1.

Datasets used for evaluating semantic relatedness

^a The parts-of-speech of words in the dataset. ‘N’ means noun, ‘V’ means verb, and ‘A’ means adjective or adverb.

Table 2.

Inter- and intra-annotator agreement on evaluation datasets. Missing values are not available from the references

Rubenstein and Goodenough (Reference Rubenstein and Goodenough1965) created a dataset with 65 English noun pairs (RG-65). No InterAA was reported for this dataset, but Pirro and Seco (Reference Pirro and Seco2008) repeated the experiment. The InterAA for native speakers is r=0.80. A subset of the RG65 dataset has been used for experiments by Miller and Charles (Reference Miller and Charles1991) (MC-30). Resnik (Reference Resnik1995) repeated the experiment (Res-30) and reported an InterAA of r=0.90.

As creating datasets of this kind is time consuming and costly, most work on evaluating SemRel measures focused on such small-scale experiments restricted to nouns (Li, Bandar and McLean Reference Li, Bandar and McLean2003; Budanitsky and Hirst Reference Budanitsky and Hirst2006; Patwardhan and Pedersen Reference Patwardhan and Pedersen2006). This leads to an effect of overfitting algorithms to these specific datasets and the employed knowledge source. Many algorithms yield near human performance on these particular datasets using WordNet as a knowledge source. This is due to the strongly related word pairs in these datasets being only related by classical lexical semantic relations that are well modeled in WordNet.

We argue that previous evaluations restricted to those datasets were limited with respect to (i) the number of word pairs involved, (ii) the parts of speech of word pairs, (iii) approaches to select word pairs (manual versus automatic, analytic versus corpus based), and (iv) the kinds of semantic relations that hold between word pairs. However, an evaluation involving the aspects described above is crucial to understand the properties of a specific measure and the results obtained under certain experimental conditions (e.g., the knowledge source used). Discovering the true nature of SemRel requires larger datasets with word pairs from different part of speech that are connected by classical as well as nonclassical relations.

Finkelstein et al. (Reference Finkelstein, Gabrilovich, Matias, Rivlin, Solan and Wolfman2002) created a larger dataset for English containing 353 word pairs (Fin-353). This dataset has been criticized in the literature (cf. Jarmasz and Szpakowicz Reference Jarmasz and Szpakowicz2003) for being culturally biased. Another problem with this dataset is that it consists of two subsets, which have been annotated by different human judges. The first subset also contains the 30 word pairs from MC-30. We performed further analysis of their dataset and found that the InterAA differs considerably for the two subsets (r=0.73 versus r=0.55). Therefore, we treat them as independent datasets Fin1-153 and Fin2-200 henceforth.

Yang and Powers (Reference Yang and Powers2006) created a dataset (YP-130) that contains 130 verb pairs. They report a high InterAA of r=0.87. As this dataset contains only verbs, the evaluation will be particularly informative about the ability of a SemRel measure to estimate verb relatedness.

Several German datasets have also been created (see Table 1). Gurevych (Reference Gurevych2005) conducted experiments with a German translation of the English RG-65 dataset (Gur-65). The subset of the Gur-65 dataset with the translated word pairs corresponding to the MC-30 dataset is called Gur-30.

As the Gur-65 dataset is small and contains only noun pairs connected by either synonymy or hyponymy, she conducted a follow-up study, and collected a larger dataset containing 350 word pairs (Gur-350). It contains nouns, verbs and adjectives that are connected by classical and nonclassical relations. However, word pairs for this dataset are biased toward strong classical relations, as they were manually selected. Thus, Zesch and Gurevych (Reference Zesch and Gurevych2006) propose an approach to create word pairs from domain specific corpora using a semi-automatic process (see Section 5.1 for a more detailed description). The resulting ZG-222 dataset contains 222 domain specific word pairs that are connected by different kinds of lexical semantic relations. As human judgments on domain specific word pairs depend on the domain knowledge of the judges, the InterAA is relatively low (r=0.49).

In Section 4.2, we describe the results of evaluating the SemRel measures introduced in Section 2.1 on the English and German datasets presented in this section.

3.2.1 Evaluation measures

A different approach to evaluate the performance of SemRel measures relies on word choice problems (Jarmasz and Szpakowicz Reference Jarmasz and Szpakowicz2003; Turney Reference Turney2006). A word choice problem consists of a target word and four candidate words or phrases. The objective is to pick the one that is most closely related to the target. An example problem is given below. There is always only one correct candidate, ‘a’ in this case.

The relatedness between the target and each of the candidates is computed by a SemRel measure, and the candidate with the maximum SemRel value is chosen. We lemmatize the target and all candidates. This is especially beneficial for German words that can be highly inflected.

If two or more candidates are equally related to the target, then the candidates are said to be tied. If one of the tied candidates is the correct answer, then the problem is counted as correctly solved, but the corresponding score is reduced. We assign a score s _i of (in effect approximating the score obtained by randomly guessing one of the tied candidates). Thus, a correctly solved problem without ties is assigned a score of 1.

If a phrase or a multiword expression is used as a candidate and cannot be found in the knowledge source, we remove stopwords (prepositions, articles, etc.) and split the candidate phrase into component words. For example, the target ‘beret’ in the above example has ‘cap with horizontal peak’ as one of its answer candidates. The candidate phrase is split into its component content words ‘cap’, ‘horizontal’, and ‘peak’. We compute semantic relatedness between the target and each phrasal component and select the maximum value as the relatedness between the target and the candidate. If the target or all candidates cannot be found in the knowledge source, a SemRel measure does not attempt to solve the problem. The overall score S of a SemRel measure is the sum of the scores yielded on the single problems S = , where A is the set of word choice problems that were attempted by the measure, and wp _i is a certain word choice problem.

Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003) used the overall score S for evaluation. However, this evaluation approach is problematic, as a measure that attempts more problems may get a higher score just from random guessing. Mohammad et al. (Reference Mohammad, Gurevych, Hirst and Zesch2007) used precision, recall and f-measure for evaluation. For word choice problems, recall is defined as R = , where n is the total number of word choice problems. Under that definition, if the score S is 0 then a SemRel measure has a recall of 0, regardless of how many word choice problems were attempted. This stands in contrast to the use of precision and recall in information retrieval, where just retrieving all documents will always give a recall of 1, regardless whether they are relevant or not. For word choice problems, just attempting all problems will only yield a recall of 1 if all attempted problems are correctly solved at the same time. Thus, for this task, recall is of very limited value for judging about the performance of a semantic relatedness measure. We therefore decided not to use precision and recall, but evaluate the word choice problems using accuracy and coverage instead. We define accuracy as Acc = , where S is the overall score as defined above and A is the number of word choice problems that were attempted by the SemRel measure. Coverage is then defined as Cov = , where n is the total number of word choice problems. Accuracy indicates how many of the attempted problems could be answered correctly, and coverage indicates how many problems were attempted.

3-2-2 Datasets

The English dataset contains 300 word choice problems collected by Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003). We collected a German dataset from the January 2001 to December 2005 issues of the German language edition of Reader's Digest (Wallace and Wallace, Reference Wallace and Wallace2005). We discarded 44 problems that had more than one correct candidate, and 20 problems that used a phrase instead of a single term as the target. The remaining 1008 problems form our German word choice dataset, which is significantly larger than any of the previous datasets employed in this type of evaluation. Additionally, it is not restricted to synonym problems, but also includes hypernymy/hyponymy, and some candidates that are related to the target by nonclassical relations.

We tested human performance on a subset of 200 manually selected German word choice problems using 41 native speakers of German. Human coverage on word choice problems is always perfect, as the experimental setting did not allow to skip word choice problems. We found that human accuracy on this task strongly depends on the level of language competence of the subjects. Average accuracy was Acc = 0.71 with σ = 0.10. We also observed a Pearson correlation r=0.69 between a subject's accuracy and her age (statistically significant, two tailed t-test with α=0.01). The highest accuracy was 0.91 (by the oldest subject), the lowest 0.45 (by the youngest subject).