The paper presents a multi-agent algorithm implementing semantic analysis of unstructured data based on ontology. In this multiagent model agents of two kinds interact: the instance agents correspond to meaningful units of the information being retrieved, and the rule agents implement rules of a given ontology. An original solution for the termination detection of this multi-agent algorithm is suggested.
The proposed approach is in the framework of modern investigations of automatic processing and analyzing huge amount of unstructured data. Multi-agent approach for information retrieval from heterogeneous data source for completing ontology is widespread, in particular, it is used for natural language processing [1, 2, 11, 6] and web processing [3{5]. Agents in these works have di erent behavior. Usually in web processing, agents are high-level agents that manage rather data ows, using standard algorithm for knowledge retrieval, than data itself. In natural language processing, agents are either associated with conventional linguistic levels (morphological, syntactic, semantic) or targeted to recognize speci c linguistic phenomena such as ellipsis, anaphora, parataxis, homonymy. These agents do not use ontological knowledge substantially. Thus they are computing processes which may speed up information retrieval due to their parallel work but they do not a ect the retrieval qualitatively.
Unlike all the above works, in our approach we use two kinds of agents, collectively possessing complete information about both the data being investigated and the domain-speci c ontology. Agents of one kind can analyze ontological (and linguistic) features. They do not use data directly, but they process information provided by requesting agents of the other kind. The latter agents are the most close to the ones from [10]. In cited paper every agent representing some word from a text has to determine correspondence between its word and an element of a given ontology. The authors do not use special agents for ontological (and linguistic) properties. Instead, they exploit statistical methods of text clustering.
Our variant of ontology-based approach for processing unstructured data contains the following stages. First, a proper domain ontology has to be selected. We suppose that rules for completing the ontology are de ned formally. Then initial ontology instances (their classes and some attributes) have to be identi ed by some preliminary algorithm. Then other instances' attributes are evaluated by the ontology rules using our algorithm.
The idea of multi-agent aspect of the our approach is that a set of di erent data items is aggregated into an agent considered as an ontology instance. This process is assisted by special support agents corresponding the ontology. First, objects signi cant for the ontology are recognized preliminary in given data. We call these objects instance agents. Belonging to an ontology, the instance agents have attributes. The values of some of these attributes are evaluated as the result of the preliminary analysis. Non-evaluated attributes can be speci ed as a result of communication of instance agents and the support rule agents. In the process of interaction, the agents establish a correspondence between the ontology concepts and the instance units, and thus complete the ontology with speci c instances of concepts and relationships.
This paper presents a multi-agent algorithm for arbitrary unstructured data processing. This algorithm improves and generalizes the algorithm for information retrieval from natural language text suggested in [7]. We estimate the time upper bound of the algorithm and prove the properties of termination and correctness of the termination controller agent.
The rest of the paper is organized as follows. The next section 2 describes the main agents in our systems and gives a simple example. The following section 3 presents protocols for the instance, rule and controller agents and sketches some properties of the systems. Finally, we conclude in the last section 4 with a discussion of further research topics. 2
Outline of the approach and multi-agent system follows. There is an ontology, a set of rules for completing it, and a nite set of data to extract the information for the ontology. The preliminary phase partially assigns values to instance agents attributes. The rule agents implementing the ontology rules (the rules depend on the ontology only, but not on the data), according to data received from various instance agents, generate new attribute values of the instances, send the obtained result to all agents interested in it, or generate new instance agents. Eventually, the instance agents assign values to all their attributes that can be evaluated with the information from the data, and the system stops. A special controller agent keeps track of system stopping.
Let the result of data pre-processing be the set IA of instance agents, where each I 2 IA is a tuple I = (id; Cl; RO0; a1(RI1; RO1); :::; ak(RIk; ROk)); where { id is a unique agent identi er; { Cl is an ontological class of the agent; { RO0 is set of rule agents that use this instance agent as an argument; { for each i 2 [1::k], ai is the attribute of the agent, which value is determined by some rule agent from RIi, every rule in set of rule agents ROi requires the value of attribute ai to get the result; let us denote the set of rule agents for incoming values as RI = [i=1::kRIi, the set of rule agents for outcoming values as RO = [i=1::kROi.
The values of attributes of an instance agent are usually only partially determined before the algorithm starts. When the algorithm terminates, the initially unvalued attributes should be provided values with help of rule agents.
Let us de ne the set of rule agents RA, where each R 2 RA is a tuple R = (id; arg1(Cl1); : : : ; args(Cls); make res(args); ares), where { id is a unique agent identi er; { for each i 2 [1::s]: argi is a set of argument values determined by the corresponding instance agent from ontological class Cli; let us denote the set of vectors of argument values as args, where each value is provided with the identi er of the de ning instance agent, the set of these agents is args:Ag; let us consider the argument values vector non-empty, if all its values are non-empty; { make res(args) is a function for computing the result from argument vector args; { ares is the result of function make res(args) which can be null, if the argument vector is inconsistent; a new value of some attribute1 for instance agents; a new instance agent (there should not be an agent with the same attribute values in the system).
As a simple example let us consider the following multi-agent system for natural language text processing. Let the given ontology includes classes P erson, Organization, and relation Employee. The corresponding instance agents have the following form:
A1 = (id; P erson; fCW ork; CP ersonDeg; : : :g; surname(fCP erson; CP ersonInig; ;); f irst name(fCP ersong; ;); degree(fCP ersonDegg; ;); :::; Employee(fCW ork; CW orkP osg). P erson has the following attributes: surname, f irst name, (academic) degree which can be used and evaluated by the corresponding rule agents CP erson, CP ersonIni, CP ersonDeg.
A2 = (id; Organization; fCW ork; CP ersonDeg; : : :g; name(COrg; ;); type(COrg; COrgT ype; CW ork); : : : ;
Employee(CW ork; CW orkP os); Organization has attributes name and type, and the corresponding inputoutput rule agents COrg and COrgT ype.
A3 = (id; Employee; fCW ork; CW orkP osg;
arg1(CW ork; ;); arg2(CW ork; ;); pos(CW orkP os; ;)).
Relation Employee can be evaluated by rule agent CW ork directly connecting P erson and Organization, or by rule agent CW orkP os which connects them using a position.
As an example of an ontology rule agent let us consider agent CW ork: CW ork = (id; arg1(A1); arg2(A2); fSentence(farg1; arg2g); BracketSegment(farg2g);
P reposition(arg1; arg2); Contact(arg1; arg2)g; Employee:arg1 = CW ork:arg1; Employee:arg2 = CW ork:arg2; A3 = newEmployee()).
This agent recognizes sentences where an organization is enclosed in brackets after a person. For example:
Academician Genrikh Aleksandrovich Tolstikov (Novosibirsk Institute of Organic Chemistry) is a prominent chemist, recognized authority in synthetic organic chemistry.
The following evaluation of attributes of the above agents is the result of analysis of the given text fragment: A1 = P erson(id = 1; surname = T olstikov; f irst name = Genrikh; degree = Academician); A2 = Organization(id = 2; name = Institute of Organic Chemistry; 1 This attribute is de ned a priory. type = Institute); A3 = Employee(id = 3; arg1 = A1; arg2 = A2; pos = ;).
In the next section, the algorithms of the instance, rule and controller agents are described in pseudocode. 3
Let IA = fI1; : : : ; In; : : :g be an instance agents set, and RA = fR1; : : : ; Rmg, be a rule agents set. The result of executing of the following algorithm is data analysis, when the instance agents determine the possible values of their attributes. Let Ii be a protocol of actions of instance agent Ii, and Rj, be the protocol of actions of rule agent Rj, C be the protocol of actions of an agent-controller C. Then the multi-agent data analysis algorithm M DA can be presented in pseudocode as follows: MDA:: begin
parallel fI1g ...fIng ...fR1g ...fRmg fCg end.
Here we assume that the parallel operator means that all execution ows (threads) in the set of braces are working in parallel. That is, all agents act in parallel until either all attributes of the instance agents are evaluated or it happens that none of the rule agent can proceed. These events are determined by the controller agent. The system is dynamic because rule agents can create new instance agents. Let N be the maximal number of instance agents that can be obtained from a given data.
The agents are connected by duplex channels. The controller agent is connected with all agents, and every instance agent is connected with several rule agents (and vise versa). Messages are transmitted asynchronously and stored in FIFO channels until being read. The messages are transmitted in a fast and reliable medium.
We consider an agent active i it does not complete its work (is not at the label \end" of the algorithms below) and either it processes some message or its queue of input messages is not empty. Otherwise, the agent is passive. We say that a multi-agent system terminates i every system agent (possibly) except the agent-controller is passive.
In the agent protocols below the function get head(queue) removes the rst element from the queue and returns that element. 3.1
Let us comment a notation of the instance agent protocol. A message for an instance agent has two elds: name of sender (name 2 [1::m] [ C)2 and ai with value of attribute i. The pseudocode of the protocol follows. 2 The agent receives messages only from the controller agent and from the rule agents.
I::
C: Controller Agent; R; Rij: Rule Agent; RI, RO: set of Rule Agents; data wait: set of Rule Agents = ;; ai: Attribute; mess: message;
In: queue of incoming messages; begin 1. send jRI [ ROj + 1 to C; 2. forall R 2 RI [ RO send evaluated data to R; 3. forall ai 2 Atr forall Rij 2 RIi f 4. send request(ai) to Rij; add (ij) to data wait;g 5. send 1 to C; 6. while (true)f 7. if In 6= ; then f 8. mess = get head(In); 9. if mess.name = C then break; 10. if mess.name 2 RIi then f 11. if ai = ; then f 12. upd(ai); 13. forall Rij 2 RIi f 14. send cancel(ai) to Rij; remove (ij) from data wait;g 15. forall Rij 2 ROi 16. send data(ai) to Rij; 17. send jROij 1 to C;g 18. if ai 6= ; then send 1 to C;g g 19. if data wait = ; then break;g end.
Let us informally describe the protocol of an instance agent. First, the agent
(
Let us estimate the time upper bound of the instance agent protocol. In the rst phase of its activities (line 2) the instance agent sends the evaluated data to all rules agents interested in this data. The complexity of this phase C1IA = O(jRIj + jROj) = O(m). Sending the activation messages to rule agent from RI (lines 3-4) is estimated as C2IA = O(k m) and the size of the queue of incoming messages In is the same. The agent processes the received data (lines 8-19). It takes time C4IA = O(jInj (jRIj + jROj)) = O(k m2). Thus, the upper bound of the protocol actions of each instance agent is CIA = O(k m2). 3.2
In the algorithm of the rule agent's actions protocol, the following functions and
notation are used. The rule agents receive messages only from instance agents
and from the controller agent. The messages have (
R::
C: Controller Agent; I: Instance Agent; a: Attribute; args: vector of Argument = ;; Arg: queue of vector of Argument = ;; // set of tuples res send: set of Instance Agents = ;;
In: queue of incoming messages; begin 1. parallel 2. f while (true) f 3. if In 6= ; then f 4. mess = get head(In); 5. if mess.name=C then goto end; 6. if mess.name=I then f 7. if mess.type=request then add I to res send; 8. if mess.type=cancel then remove I from res send; 9. if mess.type=data then f 10. a = mess.val; Arg = Arg [ make arg(a; I); send 1 to C; ggggg f while (true) f if Arg 6= ; then f send 1 to C; args = get head(Arg); ares = make res(args); if ares.type = attr then f forall I 2 args:Ag \ res sendf
send ares to I; remove I from res send;g send jargs:Ag \ res sendj 1 to C;g if ares.type = new agent then send ares:val to ares.name; if ares.type = null then send 1 to C;g g g
Let us informally describe the protocol of a rule agent. The agent can perform
in parallel both processing of incoming messages(lines 2-10) and the generating
of the outcome (lines 12-21). If it has received a message from the controller
agent, it nishes the work (line 5). If the agent receives a request from the agent
I for a result (line 7), it adds I to the recipients list; and it removes I from this
list if it was the cancelation request (line 8). If it receives a value of the attribute
a from the agent I, then using the procedure make arg it tries to create a
vector of arguments (set of vectors) (line 10). In such vectors the received value
of the attribute is one of the elements and other elements are values of attributes
received earlier. Then the agent tells the controller agent about becoming passive
(line 11). If the vector (or the set of vectors) is formed, the agent immediately
begins to process it/them (line 13). The result of processing is obtained using
the function make res. It may be (
Let us estimate the time upper bound of the rule agent's protocol. The time complexity depends on the time bounds of the parallel actions of the rule agents. Let Ag be the set of agents have sent attributes and Arg be the set of arguments of the rule agent. The complexity of requests and cancels is C2RA = O(jAgj) = O(N ) (lines 7-8). Retrieving and storing data from the instance agents (lines 9-11) is a very time-consuming process with the estimate C1RA = O(jAgjjArgj) = O(N s), since the obtained data generate a set of vectors of the argument values. The complexity of parallel data processing (lines 13-22) is C3RA = O(C1RA (jjmake resjj + jAgj) = O(N s (s + N )), where jjmake resjj is the time complexity of the function, which is linear with respect to the size of the argument. Thus, the overall time upper bound of the actions of each rule agent is CRA = O(C3RA) = O(N s (s + N )). 3.3
A special agent-controller handles the Distributed Termination Detection problem [8]. We suggest an algorithm for the problem which ts to our multi-agent system more than known termination detection algorithms, the credit/recovery algorithms in particular [9, 12]. The main feature of this agent-controller is to sequentially calculate other agents' activities by using variable Act. Instance and rule agents send information about their activities to the agent-controller. After system termination the agent informs others about this fact.
C ::
Act, num: integer; messages: queue of integer; begin 1. Act = 0; 2. while(true)f 3. if messages 6= ; then f num =get head(messages); Act=Act+num;g 4. if messages = ; and Act = 0 then break; g 5. send STOP to all; end.
Let us estimate the time upper bound of the controller agent's protocol. The size of the queue of incoming messages for the controller agent CCA is less then N + Pi2[1::N] jkij + Pj2[1::m](N + Njs), where ki is the number of attributes of instance agent i and sj is the number of attributes of instance agent j. 3.4
The time complexity of the multi-agent analysis algorithm M DA follows from the above estimations: CMDA = O(maxfC1IA; :::; CNIA; C1RA; :::; CmRA; CCAg), where CiIA and CjRA are the complexities of the protocols of the instance and rule agents, respectively, for all i 2 [1::N ], j 2 [1::m].
Correctness (completeness and soundness)3 of information retrieval algorithms is rather a notion of data analysis theory than the theory of multi-agent algorithms, thus it is out of the scope of this paper. But this multi-agent algorithm has some properties to be proved.
Proposition 1. Multi-agent system MDA terminates and the agent-controller determines the termination moment correctly.
Sketch of the proof. First, an analyzed data contains a nite number of
information objects for a given ontology. Hence the number of corresponding agents
and their attributes is nite. Hence (
Soundness mans that this information has been retrieved correctly.
determining evaluable attributes an instance agents goes to a passive state also.
Every rule agent (
Second statement of the proposition follows from the fact that the value of
variable Act becomes 0 no earlier than the termination moment. Let active(t)
be the number of active agents. For every time moment t the following holds:
Pi jmess(t)j mess(i; t) + Act = active(t), because agents in uence (
The proposed approach aims at taking advantage of the agent-based approach to knowledge representation and processing. Thus, using the agent-based technology allows to avoid unnecessary information retrieval, since at any given time, only information required for an agent is being searched for. Furthermore, due to the agents working in parallel, the speed of data processing signi cantly increases.
Note that this paper presents only a basic formal model of agents' interaction that implements a simpli ed model of data analysis, which does not yet take into account speci c problems related to ambiguity of input data. For example, let us consider a case of data ambiguity when the di erent ontology instance agents correspond to the same data (\toast" as \fried bread" and as \a tribute or proposal of health"). In order to handle such ambiguities competitive instance agents acquire points which characterize their connections with other instance agents. These connections are de ned by agents' attributes that could be the linked agents themselves or their attributes. The more links some agent has and the more points its linked agents have, it becomes more probable that this agent is the most accurate data based instance of a given ontology.
These problems can be solved by increasing the expressive power of the proposed agent-based models by giving the agent the ability to work cooperatively, to compete (as above), to keep the history of its creation and development, etc.
Acknowledgments. We would like to thank Dr. I.S. Anureev for discussions.