Hierarchical Semantic Classification: Word Sense Disambiguation with World Knowledge

1 Introduction

There is an increasing interest in natural language pro­ cessing (NLP) and information retrieval (IR) for research on lexical semantics, in particular with respect to word sense disambiguation [Yoong and Hwee, 2002], informa­ tion extraction [Riloff and Jones, 1999 ], named entity recognition [Collins, 2002], and automatic thesaurus exten­ sion [Hearst, 1992]. In general terms, the goal in these tasks is that of automatically associating words in text with seman­ tic labels. In information extraction and named-entity recog­ nition noun phrases or proper nouns are assigned to semantic categories such as "organization", "person", or "location". In word sense disambiguation and thesaurus extension the goal is to assign words to finer-grained categories defined by ex­ isting dictionaries and ontologies.

Lexical semantic information can be useful in many NLP and IR applications such as text categorization, parsing, and language modeling for speech recognition. Furthermore it can be crucial for tasks that require complex inferences in­ volving world knowledge, such as question answering.

One of the main difficulties in learning semantic annota­ tions stems from the fact that training instances are often nar­ rowly focused on very specific class labels and relatively few Mark Johnson Brown University mark_johnson®brown.edu in number. It thus seems intuitive to supplement task-specific training data, for example, sense-annotated training instances for a specific word, with background data encoding general "world knowledge". The latter are typically available in suf­ ficient quantities and need not to be generated separately for each classification task. To carry out this idea two crucial is­ sues need to be addressed: How exactly can world knowledge be compiled into additional training data, and how can task­ specific and background data be systematically integrated?

·we would like to thank our colleagues in the Information Re­ trieval and Machine Learning Group (IRML) and Brown Labora­ tory for Linguistic Information Processing (BLLIP), as well as Jesse Hochstadt for his editing advice. This material is based upon work supported by the National Science Foundation under Grant No. 0085940.

To address the first challenge, we propose to generate ad­ ditional training data about broader semantic categories by extracting training sentences from a hierarchically structured ontology, WordNet 1 [Fellbaum, 1998]. We assumed that each example sentence associated with a lexical entry provides ev­ idence for the kind of contexts in which that specific concept and all its ancestors in the hierarchy can appear. As far as the second challenge is concerned, we introduce a novel hierar­ chical learning architecture for semantic classification. More specifically, we present a simple and efficient on-line training algorithm generalizing the multi class perceptron of [Cram­ mer and Singer, 2002].

Finally, we carry out an experimental evaluation on a word sense disambiguation task, providing empirical evidence that the hierarchical classifier outperforms a state-of-the-art stan­ dard "flat" classifier for this task.

The paper is structured as follows. Section 2 introduces the main idea in more detail. In Section 3 we introduce WordNet and the simplified ontology derived from it that we used as the source of world knowledge. Section 4 deals with the ba­ sic multiclass perceptron and the proposed hierarchical mul­ ticomponent classifier. Finally, Sections 5 and 6 describe the data set used and the empirical results, respectively.

2 Word Sense Disambiguation and World Knowledge

Word sense disambiguation is the task of assigning to each occurrence of an ambiguous word in a text one of its possible senses. A dictionary is used to decide if a lexical entry is am­ biguous or not, and to specify its set of possible senses. The most widely used lexical resource for this task is WordNet, which we describe in detail in the next section.

1 In this paper we always refer to WordNet version 1.71.

As an illustration consider the noun "chair", which accord­ ing to WordNet is ambiguous. Two possible senses are ex­ plained in the following WordNet entries:

• chair1 - a seat for one person, with a support for the back;
• chair2 - (president, chairman, chairwoman, chair, chairperson), the officer who presides at the meetings of an organization;

Word sense disambiguation is often framed as a multi­ class pattern classification task. Useful features include co­ occurring words, word bigrams or trigrams, and properties of the syntactic context that contains the target word. Most com­ monly systems are trained on labeled data for a specific word, for each and tested on unseen items of the same word. The set of possible labels is the set of senses of the ambiguous word. One limitation of such a strategy is that the system bases its decision exclusively on what it has been able to learn about a few very specific concepts; e.g., chair1 and chair2 . Further­ more, since manually sense-tagging words for the required training data is slow and expensive, the data is quite sparse.

A great deal of information about objects like "chairs" is indirect and can be derived from more general world knowledge through generalization and inference processes. Suppose that the task is to disambiguate between the two simple senses of chair in the following context:

1. "Here the quality of the finest chair components 1s merged with art."

In this sentence components is a useful hint that we are dealing with the sense chair 1. Chairs are artifacts, and artifacts can have components. Conversely, even though in principle people could "have components" as well, this sounds a little odd. Intuitively, if a word sense disambigua­ tion system had access to this type of information - that "chairs" are subordinates of broader concepts like "artifacts" and "people" - and some knowledge about these broader semantic categories, it might achieve a higher accuracy in disambiguating words. Notice that the system might never have previously observed any instance of the noun "chair", in either sense, as "having components".

The goal hence is to complement specific but limited knowledge about narrow classes with richer, if less specific, knowledge about more general classes. We can easily recover the fact that chairs are kinds of furniture or people from dic­ tionaries and hierarchically organized ontologies like Word­ Net. Learning information about such general concepts, how­ ever, is complicated. One source of complication is the very problem we are trying to solve, lexical ambiguity. If we do not know whether something is a person or an artifact we cannot learn reliable information about those more general concepts. One way of addressing these problems is offered by WordNet itself.

3 The Ontology

3.1 WordNet

WordNet is a broad-coverage, machine-readable dictionary widely used in NLP. The English version contains around 150,000 entries, mostly nouns, but also verbs, adjectives, and adverbs. WordNet is organized as a network of lexicalized concepts, called synsets, that comprise sets of synonyms. For example, the nouns {president, chairman, chairwoman, chair, chairperson} form a synset. A word that belongs to several synsets is ambiguous. Synsets are linked by semantic rela­ tions, the most important of which for nouns and verbs is the is-a relation, or hyponymy; e.g., "car" is a hyponym of "ve­ hicle". The verb and noun databases form is-a hierarchies with a few general concepts at the top and several thousand specific concepts at the leaf level.

The hierarchical structure of the database has aroused some interest in NLP, because it can support interesting compu­ tational language learning models, for example, in learning predicate selectional preferences [Light and Greif, 2002]. We aim to use the hierarchy to improve lexical classification methods. The model we present here can in principle make use of the full hierarchy. However, for the sake of simplicity we have focused on a less complex hierarchy, which has been derived from WordNet as described below.

3.2 A simple two-level hierarchy

WordNet was built, and is regularly updated, by lexicogra­ phers. Lexicographers group words together in synsets and individuate the relevant semantic relations between synsets. This process includes the classification of lexical entries into one of 26 broad semantic classes. In this paper we refer to these broad classes with the term supersenses. A few exam­ ples ofsupersense labels are person, animal, artifact, food, lo­ cation, time, plant, process, attribute, substance, and relation. This set of labels is fairly general and therefore small. At the same time the labels are not too abstract. In other words, these classes seem natural and easily recognizable, and that is probably why lexicographers use them. In fact the level of generality is very close to that used in named-entity recogni­ tion ("location", "person", "organization", etc.).

Each synset in WordNet is associated with one supersense label. As a result the database implicitly defines, in addition to the full hierarchy, a simpler two-layer hierarchy. Figure

1 above illustrates the synsets and supersenses chair belongs to.

3.3 The hierarchy as a source of world knowledge

For a few thousand concepts WordNet lists, among other types of semantic information, one or more example sen­ tences. For the sense of chair above the example sentences are the following:

• chair1 - "he put his coat over the back of the chair and sat down"
• chair2 -"address your remarks to the chairperson"

Overall there are 9,258 of these sentences. Since each one is associated with one synset, that is in fact a sense-tagged instance of the word. In other words, WordNet provides a few thousand potential sense-tagged training instances.

Unfortunately, this additional data in itself would not be of much help: for most of the synsets there are no sentences 2 , and typically the sentences are very short and do not provide much context. However, the situation appears in a different light if we take into account the hierarchy. Considering an ex­ ample sentence for a synset also as an example sentence for its ancestors (synsets at higher levels in the hierarchy), the number of sentences grows larger at the superordinate lev­ els. If we consider the supersense level, the set of example sentences constitutes in fact a small corpus of supersense­ annotated data. Our hypothesis is that the several hundred sentences associated with each supersense can provide a use­ ful source of general world knowledge. In the next section we describe a general multicomponent learning architecture that can be used to exploit this supplementary training data.

4 Multicomponent Learning Architecture

The idea of using the hierarchical structure of a domain to overcome sparseness problems has been explored in text cat­ egorization. These methods show improved accuracy and ef­ ficiency [Toutanova et al., 2001; Dumais and Chen, 2000]. In NLP the hierarchical structure of WordNet has been used to overcome sparseness data problems for estimating class distributions [Clark and Weir, 2002], and to exploit morpho­ logical information to improve lexical acquisition [Ciaramita, 2002].

4.1 Multiclass perceptron

The architecture we propose is a generalization of "ultra­ conservative" on-line learning [Crammer and Singer, 2002], which is itself an extension of perceptron learning to the mul­ ticlass case. We describe this "flat" version of the classi­ fier first. Fot each noun w we are given a training set S = (x; , y;)f=1 , where each instance Xi E IRd and Yi E Y(w) . Y(w) is the set ofsynsets that WordNet assigns to~· Thus S summarizes n instances of noun w, where each mstance i is represented as a vector of features xi extracted from the context in which w occurred; d is the total number of features and Yi is the true label of Xi. 3

2 There are in total around 75,000 synsets in the noun database.

3 Since some instances are labeled with multiple senses, in cases where the taggers were uncertain, y; may actually be a set of labels.

Algorithm 1 Multiclass Perceptron

I : input training data (xi, Yi)i!: 1, V = 0 2: repeat 3: fori= 1, ... ,n do 4: if Hw(x;; V) 'I y; then 5: Vy; t- Vy; + Xi 6: Ei = {y E Y(w): (vy,Xi) > (vy.,x;)} 7: for y E Ei do 1 8: Vy t- Vy - TEifXi 9: end for 10: end if II: end for 12: until no more mistakes

In general, a multiclass classifier for word w is a function Hw : IRn --+ Y(w) that maps feature vectors x to one of the possible senses of w. In the multiclass perceptron, one introduces a weight vector Vy E IR d for every y E Y ( w) and defines Hw implicitly by the so-called winner-take-all rule:

Here V E IRk x d refers to the matrix of weights, every col­ umn corresponding to one of the weight vectors Vy .

The learning algorithm works as follows: Training patterns are presented one at a time in the standard on-line learning setting. Whenever Hw(Xii V) 'I y; an update step is per­ formed; otherwise the weight vectors remain unchanged. To perform the update, one first computes the error set E; con­ taining those class labels that have received a higher score than the correct class:

An ultraconservative update scheme in its most general form is then defined as follows: Update Vy +- Vy +ryxi with learn­ ing rates fulfilling the constraints Ty, = 1, L:v#y; Ty = -1, and r = 0 for y ~ Ei U {Yi}· Hence changes are limY . ited to v for y E E; U {y;}. The sum constramt ensures that the ~pdate is balanced, which is crucial to guaranteeing the convergence of the learning procedure ( cf. [Crammer and Singer, 2002]). We have focused on the simplest case of.uni­ form update weights, Ty = - 1 l, 1 for y E Ei. The algonthm is summarized in Algorithm 1.

Notice that the presented multiclass perceptron algorithm learns all weight vectors in a coupled manner, in contrast to methods that perform multiclass classification by combining binary classifiers, for example, training a classifier for each class in a one-against-the-rest manner.

4.2 Hierarchical multiclass perceptron

The hierarchical multiclass perceptron is inspired by the framework for learning over structured output spaces intro­ duced in [Hofmann et al., 2002]. The key idea is to intro­ duce a weight vector not only for every (leaf-level) class, but also for every inner node in a given class taxonomy. In the current application to word sense disambiguation, the inner nodes correspond to the 26 supersenses s and we will hence introduce additional weight vectors v 8 for s E S(w), where S(w) refers to the subset of supersenses induced by Y(w) . We will use the notation s (y) to refer to the supersense corre­ sponding to a synset y. Then discriminant functions f ( x, y) can be defined in an additive manner by

If one thinks off in terms of a compatibility function between an observation vector x and a synset y, then the compatibility score is simply the sum of two independent contributions, one stemming from the supersense level and the other one corning from the more detailed synset level. The rnulticlass classifier is then again defined using the winner-take-all rule,

Algorithm 2 Hierarchical Multiclass Perceptron

1: input training data (xj, Sj )j=1 and (x;, y;)f=1 , V = 0 2: repeat 3: for j = 1, ... , m do 4: Ef = {s E S(w): (v8 ,Xj) > (v8;,Xj)} 5: if Ef 'I 0 then 6: V8 ; t- V8 ; + Xj 7: for s E Ef do 8: V8 t- V8 - Ji$J Xj J 9: end for 10: end if II: end for 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: fori = 1, ... , n do if Hw(x;; V) 'I y; then Vy, t- Vy, + Xi E; = {y E Y(w): (vy,x;) > (vy.,x;)} for y E E; do 1 Vy t- Vy - TE;1Xi end for Ef = {s E S(w): (va,Xi) > (vs.,x;)} if Ef 'I 0 then Vs, t- V8 , +X; for s E Ef do 1 Vs t- Vs- JEfJXi end for end if end if end for 28: until no more mistakes

The complete algorithm is summarized in Algorithm 2. The first part of the algorithm concerns the different nature of the two types of training data. As we explained in Sec­ tion 3, the supplementary data derived from WordNet only provides annotations at the supersense level. We cannot use this information to perform updates for weight vectors v y, but only to adjust the weights v 8 · Hence for supersense-annotated training instances ( x 1 , s 1) we compute the error set on the supersense level as Ef = {s: (v8 ,Xj) > (v8;,Xj)} and perform the standard multi class update step for all v 8 with s E Ef U {sj}·

The second part concerns training on the task specific data ( x;, s;). If the classifier makes a mistake on pattern x; error sets are computed for its individual components both at the synset and supersense levels (lines 15 and 19 above), which are updated according to the standard rnulticlass update rule.

As an example, suppose that given a pattern x; of chair the synset error set is E; = {CHAIRfurniture, CHAIRdeath_chair }, while the correct label is y; = CHAIRperson, and thus S; = PERSON. The update vector ( ~ )x; is subtracted from the vectors relative to the labels in E;, while x; is added to vy, . If at the supersense level the error set Ef = {ARTIFACT}, x; is subtracted from the vector for ARTIFACT and added to V 8 ,. Therefore, through the supersense weight vectors, the background data affects classification at the synset level.

5 Data Set and Features

5.1 The Senseval data

We tested our system on a standard word sense disambigua­ tion data set. The training and test data are those used in the last Senseval workshop (Senseval-2/ ACL-0 1, 2001 ), which focused exclusively on word sense disambiguation. The train­ ing set consists of 8,611 paragraphs that contain an ambigu­ ous word whose sense has been manually annotated. The inventory of senses is taken from WordNet. Similarly, the test set consists of 4,328 unlabeled pairs. We only ran ex­ periments on the noun data, which consists of 3,512 training instances and 1,754 test instances. Each instance consists of a short passage taken from one of various sources: e.g., the Wall Street Journal, British National Corpus, and web pages. The task-specific training data, Ty, is typically smaller than the general one, Ts . The average ratio ITsi/ITyl is equal to 20.3.

5.2 Features

We used the same feature set described in [Yoong and Hwee, 2002], which is compact but includes most ofthe features that have been found useful in this task: surrounding words, bigrarns and trigrarns, and syntactic information. Yoong and Hwee report results for several classifiers broken down by part of speech, which makes it possible to compare our sys­ tem's performance with that of several others.

There are four types of features. The following sentence serves to illustrate them: "the dinner table and chairs are ele­ gant yet comfortable". The feature set is described in greater details in [Yoong and Hwee, 2002]:

• part of speech of the neighboring words: P _1 = CC, Po= NNS, P+1 = AUX, ...
• single words in the surrounding context: C = elegant, C = dinner, C = table, C = the, ...
• bigrarns and trigrarns: C_1,+1 = and_are, C-2,-2 = table, C+1,+2 = are_elegant, ...
• head of the syntactic phrase that governs the target: G =are, G_FQS = AUX, G-YOICE =active, G..RELPOS = left.

Syntactic features and part of speech tags were extracted from the syntactic parse trees of the Senseval-2 training and test data produced using Chamiak's parser [Chamiak, 2000] . In this way we created the training data Ty from the Senseval data. In exactly the same way we extracted features from the example sentences in WordNet to produce the additional training set for the supersense-level classes, T s. Overall there are around 250,000 features.

6 Experiments

6.1 Experimental setup

We tested two models described in Section 4: the flat multi­ class perceptron, trained and tested at the synset level, and the hierarchical one, trained on both the standard synset data and the training data for the supersenses extracted from WordNet. We also trained and tested a simple "flat" naive Bayes clas­ sifier. A different classifier was trained and tested for each word. We treated compounds such as easy chair and chair as different words.

All the results we report are given as accuracy:

6.2 Results

Figure 2 shows the performance of the flat perceptron (dotted line) during each iteration. The perceptron in fact converges very quickly. This is probably due to the fact that there are relatively few training items: Normally the size ofTy is be­ tween one and two hundred. To check whether an improve­ ment was due to the algorithm alone and not to the combina­ tion of the algorithm and the additional, supersense data set, we also trained a hierarchical perceptron exclusively on the synset data. Figure 2 also plots the performance of the hier­ archical perceptron trained only on Ty . The two curves are virtually indistinguishable, meaning that without additional information not much can be gained from using the hierarchi­ cal classifier alone. In other words, with "flat" data a "flat" classifier is as good as a "hierarchical" one.

Figure 3 plots the performances of the flat and the hierar­ chical perceptron when also trained on T s. The two patterns are very different. The hierarchical model converges only af­ ter more than 350 iterations.

This might be due to several facts. First, the amount of data is much greater due to the addition ofT s, and it takes longer to learn. Second, the supersense data and the synset data are probably very different and noisy; as a consequence the weight vectors are continually readjusted, possibly along very different dimensions. The interesting thing, though, is that even in the midst of very wide oscillations there is a clear improvement, particularly between 50 and 100 iterations.

We present also a comparative table. Table 1 illustrates the results of our systems and other state-of-the-art word sense disambiguation ones. We set the number of iterations to a fixed number for all words equal to 100. Given that we set this value "knowing" that it is a good one for both our sys­ tems, our results and those of other systems are not really comparable. However, it is reasonable to expect that it is possible to set this stopping criterion well enough using held out data. Thus this comparison gives us an approximate idea of where our systems stand with respect to state-of-the-art ones in terms of performance. AdaBoost is the classifier that gave the best result on nouns in [Yoong and Hwee, 2002], Best S2 [Mihalcea and Moldovan, 2001] refers to the best­ performing system on nouns among the Senseval-2 workshop systems. These results show that our systems' performance is comparable to that of state-of-the-art ones and that our hier­ archical model trained on background and specific data out­ performs the flat one.

Results for a few individual words are presented in Table 2. They show that the improvements are not uniform, but vary from word to word. Overall we identified 105 nouns. The great majority of these are compounds that typically occur only once in the test data. Both systems achieve approxi­ mately the same score on these data. On the bulk of the test data, however, the systems perform differently. Of the 21 test words on which the classifiers achieve different scores, the hierarchical perceptron is more accurate than the flat one on 15 words, or 71.5% of the time.

This finding suggests a simple improvement for the hierar­ chical system. The contribution of the individual components of the classifier could be weighted setting the weights, after training, using held out data. In the simplest setting binary weights could be used; e.g., either the background informa­ tion is used or not. Thus the background model would be used only when useful, otherwise its contributions would be ignored.

7 Conclusion

We have presented a learning architecture for lexical seman­ tic classification that supplements task-specific training data with background data encoding general "world knowledge" extracted from a widely used broad-coverage, machine­ readable dictionary. The model integrates task-specific and general information through a novel hierarchical learning ar­ chitecture based on the multiclass perceptron. Experiments on a word sense disambiguation task showed that the hierar­ chical model achieves improved performance over a state-of­ the-art standard "flat" system.

This new framework has a number of promising exten­ sions. Additional accuracy gains are expected by using more sophisticated perceptron learning algorithms such as the voted perceptron [Freund and Schapire, 1998] and by using the dual perceptron with non-linear kernels. We have only made use of the simplest possible form of hierarchy (two­ stage), in reality the hierarchical structure ofWordNet is very complex and much more informative. The model presented here can be extended to include this type of structure as well as other sources of information. In addition, the two-layer model can be applied to all other open-class words in Word­ Net and a full-hierarchy-based model could be applied to verbs and nouns. There is also more information to extract from WordNet, for example, from the glosses, which can po­ tentially be utilized as additional training data. Lastly, the ideas we presented here might be used with other learning methods. We leave these topics for future research.