In computational linguistics, word sense disambiguation (WSD) is an open problem of natural language processing, which comprises the process of identifying which sense of a word is used in any given sentence, when the word has a number of distinct senses (polysemy). Solution of this problem impacts such other tasks of computation linguistics, such as discourse, improving relevance of search engines, reference resolution, coherence (linguistics), inference and others.

Contents 1 About 2 Difficulties 2.1 Differency of dictionaries 2.2 Part-of-speech tagging 2.3 Inter-judge variance 2.4 Common sense 3 Approaches 4 See also 5 Notes 6 References 7 External links

[edit] About

A disambiguation process requires two strict things: a dictionary to specify the senses which are to be disambiguated and a corpus of language data to be disambiguated. Also, WSD task has two variants: "all-words" and "lexical sample" task. In the former, the program has to disambiguate all words, while the latter comprises of disambiguating only the words which were previously selected.

To give a hint how all this works, consider two examples of the distinct senses that exist for the (written) word "bass":

1. a type of fish
2. tones of low frequency

and the sentences:

1. I went fishing for some sea bass.
2. The bass line of the song is too weak.

To a human, it is obvious that the first sentence is using the word "bass", as in the former sense above and in the second sentence, the word "bass" is being used as in the latter sense below. Developing algorithms to replicate this human ability can often be a difficult task.

[edit] Difficulties

[edit] Differency of dictionaries

One problem with word sense disambiguation is deciding what the senses are. In cases like the word bass above, at least some senses are obviously different. In other cases, however, the different senses can be closely related (one meaning being a metaphorical or metonymic extension of another), and in such cases division of words into senses becomes much more difficult. Different dictionaries and thesauruses will provide different divisions of words into senses. One solution some researchers have used is to choose a particular dictionary, and just use its set of senses. Generally, however, research results using broad distinctions in senses have been much better than those using narrow, so most researchers ignore the fine-grained distinctions in their work.

[edit] Part-of-speech tagging

In any real test POS-tagging and sense-tagging are very closely related (it concerns only some languages, e.g. English) with each potentially making constraints to each other. And the question whether these tasks should be kept together or decoupled is still not unanimously resolved, but recently scientists incline to have these things separate.

[edit] Inter-judge variance

Another problem is inter-judge variance. WSD systems are normally tested by having their results on a task compared against those of a human. However, humans do not agree on the task at hand — give a list of senses and sentences, and humans will not always agree on which word belongs in which sense. A computer cannot be expected to give better performance on such a task than a human (indeed, since the human serves as the standard, the computer being better than the human is incoherent), so the human performance serves as an upper bound. Human performance, however, is much better on coarse-grained than fine-grained distinctions, so this again is why research on coarse-grained distinctions is most useful.

[edit] Common sense

Some AI researchers like Douglas Lenat argue that one cannot parse meanings from words without some form of common sense ontology. For example, comparing two these sentences:

• "Jill and Mary are sisters." — (they are sisters of each other).
• "Jill and Mary are mothers." — (each is independently a mother).

To properly identify senses of words one must know common sense facts^[1]. Moreover, sometimes the common sense is needed to disambiguate such words like pronouns in case of having anaphoras or cataphoras in the text.

[edit] Approaches

As in all natural language processing, there are two main approaches to WSD — deep approaches and shallow approaches.

Deep approaches presume access to a comprehensive body of; world knowledge. Knowledge, such as "you can go fishing for a type of fish, but not for low frequency sounds" and "songs have low frequency sounds as parts, but not types of fish", is then used to determine in which sense the word is used. These approaches are not very successful in practice, mainly because such a body of knowledge does not exist in a computer-readable format, outside of very limited domains. However, if such knowledge did exist, then deep approaches would be much more accurate than the shallow approaches. Also, there is a long tradition in computational linguistics, of trying such approaches in terms of coded knowledge and in some cases, it is hard to say clearly whether the knowledge involved is linguistic or world knowledge. The first attempt was that by Margaret Masterman and her colleagues, at the Cambridge Language Research Unit in England, in the 1950s. This attempt used as data a punched-card version of Roget's Thesaurus and its numbered "heads", as an indicator of topics and looked for repetitions in text, using a set intersection algorithm. It was not very successful, as is described in some detail in (Wilks, Y. et al., 1996), but had strong relationships to later work, especially Yarowsky's machine learning optimisation of a thesaurus method in the 1990s.

Shallow approaches don't try to understand the text. They just consider the surrounding words, using information such as "if bass has words sea or fishing nearby, it probably is in the fish sense; if bass has the words music or song nearby, it is probably in the music sense." These rules can be automatically derived by the computer, using a training corpus of words tagged with their word senses. This approach, while theoretically not as powerful as deep approaches, gives superior results in practice, due to the computer's limited world knowledge. However, it can be confused by sentences like The dogs bark at the tree which contains the word bark near both tree and dogs.

These approaches normally work by defining a window of N content words around each word to be disambiguated in the corpus, and statistically analyzing those N surrounding words. Two shallow approaches used to train and then disambiguate are Naïve Bayes classifiers and decision trees. In recent research, kernel based methods such as support vector machines have shown superior performance in supervised learning. But over the last few years, there hasn't been any major improvement in performance of any of these methods.

It is instructive to compare the word sense disambiguation problem with the problem of part-of-speech tagging. Both involve disambiguating or tagging with words, be it with senses or parts of speech. However, algorithms used for one do not tend to work well for the other, mainly because the part of speech of a word is primarily determined by the immediately adjacent one to three words, whereas the sense of a word may be determined by words further away. The success rate for part-of-speech tagging algorithms is at present much higher than that for WSD, state-of-the art being around 95% accuracy or better, as compared to less than 75% accuracy in word sense disambiguation with supervised learning. These figures are typical for English, and may be very different from those for other languages.

Another aspect of word sense disambiguation that differentiates it from part-of-speech tagging is the availability of training data. While it is relatively easy to assign parts of speech to text, training people to tag senses is far more difficult ^[2]. While users can memorize all of the possible parts of speech a word can take, it is impossible for individuals to memorize all of the senses a word can take. Thus, many word sense disambiguation algorithms use semi-supervised learning, which allows both labeled and unlabeled data. The Yarowsky algorithm was an early example of such an algorithm.

The Yarowsky algorithm uses the ‘One sense per collocation’ and the ‘One sense per discourse’ properties of human languages for word sense disambiguation. From observation, words tend to exhibit only one sense in most given discourse and in a given collocation.

[edit] See also

• Ambiguity
• Lesk algorithm
• Part-of-speech tagging
• Polysemy
• Syntactic ambiguity

[edit] Notes

1. ^ "Computers versus Common Sense". http://www.youtube.com/watch?v=KSrUHGaUE_c. Retrieved 2008-12-10. 
2. ^ Fellbaum, Christiane 1997. Analysis of a handtagging task. Proceedings of ANLP-97 Workshop on Tagging Text with Lexical Semantics: Why, What, and How? Washington D.C., USA.

[edit] References

• Wilks, Y., Slator, B., Guthrie, L. (1996) Electric Words: dictionaries, computers and meanings. Cambridge, MA: MIT Press.
• X.Y.Chou, (2007), Yarowsky’s unsupervised algorithm, Oxford Computing Lab.

[edit] External links

Look up disambiguation in Wiktionary, the free dictionary.

• Computational Linguistics Special Issue on Word Sense Disambiguation (1998)
• Evaluation Exercises for Word Sense Disambiguation The de-facto standard benchmarks for WSD systems.
• Rada Mihalcea. "Using Wikipedia for Automatic Word Sense Disambiguation" (PDF). Department of Computer Science, University of North Texas. http://www.cs.unt.edu/~rada/papers/mihalcea.naacl07.pdf. Retrieved 2008-07-13. 
• Roberto Navigli. Word Sense Disambiguation: A Survey, ACM Computing Surveys, 41(2), 2009, pp. 1-69. An up-to-date state of the art of the field.
• Word Sense Disambiguation as defined in Scholarpedia
• Word Sense Disambiguation: The State of the Art (PDF) A comprehensive overview By Prof. Nancy Ide & Jean Véronis (1998).
• Word Sense Disambiguation Tutorial, by Rada Mihalcea and Ted Pedersen (2005).
• www.wsdbook.org Companion website for the book Word Sense Disambiguation: Algorithms and Applications, edited by Agirre and Edmonds (2006). Covers the entire field with chapters contributed by leading researchers.