3.1 Knowledge bases

Examples of knowledge bases include dictionaries, thesauri, wordnets, and encyclopedic resources. Some methods, especially earlier ones, have employed dictionaries and thesauri, such as Morris and Hirst (Reference Morris and Hirst1991), Kozima and Furugori (Reference Kozima and Furugori1993), and Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003). Most methods employ wordnets, and encyclopedic resources. Among these, the most frequently used general purpose knowledge bases include WordNet (Fellbaum Reference Fellbaum1998), Wiktionary,Footnote ¹ and Wikipedia.Footnote ² In the biomedical domain, domain-specific knowledge bases are also available, such as the Gene Ontology (GO) (The Gene Ontology Consortium 2005) and the Medical Subject HeadingsFootnote ³ (MeSH) biomedical vocabulary resource.

3.1.2 Biomedical knowledge bases

Despite the extensively studied general-purpose knowledge bases discussed above, studies in the biomedical domain generally prefer domain-specific knowledge bases due to their comprehensive coverage of biomedical knowledge. Such resources are exceptionally abundant in this domain, thanks to decades of extensive research devoted to this area. However, domain-specific knowledge bases in other technical domains are generally scarce. Biomedical knowledge bases are usually a structured vocabulary of technical terms, which often denote unique, specialized concepts. Several frequently used biomedical knowledge bases are briefly introduced below.

The Gene Ontology is the most often used knowledge base for semantic relatedness in the biomedical domain. GO provides ‘an ontology of defined terms representing gene product properties’ (GeneOntology.org), where each term refers to a unique concept. The terms are further divided into three sub-domains: cellular component, the parts of a cell or its extracellular environment; molecular function, the elemental activities of a gene product at the molecular level, such as binding and catalytic activities; and biological process, operations, or sets of molecular events relevant to the functioning of cells, tissues, organs, and organisms. For example, the term heart contraction is a concept of a biological process representing a property of the gene product Actin, alpha cardiac muscle 1. Each term is assigned a unique identifier; a term name which is a word or word sequence; a short definition similar to that of WordNet gloss; and a name space label indicating the sub-domain that the term belongs to. Terms are interlinked with other terms within or across sub-domains, by relations such as synonymy, hypernymy, meronymy, and domain-specific relations such as regulation.

The majority of studies in the biomedical domain exploit the GO as the background information resource (Pesquita et al. Reference Pesquita, Faria, Falcão, Lord and Couto2009). Also, many have exploited the semantic similarity between GO terms to assess similarity between genes or gene products annotated by these terms. The idea is that genes are similar if they share same properties, which are described by GO terms. Due to the similarity in its structure with WordNet, many of these methods have adapted WordNet-based methods or are developed based on similar rationales.

The MeSH is a comprehensive controlled vocabulary resource for indexing articles and books in the biomedical domain. It is structured as a hierarchy of ‘descriptors’, each of which is essentially a subject heading designed for the purpose of indexing. A descriptor is accompanied with a definition of the description; a list of synonyms or very similar names known as ‘entry terms’, in the sense that the same descriptor can be looked up using such terms. This is similar to the Wikipedia redirect mechanism. The descriptors are split into sixteen categories representing sub-topics such as organisms, diseases, and drugs. Descriptors of each category are organized as sub-hierarchies from most general to most specific levels. A MeSH descriptor may appear in multiple places in a hierarchy.

The Systematized Nomenclature of Medicine – Clinical Terms Footnote ⁴(SNOMED-CT) is a controlled vocabulary of medical terminology. The terminology is organized into thirteen hierarchies based on topics such as clinical findings, procedures, organisms, and substances, containing over 1 million concepts. Each concept is assigned a unique identifier, and provided with multiple ‘descriptions’, each of which is a name used to refer the concept. Thus, these are similar to the ‘entry terms’ in MeSH. The descriptions are divided into three types: a unique ‘Fully Specified Name (FSN) a “preferred term’, and one or multiple synonyms. Preferred terms and synonyms are names that are not unique to the concept, but can be shared by multiple concepts. Concepts in SNOMED-CT are organized as taxonomies following the hypernym relation. In addition, a number of domain-specific relations (e.g., ‘due to’, ‘causative agent’) are defined to connect concepts.

The Unified Medical Language System Footnote ⁵(UMLS) is a resource that maps a wide range of biomedical knowledge bases. Initiated in 1986, the objective is to create a structured knowledge base of biomedical science to facilitate the development of computer systems that can understand biomedical language. It contains three main knowledge bases: Metathesaurus, Semantic Network, and SPECIALIST lexicon. The Metathesaurus contains over 1 million biomedical concepts and 5 million concept names integrated from over one hundred knowledge bases (source vocabularies), including GO, MeSH, and SNOMED-CT. One of its main purposes is to group different names for the same concept from different source vocabularies. Each concept is assigned a unique identifier, one or multiple concept names, and pointers to their source vocabularies. Many relationships are encoded between concepts, including the hypernymy, meronymy, and synonymy relations. Relations encoded in source vocabularies are also retained. The Semantic Network defines a set of subject categories called semantic types, such as organisms, biologic functions, and chemicals. They are organized into a hierarchy representing the hypernymy relation, and also interlinked by many other non-hierarchical relations. The SPECIALIST lexicon is intended to be an English lexicon of both common English words and biomedical vocabulary. An entry is defined for each word or phrase, and records the syntactic, morphological, and orthographical information that can be used by NLP systems.

The Unified Medical Language System has been used in a wide range of NLP tasks in the biomedical domain. However, its usage in semantic relatedness is limited to the scope of individual knowledge bases it has integrated. The usefulness of the Semantic Network, for example, has not been investigated for this task. McInnes, Pedersen and Pakhomov (Reference McInnes, Pedersen and Pakhomov2009) developed a toolkit that allows adapting a number of WordNet-based methods to the UMLS Metathesaurus only. The Semantic Network is not used.

The Human Phenotype Ontology (HPO) is a vocabulary of approximately 9,000 terms referring to phenotypic abnormalities encountered in human disease (Kohler et al. Reference Kohler, Schulz, Krawitz, Bauer, Dolken, Ott, Mundlos, Horn, Horn, Mundlos and Robinson2009). A term in HPO denotes a unique concept, which has a unique identifier and a unique name. Some terms are provided with a short definition, and many terms have one or multiple cross-reference identifiers to UMLS concepts. Terms in HPO are grouped hierarchically following the hypernymy relation, where multiple parents of a term are allowed. Synonymy and meronymy relations are also defined between terms.

The Chemical Entities of Biological Interest (ChEBI) is ‘an ontology of molecular entities focused on small chemical compounds’ (Degtyarenko et al. Reference Degtyarenko, Matos, Ennis, Hastings, Zbinden, McNaught, Alcntara, Darsow, Guedj and Ashburner2007). It contains four sub-ontologies, each addressing one of the four topics: molecular structure, which classifies molecular entities or their parts according to their structure; biological role, which classifies entities based on their role in a biological context, such as antibiotics; application, which classifies entities or their parts by their intended use by humans, such as drugs; and subatomic particle that classifies particles smaller than atoms. Each entity is assigned a unique identifier and a ChEBI name, which is sometimes ambiguous and can refer to multiple entities. Entities are primarily organized following the hypernym relation. Synonymy and meronymy relations between entities are also encoded.

Table 1 summarizes the knowledge bases discussed above.

Table 1.

Summary of general purpose and domain-specific knowledge bases

GN: general purpose; DS: domain specific purpose.

3.2 Unstructured corpora

As mentioned before, unstructured corpora can be considered the background information resource for distributional similarity methods. Some semantic relatedness methods also employ unstructured corpora in certain ways. Unlike knowledge bases, unstructured corpora do not provide sense tagging of words or define lexical semantic relations in an explicit way. As a result, background information is collected at the level of words rather than concepts, and connects words in a rather implicit way. With distributional similarity methods, this is often in the form of textual contexts of words or their co-occurring behaviors within certain contexts based on a sufficiently large collection of documents. The hypothesis is that words that tend to occur in similar contexts are similar.

Some recent approaches have proposed mining lexical semantic network of words from unstructured document collections such that methods that use structured knowledge bases can be applied. For example, Harrington (Reference Harrington2010) and Wojtinnek and Pulman (Reference Wojtinnek and Pulman2011) proposed to parse a corpus to build connected graphs of words based on their syntactic relations, and exploit the link structure using graph-based algorithms to measure semantic relatedness between words. Pozo, Pazos and Valencia (Reference Pozo, Pazos and Valencia2008) built a hierarchy of words by applying hierarchical clustering algorithms using the corpus, and applied methods that are based on hierarchical structures. Details of these will be discussed in Section 4.

4.1 Path-based methods

The fundamental rationale behind path-based methods is that the relatedness between concepts can be determined based on their distance, or the length of the paths connecting them in a semantic graph following a given type of edges, or relation. The length of a path is typically calculated by counting the number of edges or nodes along the path. For this reason, they are also referred to as edge-based methods (Pesquita et al. Reference Pesquita, Faria, Falcão, Lord and Couto2009). The majority of these methods exploit taxonomic links in a semantic network; therefore, they measure similarity rather than relatedness.

The earliest work of this type is Rada et al. (Reference Rada, Mili, Bicknell and Blettner1989), which measures semantic relatedness between two concepts using the shortest path length in a semantic graph. This method may be used to measure semantic similarity if edges of the path correspond to classical, taxonomic relations; or measure relatedness if nonclassical relations are accounted. When applied to taxonomic structures, the shortest path is effectively the one that connects the concepts by their lcs.

Despite the simplicity of this method, it has proved successful in their initial application to the MeSH concept hierarchy and in a number of follow-up studies using other knowledge bases such as Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003), Gentleman (Reference Gentleman2005), and Bhattacharya, Bhowmick and Singh (Reference Bhattacharya, Bhowmick and Singh2010). However, Lee, Kim and Lee (Reference Lee, Kim and Lee1993) stated that the method simply based on the shortest path length can be unreliable, particularly when the paths are not restricted to the hypernymy relation.

Hirst and St-Onge (Reference Hirst, St-Onge and FellBaum1998) suggested limiting the length of a valid path and discriminating the change of directions (upward such as hypernymy, downward such as hyponymy, and horizontal such as antonymy) along the path. The hypothesis is that the strength of relatedness correlates negatively with path length and frequency of changes of direction along the path. Yang and Powers (Reference Yang and Powers2005) proposed to calculate similarity as the product of edge weights rather than their sum. They also suggested that a valid path can contain different types (taxonomic relations) of edges, where most other path-based methods define a path as a consecutive set of edges of a particular type. The rationale is that different types of edges contribute differently to semantic similarity, where the weights are defined arbitrarily in their study.

Notions of specificity, depth, and density

A widely recognized limitation of these methods is that they do not account for the specificity of nodes in a taxonomy. Typically, edges at all levels in the taxonomy are assumed to represent uniform length, and that nodes are distributed uniformly across the hierarchy. These assumptions are rarely true in practice, particularly for biomedical ontologies (Pesquita et al. Reference Pesquita, Faria, Falcão, Lord and Couto2009). This can be illustrated using Figure 1, where concepts at higher levels of a hierarchy tend to represent more general and abstract meanings whereas those lower down tend to represent more specific meanings. Thus, the same path length at different levels (e.g., the shortest path between seafood and fruit, and that between spinach and chard) denote different distances.

To overcome these issues, many have incorporated the notion of depth or density, or both to account for specificity. The motivation is that two nodes are semantically closer if they reside deeper in the hierarchy or are more densely connected locally. Thus, the measure of specificity should reflect the monotonic nature. Given a node c in a taxonomy T, the depth of c denoted by depth(c) is usually the number of nodes along the longest path between c and root, and the depth of the taxonomy is the depth of the deepest node, or in mathematical terms, depth(T) = max_c∈T depth(c). In Figure 1, depth(spinach) = 4, depth(T) = 5. The density of a node, denoted by den(c), is usually defined as the number of its child nodes, or the number of its sibling nodes. In Figure 1, the density of root vegetable is 1 following the first definition, or 2 following the second definition.

These classic definitions of depth and density have been widely adopted. A recent study by Wang and Hirst (Reference Wang and Hirst2011) has shown their limitations and proposed new measures for both. Using the WordNet ontology and several gold standard datasets, they carried out experiments to uncover the correlation between the depth or density of lcs of two words and their semantic similarity. In both cases, the correlation was found to be non-definitive. In terms of depth, the classic definition assumes a linear function that returns the depth of a node as an ordinal integer. However, experiments have shown that the ‘notion of depth is relative to the distribution of number of nodes over depth value’, and the distribution of nodes over depth conforms to a normal distribution. Also, there is ‘no definitive, sufficient, and necessary relation between depth and similarity’. In particular, examples are given to show that semantically similar words (and their underlying concepts) are not necessarily deeper in the hierarchy. More experiments were carried out to show that the correlation between density (as by number of sibling nodes) and similarity is found to be even weaker. The distribution of density values is found to generally follow the Zipf's law, with more than 90% of nodes in WordNet having density values not greater than 3. This means that for the majority of concepts in WordNet, there are “only three integer values to distinguish the varying degrees of similarity.”

Wang and Hirst (Reference Wang and Hirst2011) therefore proposed new measures of depth and density that reflect their true distributional nature. These are denoted as depth__WH and den_WH, respectively, and are calculated as below:

(1) \begin{eqnarray} \label{f_1} depth_{WH}(C) = \frac{\displaystyle \sum_{c' \in T} |{c': depth(c')\leq depth (c)}|}{|T|} \end{eqnarray}

(2) \begin{eqnarray} \label{f_2} den_{WH}(c) = \begin{cases} 0 & c = root\\ \frac{\displaystyle \sum_{c' \in ancestor(c)} den_{WH}(c')}{|ancestor(c)|}+den(c) & otherwise \end{cases} \end{eqnarray}

Due to the recency of this work, existing path-based methods still exploit the classic definition of depth and density. In the following, when we describe the depth or density of a concept, we always refer to their classic definitions, unless otherwise stated.

Addressing specificity in pathbased methods

Several studies (Ye et al. Reference Ye, Peyser, Pan, Boeke, Spencer and Bader2005; Yu et al. Reference Yu, Gao, Tu and Guo2005; Lei and Dai Reference Lei and Dai2006) have proposed methods that only exploit depth of concepts or their lcs. For example, Yu et al. (Reference Yu, Gao, Tu and Guo2005) defined similarity between two concepts as the ratio between their depths. Lei and Dai (Reference Lei and Dai2006) simply determined the similarity between two concepts as the depth of their lcs. Similar to purely path-based methods, these may also lead to spurious predictions, since they would tend to suggest concepts at the same level of a taxonomy (i.e., same depth) are similar, which is not necessarily true (e.g., following Lei and Dai (Reference Lei and Dai2006), pair-wise similarity between spinach, chard, and cooking apple tends to be similar using the taxonomy in Figure 1).

The majority of path-based methods combine path length with depth or density, or both in certain ways. Four widely cited methods in this direction are Sussna (Reference Sussna1993), Wu and Palmer (Reference Wu and Palmer1994), Jiang and Conrath (Reference Jiang and Conrath1997), and Leacock and Chodorow (Reference Leacock, Chodorow and FellBaum1998), which have been thoroughly compared and discussed previously in Budanitsky and Hirst (Reference Budanitsky and Hirst2006). Leacock and Chodorow (Reference Leacock, Chodorow and FellBaum1998) normalized the shortest path length between two nodes by the depth of the taxonomy; Wu and Palmer (Reference Wu and Palmer1994) defined similarity between two nodes based on the depth of their lcs normalized with respect to the shortest path connecting them; Sussna (Reference Sussna1993) and Jiang and Conrath (Reference Jiang and Conrath1997) combined both factors. In Sussna (Reference Sussna1993), each edge connecting two nodes is assigned a weight, the calculation of which treats the edge as a combination of two unidirectional links, one leaving from a node to another and second as the inverse of this. The weight of each directed link is dependent on two factors: (1) the arbitrary weight for the relation it represents, and (2) the number of links of the same type leaving the same node (i.e., a measure of density). Then the path connecting two nodes is weighted following this method, and normalized by the depth of the two nodes. The method by Jiang and Conrath (Reference Jiang and Conrath1997) is usually classified as IC-based although the rationale is partly related to the path between concepts; this will be further discussed in Section 4.2.

In addition, Pekar and Staab (Reference Pekar and Staab2002) and Liu, Zhou and Zheng (Reference Liu, Zhou and Zheng2007) also proposed methods that are highly similar to that of Wu and Palmer (Reference Wu and Palmer1994), based on similar rationales. According to Liu et al. (Reference Liu, Zhou and Zheng2007), the principle behind Wu and Palmer's (Reference Wu and Palmer1994) method can be considered as computing semantic similarity based on the ratio of two concepts' common and different features, which can be quantified by the depth of their lcs and the shortest path length, respectively. Another study by Li et al. (Reference Li, Bandar and McLean2003) concluded with a measure that linearly combines path length with the depth of lcs, each assigned with a scaling factor to control the contribution of each.

Al-Mubaid and Nguyen (Reference Al-Mubaid and Nguyen2006) introduced the notion of common specificity, which normalizes path length with respect to the depth of lcs. The common specificity of two concepts is determined by the depth of their lcs, and that of the cluster – essentially the branch, a sub-hierarchy – in the taxonomy that contains both concepts:

(3) \begin{equation} \label{f_3} CSpec(c_1,c_2) = D - depth (lcs(c_1, c_2)) \end{equation}\end{linenomath}

(4) \begin{linenomath}\begin{equation} \label{f_4} SemSim(c_1,c_2) = log({(\delta(c_1, c_2)-1)^\alpha} \dot {CSpec(c_1, c_2)^\beta} +k) \end{equation}\end{linenomath}

Wu et al. (Reference Wu, Zhu, Guo, Zhang and Lin2006) proposed a measure called relative specificity similarity that takes into account three different factors: the specificity of the lcs of two concepts in the taxonomy (α), the generality of each concept (β), and the local distance between the two concepts relative to their lcs (γ). The specificity of the lcs of two concepts is initially introduced in Wu et al. (Reference Wu, Su, Mao, Olman and Xu2005) and is calculated as follows:

(5) \begin{linenomath}\begin{equation} \label{f_5} \alpha = max_{\substack{ p(c_1,root)\in P(c_1,root)\\ p(c_2,root)\in P(c_2,root)}} \Big{|concept(p(c_1, root)) \bigcap concept (p(c_2, root))|\Big} -1 \end{equation}\end{linenomath}

(6) \begin{linenomath}\begin{equation} \label{f_6} \beta = max {min_{u \in leaf(c_1)} {\delta(c_1,u)}, min_{v \in leaf(c_2)} {\delta(c_2,v)}} \end{equation}\end{linenomath}

(7) \begin{linenomath}\begin{equation} \label{f_7} \gamma = \delta (lcs(c_1),c_1) +\delta (lcs(c_2),c_2) \end{equation}\end{linenomath}

(8) \begin{linenomath}\begin{equation} \label{f_8} SemSim(c_1,c_2) = \frac{depth(T)}{depth(T)+\gamma} \cdot \frac{\alpha}{\alpha+\beta} \end{equation}\end{linenomath}

Tsatsaronis, Varlamis and Vazirgiannis (Reference Tsatsaronis, Varlamis and Vazirgiannis2010) proposed a method that takes into account the weighted path length as well as the depth of all nodes along the path, which they call path depth. A major difference from other path-based methods is that a path can be a combination of different types of edges, including both taxonomic and non-taxonomic relations, while different types of relations are given different weights. The path length, which is captured under the notion of compactness, is computed as the product of weighted edges connecting the nodes along the path:

(9) \begin{linenomath}\begin{equation} \label{f_9} compactness(p(c_1,c_2)) = \sideset{}{_i^l}\prod w(e_i) \end{equation}\end{linenomath}

(10) \begin{linenomath}\begin{equation} \label{f_10} spe(p(c_1,c_2)) = \sideset{}{_i^l}\prod{\frac {2 \cdot depth (c'_i) \cdot depth (c'_{i+1})}{depth (c'_i) \cdot depth (c'_{i+1})} \cdot \frac{1}{depth(T)}} \end{equation}\end{linenomath}

While these path-based methods assume symmetric semantic relatedness, Schickel-Zuber and Faltings (Reference Schickel-Zuber and Faltings2007) introduced a metric that allows measuring asymmetric similarity between concepts. The approach, called the ontology structure-based similarity (OSS), firstly computes an a-priori score (APS) of every concept in a taxonomy to reflect its topological property; then views the similarity between two concepts as an effect of transferring the score from one concept to another via a directed path connecting the two concepts by their lcs. The APS of a concept is calculated using formula (11), which has an inverse relationship with the number of descendants of a concept and therefore can be considered as a measure of density:

(11) \begin{linenomath}\begin{equation} \label{f_11} APS(c) = \frac{1}{descendant(c)+2} \end{equation}\end{linenomath}

(12) \begin{linenomath}\begin{equation} \label{f_12} lcs_{SF07}(c_1,c_2) = max_{c \in lcs(c_1,c_2)} {(|P(c_1,c)| + |P(c_2,c)|) \cdot 2^{depth(c)}} \end{equation}\end{linenomath}

(13) \begin{eqnarray} \label{f_13} & \alpha (c_1, lcs_{SF07}(c_1,c_2)) = APS (lcs_{SF07}(c_1,c_2))/APS(c_1) \\ \end{equation}\end{linenomath}

(14) \begin{linenomath}\begin{equation} \label{f_14} & \beta (c_2, lcs_{SF07}(c_1,c_2)) = APS(c_2) - APS (lcs_{SF07}(c_1,c_2)) \end{eqnarray}

(15) \begin{linenomath}\begin{align} \label{f_15} SemDist(c_1,c_2) = \frac {log (1 + 2 \beta (c_2, lcs_{SF07}(c_1,c_2))) - log (\alpha (c_1, lcs_{SF07}(c_1,c_2)))} {max D} \end{align}\end{linenomath}

Figure 2 summarizes path-based methods and the background information resources used in the original studies.

4.2 Information content-based methods

Information content-based methods hypothesize that the relatedness between concepts can be measured by the amount of information they share, which, if in a taxonomy, is often determined with respect to their lcs. These methods usually combine knowledge of a concept's hierarchical structure with statistics of its actual usage in text usually derived from a large corpus. The first IC-based method is introduced by Resnik (Reference Resnik1995), which measures the IC of a concept as follows:

(16) \begin{linenomath}\begin{equation} \label{f_16} IC(c) = -log\, p(c) \end{equation}\end{linenomath}

Resnik's (Reference Resnik1995) definition of IC is widely adopted by later methods. Lord et al. (Reference Lord, Stevens, Brass and Goble2003a) applied Resnik's method to the biomedical domain. Most of the later IC-based methods improved Resnik's in different ways to overcome a number of limitations. The first limitation is that any two pairs of concepts having the same lcs will receive the same similarity, which is not necessarily appropriate. Budanitsky and Hirst (Reference Budanitsky and Hirst2006) refers to this issue as ‘indistinguishability’. Using the taxonomy in Figure 1, Resnik's method will output the same similarity for the pair seafood–fruit and bramley–kelp, which have the same lcs, food.

To address this problem, many methods incorporate the IC of each concept in question as a way to balance that of their lcs. Two widely cited studies in this direction are Jiang and Conrath (Reference Jiang and Conrath1997) and Lin (Reference Lin1998b). They have been summarized and compared in Budanitsky and Hirst (Reference Budanitsky and Hirst2006) and Zesch and Gurevych (Reference Zesch and Gurevych2010a). Briefly, Jiang and Conrath (Reference Jiang and Conrath1997) proposed a measure based on the rationale of the shortest path but formulates the distance as a function of the IC measure. Lin's (Reference Lin1998b) semantic similarity measure aims to address the commonality of two concepts as well as their difference, both measured in terms of IC. In its initial form the measure applies to taxonomic structures only. Maguitman et al. (Reference Maguitman, Menczer, Roinestad and Vespignani2005) generalized Lin's measure such that it is applicable to both hierarchical and non-hierarchical links. A number of studies have adapted these methods to the biomedical domain with small modifications. For example, Speer, Spieth and Zell (Reference Speer, Spieth and Zell2004) converted Lin's semantic similarity measure into a distance metric whereas Schlicker et al. (Reference Schlicker, Domingues, Rahnenführer and Lengauer2006) combined Resnik's and Lin's methods to calculate similarity.

The second limitation with Resnik's definition of IC is related to the calculation of p(c), which is dependent on the choice of a corpus. As a result of this, given different corpora, it is possible to obtain a different IC of a concept. Seco, Veale and Hayes (Reference Seco, Veale and Hayes2004) argued that the IC of a concept should be related to its hierarchical structure, and introduced an alternative IC measure called ‘intrinsic IC’, calculated solely based on a taxonomy:

(17) \begin{linenomath}\begin{equation} \label{f_17} IC_{int}(c) = 1 - \frac{log(| descendent(c) | +1)}{log(|T|)} \end{equation}\end{linenomath}

(18) \begin{eqnarray} \begin{array}{rcl}\label{f_18} SemSim (c_1,c_2) &=& IC_{int} (lsc(c_1,c_2)) - (IC_{int}(c_1) - IC_{int} (lsc(c_1,c_2))) \\ && -\, (IC_{int}(c_2) - IC_{int} (lsc(c_1,c_2))) \\ &=& 3 \cdot IC_{int} (lsc(c_1,c_2)) - IC_{int} (c_1) - IC_{int} (c_2) \end{array} \end{eqnarray}

While these methods generally define semantic similarity of two concepts with respect to their lcs, which is usually a single concept, some methods have proposed to consider multiple common subsumers of the concepts. Couto, Silva and Coutinho (Reference Couto, Silva and Coutinho2005) proposed the GraSM measure, which takes the average of IC of all common disjunctive subsumer (cs _disjunct) of two concepts:

(19) \begin{linenomath}\begin{equation} \label{f_19} SemSim(c_1,c_2) = \frac{\displaystyle \sum_{c \in cs_{disjunct(c_1,c_2)}} IC (c)}{| {{c | c \in cs_{disjunct(c_1,c_2)}}} |} \end{equation}\end{linenomath}

Two common subsumers are said to be disjunctive if there are ‘independent paths from both ancestors to the concept’, where an independent path is one that contains at least one concept unused by other paths. The motivation is that each common disjunctive subsumer provides a different interpretation of concepts that can be equally important. For example, with an lcs-based method, the similarity between leaf vegetable and sea vegetable in the taxonomy of Figure 1 depends on their lcs, vegetable. GraSM also takes into account the following independent paths to food: leaf vegetable–vegetable–food and sea vegetable–seafood–food, and thus also considers the IC of food. On the other hand, there are no independent paths from root vegetable and leaf vegetable to food, and therefore their similarity is only dependent on their lcs, vegetable. Thus, following the formula, GraSM will return a higher similarity for root vegetable and leaf vegetable than leaf vegetable and sea vegetable. The intuition is that sea vegetable has another interpretation (seafood).

Wang et al. (Reference Wang, Du, Payattakool, Yu and Chen2007) also argued that firstly all ancestors of a concept should contribute to the semantics of the concept, and therefore should be accounted for when measuring semantic similarities between concepts; secondly, the significance of the contribution should follow an inverse relationship with their distance to the concept. Given a hierarchical structure containing a concept c, their method firstly extracts a sub-hierarchy to represent the semantics of c. Formally, T_c(c, C_c, E_c) is the extracted sub-hierarchy for the concept c, where C_c denotes all concepts in the sub-hierarchy, including ancestor(c) and c itself, and E_c denotes the set of edges that connect any two concepts in the sub-hierarchy. Thus, each member concept in C_c contributes to the semantics of c, via a path that connects the two concepts by edges in E_c. This contribution is quantified by

(20) \begin{linenomath}\begin{equation} \label{f_20} semantics_c(c') = \begin{cases} 1 & c = c'\\ max_{ch \in children(c'), e \in E_c} {weight(e) \cdot semantics_c(ch)} & c \neq c' \end{cases} \end{equation}\end{linenomath}

(21) \begin{linenomath}\begin{equation} \label{f_21} sv(c) = \displaystyle \sum_{c' \in C_c} semantics_c (c') \end{equation}\end{linenomath}

(22) \begin{linenomath}\begin{equation} \label{f_22} SemSim(c_1,c_2) = \frac{\displaystyle \sum_{c \in C_{c_1} \bigcap C_{c_2}} (semantics_{c_1} (c) + semantics_{c_2} (c))} {sv(c_1) + sv(c_2)} \end{equation}\end{linenomath}

A summary of IC-based methods is shown in Figure 3.

4.3 Gloss-based methods

As introduced previously in Section 3.1, concepts represented in knowledge bases are often provided with definitions and examples. Gloss-based methods generally refer to these as glosses, and hypothesize that the relationship between concepts is often implied by the shared words in their glosses. Therefore, gloss-based methods propose to measure semantic relatedness with respect to the overlap of words in two concepts' glosses. Following this definition, gloss-based methods assess relatedness rather than similarity, since they do not make use of taxonomic links. However, there are also exceptions.

Lesk (Reference Lesk1986) introduced the first gloss-based measure, which simply evaluates the relatedness between concepts by the number of overlapping words in their glosses, namely,

(23) \begin{linenomath}\begin{equation} \label{f_23} SemRel(c_1, c_2) = \left | gloss(c_1) \bigcap gloss(c_2) \right| \end{equation}\end{linenomath}

Further to the motivation behind Gurevych (Reference Gurevych2005), if we lessen the definition of gloss to allow different methods of gloss construction, a few other methods can also be classified as gloss-based. Gentleman (Reference Gentleman2005) proposed to measure the overlap of ancestors of two concepts extracted from a taxonomic structure, where ancestor(c) can be considered as a gloss representation of c,

(24) \begin{linenomath}\begin{equation} \label{f_24} SemSim(c_1,c_2) = \frac{\left | ancestor(c_1) \bigcap ancestor(c_2) \right |} {\left | ancestor(c_1) \bigcup ancestor(c_2) \right |} \end{equation}\end{linenomath}

While the method by Gentleman (Reference Gentleman2005) can be considered as quantifying similarity with respect to the shared knowledge of two concepts, Batet, Sánchez and Valls (Reference Batet, Sánchez and Valls2011) proposed a method that quantifies similarity with respect to ‘non-shared knowledge’. The method represents each concept as a gloss of their ancestors in the same way, and takes into account the ‘non-shared’ and ‘shared knowledge’ between two concepts, which is calculated based on the overlap of their gloss. Let G(c) be the set containing ancestor(c) and c, then the similarity is defined as

(25) \begin{linenomath}\begin{equation} \label{f_25} SemSim(c_1,c_2) =-\log_2{\frac{| G(c_1) \bigcup G(c_2) | - | G(c_1) \bigcap G(c_2) |} {| G(c_1) \bigcup G(c_2) |}} \end{equation}\end{linenomath}

A summary of gloss-based methods is shown in Figure 4.

4.4 Vector-based methods

This section discusses vector-based methods, which according to a narrow definition by Zesch and Guryvech (Reference Zesch and Gurevych2010a), refer to methods that represent a term or concept using a feature vector derived from a structured knowledge base, rather than using co-occurrence counts or contexts. Feature vectors are widely used for data representation. For vector-based methods, concepts and their lexicalized forms can be represented based on features encoded in knowledge bases. For example, in the taxonomy shown in Figure 1, concepts can be described by the features parent concepts and child concepts. Figure 5 illustrates the vector representations of vegetable and seafood based on these two types of features.

Fig. 5.

Feature representations of concepts based on the taxonomy in Figure 1. 0 – a feature is inactive for the concept; 1 – a feature is active for the concept.

With feature vector representations, assessing relatedness between concepts can be achieved by comparing the similarity between their feature vectors. The most well-known and widely used measure for this purpose is the cosine similarity function, which measures the similarity between two vectors by the cosine of the angle between them:

(26) \begin{linenomath}\begin{equation} \label{f_26} cosine(\vec{v_1}, \vec{v_2}) = \frac {\vec{v_1}, \cdot\vec{v_2}} {|| \vec{v_1} || \cdot ||\vec{v_2} ||} \end{equation}\end{linenomath}

Generally, we classify vector-based methods into two types. The first type of methods build a concept vector using the lexical semantic content (e.g., a concept's gloss and synonyms in WordNet) directly defined for that concept in a knowledge base. Intuitively the lexical semantic content can be considered as features relevant to a concept. The second type of methods builds a concept vector using other related concepts in the knowledge base. The intuition is that semantically related concepts are related to a similar set of concepts. In these methods, features for each relevant concept are exploited indirectly and usually contribute to the weight of the relevant concept in the corresponding vector of the target concept. The classification is illustrated in Figure 8 at the end of this section.

Patwardhan and Pedersen (Reference Patwardhan and Pedersen2006) represented a concept by a second-order gloss vector using WordNet glosses. Firstly, WordNet is turned into a corpus made of the set of glosses in WordNet. Next, a first-order context vector based on co-occurrence is created for every word in this corpus, where words are said to co-occur if they are found in the same gloss. Then for each concept, a second-order gloss vector is constructed by combining the first-order context vectors of words that appear in its gloss. For example, the second-order gloss vector for the concept cat (mammal) is built using the resultant first-order vectors of nonstop words (shown here in italic) in its WordNet gloss ‘feline mammal usually having thick soft fur and no ability to roar’. The intuition is that the orientation of the second-order gloss vector indicates the domains or topics it is associated with. The relatedness between two concepts is then measured as the cosine similarity between two vectors.

Zesch et al. (Reference Zesch, Müller and Gurevych2008b) suggested that different kinds of lexical semantic content defined for a concept can be used as features to build concept vectors. They demonstrated this using three different knowledge bases with the generic cosine similarity function. Concept vectors are built using the first paragraph of Wikipedia, WordNet gloss, and Wiktionary gloss separately. Zhang et al. (Reference Zhang, Gentile and Ciravegna2011) proposed to combine various kinds of lexical semantic content from different knowledge bases to create joint vector representations. The hypothesis is that (1) a concept may be covered in different knowledge bases, and (2) each knowledge base provides different kinds of lexical semantic content (e.g., the glosses, synonyms, and hypernyms in WordNet; the article content, redirects, and categories in Wikipedia) that present complementary perspectives to each other. To exploit this, the authors proposed to build a combined vector representation of concepts in three steps. Firstly, given a polysemous term and its corresponding concept articles found in Wikipedia and all its synsets in WordNet, a Wikipedia concept article is mapped with a WordNet synset that is likely to refer to the same meaning. This is done by using a simple gloss overlap-based method. Secondly, different kinds of lexical semantic content in each knowledge base are cross-mapped following the sense of similar semantics. For example, frequent words used in a Wikipedia article are joined with WordNet gloss; Wikipedia redirects are joined with WordNet synonyms; and the categories assigned to the article are joined with WordNet hypernyms. Finally, a joint feature vector representation is created based on the cross-mapped content from both knowledge bases. Szarvas, Zesch and Gurevych (Reference Szarvas, Zesch and Gurevych2011) also proposed to harness diverse knowledge bases, including Wikipedia, WordNet, and Wiktionary. The method firstly represents a concept using features extracted from each knowledge base separately and then computes three different scores. The scores are then used to train a model in a supervised setting.

One of the methods that represent a word or concept as a vector of related concepts is introduced in Ziegler, Simon and Lausen (Reference Ziegler, Simon and Lausen2006). They firstly queried each word on Google Directory,Footnote ⁷ which returns a ranked list of websites each annotated with a category defined in the Open Directory Project (ODP) taxonomy. The ODP taxonomy organizes category concepts in a tree structure, and classifies websites using the categories. The word is then represented as a vector of ODP categories, such that || = |T| the size of the ODP taxonomy. The initial weight of each category cat in the vector is dependent on the rank of the website that the corresponding category is associated with. Next, for each cat, its weight is propagated upwards to the ancestors of cat along the ODP taxonomic links, where the amount of propagation depends on the density of the parent node at each step. This process ensures that each ancestor of a cat receives a weight that is monotonically decreasing with respect to their depth. Then the final weight of cat is adjusted to combine the weights of all of its ancestors, resulting in the final weighted vector representation of the word. The intuition behind this is that a category could be counted as an instance of its ancestors, and therefore its weight should reflect the contribution from all its ancestors. The final semantic relatedness between two words is computed as the correlation between two vectors using the Pearson's correlation coefficient:

(27) \begin{eqnarray}\begin{array}{rcl} \label{f_27} SemRel(w_1, w_2) &=& SemRel(\vec{v}_{w_1}, \vec{v}_{w_2}) \\ &=& \displaystyle \frac {\displaystyle \sum_{k=0}^{|T|} (v_{w_1, k}-\overline{v}_{w_1}) \cdot (v_{w_2, k}-\overline{v}_{w_2})} {\left(\displaystyle \sum_{k=0}^{|T|} (v_{w_1, k}-\overline{v}_{w_1}) ^2 \displaystyle \sum_{k=0}^{|T|} (v_{w_2, k}-\overline{v}_{w_2}) ^2 \right)^{\frac{1}{2}}} \end{array}\end{eqnarray}

A similar approach is Explicit Semantic Analysis (ESA) introduced by Gabrilovich and Markovitch (Reference Gabrilovich and Markovitch2007). ESA computes word relatedness using vectors constructed using Wikipedia concepts. The method firstly builds an inverted index of words and Wikipedia articles, then represents each word as a high-dimensional vector of Wikipedia articles (Figure 6). Since each article usually focuses on certain topic, the vector can be viewed as a vector of concepts, where each element in the vector corresponds to a concept and the dimension is the number of Wikipedia articles. Each element in the vector is weighted by the tf.idf (Jones Reference Jones1973) score of the word in the associated article. The intuition is that the weight denotes the degree of relevance between the word and the concept. Semantic relatedness is also calculated using the cosine function.

Fig. 6.

Illustration of the word representation process in ESA.

Explicit semantic analysis was later extended by Hassan and Mihalcea (Reference Hassan and Mihalcea2009) and Radinsky et al. (Reference Radinsky, Agichtein, Gabrilovich and Markovitch2011). Hassan and Mihalcea (Reference Hassan and Mihalcea2009) introduced two modifications to address corresponding issues in the original ESA method. Firstly, the weight of each element in the vector is normalized to account for the length of the associated concept article, as the original method may be biased toward articles with lengthy descriptions. Secondly, the weights for the vector elements corresponding to a concept found in the Wikipedia category tree are scaled according to their depth in the category tree. The intuition is to promote concepts that are lower down (and thus more specific) in the category tree. They also replaced the cosine similarity metric with an overlap-based metric similar to that by Lesk (Reference Lesk1986) in order to place more emphasis on the overlap of vectors.

Radinsky et al. (Reference Radinsky, Agichtein, Gabrilovich and Markovitch2011) proposed to incorporate the ‘temporal behavior’ of words in computing their relatedness. The idea originates from the observation that semantically related words do not necessarily co-occur in the same articles; however, they are likely to be mentioned roughly around the same time. For example, by studying the distributional patterns of words over time using a collection of New York Times articles spanning over 130 years, they found that the words war and peace tend to correlate in their usage frequency over time. However, they might rarely be mentioned at the same time in the same articles. To exploit this feature they proposed to modify the ESA method by modelling the ‘temporal dynamics’ of each non-zero weighted concept in the vector, and scaling their temporal dynamics according to the concept's original weight in the vector. The temporal dynamics of a concept is modelled as a series of its usage frequency over the corpora:

(28) \begin{linenomath}\begin{equation} \label{f_28} dynamics(c) = \bigg\langle \frac{{d \in D_1 | freq(c,d) |)}}{|D_1|}, \dots, \frac {{d \in D_n | freq(c,d) |)}} {|D_n|} \bigg\rangle \end{equation}\end{linenomath}

Milne and Witten (Reference Milne and Witten2008) employed the hyperlinked Wikipedia article graph and proposed to represent a Wikipedia concept as a vector of concepts linking to it or a vector of concepts it links. The vector in the first case is made of incoming links in a concept article, while in the second case it is made of outgoing links. The cosine similarity function and the measure proposed by Cilibrasi and Vitanyi (Reference Cilibrasi and Vitanyi2007) were applied to each vector representation, respectively, for evaluation. Cilibrasi and Vitanyi's (Reference Cilibrasi and Vitanyi2007) method will be described in Section 4.5, since initially it was developed as a distributional similarity measure. Liu and Chen (Reference Liu and Chen2010) also represented Wikipedia concept as a vector of links, but defined the relatedness between two concept vectors as the sum of the pairwise relatedness between any two links across two vectors, which is then computed using either gloss overlap, or the Wu and Palmer's (Reference Wu and Palmer1994) measure using the category graph.

The method by Milne and Witten (Reference Milne and Witten2008) only considers the adjacent concepts (e.g., neighbors) in a semantic graph. Another stream of work based on the link structure of a semantic network exploit both direct and indirect connections between concepts. Gouws, van Rooyen and Engelbrecht (Reference Gouws, van Rooyen and Engelbrecht2010) proposed to apply the spreading activation algorithm (Collins and Loftus Reference Collins and Loftus1975) to a semantic network of concepts as a method to derive concept vectors.

Briefly, given a semantic network of nodes connected by directed and weighted edges, such as shown in Figure 7, spreading activation allows propagating the activation value from a given node (or a set of nodes) to any other nodes in the network across the path that connects them. For each pair of adjacent nodes connected by a directed edge along the path, the propagation is controlled by two factors: a firing threshold that checks whether the activation value of the current node should be passed on – thus firing the propagation – to its adjacent nodes; a decay factor decides the amount of value passed on and accumulated if the propagation is fired. The intuition is that as the propagation travels a long distance, the value propagated drops. For the purpose of measuring semantic relatedness between two concepts c ₁ and c ₂, Gouws et al. (Reference Gouws, van Rooyen and Engelbrecht2010) built a semantic network of Wikipedia concepts connected by incoming links from the article page. They firstly set a non-zero initial activation value to the node of concept c ₁, while all other nodes receive an initial value of 0. Spreading activation is started to propagate the value to c ₂ through each node along the set of paths connecting them. After the activation terminates (determined by a number of methods), c ₂ receives the final activation value, denoted by act(c ₂|c ₁). Meanwhile, a concept vector ₁ is created for c ₁ by collecting the final activation values of all nodes in the network. These values can be considered as a measure of the relevance between each node and c ₁. Next, the same process is repeated from the opposite direction, by propagating an initial activation value from c ₂ to c ₁, to obtain act(c ₁|c ₂) and ₂. Finally, the authors computed the semantic relatedness between the two concepts in three different ways: (1) as a function of the sum of act(c ₂|c ₁) and act(c ₁|c ₂), in which each value is considered to be a distance from one to another; (2) as the cosine similarity of two vectors; and (3) using a distance-based formula introduced in Cilibrasi and Vitanyi (Reference Cilibrasi and Vitanyi2007).

Fig. 7.

A spreading activation network with a decay factor of 0.9 and firing threshold of 0.3. The initial activation value of 1.0 is propagated from node 1 through the edges.

Harrington (Reference Harrington2010) and Wojtinnek and Pulman (Reference Wojtinnek and Pulman2011) applied the same technique but derived a semantic and syntactic structure from an unstructured corpus by applying NLP techniques such as Named Entity Recognition and syntactic parsing to a corpus to generate a syntactic and semantic network of entities and concepts. The authors argued that the advantage of using a corpus is that they may provide better coverage of domain-specific information than a general-purpose knowledge base.

Another popular stream of methods that exploit the link structure of a semantic network for constructing concept vectors is using Personalized PageRank (Haveliwala Reference Haveliwala2002), an extension of the well-known PageRank technique. PageRank was initially an algorithm for calculating the importance of webpages by exploiting the hyperlinks between them. It computes a stationary probability distribution that represents the chance that a person randomly clicking on links will arrive at any particular page given the entire collection, regardless of which webpage to start from. Haveliwala (Reference Haveliwala2002) extended this technique to allow the ranking (or importance) of each page to be biased (or ‘personalized’) toward a particular query, such that webpages more relevant to the query receive higher importance and therefore higher ranks. Such ideas have been adapted to a semantic network of concepts to develop semantic relatedness methods (Hughes and Ramage Reference Hughes and Ramage2007; Yeh et al. Reference Yeh, Ramage, Manning, Agirre and Soroa2009; Yazdani and Popescu-Belis Reference Yazdani and Popescu-Belis2010). Generally, the PageRank algorithm is applied to the semantic network of concepts to obtain the stationary probability distribution to represent the likelihood of reaching any node in the network. The final probability distribution depends on the connectivity of the network and weights of edges, but is independent on the starting node. Next, this distribution is personalized against each question concept node following Haveliwala's method, which effectively places more weights onto nodes closer to the target concept in the graph. Intuitively, this can be viewed as re-ranking all nodes (similar to webpages) in the network (similar to the web) with respect to their connection (similar to relevance) with the target concept node (similar to a query). The two resultant distributions, biased toward c ₁ and c ₂ respectively can be represented as two vectors, the dimensionality of which is the number of nodes in the network. Then the relatedness between them can be computed with a measure of vector similarity.

A major difference between these methods is how the semantic network is constructed. Hughes and Ramage (Reference Hughes and Ramage2007) constructed a graph of WordNet synsets, tokens (e.g., polysemous words), and token-with-part-of-speech (tokenPOS, e.g., click#noun, click#verb). Edges are established for any relations between synsets defined in WordNet, for a synset node, and a tokenPOS node if the synset ‘uses’ the tokenPOS (e.g., synset ‘click#noun#mouse click’ uses ‘click#noun’), and for a tokenPOS node with a token node following the same strategy. Yeh et al. (Reference Yeh, Ramage, Manning, Agirre and Soroa2009) and Yazdani and Popescu-Belis (Reference Yazdani and Popescu-Belis2010) constructed a graph of Wikipedia concepts. An edge is established between two concepts if they are connected by links in their article page by sharing a category, or sharing a link in their infoboxes. Yazdani and Popescu-Belis (Reference Yazdani and Popescu-Belis2010) assigned higher weights to certain types of edges to gain better performance.

A summary of vector-based methods is shown in Figure 8.

Fig. 8.

A summary of vector-based methods and the initial background information resources used. WN: WordNet, WK: Wikipedia, OTH: other knowledge bases, C: a general-purpose corpus.

4.5 Distributional similarity as a proxy for lexical semantic relatedness

A loose definition of distributional similarity based on the famous statement by Firth (Reference Firth1957), ‘You shall know a word by the company it keeps’, says that two words are similar if they appear in similar contexts. Weeds (Reference Weeds2003) summarized the literature and defined that two words are distributionally similar if (1) they tend to occur in each other's context; or (2) the contexts each word tends to occur in are similar; or (3) if one word is substituted for another in a context, its ‘plausibility’ is unchanged. Different methods have adopted different definitions of contexts, but usually a context is the set of words collected from the window around the word, or an entire document, or syntactic relationship as introduced in Lin (Reference Lin1998a) and Weeds (Reference Weeds2003). Following this definition, a multitude of methods are available for measuring distributional similarity. These are not the focus of this survey; however, details can be found in Weeds (Reference Weeds2003) and Turney and Pantel (Reference Turney and Pantel2010).

There is a widely accepted hypothesis that distributional similarity can predict semantic similarity and thus relatedness in general. As a result, many studies have proposed to use distributional similarity methods as a proxy for lexical semantic relatedness. However, Budanitsky and Hirst (Reference Budanitsky and Hirst2006) argued that there are three essential differences between the two paradigms. Firstly, semantic relatedness is inherently a relation on concepts, while distributional similarity is a relation on words; secondly, semantic relatedness is typically symmetric whereas distributional similarity can be potentially asymmetric; finally, semantic relatedness depends on a structured lexicographic or knowledge bases, distributional similarity is relative to a corpus. Nevertheless, because of the popularity of their application to semantic relatedness, in the following we discuss several recent studies that apply distributional similarity methods to such tasks. Our criteria for selection is that the method is either evaluated using methods or datasets (see Section 5) usually used for evaluating lexical semantic relatedness, or that it is later ported to address relevant tasks in other studies. A popular research direction taken by these approaches is exploiting the Web as the background information corpus.

Matsuo et al. (Reference Matsuo, Sakaki, Uchiyama and Ishizuka2006) computed distributional similarity of two words using statistics collected from search engines. The method queries each word using a search engine to retrieve the number of pages containing each word denoted by freq(w). Next, the number of pages containing both words freq(w ₁, w ₂) is counted as the page counts for a query concatenating both words. Then using these figures, the distributional similarity can be calculated using the Point-wise Mutual Information (PMI) measure or the Chi-square (x ²) statistical test. PMI measures the strength of association between two words taking into account the probability of encountering each word in the corpus and the probability of encountering both together. While Chi-square also takes into account the probability of encountering one word but not another, as well as the probability of encountering none of the words, essentially, in Matsuo et al.'s (Reference Matsuo, Sakaki, Uchiyama and Ishizuka2006) method, the context is equivalent to a webpage.

Cilibrasi and Vitanyi (Reference Cilibrasi and Vitanyi2007) introduced the Normalised Google Distance (NGD) measure, which builds on a data compression-related theory that is rather intricate. The resultant method is, however, very simple and also utilizes page counts:

(29) \begin{linenomath}\begin{align} \label{f_29} SemDist(w_1, w_2) = \frac {max {log(freq(w_1)), log(freq(w_2))} - log(freq(w_1, w_2))} {logN - min {log(freq(w_1)), log(freq(w_2))}} \end{align}\end{linenomath}

While these methods based on page counts can be effective, a potential issue is that they do not consider the relative position of words or multiple occurrences of the word in a single page. Two words occurring in a page may not be related at all if they are distant. Therefore, methods based on page counts are prone to errors (Bollegala et al. Reference Bollegala, Matsuo and Ishizuka2007).

Many methods cope with this by using the returned snippets for the query. Chen et al. (Reference Chen, Lin and Wei2006) proposed to count word co-occurrences in the top N snippets returned by a search engine. They hypothesize that two words w ₁ and w ₂ are associated if it is possible to find w ₂ from w ₁ (a forward process) and find w ₁ from w ₂ (a backward process) by web search. Therefore, their method queries each word in turn, and count the occurrences of the other in the top N snippets returned for the query (i.e., freq(w ₁|w ₂) and freq(w ₂|w ₁)). This process gives two different co-occurrence figures for the two words, which they call a ‘double checking’ process. The word similarity is then computed using a Co-Occurrence Double Check (CODC) function as shown below:

(30) \begin{equation} \label{f_30} DistSim(w_1,w_2) = \displaystyle \begin{cases} 0 & \text{if} freq (w_1|w_2) = 0 \\ & \text{or} freq (w_2|w_1) = 0 \ \\ e^{log(\frac {freq (w_2|w_1)}{freq (w_1)} \cdot \frac {freq (w_1|w_2)}{freq (w_2)})^\alpha} & \text{otherwise} \end{cases} \end{equation}

Although these methods can tackle the limitation of page counting-based methods to certain extent, one of their limitations, as suggested by Ruiz-Casado, Alfonseca and Castells (Reference Ruiz-Casado, Alfonseca and Castells2005), is that they ignore word order and phrasal structures. The authors thus proposed a method that assesses the substitutability of two words as a measure of their similarity. It firstly collects a set of sentences (S ₁, S ₂) from the snippets returned for each word (w ₁, w ₂) as a query to a search engine. Next, it counts in how many of the sentences in S ₁ it is possible to substitute w ₁ with w ₂. This is done by replacing w ₁ with w ₂ to create a new sentence, which is queried using the search engine for validation. The same process is repeated for S ₂ and the final similarity score is derived based on the percentage of sentences that are substitutable.

Bollegala et al. (Reference Bollegala, Matsuo and Ishizuka2007) proposed a method that combines both page counts and sentence-level contexts in snippets. Their method is based on supervised classification trained on examples, which is uncommon in semantic relatedness and distributional similarity methods. A Support Vector Machine (SVM)-based (Vapnik Reference Vapnik1998) classifier is trained using a set of synonym pairs as positive examples and a set of non-synonym pairs as negative examples, both of which are randomly selected from WordNet. Part of the process is illustrated in Figure 9.

Fig. 9.

Illustration of the method by Bollegala et al. (Reference Bollegala, Matsuo and Ishizuka2007). Lexical patterns are extracted for synonym and non-synonym pairs (training data) based on search results from the Web. The patterns are filtered and used as features to represent the training data, using which a model is learnt. It is then used to classify new term pairs, based on the same feature representation model.

Firstly, a pattern induction process is applied to extract lexical patterns that are likely to indicate synonyms in a text. Using the positive and negative examples, each pair is queried to obtain a set of snippets containing both words. Then from each snippet, they extract n-gram lexical patterns from the context windows that include both words. However, many patterns may be found for both positive and negative examples. Thus, for each pattern they count its frequencies of being found with positive and negative examples respectively (positive and negative frequencies), and compute a confidence score using the Chi-square function. The patterns are ranked by this score and only the top 200 patterns are selected. To train the classifier, they generate a feature vector for each of the positive and negative example. A pair of words is queried using a search engine, and the frequency of each of the 200 patterns is counted in the returned snippets. Next, four different functions of association strength are applied to compute four scores for the two words using page counts in a similar way to Matsuo et al. (Reference Matsuo, Sakaki, Uchiyama and Ishizuka2006). A feature vector is then created for the pair by concatenating the frequencies collected for 200 patterns and four scores. The SVM-based classifier is then trained using this training data to create a classification model, which is then able to predict similarity between any new pairs of words given a feature representation created in the same way.

A summary of distributional similarity methods discussed above is shown in Figure 10.

Fig. 10.

A summary of distributional similarity methods. All methods used the web (WEB) as the background information resource.

4.6 Hybrid methods

We refer to hybrid methods as those that combine multiple semantic relatedness methods or distributional similarity methods to arrive at a single measure of semantic relatedness.

Many of these methods firstly calculate semantic relatedness using an assembly of different purebred methods, and then derive an aggregated score as the average, sum or maximum of all scores. This kind of simple combination is intuitive – if each distinctive method provides a different perspective of semantic relatedness, it is natural to combine them to create a full picture. For example, Alvarez and Lim (Reference Alvarez and Liam2007) calculated semantic relatedness as the maximum score given by either a method that inverts the shortest path length (weighted by depth of concepts along the path), or a method based on the depth of lcs and the taxonomy, or the gloss overlap in WordNet. Riensche et al. (Reference Riensche, Baddeley, Sanfilippo, Posse and Gopalan2007) also adopted a similar strategy. Sheng et al. (Reference Sheng, Chen, Yu and Feng2010) linearly combined the distributional similarity of two words using a PMI-based method with the sematic similarity score calculated using Wu and Palmer's (Reference Wu and Palmer1994) method. Similarly, Gracia and Mena (Reference Gracia and Mena2008) linearly combined the score calculated using the Cilibrasi and Vitanyi's (Reference Cilibrasi and Vitanyi2007) measure with one that calculated using an overlap-based method.

Other hybrid methods employ scores given by individual methods as an integral part of the hybrid model, usually as some kind of features. To distinguish them from the above combination methods, we call this type of hybrid method the integration methods. Rodrìguez and Egenhofer (Reference Rodrìguez and Egenhofer2003) combined a gloss-based method with depth as a normalization factor. Given the gloss created for two concepts, semantic relatedness is determined by the common characteristics (set overlap) and non-common characteristics (set difference), calculated using an adapted Tversky (Reference Tversky1977) set-based algorithm. Let U(c_i, c_j) = gloss(c_i) ∩ gloss(c_j) and R(c_i, c_j) = gloss(c_i)/gloss(c_j), it is calculated as follows:

(31) \begin{eqnarray} \begin{array}{rcl} \label{f_31} SemRel(c_1, c_2) = \frac {| U(c_1, c_2) |} {| U(c_1, c_2 | + \alpha (c_1,c_2) \cdot | R(c_1,c_2) | + (1- \alpha (c_1,c_2)) \cdot | R(c_2,c_1) |} \end{array}\end{eqnarray}

(32) \begin{linenomath}\begin{equation} \label{f_32} \alpha(c_1,c_2) = \begin{cases} \displaystyle \frac {depth (c_1)}{depth (c_1)+depth (c_2)} & \text{if} depth (c_1) \leq depth (c_2) \\[6pt] 1-\displaystyle \frac {depth (c_1)}{depth (c_1)+depth (c_2)} & \text{otherwise} \end{cases} \end{equation}\end{linenomath}

Othman, Deris and Illias (Reference Othman, Deris and Illias2007) defined semantic similarity of two concepts in a taxonomy as a function of their individual distance to their lcs. This distance is calculated using a measure that combines the IC, depth, and local density in order to address specificity of concepts:

(33) \begin{linenomath}\begin{equation} \label{f_33} dist(c_1,c_2) = \displaystyle \sum_{i}^{l}D({c'}_i) \cdot E({c'}_i) \cdot (IC({c'}_{i+1}) - IC({c'}_i))) \end{equation}\end{linenomath}

(34) \begin{linenomath}\begin{align} \label{f_34} SemSim(c_1,c_2) = 1 - min \bigg{1, \frac {dist(c_1, lcs(c_1, c_2)) + dist(c_2, lcs(c_1, c_2))} {max_{c \in T} {IC(c)}} \bigg} \end{align}\end{linenomath}

Pozo et al. (Reference Pozo, Pazos and Valencia2008) proposed to derive a taxonomic structure of terms from a corpus and apply path-based methods to the taxonomy. Their motivation is that even if a well-curated knowledge base is available, many structural relations may not be encoded but may be ‘hidden’ in a large corpus. Thus, they proposed to uncover hidden structural relations between terms by applying hierarchical clustering to the terms based on their distributional features observed from corpora. The approach consists of four steps: (1) representing each term extracted from a corpus by a vector of its contextual words, and compute pairwise similarity of terms using the cosine similarity function; (2) creating a connected graph of terms, where edges are established for two terms if the pairwise similarity is above a threshold; (3) apply spectral clustering to partition the graph; and (4) apply agglomerative hierarchical clustering to generate a clustering tree of terms, which is used as a taxonomy. Then the semantic distance between any terms is simply the depth of their lcs.

Han and Zhao (Reference Han and Zhao2010) proposed the Structural Semantic Relatedness (SSR) method, which makes use of three methods, including that by Lin (Reference Lin1998b), Milne and Witten (Reference Milne and Witten2008) and the NGD method by Cilibrasi and Vitanyi (Reference Cilibrasi and Vitanyi2007). Given a collection of words, the method begins with a pre-processing step that calculates semantic relatedness for each pair of words using all three methods. Because of the coverage of background information resource used in each method, a pair may receive between one and three relatedness scores. For multiple scores, the score returned by the most ‘reliable’ method is used. This is arbitrarily determined in the order of preference as Lin (Reference Lin1998b), Milne and Witten (Reference Milne, Medelyan and Witten2006), and NGD. Next, the words are plotted in a connected graph where the score is used to weigh edges between them. Let e(w ₁, w ₂) denote the weight of the edge connecting two words, neighbor(w) returns the immediate neighbors (connected by an edge) of a word, the SSR is then computed as:

(35) \begin{linenomath}\begin{align} \label{f_35} SemRel(w_1,w_2) = \alpha \cdot \displaystyle \sum_{w' \in neighbor (w_1)} \bigg(\frac{e(w_1, w')}{d_{w_1}} \cdot SemRel (w', w_2) \bigg) + \beta \cdot e(w_1, w_2) \end{align} \end{linenomath}

Another hybrid method that does not fall under either of the two categories is Agirre et al. (Reference Agirre, Alfonseca, Hall, Kravalova, Paşca and Soroa2009). They proposed to combine a WordNet-based method adapted from Hughes and Ramage (Reference Hughes and Ramage2007) with a distributional similarity method based on context similarity. The method adapted from Hughes and Ramage (Reference Hughes and Ramage2007) exploits the link structure of WordNet. However, because of the limited coverage of WordNet, a small proportion of testing data is not covered. To cope with this, for each word that is unknown to WordNet, they firstly applied the distributional similarity method to find several similar words. These are then used to substitute the unknown word and the WordNet-based approach is reapplied.

A summary of hybrid methods is shown in Figure 11.

Fig. 11.

A summary of hybrid methods and the initial background information resources used. WN: WordNet, WK: Wikipedia, BIO: biomedical knowledge bases, OTH: other structured knowledge bases, WEB: the web, C: a general-purpose corpus, C-BIO: a biomedical corpus.

4.7 Summary

In the previous sections we have discussed methods for computing lexical semantic relatedness in six different categories. The majority of these methods have assumed relatedness to be symmetric, although a number of asymmetric relatedness methods have also been proposed (Rodrìguez and Egenhofer Reference Rodrìguez and Egenhofer2003; Petrakis et al. Reference Petrakis, Varelas, Hliaoutakis and Raftopoulou2006; Schickel-Zuber and Faltings Reference Schickel-Zuber and Faltings2007). While new methods are constantly introduced, recent studies in this area can be characterized by several trends.

Categories. In terms of different categories, there is a clear preference for vector-based methods. For example, all of the vector-based methods are introduced from 2006 onwards, and they account for a large proportion (nearly 40%) of all methods introduced since then. This is consistent with the findings by Zesch and Guryvech (Reference Zesch and Gurevych2010a). Hybrid methods have also become widely used.

Background information resources. Recent studies have explored a variety of new background information resources. Collaborative knowledge resources such as Wikipedia have been studied extensively, particularly by vector-based methods (Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2007; Milne and Witten Reference Milne and Witten2008; Zesch et al. Reference Zesch, Müller and Gurevych2008b; Yeh et al. Reference Yeh, Ramage, Manning, Agirre and Soroa2009). Studies have also been carried out to adapt previous methods based on WordNet to these resources (Strube and Ponzetto Reference Strube and Ponzetto2006; Zesch and Gurevych Reference Zesch and Gurevych2010a). Distributional similarity methods have exploited the Web as an alternative background corpus to classic pre-compiled corpora (Chen et al. Reference Chen, Lin and Wei2006; Matsuo et al. Reference Matsuo, Sakaki, Uchiyama and Ishizuka2006; Cilibrasi and Vitanyi Reference Cilibrasi and Vitanyi2007). In addition, new trends such as combining different knowledge bases to complement each other (Han and Zhao Reference Han and Zhao2010; Zhang et al. Reference Zhang, Gentile and Ciravegna2011) and incorporation of temporal usage pattern of concepts (Radinsky et al. Reference Radinsky, Agichtein, Gabrilovich and Markovitch2011) have also been suggested.

Multilinguality. Methods of lexical semantic relatedness are primarily introduced for English. As discussed before, most semantic relatedness methods can be described in a generic way and adapted to different domains and languages. However, in practice, this has been rarely addressed. A few recent studies have explored this direction. Gurevych and Niederlich (Reference Gurevych and Niederlich2005) adapted the methods by Resnik (Reference Resnik1995), Jiang and Conrath (Reference Jiang and Conrath1997), and Lin (Reference Lin1998b) to a German lexical knowledge base and tested them on a German dataset. Zesch et al. (Reference Zesch, Müller and Gurevych2008b) and Zesch and Gurevych (Reference Zesch and Gurevych2010a) also tested a few state-of-the-art methods for German. Hassan and Mihalcea (Reference Hassan and Mihalcea2009) tested their method in cross-lingual semantic relatedness, i.e., determining relatedness between a term from one language (e.g., factory) and a term from another language (e.g., lavoratore in Italian, worker in English). They exploited the inter-language links in Wikipedia to map terms in one language with another. The method was tested for Spanish, Romanian, Arabic, as well as English. Liu and Chen (Reference Liu and Chen2010) adapted the method by Wu and Palmer (Reference Wu and Palmer1994) and the cosine similarity between concept vectors to compute semantic relatedness am Chinese-named entities using Wikipedia.

In Sections 5 and 6, we discuss the evaluation of semantic relatedness methods and lessons learnt.

5.1 In-vitro evaluation

In-vitro evaluation can be done by mathematical analysis and correlation with human judgement. Lin (Reference Lin1998b) proposed a method to assess semantic relatedness methods against certain properties, e.g., whether the score between two concepts increases with their commonality and decreases with their difference. However, this does not assess how well the method performs on real data. The predominant in-vitro evaluations are based on correlation with human judgement, also known as the gold standard. Typically, a dataset containing a set of pairs of concepts or words are presented to human judges, who subjectively estimate the relatedness between each pair within a certain scale. Next, the semantic relatedness method is applied to the same dataset. The results are correlated against the human judgement to derive an indication of the accuracy of the method.

5.1.1 Correlation measures

Two correlation functions are often used in the literature, the Pearson correlation coefficient and the Spearman rank-order correlation coefficient. The Pearson correlation compares the scores computed by a semantic relatedness method with the numeric scores of the gold standard. For example, the pair table-chair might get a human judgement of 8/10. With the Pearson correlation, a machine-computed score of 7/10 will be awarded higher than a score of 4/10, since the first score is closer to the gold standard. The Pearson correlation returns a value of 1 for perfect correlation and a value of 0 for no correlation. Given X the list of scores assigned to a list of term pairs by humans, and Y the scores assigned to the same list by a semantic relatedness method, it is calculated as given below:

(36) \begin{linenomath}\begin{equation} \label{f_36} \text{Pearson}(X,Y) = \frac{\displaystyle \sum (X - \overline{X}) (Y - \overline{Y})} {\sqrt{\displaystyle \sum (X - \overline{X})^2} \sqrt{\displaystyle \sum (Y - \overline{Y})^2}} \end{equation}\end{linenomath}

The Spearman rank-order correlation coefficient is based on rankings of data series. For this method, the list of term pairs are ranked by their scores given by the human judge and a measure, respectively, and correlation strength is assessed based on how well the ranking given by the measure resembles that by the human. Effectively it can be calculated by the same formula for the Pearson correlation coefficient by simply replacing the lists of scores X and Y with the lists of ranks of these scores.

Zesch and Gurevych (Reference Zesch and Gurevych2010a) discussed the limitations of each correlation measures and argued in favor of the Spearman measure. Firstly, the Pearson correlation function is very sensitive to outliers – a single outlier may produce a significantly different result. They further justified this in an experiment and showed that on the dataset by Miller and Charles (Reference Miller and Charles1991), the method by Lesk (Reference Lesk1986) was significantly penalized by a single word pair that received an extraordinarily high score representing an outlier in the dataset. Secondly, it measures the strength of the linear relationship between two data series and can produce flawed results when the relationship between human judgements and computed scores is nonlinear. Thirdly, it requires normal distribution of two random variables (scores given by a human judge and a measure) and scores to be normalized within certain interval scales. However, studies have shown that semantic relatedness scores are not always interval-scaled (Budanitsky and Hirst Reference Budanitsky and Hirst2006; Zesch and Gurevych Reference Zesch and Gurevych2007).

In contrast, the Spearman correlation is a more robust measure and does not suffer from these limitations. However, it is known from the literature that it may yield skewed results on datasets with many tied ranks.

5.1.2 Gold standards

Gold standard datasets for correlation analysis are typically created by asking multiple human annotators to rate the semantic relatedness of a pair of concepts or terms within a certain scale, and then averaging their interpretations. Since the interpretation is subjective, inter-annotator agreement (IAA) should also be studied.

General domain English datasets. Since studies on semantic relatedness are predominantly focused on English, a variety of datasets have been created for evaluation. Among these, four datasets and their variants have been widely used. These are discussed in details in Zesch and Gurevych (Reference Zesch and Gurevych2010a). Briefly, these contain the Rubenstein and Goodenough (Reference Rubenstein and Goodenough1965) dataset of sixty-five pairs of nouns (RG65), the Miller and Charles (Reference Miller and Charles1991) dataset that is a subset of the RG65 dataset and contains thirty pairs (MC30), the Finkelstein et al. (Reference Finkelstein, Gabrilovich, Matias, Rivlin, Solan, Wolfman and Ruppin2002) dataset containing 353 pairs of words (Fin353), and the Yang and Powers (Reference Yang and Powers2006) dataset containing 130 verb pairs (YP130). In addition, Gracia and Mena (Reference Gracia and Mena2008) created a dataset of thirty pairs of common nouns. No IAA figures were reported for the original RG65 and MC30 datasets. Pirrò and Seco (Reference Pirrò and Seco2008) and Resnik (Reference Resnik1995) recreated these datasets with IAA analyses. Also, the Fin353 dataset contains two subsets, each containing 153 pairs and 200 pairs, respectively, and annotated by different groups of annotators. Zesch and Gurevych (Reference Zesch and Gurevych2010a) carried out IAA analysis and discovered largely varying figures for the two subsets, and therefore suggested treating them separately (Fin153 and Fin200) in evaluation. The RG65, MC30, and YP130 are assessed based on similarity, and are therefore used originally for evaluating semantic similarity methods. For the same purpose, Agirre et al. (Reference Agirre, Alfonseca, Hall, Kravalova, Paşca and Soroa2009) created a semantic similarity dataset based on Fin353. This (AG203) contains 203 pairs of terms from Fin353 each rescored for their similarity rather than relatedness.

One widely known limitation of these datasets is that they do not contain multi-word phrases, and only the Fin153 and Fin200 datasets contain very limited number of named entities. To address this issue, Ziegler et al. (Reference Ziegler, Simon and Lausen2006) created two English datasets of concept instances and named entities. The first dataset (Zie25) contains twenty-five pairs, annotated by twenty-three people; the second (Zie30) contains thirty pairs, annotated by fifty-one people. Eighty-seven percent of annotators are German native speakers. These datasets have rarely been used. Radinsky et al. (Reference Radinsky, Agichtein, Gabrilovich and Markovitch2011) created a dataset of 280 pairs of terms (Rad280) containing both common English words and entities. It was then annotated manually by inviting participants through the Amazon Mechanic Turk service. Table 2 summarizes these datasets.

Table 2.

General domain English datasets used for evaluating lexical semantic relatedness methods based on correlation studies

General domain other languages. Compared with English, datasets for other languages are lacking. Gurevych (Reference Gurevych2005) translated the RG65 and MC30 datasets (Gur65) into German, and expanded them to a total of 350 word pairs. Zesch and Gurevych (Reference Zesch and Gurevych2006) later created a new dataset of 222 German word pairs. Both datasets contain nouns, verbs, and adjectives. Cramer and Finthammer (Reference Cramer and Finthammer2008) created a German dataset of 600 pairs of nouns. Hassan and Mihalcea (Reference Hassan and Mihalcea2009) translated the MC30 and Fin353 datasets into Spanish, Romanian, and Arabic. Liu and Chen (Reference Liu and Chen2010) created a dataset of twenty-eight pairs of named entities for Chinese. Note that translated datasets may be biased toward the original language (Cramer and Finthammer Reference Cramer and Finthammer2008), since in many cases the translation is not a one-to-one mapping.

Biomedical datasets. While the majority of general-purpose semantic relatedness methods have been evaluated using the above datasets, few of them have been evaluated in specialized domains, which is partly due to the lack of domain-specific datasets in similar forms. To our knowledge, in the biomedical domain, three datasets are available for evaluating semantic relatedness between terms, while two of them have been empirically used (Table 3). Petrakis et al. (Reference Petrakis, Varelas, Hliaoutakis and Raftopoulou2006) compiled a set of forty-nine MeSH term pairs and asked twelve experts to assess the relatedness of these pairs. Pairs with standard deviation above 0.8 were excluded, resulting in a total of thirty-six term pairs (MeSH36). Pedersen et al. (Reference Pedersen, Pakhomov, Patwardhan and Chute2007) created a set of 120 pairs of medical terms extracted from the SNOMED-CT terminology annotated by thirteen experts. However, they obtained a very low IAA of 0.51 on this dataset. To create a more reliable test bed, they selected a subset of thirty pairs and asked another two groups of experts (three and nine annotators, respectively) to re-annotate them. The final dataset (Ped30) has IAA figures of 0.68, 0.78, respectively, and a cross-group IAA of 0.85. Pakhomov et al. (Reference Pakhomov, Mcinnes, Adam, Liu, Pedersen and Melton2010) performed experiments in which eight medical residents are required to annotate a set of 724 pairs of clinical terms (Pak724). The terms are extracted from UMLS and cover three semantic categories: disorders, symptoms, and drugs. Both intra-category and inter-category pairs are created. All datasets contain multi-word terms. Annotators are required to score pairs of terms by their relatedness and similarity separately, thus creating benchmarked datasets for both semantic relatedness and similarity methods. Due to time limit, 81% of the dataset was completed for the relatedness annotation, and 78% was completed for the similarity annotation. They found the tasks to be very challenging because only moderate IAA has been achieved. For the relatedness annotation task, an IAA between 0.45 and 0.56 (inter- and intra-categories) is reported; while for the similarity annotation task, this is between 0.24 and 0.63.

Table 3.

Biomedical English datasets used for evaluating lexical semantic relatedness methods based on correlation studies

On the other hand, evaluation of semantic similarity methods in the biomedical domain is often based on a comparison against the result of a different approach such as gene sequence similarity or family similarity. Firstly, semantic similarity between gene products is calculated usually taking into account the semantic similarity between the terms used to annotate them in the corpora. The hypothesis is that gene products are similar if they share similar properties. A large number of methods are available for this task, which, however, is not the focus of this survey. Details of this may be found in the survey by Pesquita et al. (Reference Pesquita, Faria, Falcão, Lord and Couto2009). Next, the sequence similarity and family similarity between gene products are measured using a different approach such as Altschul et al. (Reference Altschul, Madden, Schäffer, Zhang, Zhang, Miller and Lipman1997). The sequence or family similarity is then used as the gold standard against which the prediction based on semantic similarity is evaluated using a correlation metric. The hypothesis is that genes that share similar sequences or families should also be semantically similar.

5.1.3 Empirical results

Due to the large number of methods and various background information resources used, a comprehensive comparative evaluation can be very difficult. Firstly, only a very small portion of these methods – typically earlier (before 2000) WordNet-based methods – have been implemented and made publicly available. Re-implementation of other methods requires not only knowledge about the algorithms but also the background information resources used. Secondly, different methods that depend on the same background information resource may have used different versions, making the direct comparison difficult. The problem can be more acute for methods based on Wikipedia, which has been growing almost exponentially since its introduction. Zesch and Gurevych (Reference Zesch and Gurevych2010b) have shown that the growth of Wikipedia can have a major impact on the coverage of a method, and smaller effect on accuracy.

Some studies (Curran and Moens Reference Curran and Moens2002; Strube and Ponzetto Reference Strube and Ponzetto2006; Bollegala et al. Reference Bollegala, Matsuo and Ishizuka2007; Zesch et al. Reference Zesch, Müller and Gurevych2008b; Zesch and Gurevych Reference Zesch and Gurevych2010a) have addressed these issues by re-implementing other methods and adapting them to a uniform background information resource. However, the majority of studies simply compare their results against others using previously published figures, ignoring the difference in terms of background information resources.

In this work we summarize previously reported evaluations based on the datasets introduced above. Some methods have been adapted to different background information resources and retested on the same datasets in later studies. In this case, we refer to the corresponding original work if it has been evaluated on the dataset; or if not, the most recent work that has included an evaluation on that dataset. For studies that evaluate different variants of a method (e.g., parameter configurations, learning algorithms), we present the highest figures obtained. We present a summary of evaluations on the general purpose datasets in Table 4, where each method is indexed by an acronym originally introduced in Figures 2–4, 8, 10, and 11. A score calculated using the Pearson measure is denoted by r, and a score calculated using the Spearman measure is denoted by ρ.

Table 4.

Evaluation in the general domain

Sources of figures (SoF) – o.w.: original work; [1] Zesch and Gurevych (Reference Zesch and Gurevych2010a); [2] Yang and Powers (Reference Yang and Powers2006); [3] Bollegala et al. (Reference Bollegala, Matsuo and Ishizuka2007); and [4] Petrakis et al. (Reference Petrakis, Varelas, Hliaoutakis and Raftopoulou2006). For each category of methods, on each dataset and with each correlation metric, the best performing method is highlighted in bold.

In addition, a small number of methods have been evaluated using biomedical datasets in Table 3. The majority of these (except Zhang et al. Reference Zhang, Gentile and Ciravegna2011) have been built on or adapted to specific biomedical background information resources. Table 5 shows the evaluation of these methods and the used corresponding background information sources.

Table 5.

Evaluation based on biomedical datasets

S. of F.: Source of figures; BG info.: background information; [1] Al-Mubaid and Nguyen (Reference Al-Mubaid and Nguyen2006), [2] Pirrò (Reference Pirrò2009).

5.2 In-vivo evaluation

In addition to in-vitro evaluation based on the gold standard datasets, a large number of studies carry out in-vivo evaluation by assessing the performance of an application built on top of lexical semantic relatedness methods. Due to various choices and diverse datasets used, a direct comparison is infeasible. Instead, we briefly introduce relevant work and frequently use datasets as general pointers for readers.

Methods of lexical semantic relatedness can be adapted to measure text similarity, i.e., similarity between long text passages such as sentences and paragraphs. It is often considered a task highly related to semantic relatedness but essentially different. At sentence level, similarity concerns semantic, part-of-speech, and syntactic information (Li et al. Reference Li, Hu, Hu, Wang and Zhou2009). At paragraph or document levels, Bär et al. (Reference Bär, Zesch and Gurevych2011) argued that similarity should be defined along three dimensions: structure, e.g., the order of sections; style, e.g., grammar, usage; and content, i.e., facts mentioned in the texts and their relations. Only the content dimension concerns the semantic level of similarity. In general, text similarity addresses a broader sense of similarity than purely semantic. The semantic level of text similarity can be addressed by adapting methods of lexical semantic relatedness, in which case we consider text similarity as an application of lexical semantic relatedness. Often, semantic relatedness between the component terms of texts are computed and then aggregated to derive a score as text similarity (Mihalcea, Corley and Strapparava Reference Mihalcea, Corley and Strapparava2006). Alternatively for long texts, it can simply be evaluated by comparing the vocabularies (Lee, Pincombe and Welsh Reference Lee, Pincombe and Welsh2005).

A number of datasets have been created for evaluating text similarity measures (in the semantic sense). Li et al. (Reference Li, McLean, Bandar, O'Shea and Crockett2006) introduced sixty-five sentence pairs based on the noun pairs created by Rubenstein and Goodenough (Reference Rubenstein and Goodenough1965). Each noun was replaced by its definition in a reference English dictionary. Mohler and Mihalcea (Reference Mohler and Mihalcea2009) created a dataset based on computer science assignments. It contains twenty-one short questions with a reference answer and also 630 student answers for all questions. The answers were graded based on the extent to which the student answers matched the reference answer. Lee et al. (Reference Lee, Pincombe and Welsh2005) created a collection of 1,225 pairs of broadcast news articles and conducted experiments to assign semantic relatedness scores to each of them based on human judgements. The dataset has been used by, for example, Gabrilovich and Markovitch (Reference Gabrilovich and Markovitch2007) for evaluating their ESA method, and Gouws et al. (Reference Gouws, van Rooyen and Engelbrecht2010). The Microsoft Paraphrase Corpus (Dolan, Quirk and Brockett Reference Dolan, Quirk and Brockett2004) is a collection of 1,725 pairs of statements; each assigned a semantic relatedness score determined by human judges. It has been used for evaluating the semantic relatedness methods of Yazdani and Popescu-Belis (Reference Yazdani and Popescu-Belis2010).

Another popular application is solving word choice questions. A typical question presents a target word and four choices, from which the most similar must be selected. This type of question is often found in many English language tests such as Test of English as a Foreign Language (TOEFL). It has been adopted by a number of studies, including Jarmasz and Szpakowicz (Reference Jarmasz and Szpakowicz2003), Ruiz-Casado et al. (Reference Ruiz-Casado, Alfonseca and Castells2005), Tsatsaronis et al. (Reference Tsatsaronis, Varlamis and Vazirgiannis2010), and Zesch and Gurevych (Reference Zesch and Gurevych2010a). Maguitman et al. (Reference Maguitman, Menczer, Roinestad and Vespignani2005) tested their method in a similar form. However, instead of selecting the most similar term from candidates, their task is selecting the most similar webpage (typically about specific entities) from candidate pages.

Word Sense Disambiguation (WSD) concerns associating words to their underlying meanings based on their contexts. Semantic relatedness methods have been applied in this task where the hypothesis is that the desired sense of a polysemous word is the one that is highly related to those of other words in its context. The SENSEVALFootnote ⁸ public evaluation publishes benchmarking datasets for sense disambiguation of words. In 2007, it was renamed as SEMEVAL. Many studies, including Mihalcea and Moldovan (Reference Mihalcea and Moldovan1999), Banerjee and Pedersen (Reference Banerjee and Pedersen2003), Patwardhan and Pedersen (Reference Patwardhan and Pedersen2006), and Gracia and Mena (Reference Gracia and Mena2008), have evaluated their methods using the WSD datasets published by SENSEVAL. The method by Lesk (Reference Lesk1986) and one based on Rada et al. (Reference Rada, Mili, Bicknell and Blettner1989) were evaluated in a WSD task by Navigli (Reference Navigli2006). Some methods have been evaluated by Named Entity Disambiguation (NED), where an ambiguous name mention (proper nouns) must be associated with one specific entity. Cucerzan (Reference Cucerzan2007) and Turdakov and Velikov (Reference Turdakov and Velikhov2008) each created a dataset using Wikipedia. Han and Zhao (Reference Han and Zhao2010) evaluated their method using the person name disambiguation datasets created by the SEMEVAL competition. A comprehensive survey of WSD and NED methods and relevant datasets can be found in Navigli (Reference Navigli2009). Many semantic relatedness-based methods are included and details of the SENSEVAL and SEMEVAL evaluation datasets are provided.

Sense clustering is also a common technique to evaluate semantic relatedness methods. Usually semantic relatedness between words is calculated to create a similarity matrix, to which a clustering algorithm is applied to split data into clusters based on the scores. In the general domain, Matsuo et al. (Reference Matsuo, Sakaki, Uchiyama and Ishizuka2006) and Bollegala et al. (Reference Bollegala, Matsuo and Ishizuka2007) created gold standard clusters of named entities based on the categories in the Open Directory Project.Footnote ⁹ Cilibrasi and Vitanyi (Reference Cilibrasi and Vitanyi2007) evaluated their method by hierarchical clustering of a manually created dataset of words. In the biomedical domain, Speer et al. (Reference Speer, Spieth and Zell2004) and Wang et al. (Reference Wang, Du, Payattakool, Yu and Chen2007) clustered gene products based on semantic relatedness between GO terms that are used to annotate the functions related to each gene product.

In Information Retrieval (IR), semantic relatedness can be used as a ranking method to improve search accuracy. It was first used as a task to evaluate semantic relatedness methods in Rada et al. (Reference Rada, Mili, Bicknell and Blettner1989). The method is used to calculate relatedness between queries and documents, the scores of which are then used to rank documents. Rada et al. (Reference Rada, Mili, Bicknell and Blettner1989) used the PubMed corpus and human judges in the experiment. Lord et al. (Reference Lord, Stevens, Brass and Goble2003b) built a tool for searching similar proteins in a gene annotation database. Rodrìguez and Egenhofer (Reference Rodrìguez and Egenhofer2003) evaluated their method by searching for similar concepts and/or entities in an ontology. Schickel-Zuber and Faltings (Reference Schickel-Zuber and Faltings2007) tested their method in a movie search task, in which the semantic relatedness method was used to rank results to the best match against users' preferences. Sahami and Heilman (Reference Sahami and Heilman2006) applied semantic relatedness to query expansion, a technique for improving search accuracy. Egozi, Markovitch and Gabrilovich (Reference Egozi, Markovitch and Gabrilovich2011) applied the ESA (Gabrilovich and Markovitch Reference Gabrilovich and Markovitch2007) method to both document indexing and query expansion. ESA was used to find concepts related to queries and text documents. The concepts are then used to enrich the representations of queries and documents created based on the traditional bag-of-words model. Tested with standard IR approaches, the enriched representations have led to significant improvement over the traditional bag-of-words model.

Coreference resolution is the task of identifying expressions that refer to same entities. For example, in the sentences, Google is a multinational IT corporation. The company was originally founded by Larry Page and Sergey Brin, Google and The company are coreferent expressions, since they refer to the same entity. Semantic relatedness can be used for this task because the expressions used to refer to the same entity should have a certain semantic relation (Yang and Su Reference Yang and Su2007). Ponzetto and Strube (Reference Ponzetto and Strube2006) used semantic relatedness measures to compute a score for each pair of referring expressions. The score is used as a feature in a supervised classification model for coreference resolution. They tested a list of semantic relatedness methods described in Strube and Ponzetto (Reference Strube and Ponzetto2006) for this task. Yang and Su (Reference Yang and Su2007) also used semantic relatedness scores as features but computed relatedness between two expressions using the PMI measure. Lee et al. (Reference Lee, Peirsman, Chang, Chambers, Surdeanu and Jurafsky2011) exploited the lexical chains defined for two terms in WordNet, based on a similar rationale as that of path-based semantic relatedness methods. They encoded the hypernymy and synonymy relations between synsets of terms as features in a supervised classifier. Coreference resolution is a well-established research field and standard evaluation datasets have been created. Among these, the most often used include the datasets released in the Message Understanding Conference 6 (MUC6) and MUC7 (Chinchor Reference Chinchor2001; Chinchor and Sundheim Reference Chinchor and Sundheim2003), and the dataset by Mitchell et al. (Reference Mitchell, Strassel, Przybocki, Davis, Doddington, Grishman, Meyers, Brunstain, Ferro and Sundheim2003).

Semantic similarity methods have also been tested in tasks related to ontology construction and matching. In most cases, the semantic similarity between a question term or concept and existing terms or concepts in a reference ontology are calculated, based on which it is linked to the reference ontology. Pekar and Staab (Reference Pekar and Staab2002) evaluated their method based on its application in classifying terms into a domain-specific taxonomy GETESS (Staab et al. Reference Staab, Braun, Bruder, Düsterhöft, Heuer, Klettke, Neumann, Prager, Pretzel, Schnurr, Studer, Uszkoreit and Wrenger1999). Lin (Reference Lin1998a) and Curran and Moens (Reference Curran and Moens2002) applied their methods to learning thesauri from a set of terms. Gracia and Mena (Reference Gracia and Mena2008) tested their method in an ontology matching task, where terms in an ontology are matched with those in another based on semantic similarity between them.

Malapropism detection is an application of semantic relatedness to detect misused and misspelled words in text passages. For example, word in the sentence She plans to spend her gap year travelling around the word is a misused word. It exploits the assumption that naturally coherent text passage should contain instances of related pairs of words (Budanitsky and Hirst Reference Budanitsky and Hirst2006). The datasets for this type of experiments are usually based on that by Hirst and St-Onge (Reference Hirst, St-Onge and FellBaum1998), who collected 500 articles from WSJ and artificially replaced every 200th word in the collection with a malapropism.

In addition, evaluation in the biomedical domain often adopts some domain-specific applications. In addition to the approach based on gene sequence or family similarity (Couto et al. Reference Couto, Silva and Coutinho2005; Lei and Dai Reference Lei and Dai2006; Schlicker et al. Reference Schlicker, Domingues, Rahnenführer and Lengauer2006; Pozo et al. Reference Pozo, Pazos and Valencia2008), some evaluate semantic relatedness methods by predicting gene interactions based on their functional similarity and predicting gene functions Ye et al. Reference Ye, Peyser, Pan, Boeke, Spencer and Bader2005; Yu et al. Reference Yu, Gao, Tu and Guo2005; Schlicker et al. Reference Schlicker, Domingues, Rahnenführer and Lengauer2006; Wu et al. Reference Wu, Zhu, Guo, Zhang and Lin2006). Since these experiments are non-generalizable across domains, this paper does not discuss the details. Instead, a comprehensive summary of the evaluation in the biomedical domain can be found in Pesquita et al. (Reference Pesquita, Faria, Falcão, Lord and Couto2009).