Experiments on applying relaxation labeling to map multilingual hierarchies

Exp eriments on Applying Relaxation Lab eling to Map Multilingua l Hierarchies. J. Daude, L. Padro & G. Rigau. Departament de Llenguatges i Sistemes Informatics. Universitat Politecnica de Catalunya. Barcelona. f daude,padro,g.rigau g @lsi.upc.es Abstract This pap er explores the automatic construction of a multilingual Lexical Knowledge Base from preexisting lexical resources. This pap er presents a new approach for linking already existing hierarchies. The Relaxation lab eling algorithm is used to select {among all the candidate connections prop osed by a bilingual dictionary{ the right conection for each no de in the taxonomy. 1 Intro duction There is no doubt ab out the increasing need of owning accurate and broad coverage general lexical/semantic resources for developing NL applications. Thus, one of the main issues in last years as regards NLP activities has b een fo cused on the fast development of generic language resources. These resources include lexicons, lexical databases ( ldb s), lexical knowledge bases ( lkb s), ontologies, etc. Sp ecial interest presents, for knowledge-based NLP tasks, the availabilityofwide coverage ontologies. Most known ontologies (suchas gum , cyc , Ontos , Microkosmos , edr or WordNet, see Go98] for an extensiv e survey) dier in great extenton several characteristics (e.g. broad coverage vs. domain sp ecic, lexically oriented vs. conceptually oriented, granularity, kind of information stored, kind of relations, way of b eing built, etc.). However, the success of WordNet has determined the emergence of several pro jects that aim the construction of WordNets for other languages than English (e.g., HF97, AMS97]) or to develop multilingual WordNets The most imp ortant pro ject in this line is EuroWordNet ( ewn ) PBR + 97]. The construction of a WN for a sp ecic language L g ( L g WN) can b e tackled in dierentways, dep ending on the lexical sources available. Of course the manual construction can b e undertaken quite straightforwardly and leads to the b est results in terms of accuracy BCE + 98], But this metho dology has the imp ortantdrawback of its cost. So, other approaches have b een carried out taking prot of available resources in fully automatic or semi-automatic ways. Basically four kinds of resources have b een used: 1 1. English WN ( En WN), as an initial skeleton for trying to attach the words from Lg language to it. 2. Already existing taxonomies of L g (b oth at word and at sense level), 3. Bilingual (English and L g )and 4. Monolingual L g dictionaries. All the approaches using En WN as skeleton are based on the assumption of a close conceptual similaritybetween English and L g ,in suchaway that most of the structure (relations) in En WN could b e maintained for L g WN. In the case of bilingual dictionaries the usual approach is to try to link the English counterpart of entries to synsets in En WN and to assume that the entry can b e linked to the same synset ACF + 97]. Monolingual dictionaries have b een used basically as a source for extracting taxonomic (hyp ernym) links b etween words (or senses BG92], RRA98]) and in lower extent for extracting other kinds of semantic relations Ric97] (e.g. meronymic links). Once a taxonomyof L g (already existing or built from a monolingual MRD )is available, the task can consist of 1) enriching the taxonomic structure with other semantic links (manually or automatically), as is the case of building individual WNs, or 2) merging this structure with other already existing ontologies (as En WN or EWN). Recently, several attempts have b een p erformed to pro duce multilingual ontologies. ACR + 94] use a Spanish/English bilingual dictionary for (semi)automatically linking Spanish and English taxonomies extracted from DGILE and LDOCE .In a similar approach, RRT95] prop ose an automatic approach for linking Spanish taxonomies extracted from DGILE to WordNet synsets. KL94] fo cus on the construction of Sensus, a large knowledge base for supp orting the Pangloss machine traslation system merging ontologies ( Ontos and Upp er Mo del) and WordNet with monolingual and bilingual MRD s. OH94] describ e (semi)automatic metho ds for asso ciating a Japanese lexicon to an English ontology using a bilingual dictionary. UH97] describ e several exp eriments aligning EDR and WordNet ontologies. ACF + 97]combine several lexical resources and techniques to map Spanish words from a bilingual dictionary to WordNet in order to build a parallel in structure semantic net. FRR98] prop ose also the use of the taxonomic structure derived form a monolingual MRD to aid this mapping pro cess. This pap er presents a novel approach for merging already existing hierarchies. The metho d has b een applied to attach substantial fragments of the Spanish taxonomy derived from DGILE (see RRA98]) to the English WordNet using a bilingual dictionary for connecting b oth hierarchies. Although we used the system for connecting two hierarchies of dierent languages, we are esp ecting b etter results when appliying the metho d on dierentversions of the same hierarchy (for instance, WN1.5 and WN1.6). Thus, using this metho dology,we are able to reuse lexical resources develop ed previously for older versions of the same hierarchy (as for instance, SemCor). 2 2 Application of Relaxation Lab elling to NLP This section discusses the the relaxation lab elling algorithm and its use to p erform NLP tasks. To enable the application of relaxation lab elling, the language mo del must b e describ ed in terms of algorithm elements {variables, lab els, constraints, etc.{. Although relaxation lab elling has b een mainly used in elds other than NLP (engineering, computer vision, . . . ), some researchers in optimization techniques PR94, PM94]have used POS tagging as a toy problem to exp eriment their methods to improve the p erformance of relaxation lab elling. They used a 1000-word test corpus, and only binary constraints, whichwas enough to their purp oses of testing a metho d for estimating constraint compatibilityvalues. From the NLP eld, the works byPad96, MP97, VP97,Pad98] constitute a reliable background to state that relaxation lab ellin g may b e a useful to ol for the NLP interests. We will describ e the relaxation lab elling algorithm from a general p ointofview in section 2.1. Afterwards, the way to use it to match taxonomies will b e describ ed. 2.1 Algorithm Description In this section the relaxation algorithm is describ ed from a general p oint of view. Let V = f v 1 v 2 :::v N g b e a set of variables. Let T i = f t i 1 t i 2 :::t i m i g b e the set of p ossible lab els for variable v i (where m i is the numb er of dierent lab els that are p ossible for v i ). Let C b e a set of constraints b etween the lab els of the variables. Each constraint is a \compatibilityvalue" for a combination of pairs variable{lab el. For instance, the constraint 0 : 53 ( v 1 A )( v 3 B )] states that the combination of variable v 1 having lab el A , and variable v 3 having lab el B has a compatibilityvalue of 0 : 53. Constraints can b e of any order, so we can dene the compatibilityvalue for combinations of anynumber of variables (obviously we can have combinations of at most N variables). The aim of the algorithm is to nd a weightedlabel ling such that global consistency is maximized. A weightedlabel ling isaweight assignation for each p ossible lab el of eachvariable: P =( p 1 p 2 :::p N ) where each p i is a vector containing a weight for each p ossible lab el of v i , that is: p i =( p i 1 p i 2 :::p i m i ) Since relaxation is an iterative pro cess, when the time step is relevant, we will note the weight for lab el j of variable i at time n as p i j ( n ). When the time step is not relevant, we will note it as p i j . Maximizing global consistency is dened as maximizing for eachvariable v i ,(1  i  N ), the average supp ort for that variable, which is dened as the weighted sum 3 of the supp ort received by each of its p ossible lab els, that is: m i X j =1 p i j  S ij where p i j is the weight for lab el j of variable v i and S ij is the supp ort received by that pair from the context. The supp ort for the pair variable{lab el expresses how compatible that pair is with the lab els of neighb ouring variables, according to the constraint set. The p erformed global consistency maximization is a vector optimization. It do es not maximize {as one might think{ the sum of the supp orts of all variables. It nds aweighted lab elling such that any other choice would not increase the supp ort for any variable given {of course{ that such a lab elling exists. If such a lab elling do es not exist, the algorithm will end in a lo cal maximum. The relaxation algorithm consists of:  start in a random lab elling P 0 .  for eachvariable, compute the \supp ort" that each lab el receives from the currentweights for the lab els of the other variables (i.e. see how compatible is the currentweighting with the currentweightings of the other variables, given the set of constraints).  Up date the weigh tofeachvariable lab el according to the supp ort obtained by each of them (that is, increase weight for lab els with high supp ort, and decrease weight for those with low supp ort).  iterate the pro cess until a convergence criterion is met. The supp ort computing and weightchanging must b e p erformed in parallel, to avoid that changing a weight for a lab el would aect the supp ort computation of the others. We could summarize this algorithm saying that at each time step, a variable changes its lab el weights dep ending on how compatible is that lab el with the lab els of the other variables at that time step. If the constraints are consistent, this pro cess converges to a state where eachvariable has weight 1 for one of its lab els and weight 0 for all the others. Note that the global consistency idea {dened as the maximization of the average supp ort received byeachvariable from the context{ makes the algorithm robust, since the problem of having mutually incompatible constraints (so one can not nd a combination of lab el assignations which satises all the constraints) is solved b ecause relaxation do es not (necessarily) nd an exclusivecombination of lab els, that is, an unique lab el for eachvariable, but a weight for each p ossible lab el such that consistency is maximized (the constraints are satised to the maximum p ossible degree). Advantages of the algorithm are: 4  Its highly lo cal character (eachvariable can compute its new lab el weights given only the state at previous time step). This makes the algorithm highly parallelizable (we could have a pro cessor to compute the new lab el weights for eachvariable, or even a pro cessor to compute the weightforeach lab el of each variable).  Its expressiveness, since we state the problem in terms of constraints b etween variable lab els.  Its exibili ty,wedonothavetocheck absolute consistency of constraints.  Its robustness, since it can give an answer to problems without an exact solution (incompatible constraints, insucient data, . . . )  Its ability to nd lo cally optimal solutions to NP problems in a non-exp onential time (Only if wehave an upp er b ound for the numb er of iterations, i.e. convergence is fast or the algorithm is stopp ed after a xed numb er of iterations). Drawbacks of the algorithm are:  Its cost. Being N the number of variables, v the average numb er of p ossible labels per variable, c the average numb er of constraints p er lab el, and I the average numb er of iterations until conv ergence, the average cost is N  v  c  I , that is, it dep ends linearly on N , but for a problem with many lab els and constraints,orifconvergence is not quickly achieved, the multiplying terms mightbe much bigger than N .  Since it acts as an approximation of gradient step algorithms, it has their typical convergence problems: Found optima are lo cal, and convergence is not guaranteed, since the chosen step might b e to o large for the function to optimize.  In general, constraints must b e written manually, since they are the mo delling of the problem. This is go o d for easy-to-mo del domains or reduced constraintset problems, but in the case of POS tagging or WSD constraint are to o many and to o complicated to b e written by hand.  The diculty to state whichisthe compatibility value for each constraint. If we deal with combinatorial problems with an exact solution (e.g. travelling salesman), the constraints will b e all fully compatible (e.g. stating that it is p ossible to go to anycityfromany other) or fully incompatible (e.g. stating that it is not p ossible to b e twice in the same city). But if we try to mo del more sophisticated or less exact problems (such as POS tagging) things will not b e blackorwhite. We will have to assign a compatibilityvalue to each constraint.  The dicultytocho ose the supp ort and up dating functions more suitable for each particular problem. 2.1.1 Supp ort F unction The relaxation lab elling algorithm requires a way to compute which is the supp ort foravariable lab el given the constraints and the current lab el weights for the other 5 variables. This is called the support function and it is the heart of the algorithm, since it is closely related to what will b e maximized. To dene the supp ort received byavariable lab el from its context, wehaveto combine the individual inuences of each constraint that can b e applied for that pair in the current context. So, we will dene Inf ( rij ) as the inuence of a constraint r on lab el j for variable i . Its formal denition requires some previous steps: DEF: Constraint. A constraint r consists of a compatibilityvalue C r and its asso ciated set of pairs variable{lab el. The compatibilityvalues can b e restricted to a certain interval (e.g. 0  1],  ; 1  1], 0  + 1 ] . . . ), or not restricted at all. A constraint expresses a how compatible is a given combination of variable lab els. It can b e written as follows: C r ( v i 1 t i 1 j 1 ) ::: ( v i n r t i n r j n r )] where 1  i 1 :::i n r  N and 1  j k  m i k for k =1 :::n r where n r is the constraint degree , that is, the numb er of pairs variable{lab el it involves, and ( v i 1 t i 1 j 1 ) ::: ( v i n r t i n r j n r ) are the pairs involved in the constraint. For simplicitywe will note lab el j for variable i as t j instead of t i j , since the variable i which the lab el is applied to is already present in the pair. The previous constraint will then b e expressed as: C r ( v i 1 t j 1 ) ::: ( v i n r t j n r )] DEF: Context weight .Obviously, the inuence of a constraintonagiven variable lab el is zero if the constraint do es not include the pair variable{lab el. (i.e. that constraint is not applied). Then, constraints that have an inuence on a given pair ( v i t j ) are only those that include that pair, i.e., those of the form: C r ( v i 1 t j 1 ) ::: ( v i t j ) ::: ( v i n r t j n r )] We dene the context weight for a constraint and a pair variable{lab el W ( rij ) as the pro duct of the currentweights for the lab els app earing in the constraint except ( v i t j ), or, if preferred, as though the weight for that lab el was 1. The context weight states how applicable the constraintis given the currentcontext of ( v i t j ). The constraint compatibility value C r states how compatible the pair is with the context. Being p s q ( n ) the weight assigned to lab el t q for variable v s at time n , the context weight is: W ( rij )= p i 1 j 1 ( n )  :::  p i n r j n r ( n ) where p i j ( n ) is not included in the pro duct. 6 DEF: Constraint Inuence. Once wehave dened the constraint compatibility values and the context weight, we can dene the inuence of a constraint on the pair ( v i t j )as: Inf ( rij )= C r  W ( rij ) DEF: Support. Once wehave computed the inuence for each constrainton the given lab el of a variable, we can compute the total supp ort received by that lab el combining the inuences of all constraints. Several supp ort functions are used in the literature, dep ending on the problem addressed, to dene the supp ort S ij received by lab el j of variable i . Dierent supp ort functions corresp ond to dierentways of combining constraint inuences. See KF86] for further details on dierent p ossible supp ort functions. In our case, we will b e using the following formula, which computes the supp ort for a lab el adding the inuences obtained from each constraints. Dep ending on the nature of the compatibilityvalues, supp ort values maybe negative indicating incompatibility . S ij = X r Inf ( rij ) (1) 2.1.2 Up dating Function The algorithm also needs to compute which is the new weightfora variable lab el, and this computation must b e done in suchaway that it can b e proven to meet a certain convergence criterion, at least under appropriate conditions 1 ZKH78, ZLM81,HZ83]. This is called the updating function and it is used to compute and normalize the new weights for each p ossible lab el. Several formulas have b een prop osed RHZ76], and some of them havebeen proven to b e approximations of a gradient step algorithm. The up dating formulas must increase the weight asso ciated with lab els with a higher supp ort, and decrease those of lab els with lower supp ort. This is achieved bymultiplying the currentweightofalabel by a factor dep ending on the supp ort received by that lab el. Normalization is p erformed in order that the weights for all the lab els of a variable add up to one. For the application describ edin this pap er, we will b e using the following up dating function, which increases the weight for a lab el when S ij is p ositive and decreases it when S ij is negative. Values for S ij must b e in  ; 1  1]. p i j ( n +1) = p i j ( n )  (1 + S ij ) m i X k =1 p i k ( n )  (1 + S ik ) (2) Since the supp ort values S ij are computed using the constraint compatibility values C r , whichmaybe unb ounded, they do not necessarily b elong to the intervals 1 Convergence has b een proven under certain conditions, but in a complex application suchasPOS tagging we will nd cases where it is not necessarily achieved. 7 required byany of the ab ove up dating functions. Even in the case that the C r were b ounded, if the supp ort computation used is additive (such as 1), the nal supp ort result can not b e guaranteed to b e in the required interval. Thus, it will b e necessary to normalize the nal supp ort value for each lab el, in order to t in the appropriate interval. See KI85,Tor89] for clear exp ositions of what is relaxation lab ellin g and what kinds of relaxation can wegetbycombining dierent supp ort and up dating functions. 2.1.3 Convergence and Stopping Criteria Relaxation lab ellin g is an iterative algorithm which has b een proven to converge under certain conditions ZKH78, ZLM81, HZ83]. These conditions often require simple mo dels {e.g. consisting only on binary constraints whichmust b e symmetric{ which are not likely to hold in complex applications such as those of NLP. In addition, relaxation algorithms are often stopp ed b efore convergence, since they either pro duce b etter results at early iterations RLS81, Llo83] or it is not necessary to wait until convergence to know what the result will b e ZLM81]. Dierent stopping criteria can b e found in the literature, although most of them have a strong adhoc avour ER78,Pel79]. Har83] presents a conditional probabilityinterpretation of relaxation lab elling which enables a theoretically grounded stopping criterion, unfortunately, it is only applicable in sp ecic cases (binary constraints only, with b ounded weight sum for all constraints aecting the same variable). 2.2 Application to taxonomymatching As describ ed in previous sections, the problem we are dealing with is to matchtwo (p ossibly non{fully{connected) taxonomies. That is:  Wehave a Spanish taxonomy (which, in our case, was automatically extracted from a monolingual dictionary RRA98]). It is not fully connected {it can b e seen as a set of smaller taxonomies{, and it is a a word taxonomy {there are no conceptual classications suchas concept , sense or synset .  Wehave a conceptual taxonomy(e.g. WordNet), in which the no des represent ideas suchas concepts , senses or synsets .  Wewant to relate b oth taxonomies in order to have a semantic assignation to each word {no de of the Spanish taxonomy. We will try to achieve our goal by using the relaxation lab elling algorithm to assing to each Spanish word a no de in the conceptual taxonomy(WordNet in our case). The mo delling of the problem is the following:  Eachword in the Spanish taxonomyis a variable for the relaxation problem.  The p ossible values of that variable, are all the WN synsets whichcontain a word that is a p ossible translation of the Spanish word. Thus, we will need a bilingual dictionary to know all the p ossible translations for a given word. 8  The relaxation algorithm will select one lab el for eachvariable, that is, one synset for each Spanish word. In that way,we will have the conceptual assignation for our Spanish taxonomy.  The algorithm will need constraints stating when a synset is or is not a suitable assignment foraword. These constraints will rely on the taxonomy structure (e.g., a synset S 1 may b e selected for a word W 1 if that word has a hyp eronym W 2 in the Spanish taxonomy whichmay b e (or is) assigned to a synset S 2 that is in turn hyp ernonym of S 1 ). More detail on the used constraints is given in section 3. 3 The Constraints Constraint are used in relaxation lab eling to increase or decrease the weight for a variable lab el. In our application, eachword in the Spanish taxonomyis a variable, and each of its p ossible connections to a WordNet sysnet is a lab el. In this way, constraints increase the weights for the connections b etween a no de in the Spanish taxonomyand a WordNet synset. Increasing the weight for a connection implies decreasing the weights for all the other p ossible connections for the same no de. To increase the weight for a connection b etween a Spanish taxonomynode ( N s ) and a WordNet synset ( N e ), we lo ok for already connected no des that have the same relationships in b oth taxonomies. For instance, that N s has an hyp onim H s in the Spanish taxonomy and N e has an hyp onim H e in WordNet, such that H s is connected to H e . C1 C2 C3 C4 C5 C6 Figure 1: Example of connections b etween taxonomies. Although there is a wide range of relationships b etween WordNet no des which can b e used to bulid constraints, wehave fo cused on the hyp er/hyp onym relationships. That is, we increase the weight for a connection when the involved no des have hyp eronyms (hyp onyms) also connected. Weconsiderhyp er/hyp onim relationships either directly or indirectly (i.e. ancestors or descendants), dep ending on the kind of constraint used. 9 animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > ) 0.003 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.996 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 The b ehaviour here is the same that wewould obtain with constraint iio if there were no intermediate no des. 3.7 aib constraint This constraint increases the weight for the connections in which an ancestor of the Spanish word is connected to the immediate hyp eronym of the WN synset and a descendant of the Spanish word is connected to an immediate hyp onym of the WN synset. Its graphical representation is shown in gure 7. Figure 7: aib constraint. The results for the example in this case are: animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 vertebrado = ) (00854210 animal < vertebrate > )1.0 16 oviparo = ) ave= ) (00884285 animal < bird > ) 0.999 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 The algorithm mo dies here the connections for ave , assigning the right synset. 3.8 Combining aie , aio and aib . If we use constraints aie , aio and aib simultaneously, in additivecombination, b e obtain the results presented b elow. Note that in this case we apply either a hyp eronym constraint, either a hyp onym constraint or either b oth of them. In the last case, the joint constraint is also applied. This means than connections with matching hyp eronym and hyp onym will have their weights doubly increased. animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > ) 0.998 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.001 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.000 = ) (04893480 food < pheasant > )1.0 rapaz = ) (00980561 animal < bird of prey,raptor,... > )1.0 = ) (05971784 person < cub,lad,... > ) 0.000 = ) (05992182 person < chap,fellow,... > ) 0.000 = ) (06110874 person < lass,young girl,... > ) 0.000 All connections suer weight mo dication except animal . Again, faisan gets the wrong connection assignment. 17 3.9 iae constraint This constraint increases the weight for the connections in which the immediate hyp eronym of the Spanish word is connected to an ancestor of the WN synset. Its graphical representation is shown in gure 8. Figure 8: iae constraint. The results obtained with this constraint are the following: animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 ave = ) (00884285 animal < bird > ) 0.98 = ) (01146542 animal < fowl,p oultry,... > ) 0.02 = ) (03073246 artifact < bird,shuttle,... > ) 0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 faisan = ) (01158294 animal < pheasant > )1.0 = ) (04893480 food < pheasant > ) 0.000 rapaz = ) (00980561 animal < bird of prey,raptor,... > )1.0 = ) (05971784 person < cub,lad,... > ) 0.000 = ) (05992182 person < chap,fellow,... > ) 0.000 = ) (06110874 person < lass,young girl,... > ) 0.000 In this case the weights for connections for words faisan and rapaz yield the correct assignment, since the constraint has b een applied to the word ave and its hyp ernonym animal ,even when there are twointermediate no des b etween (00008030 Tops < animal,animate b eing,... > ) and (00884285 animal < bird > )inWordNet. 3.10 iao constraint This constraint increases the weight for the connections in which an immediate hyponym of the Spanish word is connected to a descendant of the WN synset. Its graphical representation is shown in gure 9. animal = ) (00008030 Tops < animal,animate b eing,... > )1.0 = ) (05957021 person < b east,brute,... > ) 0.000 = ) (06061413 person < dunce,blo ckhead,... > ) 0.000 ave = ) (00884285 animal < bird > ) 0.995 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 18 Figure 9: iao constraint. = ) (03073246 artifact < bird,shuttle,... > ) 0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.005 = ) (06035118 person < dame,doll,... > ) 0.000 faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 In this case the constraint is also applied to animal , though there are two no des in WN b etween (00008030 Tops < animal,animate b eing,... > ) and (00884285 animal < bird > ). The constraint recurses downwards WordNet searching for connected descendants. The weight assignmentfor animal and ave select the right connection. In the case of ave , despite the word faisan has a nearer connected descendantfor food than for animal ,the animal sense is chosen b ecause of the contribution of rapaz . 3.11 iab constraint This constraint increases the weight for the connections in which the immediate hyp eronym of the Spanish word is connected to an ancestor of the WN synset and an immediate hyp onym of the Spanish word is connected to a descendant of the WN synset. Its graphical representation is presented in gure 10. Figure 10: iab constraint. The obtained results are: 19 animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 ave = ) (00884285 animal < bird > ) 0.999 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > ) 0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 The constraint pro duces a rightweight assignment for ave ,combining the constraints for animal { faisan ( animal ), and for animal { rapaz ( animal ) 3.12 Combining iae , iao and iab Using simultaneously constraints iae , iao and iab we obtain the results presented b elow. As in section 3.8, the combination pro duces a stronger evidence when b oth connected hyp eronym and hyp onym are found. animal = ) (00008030 Tops < animal,animate b eing,... > )1.0 = ) (05957021 person < b east,brute,... > ) 0.000 = ) (06061413 person < dunce,blo ckhead,... > ) 0.000 ave = ) (00884285 animal < bird > ) 0.999 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > ) 0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 faisan = ) (01158294 animal < pheasant > )0.999 = ) (04893480 food < pheasant > ) 0.000 rapaz = ) (00980561 animal < bird of prey,raptor,... > )1.0 = ) (05971784 person < cub,lad,... > ) 0.000 = ) (05992182 person < chap,fellow,... > ) 0.000 = ) (06110874 person < lass,young girl,... > ) 0.000 In this example, all the selected connections are the right ones. 3.13 aae constraint This constraint increases the weight for the connections in which an ancestor of the Spanish word is connected to an ancestor of the WN synset. Its graphical representation is presented in gure 11. 20 Figure 11: aae constraint. The constraint aects all no des that haveahyp onym. The results obtained applying this constraint are the following: animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > )0.98 = ) (01146542 animal < fowl,p oultry,... > )0.02 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )1.0 = ) (04893480 food < pheasant > ) 0.000 rapaz = ) (00980561 animal < bird of prey,raptor,... > )1.0 = ) (05971784 person < cub,lad,... > ) 0.000 = ) (05992182 person < chap,fellow,... > ) 0.000 = ) (06110874 person < lass,young girl,... > ) 0.000 3.14 aao constraint This constraint increases the weight for the connections in which a descendantof the Spanish word is connected to a descendant of the WN synset. Its graphical representation is presentedingure12. Figure 12: aao constraint. The constraint aects all no des that havea hyp onym. The results pro duced by the application of this constraint are: 21 animal = ) (00008030 Tops < animal,animate b eing,... > )1.0 = ) (05957021 person < b east,brute,... > ) 0.000 = ) (06061413 person < dunce,blo ckhead,... > ) 0.000 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > ) 0.995 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.005 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 3.15 aab constraint This constraint increases the weight for the connections in which an ancestor of the Spanish word is connected to an ancestor of the WN synset and a descendantof the Spanish word is connected to a descendant of the WN synset. Its graphical representation is presentedingure13. Figure 13: aab constraint. The obtained results are: animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.368 = ) (05957021 person < b east,brute,... > ) 0.264 = ) (06061413 person < dunce,blo ckhead,... > ) 0.368 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > ) 0.999 = ) (01146542 animal < fowl,p oultry,... > ) 0.000 22 = ) (03073246 artifact < bird,shuttle,... > )0.000 = ) (04891638 food < fowl,p oultry,... > ) 0.000 = ) (06035118 person < dame,doll,... > ) 0.000 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.5 = ) (04893480 food < pheasant > )0.5 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.291 = ) (05971784 person < cub,lad,... > ) 0.209 = ) (05992182 person < chap,fellow,... > ) 0.209 = ) (06110874 person < lass,young girl,... > ) 0.291 The only aected no de is ave , since it is the only no de with connected ancestor and descendant. 3.16 Combining aae , aao and aab If we apply, as in previous cases, the combination of constraint aae , aao and aab , we obtain: animal = ) (00008030 Tops < animal,animate b eing,... > ) 0.949 = ) (05957021 person < b east,brute,... > ) 0.021 = ) (06061413 person < dunce,blo ckhead,... > ) 0.029 vertebrado = ) (00854210 animal < vertebrate > )1.0 oviparo = ) ave= ) (00884285 animal < bird > ) 0.873 = ) (01146542 animal < fowl,p oultry,... > ) 0.040 = ) (03073246 artifact < bird,shuttle,... > )0.027 = ) (04891638 food < fowl,p oultry,... > ) 0.032 = ) (06035118 person < dame,doll,... > ) 0.027 ave mediana = ) faisan = ) (01158294 animal < pheasant > )0.946 = ) (04893480 food < pheasant > ) 0.054 rapaz = ) (00980561 animal < bird of prey,raptor,... > )0.929 = ) (05971784 person < cub,lad,... > ) 0.020 = ) (05992182 person < chap,fellow,... > ) 0.020 = ) (06110874 person < lass,young girl,... > ) 0.029 The pro cess afects now all no des, since any no de has either a connected ascendant or a connected descendant. 3.17 Relationships b etween constraints Some of the presented constraints are particular cases of others. For instance, constraint aie checks whether any ascendant in the Spanish taxonomy is connected to the immediate hyp eronym in WordNet. The search is p erformed upwards, and stopp ed when the rst match is found. The rst matching ascendant could b e the immediate 23 hyp eronym in the Spanish taxonomy, which is what iie constraintchecks. Thus, iie is a particular case of aie . Analogous reasonings yield that iie is also a particular case of iae .Both aie and iae are particular cases of aae .Thus, wehave the constraint relationships presented in gure 14. IIE AIE AAE IAE Figure 14: Particular{general relationships among hyp eronym constraints. For the constraints aecting hyp onyms, we obtain the relationships in gure 15. For those aecting b oth hyp eronyms and hyp onyms we obtain the relationships in gure 16 IIO AIO AAO IAO Figure 15: Particular{general relationships among hyp onym constraints. IIB AIB AAB IAB Figure 16: Particular{general relationships among hyp eronym/hyp onym constraints. 3.18 Grouping Constraints There are constraints that work b etter combined with others. For instance, the constraint iio is only applied to no des that have connected hyp onyms. Then, leaf no des {whichhavenohyp onym at all{ will never b e aected by that constraint. Simmetrically, constraint iie only aects no des whichhavehyp eronyms, and thus will never mo dify top no des in the taxonomy.Combining them b oth, every no de in the taxonomy can b e aected by at least one of the constraints. We can reinforce the eect on no des having b oth a hyp eronym and a hyp onym, intro ducing also the constraint iib in the pack {as describ ed in section 3.8{. We will name this pack ii . In the same way,we can group aie , aio and aib in a packnamed ai , iae , iao and iab in ia , and nally aae , aao and aab in aa . The particular{general relationships of the individual constraints are also valid for the packs, as shown in gure 17. 24 AA II AI IA Figure 17: Particular{general relationships among constraint classes. 3.19 Weights for Constraints When using a constraint alone, any p ositivevalue is adecuate for the compatibility value expressed by the constraint, since all applications will have the same strengh. But when we use several constraints at the same time, it b ecomes necessary to give each one an appropriate compatibilityvalue, according to our needs. For instance, when we use simultaneously iie and iio , the later constraint increases the weight for the connection b etween no des with connected hyp onyms. Given that the hierarchical structure of WN is {in most cases{ tree-like, we will consider the evidence supplied by a common hyp onym as 1 and use this value as the compatibilityvalue for constraint iio . On the other hand, constraint iie increases the weight for the connection b etween no des with connected hyp eronyms. It seems logical that the evidence supplied bya connected hyp eronym is smaller than that supplied by a connected hyp onym, since all siblings have a common hyp eronym without b eing necessarily the same no de. Since WN1.5 has 4.54 hyp onyms p er sysnet in average, we can assume that the evidence supplied by a connected hyp eronym is 1 4 : 52  0 : 22, and use this value as the compatibilityvalue for iie . When weusesimultaneously iie , iio and iib (pack ii ), we can use the same compatibilityvalues for iie (0.22) and iio (1). We will cho ose the compatibility value for iib according to the following criteria:  The supp ort for a connection provided by a constraint is the compatibilityvalue for the constraintmultiplied by the weights for the connections intervening in it (see section 2.1.1). Let n be the average numb er of candidate connections p er word. Then, the average weight for a connection is 1 n and thus the average supp ort contribution from constraint iie is 0 : 22  1 n . In the same way, the average supp ort from iio is 1  1 n . Being x the compatibilityvalue for constraint iib ,wehave that its supp ort should b e x  1 n 2 {since there wearecombining two connections (a hyp onym and a hyp eronym) with a weightof 1 n each.  It should b e larger than the combination of the other two, since it is more informativetohavesimultaneously connected hyp eronym and hyp onym, than having one of each separately.Thus, the supp ort provided by this constraint should b e larger than the supp ort provided by the other two toghether. The combined supp ort for a disjunction is the addition, i.e. (1 + 0 : 22)  1 n . Thus, to nd a value for x that satises these conditions, wemust solvethe 25 A Coverage gures Bilingual dict. Taxonomy ii ai ia aa original 67 (19%) 67 (19%) 172 (49%) 177 (50%) vox +top 74 (21%) 75 (21%) 203 (58%) 253 (72%) essential only-top 12 (15%) 12 (15%) 60 (77%) 63 (81%) no-senses 59 (20%) 59 (20%) 156 (53%) 161 (54%) original 134 (23%) 135 (23%) 357 (62%) 365 (63%) Multisource +top 138 (24%) 143 (25%) 375 (65%) 454 (78%) only-top 17 (14%) 18 (15%) 100 (82%) 106 (87%) no-senses 118 (23%) 119 (20%) 311 (61%) 319 (62%) Table 8: Coverage for noun.animal . Bilingual dict. Taxonomy ii ai ia aa original 57 (27%) 66 (31%) 82 (38%) 92 (43%) vox +top 61 (29%) 70 (33%) 117 (55%) 156 (73%) essential only-top 4 (36%) 4 (36%) 6 (55%) 6 (55%) no-senses 46 (27%) 54 (32%) 70 (41%) 78 (46%) original 119 (36%) 130 (39%) 164 (49%) 180 (54%) Multisource +top 134 (40%) 158 (47%) 194 (58%) 259 (73%) only-top 6 (40%) 6 (40%) 12 (80%) 13 (87%) no-senses 102 (36%) 111 (39%) 143 (51%) 156 (55%) Table 9: Coverage for noun.food . 32 Bilingual dict. Taxonomy ii ai ia aa original 124 (29%) 131 (30%) 208 (48%) 221 (51%) vox +top 130 (30%) 145 (34%) 264 (61%) 375 (87%) essential only-top 4 (16%) 4 (16%) 18 (72%) 19 (76%) no-senses 109 (31%) 115 (33%) 175 (50%) 186 (53%) original 225 (37%) 230 (38%) 360 (60%) 373 (62%) Multisource +top 230 (38%) 240 (40%) 395 (65%) 509 (84%) only-top 7 (20%) 7 (20%) 25 (71%) 26 (74%) no-senses 192 (37%) 197 (38%) 306 (59%) 318 (61%) Table 10: Coverage for noun.cognition . Bilingual dict. Taxonomy ii ai ia aa original 260 (28%) 273 (29%) 391 (41%) 406 (43%) vox +top 292 (31%) 337 (36%) 481 (51%) 782 (83%) essential only-top 4 (50%) 4 (50%) 8(100%) 8(100%) no-senses 230 (29%) 243 (30%) 338 (42%) 353 (44%) original 552 (43%) 577 (45%) 737 (57%) 760 (59%) Multisource +top 589 (46%) 697 (54%) 802 (62%) 1136 (88%) only-top 7 (78%) 7 (78%) 9(100%) 9(100%) no-senses 485 (43%) 509 (45%) 645 (57%) 668 (59%) Table 11: Coverage for noun.communication . References ACF + 97] J. Atserias, S. Climent, X. Farreres, G. Rigau, and H. Ro dr guez. Combining Multiple Metho ds for the Automatic Construction of Multilingual WordNets. In proceedings of International Conferenceon Recent Advances in Natural Language Processing (RANLP'97) , Tzigov Chark, Bulgaria, 1997. ACR + 94] A. Ageno, I. Castellon, F. Ribas, G. Rigau, H. Ro dr guez, and A. Samiotou. TGE: Tlink Generation Environment. In Proceedings of the 15th International Conference on Computational Linguistics (COLING'94) ,Kyoto, Japan, 1994. AMS97] A. Artale, B. Magnini, and C. Strapparava. Lexical Discrimination with the Italian Version of WordNet. In Proceedings of ACL Workshop Automatic Information Extraction and Building of Lexical Semantic Resources , Madrid. Spain, 1997. BCE + 98] L. Ben tez, S. Cervell, G. Escudero, M. Lop ez, G. Rigau, and M. Taule. Metho ds and To ols for Building the Catalan WordNet. In Proceedings 33 of ELRA Workshop on Language Resources for European Minority Languages , Granada, Spain, 1998. BG92] R. Bruce and L. Guthrie. Genus disambiguation: A study in weigthed preference. In Proceedings of the 14th International Conferenceon Computational Linguistics (COLING'92) , Nantes, France, 1992. ER78] J. O. Eklundh and A. Rosenfeld. Convergence Prop erties of Relaxation Lab elling. Technical Rep ort 701, Computer Science Center. Universityof Maryland, 1978. FRR98] X. Farreres, G. Rigau, and H. Ro dr guez. Using WordNet for Building WordNets. In Proceedings of COLING-ACL Workshop on Usage of WordNet in Natural Language Processing Systems ,Montreal, Canada, 1998. Go98] A. Gomez. J. Liebowitz (ed.). The Handbook of AppliedExpert Systems . CRC Press, 1998. Har83] R. M. Haralick. An interpretation for Probabilistic Relaxation. Computer Vision, Graphics & Image Processing , 22:388{395, 1983. HF97] B. Hamp and H. Feldweg. GermaNet - a Lexical-Semantic Net for German. In Proceedings of ACL Workshop on Automatic Information Extraction and Building of Lexical Semantic Resources , Madrid. Spain, 1997. HZ83] R. A. Hummel and S. W. Zucker. On the foundations of relaxation lab elling pro cesses. IEEE Transactions on Pattern Analysis and Machine Intel ligence , 5(3), 1983. KF86] J. Kittler and J. F!oglein. On Compatibility and Supp ort Functions in Probabilistic Relaxation. Computer Vision, Graphics & Image Processing , 34:257{267, 1986. KI85] J. Kittler and J. Illingworth. Relaxation Lab elling Algorithms - A Review. Image & Vision Computing , 3(4), 1985. KL94] K. Knight and S. Luk. Building a Large-Scale Knowledge Base for Machine Translation. In Proceedings of the American Association for Arti- cial Inteligence (AAAI'94) ,1994. Llo83] S. A. Lloyd. An optimization approach to relaxation lab ellin g algorithms. Image and Vision Computing , 1(2):85{91, 1983. MP97] Llu sM"arquez and Llu sPadro. A Flexible POS Tagger Using an Automatically Acquired Language Mo del. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics. Joint ACL/EACL , pages 238{245, Madrid, Spain, July 1997. OH94] A. Okumura and E. Hovy. Building japanese-english dictionary based on on tology for machine translation. In proceedings of ARPA Workshop on Human Language Technology , pages 236{241, 1994. Pad96] Llu sPadro. POS Tagging Using Relaxation Lab elling. In Proceedings of the 16th International Conference on Computational Linguistics, COLING , pages 877{882, Cop enhagen, Denmark, August 1996. 34 Pad98] Llu sPadro. A Hybrid Environment for Syntax{Semantic Tagging . Phd. Thesis, Dep. Llenguatges i Sistemes Inform"atics. Universitat Polit"ecnica de Catalunya, February 1998. http://www.lsi.up c.es/~padro. PBR + 97] P.Vossen P, L. Bloksma, H. Ro dr guez, S. Climent, A. Roventini, F. Bertagna, and A. Alonge. The EuroWordNet Base Concepts and TopOntology. Technical rep ort, Deliverable D017D034D036 EuroWordNet LE2-4003, 1997. Pel79] S. Peleg. Monitoring Relaxation Lab elling Algorithms Using Lab elling Evaluation. Technical Rep ort 842, Computer Vision Lab oratory.Computer Science Center, 1979. PM94] M. Pelillo and A. Maone. Using Simulated Annealing to Train Relaxation Lab elling Pro cesses. In Proceedings of ICANN '94 ,1994. PR94] M. Pelillo and M. Rece. Learning Compatibility Co ecients for Relaxation Lab eling Pro cesses. IEEE Transactions on Pattern Analysis and Machine Intel ligence , 16(9), 1994. RAA97] German Rigau, Jordi Atserias, and Eneko Agirre. Combining Unsup ervised Lexical Knowledge Metho ds for Word Sense Disambiguation. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics. Joint ACL/EACL , pages 48{55, Madrid, Spain, July 1997. RHZ76] R. Rosenfeld, R. Hummel, and S. Zucker. Scene lab elling by relaxation operations. IEEE Transactions on Systems, Man and Cybernetics , 6(6):420{ 433, 1976. Ric97] S. Richardson. Determining Similarity and Inferring Relations in a Lexical Know ledge Base . Phd. Thesis, The City University of New York, New York, NY, 1997. RLS81] J. Richards, D. Landgreb e, and P.Swain. On the accuracy of pixel relaxation lab elling. IEEE Transactions on Systems, Man and Cybernetics , 11(4):303{309, 1981. RRA98] G. Rigau, H. Ro dr guez, and E. Agirre. Building Accurate Semantic Taxonomies from MRDs. In Proceedings of COLING-ACL'98 ,Montreal, Canada, 1998. RRT95] G. Rigau, H. Ro dr guez, and J. Turmo. Automatically extracting Translation Links using a wide coverage semantic taxonomy. In proceedings 15th International Conference AI'95 ,Montp ellier, France, 1995. Tor89] C. Torras. Relaxation and Neural Learning: Points of Conv ergence and Divergence. Journal of Paral lel and Distributed Computing , 6:217{244, 1989. UH97] M. Utiyama and K. Hasida. Bottom-up AlignmentofOntologies. In Proceedings of IJCAI workshop on Ontologies and Multilingual NLP ,Nagoya, Japan, 1997. 35 VP97] Atro Voutilainen and Llu sPadro. Developing a Hybrid NP Parser. In Proceedings of the 5th Conference on AppliedNatural Language Processing, ANLP , pages 80{87, Washington DC, 1997. ACL. ZKH78] S. W. Zucker, E. V. Krishnamurty, and R. L. Haar. Relaxation pro cesses for scene lab elling: Convergence, sp eed and stability. IEEE Transactions on Systems, Man and Cybernetics , 8(1), 1978. ZLM81] S. W. Zucker, Y. G. Leclerc, and J. L. Mohammed. Continuous Relaxation and lo cal maxima selection: Conditions for equivalence. IEEE Transactions on Pattern Analysis and Machine Intel ligence , 3(2), 1981. 36