This paper presents a Word Sense Disambiguation method based on the idea of semantic density between words. The disambiguation is done in the context of WordNet. The Internet is used as a raw corpora to provide statistical information for word associations. A metric is introduced and used to measure the semantic density and to rank all possible combinations of the senses of two words. This method provides a precision of 58% in indicating the correct sense for both words at the same time. The precision increases as we consider more choices: 70% for top two ranked and 7'3% for top three ranked. Word Sense Disambiguation (WSD) is an open problem in Natural Language Processing. Its solution impacts other tasks such as discourse, reference resolution, coherence, inference and others. WSD methods can be broadly classified into three types: 1. WSD that make use of the information provided by machine readable dictionaries (Cowie et a1.1992), (Miller et a1.1994), (Agirre and Rigau, 1995), (Li et a1.1995), (McRoy, 1992); 2. WSD that use information gathered from training on a corpus that has already been semantically disambiguated (supervised training methods) (Gale, Church et al., 1992), (Ng and Lee, 1996}; 3. WSD that use information gathered from raw corpora (unsupervised training methods) (Yarowsky 1995) (Resnik 1997). There are also hybrid methods that combine several sources of knowledge such as lexicon information, heuristics, collocations and others (McRoy, 1992) (Bruce and Wiebe, 1994) (Ng and Lee, 1996) (Rigau, Asterias et al., 1997). Statistical methods produce high accuracy results for small number of preselected words. A lack of widely available semantically tagged corpora almost excludes supervised learning methods. On the other hand, the disambiguation using unsupervised methods has the disadvantage that the senses are not well defined. To our knowledge, none of the statistical methods disambiguate adjectives or adverbs so far. One approach to WSD is to determine the conceptual distance between words, that is to measure the semantic closeness of the words within a semantic network. Essentially. it is the length of the shortest path connecting the concepts (Rada et a1.1989), (Rigau. Asterias et al., 1997). By measuring the conceptual distance between words, it is possible to determine the likelihood of word sense associations. For example, the method proposed in (Li et a1.1995) tries to determine the possible sense of a noun associated with a verb using WordNet and a large text. Based on other occurrences of the verb or semantically related verbs in the text, the possible object is determined by measuring the semantic similarity between the noun objects. Methods that do not need large corpora are usually based exclusively on MRD. A proposal in this sense has been made in (Agirre and Rigau, 1995): they measure the conceptual density between nouns, by using WordNet, but the method proposed in their paper cannot be applied to measuring a conceptual distance between a verb and a noun, as no direct links are provided in MRDs between the nouns and verbs hierarchies. A WordNet-based method for measuring the semantic similarity between nouns was also proposed in (Richardson et ai., 1994). Their method consists of using hierarchical concept graphs constructed from WordNet data files, and a semantic similarity formula. Still, the method does not provide a link between different part-of-speech words. Our approach The approach described in this paper is based on the idea of semantic density. This can be measured by the number of common words that are within a semantic distance of two or more words. The closer the semantic relationship between two words the higher the semantic density between them. The way it is defined here. the semantic density works well in the case of uniform MRD. In reality there are gaps in the knowledge representations and the semantic density can provide only an estimation of the actual semantic relatedness between words. We introduce the semantic density because it is I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I relatively easy to measure it on a MRD like WordNet. This is done by counting the number of concepts two words have in common. A metric is introduced in this sense which when applied to all possible combinations of the senses of two or more words it ranks them. Another idea of this paper is to use the Internet as a raw corpora. Thus we have two sources of information: (1) the Internet for gathering statistics and (2) WordNet for measuring semantic density. As will be shown below, a ranking of words senses results from each of these two sources. The issue now is how to combine these two rankings in order to provide an overall ranking. One possibility is to use them in parallel and the other one is to use them serially. We have tried both and the serial approach provided better results. Thus, for a verb -noun pair, the WSD method consists of two Algorithms, the first one ranks the noun senses, of which we retain only the best two senses; and a second Algorithm takes the output produced by the first Algorithm and ranks the pairs of verb -noun senses. Extensions of this method to other pairs than verb -noun are discussed, and larger windows of more than two words are considered. An essential aspect of the WSD method presented here is that we provide a raking of possible associations between words instead of a binary yes/no decision for each possible sense combination. This allows for a controllable precision as other modules may be able to distinguish later the correct sense association from such a small pool. WordNet is a fine grain MRD and this makes it more difficult to pinpoint the correct sense combination since there are many to choose from and many are semantically close. For applications such as machine translation, fine grain disambiguation works well but for information extraction and some other applications this is an overkill, and some senses may be lumped together. A simple sentence or question can usually be briefly described by an action and an object; for example, the main idea from the sentence He has to investigate all the reports can be described by the action-object pair investigate-report. Even the phrase may" be ambiguous by having a poor context, still the results of a search or interface based on such a sentence can be improved if the possible associations between the senses of the verb and the noun are determined. In WordNet (Miller 1990) , the gloss of a verb synset provides a noun-context for that verb, i.e. the possible nouns occurring in the context of that particular verb. The glosses are used here in the same way a corpus is used. In order to improve the precision of determining the conceptual density between a verb and a noun, the senses of the noun should be ranked, such as to indicate with a reasonable accuracy the first possible senses that it might have. The approach we considered for this task is the use of unsupervised statistical methods on large texts. The larger the collection of texts, the bigger is the probability to provide an accurate ranking of senses. As the biggest number of texts electronically stored -and thus favoring an automatic processing -is contained on the Web, we thought of using the Internet as a source of corpora for ranking the senses of the words. This first step of our method takes into consideration verb-noun pairs V -N, and it creates pairs in which the verb remains constant, i.e. V, and the noun is replaced by the words in its similarity lists. Using WordNet, a similarity list is created for each sense of the noun. and it contains: the words from the noun synset and the words from the noun hypernym synset.  The pairs that may be formed are: . Search the [nternet and rank senses. A search performed on the Internet for each of these groups will indicate a ranking over the possible senses of the noun N. In our experiments we used (AhaVista) since it is one of the most powerful search engines currently available. where the asterisk (*) is used as a wildcard indicating that we want to find all words containing a match for the specified pattern of letters. Using one of these queries, we can get the number of hits for each sense i of the noun and this provides a ranking of the m senses of the noun as they relate with the verb V. We tested this method for 80 verb-noun pairs extracted from SemCor 1.5 of the Brown corpus, i Using query form (a) as an input to the search engine, we obtained an accuracy of 83% in providing a ranking over the noun senses, such as the sense indicated in SemCor was one of the first two senses in this classification. [n Table 1 , we present a sample of the results we obtained. The column Result in this table presents the ranking over the noun senses: a I in this column means that the sense indicated in SemCor was also indicated by our method: 2 means that the sense indicated in SemCor was in top two of the sense ranking provided by our method; similarly, 3 or 4 indicates that the sense of the noun, as specified in :~emCor, was in the top three, respectively four, of 1;his sense ranking. We u.,ed also the query form (b), but the results we obtained have been proved to be similar; using the operator NEAR, a bigger number of hits is reported, but the sense ranking remains the same. It is i:ateresting to observe that even we are creating queries starting with a verb-noun pair, it is ITh~: verb-noun pairs have been extracted from the file br-aO:. not guaranteed that the search on the web will identify only words linked by such a lexical relation. We based our idea on the fact that: (1) the noun directly following a verb is highly probable to be an object of the verb (as in the expression "Verb* Noun*") and (2) for our method, we are actually interested in determining possible senses of a verb and a noun that can share a common context. 2. Using the method described in section 3, the senses of the noun are ranked. Only the first two possible senses indicated by this step will be considered. 3. For each possible pair Vi --n), the conceptual density is computed as follows: (a) extract all the glosses from the subhierarchy including vi (the rationale of the method used to determine these subhierarchies is explained below) (b) Determine the nouns from these glosses. These constitute the noun-context of the verb. All these nouns are stored together with the level of the associated verb within the sub-hierarchy of vi. In order to determine the sub-hierarchies that should be used for vl and nj, we used statistics provided by SemCor, a sense tagged version of the Brown corpus (Francis and Kucera, 1967) (Miller, Leacock et al., 1993), containing 250,000 words. Each word (noun, verb, adjective, adverb) is ineluded in a synset within a hierarchy. The tops of these hierarchies denominate the class of the word. The sense in SemCor for a word W is indicated by the class C of the word W, and the sense of the word within the class C. For example, the SemCor entry: Table 2 , the class of the noun indicates with a probability of 85% a correct sense 1 within that class. Thus, for this algorithm, we consider for a noun the hierarchy including the noun (if the class of the noun ni is C', then the method considers all the nouns from the class C). This does not work for the verbs, as the probability to indicate a correct sense knowing the class is much smaller (only 60%). For this reason, and based on the experiments we computed, the sub-hierarchy 19 including a verb vi is determined as follows: (i) consider the hypernym hi of the verb oi and (ii) consider the hierarchy having hi as top. It is necessary to consider a bigger hierarchy then just the one provided by synonyms and direct hyponyms, since providing accuracy in a metric computation needs large corpora. As we replaced the corpora with the glosses, better results are achieved if more glosses are considered. Still, we do not have to enlarge too much the context, in order not to miss the correct answers. For determining the conceptual density between a noun ni and a verb vj, the algorithm considers: • the list of nouns sv~ associated with the glosses of the verbs within the hierarchy determined by hi: (svk,w~), where: -hj is the hypernym of vj -w~ is the level in this hierarchy • the list of nouns snt within the class of ni : The common words between these two lists (svk,wk) and (snt) will produce a list of common concepts with the associated weights cdij < w~ >. The conceptual density between rli and vj is given by the formula: where: • Icdijl is the number of common concepts between the hierarchies of ni and uj • w~ are the weights associated with the nouns from the noun-context of the verb vj • desci is the total number of words within the hierarchy of noun nl As the nouns with a big hierarchy tend to indicate a big value for Icdijl, the weighted sum of common concepts has to be normalized in respect with the dimension of the noun hierarchy. This is estimated as the logarithm of the total number of descendants in the hierarchy (i.e. Io9(desci)). We also took into consideration other metrics, like: (2) The number of common concepts between the noun and verb hierarchies, without considering the weights. A possible improvement to the metric (1) is to consider the weights for the levels in the noun hierarchy, in addition to the levels in the verb hierarchy. An example Consider as example of a verb-noun pair the phrase revise lau¢. The verb revise has two possible senses in WordNet 1.5: Sense 1 revise, make revisions in gloss: (revise a thesis, for example) =~ rewrite, write differently, alter by writing gloss: ("The student rewrote his thesis") Sense 2 re tool, revise =~ reorganize, shake up, organize an The noun law has 7 possible senses Sense 1 law, jurisprudence gloss: (the collection of rules imposed by authority; ~civilization presupposes respect for the law") collection, aggregation, accumulation, assemblage gloss: (several things grouped together) Sense 2 law gloss: (one of a set of rules governing a particular activity or a legal document setting forth such a rule; "there is a law against kidnapping" ) ~, rule, prescript gloss: (prescribed guide for conduct or action) =~ legal document, legal instrument, ofl~icial document, instrument Sense 3 law, natural law gloss: (a rule or body of rules ofconduct inherent in human nature and essential to or binding upon human society) =~ concept, conception gloss: (an abstract or general idea inferred or derived from specific instances) Sense 4 law, law of nature gloss: (a generalization based on recurring facts or events (in science or mathematics etc): "the laws of thermodynamics) concept, conception gloss: (an abstract or general idea inferred or derived from specific instances) Sense 5 jurisprudence, law, legal philosophy gloss: (the branch of philosophy concerned with the law) philosophy gloss: (the rational investigation of questions about existence and knowledge and ethics) Sense 6 police, police force, constabulary, law gloss: (the force or policemen and officer~; "the law came looking for him" } =~ force, personnel gloss: (group of people willing to obey orders} Sense T law. practice of law gloss: Ithe learned profession that is mastered by graduate study in a law school and that is responsible for the judicial system; "he studied law at Yale") :*. learned profession gloss: (one of the three professions traditionally believed to require advanced [earning and high principles) We searched on lnternet, using AltaVista, for all possible pairs V-N that may be created using revise and the words from the similarity lists of law. Over the seven possible senses for this noun, the first step of our method indicated the following ranking (we indicate the number of hits between parenthesis):law#e(2829), !aw#3(648), law#4(640), law#6(397),   1aw#1(224), 1aw#5(37), taw#7(0) . Thus, only the sense #• and #3 of the noun law are eligible to be used for the next algorithm. For each of the two senses of the verb, we determined the noun-context, including the nouns from the glosses in the sub-hierarchy of the verb, and the associated weights. For each of the two possible senses of the noun, we determined the nouns from the class of each sense. In Table 3 , we present: (1)  Tests against SemCor We tested this method by using verb-noun pairs from SemCor. A randomly selected sample from the entire table with 80 pairs is presented in Table 4 . For each pair verb-noun, we indicate the sense of the verb (column B). the sense of the noun (column C), as they result from SemCor; the total number of possible senses for both the verb (column D) 2The notation #iln means sense i out of n possible. I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I i I these cases, the NEAR operator should be used for the first step of this algorithm). 2. The number of words considered at a time can be increased, from two to three, four or even more words. I In this paper, we have presented a method for WSD that is based on measuring the conceptual density between words using WordNet. The metric proposed may be further improved by considering the weights for verbs as well as for nouns. The senses of the words are ranked, and an user may select the first choice or the first few choices, depending upon the application. We have also proposed to use the Internet as a source of statistics on a raw corpora. The method extends well to considering more than two words at a time, and also for all parts of speech covered by WordNet. It is difficult to compare the precision obtained by this method with other methods, since we consider here the collective meaning of two or more words, while most of other methods consider one word at a time. However, an estimation can be done by extracting the square root of the accuracy for a pair of verb-noun words; and that is 76.15% for the first choice, 83.66% for the first two choices and 85.44% for the first three choices. Since the disambiguation precision for nouns is usually higher than for verbs, those numbers provide only an average. Abstract This paper describes a probabilistic model that is formed from the integration of an analytical and empirical component. The analytical component is a Bayesian network derived from WordNet, and the empirical component is composed of compatible probabilistic models formulated from tagged training data. The components are integrated in a forreal, uniform framework based on the semantics of causal dependence. The paper explores various representational issues that must be addressed when formulating a Bayesian network representation of lexical iaformation such as that expressed in WordNet. These issues are essential to the design of such a network and they have not been previously explored. We describe two choices for the representation of lexical items and two choices for the representation lexical relations. The effect of each combination of choices on evidence propagation in the network is discussed. References
Prior knowledge about the likelihood of different senses or semantic classes is derived heuristically by submitting queries (e.g., great hurricane) to the AltaVista search engine and extrapolating from the number of returned documents the frequency of the adjective-noun pair (see REF for details of this technique).
Word Sense Disambiguation Based On Semantic Density
Workshop On Usage Of WordNet In Natural Language Processing Systems
Computer Science