Microsoft Word - $ASQ84be92bb200836fc-41787c73-1030c38ec1f-7eb0#0 R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 1 of 24 Measuring the understanding between two agents through concept similarity Adolfo Guzman-Arenasm Jesus M. Olivares-Ceja Centro de Investigacion en Computacion (CIC), Instituto Politecnico Nacional, Mexico {a.guzman, jesuso}@acm.org SUMMARY. Two agents previously unknown to each other cannot communicate by ex- changing concepts (nodes of their own ontology): they need to use a common communica- tion language. If they do not use a standard protocol, most likely they use a natural lan- guage. The ambiguities of it, and the different concepts the agents possess, give rise to im- perfect understanding among them: How closely concepts in ontology OA map1 to which of OB? Can we measure these mismatches? Given a concept from ontology OA, a method is provided to find the most similar con- cept in OB, and to measure the similarity between both concepts. The paper also gives an algorithm to gauge du(A, B), the degree of understanding that agent A has about the ontol- ogy of B. The procedures use word comparison, since no agent (except the Very Wise Crea- ture, VWC) can measure du directly. Examples are given. KEY WORDS: Ontology matching, natural language, concept similarity, degree of under- standing, imperfect knowledge. 1. Introduction and objectives Agents A and B having to communicate with each other in order to achieve their goals, do so in one of two ways: (a) (Easier) Through a private language or protocol and naming convention, which requires prior agreement among programmers’ team or a Standards Committee; (b) (More general) Through a common popular general-purpose language, most likely a natural language. This paper addresses concept communication in the (b) setting. Two points stand: (1) Such communication can not be fulfilled through direct exchange of concepts belonging to an ontology, since A and B do not share the same ontology (they do not know exactly the same, from the same point of view), and OA and OB are in different address spaces. (2) Unlike case (a), the communication language is very often ambiguous. Together, (1) and (2) give rise to imperfect understanding (confusion). Knowledge is stored in concepts, which are mapped by the talker into words of the communication language; perceived words are internalized as concepts by the listener. If the concepts exchanged are animals and plants, Latin is fine: Felix Leo represents the con- 1 OA and OB are the ontologies of agents A (the talker or sender) and B (the listener), in the rest of the paper. 1 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 2 of 24 cept lion-león-loin2 while Canabis Indica stands for the concept marijuana. Other examples of words or symbols with a unique (universal) meaning: 4, π, Abelian group, Mexico, (23° 22’ 57”N, 100° 30’W), Abraham Lincoln, Berlin Symphony Orchestra. There are also semi-universal (popular) conventions, such as standard naming for chemical compounds; the Library of Congress Catalog for books, or the USA Social Security Num- ber; they provide non-ambiguity for those who adhere. If two agents can select a non- ambiguous language (each of its words maps exactly to one concept) or convention to ex- change concepts, great: they fall in case (a). If not, they have to settle for an ambiguous lan- guage, such as English [10], falling in case (b). When A talks to B, can either discover what produces the confusion? Is it possible to measure it? How can I be sure you understand me? Can I measure how much you under- stand me? Can you measure it? These questions have intrigued sociologists; they are also relevant to agents “not previously known to each other”3 trying to “interact with free-will”,4 for which they have to exchange knowledge. The paper provides answers to: (i) What is the most similar concept cB∈OB to concept cA∈OA? How similar is cB to cA? (ii) how much does B know about OA? If two agents do not share a concept, at least partially, they can not com- municate it or about it. Thus, a measure of the amount of understanding is the number of concepts they share, and how well they share them.5 We will sharpen these measures for both the ambiguous and the non ambiguous communication language. 1.1 Related work Huhns [12] seeks to communicate several agents sharing a single ontology. The authors have constructed [9, 10] agents communicating with previously unknown agents, so that not much a priori agreement between them is possible.3 An ancestor of our sim (§3.1) matching mechanism is [4], based on the theory of anal- ogy. Most work on ontologies involve the construction of a single ontology [for instance, 15], even in those that do collaborative design [11]. Often, ontologies are built for man- machine interaction [13] and not for machine-machine interaction. Everett [3] tries to iden- tify conceptually similar documents, but use a single ontology. Gelbukh [5, 6] does the same using a topic hierarchy: a kind of ontology. Linguists [18] identify related words (se- mantic relatedness), not concepts, often by statistical comparisons. With respect to measuring how close is a concept to another, Levachkine [16, 17] makes simpler measurements between qualitative values (“words,” you can say) belonging to a hierarchy, to measure their confusion. More at §3.1.2.1 below. With respect to the communication language, we prefer [2] in decreasing order: 2 We represent concepts in Courier font or with a subscript c. A concept is language-independent: the concept cat is the same as the concepts gato-gata, gatto-gatta, chat-chatt, Katze, КОТ-КОШКА, ዊ�ዊ� (neko), meaning “a small domestic feline animal”. Concepts appear in English in this paper, for readers’ benefit. 3 It is much easier to design the interaction (hence, the exchange of concepts) between two agents (or pieces of software), when the same team designs both agents. In this sense, “they previously know each other:” each agent knows what the other expects, when (the calling sequences), and the proper vocabulary to use. 4 Not-free will or canned interactions are those that follow defined paths. For instance, the interaction between a program and a subroutine it calls, where the calling sequence (of arguments) is known to both. Free will usually requires goals, resources, and planning [19]. 5 Knowledge is also stored in the relations (or verbs, actions, processes) between objects (or nouns, subjects): §1.2. 2 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 3 of 24 OP 1. A language whose words (tokens, atoms) are formed by concepts [19]; 2. One with unambiguous words (a word represents only one concept). Examples: the Natural Numbers; the Proper Nouns; 3. One where each word has a small number of ambiguities, for instance, a natural lan- guage [18] (we use this option in this paper; see figure 1); 4. One where each word points to a foreign address space, thus representing “black boxes” that can only be compared with = and ≠. Example: a language consisting of tokens such as “toves,” “borogove,” “mome”, “outgrabe”, “fromelic,” “meratroping,” tokens that only admit equality as their comparator. These are the four choices to name a concept. Often, an ontology skips details by just keep- ing the names (and nothing else) of a concept, as when it says John [owns=wardrobe] and it does not say anything else about wardrobe. It is a shallow comcept. The book [1] gives other approaches and experimental results in semantic analysis. thing (thing, something, object, entity) { food { vegetable [contain=chlorophyll, structure=living] { onion [color=white] lemon [color=green, shape=circle_shape, taste=sour, size=3cm] } fruit { orange [color=orange_color, shape=circle_shape] } meat { pork [texture=soft, color=pink] beef [texture=medium, color=red] turkey [texture=medium, color=white] veal [texture=soft, color=red] } seed (seed, cereal) { rice [color=white, shape=oval_shape] wheat [color=yellow, shape=oval_shape] } } tool (tool, hardware) { wrench (wrench) electrical_tool (household, electrical_tool) { dishwasher [use=cleaning, structure=manmade, size=small, covering=paint] blender [use=blend, structure=manmade, covering=paint] drill mixer [use=mix, structure=manmade] } } furniture { bed table sofa (sofa, seat) bench } pet { cat [covering=hair, family=feline] dog [covering=hair, family=canine] canary [covering=feather] } relation { color { white yellow green purple orange_color } shape (shape, contour) { circle_shape (circle, oval) square_shape (square ) } taste { sweet sour } size { 3cm (3cm, 1-2in) } covering { hair feather paint (paint, painted) } structure { living (living, alive) manmade (handcrafted, manmade) } contain (contain, content) { chlorophyll } family { feline canine } use { cleaning blend mix } matter_states (matter_state) {liquid suspension gel solid gas } } } Figure 1. OP, the ontology of person P. Concepts such as sofa appear in Courier font, while the words w(sofa) = (sofa, seat) (Cf. §1.2) denoting the concept appear in Times Roman. These words do not appear in the listing if identical to the concept denoted. Thus, we see onion and not onion (onion). Facts (Cf. §1.2) appear as cat [covering=hair], meaning that, for cat, the value of relation covering is hair. OP contains 68 concepts. thing (thing, something) { 3 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 4 of 24 OS pharmacy (pharmacy, drugs, medicine, medicament) { self_service { personal_care { mouth_care feminine_hygiene burns (burns, solar_protector) repellent } diet (diet_substance) { diet_powders (diet_powders, diet_creams) diet_solutions diet_tablets } stomach { laxatives_suspension [is_a=suspension] laxatives_suppository [is_a=gel] laxatives_tablets [is_a=solid, shape=circle] antiparasites } } patent_pharmacy } general_merchandise { hardware { bathroom_kitchen electrical { socket multicontact } lightbulb manual screw } } cloth {ladies_stocking hosiery shoe } perishable { frozen_food meat { pork beef turkey veal } fruit_vegetable { garlic_onion { garlic white_onion (onion) [color=white] yellow_onion (onion) [color=yellow] purple_onion (onion) [color=purple] } bulk_fruit { bulk_citrics (citric) exotics annual_fruits season_fruits } packed_fruits {avocados packed_citrics (citric) } } cooked (cooked_food) seeds {rice cereal bean } bulk_vegetable {gourd potato lemon [color=green, shape=spheric_shape, size=3cm, taste=sour] } seafood (fish_seafood) { fish (fish) preparations (fish_preparations) } } groceries { oils (eatable_ oil) { aerosol_oil sunflower_oil corn_oil mixed_oil olive_oil } rice (seed_rice) {extra_rice integral_rice shushi_rice precooked_rice super_extra_rice (super_extra_rice) } sugar (sugar, sweetener) { aspartame (aspartame, diet_sugar) glass_sugar (sugar) black_sugar (sugar) refined saccharin standard } coffee {decaffeinated_grain grain sweetened_coffee (sweetened) normal_soluble sweetened_soluble decaffeinated_soluble special_soluble } hot_cereal { oats mixed granola } cold_cereals { cereal_bars(bar) fiber_bars granola_bars energetic_bars filled_bars cold_rice_cereal (rice) cold_oats_cereal (oat) cold_corn_cereal (corn) cold_wheat_cereal (wheat) cold_mixed_cereal (mixed_cereal) diet_cereal } chili{ancho_chili tree_chili guajillo_chili morita_chili pasilla_chili } dry_fruits(dry, fruits) {prune coconut jamaica tamarind raisin (raisin, dry_grape)} flour (flour) { rice_flour (rice) wheat_flour (wheat) corn_flour (corn) hotcakes_flour (hotcakes, flour) pastries_flour (pastries, flour) powder (powder) other_flour (barley, rye, flour) } } other { relation { color { white yellow green purple } shape (shape, contour) {circle (circle_shape) spheric_shape (sphere) square_shape (square ) } taste { sweet sour } size {3cm (3cm, 2in) } } matter_states (matter_state) { liquid suspension gel solid gas } } } Fig. 2. Superama ontology (150 concepts). To save space, words of a concept do not appear when identical to it 4 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 5 of 24 1.2 Definitions Named entity. An object, relation, property, action, process, idea or thing that has a name: a word (or word phrase) in a natural language. ♦6 A named entity is shared. Concept. The representation of a named entity. ♦7 Examples: peak-uttermost, to_- fly_in_air, angry-mad. So, concepts have names: those words (or word phrases, such as New York City) used to denote the named entity that the concept represents.2 Unfortunately, the names given by different people to concepts differ (synonymy) and, more unluckily, the same word is given to two concepts (examples: words peak; fly; mad). Thus, words are ambiguous, while concepts are not. A person or agent, when re- ceiving words from a speaker, has to solve their ambiguity in order to understand the speaker, by mapping the words to the “right” concept in his/her/its own ontology. This mapping is called disambiguation. There are also composite or complex concepts, such as “to ski in a gently slope under a fair breeze while holding in the left hand a can of beer.” These can be shared with other agents, too, but they do not possess a name: they have not been reified (Cf. §2.2). Concepts can enter also in relations (called restrictions in some Logics) with other con- cepts, as defined below. A concept represents three kinds of real-world entities: (a) sets, like animal (repre- sents all the animals); (b) individuals, like Abraham Lincoln (represents a particu- lar person), and (c) relations, such as buys. Relation. A relation of order k is a sequence of concepts (rel c1 c2 … ck)representing that relation rel holds between c1, c2, ..,ck. ♦ Notice that rel is also a con- cept (which may be shallow). Notation. For binary relations (rel c1 c2) we write in the ontology rel [c1=c2], for instance lemon [color=green] in figure 2. Notice the use of c {p q r …} to indi- cate that the subsets of c are p, q, r… More at [19]. Fact. A relation is a fact if it holds in reality. ♦ It agrees with the real world. It faithfully represents an aspect of reality. To discover facts is not easy: people make tedious ex- periments and observations to ascertain what “really happens in the real world” and what does not. Thinking or philosophizing is not enough. We are not interested in how to discover facts. Thus, we postulate that an agent “knows” or “believes” that its knowl- edge consists of only facts: truthful representations of reality. It is possible for some rel∈OA not to be a fact, but A does not know this. An agent does not lie to itself. Rela- tions not agreeing with reality are “lies.” Knowledge is the concrete internalization8 of facts among real-world entities ♦6 It is stored as facts and as concepts; it is measured (grosso-modo) in “number of concepts.” Ontology. It is a formal explicit specification of a shared conceptualization. [7] ♦ It is a taxonomy of the concepts I want to represent.9 See figure 1. 6 Symbol ♦ means: end of definition. Having a name in a shared language means that is known to many people. 7 We differ from Formal Concept Analysis (FCA) where a concept is any subset of attributes (or the corresponding set of objects) while we narrow concept to represent only an objects or thing that has a name in a natural language. 8 By “concrete internalization” we mean writing down (storing) the fact as a relation, for later use. 9 Each concept that I know and has a name is shared, since it was named by somebody else. More at §2.2. 5 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 6 of 24 Our definition. O = (C, R, root), an ontology is a structure formed by concepts and relations among concepts. Each concept that represents a set (such as the concept ani- mal) necessarily holds the relation subset with some other set, except the distin- guished concept root, which is subset of nobody, and which is superset of all other sets. Each concept that represents an individual must be in relation member of with some set-representing concept. ♦ Each concept and relation has as name (or has associ- ated) words from a natural language, since the ontology tries to represent a part of the real world. The required presence of relations subset and member of give an ontology a tree- like or taxonomy-like appearance; nevertheless, a set (apple) may be subset of more than one sets, such as fruit and food, and a person may be member of several sets. Word(s) associated with a concept: w(cA, OA) = the words associated in OA to concept cA. Example: (figure 1): w(tool, OP) = (tool, hardware). 2. Degree of know ledge about a concept; amount of know ledge of an agent How much does an agent know? In this section, we measure the amount of knowledge of an agent against the “total ontology” (an impractical abstraction). Later (§3.2), we meas- ure its knowledge relative to the knowledge of another agent. The idea is to know first how much an agent knows about a given concept, and then sum these amounts over all its known concepts. Total ontology. It is the ontology OK of an agent K that knows everything known to every agent. ♦ It is the union of all the ontologies of all the intelligent creatures, people and agents. Observations: 1. The total ontology is finite, and grows every day. 2. It is unique. Idea: think of a huge encyclopedia. 3. It contains only facts. To comply with 2 and 3 above, when trying to merge contradicting facts, K must dis- cover what “fact” is a lie. K could keep prevailing knowledge, but this can produce widespread knowledge that is nevertheless wrong, such as (Earth-World shape- form flat-plane). Truth is not discovered by majority voting. Since it is not the purpose of this article to unveil a method to find facts, we simply pos- tulate that the total ontology of K is formed with the help of a god or Very Wise Creature (VWC) that makes sure lies coming from some person or agent do not enter it. Thus, OK contains only facts,10 while an agent or person can still have parts of its/his/her ontology formed by lies. OK holds all known and “right” knowledge. The degree of knowledge (dk, §2.1) of an agent is measured against OK. 10 This total ontology grows every day, as new discoveries are performed. Also, notice that the ontology of a VWC must be larger or at least equal than the total ontology. Nevertheless, a VWC can not easily communicate its “ex- cess knowledge” to any person or agent A, because A will not understand some trios coming from VWC. Neverthe- less, VWC can (sequentially) teach this new knowledge to A, cf. §3.3.1. In most cultures’ cosmogony, there is a god that did just that. Such god is a VWC. In fact, we can define a VWC as an agent who has the total ontology. K=VWC ♦ 6 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 7 of 24 2.1 Degree of knowledge of an agent about a concept This degree is a measure of the (imperfect) grasp of a concept by an agent A. The idea is that the more relations that concept has in OA, the larger such degree of knowledge is. The degree of knowledge dkA(c) of A about a concept c is a number between 0 and 1, ob- tained by counting the number of arcs connecting to/from c in OA, adding the number of arcs labeled c in OA,11 and dividing into the similar calculation for c in the total on- tology OK. ♦ The closer dkA(c) is to 1, the less imperfect is A’s knowledge of c. 2 . 1 . 1 A mo u n t o f k n o w l e d g e o f a n a g e n t The idea is that every concept in OA contributes to the amount of knowledge of A. The amount of knowledge an agent has = Σ dkA(ci) over all ci∈OA. ♦ It is measured against the total ontology. It is approximated by the area under the histogram of con- cepts (see Clasitex in [8]). Similarly, the amount of knowledge of an agent in a disci- pline or area D⊂ OK is Σ dkA(ci) over all ci∈D. Definitions 2.1 “Degree of knowledge of an agent about a concept” and 2.1.1 “Amount of knowledge of an agent” are impractical since the total ontology is out of our reach. In their place, we shall define and compute, i.) (instead of 2.1) The degree of knowledge of an agent about a concept with respect to other agent’s knowledge of such concept, to be called in §3.1 the similarity value (sv). ii.) (instead of 2.1.1) The amount of knowledge of an agent with respect to another agent’s knowledge, to be called in §3.2 the degree of understanding (du) of A about B: how much A understands about what B knows. 2.2 Reification slightly increases knowledge Reification. The action of exposing the internal representation of a system in terms of pro- gramming entities that can be manipulated at runtime. The opposite process, absorption, consists of effecting the changes made to reified entries into the system, thus realizing the causal connection link [14]. ♦ To reify a (usually complex) concept or relation is to represent it by an atomic symbol (“to give it a name”), probably because we want to say more complex things about it; for instance, to affect it by other relations. Example: The complex concept “When Bill Clinton tries to convince a person about x, he explains and praises very much and with abundant examples the good things about x, but (without skipping any) explains lightly the bad things about x, thus giving the false appear- ance of an unbiased explainer”12 can be reified by giving it a name: clintonize (x). Then we can speak of clintonization, quasi-clintonization, and express clearly relations such as “clin- tonizing is immoral.” An ontology OA’=OA∪clintonize has one more concept than OA: the concept clintonize. A private concept, shared by few; not very useful for communications.13 In 11 This makes sense when c is a relation. 12 I believe this definition was introduced by President George Bush (Sr.) during a debate with then-candidate Bill Clinton. 13 An agent that reifies a concept could find this very useful for its own work (not for communication with others), much as an experienced locksmith invents a new tool by modifying other, in order to work faster: a private tool. 7 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 8 of 24 OQ our ontologies we will not cache (store) derived concepts [9], unless they are shared by many people (by having a name and a definition in a certain dictionary, say); that is, unless they are reified and given the same name by many people. thing (thing, something, entity) { eatable_thing (food, foodstuffs, groceries) { plant { vegetable [structure=living] {lettuce tomato onion potato (potatoes, potato, pome_de_terre) } fruit { strawberry banana } tree { lemon [color=green, shape=circle_shape] orange [color=orange_color] } cereal {rice[color=white] wheat[color=light_brown] }}} animal (animal, creature) [structure=living] { bird [covering=feather] { canary[size=small, covering=feather, color=yellow] } reptile[covering=scale] { lizard [size=medium, covering=scale, color=green] } mammal [covering=hair] {cat[covering=hair, size=medium, family=feline] dog [covering=hair, size=medium, family=canine]}} inanimate_thing (inanimate, object) { tool (tool,hardware) { manual (manual_tool) { wrench hammer } appliance (appliance, electrical) { drill [use=boring] electrical_saw (saw) [use=cutting] dishwasher [use=cleaning] blender [use=blend]}} furniture { bed table (table, surface) sofa (sofa, place) chair (chair, seat) } energy water } relation { color { white yellow purple green light_brown orange_color } shape (shape, contour) { circle_shape (circle, oval, round) square_shape (square ) } size { small medium } structure { living (living, alive) manmade (handcrafted, manmade) } covering { hair feather } family { feline canine } use { cleaning blend mix } | matter_state (matter_state) { liquid suspension gel solid gas plasma } } Figure 3. Ontology of person Q that buys in the supermarket of figure 2. It has 75 concepts. 3. Measuring the degree of understanding (comprehension) This section finds the concept cB∈OB most similar to cA∈OA, and how similar they are. From this, adding the similarities over all cB∈OB, we measure the degree of understanding of A with respect to OB. How well A knows the concepts in OB. 3.1 Finding the concept in your ontology most similar to one I have Consider two persons P and Q buying something specific at a real supermarket (www.superama.com.mx; its real ontology contains more than 500 concepts, we have cho- sen 150 of them for Ontology S, figure 2). Their ontologies are shown in figures 1 and 3. If 8 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 9 of 24 a person does not find exactly what he wants, he would like to know what is the most simi- lar item available. The sim algorithm (called “hallar (cA)” or COM in [19]) finds the most similar concept cB∈OB to concept cA∈OA. It also computes a similarity value sv∈[0, 1] expressing how similar was cB to cA. Agent A makes known concept cA to B by sending to B w(cA, OA) (words14 denoting cA), and also sending words w(pA, OA) denoting the father pA of cA. Four cases exist for cB = sim(cA).15 Case a) Node and father match. (Figures 4, 5) We look in OB for nodes pB and cB such that: (1) w(cB, OB)∩w(cA, OA)≠∅ (the intersection between the words associated to cB and those associated with cA is not empty); and (2) w(pB, OB)∩w(pA, OA)≠∅ (the intersection between words associated to pB and those associated to pA is not empty); and (3) pB is the father, grandfather or great-grandfather16 of cB. If such pB and cB are found, then cB is the answer and the algorithm returns sv = 1, too. Figure 4. Case a) Agent P (with ontology OP, figure 1) wants to find the most similar concept to cA = onion in OS (figure 2). Words (shown inside round parenthesis) from cA map to different concepts in B, but the most similar concept found (cB) is white_onion. We see that pA maps into pB, the grandfather of cB. sim does not compare concepts directly; it compares their words. 14 By §1, A can not send any node of OA to B. 15 Rigorously, sim is a function of two variables that returns two values, so it should be written (sv, cB) = sim (cA, OB). 16 If pB is found more than three levels up, the “semantic distance” is too high and sim says “no match.” B (ontology OS, supermarket) pA cA pB cB A (ontology OP) vegetable (vegetable) lemon (lemon) food (food) white_onion (onion)[COLOR=WHITE] onion (onion)[COLOR=WHITE] garlic_onion (garlic, onion) fruit_vegetable (fruit, vegetable) yellow_onion (onion)[COLOR=YELLOW] meat (meat) bulk_fruit (bulk fruit) (vegetable) (onion) 9 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 10 of 24 Figure 5. Case a) Father and son in OA find matches in OB. There are in OB three candidate nodes, the first that matches is the most similar concept, in this case white_onion. Case b) Father matches but node does not. Figures Error! Reference source not found. and Error! Reference source not found.. This case occurs when (2) of case (a) holds, but (1) and (3) do not. pB is found in OB but cB is not. In this case, sim is called recur- sively, and we try to compute pB' = sim(pA) to confirm that pB is the ancestor of cA, the concept of interest. (1) If the pB' found is thing, the root of OB, the algorithm returns not_found and concludes; sv = 0; (2) Otherwise, a certain child of pB, to be called cB', is searched in OB, such that: A. Most17 of the facts of cB' coincide with the corresponding facts of cA. Children of pB with just a few matching facts17 are rejected. If the candidate cB' analyzed has children, they are checked (using sim recursively) for a reasonable match17 with the children of cA. If a cB' is found with the desired properties, the algorithm re- ports success returning cB' as the concept in OB most similar to cA. Then sv = the fraction of facts of cB' coinciding with corresponding facts of cA. B. Otherwise cB' is sought among the sons of the father (in B) of pB; that is, among the brothers of pB; if necessary, among the sons of the sons of pB; that is, among the grandsons of pB. If found, the answer is cB'. sv = the sv returned by cB' multi- plied by 0.8 if cB' was found among the sons of pB,18 or by 0.82 = 0.64 if found among the grandsons of pB. C. If such cB' is not found, then the node nearest to cA is some son of pB, therefore sim returns the remark (son_of pB) and the algorithm concludes. sv = 0.5, an ar- bitrary but reasonable value. For example, in Figure 6, A sends words that corre- spond to the pair (cA = drill, pA = electrical), whereas B has the concept electrical but doesn't have drill nor any similar. In this case, the concept drillA is translated by B into (son_of electrical)B, which means “some electricalB I don't know” or “some electricalB I do not have in my on- tology. 17 We have found useful the threshold 0.5: more than half of the compared entities must coincide. 18 We have found that 0.8 allows for a fast decay as one moves up from father to grandfather and up. S P 10 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 11 of 24 Figure 6. Case b). Agent A (with ontology of person Q, figure 3) wants to find in ontology OS the concept most similar to cA = drill. Words from pA map to words from pB but cA has no equivalence in the ontology OS of B. Figure 7 shows the execution of sim for case (b)2(C). In this case concept drillA has no equivalent in B. Here son_of_electricalB is chosen from B as the most similar concept because parents electricalA and electricalB coincide and were confirmed. We assign sv = 0.5 Figure 7. Case b) The father of cA finds its corresponding pB, but cA does not find a matching cB Case c) The node matches but the father does not. This case occurs when (1) of case (a) holds but (2) and (3) do not. See figures 8 and 9. Concept cB is found but pB is not. We verify two conditions (A) and (B): (A) Most17 of the facts of cB should coincide (using sim) with those of cA ; and (B) Most of the children of cA should coincide (by sim) with most17 of the children of cB. cA PB A (ontology OQ) B (ontology OS supermarket) electrical (electrical) electrical_saw (saw) tool (tool, hardware) multicontact (multicontact) drill (drill) electrical (electrical) hardware (hardware) socket (socket) PA ? (electrical) (drill) Q S 11 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 12 of 24 (1) If the facts in (A) and the children in (B) coincide, the algorithm concludes with re- sponse cB, although it did not find the pB∈OB that corresponds to pA∈OA. Here sv = the fraction of facts and children of cB matching with corresponding entities of cA. (2) If even fewer properties and children are similar then response is (probably cB) and the algorithm finishes. Here sv is computed like in (1)B. (3) If neither properties nor children are similar, response is not_found and the algo- rithm finishes. sv = 0. Figure 8. Case c). Node matches but father does not. Agent A (with ontology OP of figure 1) wants to find a concept in B’s ontology OS corresponding to cA = lemon. Words from cA match with words from cB, but there is no equivalence for words from pA. Figure 9 shows an example of case (c)(2). In this case we use sim to seek in B the most similar concept to lemonA. Here concepts match but parents (vegetableA, bulk_vegetableB) do not (words are different for each parent), therefore similarity of the properties are used (calling recursively to sim). sv = 0.75 because parents do not coin- cide, and the answer is “probably lemon.” Case d) If neither cB nor pB are found, the algorithm concludes returning the response not_found. Figures 1 and 1. sv = 0. cA could not find a similar node in OB. The agents may have different ontologies (they know about different subjects) or they may not share a common cmmunication language. See figures 10 and 11. PB A (ontology OP) B (ontology OS supermarket) lemon (lemon)[COLOR=GREEN, SHAPE=SPHERIC_SHAPE, SIZE=3CM,TASTE=SOUR] bulk_vegetable (bulk_vegetable) perishable (perishable) PA vegetable (vegetable) lemon (lemon)[COLOR=GREEN, SHAPE=CIRCLE_SHAPE, TASTE=SOUR,SIZE=3CM] food (food) onion (onion)[COLOR=WHITE] ? CB CA (vegetable) (lemon) 12 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 13 of 24 Figure 9. Case c) Unable to find in B the father of cA , although cB corresponding to cA was found. Figure 10. Case d) Neither node nor father match. Agent A wants to find the most similar concept in B to cA = sofa. There are no words from cA that map into words of cB nor for pA and pB. Ontologies are those of fig- ures 2 (OS) and 3 (OP). Figure 11 shows the execution for case (d). Observe that A’s ontology OP fragment of interest is mainly about furniture while B’s ontology OS is mainly about groceries. There are some concepts in common, but not the involved concepts. sv = 0. Figure 11. Case d) Neither cA = bed nor pA = furniture find suitable matches in ontology S. cA A (ontology OP) B (ontology OS supermarket) pharmacy (pharmacy) thing (thing, something) perishable (perishable) PA cloth (cloth) ? ? sofa (sofa) bed (bed) (bed) (furniture) furniture (furniture) Self_service (self service) patent (patent) SP P S 13 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 14 of 24 Ph hepatitis type_A_hepatitis type_C_hepatitis type_V_hepatitis type_B_hepatitis hepatitis cirrosis John If cB is the concept most similar to cA, it is not necessarily true that cA is the concept most similar to cB. sim is not symmetric. Example: Refer to Figure 12. Levachkine [16] digs deeper into this. The function sim is only defined between a concept cA in OA and the most similar con- cept cB in OB; extensions sim’ amd sim’’ are in §3.1.2 below. 3 . 1 . 1 W h o r u n s sim? Who compares these two concepts, since they belong to different ontologies? That is, who runs sim? Either agent A or B can execute it, since sim compares words, not concepts. Nevertheless, when A runs sim, it needs the collaboration of B (and vice versa), which has to provide words to be used by sim (thus, by A). Also, even when A executes sim producing cB as result, A can not “have” or “see” cB: it is a pointer to the memory OB, a meaningless pointer for A, such as the tokens of point 4 of §1.1. What A can see of cB is: (1) the words which denote cB, as well as (the words for) the nodes related to cB; (2) corresponding words for the father, grandfather, sons... of cB (and words for their relations); (3) sv, indicating how similar that elusive cB is to its (very solid) cA. In fact, A still has cA as “the concept I have been thinking all along.” When A runs sim, B can see, of course, cB, but it can not “see” or “grasp” cA. The most of what B can see of cA is that “A wants to talk about some- thing of which the closest I have is cB”.19 B can sense from the words sent to it by A some differences between its solid cB and the elusive cA of A. More in §3.3. Figure 12. sim is not symmetric. Physician Ph knows four kinds of hepatitis, including the popular type_A_hepatitis and the rare type_V_hepatitis (viral), while John only knows hepatitis. The type_V_hepatitis of Ph (and all others) finds John’s hepatitis as “the most similar concept John has,” while John’s hepatitis best maps into Ph’s type_A_hepatitis. Ph knows more than John, so Ph can select a better target in his rich ontology for John’s vague concept. John can not make such selec- tion. 19 It will not help if B is more cooperative. For instance, dumping all its ontology OB into A’s memory will not help A, who will still see a tangled tree of meaningless pointers. Well, not totally meaningless—some understandable words are attached to each node. Yes: A can (patiently) understand (untangle) OB by comparing each of OB nodes with its own OA –that is, by using sim! 14 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 15 of 24 3 . 1 . 2 Ge n e r a l i z i n g s i m sim’ (cA, dA) for two concepts belonging to the same ontology, is defined as the 1/(1+length of the path going from cA to dA in the OA tree). ♦ sim’ (cA, dA) ∈ [0, 1]. sim’ is sym- metric. Example: see figure 14. 3.1.2.1 Relation to confusion In [16], the confusion conf(cA, dA) occurred by using cA instead of dA, is defined as the length of the descending20 path from cA to dA. ♦ This definition holds for hierarchies; it is here extended to ontologies. If we had defined sim’ (cA, dA) = (1/(1 + length of the descend- ing path going from cA to dA in the OA tree), we would have had sim’ (cA, dA) = 1/1+conf(cA, dA). We prefer, for ontologies, the definition of sim’ in §3.1.2, since it is symmetric, while conf is not. Example: for ontology D of figures 1 and 2, conf (liq- uid_food, food) = 0; the confusion when using liquid_food instead of food is 0, since liquid food is food. conf (food, liquid_food) = 1; when I want liquid food but I am given food, there is an error of 1 (a small error, you could think). For other concepts, we obtain the values in figure 13. Confusion and similarity for concepts x and y belonging to the same ontol- ogy OP of figure 1 conf (x, y); con- fusion in using x instead of y conf (y, x); confu- sion in using y instead of x sim’ (x,y) = sim’ (y,x); simi- larity between x and y x =plant, y =animal 1 1 1/3 x =plant, y =inanimate_thing 1 2 1/4 x =plant, y =cereal 1 0 1/2 x = fruit, y = tool 2 3 1/6 x = strawbery, y = furniture 2 4 1/7 x=thing, y=furniture 2 0 1/3 Figure 13. Examples of confusion and similarity (sim’) for two concepts of the same ontology OP, figure 1. conf is not symmetric; sim’ it is. For similarity between any two objects of different ontologies, we have: sim’’ (cA, dB) when dB is not the most similar concept in OB to cA, is found by making first s1 = sv returned by sim (cA) [this also finds cB, the object in OB most similar to cA]; then, find s2 = sim’ (dB, cB). Now, sim’’ (cA, dB) = s1s2. 3.2 Degree of understanding The value sv found in cB=sim(cA) in §3.1 can be thought of as the degree of under- standing that agent B has about concept cA. Each cA that forces B to answer sv=0 indicates that B has no idea (no concept) about this cA. We can add all these sv’s for every concept 20 Going towards more specialized concepts. “Using a person from Houston when I want to use a Texan person, confusion is 0; using a Texan person when a Houston person is needed causes confusion=1; using a US person causes confusion=2.” 15 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 16 of 24 cA∈OA and find the degree of understanding that agent B has about OA.21 It is as if A asks B, for each concept cA∈OA, «do you understand what is cA?» How much do you understand my cA? At the end, A has a good idea of the understanding of B (with respect to OA). The degree of understanding of B about OA, du(B, A) = {sum over all cA∈OA of sv re- turned by sim(cA)} / number of concepts in OA. ♦ [20] Similarly, we can measure the de- gree of understanding of B about some region of OA. du is not symmetric. In general, an agent understands some parts better than others. Notice that if OA is a large (approaching in size the total ontology of §1.2), then the degree of understanding of B with respect to OA approaches its amount of knowledge as given in §2.1.1. du(B, A)≤ 1; in the regions where B knows more than A, du= 1. Example: for person P of figure 1 and supermarket S (Fig. 2), the degree of understanding of P about PS is du(P,S)= 29.75 / 150 =0.2. See figures 14, 1 and 15. cS CP= sim (cS) sv cS CP= sim (cS) sv thing thing 1.0 purple purple 1.0 electrical electrical_tool 1.0 shape shape 1.0 socket son_of_electric al_tool 0.5 circle son_of_shape 0.5 multicon- tact son_of_electric al_tool 0.5 spheric_shape son_of_shape 0.5 meat meat 1.0 square_shape square_shape 1.0 pork pork 1.0 taste taste 1.0 beef beef 1.0 sweet sweet 1.0 turkey turkey 1.0 sour sour 1.0 veal veal 1.0 size size 1.0 white_onion onion 1.0 3cm 3cm 1.0 lemon probably lemon 0.75 matter_states matter_states 1.0 relation relation 1.0 liquid liquid 1.0 color color 1.0 suspension suspension 1.0 white white 1.0 gel gel 1.0 yellow yellow 1.0 solid solid 1.0 green green 1.0 gas gas 1.0 Figure 14. We are trying to assess du(P, S), the degree of understanding that person P (figure 1) has about S’s ontology (figure 2). Only rows where sv≠0 are shown. Columns 2 and 5 show the concept cA most similar to each cS∈OS; columns 3 and 6 show the corresponding similarity value sv. The degree of understanding du(P,S) is computed by adding over every cS∈OS the corresponding sv returned by cP=sim(cS) and dividing by 150 = number of concepts in OS. Thus, du(P, S)= (ΣSsv)/150= 29.75/150= 0.2. That is, P understands 20% of S. Results appear in Figure 15 21 B does not know how many concepts there are in OA, so it needs cooperation of A, for instance, when B asks A “give me the next concept in your ontology, please.” 16 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 17 of 24 Figure 15. Computing du(P,S) as detailed in figure 14 shows that P understands 20% of S. Since the size of S is larger than the size of P, probably du(S, P), the degree of under- standing of S about P, will be larger than du(P, S). “The more I know, the more I under- stand.” This is shown in figures 16 and 17. Figure 16. To compute du(S, P), the program adds all sv’s produced (see figure 18) by each answer cS=sim(cP) when every concept of P is visited. Thus, du(S, P) = 0.51. S understands 51% of P. S P S P 17 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 18 of 24 CP cS = sim (cp) sv CP cS = sim (cP) sv thing thing 1.0 orange_color son_of_relation 0.5 onion white_onion 1.0 shape shape 1.0 lemon probably lemon 0.7 5 circle_shape son_of_shape 0.5 meat meat 1.0 square_shape square_shape 1.0 pork pork 1.0 taste taste 1.0 beef beef 1.0 sweet sweet 1.0 turkey turkey 1.0 sour sour 1.0 veal veal 1.0 size size 1.0 tool hardware 1.0 3cm 3cm 1.0 wrench son_of_hardware 0.5 covering son_of_relation 0.5 electri- cal_tool electrical 1.0 structure son_of_relation 0.5 dish- washer son_of_electrical 0.5 contain son_of_relation 0.5 blender son_of_electrical 0.5 family son_of_relation 0.5 drill son_of_electrical 0.5 use son_of_relation 0.5 mixer son_of_electrical 0.5 matter_states matter_states 1.0 relation relation 1.0 liquid liquid 1.0 color color 1.0 suspension suspension 1.0 white white 1.0 gel gel 1.0 yellow yellow 1.0 solid solid 1.0 green green 1.0 gas gas 1.0 purple Purple 1.0 Figure 17. Now S is asked by P about each concept in OP. Each answer of S (second and fifth columns; only cs’s with sv≠0 are shown) produces a similarity value (third and last columns). Adding these numbers gives 34.75. Dividing into | P |=68, the degree of understanding of S with respect to P is found to be 0.51. We can also compute the “cross” knowledge among our two supermarket customers. Figures 18 and 19 show du(Q,P)=0.82. Figures 20 and 21 show that du(P, Q)=0.71. Thus, we can see that P knows more about Q than Q about P. Figure 18. The degree of understanding of Q about P is du(Q, P) = 55.5 / 68 = 0.82. Details in figure 20. P Q 18 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 19 of 24 CP CQ = sim (cP) sv CP CQ = sim (cP) sv thing thing 1.0 green green 1.0 food eatable_thing 1.0 purple purple 1.0 vegetable vegetable 1.0 orange_color orange_color 1.0 onion onion 1.0 shape shape 1.0 lemon probably lemon 0.5 circle_shape circle_shape 1.0 fruit fruit 1.0 square_shape square_shape 1.0 orange probably orange 0.5 taste son_of_relation 0.5 meat son_of_eatable_th ing 0.5 size size 1.0 seed cereal 1.0 3cm son_of_size 0.5 rice rice 1.0 covering covering 1.0 wheat wheat 1.0 hair hair 1.0 tool tool 1.0 feather feather 1.0 wrench wrench 1.0 paint son_of_covering 0.5 Electri- cal_tool appliance 1.0 structure structure 1.0 Dish- washer dishwasher 1.0 living living 1.0 blender blender 1.0 man_made man_made 1.0 drill drill 1.0 contain son_of_relation 0.5 mixer son_of_appliance 0.5 family family 1.0 furniture furniture 1.0 feline feline 1.0 bed bed 1.0 canine canine 1.0 table table 1.0 use use 1.0 sofa sofa 1.0 cleaning cleaning 1.0 bench son_of_furniture 0.5 blend blend 1.0 cat cat 1.0 mix mix 1.0 dog dog 1.0 matter_states matter_state 1.0 canary canary 1.0 liquid liquid 1.0 relation relation 1.0 suspension suspension 1.0 color color 1.0 gel gel 1.0 white white 1.0 solid solid 1.0 yellow yellow 1.0 gas gas 1.0 Figure 19. To compute du(Q, P), every cP∈P (first and fourth columns) is visited and the most similar cQ∈Q (second and fifth columns) is found, as well as its similarity value sv (third and sixth columns). Only rows where sv≠0 are shown. The sum of all these sv’s (55.5) divided by the number of concepts in P (68) gives du(Q, P) = 0.81 19 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 20 of 24 Figure 20. du(P, Q) = 54.1 / 75 = 0.71. P understands 72% of Q’s knowledge. Details in figure 21. 3.3 Can I understand the source of our disagreement? Can I mend it? §3.1.1 shows that A can not perceive or see cB directly. Given cA∈OA and its most similar concept cB∈OB, can A perceive in what way cB differs from its cA? After all, A knows from the value sv returned by sim(cA), how imperfect is the matching of cA to cB. The answer is yes, and it will be explained qualitatively. A can ask B about the facts involving cB. It will receive the answers in words. Then, A can proc- ess them (through sim, perhaps) to see how cA’s facts differ from those re- ceived. It can do the same with the father_of (cB), and with the sons_of (cB). And so on. Some words received will refer to concepts of which A is not sure (it has no knowledge of them, or there is ambiguity), so that more processing (Process P is called again) on these concepts is needed. Also, occasionally A will receive from B relations involving cB which A has as false for cA. 3 . 3 . 1 A n a g e n t l e a r n i n g f r o m a n o t h e r a g e n t A can collect all this information in a note N attached to cA: “N is what B knows about my concept cA, which differs from my knowledge”. It is like having A compute a belief: “B believes or knows N about cA, and N is not what I know about cA.” Or, perhaps, A can go ahead and decide to internalize N, that is, to “make it its knowledge”: to learn N about cA from OB. For this to happen, A needs to incorporate the relations in N in its OA,22 and to resolve the ambiguities and inconsistencies coming from N (some of N’s relations are known to A to be false; others make little sense to A). This has been solved for an agent teaching a person, but not yet for an agent teaching another agent. It can be done, perhaps, by using other knowledge services in the Web to referee disagreements between A and B and help A decide who is wrong about what (the “what” is already captured in N). We call this ontology merging: if A learns OB from B, its new OA will be its old OA merged (as in- formally described here) with OB. Cuevas’ Ph.D. Thesis [2] is along these lines. 22 This (to regard N as facts) is not difficult, once A decides to do it. Process P P Q 20 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 21 of 24 CP CQ = sim (cP) sv CP CQ = sim (cP) sv thing thing 1.0 purple purple 1.0 Eat- able_thing food 1.0 green green 1.0 plant son_of_food 0.5 light_brown son_of_color 0.5 vegetable vegetable 1.0 orange_color son_of_color 0.5 lettuce son_of_vegetable 0.5 shape shape 1.0 tomato son_of_vegetable 0.5 circle_shape circle_shape 1.0 onion onion 1.0 square_shape square_shape 1.0 potato son_of_vegetable 0.5 size size 1.0 lemon lemon 1.0 small son_of_size 0.5 cereal seed 1.0 medium son_of_size 0.5 rice rice 1.0 structure structure 1.0 wheat wheat 1.0 living living 1.0 canary probably canary 0.34 man_made man_made 1.0 cat probably cat 0.67 covering covering 1.0 dog probably dog 0.67 hair hair 1.0 tool tool 1.0 feather feather 1.0 manual son_of_tool 0.5 family family 1.0 appliance electrical_tool 1.0 feline feline 1.0 drill drill 1.0 canine canine 1.0 Electri- cal_saw son_of_electrical _tool 0.5 use use 1.0 dishwasher dishwasher 1.0 cleaning cleaning 1.0 blender blender 1.0 blend blend 1.0 furniture furniture 1.0 mix mix 1.0 bed bed 1.0 matter_state matter_states 1.0 table table 1.0 liquid liquid 1.0 sofa sofa 1.0 suspension suspension 1.0 chair sofa 1.0 gel gel 1.0 relation relation 1.0 solid solid 1.0 color color 1.0 gas gas 1.0 white white 1.0 plasma son_of_matter_s tates 0.5 yellow yellow 1.0 Fig. 21. To compute du(P, Q), concepts in Q (columns 2 y 5) most similar to each concept in P (columns 1 and 4), as well as the similarity value sv, are computed. Only rows with sv≠0 are shown. 3.4 Conclusions Methods are given to allow interaction and understanding between agents with different ontologies, so that there is no need to agree first on a standard set of concept definitions. Given a concept and associated words, a procedure for finding the most similar concept in another ontology is shown, with examples, as well as a measure of the degree of under- standing between two agents. It remains to test our methods with large, vastly different, or practical ontologies. Work reported is a step towards free will interactions4 among agents, instead of using canned interactions. Also, towards agents “strange to each other”3 that try to interact and 21 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 22 of 24 make sense of their utterances, opposing the current trend where only agents written by the same person or group, or following the same data exchange standards, can interact. Interaction through standards will still dominate the market for some time: it is easier to define and follow standards than to be “flexible, uncompromising and willing to try to un- derstand new concepts.” A standard ontology in a discipline is a good thing, although it feels rigid and archaic after a while.23 Nevertheless, knowledge can not be standardized, since each day more sprouts; standardization will always fall behind. It is preferable, I think, for me to be flexible and have general ways of trying to understand what you have to say (even new or unusual things), instead of forcing you to use a standard for concept- sharing with me (I already force you to use a shared communication language, perhaps a natural language, but that is unavoidable). Our work shows that a standard ontology for concept-sharing is not needed; it will be impossible in general, anyway. 3 . 4 . 1 S u g g e s t i o n s f o r f u r t h e r w o r k From text document to ontology. To help ontology merging (§3.3.1), write a converter that forms ontologies out of text documents. Notation to describe any complex concept. How do you describe complex concepts, such as “clintonize” of §2.2? Idea: express it as relations composed by relations. See [19] for a first try. Describe actions. Extend ontologies to make possible to describe a sequence of events [22]. Better notation for ontologies. � Tree notation (figure 1) is cumbersome, since only one “subset” relation is represented, and often a set S is partitioned in several partitions. Thus, a better notation could be: person {partition sex (=M : male_person) (=F : female_person) } {partition age (≤20 : young_person) (20< age ≤ 60 : adult_person) (>60 : old_person) } � Similarly, graphic notations make cumbersome to represent n-ary relations. � When char- acterizing the relations (as another branch of the ontology), you need to define types of par- titioning relations (sex, age…), or whether the partition is a “natural” one, like partition- ing vertebrate into fish, bird, reptile, batrachians and mammal. Agent interaction. Establish necessary or sufficient conditions for agent interaction that do not have a communication agreement, as mentioned in §1. 3.5 Acknowledgments Helpful discussions were held with Profs. Serguei Levachkine (CIC), Michael N. Huhns (U. of South Carolina), Alexander Gelbukh (CIC), and Hal Berghel (U. of Nevada Las Ve- gas). Work herein reported was partially supported by NSF-CONACYT Grant 32973-A and Project CGPI-IPN 2004442). Authors have SNI National Scientist Award (CONACYT) 23 Compare the UNESCO Catalog of Sciences (which is 30-years obsolete in Computer Science) with the ACM Computing Classification System, which is 2-years obsolete. 22 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 23 of 24 3.6 References 1. V. Alexandrov, S. Levachkine and A. Guzman. “Data Dynamical Structures for Image Treatment with Applications to Digital Cartography”. Book in preparation. 2. A. Cuevas-Rasgado. Automatic learning by an agent through ontology merging. Ph. D. Thesis (in preparation; in Spanish), CIC-IPN. 3. J. Everett, D. Bobrow, R. Stolle, R. Crouch, V. de Paiva, C Condoravdi, M van den Berg, and L Polyani. Making ontologies work for resolving redundancies across docu- ments. Comm. ACM 45 (2) (2002) 55-60. 4. K. Forbus, B. Falkenhainer and D. Gentner. The structure mapping engine: algorithms and examples. Artificial Intelligence 41 (1) (1989) 1-63. 5. A. Gelbukh, G. Sidorov and A. Guzman-Arenas. Use of a weighted document topic hierarchy for document classification. Text, Speech, Dialogue (Pilsen, Chech Republic, 1999)133-138. 6. A. Gelbukh, G. Sidorov, and A. Guzman-Arenas. Document comparison with a weighted topic hierarchy. DEXA-99, 10th International Conference on Database and Expert System applications, Workshop on Document Analysis and Understanding for Document Databases (Florence, Italy, 1999) 566-570. 7. T. Gruber. Toward Principles for the Design of Ontologies Used for Knowledge Shar- ing, in: Nicola Guarino and Roberto Poli (eds.), Formal Ontology in Conceptual Analy- sis and Knowledge Representation (Kluwer Academic Publishers 1993). 8. A. Guzman-Arenas. Finding the main themes in a Spanish document. Journal Expert Systems with Applications, 14 (1/2) (1998) 139-148. 9. A. Guzman-Arenas, J Olivares, A. Demetrio and C. Dominguez. Interaction of purpose- ful agents that use different ontologies. In: Lecture Notes in Artificial Intelligence 1793 (Springer 2000) 557-573. 10. A. Guzman-Arenas, C. Dominguez and J. Olivares. Reacting to unexpected events and communicating in spite of mixed ontologies In: Lecture Notes in Artificial Intelligence 2313 (Springer Heidelberg 2002) 377-386. 11. C. Holsapple and K. Joshi. A collaborative approach to ontology design. Comm. ACM 45 (2) (2002) 42-47. 12. M. N. Huhns, M. P. Singh and T. Ksiezyk. Global Information Management Via Local Autonomous Agents. In: M. N. Huhns and M. P. Singh (eds.): Readings in Agents (Morgan Kauffmann 1997). 13. H. Kim. (2002) Predicting how ontologies for the semantic web will evolve. Comm. ACM 45 (2) (2002) 48-54. 14. F. Kon, F. Costa, G. Blair and R. H. Campbell. The case for reflective middleware. Comm. ACM 45 (6) (2002) 33-38. 15. D. B. Lenat, R. V. Guha, K. Pittman, D. Pratt and M. Shepherd. Cyc: Toward Programs with Common Sense, Comm. of the ACM 33 (9) (1990) 30-49. 16. S. Levachkine and A. Guzman-Arenas. Hierarchies Measuring Qualitative Variables. In: Lecture Notes in Computer Science 2945 (Springer-Verlag 2004) 262-274. 17. S. Levachkine and A. Guzman-Arenas. Hierarchy as a new data type for qualitative variables. Submitted to Data and Knowledge Engineering. 23 of 24 Monday , April 04, 2005 Elsevier R ev ie w C op y Measuring comprehension between two agents 4-Apr-05 24 of 24 18. M. Montes-y-Gomez, A. Lopez-Lopez and A. Gelbukh. Information Retrieval with Conceptual Graph Matching. In: Lecture Notes in Computer Science 1873 (Springer- Verlag 2000) 312-321. 19. J. Olivares. An Interaction Model among Purposeful Agents, Mixed Ontologies and Unexpected Events. Ph. D. Thesis, CIC-IPN, 2002. (In Spanish) Available on line at http://www.jesusolivares.com/interaction/publica 20. Jesus M. Olivares-Ceja, Adolfo Guzman-Arenas. Concept similarity measures the un- derstanding between two agents. Accepted in NLDB 04. To appear in Lecture Notes in Computer Science (Springer 2004). 21. Jan Kupper, Horacio Saggion, et al. Multi-source in formation extraction and merging. Proc. IJCAI 03, 409-414 24 of 24 Monday , April 04, 2005 Elsevier