=Paper=
{{Paper
|id=Vol-66/paper-9
|storemode=property
|title=Multiagent Distributed Ontology Learning
|pdfUrl=https://ceur-ws.org/Vol-66/oas02-5.pdf
|volume=Vol-66
|authors=Leen-Kiat Soh
}}
==Multiagent Distributed Ontology Learning==
https://ceur-ws.org/Vol-66/oas02-5.pdf
Multiagent Distributed Ontology Learning
Leen-Kiat Soh
Computer Science and Engineering
University of Nebraska
115 Ferguson Hall
Lincoln, NE
(402) 472-6738
lksoh@cse.unl.edu
ABSTRACT agent learns its own concepts based on its experiences and special-
In this paper, we describe a framework for distributed ontology ties. When a new experience case arrives, the agent needs to in-
learning embedded in a multiagent environment. The objective of corporate it into its dictionary and its translation table. This is
this framework is to improve communication and understanding supported by three important components: conceptual learning,
among the agents while preserving agent autonomy. Each agent translation, and interpretation, with a Dempster-Shafer belief sys-
maintains a dictionary for its own experience and a translation tem [1] as the underlying structure to maintain ontology consis-
table. The dictionary allows the agent to compare and discover tency.
relationships between a pair of words or concepts, while the Our discussion here is related to [2]. In [2], however, the agents
translation table enables the agent to learn and record (a selected were not able to learn collaboratively in a multiagent system.
portion of) the vocabulary of its neighbors that is useful for the Instead, the learning was conducted only between two agents via
collaboration among the agents. The motivation for this distrib- exchange of concepts (ontologies) where the agents were neither
uted ontology learning is that each agent has its own experience able to adapt to changes in concept definitions nor able to handle
and thus learns its own ontology depending on what it has been multiple assertions from different neighbors. Moreover, our
exposed to. As a result, different agents may use different words framework addresses translation and interpretation of concepts,
to represent the same experience. When two agents communi- query processing and composition for collaboration among agents,
cate, agent A may not understand what agent B and that hinders and action planning based on traffic and agent activities, which
collaboration. However, equipped with the distributed ontology indirectly control the learning rates of the agents.
learning capabilities, agents are able to evolve independently their
own ontological knowledge while maintaining translation tables
through learning to help sustain the collaborative effort. 2. METHODOLOGY
In our framework, the multiagent system is one in which agents
can exchange queries and messages to learn about each other’s
Keywords ontology. To improve the communication and collaboration effi-
Multiagent systems, distributed learning, ontology learning, ciency, agents determine whether some translation is worth learn-
Dempster-Shafer belief system ing, which neighbors to communicate to, how to handle and dis-
tribute queries, and how to plan for agent activities. The frame-
1. INTRODUCTION work consists of two sets of components: operational and onto-
In the real world, where human agents are autonomous, distrib- logical. The operational components allow the agents to work
uted, and capable of individual learning, there are different lan- together in a multiagent system. The ontological components
guages. To communicate or collaborate, humans speaking differ- allow the agents to communicate and understand each other.
ent languages either learn a common language or use a translator.
Learning a common language that is not a person’s native incurs 2.1. Operational Components
imposes additional effort on that person and may result in disad- There are three important operational components: query process-
vantages. However, speaking through a translator may be not ing, action planning, and query composition. Note that in our
cost-effective and may be not feasible in some applications. framework, an agent sends out a query to its neighbor when it
Similarly, in a multiagent environment, autonomous and distrib- needs to find some additional experience cases for that some clas-
uted agents may encounter different events, gather different ex- sifying concepts. The query consists of the concepts and may
periences, and learn different ontologies. The focus of this paper consist of also some experience cases that the agent already has.
is to describe a distributed ontology learning framework in a When a user submits a new experience case, the agent also treats it
multiagent environment. as a query. Thus, each agent must be able to process queries.
Agents are required to compose queries as well as they also need
In our framework, each agent maintains a collection of experi-
to relay or distribute queries to other agents by modifying the que-
ence cases. Each experience case is a list of words with a list of
ries in their own words. Finally, for the system to be effective, the
classifying concepts. There are two ways that an agent can learn
query distribution and the ontology learning behavior are sup-
experience cases. First, users can teach them—by supplying a
ported by an action planning component that makes decision based
list of words and what the classifying concepts are for that list of
on the agent’s environment such as message traffic and neighbor-
words. Second, an agent can learn a new experience case
hood profile.
through its interactions with its neighbors. As a result, each
2.2. Ontological Components agent builds a group of concept hierarchies to link the concepts
together. This allows matching to find part-of concepts. More-
There are three important ontological components in our frame- over, the agent derives semantic rules to distinguish each concept.
work: conceptual learning, translation, and interpretation. We With these, the agent is able to tell whether a description vector
represent an experience case as a vector. Each vector consists of has anything to do with a particular concept. This is critical to our
the classifying concept and then a list of words describing that ontological learning. We assume that the concept names may
concept. A concept may have many different experience cases. differ among agents or users while the words describing these
Different concepts may be used to classify the same list of words, concepts are of the same vocabulary, of common examples.
resulting in different experience cases. A word may appear in
different experience cases for different concepts as well. These
experience cases can be further linked under a concept hierarchy.
2.2.2. Translation
An agent sends out query when it needs to obtain some experience
Moreover, for each concept, the agent also learns the description
cases or a description vector for a particular concept. When the
vector, combining all relevant experience cases together. This
queried agent processes the query, it first matches the concept to
allows the system to incrementally learn and evolve existing on-
its translation table. This is translation.
tologies.
If a credible translation is found, then the queried agent simply
2.2.1. Conceptual Learning sends back its experience cases or a description vector (depending
This component has three structures: description vectors, concept on what the querying agent has asked for) associated with the con-
hierarchies, and semantic rules. A descriptor vector is concept- cept translated.
specific. A concept hierarchy links several concepts together. A
semantic rule distinguishes a concept from all other concepts. Each agent maintains a comprehensive translation table. Each
table lists the concepts that the agent knows and maps them to the
First, when submitted, each concept is supported by n experience corresponding concepts of the neighboring agents. Only transla-
cases, in which each case has a list of words. Then, this compo- tions that are credible will be recorded in the table.
nent examines these experience cases to update the description
vector for that concept. A description vector consists of a list of In the beginning, each agent has an empty repository of translation
word-frequency pairs. For each word found in all the experience tables. At birth, an agent learns from the users’ submission (or
cases describing the same concept, the agent finds its frequency. queries). Then the agent learns about the relations it has with its
In this manner, the agent learns the different significance of the neighbors through two functional occasions. First, when it queries
words describing a concept. another agent for certain information (experience cases or descrip-
tion vectors). Second, when it receives a query from another
Second, each agent uses a set of concept hierarchies to organize agent. When an agent queries another agent for certain informa-
the concepts. If a concept name is a word in the description vec- tion and if the queried agent responds positively with its own se-
tor of another concept, then we say that the concept is part of that mantics, the querying agent will duly interpret it and update it in
another concept. its translation table. When an agent receives a query from another
Third, for the purpose of query matching and ontological learn- agent, if it does not have a readily available and up-to-date transla-
ing, the conceptual learning includes deriving semantic rules that tion, then the agent interprets the semantics that accompany the
help discriminate one concept from another. To construct rules, query. At the end of the interpretation, if the agent is able to rec-
we feed the vector field into an inductive learner. The learner ognize the semantics, it then reflects the learned mappings in the
parses the vectors into a decision tree that deterministically allo- translation tables.
cates each example into a semantically unique branch. Branches
will then be traversed—attribute values extracted and compara- 2.2.3. Interpretation
tives introduced—to arrive at rules. An example rule is: When a query fails to be matched through during translation, it is
If(university > 0.20) and forwarded to the interpretation module. There are two steps here:
(nebraska > 0.35) and (lincoln > 0.5) clarification and matching.
and(omaha < 0.1) and then Clarification. At this step, the queried agent first requests from
NU.
the querying agent the semantic rule that characterizes the concept
The above rule says that if frequency of the word “univer- in question. The querying agent may not have a semantic rule for
sity” appears in the description vector is greater than 20%, and that concept and thus may be unable to satisfy the request. Then
the frequency of the word “nebraska” is more greater than the queried agent may ask for a description vector supporting the
35%, and the frequency of the word “lincoln” is greater than concept in question. Once again, the querying agent may or may
50 percent, and the frequency of the word “omaha” is less than not have the vector for the request. If the queried agent does not
10%, then the concept is “NU.” This rule thus is used in query get further clarification on the concept, the interpretation step
processing: if a query asks for experience cases under the concept stops. However, if the querying agent is able to provide a seman-
“NU,” the agent knows how to evaluate the relevance of the de- tic rule, then the process moves to the matching step. If the query-
scription vectors to the query. ing agent is able to provide only a description vector, then the
queried agent has to perform conceptual learning to understand the
So, conceptual learning gives us a description vector for each concept before moving to the next step. In the end, if a clarifica-
concept. Each description vector specifies a list of words (with tion is achieved, the queried agent will have a semantic rule char-
their frequencies) for that particular concept. The collection of acterizing the concept in question. Then, the interpretation mod-
the description vectors is the agent’s dictionary. Further, the ule is ready to perform matching.
Note that a querying agent may not have a semantic rule for the receives evidence and maintains global beliefs in its assertions
concept in question when it simply relays that query from another consistently.
agent. A querying agent may only have a description vector if
Suppose that all the concept names that an agent understands,
the concept has not been incorporated into the ontology of the
stored in its ontologies, are of the frame of discernment or uni-
agent.
verse U. A proposition in favor of a concept name, Γ , is thus an
Matching. When matching the semantics of the query with the assertion as previously described. Thus, the set of all propositions
semantics of a resident rule, if the two sets are synonymic, then a is Ρ(U ) , the power set of U. Let m : Ρ(U ) → [0,1] be a func-
mass of 1.0 will be added to the interpretation scores. When we tion—a basic probability assignment—satisfying conditions for a
certainly false proposition, m(∅ ) = 0 , and for a certainly true
say ‘synonymic’, we refer to the inclusiveness and exclusiveness
when comparatives are involved. For example, if the querying
semantic has a semantic component “university > 0.20” proposition, ∑ m(Γ ) = 1 . The belief function,
and the resident semantic has “university > 0.15”, then Γ ⊆U
the resident semantic component is said to be inclusive of the Bel : Ρ(U ) → [0,1], is defined in terms of the basic probability
assignment m: Bel (Γ ) = ∑ m(α ) . This tells us the degree of
querying semantic component. A similar observation can be said
about the less-than comparative. Hence, two semantics are syn- α ⊆Γ
onymic when the resident components include the querying com-
belief associated with the proposition Γ as the probability mass
ponents. In the sense of rule-based systems, if a semantic is
matched, then the resident rule is fired by asserting the concept associated with Γ and its subsets. The plausibility of a proposi-
name entailed by the resident rule with a mass of 1.0. The trans- tion is further defined as Pls (Γ ) = 1 − Bel (¬Γ ) . Hence a propo-
lation between the concepts that describe the synonymic seman- sition is always bound by [Bel, Pls ] in terms of the confidence in
tics will then be recorded in the translation tables. its perceived truthfulness. To combine various pieces of evidence
Our agent is also equipped to handle relevant matching since a for building up beliefs in favor of various propositions, the Demp-
synonymic matching is rare. Suppose we have a querying seman- ster’s rule of combination is used. Suppose we are given two as-
tic “(college > 0.13 nebraska > 0.1237 corn- signments (two pieces of evidence), m1 and m 2 , and we want to
husker > 0.10)” and the resident semantic “(corn- combine them into a single piece of evidence. Hence, we compute
husker > 0.2000 university > 0.1200 nebraska
> 0.1138)”. Now, the first semantic component is not ∑ m1 (α )m 2 (β )
matched. The second semantic component is matched. The third
[m1 ⊕ m 2 ](Γ ) = α ∩ β =Γ
,
semantic component is partially matched: the semantic token is
matched but the comparative requirement is not fulfilled. Sup-
1− ∑ m1 (α )m 2 (β )
α ∩ β =∅
pose the number of resident semantic components is N sc , the
where Γ ≠ ∅ , and [m1 ⊕ m 2 ](∅ ) = 0 .
mass of the assertion of the above partially-matched rule is
N sc
For example, suppose after matching the semantics to our rule
∑ matched (resident con compi , query con) base, we arrive at two assertions: NU with mass 0.7 and Monet
Mass = i =1 with mass 0.2. Hence, m1 corresponds to our belief:
N sc
{NU} 0.7
If a resident semantic component is matched, then the function
Θ 0.3
matched returns 1.0. If the semantic token of a resident semantic
component is not found in the querying semantic, then the func- and m2 corresponds to our belief:
tion matched returns 0.0. If the semantic token matches but its
semantic frequency is excluded (from the range), then matched {Monet} 0.2
returns Θ 0.8
1.0 − resident con freq − query con freq Then we can compute their combination m3 using the rule of
combination above (presented as a table below):
3. DEMPSTER-SHAFER BELIEF SYS-
TEM
{NU} 0.7 Θ 0.5
{Monet} 0.2 {} 0.14 {Monet} 0.10
An agent performs two types of learning. It learns incrementally,
refining its concepts whenever there is a new submission. It also Θ 0.8 {NU} 0.56 Θ 0.40
learns collaboratively, refining its translation table whenever
there is a query that prompts the agent to ask for help from its
neighbors. The underlying problem is how to combine the vari- 3.1. Concept Disambiguation
ous assertions made by the relevant matching that we discussed Until now, after the rule-based, semantics-driven assertions and
earlier in a consistent manner. Towards this end, we incorporate the evidential combination, we arrive at a set of evidential inter-
the Dempster-Shafer theory [1] for building a belief system that vals for the propositions or concept names. For our disambigua-
tion process, we follow the two axioms of evidential interval ronment, users can still submit both queries and new experience
analysis: cases to an agent. When new experience cases are submitted, an
agent revises its concept database through the belief system in the
Axiom 1 The higher the belief and the plausibility values, the following manner. If the new experience cases are submitted with
more credible the proposition is. an existing concept name, then the agent essentially finds a trans-
Axiom 2 The closer the belief value is to the plausibility value, lation between the concept name with new experience cases (evi-
the more credible the proposition is. dence) and the concept name with old experience cases. The
credibility of the translation is then used to re-weight mass of the
Axiom 1 follows naturally from the work of the Dempster- existing semantic rules and the new rules derived from the new
Shafer theory. On the other hand, Axiom 2 punishes ignorance. experience cases. This revision is then propagated to all related
That is, if the agent thinks that a proposition is very plausible but translations in the table. On the other hand, when a query is sub-
believes with little confidence that the proposition is true, then mitted and the agent fails to recognize the concept of that query, it
the agent is ignorant about the proposition. Following from the may relay it to other agents. If another agent retrieves the relevant
above two axioms, we devise a measure of credibility of a propo- experience cases and returns them, then the originating agent
sition as: learns that new concept using the retrieved experience cases as
Pls(Γ )+ Bel (Γ )
examples, absorbing it into its concept base via belief system in a
Credibility (Γ ) = . manner similar to the aforementioned.
Pls(Γ )− Bel (Γ )
During interactions with other agents, an agent also learns to re-
During interpretation, the concept that yields the highest credibil- direct tasks and re-formulate queries for better ontology under-
ity will be the winning concept. Note that if the credibility of the standing. The fundamental mechanism that enables such behavior
winning concept is below a certain threshold, then the interpreter is through the maintenance of the translation tables in the system.
realizes that it does not understand or recognize the querying The presence of a unique translation table at each agent increases
concept. This provision prevents low-quality recognition. the autonomy of the agents in the system, allowing each to special-
ize for specific sets of queries and experience cases. Further, an
At the end of this stage, the interpreter performs one of the fol-
agent is designed to relay a query that it cannot satisfy to other
lowing: (1) If the winning concept passes the credibility test, then
agents for help. An agent may not satisfy a query when it does not
the agent supplies the querying agent with what it knows, i.e., the
recognize the query concept, or does not find a relevant match, or
experience cases under the winning concept. The translation will
does not retrieve experience cases with high relevance values, or
also be recorded in the translation tables, or (2) If the winning
does not find enough experience cases as required. As a result, the
concept fails the credibility test, then the agent turns to the trans-
agent can use its translation table to locate useful neighbors to
lator module of its system.
approach for help. If the concept query does not have a translation
but the agent does have a few lowly-relevant experience cases,
3.2. Concept Amalgamation then it will supply those to its neighbors as examples. The key of
This process is triggered by the combination of (1) the lack of a our utilization of this type of distributed learning is that each agent
credible winning concept, and (2) the existence of a credible, has its own set of concepts to facilitate query accuracy and speed.
relevant non-singleton concept structure. The objective is to Communications are only necessary when agents need help.
promote non-singleton sets of concepts, such as {Basketball, Through communications, queries are relayed and concepts are
NU}, to a recognizable concept structure. For example, suppose shared. Thus, the agents only learn necessary translations based
the set {Basketball, NU} has an evidential interval of [0.6 0.9]. on their experiences, making the learning process efficient and
Its credibility is 5.0. Suppose this passes our filter and the win- effective.
ning concept fails.
In conclusion, the belief system allows the agents to evolve their
The amalgamation process will register the conceptual complex own ontologies in the following ways: (1) infusion of new experi-
{Basketball, NU} to a complex-relevant table, together with the ence cases into the translation table via the concept hierarchies, (2)
semantics that support the complex. Further, it will record the propagation of new credibility values to all translation entries, (3)
translation and its credibility to the corresponding space under joining terms to form complex concept names, and (4) exchange of
the querying agent. concepts between agents that is based on the collaboration behav-
This provision self-motivates every agent to build and learn com- ior between the agents (traffic congestion and agent activities).
plex concepts, which in turns increases the complexity and level
of understanding among the agents with distributed ontologies. 4. REFERENCES
[1] Shafer, G. 1976. A Mathematical Theory of Evidence,
3.3. Belief System and Distributed Ontology Learn- Princeton, NJ: Princeton University Press.
ing [2] Williams, A. B. and Tsatsoulis, C. 1999. Diverse Web
Our agents conduct distributed ontology learning at different Ontologies: What Intelligent Agents Must Teach to Each
times. When an agent interacts with the user, it handles user Other, Working Notes of the AAAI Spring Symposium Series
submissions, performs inductive learning to obtain semantic on Intelligent Agents in Cyberspace, Stanford, CA, Mar 22-
rules, and builds its concept database. Since these submissions 24, 115-120.
or experience cases are received sequentially, the learning is in-
cremental. During the interaction with other agents in the envi-