=Paper=
{{Paper
|id=Vol-1492/Paper_13
|storemode=property
|title=An Approach to Ambiguity Resolution for Ontology Population
|pdfUrl=https://ceur-ws.org/Vol-1492/Paper_13.pdf
|volume=Vol-1492
|dblpUrl=https://dblp.org/rec/conf/csp/GaraninaS15
}}
==An Approach to Ambiguity Resolution for Ontology Population==
https://ceur-ws.org/Vol-1492/Paper_13.pdf
An Approach to Ambiguity Resolution for Ontology
Population ⋆
Natalia Garanina and Elena Sidorova
A.P. Ershov Institute of Informatics Systems,
Lavrent’ev av., 6, Novosibirsk 630090, Russia
{garanina,lsidorova}@iis.nsk.su
Abstract. We study a problem of information retrieval and ambiguity resolution
for ontology population. The process for retrieval of information in a form of a set
of ontology instances is presented as a Scott information system. This represen-
tation proves termination of the process. The Scott information system is a basis
for our approach to context-dependent ambiguity resolution. This system gener-
ates a multi-agent system in which agents resolve the ambiguity by computing
the cardinality of their contexts.
1 Introduction
Ontological databases are currently widely used for storing information obtained from
a great number of sources. To complete such ontologies, formalisms and methods that
allow one to automate the process are developed.
We propose to consider the process of ontology population as work with informa-
tion systems, which are concepts of the domain theory [9]. An information system is a
universal model for knowledge (ontologies, thesauri, databases, etc.) organization sys-
tems. Information systems are “syntactic” representations of the Scott domains. They
are simple, well-studied, and, in the context of ontology population, possess, in par-
ticular, useful properties of the entailment relation. In the framework of the algebraic
approach to work with ontologies, theory of Formal Concept Analysis is usually ap-
plied, which makes it possible to enrich the ontology with new concepts [2]. The Scott
domain theory was used for enriching ontologies with topological relations [4].
In this paper, we show that an ontology population system is a Scott information
system, which gives an idea of certain general properties of the population process,
in particular, a simple proof of termination of the population process and justification
of the resolution of context-dependent semantic ambiguity. Features of information re-
trieval cause ontology population ambiguities. These ambiguities arise when several
ontology instances are formed for the same input data. We use the information system
of ontology population for resolving context-depending ambiguities. We can evaluate
the cardinality of the instance contexts, i.e. how much an instance is related with the
⋆
The research has been supported by Russian Foundation for Basic Research (grant 13-01-
00643, 15-07-04144, 13-07-00422) and the People Programme (Marie Curie Actions) of the
European UnionŠs Seventh Framework Programme FP7/2007-2013/ under REA grant agree-
ment n PIRSES-GA-2011-294962-COMPUTAL.
135
other retrieved instances via the information contained in it. Thereby, the information
system of ontology population generates a multi-agent system in which agents are on-
tology instances informationally connected. They are in conflict when there is the on-
tology ambiguity for them. Agents resolve the conflict by removing the less integrated
agents with all their connections from the system. Hence the system is dynamic.
The works on multi-agent systems usually focus on the behavior of agents, methods
of communication between agents, knowledge and belief of an agent about environment
and other agents, etc [3, 10]. Works about conflict resolution process usually consider
the process in terms of the behavior of the agent depending on its internal state, reason-
ing and argumentation methods etc. [7]. The dynamics of the agents connections is not
a subject of these researches. On the other hand, there are studies on social networks,
in which agents are connected by typed connections, but their weight is irrelevant [1].
The allied approach to ontology-driven disambiguation which uses a context of a
given input text is suggested in [6]. Sequential sentence-by-sentence ambiguity resolu-
tion is performed. For every sentence, a set of semantic interpretation is constructed.
Each interpretation is represented by a graph with vertices as ontology entities and
edges as ontology relations. Every next sentence may increase scores of some interpre-
tation of the previous ones. Hence the preference of alternative meaning of words is
based on ontology relations. This approach has low accuracy because such on-the-fly
choice of alternative takes into account the nearest context mainly. Our approach uses
the maximal context available from an input text for choosing alternative. Connections
between ontology objects (class and relation instances) correspond to informational de-
pendance of the text. Since the approach does not require complete sentence parsing,
this considerably simplify the text analysis for ontology population.
We propose a multi-agent algorithm for the conflict resolution in the generated
multi-agent system of ontology instances. This algorithm is based on an idea of con-
nectivity cardinality of instance agents. On a run of the algorithm agents compute their
system weight corresponding to this connectivity. According to these weights, conflicts
are resolved by a special agent. This agent adjusts the weight computing processes and
constructing a conflict-free set of agents which is an optimal solution of a conflict res-
olution problem for a given system.
The rest of the paper is organized as follows. In Section 2, an approach to ontology
population in the framework of information systems is discussed. The next Section 3,
gives definitions for a multi-agent system for ambiguity resolution. Section 4 describes
agents of our systems, their action protocols, and the main conflict resolution algorithm.
In the concluding Section 5, directions of future researches are discussed.
2 Ontology Population and Scott Information Systems
Let we are given by an ontology of a subject domain, the ontology population rules,
semantic and syntactic model for a sublanguage of the subject domain and a data format,
and input data with information for population of the ontology. We consider an ontology
of a subject domain which includes (1) a finite nonempty set of classes for concepts of
the subject domain, (2) a finite set of named binary relations on the classes, (3) a finite
set of attributes, and (4) a finite set of data types. Every class is defined by a tuple of
136
typed attributes. Every relation is defined by a couple of classes and a tuple of typed
attributes. Information content of an ontology is a set of class instances and relation
instances defined on these class instances.
Ontology population problem is to compute information content for a given ontol-
ogy from given input data. A mapping of input data to the ontology has to be a one-
to-one correspondence, i.e. different ontology instances correspond to different data
fragments. Rules for ontology population and data processing determine ontology in-
stances in input data, and evaluate their attributes. Determination of the information
content includes the following stages. First, input data are matched to characters of
attributes, classes, and relations of the ontology. These matchings are predefined and
depend on an input data format. Initial ontology instances are formed using obtained
ontology characters independently from each other. At this stage the instances are not
determined completely, because information, which is necessary for evaluating their
attributes and establishing relations, frequently places at isolated parts of input data.
This information is usually stored in different ontology instances. At the second stage
initial instances are formed consistently and completely (as much as possible), i.e. in-
formation from some instances could be used for evaluating other and for defining new
ontology instances. Rules for ontology population and data processing define informa-
tionally connected instances. In paper [5] multiagent algorithm for the second stage is
presented. In a process of instance determination, some ambiguities are possible when
several ontology instances are formed for the same data fragment. These ambiguities
can be caused by homonymy, references, etc. The problem of ambiguity resolution is
solved at the third stage. This paper suggests an approach for the solving. At the forth
stage ontology population itself is performed. Computed instances could be included
into the (possibly nonempty) ontology informational content. At this stage possible in-
consistences and ambiguities related to instances in the content should be processed.
We suggest to consider the second stage of the ontology population process as work
with Scott information systems. A Scott information system T is a triple (T, Con, ⊢),
where
– T is a set of tokens and F in(T ) is a set of finite subsets;
– Con is a consistency predicate such that Con ⊆ F in(T ), ∅ ⊢ Con and
1. Y ∈ Con and X ⊆ Y ⇒ X ∈ Con,
2. a ∈ T ⇒ a ∈ Con;
– ⊢ is an entailment relation such that ⊢⊆ Con × T and
3. X ∈ Con and X ⊢ a ⇒ X ∪ {a} ∈ Con,
4. X ∈ Con and a ∈ X ⇒ X ⊢ a,
5. ∀b ∈ Y : X ⊢ b and Y ⊢ c ⇒ X ⊢ c.
An ontology population system based on an ontology, input data, and the ontology
population and the data processing rules, could be defined as a triple (Aop , Conop , ⊢op ).
Set of tokens Aop is a set of all (underdetermined) ontology instances formed by the
rules in the determination process of initial instances:
– class instances a, . . . of form (Classa , Atra ),
– Atra are values of attributes of class Classa containing:
grammar information (morphological and syntactic features), and
structural information (position in input data);
137
– relation instances r, . . . of form (Relationr , (o1 , o2 )r , Atrr )
– (o1 , o2 )r are instances of classes related by the relation Relationr ,
– Atrr are values of attributes of the relation Relationr containing
grammar and structural information.
For every X ⊆ A let X = XC ∪ XR , where XC is a set of class instances and XR is a
set of relation instances.
Consistency predicate Conop and entailment relation ⊢op correspond to the rules of
ontology population and data processing. Let x, x′ ∈ Aop , o ∈ AC , and X ⊆ Aop . The
entailment relation connects informationally associated tokens:
– X ⊢op x, iff x ∈ X, or x ∈ / X ∧ ∃y ∈ XR : x ∈ Oy , or x ∈ / X ∧ (Atrx = ∅ ∨
Atrx = ∪{α | ∃x′ ∈ X : α ⊆ Atrx′ }) ∧ (x ∈ AR → (Ox = ∅ ∨ ∀o ∈ Ox : X ⊢op o)),
i.e. instance x is entailed from X, if (1) it is in this set, or (2) it is an object of some
relation from this set, or (3) information from tokens of this set is used for evaluating
attributes or objects of x, and x does not include other information.
The consistency predicate determines informationally bound sets of tokens:
– X ∈ Conop , if ∃x ∈ Aop : X ⊢op x, i.e. a set of instance-tokens is consistent, if
it entails (new) instance;
– ∅ ∈ Conop .
Set X is nontrivial consistent, if ∃x ∈ / X : X ⊢op x, i.e. the set entails not only its
elements and x is nontrivially entailed. An information order relation ≺ is defined on
class and relation instances. Let a, a′ ∈ AC and r, r′ ∈ AR :
– a ≺ a′ , if a = a′ everywhere except for at least one attribute, with the
number of values of this attribute in a being strictly less than that in a′ ;
– r ≺ r′ , if r = r′ everywhere except for (1) at least one object and/or
(2) at least one attribute, with the number of values of this attribute in r
being strictly less than that in r′ .
For token x ∈ Aop : if x ≺ x′ , then x′ is information extension of x, and x↑ = {x} ∪
{x′ | x ≺ x′ }, x↓ = {x} ∪ {x′ | x′ ≺ x} are upper and down cones of x.
Theorem 1. Triple (Aop , Conop , ⊢op ) is a Scott information system.
Proof. Let us show that the consistency predicate Conop and the entailment relation
⊢op satisfy properties 1–5 of information systems.
1. Y ∈ Conop and X ⊆ Y ⇒ X ∈ Conop . For trivial consistent sets the proposition
is obvious. Let Y is nontrivial consistent: Y ⊢op z, z ∈
/ Y . Then ∃z ′ ∈ z ↓ : X ⊢op z or
X is trivial consistent, hence X ∈ Conop .
2. a ∈ Aop ⇒ a ∈ Conop . {a} ⊢op a, hence {a} ∈ Conop .
3. X ∈ Conop and X ⊢op a ⇒ X ∪ {a} ∈ Conop . X ∪ {a} is trivial consistent.
4. X ∈ Conop and a ∈ X ⇒ X ⊢op a. By the def. of the entailment relation.
5. ∀b ∈ Y : X ⊢op b and Y ⊢op c ⇒ X ⊢op c. For trivial consistent sets the propo-
sition is obvious. Let sets X and Y are trivial consistent. Set Y includes information
from instance-tokens of X only, hence token c does not include information more than
in X, hence X ⊢op c. Formally: Y ⊢op c, if c ∈ / Y ∧ (Atrc = ∅ ∨ Atrc = ∪{α | ∃b ∈
Y, X ′ ⊆ X : α ⊑ Atrb ⊑ ∪x∈X ′ Atrx }) ∧ (c ∈ AR → (Oc = ∅ ∨ ∀o ∈ Oc : o ∈
Y ∨ X ⊢op Y ⊢op o)), hence X ⊢op c.
The proposition below directly follows from monotonicity of the entailment relation
and finiteness of input data.
138
Proposition 1. Ontology population process terminates.
Let us define a closure of an entailment relation: X ⊢∗ x iff ∃y ∈ A, Y ⊆ A :
X ⊢ y ∧ Y ∪ {y} ⊢∗ x. An information state of set of token X ⊆ A is all tokens
(all information) that can be obtained from this set by the entailment relation: F (X) =
{x|∀Y ⊆ F in(X) and Y ⊢∗ x)}. A projection of information state of set X to token
a ∈ X is all tokens that can be entailed from this set using this token: F (X, a) =
{x|∀Y ⊆ F in(X) : a ∈ Y and Y ⊢∗ x)}. Let a context of token a be F (a) =
{X | a ∈ F (X)} ∪a∈X F (X, a). Intuitively, a context of a is a set of token which
includes all tokens necessary for the token entailment and all tokens entailed using the
token. In the ontology population framework a context of an instance-token can be used
for resolution of context-depending ambiguity. Suppose that there are two instance-
tokens that are at the same position of input data. The ontology can be populated with
only one of them. Obviously, we prefer the token that is more closely related to the
other information obtained from the input data. This is the token that possesses a more
powerful context which uses nontrivial entailment relations only.
Hence, the problem of context-depending ambiguity resolution is reduced to the
problem of computing the cardinality of contexts for competing instance-tokens. We
show that an information system of ontology population generates a special multi-agent
system with typed connections. Agents of the system resolve the ambiguities by com-
puting and comparing the context cardinalities.
3 A Multi-agent System of Ambiguity Resolution
Let a set of maximal determined instances, which is the result of the analysis of input
data, be A↑op = {x ∈ Aop | x↑ = {x}}. For every x ∈ / A↑op the corresponding maximal
determined instance is x̃ such that x̃ ∈ A↑op ∧ x ≺ x̃.
Entailment relation ⊢op generates information connections between maximal deter-
mined instances. Let X ⊢op x and y ∈ X ∧ y ⊀ x. Then
– attribute connections between ỹ and x̃ are
α
– ỹ −→ x̃ iff ∃α ∈ Atry : α ∈ Atrx ;
αtut
– of tutorial type ỹ −→ x̃ iff ∃x′ ∈ X : x′ ≺ x;
αpar
– of parental type ỹ −→ x̃ iff ∄x′ ∈ X : x′ ≺ x;
– object connections between ỹ and x̃ are
y
– ỹ −→ x̃ iff x ∈ AR ∧ (y ∈ XC ∧ y ∈ Ox ∨ y ∈ XR ∧ ∃oy ∈ Oy : oy ∈ Ox );
y par
– of parental type ỹ −→ x̃.
Information system (Aop , Conop , ⊢op ) generates Multi-agent System of Ambiguity
Resolution (MASAR) as a tuple S = (A, C, IC , TC ), where
– A = {ax | x ∈ A↑op } is a finite set of agents corresponded to maximal determined
instances;
α x
– C = {α | ∃x, y ∈ Aop : x̃ −→ ỹ} ∪ {x | ∃x, y ∈ Aop : x̃ −→ ỹ} is a finite set of
connections;
– mapping IC : C −→ 2A×A is an interpretation function of (ordered)
c
connections between agents: IC (c) = (ax , ay ) iff x̃ −→ ỹ;
139
– mapping TC : C ×2A×A −→ {tut, par} is types of connections: T (c, ax , ay ) = r
cr
iff IC (c) = (ax , ay ) → (x̃ −→ ỹ), r ∈ {tut, par}.
For every agent a ∈ A we define the following sets of agents and connections.
The similar definitions are used in the graph theory, but we would like to reformulate
them for the clarity. We omit symmetric definitions of ancestors Anc∗ (for Des∗) and
predecessors P red∗ (for Succ∗) for the brevity: W
– Ca = {c ∈ C|∃a′ ∈ A : (a, a′ ) ∈ IC (c) (a′ , a) ∈ IC (c)} is connections of a;
– Desca = {a ′
S ∈ A | (a, a′ ) ∈ IC (c)} is a set of descendants by c connection;
– Desa = c∈Ca Des S a is a set of descendants;
c
– Succca = Desca ∪ a′ ∈Desca Succca′ is successors by c connection;
S
– Succa = c∈Ca Succca is a set of successors.
MASAR is a multiagent system of information dependencies. In these systems agents
can use information from predecessors and can pass the (processed) information to
successors. Hence Succca ∩ P redca = ∅, i.e. every connection has no cycle because of
information transfer. Note, that in MASAR every agent has one ancestor at the most.
The weight functions for agents should correspond to information worth of agents and
their connectivity with other agents. Let P rt ∈ {Des, Anc}. For every a ∈ A mapping
– wtaP rt : C −→ N is the weight function of connection descendants (ancestors)
P ′ P
wtP rt (c) = a′ ∈P rtca wtaP rt (c) + 1, and wtP rt (a) = c∈Ca (wtaP rt (c) − 1);
a
– wt : A −→ N is the weight function of information agents defined by wt(a) =
wtDes (a) + wtAnc (a) + 1. P
Weight of system S is wt(S) = a∈A wt(a).
Let conflict set Conf ⊆ A × A be a set of unordered conflict pairs of agents
corresponded to informational objects formed for the same data fragments. For every
pair of agents from Conf we say that a conflict is resolved if one of the agents in the
pair called the minor agent deletes itself from A (with all its connections) and involves
all its descendants. Every descendant involved performs the following conflict actions:
(1) if the involving connection is of the parental type then it deletes itself from A
(with all its connections) and involves all its descendants;
(2) if the involving connection c is of the tutorial type then it deletes all outgoing
connections c, and involves its descendants connected by the connections.
Note that all successors of the minor agents are involved in its conflict resolution. A
conflict pair of agents is deleted from Conf after conflict resolution. Conflict actions
decrease the weight of all successors and predecessors of a conflicting agent. The first
conflict action reduces the conflict set and the set of agents in MASAR. Hence the
system is dynamic due to conflict resolution. Change of the system weight with the
fixed weight function depends on a policy of conflict actions for every agent. Problem
of conflict resolution in MASAR is to get a conflict-free MASAR of the maximal weight.
We develop a multiagent algorithm that produces such system.
4 Conflict Resolution in MASAR
For constructing the conflict-free multiagent system of the maximal weight by resolving
a chain of conflicts we should know how much each conflict resolution step affects to
140
the system weight. For every agent in conflict, it is necessary to compute its conflict
weight which is the difference between the system weight before and after the agent
conflict resolution. Distributed computing of this weight takes polynomial time.
Action protocols for conflict resolution used by MASAR agents forms a multi-agent
system of conflict resolution MACR. The system MACR includes set of MASAR agents
and an agent-master. Note, that a fully distributed version of our algorithm could be de-
veloped but it should be very ineffective. The result of agent interactions by protocols
described below is the conflict-free MASAR. All agents execute their protocols in paral-
lel until the master detects termination. The system is dynamic because MASAR agents
can be deleted from the system.
The agents are connected by synchronous duplex channels. The master agent is con-
nected with all agents, MASAR agents are connected with their ancestors and descen-
dants. Messages are transmitted instantly via a reliable medium and stored in channels
until being read.
Let A = {a1 , ..., an } be a MASAR agents set, and M be the master agent. Let
Ai be an interface protocol of agent ai , and M be the protocol of actions of the agent-
master M . Then multi-agent conflict resolution algorithm MACR can be presented in
pseudocode as follows:
MACR:: parallel {A1} ...{An} {M}
Our algorithm for constructing a conflict-free MASAR of the maximal weight is
a greedy algorithm. At every step it chooses for resolution a conflict which has the
maximal effect to the system weight. This effect depends on conflict actions of involved
agents. Hence the following algorithms should be implemented: calculating of agents’
weights, calculating of agents’ conflict weights, the main algorithm for constructing a
conflict-free set of agents of the maximal weight. Calculating the weights should be
performed by MASAR agents, but constructing a conflict-free set should be conducted
by the master agent.
We define an interface protocol Ai for system agents, which specifies agent’s re-
actions for incoming messages. These messages include information which protocol
Act (to perform a conflict action) or ChangeWeight (to change its weight) should be
run and their parameters described below at the protocols’ definitions. Until an input
message cause an agent to react the agent stays in a wait mode.
Interface protocol of agent a.
Ai (a) ::
set of msg Input; msg mess=(start,∅);
1. while ( mess.act != Stop )
2. if( Input != null ) then {
3. mess = get (Input);
4. if( mess.act = ToAct ) then Act(mess);
5. if( mess.act = ToChange ) then ChangeWeight(mess);}
(1) The main algorithm for conflict resolution
Let us give an informal description of protocol Master. Let DelA be set of agents re-
moved from A due to particular conflict resolution, P artConfa = {b ∈ A|(a, b) ∈
Conf } be a set of agents in conflict with a and ConfA = {a ∈ A|∃b ∈ A(a, b) ∈
Conf } be a set of agents in a conflict. Until the latter set becomes empty the following
141
steps repeat: (1) to compute of agents’ weights by launching agents to perform proto-
cols WeightCount in parallel, (2) to compute of agents’ conflict weights by launching
conflict agents to perform protocols Start in sequence, (3) to find the minor partner
of the agent of maximal impact for the system weight, with the maximal difference in
their conflict weights, (4) to change the weights of agents involved by this agent by
launching the minor agent to perform protocol Start, (5) to remove the conflict of the
agent and conflicts of deleted agents from the conflict set and (6) to recalculate the set
of agents in conflicts. We consider the master can detect termination moments of other
agents’ parallel computations at every step. The protocol of conflict weights comput-
ing and weights changing belongs to the class of wave echo algorithms [8]. Let function
max_wConf(X) (min_wConf(X)) returns the agent of the maximal (minimal) conflict
weight in set of agents X.
Protocol of the master agent for conflict resolution.
Master ::
agent a, b;
1. while ( ConfA 6= ∅ ){
2. forall a∈ A in_parallel WeightCount(a);
3. forall a∈ ConfA in_sequence Start(a, true);
4. a = max_wConf( ConfA ); b = min_wConf( P artConfa );
5. Start(b, false);
6. Conf = Conf \ {(a, b)};
7. forall c∈ DelA Conf = Conf \ {(c, d) | d ∈ P artConfc };
8. recalculate(ConfA );}
9. forall a∈ A in_parallel send ( Stop ) to a;
(2) Computing agents’ weight
Let the set of connection of agent a is Ca = {c1 , . . . , cn }. Following the definitions
of the weights the agent launches in parallel calculations of the sum weight by ev-
ery connection ci for successors CiDes and for predecessors CiAnc (line 1) and stores
calculated weights in arrays w_Des and w_Anc respectively. When these parallel cal-
culations are finished, the agent computes its own weight (lines 2–3). The calculation
processes have local channels Input for messages with integer weights of successors
(predecessors). They send the weights increased by 1 to predecessors (successors) re-
spectively. We omit the similar description of predecessors’ processes CiAnc for the
brevity. All these agent’s weights are accessible to the agent for changing in its other
protocols.
Protocol of agent a for weight compute.
WeightCount (a) ::
array [n] of int: w_Des, w_Anc; int w_Des_own, w_Anc_own;
1. parallel {C1Des}P {C1Anc} ... {CnDes} {CnAnc}
P
2. w_Des_own = i∈[1..n] w_Des[i]; w_Anc_own = i∈[1..n] w_Anc[i];
3. wt_A = w_Des_own + w_Anc_own + 1;
CiDes() ::
set of int Input; NumD = |Descai |;
1. w_Des[i] = 0;
2. while( NumD != 0 )
142
3. if ( Input != null ) then {
4. w_Des[i] = w_Des[i] + get( Input ); NumD = NumD - 1;}
5. forall (b in Anccai ) send w_Des[i]+1 to b;
(3) Computing agents’ conflict weight
The next protocol is performed by the agent which starts to compute its conflict weight
(wc=true) or is the minor agent (wc=false). It performs conflict action 1 launching
a wave of weight changing of successors and predecessors and initiates actions of in-
volved agents in protocol Act in line 2. Before the wave starts, agents restore its initial
weights and the presence status in line 1. If there is real system change (not conflict
weight computing) then all agents change their weight in line 3. Let wta be integer
temporal weight of agent a, and boolean variable a.Rmvd be true if a is removed by its
conflict action 1, and false in other case.
Protocol of initial agent a
Start(a, wc) ::
1. forall b ∈ A wtb =wt(b); b.Rmvd = false;
2. Act(1, ∅, ∅, wc);
3. if (not wc) forall b ∈ A wt(b)=wtb ;
An input for protocol Act is a message of the form mess = (ct, x, c, wc),
where ct is conflict action type, x is an agent which activate this action, c is a connec-
tion with this agent, and wc is true if a conflict weight is computing. In this protocol
(lines 1–2) an agent depending on the type of its conflict action (1) determines the dif-
ference of own weight, (2) forms sets of descendants and ancestors which weights are
changing due to this action, and (3) specifies the amount of these changes in variable w.
Then the agent sends the corresponding messages to the partners (lines 7) launching a
wave of weight changing of its successors and predecessors and waits when it finishes
(line 8). Further the agent depending on its conflict type launches a wave of conflict
actions of its successors (lines 9,10) and waits when it finishes (line 11). The agent has
local channel Input for messages with integer conflict weights of involved successors.
In line 13 the agent sums these weights. Let function i(c) returns index of connection
c in set Ca for agent a, ActId = {1, 2} be a set of indexes of conflict actions, and
C1a = {a′ | ∃c : T (c, a, a′ ) = par} and C2a = {a′ | ∃c : T (c, a, a′ ) = tut} be sets of
agents immediately involved in a conflict by agent a to perform action 1 or 2.
Protocol of agent a for conflict actions.
Act( mess = (ct, x, c, wc) ) :: {
int w, wConf, wConfTmp; agent b; connection c;
set of agents Desa, Anca; set of int Input; ActId i;
1. if ( ct = 1 ) then Desa = Desa ; Anca = Anca ; wConf = wt_A;
2. if ( ct = 2 ) then Desa = Desca ; Anca = Ancca ;
wConf = w_Des[i(c)]+w_Anc[i(c)];
3. forall b∈Desa∪Anca {
4. c = (a,b);
5. if b∈Desa then Rel = Anc; w = w_Anc[i(c)];
6. else Rel = Des; w = w_Des[i(c)];
7. send (ToChange, delMe, a, c, w, Rel) to b;}
8. wait (doneWt) fromall b;
143
9. while( Input != ∅ ) wConf = wConf + get( Input );
10. if( ct = 1 ) then forall i∈ActId forall b∈ Cia
send (ToAct, i, a, (a,b), wc) to b;
11. if( ct = 2 ) then forall i∈ActId forall b∈ Cia ∩ Desca
send (ToAct, i, a, c, wc) to b;
12. wait (doneAct) fromall b;
13. if ( wc ) then {
14. while( Input != null ) wConf = wConf + get( Input );
15. if ( x != null ) then send (doneAct, wConf) to x;}
16. else A = A \ {a}; }
An input for the next protocol is a message of the form mess = (act, x, c,
w, Rel), where act specifies should the agent a remove (act=delMe) agent x from
its ancestors (Rel = Anc) or descendants (Rel = Des) by connection c (lines 2,5).
The agent decreases its corresponding weights by w. Decreasing of the weight affects
weights of its successors and predecessors. The agent initiates the changing of these
weights in line 8 and waits when it finishes (line 9).
Protocol of agent a for its weight changing.
ChangeWeight( mess = (act, x, c, w, Rel) ) :: {
int w; agent b; set of agents Parts;
1. if( Rel = Anc ) then w_Anc[i(c)] = w_Anc[i(c)] - w;
2. if( act = delMe ) then Ancca = Ancca \ {x};
3. Parts = Desca ;
4. else w_Des[i(c)] = w_Des[i(c)] - w;
5. if( act = delMe ) then Desca = Desca \ {x};
6. Parts = Ancca ;
a a
7. wt = wt - w;
8. forall b∈Parts send (ToChange, decMe, a, c, w, Rel);
9. wait (doneWt) fromall b∈Parts;
10. while( Input != ∅ ) wta = wta + get( Input );
11. send (doneWt, wta ) to x; } }
Consider now the performance of the conflict resolution algorithm in a particular
case of ambiguity in the following sentence:
On October 22, 2013, an official ceremony was held in the Nenets Autonomous
District to mark the start of pilot oil production at the A. Titov field.
We consider Energetics as an ontology subject domain. Thesaurus of this subject
area among others should contain single-word terms pilot, oil and production together
with multi-word terms pilot oil and oil production. Thus the ambiguity in the example
above is the following:
[ [ pilot [ oil production ] ] ←→ [ [ pilot oil ] production ] ]
During the multiagent algorithm initialization for the above sentence the follow-
ing lexical objects L1–L5 is created with semantic attributes from the thesaurus (see
Fig. 1). As a result of main stage of multiagent algorithm by the means of rule-agents
implementing search of information concerning activities related to the oil production,
an informational agents I1–I4 and R1–R3 corresponding to the ontological classes and
relations is created.
144
Fig. 1. An example of conflicting agents.
Thus the main stage of the analysis in our example results in the following list
of ambiguity conflicts: (L1,L2), (L2,L3), (L3,L4), (I1,I2), (I3,I4), (R1,R2). Calculated
weights of agents are also depicted at Fig.1. The conflict resolution algorithm deletes
agents L2, I1, and R1 at the first iteration, and L4 and I4 at the second one. The result
of the algorithm is the set of information agents I2, I3, I5, R2, and R3. Thereby all
remaining conflicts are resolved automatically.
5 Conclusion
In this paper, we show that instances of the ontology classes and relations that take part
in the process of population form, together with the rules of data processing and ontol-
ogy population, a Scott information system. This results in a simple proof of termination
of the population process and justification of the resolution of context-dependent ambi-
guity of instances by calculating their context cardinalities. The Scott information sys-
tem is a basis for our approach to context-dependent ambiguity resolution. This system
generates a multi-agent system in which agents resolve the ambiguity by computing the
cardinality of their contexts. The suggested algorithm of ambiguity resolution chooses
the most powerful agents and removes their competitors. The choice is based on agents’
weights and their impact on the system in the process of ambiguity resolution.
In the near future we plan to give formal proofs of correctness of the algorithm
proposed and to estimate its time complexity. In a development process of our multi-
agent system of the semantic analysis of natural language texts for ontology population,
we intend to carry out integrated testing and to rate quality of these algorithms in terms
of completeness and soundness.
145
References
1. Bergenti F., Franchi E., Poggi A.: Selected models for agent-based simulation of social net-
works // In: Procs. 3rd Symposium on Social Networks and Multiagent Systems (SNAMAS
2011) 2011, pp. 27-32.
2. Cimiano P., Hotho A., Stumme G., Tane J.: Conceptual Knowledge Processing with Formal
Concept Analysis and Ontologies // Proc. of 2nd Conference on Formal Concept Analysis
(ICFCA 2004). LNCS Vol. 2961, 2004, pp 189-207.
3. Fagin R., Halpern J.Y., Moses Y., Vardi M.Y.: Reasoning about Knowledge. MIT Press, 1995.
4. Fernhdez-Breis J.T., et all: Towards Scott Domains-Based Topological Ontology Models:
An Application to a Cancer Domain // In Proc. of the Conference on Formal Ontology in
Information Systems (FOIS ’01). ACM, 2001, p. 127–138.
5. Garanina N., Sidorova E., Bodin E.: A Multi-agent Approach to Unstructured Data Anal-
ysis Based on Domain-specific Onthology // Proc. of the 22nd International Workshop on
Concurrency, Specification and Programming, Warsaw, Poland, Sept. 25-27, 2013. CEUR
Workshop Proceedings, Vol-1032, p. 122-132
6. Kim D.S., Barker K., Porter B.W.: Improving the Quality of Text Understanding by Delay-
ing Ambiguity Resolution // Proc. of the 23rd International Conference on Computational
Linguistics (Coling 2010), Beijing, August 2010. pp. 581Ű-589
7. Huhns M. N., Stephens L. M.: Multiagent Systems and Societies of Agents // In: Multiagent
Systems, MIT Press, 1999 pp. 79–120.
8. Tel G.: Introduction to Distributed Algorithms. Cambridge University Press, 2000.
9. Winskel G.: The Formal Semantics of Programming Languages: An Introduction. MIT Press,
1993.
10. Wooldridge, M.: An Introduction to Multiagent Systems. Willey&Sons Ltd, 2002.