We suggest an approach to resolution of context-dependent lexical and syntactic ambiguity in a framework of ontology population from natural language texts. We show that a set of maximally determined ontology instances can be represented as a Scott information system with an entailment relation as a collection of information connections. Moreover, consistent primary lexical instances form FCA-concepts. These representations are used to justify correctness of lexical disambiguation and to de ne syntactic ambiguity and its resolution. This information system generates a multi-agent system in which agents resolve the ambiguity of both types.
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. Features of
automatic information retrieval cause ontology population ambiguities. In
linguistics several kinds of ambiguities are considered: lexical, syntactic, semantic, and
pragmatic [2]. In a process of ontology population from natural language texts we
use our algorithms [5] in which the following ambiguity types appear: (
In [6] we demonstrated that the process of retrieval of information in a form of a set of ontology instances can be presented as a Scott information system [13].
This process produces maximally determined instances for ontology population. In this paper we prove that consistent sets of instances and lexical objects which values assign attributes of these instances form FCA concepts [3]. This fact grantees that information states of ambiguous con icting agents do not intersect. This implies correctness of lexical disambiguation.
Besides, now we use a representation of ontologies which does not consider ontology relations as special structures. Only classes are allowed in these ontologies, and relations are represented as special attributes of classes. Well-known ontology representation language OWL uses the notation of this kind. This representation is a good solution for speci cation of polyadic relations. Our algorithms for ontology population are simpler with this representation because class and relation instances are packed in the same item.
Automatic techniques of disambiguation usually do not use an input data context in full. This can lead to incomplete and incorrect ambiguity resolution [1, 9, 8, 7]. Our approach tries to ease these drawbacks. For disambiguation we use a distributed approach. Every retrieved instance is related to agent. These agents detect and resolve ambiguities with help of a special master agent. This approach takes polynomial time for disambiguation.
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. Section 3 describes lexical and syntactic disambiguation in terms of the system de ned in the previous section. The next Section 4, gives de nitions for a multiagent system of context-dependent ambiguity resolution. Section 5 informally describes agents of our systems, their action protocols, and the main con ict resolution algorithm. In the concluding Section 6, directions of future researches are discussed. 2
Let we be given 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 as a nite natural language text with information
for population of the ontology. We consider ontology O of a subject domain
which includes (
The information retrieval system based on an ontology, nite input data, and rules of the ontology population and the data processing is de ned as a triple R = (A; Con; `). Set of tokens A consists of a set of all (underdetermined) ontology p-instances formed by the rules in the determination process of initial p-instances which are retrieved from an input text by the special preprocess. Every p-instances a 2 A has form (ca; Data; Rela; Pa), where { class ca 2 CO, and { every data p-attribute a 2 Data is of form ( ; IV ), where { name 2 Datca , where { its information values v 2 IV has form (vv; gv; sv) with { data value vv 2 d , a set of all values of is V al a = fvv j v 2 IV g, { gv is grammar information (morphological and syntactic features), and { sv is structural information (position in input data); { every relation p-attribute a 2 Rela is of form ( ; O a ), where { a name 2 Relca , and { every o 2 O a has form (o; po), where { o is an instance of class c a , and { po 2 Po is its position, { a set of all relation objects of a is O(Rela) = fag [ a2Rela fojo 2 O a g; { Pa is structural information (a set of positions in input data). We consider a special set of tokens: a set of lexical objects LO corresponding to values of data attributes retrieved from input data. Every lexical object is a p-instance which has only a single data attribute with a single information value. P-instances correspond to ontology instances in a natural way. Let a = (ca; Data; Rela; pa) be p-instance, then its corresponding ontology instance is a0 = (ca; Data0 ; Rela0 ), where every 2 Data0 has value(s) in V al a and every 2 Rela0 has value o with (o; po) 2 O a . Further we omit pre x \p-" if there is no ambiguity. An information order relation is de ned on ontology instances. Let a; a0 2 A: a a0, if a = a0 everywhere except for at least one attribute, with the number of values of this attribute in a being strictly less than that in a0. For x; x0 2 A: if x x0, then x0 is information extension of x.
Rules of ontology population and data processing Rules = frule1; : : : ; ruleng map nite sets of instances of ontology classes to an instance which is an informational extension of some instance of the domain set or a new instance. This sets must be linguistically and ontologically compatible: speci ed sets of their attributes and some instances have to satisfy conditions on values, grammatical and structural information [10]: rulei : Domi 7! A, Domi 2A, such that 8X 2 Domi : LingConsi([x02X Datx0 [ Relx0 ) = true ^ 8x0 2 X : cx0 2 Classi, where predicate LingConsi and set of classes Classi CO detect linguistic and ontological compatibility of the instance set, correspondingly. Let for X 2 Domi; x 2 A: rulei(X) = x i ((9y 2 X : y x^cx = cy)_(8y 2 X : y x^cx = geni(X)))^ (Datx = ; _ Datx = [ ( ; [f(fi(V ); gi(V ); si(V )) j 9Y X : dat \y2Y Daty ^ V = [ 2dat fvjv 2 IV gg)) ^
(Relx = ; _ 8o 2 O(Relx) : o 2 X [y2X O(Rely)), where geni(X) generates a new class for a new instance, fi(V ) produces a value based on values in (V ) for an attribute of instance x, and gi(V ) and si(V ) inherit grammatical and structural information from set of information values V .
Consistency predicate Con and entailment relation ` correspond to the rules of ontology population and data processing. Let x; x0 2 A and X A. The entailment relation connects informationally associated tokens: { X ` x, i x 2 X, or x 2= X ^
((9X0 X; X00 A; rulei 2 Rules : rulei(X0 [ X00) = x) _ (9x0 2 A; X00 A; rulei 2 Rules : X ` x0 ^ rulei(fx0g [ X00) = x)), i.e. instance x is entailed from X, if it is in this set, or information from tokens of this set is used for evaluating attributes of x.
The consistency predicate de nes informationally consistent sets of tokens: { X 2 Con, i for some rulei 2 Rules holds 8X0 X([x02X0 cx Classi) ) (9x 2 A; X00 A : rulei(X0 [ X00) = x), i.e. if there exists some rule which can nd in a set of tokens some instances satisfying its class compatibility then these instances should be consistent with some other set of tokens with respect to the rule. Class compatible, but linguistically incompatible sets cannot be processed by rules, hence we do not consider them consistent.
Let us prove the following theorem for the system R: Theorem 1. Triple R = (A; Con; `) is a Scott information system. Proof. Let us show that the consistency predicate Con and the entailment relation ` satisfy properties 1{5 of information systems.
1. Y 2 Con and X Y ) X 2 Con. This fact follows from the de nition of the consistency predicate directly because the condition of de nition should hold for every subset of a consistent set.
2. a 2 A ) fag 2 Con. By the de nition for every rulei 2 Rules the class of a is not included in Classi or single fag can be complemented by some set of tokens in such a way that the rulei produces a new token.
Proposition 1. Information retrieval process of ontology population terminates.
For token x 2 A: x" = fxg [ fx0 j x x0g and x# = fxg [ fx0 j x0 xg are upper and down cones of x. Let a set of maximally determined instances (maximal instances or tokens), which is the result of the analysis of input data, be A" = fx 2 A j x" = fxgg. These instances may populate an ontology. Obviously, Proposition 2. Triple I = (A"; Con; `) is a Scott information system.
An information descendants of token a 2 A" are all maximal tokens (all information) that can be obtained from this token by the entailment relation: Ds(a) = fx 2 A"jfag ` xg. An information ancestors of token a 2 A" are all maximal tokens from which a can be obtained: An(a) = fx 2 A"jfxg ` ag. In our framework for lexical objects the following equality holds: An(a) = fag because ontology instances are based on retrieved lexical objects. Information descendants are a particular case of Scott information states [14]. Like in the cited paper, we show that tokens from LO and their information descendants form a concept lattice.
Proposition 3. Consistent sets of lexical objects form FCA concepts. Every consistent set of instances is a base for FCA concepts.
Proof. Let every set x of information descendants of LO be an object, and every l 2 LO be an attribute. Lexical object l is an attribute of x i l 2 x. The extension of a set of attributes L LO is the set L0 = fxjL xg and the intension of L0 is the set flj8x 2 L0; l 2 xg. L is a concept i the condition on the intension of the extension of L holds: L = flj8x 2 L0; l 2 xg i L is an information state of information system I i L is a consistent set. The intension of a set of infostates X is the set X0 = flj8x 2 X; l 2 xg and the extension of X0 is the set fxjX0 xg. X is a concept i the condition on the extension of the intension of X holds: X = fxjX0 xg i a set of all instances in set of infostates X forms an infostate too: Xi = fa j a 2 x 2 Xg, hence Xi is a consistent set. Hence every consistent set of instances is a base for FCA concepts. 3
(
Let l; l0 2 LO be in a con ict l ! l0 i s(l) \ s(l0) 6= ;. Let set AmbLO be a set of con ict lexical objects and Lex be a set of their descendants. We consider that rules in Rules cannot generate instances which include inconsistent information. I.e. for every rulei 2 Rules holds 8X 2 Domi; a; a0 2 X; l; l0 2 An(a) \ An(a0) \ LO : :(l ! l0). Hence for lexical objects l and l0 in con ict: Ds(l) \ Ds(l0) = ;.
For the lexical disambiguation of two con icting lexical objects we prefer a
lexical object which is more incorporated in an input text than its competitor.
For l; l0 2 LO if jDes(l)j > jDes(l0)j we take l for evaluating attributes of
ontology instances and ignore l0.
(
Detection of syntactic ambiguity frequently requires analysis of homogeneous groups. Syntactic ambiguity is de ned for ontology instances, not for lexical objects. Our types of syntactic ambiguity can depend on an ontology speci cation, hence here we consider syntactic-semantic ambiguity really. We omit \-semantic" for the brevity. Syntactic ambiguity usually can be expressed by corresponding single lexical object to several ontology items in various ways. For disambiguation it is necessary to nd in an input text an evidence of correctness of the correspondence. This could be performed using the following inequalities.
For every instance a and its data attribute 2 Data a set of information
values equal to v 2 d is EQ(a; ; v) = fv 2 IV j vv = vg. For every instance
a and its relation attribute 2 Rela a set of relation objects with an instance
equal to e 2 c a is EQ(a; ; e) = f(o; po) 2 O j o = eg. A power of these
sets is an evidence power. A triple (a; ; v) denotes information value v 2 IV
of data attribute 2 Data of instance a. A couple (a; ) denotes a value of
relation attribute 2 Rela of instance a. A set of information values which e ects
on (a; ; v) is V (a; ; v) = f(c; ; w) j 9rulei 2 Rules; X A" : rulei(X) =
a ^ c 2 X ^ 2 dat \ Datc ^ w 2 IV ^ v = (f (V ); g(V ); s(V ))g. A set of
instances which e ects on (a; ) is I(a; ) = fe 2 A" j 9rule 2 Rules; X A" :
rule(X) = a ^ e 2 X ^ O \ O(Rele) 6= ;g. Now we de ne a method of syntactic
disambiguation.
(
In a case of equalities of evidence powers the con ict is not resolved. We consider systems in which all these ambiguities are independent, i.e. pairwise intersections of sets Lex, Synt11, Synt12, Synt112 and Synt211 are empty. Informal description of action protocols for instance agents presents resolution of independent lexical and syntactic ambiguities. These protocols work correctly if resolution of references and detection of syntactic ambiguities are correct. 4
Let a set of lexical objects which e ect on some information value of data attribute of instance a be L(a; ) = fl 2 LO j 9rulei 2 Rules; X A" : rulei(X) = a ^ (9x 2 X : x 2 Ds(l) ^ (9 2 dat \ Datx : l 2 L(x; )))g. For every x 2= A", the corresponding maximally determined instance is x~ such that x~ 2 A" ^ x x~. Entailment relation ` generates information connections between maximally determined instances. Let X ` x and y 2 X ^ y 2= x#. Then { information connections between y~ and x~ are
{ y~ !~! x~ i (9 2 Datx; 2 Daty : ! 2 L(x; ) \ L(y; )) _ (! 2 O(Relx) \ O(Rely) { of updating type y~ !~!u x~ i 9x0 2 X : x0 x, { of generating type y~ !~!g x~ i @x0 2 X : x0 x.
An information system of information retrieval R generates a multi-agent system with typed connections. Agents of the system resolve the ambiguities by computing and comparing the context cardinalities and evidence powers. Information system (A; Con; `) generates Multi-agent System of Ambiguity Resolution (MASAR) as a tuple S = (A; C; I; T ), where
{ A = fax j x 2 A"g is a nite set of agents corresponded to maximally determined instances;
!~ { C = f!~ j 9x; y 2 A : x~ ! y~g is a nite set of connections; { mapping I : C ! 2A A is an interpretation function of ordered connections between agents: I(c) = (ax; ay) i x~ !c y~; { mapping T : C A A ! fgen; updg is types of connections: T (c; ax; ay) = g gen i I(c) = (ax; ay) ! (x~ c! y~), and T (c; ax; ay) = upd i I(c) = (ax; ay) ! (x~ c!u y~). Let (con ict) lexical agents correspond to (con ict) lexical objects.
Not every instance from A" is used for ontology population. There is a set of utility instances U tl. They do not resolve ambiguities or populate an ontology. They just transfer information to its descendants. Hence A" = LO [ Ont [ U tl, where only instances from Ont may populate an ontology.
For every agent a 2 A we de ne the following sets of agents and connections. We omit symmetric de nitions of ancestors Anc (for Des ) and utility predecessors U tP (for U tS ) for the brevity: { Ca = fc 2 Cj9a0 2 A : (a; a0) 2 IC (c) W(a0; a) 2 IC (c)g is connections of a; { Scgac = fa0 2 A j (a; a0) 2 IC (c) ^ T (c; a; a0) = geng is a set of generated successors by c connection;
{ Scuca = fa0 2 A j (a; a0) 2 IC (c) ^ T (c; a; a0) = updg is a set of updated successors by c connection; { Scca = Scgac [ Scuca is a set of all successors by c connection; { P rac = fa0 2 A j (a0; a) 2 IC (c)g is a set of predecessors by c connection; { U tSac = fa0 2 U tl j (a; a0) 2 IC (c)g is a set of utility successors by c; { Desca = Scca [ Sa02Scca Desca0 is descendants by c connection; 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 Desca \ Ancca = ;, i.e. every connection has no cycle because of information transfer.
A weight of an agent corresponds to the number and the quality (in a case of generation) of its non-utility ancestors and descendants. For every a 2 A { wtaP r(c) = 1 + Pa02P rac wtaP0r(c) is the weight of connection ancestors, { wtaSc(c) = 1+Pa02Scgac wt(a0)+Pa02Scuca wtaS0c(c) is the weight of connection descendants,
{ wtaUt(P=S)(c) = 1 + Pa02Ut(P=S)ca wtaU0t(P=S)(c) is the weight of connection utility ancestors/descendants,
{ wt(a) = 1 + Pc2Ca (wtaP r(c) + wtaSc(c) (wtaUtP (c) + wtaUtS (c))) is the weight of information agents.
Weight of system S is wt(S) = Pa2Ont wt(a).
Problem of con ict resolution in MASAR is to get a con ict-free MASAR of the maximal weight. A multiagent algorithm below produces such system. 5
In this paper we consider independent ambiguities only. In this case an order of their resolution is irrelevant. But it is naturally to resolve lexical ambiguity rst, because this disambiguation e ects on existence of ontology instances. Syntactic disambiguation re nes distribution of information among instances.
Action protocols for con ict resolution used by MASAR agents form a multiagent system of con ict resolution MACR. The system MACR includes a set of MASAR agents and an agent-master. Note, that a fully distributed version of our algorithm could be developed but it should be very ine ective. The result of agents' interactions by protocols described below is the con ict-free MASAR. All agents execute their protocols in parallel 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 connected with all agents, MASAR agents are connected with their successors and predecessors, and con ict lexical agents are connected too. Messages are transmitted via a reliable medium and stored in channels until being read.
For correct lexical disambiguation it is necessary to nd groups of lexical agents which e ect on weights of each other in a case of removing. Let us denote these groups of relatives as Relatives. Agents of groups from Relatives have common descendants: 8Rlt 2 Relatives(8a 2 Rlt(9b 2 Rlt : Ds(a) \ Ds(b) 6= ; ^ 8c 2 AmbLO n Rlt : Ds(a) \ Ds(c) = ;)). Due to the mutual e ect of relatives on their weights it is necessary to resolve con icts between groups of relatives. Let GR1 Rlt1 and GR2 Rlt2, where Rlt1; Rlt2 2 Relatives. Relative groups GR1 and GR2 are in a con ict GR1 ! GR2 i (8a 2 GR19b 2 GR2 : a ! b) ^ (8b 2 GR29a 2 GR1 : b ! a). Let sets G1 = [in=1GR1i = [im=1Rlti1 and G2 = [i=1GR2i = [i=1Rlti2, where Rlti1; Rlti2 2 Relatives for every i 2 [1::m] n m be groups of friends. These groups of friends are in a con ict i (8i 2 [1::n] : GR1i ! GR2i). Note that due to proposition 3 set AmbLO can be disjoined to nonintersecting subsets of relatives. A con ict is resolved for a bene t of the group with the greater weight, i.e. if Pa2G1 wt(a) > Pb2G2 wt(b), then agents of group G2 are removed from the system, and their descendants delete their inherited values of attributes or the descendant is removed itself if the lexical value from a lexical agent in G2 is generating for this descendant.
Hence, for resolving all con icts in the system it is necessary to perform
the following steps: (
Below we give informal descriptions of several protocols of the system agents.
(
Resolution of syntactic ambiguities Synt11 and Synt12 consists of two steps.
(
If an agent nds attributes !1 and !2 with value c then it compares evidence
powers EQ(a; !1; c) and EQ(a; !2; c). The attribute value is removed from values
of an attribute with the less power.
(
If an agent nds attribute ! with values c1 and c2 then it compares evidence powers EQ(a; !; c1) and EQ(a; !1; c2). The attribute value with the less power is removed from values of the attribute. 6
In this paper, we show that maximal instances of the ontology classes that take part in the process of population form, together with the rules of data processing and ontology population, a Scott information system. This result justi es resolution of context-dependent lexical ambiguity by calculating context cardinalities. The Scott information system is also a basis for our approach to syntactic context-dependent ambiguity resolution. This system generates a multi-agent system in which agents resolve the ambiguities by computing the cardinality of their contexts and evidence powers. The suggested algorithm of lexical ambiguity resolution chooses the most powerful group of agents and removes their competitors. The choice is based on agents' weights and their e ect on the system.
We considered independent lexical and syntactic ambiguities only. In the near future we plan to study disambiguation of combination of various types syntactic and lexical ambiguities. In this work it is useful to introduce a membership probability of attribute ambiguity values and a degree of their e ect on other instances. We would like to try the developed technique for resolving references also.