20.4.1 The Lesk Algorithm
By far the most well-studied dictionary-based algorithm for sense disambiguation is the Lesk algorithm, really a family of algorithms that choose the sense whose dictionary gloss or definition shares the most words with the target word's neighborhood. Fig. 20.3 shows the simplest version of the algorithm, often called the Simplified Lesk algorithm (Kilgarriff and Rosenzweig, 2000).
function SIMPLIFIED LESK(word, sentence) returns best sense of word
best-sense←most frequent sense for word
max-overlap←0
context←set of words in sentence
for each sense in senses of word do
signature←set of words in the gloss and examples of sense
overlap←COMPUTEOVERLAP(signature,context)
if overlap > max-overlap then
max-overlap←overlap
best-sense←sense
end
return(best-sense)
Figure 20.3 The Simplified Lesk Algorithm. The COMPUTEOVERLAP function returns the number of words in common between two sets, ignoring function words or other words on a stop list. The original Lesk algorithm defines the context in a more complex way. The Corpus Lesk algorithm weights each overlapping word w by its $ -\log P(w) $, and includes labeled training corpus data in the signature.
As an example of the Lesk algorithm at work, consider disambiguating the word bank in the following context:
The bank can guarantee deposits will eventually cover future tuition costs because it invests in adjustable-rate mortgage securities.
given the following two WordNet senses:
| $ bank^{1} $ | Gloss:\nExamples: | a financial institution that accepts deposits and channels the money into lending activities\n“he cashed a check at the bank”, “that bank holds the mortgage on my home” |
| --- | --- | --- |
| $ bank^{2} $ | Gloss:\nExamples: | sloping land (especially the slope beside a body of water)\n“they pulled the canoe up on the bank”, “he sat on the bank of the river and watched the currents” |
Sense bank $ ^{1} $ has two (non-stop) words overlapping with the context in (20.10): deposits and mortgage, while sense bank $ ^{2} $ has zero, so sense bank $ ^{1} $ is chosen.
There are many obvious extensions to Simplified Lesk. The original Lesk algorithm (Lesk, 1986) is slightly more indirect. Instead of comparing a target word's signature with the context words, the target signature is compared with the signatures of each of the context words. For example, consider Lesk's example of selecting the appropriate sense of cone in the phrase pine cone given the following definitions for pine and cone.
pine 1 kinds of evergreen tree with needle-shaped leaves
2 waste away through sorrow or illness
cone 1 solid body which narrows to a point
2 something of this shape whether solid or hollow
3 fruit of certain evergreen trees
In this example, Lesk’s method would select $ cone^3 $ as the correct sense since two of the words in its entry, evergreen and tree, overlap with words in the entry for pine, whereas neither of the other entries have any overlap with words in the definition of pine. In general Simplified Lesk seems to work better than original Lesk.
The primary problem with either the original or simplified approaches, however, is that the dictionary entries for the target words are short, and may not provide enough chance of overlap with the context. $ ^{2} $ One remedy is to expand the list of words used in the classifier to include words related to, but not contained in their individual sense definitions. But the best solution, if any sense-tagged corpus data like SemCor is available, is to add all the words in the labeled corpus sentences for a word sense into the signature for that sense. This version of the algorithm, the Corpus Lesk algorithm is the best-performing of all the Lesk variants (Kilgarriff and Rosenzweig, 2000; Vasilescu et al., 2004) and is used as a baseline in the SENSEVAL competitions. Instead of just counting up the overlapping words, the Corpus Lesk algorithm also applies a weight to each overlapping word. The weight is the inverse document frequency or IDF, a standard information-retrieval measure to be introduced in Ch. 23. IDF measures how many different 'documents' (in this case glosses and examples) a word occurs in (Ch. 23) and is thus a way of discounting function words. Since function words like the, of, etc, occur in many documents, their IDF is very low, while the IDF of content words is high. Corpus Lesk thus uses IDF instead of a stoplist.
Formally the IDF for a word i can be defined as
$$ idf_{i}=log\left(\frac{Ndoc}{nd_{i}}\right) $$
where $ N_{doc} $ is the total number of ‘documents’ (glosses and examples) and $ nd_{i} $ is the number of these documents containing word i.
Finally, it is possible to combine the Lesk and supervised approaches, by adding new Lesk-like bag-of-words features. For example, the glosses and example sentences for the target sense in WordNet could be used to compute the supervised bag-of-words features instead of (or in addition to) the words in the SemCor context sentence for the sense (Yuret, 2004).