Word Sense Disambiguation through Sememe Labeling

1 Introduction

Word sense disambiguation (WSD) is one of the important tasks in natural language processing. Given the context of a word, a WSD system should automatically assign a correct sense to this word. WSD has been studied for many years. Current word sense disambiguation systems are mainly individual word sense experts [Ide et al., 1998]. In these systems, there are mainly two categories of the target word's contexts. One category is the words in some windows surrounding the target word, the other category is the relational information, such as syntactic relation, selectional preferences, etc. But senses of contextual words, which may also need to be disambiguated, attract little attention. In this paper, senses of contextual word and the target word are simultaneously considered. We try to incorporate sense transitions between every contextual word and the target word into one framework, and our target is to disambiguate all words through determining word sense transitions.

Some scholars have done relative researches on globally modeling word sense assignments. Some methods have been proposed, including GAMBL (a cascaded memory-based classifiers) [Decadt et al., 2004], SenseLearner [Mihalcea and Csomai, 2005], Naïve Bayes methods [Yuret, 2004].

Most of these methods still based on individual word experts while our motivation is to model word sense transitions. This is a different view of globally modeling word sense assignments. In a sentence with no syntactic information, word sense transitions take the form of linear chain. That is, transitions are from left to right, word by word. In a sentence with dependency syntactic information, word sense transitions are from all children to their parent. Although linear chain word sense transitions had been studied, by using simulated annealing [Cowie et al., 1992] and unsupervised graph-based algorithm [Mihalcea, 2005], the number of word sense transitions is so tremendous that they are not easy to be captured. In order to circumvent this shortcoming, we adopt HowNet (http://www.keenage.com) knowledge base to decompose every word sense into several sememes (usually no more than 6 sememes). HowNet defines a closed set of sememes that are much less than word senses. But various combinations of these sememes can describe various word senses. It is more practical to model sense transitions through sememes than through pure word senses.

Then one transition between two words' senses becomes multiple transitions between sememes. In this paper, we propose multi-layered conditional random fields (MLCRF) to model sememe transitions. As we know, conditional random fields (CRF) can label nodes of structures like sequences and trees. Consecutive labels in CRF also constitute label transitions. Therefore, the problem of modeling sememe transitions can also be viewed as sememe labeling problem.

There are researches on HowNet-based WSD. Wong and Yang [2002] have done a similar work to ours. Just like POS tagging, they regarded WSD as word sense tagging and adopted a maximum entropy approach to tag senses. In section 4.2, we made some comparisons. The experiments show that MLCRF performs better than a base-line system and Wong and Yang's maximum entropy model. Syntactic and hypernym features can enhance the performance significantly.

2 An Introduction of HowNet

HowNet [Zhendong Dong et, 2006] is a bilingual common-sense knowledge base. One important component of HowNet is the knowledge dictionary, which covers over 6,500 words in Chinese and close to 7,500 English equivalents. We use this knowledge dictionary to generate candidate senses of a word. In HowNet, each candidate sense of one word is a combination of several sememes. For example, a sense definition of the Chinese word "research institute" is as follows:

DEF=InstitutePlace, *research, #knowledge

where word sense (DEF) is split into sememes by commas. The sememes in this example are "InstitutePlace", "research", "knowledge". Symbols preceding sememes represent relations between the entry word and the corresponding sememe. In this example, symbols are "*" and "#". Symbol "*" represents agent-event relation, "#" represents co-relation. This word sense (DEF) can be glossed as: "research institute" is an "InstitutePlace", which acts as an agent of a "researching" activity, and it has a co-relation with "knowledge".

Sememes are the most basic semantic units that are non-decomposable. It is feasible to extract a close set of sememes from Chinese characters. This is because each Chinese character is monosyllabic and meaning bearing. Using this closed set of sememes, HowNet can define all words' senses through various combinations of these sememes.

A word sense is defined by sememes according to an order. The first sememe in a word sense definition represents the main feature of the sense of that word, and this main feature is always the category of that sense. In the example mentioned above, the main feature of the word "research institute" is "InstitutePlace". Other sememes in a word sense are organized by an order of importance from the HowNet's point of view. In our current system, symbols representing relations are omitted.

Totally, HowNet contains 1,600 sememes, which are classified into 7 main classes, including "entity", "event", "attribute", "attribute value", "quantity", "quantity value", "secondary feature". These 7 main classes are further classified hierarchically. In the end, all of 1,600 sememes are organized as 7 trees. Each sememe besides the root sememe has a hypernym (A is a hypernym of B if B is a type of A). For example, "InstitutePlace" has a hypernym "organization", "organization" has a hypernym "thing", "thing" has a hypernym "entity". The hypernym feature shows usefulness in our word sense disambiguation system.

3 System Description

3.1 Task Definition

Our task is to disambiguate word senses through sememe labeling. Here is the formal description of our task. In what follows, X denotes a sentence. The ith word of X is denoted by i , and the sentence's length is n. According to HowNet, the sense of each is decomposed into m layers x i x of sememes denoted by im i1 , where m is an empirical parameter depending on how much layers of sememes bound together can differentiate word senses from each other. Please note that i1 are ordered by decreasing importance. For example, 1 i is the first sememe in the sense definition of i . With some simplification of the HowNet knowledge dictionary, word senses can distinguish each other by 2 layers of sememes. If sememes are taken as labels, every word i has 2 layers of labels. Word sense disambiguation becomes a 2-layered labeling problem. Sememe labeling can be carried on flat sentences (sequences) or dependency syntactic trees. This is illustrated in Figure 1. y y ,... im y y ,... y x x Sememes per layer constitute a label configuration of the sentence. These m layer configurations of the sentence are denoted by m ,... 1 . Our aim is to find:

We propose a layer-by-layer strategy "MLCRF" to solve this equation. Current layer sememe labeling can use labeled pre-layer sememes as features. The order of the strategy is bottom up, from 1 st layer to mth layer. To introduce MLCRF, we introduce conditional random fields in the following section.

3.2 Introduction of Conditional Random Fields

Conditional random fields (CRF) [Lafferty et al., 2001] are undirected graphical models used to calculate the conditional probability of a set of labels given a set of input values. We cite the definitions of CRF in [McCallum, 2003]. It defines the conditional probability proportional to the product of potential functions on cliques of the graph,

where X is a set of input random variables and Y is a set of random labels. c c c is the clique potential on clique c. C(Y,X) is the set of all cliques of the graph. In CRF, clique is often an edge with a node on each end. c represents labels of the two end nodes. Clique potential is often defined as: ) , (

where is an arbitrary feature function over its arguments, r r f is a learned weight for each feature function, R is the total number of feature functions of the clique. is a normalization factor over all output values,

Two dynamic programming algorithms are employed: Viterbi for decoding and a variant of the forward-backward algorithm [Sha and Pereira, 2003] for the computing of expectations and normalization.

Two kinds of CRF are used in our system: sequential CRF and tree CRF. Sequential CRF is like traditional linear chain CRF, while tree CRF is slightly different. In linear chain CRF, one clique is composed of current word and its pre-word. In tree CRF, one clique is composed of current word and one child of it. Tree CRF adopts sum-product algorithm [Pearl, 1988], which is an inference algorithm in graphical models. Cohn and Blunsom [2005] have used tree CRF to solve semantic role labeling. But the algorithm was not presented. In this paper, we take sum-product algorithm into a forward-backward frame. Each node in the tree has several sub forward (backward) vectors. The detailed description of the algorithm is not included in this paper for the limit of the paper length.

3.3 Multi-layered Conditional Random Fields

In multi-layered conditional random fields, the conditional probability is as follows:

where i c ] [ denotes t he product of clique potentials of the ith etc denotes normalization factor. For example, layer.

where denotes the pair of mth layer labels of the words of clique c. m c,

yer probabilities respectively. Each layer CRF rained ind , using seque ) , ) | ( ,…, ) , ,..., | ( 1 1 m m represent 1, 2, …, mth la model can be t | ( 1 ividually ntial CRF or tree CRF.

Sutton et al. [2004] use dynamic CRF to perform multiple, cascaded labeling tasks. Rather than perform approximate inference, we perform exact inference. To avoid exponential increase, we propose a multi-layered Viterbi algorithm for decoding.

To illustrate multi-layered Viterbi, let us look back on single layer decoding. For single layer, the most probable Y is as follows:

here w c c c ) , ( ) , ( . The denominator is itom

ause is the sam ul e next layer decod ted bec e for all Y. But in m ti-layered case, th ing will use pre layer labels as features, so the denominators are no longer the same.

For the ease of explanation, let us consider linear chain CRF of single layer. If the denominator is not omitted for one layer, it can also be expressed as:

i ain. where denotes the forward vector at the ith position of the ch ) ( sum denotes the sum of the vector 's elements. In CRF, the sum of the forward vector i 's elements is the sum of all possible paths up to the ith position. So ) ( n sum is equal to .

Then the linear chain probability is as follows:

Equation 8 shows that the linear chain probability can be puted dynamically. At each time step, we can get probcom ability up to that time. Based on this single layer equation, we can derive the multi-layered Viterbi algorithm.

With some simplification of the HowNet knowledge dictionary, word senses can distinguish each other by 2 layers of sememes. We present a 2-layer Viterbi for sequential CRF in Figure 2. Multi-layered Viterbi can be extended from 2-layer Viterbi. In Figure 2, all forward vectors and transition matrices M are only about second layer. i S denotes a combined label of 2 layers at ith position, S 2 , i denotes the second layer label at ith position. Suppose that the label set of each layer contains k elements, then i S k*k kinds of 2-layer combinations. has In 2-layer Viterbi, we do not need transition m trices and forward vectors of 1 ause is the same for l a st layer bec al 1 . But for 2 nd layer, the normalizing factor is 1 , , where 1 is the 1 st layer sememes that are related to 1 st layer decoding. So forward vectors and transition matrices are nee d to calculate normalization factor for the 2 de nd layer only. ) , ( 2 , 2 , 1 i i i s s is the forward vector of 2 nd layer at ith position. ) , ( 2 , i s s M is the transition matrix of 2 2 , 1 i i nd layer at ith position. and 2 , ] [ i 1 , ] [ i nd lay are the logarithm value of 1 st layer and 2 er's ith clique potential respectively.

Initial value: 0 ) ( 0 s Val , 0 s is the initial state ] 0 ... 1 [ ) ( 2 , 0 0 s for every pos ' iti n i: for every candidate 2-layer label i s i o i s : ' s s ) , ( ) ( ) , ( 2 2 , 1 2 , 1 1 2 , 2 , 1 i i i i i i i s M s , Val )} , ( ) ( { max ) ( 1 1 1 i i i s i s s pair s Val s ))]} ( ( log[ ))] , ( ( {log[ ] [ ] [ ) , ( 2 , 1 1 ' 2 , 2 , 1 2 , 1 , 1 i i i i i i i i i s sum s s sum s s pair i the end node )} , ( ) ( { max arg 1 1 1 ' 1 i i i s i s s pair s Val s ) , ( ) ( 2 , ' 2 , 1 2 , ' i i i i i s s s till

of 2-layer Viterbi for one sentence he number of 1 st layer labels, K is The time complexity is O( T K J 4 2 ), where J is t the number of 2 nd layer labels, T is the length of the sentence. Figure 2 mainly deals with sequence. When applying it to trees, sub s for every tree node should be introduced. In our problem for WSD, i S is the candidate sense at position i, whic is less than 2-layer combinations of entire labels. h

3.4 Reducing the Number of Candidate Labels

nour In common CRF, every input variable i has several ca didate labels. There are 1,600 sememes in HowNet. For x WSD problem, it is impractical to treat all these sememes as candidate labels for the training of single layer CRF.

is Using the HowNet knowledge dictionary we can generate candidate sememes much less. We propose two methods to reduce the number of candidate sememes. One DefSpace and the other is ExDefSpace. In the following, we will introduce how to apply these two methods to first layer CRF in detail.

DefSpace

emes appeared in the definitions of this wNet. DefSpace generates a real space that only For DefSpace, candidate first layer sememes of a word are the first layer sem word in Ho includes the labels (sememes) listed in the definitions of the entry word. For example, Chinese word fazhan has 3 senses in the HowNet dictionary: "CauseToGrow", "grow" and "include". Since all these senses are single sememes, candidate sememes of the first layer are these 3 sememes for DefSpace.

ExDefSpace

words a and b. According to the HowNet dic2 candidate first layer sememes sem_1 and ExDefSpace is the extended version of DefSpace. Suppose there are two tionary, a has sem_2, b has 2 candidate first layer sememes sem_2 and sem_3. Suppose a appears in the training corpus while b does not appears. Considering training examples of a with sem_1 or sem_2, for DefSpace, the training procedure only discriminates sem_1 and sem_2, while sem_2 and sem_3 are not discriminated in this discriminative training. Then when b appears in test data, it can't be disambiguated. To overcome this shortcoming of DefSpace, candidate sememes of a word are extended. For every sememe in HowNet, we build a candidate sememe list. Concretely speaking, for every sememe s, we search the whole dictionary entries to find sememes of first layer that together with s define a common polysemous word. All such sememes are put into the candidate sememe list of s. Then during training, the candidate sememes of a word are generated according to the hand labeled sememe's candidate list. For above example, sem_3 is added to the candidate lists of sem_1 and sem_2. Then word a provides a positive example of sem_1 or sem_2, but a negative example of sem_3. Also, if one sem_3 is tagged in the training corpus, it provides a negative example of sem_1 or sem_2.

Finally, in a sememe's candidate sememe list, there are average 11.76 candidate sememes.

sememes of a word are generated e labeled first layer semem Candidate second layer according to this word's entries in HowNet whose first layer sememes are the same as th e. This is like DefSpace used in first layer CRF.

aken. In the phase of decoding (multi-layered Viterbi), only multiple senses of a word are regarded as candidate senses of this word. No special measure like ExDefSpace is t

3.5 Feature Set

actored representation for features. In MLCRF, training is taken layer by layer. For first layer, we use the following f

current is a binary predicate on pairs where ) , ( c p is a binary predicate on the input X and clique c, ) , ( ' c c q of labe nt clique c. For instance, ) , ( c p might be " whether word at position i is de". ls of curre Table 1 presents the categories of ) , ( c p and ) , ( ' c c q .

For first layer, a label of the clique c is the first layer semem st f ith word i eme f cu e. In table 1, s_i_0 denotes 1 layer sememe o n sequential CRF and s_n_0 denotes 1 st layer sem o rrent node n in tree CRF. "^" denotes hypernym, uni, bi and tri denote unigrams, bigrams and trigrams respectively, w denotes word, p denotes POS. The subscript seq and tree represent sequential CRF and tree CRF respectively. For tree CRF, c denotes the child of n in current clique. cl and cr are the left and right sibling of node c. f denotes the parent node of n, ff denotes grandfather of n.

out s_i_1 (s_n_1) or i-1 For second layer, s_i_0 (s_n_0) is replaced by s_i_1 (s_n_1). p(X,c) excluding true are appended by s_i_0 (s_n_0). For true value, when q is ab s_ _1 (s_c_1), additional feature s_i_0 (s_n_0) is added to p(X,c).

4 Experiments and Results

4.1 Experimental Settings

tion is widely used in 3 Chinese lexical sample ion at sememe level is Sememe (HowNet) based disambigua Chinese WSD such as Senseval task. But full text disambiguat scarcely considered. Furthermore, the full text corpus tagged with WordNet like thesaurus is not publicly available. The sentences used in our experiments are from Chinese Linguistic Data Consortium (http://www.chineseldc.org) that contains phrase structure syntactic trees. We can generate gold standard dependency trees using head rules. We selected some dependency trees and hand tagged senses on them with over 7,000 words for training and over 1,600 words for testing. There are two taggers to tag the corpus and an adjudicator to decide the tagging results. The agreement figure is the ratio of matches to the total number of annotations, and the figure is 0.88. This corpus is included in ChineseLDC.

predicts word senses according to the most equ For comparison, we build a base-line system and duplicate Wong and Yang's method [Wong et al., 2002]. The base-line system fr ent sense of the word in the training corpus. For words that do not appear in the training corpus, we choose the first sense entry in the HowNet dictionary. We also imitate Wong's method. Their method is at a word level. The sense of a word is the first sememe optionally combined with the second sememe. They defined this kind of word sense as categorical attribute (and also a semantic tag). Then an off-the-shelf POS tagger (MXPOST) is used to tag these senses.

sense "human| ". For those words that do not ve In our system, named entities have been mapped to predefined senses. For example, all person named entities have the ha entries in dictionary, we define their sense by referring to their synonyms that have entries. In the end, polysemous words take up about 1/3 of the corpus, and there are average 3.7 senses per polysemous word.

e mapped to some senses, recal In the following sections, precisions of polysemous words are used to measure the performance. Since all words have entries in dictionary or can b l is the same with precision. Note that for single layer sememe labeling, precision is the rate of correct sememes of the corresponding layer. Sense precision is the rate of correct senses, not sememes.

4.2 Results of MLCRF in WSD

repre hyperny plus hying DefSpace (ExD etter than sequentia s in trees are easie Table 2 shows the performance of MLCRF in WSD. "c" sents common features that presented in table 1 except m features. "+h" means common features pernym features. Def Seq ( ExDef Seq ) denotes sequential CRF using DefSpace (ExDefSpace). Def Tree ( ExDef Tree ) denotes tree CRF us efSpace). From table 2, we can see that tree CRF performs b l CRF, which shows that sense transition r to be captured than in sequences. Hypernym features enhance performance of tree CRF partly because it avoids sparse data problem, while it adds noise to sequential CRF. ExDefSpace performs similarly as DefSpace, which maybe due to our relatively small corpus.

In the test set, there are 203 different types of 502 polysemous words. Our best result correctly label 57 word senses that are labeled wrongly by baseline system. Of these p 57 olysemous words, there are 36 word types, of which 16 word types never occur in the training corpus. Although baseline system also wins our method a few words, totally our method improves 6.9% over baseline.

Our dependency trees are golden standard. We insist that parsing and WSD should not be processed in a pipe line mode. WSD is not the ultimate object of NLP. It has interplays with parsing, semantic role labeling etc. They can be integrated together if WSD can be fulfilled by globally modeling word senses. There are some methods like re-ranking and approximate parameter estimation that have the potential to solve that integrating.

perform better than Table 3 shows the comparisons between our system and (1) base-line system, (2) Wong and Yang's method. Both sequential CRF and tree CRF base-line system and Wong and Yang's method. The syntactic feature enhances performance significantly. Sequential CRF enhances little over base line partly because sense transitions in sequences are not easy to be captured. The performance of Wong and Yang's method is below base-line system, which maybe due to its simple features and sparse representation of all possible paths. That is, even POS features are not included in MXPOST and no syntactic features are used. Moreover, in MXPOST, only features that appear more than 4 times in the training corpus are included in the feature set. But candidate labels are all sememes. No special measures like DefSpace and ExDefSpace are taken. Then the feature set is very sparse to represent all possible paths even we duplicate training corpus 3 times.

5 Conclusion

In th transition by decomposing hen sense transition can be replaced . is paper, we probe into sense sense into sememes. T by sememe transitions

We model sememe transitions by MLCRF. For each layer sememe, sequential CRF and tree CRF are used. Multi-layered Viterbi algorithm is proposed at the predicting as ph e. Experiments show that MLCRF performs better than a base-line system and a max entropy model. Syntactic and hypernym features can enhance the performance significantly.

Acknowledgments

This work was supported by the Natural Sciences Foundation of China under grant No. 60372016, 60673042, and the Natural Science Foundation of Beijing under grant No. 4052027. Thanks for the helpful advices of Professor Zhendong Dong, the founder of HowNet.