Improving Supervised Sense Disambiguation with Web-Scale Selectors

This paper introduces a method to improve supervised word sense disambiguation performance by including a new class of features which leverage contextual information from large unannotated corpora. This new feature class, selectors, contains words that appear in other corpora with the same local context as a given lexical instance. We show that support vector sense classifiers trained with selectors achieve higher accuracy than those trained only with standard features, producing error reductions of 15.4% and 6.9% on standard coarse-grained and fine-grained disambiguation tasks respectively. Furthermore, we find an error reduction of 9.3% when including selectors for the classification step of named-entity recognition over a representative sample of OntoNotes. These significant improvements come free of any human annotation cost, only requiring unlabeled Web-Scale corpora.


Introduction
Supervised word sense disambiguation (WSD) systems often rely directly on the local contexts in which target words appear. For example, the state-of-the-art system of Zhong et al. (2008) uses features based on collocations centered on the target word. Models relying on such features do well with copious amounts of training data, but they are prone to errors when the local context of a test instance differs from local context observed during training. Consider the sentences below.
1. The workers loaded the port onto the ship this morning. 2. She purchased a couple of bottles of port from the store. 3. The couple enjoyed their richly-flavored port.
Though referring to the same sense of 'port', "a sweet dark-red dessert wine" (Miller et al., 1993), it is difficult to connect any two instances based on local context; the parts-of-speech even differ substantially. Models for disambiguation can benefit from the addition of a feature that does not rely directly on the local context.
We present a new class of features which encodes an abstraction of a word's context, rather than encoding contents of the local context itself. We refer to this new feature class as selectors, borrowing the term from an approach to knowledge-based (unsupervised) word sense disambiguation which uses the idea of searching for words that share the same context (Lin, 1997;Schwartz and Gomez, 2008). More precisely, selectors are words that show up in the same local context as a given instance of another word. For example, selectors for 'port' in sentence 1 might be 'bottles ', 'crates', 'passengers', 'wine', 'luggage', etc. Considering that the other sentences may share some of the same selectors such as 'bottles' or 'wine', one can see how this abstraction of context to selectors can be beneficial. Figure 1 demonstrates mapping the context from one instance to selectors, which match the selectors of another instance. In this sense, it is the contexts (or word instances) that have selectors rather than the words themselves.
The contribution of this paper is the introduction of a novel and effective type of feature that improves WSD accuracy at no cost in human annotation. Rather than requiring more examples of labeled context to match a given test instance, we need only to match against an orders-of-magnitude-larger unlabeled set of data. Because selectors leverage unlabeled data, their inclusion in a supervised system constitutes semi-supervised learning.
The paper proceeds with a discussion of related work in semi-supervised WSD and the use of web-scale data in language processing (Section 2). Then, we present our approach to acquiring selectors as features from n-grams, and show how we translate selectors into features (Section 3). The effectiveness of selectors is evaluated within supervised word sense disambiguation classifiers over the SemEval-2007 Task 17 (Pradhan et al., 2007), Senseval 3 English Lexical Sample , and OntoNotes 4 (Weischedel et al., 2011) (Section 4). We also test selectors as features for the classification step of named-entity recognition over a representative sample of OntoNotes. Lastly, we discuss the robustness of selectors as features by inspecting actual instances from our experimental corpus (Section 5).
The workers loaded the port onto the ship this morning.
She purchased a couple bottles of port from the store.

Related Work
The idea of improving a supervised classifier by utilizing unlabeled data has been investigated at different levels. For example, other approaches to disambiguation have used bootstrapped samples (Yarowsky, 1995;Mihalcea and Moldovan, 1999;Mihalcea, 2004;Pham et al., 2005), Wikipedia concepts (Mihalcea, 2007), or parallel corpora (Chan et al., 2007). Most of these approaches, which are considered semi-supervised learning (Zhu, 2008), exploit some facet of unannotated text to collect more training instances. Rather than produce more training instances, we introduce a method to leverage massive unlabeled corpora to create a richer and robust set of features.
One can contrast selectors with clusters of words formed via context or distributional similarity (for seminal examples see (Brown et al., 1992;Pereira et al., 1993;Lin, 1998;Schütze, 1998;Pantel and Lin, 2002)). Distributional clusters are made up of words that appear in similar contexts to each other, whereas selectors are words which show up in the specific context of a single instance. In other words, selectors are instance-specific while distributional clusters are created based on observing many instances of context. This key difference should become more clear when we present our method of acquiring selectors.
The traditional use of selectors is in knowledge-based word sense disambiguation systems, not utilizing training data. In Lin (1997), dependency relationships over a small corpus were used to find noun selectors. We previously extended this to the Web, treating context as surrounding text and introduced the ideas of acquiring selectors for additional parts-of-speech as well as for words in context in addition to the target word Gomez, 2008, 2009). Similar to selectional preferences (Resnik, 1997), selectors essentially indicate the types of concepts expected in a given syntactic or grammatical position. In these knowledge-based approaches, disambiguation is performed by computing the semantic distance between selectors and senses of the target word. These approaches rely on both a knowledge source such as WordNet (Miller et al., 1993) and a semantic distance metric. In contrast, in the current approach we do not need such a knowledge source or similarity judgments, and since our approach is data-driven, selectors function as an abstraction of word instance context rather than as a list of semantically similar words. Our current goal is to get the most out of supervised training data by leveraging unannotated data via selectors (no use of a knowledge-base or similarity metrics). Consequently, our system achieves state-of-the-art results in line with top supervised systems while our earlier knowledge-based approaches produce results in line with systems not utilizing training data.
A couple previous works have integrated unannotated data as features into supervised disambiguation systems. Dligach and Palmer (2008) used dynamic dependency neighbors, a feature encoding verbs with the same object, according to a dependency parsed corpus, as a given target verb in a verb WSD task. Besides our method not being limited to verbs, selectors are much more specific than dependency neighbors; They are found by matching a larger context and from a much larger, web-scale, dataset. Cárcamo et al. (2008) adapt the predominant sense method of McCarthy et al. (2004) to find the best sense choice for a word instance rather than it's most common sense over a corpus. Yuret (2007) leveraged web-scale data to acquire probability distributions of substitutes being within the same context as target instances. Unlike selectors which are open-ended, substitutes were chosen from an a priori word list derived from thesauri, and contextual part-of-speech was not considered. Additionally, the substitutes' probability distribution itself was the entire feature set, rather than used to supplement an existing feature set, and the resulting accuracies were lower than those we find with selectors.
Our approach utilizes web-scale N-grams, a source of unlabeled data which has previously been used for many other supervised lexico-semantic tasks including delimiting named entities, preposition selection, spelling correction, search query processing, adjective ordering, verb POS disambiguation, and noun compound bracketing (Downey et al., 2007;Bergsma et al., 2009;Huang et al., 2010;Bergsma et al., 2010). All of these systems utilized n-grams to find frequency information for specific n-grams. In contrast, we use the n-grams as a source for acquiring sets of lexical data (selectors), where we search with context and ask for the missing piece rather than search for a complete n-grams. We believe this is the first work to use web-scale N-grams as a source for selectors; motivation for using this source is discussed in the next section.

Acquiring Selectors
A selector is a word which appears in the same local context as a given instance of a focus word. For example, in the sentence below, with 'port' as the focus word, one might find selectors such as 'bottles', 'cargo', 'crates', 'wine', 'passengers', or 'supplies'.
The workers loaded the port onto the ship last night.
More formally, for a given word instance, w i , selectors are found based on the particular context of w i . What defines the context may vary from syntactic or dependency relations (i.e., other nouns which are objects of the verb 'loaded') to simple sequences of tokens (e.g.,finding words that fill in the blank in "The workers loaded the ___ onto the ship last night.").

Approach
We find selectors by searching for sequences of tokens in the Google N-grams version 2, which contains 4.1 billion n-grams that were automatically part-of-speech tagged . The primary reason we chose web-scale N-grams as a source is because it has become difficult to get selectors via search engines. 1 Still, using web-scale n-grams for context searches has advantages: there is a decent likelihood of finding selectors for a given instance, the search Workers loaded the port onto the ship last night. workers loaded 〈det〉? (〈noun〉+) onto loaded 〈det〉? (〈noun〉+) onto (〈noun〉+) onto 〈d et〉 ship last My objective was to fight as a mother for what I hold dearest. was to (〈ver b〉+) as 〈d et〉 to (〈ver b〉+) as 〈det〉? mother objective was to (〈ver b〉+) The new economy in the US depends heavily, for one thing, on a deep foundation of basic scientific research, which comes up with revolutionary products like genetically modified foods. with revolutionary (〈noun〉+) like genetically revolutionary (〈noun〉+) like (〈noun〉+) like genetically modified ...which comes up with revolutionary products like... up with (〈ad j〉+) products like up with (〈ad j〉+) products with (〈ad j〉+) products process is offline, this version of the Google N-grams provides part-of-speech information, and they have been shown helpful for other lexico-semantic tasks (Bergsma et al., 2009;Huang et al., 2010;Bergsma et al., 2010). On the downside, because the Google N-grams are at most 5-grams, the selectors can only be found using a relatively small context. -up to 4 tokens. For this first investigation of selectors as features we think this trade-off is worthwhile.
We search the n-grams by constructing 3 to 5 token sequences consisting of words or part-ofspeech (POS) tags. Determiners, conjunctions, possessives, and symbols in the sequence are replaced with their POS tag, and determiners are also marked as optional if they do not begin or end the phrase. The slot of the focus word, the word for which selectors are being acquired, is restricted by POS and permitted to match multi-word phrases (taking the head-word as the selector in such cases). Examples of search sequences are given in Table 1.
Searching based on all sequences can be expensive in terms of disk IO, so the sequences are sorted such that the process can be halted once enough selectors have been found. In particular, we define four criteria of informative value for a given sequence seq: Next, we iterate through the list of sorted search sequences in order to aggregate selector(s) frequencies. During aggregation, the selector frequencies are normalized and weighted by in f o (seq): where sels(seq) is the set of selectors found when searching with sequence seq. This favors both selectors occurring with multiple sequences as well as those found based on a more informative context. In practice we break the aggregation loop one iteration after acquiring a soft minimum (k) of selectors to improve runtime. 2

Selectors as Features.
We have described acquisition of selectors for an arbitrary focus word instance. In order to use selectors as features, we acquire selectors for all target words (words being disambiguated) and encode the top k, according to scor e(s), as binary features. We selected k = 50 as well as weightings α 1..4 = [0.2, 0.2, 0.1, 0.5] after cross-validating over the training set (defined in Section 4).

Experiments
We evaluate whether the selector class of features can benefit WSD classifiers above and beyond a standard set of features in a variety of datasets and situations. Supervised classifiers are trained with and without utilization of selectors and we record a simple accuracy of |cor r ec t_inst ances| |al l_inst ances| * 100 of the testing data. 3 In particular, we use support vector classifiers implemented with Scikit-learn (Pedregosa et al., 2011) with a radial basis kernel and other parameters set via 5-fold crossvalidation over the training set. As a standard point of comparison, most frequent sense (M F S) accuracy is also reported, indicating the testing accuracy if the system always predicted the most common sense according to the training data. As often noted, state-of-the-art supervised systems often perform just above the M F S (Navigli et al., 2007;Pradhan et al., 2007).

Data Sets
We test selectors over three sense-annotated corpora. For our primary corpus, we use the SemEval-2007 Task 17: Lexical Sample (Pradhan et al., 2007) (results in sections 4.3.1 and 4.3.3). This corpus is an early selection from the Wall Street Journal portion of OntoNotes (Weischedel et al., 2011), and contains coarse-grained noun and verb senses. We also experiment over the Senseval-3 English Lexical Sample data , containing fined-grained noun, verb, and adjective sense annotations over selections of the British National Corpus (Clear, 1993) (section 4.3.2). The inclusion of adjectives, fine-grained senses, and difference in corpus gives us a more robust evaluation of selectors. Lastly, we experiment with random samples over portions of the full Ontonotes 4.0 in order to test on out-of-domain data and to examine if selectors help for another lexico-semantic task: named-entity classification. Details about the OntoNotes test sets are included when discussing those results (sections 4.3.4 and 4.3.5).

Baseline Features
As a consistent baseline throughout our experiments, we use the same features as Zhong et al. (2008)'s state-of-the-art system, first explored by Lee and Ng (2002). These features give the best published results that we are aware of over the Wall Street Journal portion of OntoNotes, plus they are the common denominator in many high-performance supervised WSD systems (Cai et al., 2007;Chan et al., 2007;Zhong et al., 2008).
• collocations (coll). Tokens relative to the target, denoted c i, j , starting at i; ending at j.

SemEval-2007
Tables 3 and 4 break the results down for each word. Though it is possible for selectors to introduce noise leading to occasional errors, we see that both words with many training instances as well as those with fewer ones can benefit from selectors. We will inspect a couple instances where selectors helped prediction in Section 5.

Senseval-3
We also tested selectors as features over the Senseval-3 data  to get a more robust idea of their impact. The instances in this sample come from a difference corpus, the British National Corpus, include fine-grained sense annotations, and a limited number of adjectives.
Examining the results in Table 5, we see an improvement from using selectors over the baseline for all three parts-of-speech. Overall error reductions is 6.9%. Selectors seem to help the most for both nouns and adjectives, but in the case of adjectives we actually see the mfs just outperforms the supervised systems. We suspect this is partly due to the average adjective having many more possible senses (10.2, versus 5.8 for nouns and 6.3 for verbs), and one should also keep in mind the small number of adjective examples.

Feature Impact Analysis
Results discussed thus far imply selectors are contributing information beyond that of the standard set of features. However, since selectors represent an abstraction of context and the baseline features encode various contextual information, it is possible that all information from certain baseline features is subsumed by selectors. In this experiment, we try to understand the type of information being contributed by selectors by observing accuracies when features are removed. Table 6 shows accuracy results when building classifiers with all combinations of feature types. For these tests, we used the SemEval-2007 data set, the larger and more recent of the two previously mentioned evaluation data sets. We see a clear benefit from the inclusion of selectors across the board. Interestingly, we see that although surr class of features gets the system beyond the mfs baseline, it seems to provide more distractions than help once other features are included as well. In fact, our best results come from the combination of collocations, part-of-speech information, and selectors with an accuracy of 88.1.

Out-of-Domain Test Data
It is often noted that WSD systems perform poorly on test data from a different domain than that of the training data (Zhong et al., 2008;Agirre et al., 2010). We examine whether selectors keep their benefit when tested on out-of-domain data over a portion of OntoNotes 4.0 (Weischedel et al., 2011). We put together all occurrences of a random selection of 100 nouns and verbs over three portions of OntoNotes: The Wall Street Journal (WSJ), Xinhua New Agency (Xh), and Sinorama Magazine (Sr). The Xinhua and Sinorama corpora correspond to a different source of newswire data and a different genre (magazine) respectively. As is standard, we used   We see from Table 7 that selectors still give an improvement in the case of another source of newswire. When moving to a more distant domain, such as another genre, the improvement still exists though it is no longer significant. The difficulty of the out-of-domain task is exemplified by lower M F S values, which are still based on the most frequent sense in the training data (always W SJ in this case). The results demonstrate relative robustness across minor shifts in domain, and potential for greater success if one combined them with a domain-adaptation technique.

Named Entity Classification
We believe selectors can benefit other supervised lexical disambiguation tasks. In this experiment, we seek preliminary evidence for such a belief based on improving the classification step of named entity recognition.
In named entity classification, one is given a noun phrase representing an entity with its context, and one attempts to classify the named entity into a variety of classes. We build a classifier which labels entities with one of the 18 classes provided by OntoNotes. We sample 1000 randomly selected sentences from The Wall Street Journal, Xinhua, and Sinorama portions of OntoNotes. The data is divided into training and testing samples:  We choose our features by looking at the most common types of features used during the CoNLL-2003 Shared Task in Named Entity Recognition(Tjong Kim Sang andDe Meulder, 2003), and more recent developments (Ratinov and Roth, 2009;Finkel and Manning, 2009). To the best of our knowledge state-of-the-art features have not been established for labeling all classes of Named Entities in OntoNotes, though Finkel and Manning use the three most common classes and group the others into a misc category.
• character n-grams. Character sequences of length 1 to 6.
• selectors. Selectors were included for the target word as in W SD. Table 8 shows the results for named entity classification. Here, we used one classifier and many potential labels, and thus the most frequent class accuracy is very low, corresponding to the prediction of organization for each instance. The inclusion of selectors as features increased the accuracy of our named entity classification system, with a significant 9.3% error reduction. These results, combined with the extensive W S D tests lead us to believe that selectors can also be used successfully as features for many tasks requiring contextual information, such as prepositional phrase attachment or semantic role labeling, could also benefit from the inclusion of selectors as features.

Discussion: On the Robustness of Selectors
In the previous section we saw that adding selectors to a standard feature space increases classifier accuracy. In this section, we discuss this improvement by examining the values of features extracted for instances in the SemEval-2007 experimental corpus. Particularly, we endeavor to show that selectors contribute robustness to the WSD feature space through an abstraction of context that distinguishes senses of words.
The idea of abstracting context is based on the notion that contexts which realize words of similar meaning have similar selectors. Consider the selectors for senses of both words in Table  9: 'bill' and 'occur'. We see that each of the sets of selectors varies depending on the sense of each word. Furthermore, though coarse-grained, one may even infer the sense of each word by considering its most common selectors; they should be similar to the sense.
For the the supervised classifier, selectors are an encoding or abstraction of context to help identify each sense with no need for concept similarity judgments. For example, both sentences below were annotated incorrectly without selectors, but correctly with selectors.
1. Polls show wide, generalized support for some vague concept of service, but the bill now under discussion lacks any passionate public backing. 2. Emerson, in his lecture, refers to the "startling experience which almost every person confesses in daylight, that particular passages of conversation and action have occurred to him in the same order before, whether dreaming or waking, a suspicion that they have been with precisely these persons in precisely this room, and heard precisely this dialogue, at some former hour, they know not when".
For sentence 1, selectors of bill-n.1 seem to best match the instance's local context (i.e. one can imagine inserting selectors from bill-n.1 in place of 'bill' more easily than selectors from other senses of bill). Though the training set never contained the exact context "...but the ___ now under..", it did produce selectors which match this context. In sentence 2 the immediate context before and after the target word seem contradictory: "... action have occurred..." implies occur-v.1 (to "happen or take place"), while "... occurred to him ..." implies occur-v.1 (to "come to mind"). However, when considering the whole context occur-v.2 fits best, and in fact, the selectors for this instance match with many of the most frequent selectors for occur-v.2 such as 'belong', 'lead', 'listen', and 'try'.

Extensions
We presented evidence that selectors may benefit other lexico-semantic classification tasks in section 4.3.5. Here, we discuss a few extensions to our selector acquisition approach that we believe could bring about further improvements in accuracy. The primary reason we chose to use n-grams as a source for selectors is because the Web search engines that support wildcard search (Yahoo and Google), which is necessary for efficient selector acquisition, no longer support APIs which return all matches. However, because our n-grams were restricted to the order of 5 tokens, the size of local context is limited.
To allow one to search with larger local context, a couple more advanced approaches might be employed. One solution is to use non-wildcard Web search queries (The still-supported Microsoft API could handle this) where candidate selectors are inserted in place of the wildcard. Because this would result in an expensive number of Web queries, one could limit candidates to selectors found through the web-scale 5-grams corpora. Another idea might be to use a smaller corpus than the Web where it is practical to base selectors on grammatical or dependency relationships. A similar approach was done by Lin (1997) without supervision. One can now produce dependency parses over much larger corpora. This would allow one to focus on the important constituents in context as well as capture long distance relationships. Still, part of the attractiveness of web-scale n-grams for selectors is the simplicity. Should our n-gram selectors not contain sufficient local context, one would expect selectors to be ineffective as a type of feature. We found that is not the case.

Conclusion
We introduced a novel method for increasing the informative value of a supervised disambiguation set of features by leveraging large unannotated corpora to encode an abstraction of local context via selectors. When tested over SemEval-2007 Task 17 and Senseval-3 English Lexical Sample, we found that word sense disambiguation classifiers utilizing selectors performed significantly better than those without. The improvements from selectors come free of any annotation cost, requiring only a web-scale n-gram collection. We believe other tasks, such as prepositional phrase attachment or semantic role labeling, could also benefit from the inclusion of selectors as features.