20.2.2 Naive Bayes and Decision List Classifiers

Given training data together with the extracted features, any supervised machine learning paradigm can be used to train a sense classifier. We will restrict our discussion here to the naive Bayes and decision list approaches, since they have been the focus of considerable work in word sense disambiguation and have not yet been introduced in previous chapters.

NAIVE BAYES CLASSIFIER

The naive Bayes classifier approach to WSD is based on the premise that choosing the best sense $\hat{s}$ out of the set of possible senses $S$ for a feature vector $\vec{f}$ amounts to choosing the most probable sense given that vector. In other words:

$$ \hat{s}=\underset{s\in S}{\mathrm{a r g m a x}}P(s|\vec{f}) $$

As is almost always the case, it would be difficult to collect reasonable statistics for this equation directly. To see this, consider that a simple binary bag of words vector defined over a vocabulary of 20 words would have $ 2^{20} $ possible feature vectors. It's unlikely that any corpus we have access to will provide coverage to adequately train this kind of feature vector. To get around this problem we first reformulate our problem in the usual Bayesian manner as follows:

$$ \hat{s}=\underset{s\in S}{\argmax}\frac{P(\overrightarrow{f}|s)P(s)}{P(\overrightarrow{f})} $$

Even this equation isn’t helpful enough, since the data available that associates specific vectors $ \vec{f} $ with each sense $ s $ is also too sparse. However, what is available in greater abundance in a tagged training set is information about individual feature-value pairs in the context of specific senses. Therefore, we can make the independence assumption that gives this method its name, and that has served us well in part-of-speech tagging, speech recognition, and probabilistic parsing — naively assume that the features are independent of one another. Making this assumption that the features are conditionally independent given the word sense yields the following approximation for $ P(\vec{f}|s) $:

$$ P(\overrightarrow{f}|s)\approx\prod_{j=1}^{n}P(f_{j}|s) $$

In other words, we can estimate the probability of an entire vector given a sense by the product of the probabilities of its individual features given that sense. Since $ P(\vec{f}) $ is the same for all possible senses, it does not effect the final ranking of senses, leaving us with the following formulation of a naive Bayes classifier for WSD:

$$ \hat{s}=\underset{s\in S}{\operatorname{argmax}}P(s)\prod_{j=1}^{n}P(f_{j}|s) $$

Given this equation, training a naive Bayes classifier consists of estimating each of these probabilities. (20.6) first requires an estimate for the prior probability of each sense $P(s)$. We get the maximum likelihood estimate of this probability from the sense-tagged training corpus by counting the number of times the sense $s_{i}$ occurs and dividing by the total count of the target word $w_{j}$ (i.e. the sum of the instances of each sense of the word). That is:

$$ P(s_{i})=\frac{\mathrm{count}(s_{i},w_{j})}{\mathrm{count}(w_{j})} $$

We also need to know each of the individual feature probabilities $ P(f_j | s) $. The maximum likelihood estimate for these would be:

$$ P(f_{j}|s)=\frac{\mathrm{count}(f_{j},s)}{\mathrm{count}(s)} $$

Thus, if a collocational feature such as $ [w_{i-2} = \text{guitar}] $ occurred 3 times for sense bass $ ^1 $, and sense bass $ ^1 $ itself occurred 60 times in training, the MLE estimate is $ P(f_j | s) = 0.05 $. Binary bag-of-word features are treated in a similar manner; we simply count the number of times a given vocabulary item is present with each of the possible senses and divide by the count for each sense.

With the necessary estimates in place, we can assign senses to words in context by applying Equation (20.6). More specifically, we take the target word in context, extract the specified features, compute $ P(s) \prod_{j=1}^{n} P(f_j | s) $ for each sense, and return the sense associated with the highest score. Note that in practice, the probabilities produced for even the highest scoring senses will be dangerously low due to the various multiplications involved; mapping everything to log-space and instead performing additions is the usual solution.

The use of a simple maximum likelihood estimator means that in testing, when a target word cooccurs with a word that it did not cooccur with in training, all of its senses will receive a probability of zero. Smoothing is therefore essential to the whole enterprise. Naive Bayes approaches to sense disambiguation generally use the simple Laplace (add-one or add-k) smoothing discussed in Ch. 4.

One problem with naive Bayes and some other classifiers is that it's hard for humans to examine their workings and understand their decisions. Decision lists and decision trees are somewhat more transparent approaches that lend themselves to inspection. Decision list classifiers are equivalent to simple case statements in most programming languages. In a decision list classifier, a sequence of tests is applied to each target word feature vector. Each test is indicative of a particular sense. If a test succeeds, then the sense associated with that test is returned. If the test fails, then the next test in the sequence is applied. This continues until the end of the list, where a default test simply returns the majority sense.

Figure 20.2 shows a portion of a decision list for the task of discriminating the fish sense of bass from the music sense. The first test says that if the word fish occurs anywhere within the input context then bass $ ^{1} $ is the correct answer. If it doesn't then each of the subsequent tests is consulted in turn until one returns true; as with case statements a default test that returns true is included at the end of the list.

Learning a decision list classifier consists of generating and ordering individual tests based on the characteristics of the training data. There are a wide number of methods that can be used to create such lists. In the approach used by Yarowsky (1994) for binary homonym discrimination, each individual feature-value pair constitutes a test. We can measure how much a feature indicates a particular sense by computing the log-likelihood of the sense given the feature. The ratio between the log-likelihoods of the two senses tells us how discriminative a feature is between senses:

$$ \left|Log\left(\frac{P(Sense_{1}|f_{i})}{P(Sense_{2}|f_{i})}\right)\right| $$

The decision list is then created from these tests by simply ordering the tests in the list according to the log-likelihood ratio. Each test is checked in order and returns the appropriate sense. This training method differs quite a bit from standard decision list learning algorithms. For the details and theoretical motivation for these approaches see Rivest (1987) or Russell and Norvig (1995).

| Rule | | Sense |

| --- | --- | --- |

| fish within window | $ \Rightarrow $ | $ bass^{{1}} $ |

| striped bass | $ \Rightarrow $ | $ bass^{{1}} $ |

| guitar within window | $ \Rightarrow $ | $ bass^{{2}} $ |

| bass player | $ \Rightarrow $ | $ bass^{{2}} $ |

| piano within window | $ \Rightarrow $ | $ bass^{{2}} $ |

| tenor within window | $ \Rightarrow $ | $ bass^{{2}} $ |

| sea bass | $ \Rightarrow $ | $ bass^{{1}} $ |

| play/V bass | $ \Rightarrow $ | $ bass^{{2}} $ |

| river within window | $ \Rightarrow $ | $ bass^{{1}} $ |

| violin within window | $ \Rightarrow $ | $ bass^{{2}} $ |

| salmon within window | $ \Rightarrow $ | $ bass^{{1}} $ |

| on bass | $ \Rightarrow $ | $ bass^{{2}} $ |

| bass are | $ \Rightarrow $ | $ bass^{{1}} $ |

20.3 WSD EVALUATION, BASELINES, AND CEILINGS

Evaluating component technologies like WSD is always a complicated affair. In the long term, we're primarily interested in the extent to which they improve performance in some end-to-end application such as information retrieval, question answering or machine translation. Evaluating component NLP tasks embedded in end-to-end applications is called extrinsic evaluation, task-based evaluation, end-to-end evaluation, or in vivo evaluation. It is only with extrinsic evaluation that we can tell if a technology such as WSD is working in the sense of actually improving performance on some real task.

Extrinsic evaluations are much more difficult and time-consuming to implement, however, since they require integration into complete working systems. Furthermore, an extrinsic evaluation may only tell us something about WSD in the context of the application, and may not generalize to other applications.

For these reasons, WSD systems are typically developed and evaluated intrinsically. In intrinsic or in vitro we treat a WSD component as if it were a stand-alone system operating independently of any given application. In this style of evaluation, systems are evaluated either using exact match sense accuracy: the percentage of words that are tagged identically with the hand-labeled sense tags in a test set; or with standard precision and recall measures if systems are permitted to pass on labeling some instances. In general, we evaluate using held out data from the same sense-tagged corpora that we used for training, such as the SemCor corpus discussed above, or the various corpora produced by the SENSEVAL effort.

Many aspects of sense evaluation have been standardized by the SENSEVAL/SEMEVAL efforts (Palmer et al., 2006; Kilgarriff and Palmer, 2000). This framework provides a shared task with training and testing materials along with sense inventories for all-words and lexical sample tasks in a variety of languages.

Whichever WSD task we are performing, we ideally need two additional measures to assess how well we're doing: a baseline measure to tell use how well we're doing as compared to relatively simple approaches, and a ceiling to tell us how close we are to optimal performance.

The simplest baseline is to choose the most frequent sense for each word (Gale et al., 1992b) from the senses in a labeled corpus. For WordNet, this corresponds to the take the first sense heuristic, since senses in WordNet are generally ordered from most-frequent to least-frequent. WordNet sense frequencies come from the SemCor sense-tagged corpus described above.

Unfortunately, many WordNet senses do not occur in SemCor; these unseen senses are thus ordered arbitrarily after those that do. The four WordNet senses of the noun plant, for example, are as follows:

| Freq | Synset | Gloss |

| --- | --- | --- |

| 338 | plant $ ^{{1}} $, works, industrial plant | buildings for carrying on industrial labor |

| 207 | plant $ ^{{2}} $, flora, plant life | a living organism lacking the power of locomotion |

| 2 | plant $ ^{{3}} $ | something planted secretly for discovery by another |

| 0 | plant $ ^{{4}} $ | an actor situated in the audience whose acting is rehearsed but seems spontaneous to the audience |

The most frequent sense baseline can be quite accurate, and is therefore often used as a default, to supply a word sense when a supervised algorithm has insufficient training data. A second commonly used baseline is the Lesk algorithm, discussed in the next section.

Human inter-annotator agreement is generally considered as a ceiling, or upper bound, for sense disambiguation evaluations. Human agreement is measured by comparing the annotations of two human annotators on the same data given the same tagging guidelines. The ceiling (inter-annotator agreement) for many all-words corpora using WordNet-style sense inventories seems to range from about 75% to 80% (Palmer et al., 2006). Agreement on more coarse grained, often binary, sense inventories is closer to 90% (Gale et al., 1992b).

While using hand-labeled test sets is the best current method for evaluation, labeling large amounts of data is still quite expensive. For supervised approaches, we need this data anyhow for training so the effort to label large amounts of data seems justified. But for unsupervised algorithms like those we will discuss in Sec. 20.10, it would be nice to have an evaluation method that avoided hand labeling. The use of pseudowords is one such simplified evaluation method (Gale et al., 1992a; Schütze, 1992a). A pseudoword is an artificial word created by concatenating two randomly-chosen words together (e.g., banana and door to create banana-door.) Each occurrence of the two words in the test set is replaced by the new concatenation, creating a new 'word' which is now ambiguous between the senses banana and door. The 'correct sense' is defined by the original word, and so we can apply our disambiguation algorithm and compute accuracy as usual. In general, pseudowords give an overly optimistic measure of performance, since they are a bit easier to disambiguate than average ambiguous words. This is because the different senses of real words tend to be similar, while pseudowords are generally not semantically similar, acting like homonymous but not polysemous words (Gaustad, 2001). Nakov and Hearst (2003) show that it is possible to improve the

accuracy of pseudoword evaluation by more carefully choosing the pseudowords.

20.4 WSD: DICTIONARY AND THESAURUS METHODS

Supervised algorithms based on sense-labeled corpora are the best performing algorithms for sense disambiguation. However, such labeled training data is expensive and limited and supervised approaches fail on words not in the training data. Thus this section and the next describe different ways to get indirect supervision from other sources. In this section, we describe methods for using a dictionary or thesaurus as an indirect kind of supervision; the next section describes bootstrapping approaches.