UTIYAMA Masao Shinshu University 500 Wakasato, Nagano-si, Nagano 380 Japan
Abstract
A large scale multilingual ontology is necessary in order to support multilingual communication across the Internet by AI applications such as machine translation and multilingual informa- tion retrieval. To build such an ontology, align- ment of EDR Concept Classification Dictionary and WordNet has been attempted. An experi- ment shows that the two ontologies are very dif- ferent with respect to the distances among lex¬ ical entries. Another experiment on alignment of them based on a maximum weight match¬ ing algorithm shows that more than a half of the correspondences can be automatically rec¬ ognized even in highly ambiguous cases.
Introduction
1
The explosive spread of the Internet is fermenting a huge bunch of desire of people to communicate their ideas to each other. However, this desire is yet far from fully sat- isfied.  One major reason for this is language barrier.  For example, if your web pages are written in Japanese, it is unlikely that they acquire a huge readership around the globe. Another major reason in this connection is the lack of computational infrastructure to support transla¬ tion, retrieval, extraction, and so on. The GDA (Global Document Annotation) initiative attempts to solve these problems by:
tronic documents, and ● thereby having people annotate their electronic documents (mainly web pages) with the standard
HASIDA Kôiti Electrotechnical Laboratory 1-1-4, Umezono, Tukuba, Ibaraki 305 Japan Web authors will be motivated to annotate their pages if the annotated pages are translated, retrieved, and so on with a high accuracy and thus have greater chance to reach many, right kind of readers.  As a result, a huge amount of annotated data is expected to emerge, which will trigger further supply of tag-based AI appli- cations. Thus a positive feedback cycle will start turn- ing. Namely, when plenty of high-quality, low-cost tag- based AI applications are available for communication aid, many authors will be motivated to markup their web pages, and when plenty of tagged documents are out there, more competitive tag-based AI applications will be provided, and so on and so forth. Figure 1 should give a flavor of the tags to be proposed Figure 1: Annotated Text in GDA. A <seg> . . </seg> encodes parse tree brack- eting, and the property sem disambiguates polysemy of words. Note that these tags reduce the notorious am- biguities involved here, so that it is easy to automati- cally determine the underlying structure of the sentence by the present technology. The tags will also encode coreferences, scopes of logical/modal operators, rhetori- cal structure, social relationship between the author and the readers, and so on, in order to render documents machine-understandable to various degrees.  The GDA tagset will be designed by incorporating the results of TEI¹ , EAGLES², CES³, and so on, as much as possible. The GDA tagset and a tagging editor (a tool to support tagging) are currently under development. They will be
published in August 1997 at:
h ttp://www.etl.go.jp/etl/nl/GDA
for public review, discussion and experiments. GDA can be kicked off with a minimal tagset which captures just parse tree bracketing, for instance. Even such a simple tagset will no doubt dramatically im- prove the accuracy of machine translation, informa- tion retrieval, and so on. In order to maximally im- prove the quality of such GDA applications, however, tags should capture more detailed linguistic information, among which the most important will be lexical seman- tics. Tags should be rich enough to capture the linguistic semantics of various web pages in various languages. A large multilingual ontology is thus necessary after an ini- tial stage of GDA; It is desirable that the values of the sem attribute be based on such an ontology. In this connection, note that GDA does not only need such an ontology, but also promotes its development. That is, if the early stages of GDA prove useful even without sense tags, the development of a huge, sharable ontology will be strongly motivated in order to further improve the quality of GDA applications. The mainte- nance of the ontology will also be facilitated through the massive use of it by GDA applications. It is a hope of the authors that GDA should provide concrete objectives for which to promote international cooperations to develop a common multilingual ontology. The rest of the paper reports on some attempts toward developing a multilin- gual ontology for GDA by connecting various existing ontologies. A connection among different ontologies may be tight or loose. A tightly connected ontology is a unified ontol¬ ogy into which the source ontologies have been mapped so that concepts originating from different ontologies are either unified or related in the same way as those orig- inating from the same ontology are; Typically, the fact that one concept is a subset of another is reflected in the ontology in such a way that the former is a descen- dant node of the latter in the concept hierarchy.  On the other hand, a loosely connected ontology is one in which the source ontologies are more loosely aligned, the concept hierarchy failing to capture some set-theoretic relations among concepts from different ontologies. In such an ontology compiled from an English ontology and a Japanese ontology, "brother" in the English ontology might not be connected with “ani” (elder brother) in the Japanese ontology. High-quality, multilingual, tag-based applications would be easy to make if a tightly connected multilin- gual ontology were available. However, the development of such an ontology will require a huge cost of manual work. On the other hand, a loosely connected ontology may be automatically compiled by machines with rela- tively little human intervention. So such an ontology is much less expensive to build. GDA can smoothly move from a loosely connected ontology to a tightly connected one, because annota- tion using a loosely connected ontology will still be ef- fective under a tightly connected ontology as long as the former ontology is included in the latter. So tag- based applications presupposing a loosely connected on- tology can be adapted to a tightly coupled ontology with minimum modifications. Under these considera- tions, GDA attempts to first demonstrate the usefulness of tags even without ontologies, and then to develop a loosely connected ontology, showing how tag-based ap- plications based that ontology can aid multilingual com- munication efficiently, which will induce the motivation to develop a tightly connected ontology for more useful applications. As a first step to construct a loosely connected on- tology, the authors have examined the quantitative cor- respondences between two existing ontologies — EDR Concept Classification Dictionary [Yokoi, 1996] and WordNet [Miller, 1995] — and studied how to align them. What follows is a progress report on that.
2
Two Ontologies
2.1
EDR Concept Classification Dictionary
EDR concept classification Dictionary (hereafter EDR) is a bilingual ontology which contains a classification of concepts organized with respect to super-sub (is-a) re- lation.  A concept may refer to some English and/or Japanese words (and phrases) 4 and is associated with an English explanation and a Japanese explanation of its intuitive sense. Although EDR is a bilingual ontology, the Japanese part is not considered in the present paper because it is not needed to align EDR and WordNet.
2.2
WordNet
WordNet is an English ontology.  It organizes English words and phrases into synonym sets ("synsets"), each representing one underlying lexical concept. Synsets are linked with each other via relationships such as super- sub and antonym.  Approximately one half of the synsets have short English explanations of their intuitive sense. Concepts and synsets are equally regarded as sets of words (and phrases) in the rest of the paper.
3
Comparison between EDR and
WordNet
Two experiments were conducted to compare distances between words contained in the two ontologies. 4Some concepts do not refer to any words or phrases at all. The distance between two words in each ontology is defined as follows. First, the distance DE between two words w 1  and w 2  in EDR is defined as
where C(wi)(i = 1,2) is the set of concepts which con- tain wi and de (c 1 , c 2 ) is the length of the shortest path between two concepts c 1 and c 2 in EDR. Second, the distance Dw between two words w 1 and w 2 in WordNet is defined as
where S(wi)(i = 1,2) is the set of synsets which con- tain wi and dw (s1, s2) is the length of the shortest path between two synsets s 1 and s 2 in WordNet.
Comparison of WordNet Distance with
EDR Distance
The first experiment concerns the distances in WordNet between two words (of a common syntactic category) between which the distance in EDR is zero. The result is shown in Table 1. In the table, "Num. of pairs" is the number of pairs of words whose WordNet distances are Dw The table shows that the number of pairs decreases as DW increases. However, the decrease is not sharp. This implies that words which are close to each other in EDR are not necessarily close to each other in WordNet.
3.2
Comparison of EDR Distance with
WordNet  Distance
The second experiment examines the EDR distances be- tween two words (of a common syntactic category) whose WordNet distance is zero. The result is shown in Ta- ble 2. As before, "Num. of pairs" is the number of pairs of words whose WordNet distance is DE. The decrease in the number of pairs shown in Table 2 is sharper than that in Table 1. But the decrease is not very sharp, either, which implies that words which are close to each other in WordNet are not necessarily close to each other in EDR. 5
3.3
Remarks
Suppose that two words are far from each other in an ontology whereas they are close to each other in another. This gap arises in one of the following two cases. Case 1. The words are actually similar in meaning, but the former ontology fails to capture that similarity. Case 2. The words are actually dissimilar, but the lat- ter ontology incorrectly connects them via a short path. Case 1 occurs when the builder of the former ontology has overlooked some relations between the words.  On the other hand, Case 2 occurs when the builder of the latter ontology has assigned wrong relations between the words. It is likely that Case 1 occurs much more fre- quently than Case 2. In fact, this was the case in the above two experiments according to the first author's SULVEY. Alignment of ontologies will improve the accuracy of the resulting ontology in two ways. First, missing edges in one ontology may be supplied by another, correspond- ing to Case 1. Second, erroneous edges may be removed, corresponding to Case 1, though that would be harder than the first type of improvement.
Alignment of EDR and WordNet
4
If an EDR concept and a WordNet synset are equivalent, very probably they share a word. We can conceive of a bipartite graph G by regarding this relation of sharing a word as an edge connecting the two nodes (the EDR concept and the WordNet synset). G consists of four subgraphs, Gnoun, Gverb, Gadjective, and Gadverb, which correspond to the four syntactic categories in WordNet. Gcat (cat = noun, verb, adjective, adverb) is the bipar- tite graph (VEat, Vgat, Eeee,) where VEat (Vgat) is the set of EDR concepts (WordNet synsets) containing words categorized in cat, and EEW, is the set of edges connect- ing EDR concepts in VEat and WordNet synsets in Vfat. A small part of Gnoun is shown in Figure 2. In the figure, each box in the left column represents an EDR concept and contains the identifier of the concept (c 1 , c 2 , or c 3 ) and the words contained in the concept. Simi- larly, each box in the right column represents a WordNet Synset. Two experiments are reported in this section, one ex- amining G and the other attempting to align EDR and WordNet based on this examination.
Number of Connected Components
4.1
The first experiment examined sizes of connected com- ponents in G. The size of a connected component can be very large. In that case, an EDR concept may have many candidates for the corresponding WordNet synset so that deciding the corresponding synset correctly will be diffi- cult, and vice versa. There are large connected compo- nents mainly because of polysemous words. In Figure 2, for example, the polysemous word, “lime”, connects c2 to the semantically unrelated synsets, s 1 and s 3 , so that the connected component spreads.
3.1

The distribution of connected components (CCs) in G is shown in Table 3. In the table, |VE| and |VW| stand for the number of EDR concepts and WordNet synsets, respectively, in each connected component.  "x ~ y" means that the greater of |VE | and |VW | is in the range of x through y. The common syntactic category of the words in the connected component is shown in the table where “Num. of CCs” is one. Table 3 shows that most connected components are Such connected components can be manually small. checked by humans to validate the edges therein. To examine the largest four connected components in Ta- ble 3, however, some computational aid by machine is n ecessary.
4.2
Alignment by Maximum Weight
Matching Algorithm
The second experiment addresses an alignment of EDR concepts and WordNet synsets by extracting a one-to- one correspondence from G. A one-to-one correspondence between EDR concepts and WordNet synsets is represented by a set of edges in which no two edges have common concepts or synsets. Such a set is called a match on G . In Figure 2, for exam- ple, {{02, s 1}, {C3, s 3}} is a match. We should probably generalize the notion of a match to allow one-to-many and many-to-one (but maybe not many-to-many) corre- spondences between concepts and synsets. The present formulation is a simplification for the sake of quick com- putation. If each edge e in a match M has some real-number weight w(e), then w(M) = Σe ∈ M w(e) is called the weight of M. If w(M) is the greatest of all the weights of matches in G, then M is called the maximum weight match (MWM) in G.  Note that a match and a MWM can naturally be defined for subgraphs of G. For exam- ple, they can also be defined on the graph in Figure 2 which is a subgraph of G. Suppose that the edges in Figure 2 have an equal weight of one, then the MWM is M' = {{c1, s1}, {c2, s2}, {c3, s3}} and w(M') = 3. If M is the MWM in G, then M will give the best one- to-one correspondence between EDR and WordNet on the condition that each edge in G is given an appropriate weight. Let e = (c, s) be an edge where c is an EDR concept and s is a WordNet synset. Then the weight w(e) of e is defined by
where x is a word, and
See Section 3 for the definitions of dE and dW. In for- captures the similarity between E and mula (1).  Eu W W. Due to ∑ - log P(x), w(e) takes a greater value when rarer words are shared by c and s. The second experiment obtained the four MWMs listed in Table 4 for the four largest connected compo-
Table 3:  Number of connected components
Table 4: Connected components examined nents in Table 3. To examine the results, the edges in each MWM were first sorted in the decreasing order of the weights, and three parts (the top 30 edges, the middle 30 edges, and the last 30 edges) were extracted of each sorted list. Next, the correctness of the extracted edges were judged manually by the first author. The edges were classi- fied into three categories: "correct" "wrong" and "un¬ certain." The results of the judgments are shown in Table 5 In the tables, "range" means the range of through 8.
av. degree = 3.74 Table 5: Judgment on edges extracted from A
av . degree = 5.52 Table 6:  Judgment on edges extracted from B the weights of the extracted edges. “av. degree” is the average number of edges connected with an EDR concept or a WordNet synset in a connected component.
Table 7: Judgment on edges extracted from C
av. degree = 5.8 Table 8: Judgment on edges extracted from D Note that the accuracy of the top 30 edges are very This suggests that the weight defined by (1) is high. appropriate.  Next, over a half of the extracted edges are correct, though the connected components involve a lot of ambiguities, with the av. degree between 3.74 and 8.47. The authors are planning to improve the accu- racy by revising the weight calculation and taking into account other information in the source ontologies. It should also be studied what happens if the notion of a match is generalized to include one-to-many and many- to-one correspondences.  For the latter purpose, vari- ous graph algorithms will be useful as well as maximum weight matching algorithm is useful for extracting a one- to-one correspondence from G.
5
Related Works
EuroWordNet® and Penman, Pangloss Projects [Knight and Luk, 1994]7 also aim at building multilingual ontolo- gies. EuroWordNet addresses development of a multilin- gual ontology for four European languages. The ontol- ogy will be made from existing ontologies. The method proposed above may be useful for connecting those on- tologies.  A  work in  Penman,  Pangloss  Projects auto- 7http://www.isi.edu/natural-language/nlp-at-isi.html matically merge WordNet and Longman's Dictionary of Contemporary English. Their merging problem can also be regarded as a maximum weight matching problem (though they did not do so), which demonstrates the generality of the formulation proposed in this paper. [Ogino et al., 1997] attempt to manually align upper parts of EDR and WordNet. The bottom-up alignment reported above will be improved by incorporating their result.
Conclusion
6
The paper first discussed the role of a large scale multi- lingual ontology in Global Document Annotation. Next it compared the distances among words in EDR Concept Classification Dictionary and in WordNet. The compar- ison suggests that the two ontologies are not very simi- lar in encoded distances, and that alignment should im- prove the overall quality of the ontology. Finally, the pa- per reported on an attempt to align the two ontologies by maximum weight matching algorithm. The results of the alignment shows that over a half of the corre- spondences were correct even in highly ambiguous cases. Since the current method uses only small parts of the entire source ontologies, the alignment quality could be further improved by exploiting other information in the ontologies.