{'fraction_non_alphanumeric': 0.03168817347346016, 'fraction_numerical': 0.012584807769056804, 'mean_word_length': 4.673358490566038, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Noisy Channel Model for Unsupervised Word Sense Disambiguation

Abstract We introduce a generative probabilistic model, the noisy channel model, for unsupervised word sense disambiguation. In our model, each context C is modeled as a distinct channel through which the speaker intends to transmit a particular meaning S using a possibly ambiguous word W. To reconstruct the intended meaning the hearer uses the distribution of possible meanings in the given context P(S|C) and possible words that can express each meaning P(W|S). We assume P(W|S) is independent of the context and estimate it using WordNet sense frequencies. The main problem of unsupervised WSD is estimating context-dependent P(S|C) without access to any sense-tagged text. We show one way to solve this problem using a statistical language model based on large amounts of untagged text. Our model uses coarse-grained semantic classes for S internally and we explore the effect of using different levels of granularity on WSD performance. The system outputs fine-grained senses for evaluation, and its performance on noun disambiguation is better than most previously reported unsupervised systems and close to the best supervised systems.


Introduction
Word sense disambiguation (WSD) is the task of identifying the correct sense of an ambiguous word in a given context. An accurate WSD system would benefit applications such as machine translation and information retrieval. The most successful WSD systems to date are based on supervised learning and trained on sense-tagged corpora. In this article we present an unsupervised WSD algorithm that can leverage untagged text and can perform at the level of the best supervised systems for the allnouns disambiguation task.
The main drawback of the supervised approach is the difficulty of acquiring considerable amounts of training data, also known as the knowledge acquisition bottleneck. Yarowsky and Florian (2002) report that each successive doubling of the training data for WSD only leads to a 3-4% error reduction within their experimental range. Banko and Brill (2001) experiment with the problem of selection among confusable words and show that the learning curves do not converge even after a billion words of training data. They suggest unsupervised, semi-supervised, or active learning to take advantage of large data sets when labeling is expensive. Yuret (2004) observes that in a supervised naive Bayes WSD system trained on SemCor, approximately half of the test instances do not contain any of the contextual features (e.g., neighboring content words or local collocation patterns) observed in the training data. SemCor is the largest publicly available corpus of sense-tagged text, and has only about a quarter million sense-tagged words. In contrast, our unsupervised system uses the Web1T data set (Brants and Franz 2006) for unlabeled examples, which contains counts from a 10 12 word corpus derived from publicly-available Web pages.
A note on the term "unsupervised" may be appropriate here. In the WSD literature "unsupervised" is typically used to describe systems that do not directly use sensetagged corpora for training. However, many of these unsupervised systems, including ours, use sense ordering or sense frequencies from WordNet (Fellbaum 1998) or other dictionaries. Thus it might be more appropriate to call them weakly supervised or semi-supervised. More specifically, context-sense pairs or context-word-sense triples are not observed in the training data, but context-word frequencies (from untagged text) and word-sense frequencies (from dictionaries or other sources) are used in model building. One of the main problems we explore in this study is the estimation of contextdependent sense probabilities when no context-sense pairs have been observed in the training data.
The first contribution of this article is a probabilistic generative model for word sense disambiguation that seamlessly integrates unlabeled text data into the model building process. Our approach is based on the noisy channel model (Shannon 1948), which has been an essential ingredient in fields such as speech recognition and machine translation. In this study we demonstrate that the noisy channel model can also be the key component for unsupervised word sense disambiguation, provided we can solve the context-dependent sense distribution problem. In Section 2.1 we show one way to estimate the context-dependent sense distribution without using any sense-tagged data. Section 2.2 outlines the complete unsupervised WSD algorithm using this model. We estimate the distribution of coarse-grained semantic classes rather than fine-grained senses. The solution uses the two distributions for which we do have data: the distribution of words used to express a given sense, and the distribution of words that appear in a given context. The first can be estimated using WordNet sense frequencies, and the second can be estimated using an n-gram language model as described in Section 2.3.
The second contribution of this article is an exploration of semantic classes at different levels of granularity for word sense disambiguation. Using fine-grained senses for model building is inefficient both computationally and from a learning perspective. The noisy channel model can take advantage of the close distribution of similar senses if they are grouped into semantic classes. We take semantic classes to be groups of WordNet synsets defined using the hypernym hierarchy. In each experiment we designate a number of synsets high in the WordNet hypernym hierarchy as "head synsets" and use their descendants to partition the senses into separate semantic classes. In Section 3 we present performance bounds for such class-based WSD and describe our method of exploring the different levels of granularity.
In Section 4 we report on our actual experiments and compare our results with the best supervised and unsupervised systems from SensEval-2 (Cotton et al. 2001), SensEval-3 (Mihalcea and Edmonds 2004), and SemEval-2007(Agirre, Màrquez, and Wicentowski 2007. Section 5 discusses these results and the idiosyncrasies of the data sets, baselines, and evaluation metrics used. Section 6 presents related work, and Section 7 summarizes our contributions.

Model
The noisy channel model has been the foundation of standard models in speech recognition (Bahl, Jelinek, and Mercer 1983) and machine translation (Brown et al. 1990). In this article we explore its application to WSD. The noisy channel model can be used whenever a signal received does not uniquely identify the message being sent. Bayes' Law is used to interpret the ambiguous signal and identify the most probable intended message. In WSD, we model each context as a distinct channel where the intended message is a word sense (or semantic class) S, and the signal received is an ambiguous word W. In this section we will describe how to model a given context C as a noisy channel, and in particular how to estimate the context-specific sense distribution without using any sense-tagged data.
Equation (1) expresses the probability of a sense S of word W in a given context C. This is the well-known Bayes' formula with an extra P(.|C) in each term indicating the dependence on the context.
To perform WSD we need to find the sense S that maximizes the probability P(S|W, C). This is equivalent to the maximization of the product P(W|S, C)P(S|C) because the denominator P(W|C) does not depend on S. To perform the maximization, the two distributions P(W|S, C) and P(S|C) need to be estimated for each context C. The main challenge is to estimate P(S|C), the distribution of word senses that can be expressed in the given context. In unsupervised WSD we do not have access to any sense-tagged data, thus we do not know what senses are likely to be expressed in any given context. Therefore it is not possible to estimate P(S|C) directly.
What we do have is the word frequencies for each sense P(W|S), and the word frequencies for the given context P(W|C). We use the WordNet sense frequencies to estimate P(W|S) and a statistical language model to estimate P(W|C) as detailed in Section 2.3. We make the independence assumption P(W|S, C) = P(W|S), that is, the distribution of words used to express a particular sense is the same for all contexts. Finally, the relationship between the three distributions, P(S|C), P(W|S, C), and P(W|C) is given by the total probability theorem: We can solve for P(S|C) using linear algebra. Let WS be a matrix, s and w two vectors such that: Using this new form, we can see that Equation (2) is equivalent to the linear equation w = WS × s and s can be solved using a linear solver. Typically WS is a tall matrix and the system has no exact solutions. We use the Moore-Penrose pseudoinverse WS + to compute an approximate solution: Appendix A discusses possible scaling issues of this solution and offers alternative solutions. We use the pseudoinverse solution in all our experiments because it can be computed fast and none of the alternatives we tried made a significant difference in WSD performance.

Algorithm
Section 2.1 described how to apply the noisy channel model for WSD in a single context. In this section we present the steps we follow in our experiments to simultaneously apply the noisy channel model to all the contexts in a given word sense disambiguation task.
Let W be the vocabulary. In this study we took the vocabulary to be the approximately 12,000 nouns in WordNet that have non-zero sense frequencies.
2. Let S be the set of senses or semantic classes to be used. In this study we used various partitions of noun synsets as semantic classes.
3. Let C be the set of contexts (nine-word windows for a 5-gram model) surrounding each target word in the given WSD task.

4.
Compute the matrix WC where WC ik = P(W = i|C = k). Here i ranges over the vocabulary W and k ranges over the contexts C. This matrix concatenates the (w) word distribution vectors from Equation (4) for each context. The entries of the matrix are computed using the n-gram language model described in Section 2.3. This is the most expensive step in the algorithm (see Appendix B for a discussion of implementation efficiency).

5.
Compute the matrix WS where WS ij = P(W = i|S = j). Here i ranges over the vocabulary W and j ranges over the semantic classes S. The entries of the matrix are computed using the WordNet sense frequencies.
Here j ranges over the semantic classes S and k ranges over the contexts C. This step computes the pseudoinverse solution described in Section 2.1 simultaneously for all the contexts, and the resulting SC matrix is a concatenation of the (s) solution vectors from Equation (4) for each context. WS + is the pseudoinverse of the matrix WS.

7.
Compute the best semantic class for each WSD instance by using argmax S P(S|W, C) ∝ P(W|S)P(S|C). Here P(S|C) comes from the column of the SC matrix that corresponds to the context of the WSD instance and P(W|S) comes from the row of the WS matrix that corresponds to the word to be disambiguated.

8.
Compute the fine-grained answer for each WSD instance by taking the most frequent (lowest numbered) sense in the chosen semantic class.

9.
Apply the one sense per discourse heuristic: If a word is found to have multiple senses in a document, replace them with the majority answer.

Estimation Procedure
In Section 2.1, we showed how the unsupervised WSD problem expressed as a noisy channel model can be decomposed into the estimation of two distributions: P(W|S) and P(W|C). In this section we detail our estimation procedure for these two distributions.
To estimate P(W|S), the distribution of words that can be used to express a given meaning, we used the WordNet sense frequencies. 1 We did not perform any smoothing for the zero counts and used the maximum likelihood estimate: count(W, S)/count(S). As described in later sections, we also experimented with grouping similar WordNet senses into semantic classes. In this case S stands for the semantic class, and the counts from various senses of a word in the same semantic class are added together to estimate P(W|S).
To estimate the distribution of words in a given context, P(W|C), we used a 5-gram language model. We define the context as the nine-word window centered on the target word w 1 w 2 . . . w 9 , where W = w 5 . The probability of a word in the given context can be expressed as: = P(w 1 )P(w 2 |w 1 ) . . . P(w 9 |w 1 . . . w 8 ) ( 6 ) ∝ P(w 5 |w 1 . . . w 4 )P(w 6 |w 2 . . . w 5 )P(w 7 |w 3 . . . w 6 ) ( 7 ) P(w 8 |w 4 . . . w 7 )P(w 9 |w 5 . . . w 8 ) Equation (5) indicates that P(W|C) is proportional to P(w 1 . . . w 9 ) because the other words in the context are fixed for a given WSD instance. Equation (6) is the standard decomposition of the probability of a word sequence into conditional probabilities. The first four terms do not include the target word w 5 , and have been dropped in Equation (7). We also truncate the remaining conditionals to four words reflecting the Markov assumption of the 5-gram model. Finally, using an expression that is proportional to P(W|C) instead of P(W|C) itself will not change the WSD result because we are taking the argmax in Equation (1). Each term on the right hand side of Equation (7) is estimated using a 5-gram language model. To get accurate domain-independent probability estimates we used the Web 1T data set (Brants and Franz 2006), which contains the counts of word sequences up to length five in a 10 12 word corpus derived from publicly-accessible Web pages. Estimation of P(W|C) is the most computationally expensive step of the algorithm, and some implementation details are given in Appendix B.

Figure 1
Upper bound on fine-grained accuracy for a given number of semantic classes.

Semantic Classes
Our algorithm internally differentiates semantic classes rather than fine-grained senses. Using fine-grained senses in the noisy channel model would be computationally expensive because the word-sense matrix needs to be inverted (see Equation [4]). It is also unclear whether using fine-grained senses for model building will lead to better learning performance: The similarity between the distributions of related senses is ignored and the data becomes unnecessarily fragmented.
Even though we use coarse-grained semantic classes for model building, we use fine-grained senses for evaluation. During evaluation, the coarse-grained semantic classes predicted by the model are mapped to fine-grained senses by picking the lowest numbered WordNet sense in the chosen semantic class. 2 This is necessary to perform a meaningful comparison with published results.
We take semantic classes to be groups of WordNet synsets defined using the hypernym hierarchy (see Section 6 for alternative definitions). Section 4 presents three WSD experiments using different sets of semantic classes at different levels of granularity. In each experiment we designate a number of synsets high in the WordNet hypernym hierarchy as "head synsets" and use their descendants to form the separate semantic classes.
An arbitrary set of head synsets will not necessarily have mutually exclusive and collectively exhaustive descendants. To assign every synset to a unique semantic class, we impose an ordering on the semantic classes. Each synset is assigned only to the first semantic class whose head it is a descendant of according to this ordering. If there are synsets that are not descendants of any of the heads, they are collected into a separate semantic class created for that purpose.
Using the coarse-grained semantic classes for prediction, Algorithm 1 will be unable to return the correct fine-grained sense when this is not the lowest numbered sense in a semantic class. To quantify the restrictive effect of working with a small number of semantic classes, Figure 1 plots the number of semantic classes versus the best possible oracle accuracy for the nouns in the SemCor corpus. To compute the oracle accuracy, we assume that the program can find the correct semantic class for each instance, but has to pick the first sense in that class as the answer. To construct a given number of semantic classes, we used the following algorithm: Initialize all synsets to be in a single "default" semantic class.

2.
For each synset, compute the following score: the oracle accuracy achieved if that synset and all its descendants are split into a new semantic class.

3.
Take the synset with the highest score and split that synset and its descendants into a new semantic class.

4.
Repeat steps 2 and 3 until the desired number of semantic classes is achieved.
The upper bound on fine-grained accuracy given a small number of semantic classes is surprisingly high. In particular, the best reported noun WSD accuracy (78%) is achievable if we could perfectly distinguish between five semantic classes.

Three Experiments
We ran three experiments with the noisy channel model using different sets of semantic classes. The first experiment uses the 25 WordNet semantic categories for nouns, the second experiment looks at what happens when we group all the senses to just two or three semantic classes, and the final experiment optimizes the number of semantic classes using one data set (which gives 135 classes) and reports the out-of-sample result using another data set.
The noun instances from the last three SensEval/SemEval English all-words tasks are used for evaluation. We focus on the disambiguation of nouns for several reasons. Nouns constitute the largest portion of content words (48% of the content words in the Brown corpus [Kucera and Francis 1967] are nouns). For many tasks and applications (e.g., Web queries [Jansen, Spink, and Pfaff 2000]) nouns are the most frequently encountered and important part of speech. Finally, WordNet has a more complete coverage of noun semantic relations than other parts of speech, which is important for our experiments with semantic classes.
As described in Section 2.2 we use the model to assign each ambiguous word to its most likely semantic class in all the experiments. The lowest numbered sense in that class is taken as the fine-grained answer. Finally we apply the one sense per discourse heuristic: If the same word has been assigned more than one sense within the same document, we take a majority vote and use sense numbers to break the ties. Table 1 gives some baselines for comparison. The performance of the best supervised and unsupervised systems on noun disambiguation for each data set are given. The first-sense baseline (FSB) is obtained by always picking the lowest numbered sense for the word in the appropriate WordNet version. We prefer the FSB baseline over the commonly used most-frequent-sense baseline because the tie breaking is unambiguous. All the results reported are for fine-grained sense disambiguation. The top three systems given in the table for each task are all supervised systems; the result for the best Table 1 Baselines for the three SensEval English all-words tasks; the WordNet version used (WN); number of noun instances (Nouns); percentage accuracy of the first-sense baseline (FSB); the top three supervised systems; and the best unsupervised system (Unsup). The last row gives the total score of the best systems on the three tasks. unsupervised system is given in the last column. The reported unsupervised systems do use the sense ordering and frequency information from WordNet.

First Experiment: The 25 WordNet Categories
In previous work, descendants of 25 special WordNet synsets (known as the unique beginners) have been used as the coarse-grained semantic classes for nouns (Crestan, El-Bèze, and De Loupy 2001;Kohomban and Lee 2005). These unique beginners were used to organize the nouns into 25 lexicographer files based on their semantic category during WordNet development. Figure 2 shows the synsets at the top of the noun hierarchy in WordNet. The 25 unique beginners have been shaded, and the two graphics show how the hierarchy evolved between the two WordNet versions used in this study.

Figure 2
The top of the WordNet noun hypernym hierarchy for version 1.7 (left) and version 2.1 (right). The 25 WordNet noun categories are shaded. We ran our initial experiments using these 25 WordNet categories as semantic classes. The distribution of words for each semantic class, P(W|S), is estimated based on WordNet sense frequencies. The distribution of words for each context, P(W|C), is estimated using a 5-gram model based on the Web 1T corpus. The system first finds the most likely semantic class based on the noisy channel model, then picks the first sense in that class. Table 2 gives the results for the three data sets, which are significantly higher than the previously reported unsupervised results.
To illustrate which semantic classes are the most difficult to disambiguate, Table 3 gives the confusion matrix for the Senseval2 data set. We can see that frequently occurring concrete classes like person and body are disambiguated well. The largest source of errors are the abstract classes like act, attribute, cognition, and communication. These 25 classes may not be the ideal candidates for word sense disambiguation. Even though they allow a sufficient degree of fine-grained distinction ( Table 2 shows that we can get Table 3 Confusion matrix for Senseval2 data with the 25 WordNet noun classes. The rows are actual classes, the columns are predicted classes. Column names have been abbreviated to save space. The last two columns give the frequency of the class (F) and the accuracy of the class (A).
ac an ar at bo co co ev fe fo gr lo mo ob pe ph po pr qu re sh st su ti  Table 4 The performance of the noisy channel model with two to three semantic classes. The columns give the data set, the head synsets, the percentage of times the model picks the correct semantic class, maximum possible fine-grained score if the model had always picked the correct class, and the actual score. 85-90% if we could pick the right class every time), they seem too easy to confuse. In the next few experiments we will use these observations to design better sets of semantic classes. Figure 1 shows that the upper bound for fine-grained disambiguation is relatively high even for a very small number of semantic classes. In our next experiment we look at how well our approach can perform differentiating only two or three semantic classes. We use Algorithm 2 applied to the appropriate version of SemCor to pick the head synsets used to define the semantic classes. Figure 2 shows that the top level of the hypernym hierarchy has changed significantly between the WordNet versions. Thus, different head synsets are chosen for different data sets. However, the main distinction captured by our semantic classes seems to be between mental and physical concepts. Table 4 gives the results. The performance with a few semantic classes is comparable to the top supervised algorithms in each of the three data sets.

Third Experiment: Tuning the Number of Classes
Increasing the number of semantic classes has two opposite effects on WSD performance. The higher the number, the finer distinctions we can make, and the maximum possible fine-grained accuracy goes up. However, the more semantic classes we define, the more difficult it becomes to distinguish them from one another. For an empirical analysis of the effect of semantic class granularity on the fine-grained WSD accuracy, we generated different sets of semantic classes using the following algorithm.
Sort all the synsets according to their "subtree frequency": i.e., the total frequency of each synset's descendants in the hypernym tree.

2.
Take the desired number of synsets with the highest subtree frequency and use them as head synsets, that is, split their descendants into separate semantic classes. Figure 3 shows the fine-grained accuracy we achieved on the Senseval2 data set with up to 600 semantic classes defined based on Algorithm 3. Note the differences: (i)

Figure 3
The fine-grained accuracy on Senseval2 data set for a given number of semantic classes. Figure 1 gives the best possible oracle accuracy, Figure 3 gives the actual WSD accuracy; (ii) Algorithm 2 chooses the head synsets based on their oracle score, Algorithm 3 chooses them based on their subtree frequency.
As we suspected, the relationship is not simple or monotonic. However, one can identify distinct peaks at 3, 25, and 100-150 semantic classes. One hypothesis is that these peaks correspond to "natural classes" at different levels of granularity. Here are some example semantic classes from each peak: 3 classes entity, abstraction 25 classes action, state, content, location, attribute, ... 135 classes food, day, container, home, word, business, feeling, material, job, man, ...
To test the out-of-sample effect of tuning the semantic classes based on the peaks of Figure 3, we used the SemEval-2007 data set as our test sample. When the 135 semantic classes from the highest peak are used for the disambiguation of the nouns in the SemEval-2007 data set, an accuracy of 69.8% was achieved. This is higher than the accuracy of the best supervised system on this task (68.6%), although the difference is not statistically significant.

Discussion
In this section we will address several questions raised by the results of the experiments. Why do we get different results from different data sets? Are the best results significantly different than the first-sense baseline? Can we improve our results using better semantic classes?

Why Do We Get Different Results from Different Data Sets?
Table 5 summarizes our results from the three experiments of Section 4. There are some significant differences between the data sets. Table 5 Result summary for the three data sets. The columns give the data set, the results of the three experiments, best reported result, the first-sense baseline, and the number of instances. The SemEval-2007 data set appears to be significantly different from the other two with its generally lower baseline and scores. The difference in accuracy is probably due to the difference in data preparation. In the two Senseval data sets all content words were targeted for disambiguation. In the SemEval-2007 data set only verbs and their noun arguments were selected, targeting only about 465 lemmas from about 3,500 words of text. For the Senseval-3 data set none of our results, or any published result we know of, is significantly above the baseline for noun disambiguation. This may be due to extra noise in the data-the inter-annotator agreement for nouns in this data set was 74.9%.

Are the Best Results Significantly Different Than the FSB?
Among all the published results for these three data sets, our two results for the Senseval-2 data set and the top supervised result for the Senseval-2 data set are the only ones statistically significantly above the FSB for noun disambiguation at the 95% confidence interval. This is partly because of the lack of sufficient data. For example, the SemEval-2007 data set has only 159 nouns; and a result of 71.8% would be needed to demonstrate a difference from the baseline of 64.2% at the 95% confidence interval.
More importantly, however, statistical significance should not be confused with "significance" in general. A statistically significant difference may not be necessary or sufficient for a significant impact on an application. Even a WSD system that is statistically indistinguishable from the baseline according to the "total accuracy" metric is most probably providing significantly different answers compared to always guessing the first sense. There are metrics that can reveal these differences, such as "balanced error rate" (i.e., arithmetic average of the error rates for different senses) or "accuracy in detecting the use of a non-dominant sense." Finally, the relatively high first-sense baseline (e.g., 71.0% for Senseval-3 nouns) combined with the relatively low inter-annotator agreement (e.g., 74.9% for Senseval-3 nouns) makes progress in the traditional WSD task difficult. Annotators who are perfectly proficient in comprehending language nevertheless find it difficult to distinguish between artificially-created dictionary senses. If our long term goal is to model human competence in language comprehension, it would make sense to focus on tasks at which humans are naturally competent. Dictionary-independent tasks such as lexical substitution or textual entailment may be the right steps in this direction.

Can We Improve Our Results Using Better Semantic Classes?
In order to get an upper bound for our approach, we searched for the best set of semantic classes specific to each data set using the following greedy algorithm. Table 6 The performance of the noisy channel model with the best set of semantic classes picked for each data set. The columns give the data set, the number of classes, maximum possible score if the model always picks the correct class, percentage of times it actually picks the correct class, and its fine-grained accuracy. 1.
Initialize all synsets to be in a single "default" semantic class.

2.
For each synset, compute the following score: the WSD accuracy achieved if that synset and all its descendants are split into a new semantic class.

3.
Take the synset with the highest score and split that synset and its descendants into a new semantic class.

4.
Repeat steps 2 and 3 until the WSD accuracy can no longer be improved.
Algorithm 4 was run for each of the three data sets, which resulted in three different sets of semantic classes. The noisy channel model was applied with the best set of semantic classes for each data set. Table 6 summarizes the results. Note that these results are not predictive of out-of-sample accuracy because Algorithm 4 picks a specific set of semantic classes optimal for a given data set. But the results do indicate that a better set of semantic classes may lead to significantly better WSD accuracy. In particular each result in Table 6 is significantly higher than previously reported supervised or unsupervised results.
How to construct a good set of semantic classes that balance specificity and identifiability is a topic of ongoing research. See Kohomban and Lee (2007) for a supervised solution using feature-based clustering that tries to maintain feature-class coherence. Non-parametric Bayesian approaches such as Teh et al. (2006) applied to context distributions could reveal latent senses in an unsupervised setting.

Related Work
For a general overview of different approaches to WSD, see Navigli (2009) and Stevenson (2003). The Senseval and SemEval workshops (Cotton et al. 2001;Mihalcea and Edmonds 2004;Agirre, Màrquez, and Wicentowski 2007) are good sources of recent work, and have been used in this article to benchmark our results.
Generative models based on the noisy channel framework have previously been used for speech recognition (Bahl, Jelinek, and Mercer 1983), machine translation (Brown et al. 1990), question answering (Echihabi and Marcu 2003), spelling correction (Brill and Moore 2000), and document compression (Daume III and Marcu 2002) among others. To our knowledge our work is the first application of the noisy channel model to unsupervised word sense disambiguation.
Using statistical language models based on large corpora for WSD has been explored in Yuret (2007) and Hawker (2007). For specific modeling techniques used in this article see Yuret (2008); for a more general review of statistical language modeling see Chen and Goodman (1999), Rosenfeld (2000), and Goodman (2001).
Ciaramita and Altun (2006) build a supervised HMM tagger using "supersenses," essentially the 25 WordNet noun categories we have used in our first experiment in addition to 15 verb categories similarly defined. They report a supersense precision of 67.60 for nouns and verbs of Senseval-3. Table 2 gives our supersense score as 78% for Senseval-3 nouns. However, the results are not directly comparable because they do not report the noun and verb scores separately or calculate the corresponding fine-grained score to compare with other Senseval-3 results.
Kohomban and Lee (2007) go beyond the WordNet categories based on lexicographer files and experiment with clustering techniques to construct their semantic classes. Their classes are based on local features from sense-labeled data and optimize featureclass coherence rather than adhering to the WordNet hierarchy. Their supervised system achieves an accuracy of 74.7% on Senseval-2 nouns and 73.6% on Senseval-3 nouns.
The systems mentioned so far are supervised WSD systems. Agirre and Martinez (2004) explore the large-scale acquisition of sense-tagged examples from the Web and train supervised, minimally supervised (requiring sense bias information from handtagged corpora, similar to our system), and fully unsupervised WSD algorithms using this corpus. They report good results on the Senseval-2 lexical sample data compared to other unsupervised systems. Martinez, de Lacalle, and Agirre (2008) test a similar set of systems trained using automatically acquired corpora on Senseval-3 nouns. Their minimally supervised system obtains 63.9% accuracy on polysemous nouns from Senseval-3 (corresponding to 71.86% on all nouns).

Contributions
We have introduced a new generative probabilistic model based on the noisy channel framework for unsupervised word sense disambiguation. The main contribution of this model is the reduction of the word sense disambiguation problem to the estimation of two distributions: the distribution of words used to express a given sense, and the distribution of words that appear in a given context. In this framework, context similarity is determined by the distribution of words that can be placed in the given context. This replaces the ad hoc contextual feature design process by a statistical language model, allowing the advances in language modeling and the availability of large unlabeled corpora to have a direct impact on WSD performance.
We have provided a detailed analysis of using coarse-grained semantic classes for fine-grained WSD. The noisy channel model is a good fit for class-based WSD, where the model decides on a coarse-grained semantic class instead of a fine-grained sense. The chosen semantic class is then mapped to a specific sense based on the WordNet ordering during evaluation. We show that the potential loss from using coarse-grained classes is limited, and state-of-the-art performance is possible using only a few semantic classes. We explore semantic classes at various levels of granularity and show that the relationship between granularity and fine-grained accuracy is complex, thus more work is needed to determine an ideal set of semantic classes.
In several experiments we compare the performance of our unsupervised WSD system with the best systems from previous Senseval and SemEval workshops. We consistently outperform any previously reported unsupervised results and achieve comparable performance to the best supervised results.

Appendix A: Solutions for P(S|C)
To solve for P(S|C) using P(W|C) and P(W|S), we represent the first two as vectors: s j = P(S = j|C = k) and w i = P(W = i|C = k), and the last one as a matrix: WS ij = P(W = i|S = j). Our problem becomes finding a solution to the linear equation w = WS × s. Using the Moore-Penrose pseudoinverse, WS + , we find a solution s = WS + × w. This solution minimizes the distance |WS × s − w|. There are two potential problems with this pseudoinverse solution. First, it may violate the non-negativity and normalization constraints of a probability distribution. Second, a maximum likelihood estimate should minimize the cross entropy between WS × s and w, not the Euclidean distance. We addressed the normalization problem using a constrained linear solver and the crossentropy problem using numerical optimization. However, our experiments showed the difference in WSD performance to be less than 1% in each case. The pseudoinverse solution, s = WS + × w, can be computed quickly and works well in practice, so this is the solution that is used in all our experiments.

Appendix B: Estimating P(W|C)
Estimating P(W|C) for each context is expensive because the number of words that need to be considered is large. The Web 1T data set contains 13.5 million unique words, and WordNet defines about 150,000 lemmas. To make the computation feasible we needed to limit the set of words for which P(W|C) needs to be estimated. We limited our set to WordNet lemmas with the same part of speech as the target word. We further required the word to have a non-zero count in WordNet sense frequencies. The inflection and capitalization of each word W was automatically matched to the target word. As a result, we estimated P(W|C) for about 10,000 words for each noun context and assumed the other words had zero probability. The n-grams required for all the contexts were listed, and their counts were extracted from the Web 1T data set in one pass. The P(W|C) was estimated for all the words and contexts based on these counts. In the end, we only used the 100 most likely words in each context for efficiency, as the difference in results using the whole distribution was not significant. For more details on smoothing with a large language model see Yuret (2008), although we did not see a significant difference in WSD performance based on the smoothing method used.