ARTICLE IN PRESS Neurocomputing 72 (2009) 1639–1647
Contents lists available at ScienceDirect
Neurocomputing journal homepage: www.elsevier.com/locate/neucom
A neural network-based multi-agent classifier system Anas Quteishat a, Chee Peng Lim a,, Jeffrey Tweedale b,c, Lakhmi C. Jain b a b c
School of Electrical and Electronic Engineering, University of Science Malaysia, Malaysia School of Electrical and Information Engineering, University of South Australia, Australia Defence Science and Technology Organisation, Edinburgh, South Australia, Australia
a r t i c l e in fo
abstract
Article history: Received 10 October 2007 Received in revised form 15 August 2008 Accepted 18 August 2008 Communicated by T. Heskes Available online 10 October 2008
In this paper, we propose a neural network (NN)-based multi-agent classifier system (MACS) using the trust, negotiation, and communication (TNC) reasoning model. The main contribution of this work is that a novel trust measurement method, based on the recognition and rejection rates, is proposed. Besides, an auctioning procedure, based on the sealed bid, first price method, is adapted for the negotiation phase. Two agent teams are formed; each consists of three NN learning agents. The first is a fuzzy min–max (FMM) NN agent team and the second is a fuzzy ARTMAP (FAM) NN agent team. Modifications to the FMM and FAM models are also proposed so that they can be used for trust measurement in the TNC model. To assess the effectiveness of the proposed model and the bond (based on trust), five benchmark data sets are tested. The results compare favorably with those from a number of classification methods published in the literature. & 2008 Elsevier B.V. All rights reserved.
Keywords: Neural networks Multi-agent systems Pattern classification
1. Introduction Multi-agent systems (MASs) have gained much interest of researchers over the last decade. This is evidenced by the widespread application of MASs to different domains including e-commerce [12], healthcare [16], military support [32], decision support [26], knowledge management [31], as well as control systems [27]. Some successful case studies of MASs are as follows. In [17], an MAS-based decision support system is applied to steel processing. Each agent symbolizes a special approach, and cooperation takes place by evolving a shared population of solutions. In e-commerce applications, an MAS framework for credit risk prediction is described in [28]. The proposed credit management system includes risk prediction, risk control, and risk event handling. The model is based on autonomy and society of the agent. In [36], intelligent agents are used for pattern classification. An MAS architecture that combines recognition hypotheses of several classifiers is proposed. Another industrial application of an MAS is presented in [24], whereby the MAS is used to monitor the start-up sequence of an industrial gas turbine. There are many definitions of agents. One of the definitions is as follows [2]: ‘‘sophisticated computer programs that act autonomously on behalf of their users, across open distributed environments, to solve a growing number of complex problems.’’ This definition shows that agents have the capability of making decisions and of
Corresponding author. Tel.: +60 4 5996033; fax: +60 4 5941023.
E-mail address:
[email protected] (C. Peng Lim). 0925-2312/$ - see front matter & 2008 Elsevier B.V. All rights reserved. doi:10.1016/j.neucom.2008.08.012
performing tasks. To carry out a particular task, the relationship among a pool of agents needs to follow some pre-defined model. One of the earliest models is the beliefs, desires, intentions (BDI) reasoning model [5,34]. In BDI, beliefs represent an agent’s information about the environment; desires are goals that the agent wants to achieve; and intentions are plans that the agent uses to reach its goals. Another MAS reasoning model is the decision support pyramid model [35]. This model organizes agents into groups according to the model’s problem-solving phases. The agent groups interact with the user, the environment, and each other to improve the overall performance. A specific MAS model introduced for industrial applications is COMMAS (condition monitoring MAS) [23]. This model employs a hierarchal decentralised multi-agent architecture for condition monitoring. It has three layers: (i) the attribute reasoning agents (ARA); (ii) the cross sensor corroboration agents (CSCA); and (iii) the meta knowledge reasoning agents (MKRA). The model has demonstrated its usefulness in monitoring the starting sequences of industrial gas turbines [24]. In this paper, the focus, however, is on the trust, negotiation, and communication (TNC) model [20,33] in agent-based technology. The TNC model is based on the premise that the origin and justification of the strength of beliefs come from different sources of beliefs. In this model, four possible sources of beliefs are considered: direct experience, categorization, reasoning, and reputation. In the TNC model, the agents within the team collaborate with each other, and trust each other (i.e., forming inter-team relation). The TNC model describes trust as a bond that can be strengthened via the exchange of certified tokens. In
ARTICLE IN PRESS 1640
A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
essence, trust is dynamic by nature. It is strengthened by successful interactions, and is weakened by unsuccessful outcomes. Therefore, measuring and quantifying trust is of prime importance to determine the success/failure of the TNC model. The TNC model is used as the backbone to establish a multiagent classifier system (MACS) in this work. The proposed MACS consists of a pool of neural network (NN)-based classifiers. In our demonstration, two different NN classifier agents are formed, i.e., fuzzy ARTMAP (FAM) [7] and fuzzy min–max (FMM) [29] NNs. In addition to the proposed NN-based MACS, another main contribution of this paper is that a novel method to measure trust, based on classification accuracy of agents, is introduced. Modifications to the FAM and FMM models are suggested so that they can be used for trust measurement. Besides, an auction method is implemented in the negotiation phase of the TNC model. To verify the overall effectiveness of the proposed MACS, five benchmark data sets are evaluated, i.e., Pima indian diabetes (PID), Wisconsin breast cancer (WBC), glass, wine, and sonar data sets from the UCI machine learning repository [25]. The results obtained are compared with those from a number of machine learning systems published in the literature. This paper is organized as follows: Section 2 introduces the TNC-based MACS model. A brief description on both the FAM and FMM models is presented in Section 3. The proposed trust measurement and negotiation methods of the TNC model, as well as the proposed modifications to FAM and FMM for trust measurement are explained in Section 4. The experimental results and discussion are presented in Section 5. Finally, Section 6 concludes the work presented in this paper.
2. A TNC-based MACS The TNC model used in this work is shown in Fig. 1. In this model, communication is concerned with interaction among agents in order for them to understand each other. Negotiation, on the other hand, is concerned with how agent teams are formed. In an MAS, the requirements of a team are separated from the requirements of individual agents. Thus, it is necessary to assign goals for each agent as well as goals for the whole team. The core
Parent Agent (Controller) Environment
Cooperation Child Agent Cooperation Sibling Agent
MAS
(Intra-team)
(Inter-team)
Collaboration
Collaboration Agent Trust Negotiation Communication
Parent Agent
Agent Manager 1
Agent Manager 2
...
Agent 1 Agent 1 Agent 1
Agent Manager K
Agent . . . Agent 2 Z
Agent . . .Agent 2 Y
Agent . . . Agent 2 X Fig. 2. The proposed MACS model.
element of the TNC model is on trust, whereby the concern is how an agent handles trust with regard to other agents. The questions raised include ‘‘should an agent trust information given by another agent’’ or ‘‘should an agent trust another agent to perform a particular task?’’ Fig. 2 shows the proposed MACS model. The model consists of three layers. The top layer contains a parent agent, which is responsible for making the final decision. The second layer is a hidden layer, which contains team managers, while the third layer contains team members. As TNC is used as the framework for developing the MACS, methods for measuring trust and for making negotiation are necessary. As such, an auction method for negotiation is first described, and a novel method for measuring and propagating trust within the TNC model is proposed in Section 4. Auctioning is one of the most popular and widely used negotiation methods in MASs [2]. There are several bidding methods available, and the method used here is ‘‘sealed bid-first price auction’’ [4]. First price auction is based on the highest price, i.e., the bid with the highest price wins the auction. The method is selected because it can be easily adapted into the TNC model, with trust measurement, as follows. During the negotiation phase, each agent first submits its bidding value, without knowing the bidding values of other agents (sealed bid), and a decision is made based on the highest price (first price auction). The auction process occurs in two different phases in the MACS. Given a new input sample, each agent within the team first gives a prediction (if available) of the output class. The prediction is associated with a trust value. Then, the team manager selects the prediction with the highest inherited trust value (first auction). After that, a second auction process takes place among the team managers. Each agent manager gives its prediction to the parent agent. Along with the prediction, each manager gives a trust value and a reputation value. Based on the information in hand, the parent agent makes a final decision, and produces a final predicted output class for the current input sample. As explained earlier, there are two agent teams in the proposed MACS model. The first is formed by three FMM agents, while the second is formed by three FAM agents. The next section describes FAM and FMM, their similarities, as well as the reason of employing them as the learning agents in the MACS.
Descendent Agent Cooperation
Sub-Agent/Descendent (Controlled Agent) Cooperation
3. The NN-based agents
Environment
Fig. 1. The trust, negotiation, and communication (TNC) model.
In the proposed MACS, two NN models, i.e., FAM and FMM, are used as the learning agents. The dynamics and similarities of FAM and FMM are as follows.
ARTICLE IN PRESS A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
as in Eq. (3) [7]
3.1. The fuzzy ARTMAP neural network FAM [7] is a supervised ART network which realizes a synthesis of ART and fuzzy set theory. The network has the capability of incremental learning, and, at the same time, of building a map between an analog input space and an output space, all in arbitrary dimensionality. Fig. 3 shows the architecture of FAM. FAM comprises a pair of fuzzy ART [7] modules, ARTa and ARTb, in which they are linked through a map field, Fab. Each ART module contains three layers of nodes: Fa0 (Fb0) is the input layer that performs complement coding of the input patterns; Fa1 (Fb1) is a layer where 2M-dimensional input patterns are interconnected with all nodes in Fa2 (Fb2); Fa2 (Fb2) is a dynamic layer that encodes the prototypes of input patterns, and that allows the creation of new nodes when necessary. A normalization technique called complement coding is introduced to prevent the category drift and proliferation problem [7]. With complement coding, an M-dimensional input vector, a, is normalized to a 2M-dimensional vector, A, using Eq. (1) [7]: A ¼ ða; ac Þ ða1 ; . . . ; aM ; 1 a1 ; . . . ; 1 aM Þ
(1)
In this case, the norm of the input vector is a constant, as in Eq. (2) [7]: jAj ¼ jða; ac Þj ¼
M X
ai þ
i¼1
M
M X
! ai
¼M
(2)
i¼1
During supervised learning, ARTa and ARTb,, respectively, receive a stream of input patterns and their associated target classes. In each ART module, a pattern matching cycle occurs simultaneously. This pattern matching cycle encompasses a twostage hypothesis selection and hypothesis test process [1]. In ARTa, a feedforward pass is initiated to select a prototype that has the highest similarity with the input pattern as the winning node in Fa2. The degree of similarity is measured by a choice function
F0b B = ( b, 1 − b) F1b
1641
jA ^ waj j
aa þ jwaj j
(3)
where A is the input pattern in complement-coded format, aa is the choice parameter of ARTa, wja is the weight vector of the jth Fa2 node. Upon completion of the feedforward pass, a feedback pass ensues. The winning prototype (represented by J) has to seek for a vigilance test, which is in fact a similarity check between the input and the prototype vectors against a threshold, as in Eq. (4) [7]: jA ^ waJ j A
Xra
(4)
where wJa is the winning Jth node in Fa2; ra is ARTa vigilance parameter. If the winning prototype fails in the vigilance test, it is made inactive, and a new cycle of feedforward selection and feedback test is carried out. Both feedforward and feedback passes are continued until the selected winning prototype is able to pass the vigilance test. If no such prototype exists, a new node is created in Fa2 to code the input pattern. The same pattern matching cycle occurs simultaneously in ARTb for the target pattern. Upon completion of the pattern matching cycle in ARTa and ARTb, the winning prototype in Fa2 sends a prediction to ARTb via the map field Fab. A map field vigilance test is performed to confirm the prediction. The map field vigilance test fails if the winning ARTa prototype makes a wrong prediction of the target class in ARTb. A match-tracking process is initiated to trigger a new search in ARTa. On the other hand, the system enters a learning phase if a correct prediction from ARTa to ARTb is reached. During learning, the winning ARTa prototype are updated using Eq. (5) [7]: wJaðnewÞ ¼ ba ðA ^ wJaðoldÞ Þ þ ð1 ba ÞwJaðoldÞ
(5)
where ba is the ARTa learning rate. Note that FAM does not directly associate input patterns at ARTa with target classes at ARTb. Rather, input patterns are first classified into prototypical category clusters before being linked with their target outputs via a map field. At each input pattern presentation, this map field establishes a link from the winning category prototype in Fa2 to the target output in Fb2. This association is used, during testing, to recall a prediction when an input pattern is presented to ARTa.
ρ
3.2. The fuzzy min–max neural network b 2
F
F ab
ρ
F2a F1a F0a A = (a , 1 − a )
Fig. 3. The architecture of FAM.
ρ
The FMM model was first introduced as a supervised classification neural network by Simpson [29]. Later, an unsupervised clustering FMM was also introduced [30]. Since then, variants of FMM-based networks have been suggested in the literature, e.g., general FMM (GFMM) [11], stochastic FMM (SFMM) [22], and inclusive/exclusive FMM [3]. In this paper, the original supervised FMM classification network [29] is used. The FMM classification network is formed using hyperbox fuzzy sets. A hyperbox defines a region of the n-dimensional pattern space that has patterns with full class membership. The hyperbox is completely defined by its minimum (min) and maximum (max) points. The membership function is defined with respect to these hyperbox min–max points, and describes the degree to which a pattern fits in the hyperbox. For an input pattern of n-dimensions a unit cube, In, is defined. In this case, the membership value ranges between 0 and 1. A pattern, which is contained in the hyperbox, has a membership value of
ARTICLE IN PRESS 1642
A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
Class 1
χ
χ
χ
FC Class Nodes
U
Boundary FB Hyperbox Nodes
V &W α
Class 2
α
α
Fig. 4. An example of FMM hyperboxes placed along the boundary of a two-class problem.
FA Input Nodes Fig. 5. A three layer FMM network.
one. Each hyperbox fuzzy set, Bj, is defined by [29] Bj ¼ fX; V j ; W j ; f ðX; V j ; W j Þg
8X 2 In
(6)
where Vj and Wj are the min and max points, respectively. Applying the definition of a hyperbox fuzzy set, the combined fuzzy set that classifies the Kth pattern class, Ck, is defined by [29] C k ¼ [ Bj j2K
(7)
where K is the index set of those hyperboxes associated with class k. In FMM, the majority of processing is concerned with finding and fine-tuning the boundaries of the classes, as shown in Fig. 4. The learning algorithm of FMM allows overlap of hyperboxes belonging to the same class while eliminating overlap among different classes. The membership function for the jth hyperbox bj(Hh), 0pbj(Hh)p1, measures the degree to which the hth input pattern, Ah, falls outside hyperbox Bj. On a dimension by dimension basis, this can be considered as a measurement of how far each component is higher (or lower) than the max (or min) point value along each dimension that falls outside the min–max bounds of the hyperbox. In addition, as bj(Hh) approaches 1, the point is more ‘‘contained’’ by the hyperbox. The function that meets all these criteria is the sum of two complements—the average amount of max point violation and the average amount of min point violation. The resulting membership function is defined by [29] n 1 X bj ðAh Þ ¼ ½maxð0; 1 maxð0; gminð1; ahi wji ÞÞÞ 2n i¼1
þ maxð0; 1 maxð0; gminð1; vji ahi ÞÞÞ
(8)
where Ah ¼ (ah1,ah2,y,ahn)AIn is the hth input pattern, Vj ¼ (vj1,vj2,y,vjn) is the min point for Bj, Wj ¼ (wj1,wj2,y,wjn) is the max point for Bj, and g is the sensitivity parameter that regulates how fast the membership values decrease as the distance between Ah and Bj increases. As shown in Fig. 5, FMM is a three layer network. The first layer, FA, is the input layer which contains input nodes equal in number to the number of dimensions of the input pattern. Layer FC is the output layer. The number of FC nodes is the same as the number of classes. The hidden layer is called the hyperbox layer FB. Each FB node represents a hyperbox fuzzy set, where FA to FB connections are the min–max points, and the FB transfer function is the hyperbox membership function defined by Eq. (8). The min points are stored in matrix V and the max points are stored in matrix W. The connections are adjusted using the learning algorithm, as described later. The connections between the FB and FC nodes are binary-valued, and are stored in matrix U. Eq. (9)
shows the connection between FB and FC [29] 1 if bj is a hyperbox for class C k ujk ¼ 0 otherwise
(9)
where bj is the jth node and Ck is the kth node. Each FC node represents one class. The output of the FC node represents the degree to which input pattern Ah fits within class k. The transfer function for each of the FC nodes performs fuzzy union of the appropriate hyperbox fuzzy set values. This operation is defined by [29] m
ck ¼ max bj ujk j¼1
(10)
In FMM, the fuzzy min–max learning methodology comprises an expansion/contraction process. The training set, D, consists of a set of M ordered pairs {Xh,dh}, where, Xh ¼ (xh1,wh2,y,whn)AIn is the input pattern and dhA{1,2,ym} is the index of one of the m classes. The learning process begins by selecting an ordered pair from D and finding a hyperbox of the same class that can be expanded, if necessary, to include the input. The expansion criterion is defined by [29] nyX
n X ðmaxðwji ; xhi Þ minðvji ; xhi ÞÞ
(11)
i¼1
where 0pyp1 is the hyperbox size. If a hyperbox that satisfies the expansion criterion cannot be found, a new hyperbox is formed and is added to the network. This growth process allows the number of classes to be added without retraining. When hyperboxes expand, there is a possibility of overlap among these hyperboxes. So, an overlap test is introduced to check if the overlap is among the same classes, or among different classes. While it is acceptable to have overlaps among the same classes, overlaps among different classes are to be eliminated by a contraction process. As such, the fuzzy min–max learning process comprises a series of activities that create and expand hyperboxes and then fine-tune the hyperboxes by the contraction process [29]. 3.3. Similarities between FAM and FMM Although FAM and FMM have different network structures, they share a number of similarities. First, both networks possess the incremental learning property, i.e., they learn through a single pass through the training data set, and re-training of new data samples is not needed. Second, since both networks learn incrementally, the knowledge bases formed in the networks are
ARTICLE IN PRESS A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
affected by the sequence of training data samples. In other words, different sequences of training samples form different knowledge bases; hence different prediction capabilities and performance scores. Third, in FMM, the weight vector of each node represents the minimum and maximum points that form a hyperbox in the pattern space. In FAM, the weight vector of each node also represents a hyperbox encoded by the complement-coded weight vectors. Finally, the performances of FAM and FMM are governed mainly by one user-defined parameter, i.e., the ARTa baseline vigilance parameter, ra , in FAM, and the hyperbox size, y, in FMM. As pointed out earlier that the performances of FMM and FAM are affected by the sequence of training samples, combining the predictions from more than one FAM/FMM network is able to improve the network performances. Indeed, different combination techniques exist, and the simplest one is the voting strategy [15]. Instead of voting, we use the agent-based framework for overcoming the problem associated with the sequence of training samples in FAM/FMM in this study.
4. Measuring trust in the MACS model As shown in Fig. 1, the core element of the TNC model is on trust. There are many definitions of trust. A simple one is the confidence places in a person/thing, or more precisely the degree of belief in the strength, ability, truth, or reliability of a person/ thing [21]. Indeed, measuring trust is inherently subjective. In this paper, we propose to use the reliability rate [37] for trust measurement in each FMM/FAM agent, as in Eq. (12): Trust ¼ Reliability ¼
Recognition 1 Rejection
(12)
where Recognition is the ratio of the number of correct predictions to the total number of test samples, and Rejection is the ratio of the number of rejected predictions to the total number of test samples. In the original manifestation of FMM and FAM, there are no rejection criteria. As such, modifications to FMM and FAM are necessary. To calculate the rejection rate, we propose to use the classifier quality concepts in [8]. Two failure (rejection) quantities used are interference and restrictedness, and are defined as follows:
Interference: the degree to which a classifier is unable to label a
class to an input sample because the sample seems to fit in more than one class. Restrictedness: the degree where a classifier leaves an input sample without classification because that sample does not fit to any class label.
FMM/FAM with the above rejection criteria is referred to as modified FMM/FAM hereafter. To measure the above quantities we first need to apply the concept of confidence factor [6] for both FAM/FMM classifications. The confidence factor of the jth Fa2 node in FAM or the jth hyperbox in FMM is calculated using Eq. (13): CF j ¼ ð1 gÞU j þ gAj
(13)
Fa2
node/hyperbox, Aj is the where Uj is the usage of the j th accuracy of the jth Fa2 node/hyperbox, and gA[0,1] is a weighing factor. According to [7], Uj of an Fa2 node in FAM/hyperbox j in FMM is defined as the number of prediction set patterns classified by any Fa2 node/hyperbox j divided by the maximum number of prediction patterns classified by any node/hyperbox with the same classification class; Aj of an Fa2 node/hyperbox j is defined as the number of correctly predicted set of patterns classified by any hyperbox/node j divided by the maximum correctly classified
1643
patterns with the same classification class. Based on the confidence factor, the rejection criteria are computed as 1 ifjCF 1 CF 2 joint classðCF 1 ÞaclassðCF 2 Þ Interference ¼ 0 otherwise (14) Restrictedness ¼
1
if CF 1 ores
0
otherwise
(15)
where CF1 and CF2 are the confidence factors of the highest and second highest node/hyperbox activated by the current input sample, eint and eres are user-defined interference and restrictedness thresholds, respectively. To facilitate the computation of confidence factors, a data set is divided into three sub-sets: training set, prediction set, and test set. The prediction set is used to calculate the confidence factor of each node/hyperbox. In addition, the prediction data set is used to calculate the initial trust of each agent. This initial trust is regarded as the agent’s reputation. The overall team reputation is the average of all agents’ reputation in the team. The operation of the TNC-based MACS is elaborated as follows. In the test phase, the parent agent (the auctioneer) provides the current test sample to the team managers. The managers propagate the test sample to all team agents. Each agent gives a prediction of a target output to the team manager, along with the trust value and the confidence factor of the node/hyperbox responsible for the prediction. The team manager then runs an auction for the test sample. Based on the sealed bid-first price auction, the prediction with the highest trust value is chosen, and submitted to the parent agent along with the reputation value and the trust value of the prediction belonging to the winning node in FAM or winning hyperbox in FMM. When the parent agent receives the predictions from all teams, it makes a final prediction based on the highest decision score computed using Eq. (16): decision ¼ team reputation þ trust value
(16)
Note that using the rejection criteria, modified FAM/FMM agents produce non-predictions with respect to some test samples; hence their performances are affected. Indeed, their performances are problem-dependent, as demonstrated in Section 5. However, modified FAM/FMM agents as well as their associated agent team managers are components (at the bottom and middle levels, respectively, of Fig. 2) embedded in the proposed MACS, and their results serve as an intermediate indicators for trust measurement in the TNC-based model. Ultimately, the overall impacts of the rejection criteria on FAM/FMM agents should be mitigated by the MACS. As a result, the main objectives of the proposed MACS are two-fold: to minimize the number of nonpredicted samples and to improve the overall classification performances. In addition, to preserve the dynamic nature of trust measurement, the trust value is increased/decreased when a successful/unsuccessful prediction is made. To satisfy this requirement, if the prediction of the current test sample is correct, the trust value is increased by the Reliability rate divided by the total number of test samples. However, if a test sample is wrongly predicted or is rejected for classification, the trust value is reduced by a factor equal to one over the total number of test samples.
5. Experimental Studies The proposed TNC-based MACS model is evaluated using five benchmark problems, i.e., Pima indian diabetes (PID), Wisconsin breast cancer (WBC), glass, wine, and sonar data sets obtained from the UCI machine learning repository [25]. The train-validation-test
ARTICLE IN PRESS 1644
A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
method and the cross-validation method are used for evaluation, and all the results are compared with those published in the literature. In the experiments, three agents for each FAM/FMM team were created using randomized sequences of training samples. The restrictedness threshold (eres) and interference threshold (eint) were set to 0.1 and 0.01, respectively, in all experiments. These two parameters were set based on some stringent rejection criteria. First, the prediction of a node/hyperbox in FAM/FMM with a confidence factor less than 0.1 (eres ¼ 0.1) would be rejected. Second, the difference in confidence factors between the highest winning node/hyperbox and the highest winning node/ hyperbox belonging to a different class in FAM/FMM must be greater than 0.01 (eint ¼ 0.01); otherwise the prediction would be rejected. Other network parameters, e.g., the hyperbox size of FMM and the vigilance threshold of FAM, were set by the trialand-error method. Finally, the final MACS test accuracy rate are computed as
Table 1 Results of the original and modified FMM networks Data set
Agents
Original FMM
Modified FMM
Test accuracy (%)
Test accuracy (%)
Non-predictions
PID
Agent 1 Agent 2 Agent 3
67.69 70.44 73.90
67.62 70.84 73.95
1–20 2–20 2–15
WBC
Agent 1 Agent 2 Agent 3
97.00 95.29 95.86
99.53 97.69 96.98
67–85 40–62 3–16
Glass
Agent 1 Agent 2 Agent 3
65.92 62.14 56.85
63.72 61.49 56.06
11–25 2–10 0–7
Table 2 Results of the original and modified FAM networks
Test accuracy ¼
Number of correctly classified test samples Total number of test samples number of non-predicted samples
Data set
Agents
(17)
Modified FMM
Test accuracy (%)
Test accuracy (%)
Non-predictions
PID
Agent 1 Agent 2 Agent 3
65.99 73.52 70.27
64.44 71.81 69.20
0–13 0–14 1–11
WBC
Agent 1 Agent 2 Agent 3
95.00 95.79 96.00
93.78 95.07 93.34
0–6 1–6 2–11
Glass
Agent 1 Agent 2 Agent 3
64.56 65.80 67.94
58.39 58.97 57.87
0–51 0–51 2–43
5.1. Performance evaluation using the train-validation-test approach In this study, three benchmark problems (PID, WBC, and glass) were used to evaluate the usefulness of the proposed MACS. The PID data set contained 768 cases, in which 268 cases (35%) were from patients diagnosed as diabetic and the remaining were healthy. The WBC data set contained 699 records of virtually assessed nuclear features of fine needle aspirates from patients, with 458 (65.5%) benign and 241 (34.5%) malignant cases of breast cancer. The glass data set contained 214 samples with nine continuous attributes from six classes. To facilitate a fair performance comparison with other methods published in the literature, the experimental procedures in [13,9] (for the PID and WBC problems) and in [14,18,38] (for the glass problem) were followed. According to [13], 80% of the data samples were used for training and the remaining for test. Here, the PID and WBC data samples were divided into 60% for training, 20% for prediction, and 20% for test. The experiments were repeated 10 times, and the results were averaged. For the glass problem, according to [14,19], 2/3 of the glass data samples were used for training, and 1/3 for test. Here, the glass data samples were divided into 1/2 for training, 1/6 for prediction, and 1/3 for test. The experiments were repeated 25 times, with the results averaged. The main rationale behind all these arrangements was to ensure that the numbers of test samples and the number of experimental runs were the same so that a fair comparison could be reported. Tables 1 and 2 show the average results of all agents comprising the original and modified FMM/FAM networks. A few observations in terms of classification accuracy and the numbers of non-predictions can be made. As mentioned earlier, owing to the rejection criteria, modified FMM/FAM might not produce a prediction for some test samples. The numbers of non-predictions produced by modified FMM/FAM were problem-dependent. For example, modified FMM produced more non-predicted samples than modified FAM in both PID and WBC problems, but the opposite occurred in the glass problem. The performances of modified FMM/FAM agents were also affected by the number of non-predictions. For the WBC problem, notice that the results (especially agent 1) of modified FMM were better than those of original FMM. This basically was because of
Original FMM
Table 3 Results of the FMM and FAM agent teams as well as the MACS Data set
Method
Test accuracy (%)
Non-predictions
PID
FMM team FAM team MACS
75.70 72.80 75.82
0–2 0 0
WBC
FMM team FAM team MACS
97.12 96.86 97.43
0–10 0–1 0
Glass
FMM team FAM team MACS
66.21 67.15 70.68
0–5 0–19 0
the high numbers of non-predictions. For example, 67–85 (48%–61%) of the total 140 test samples were rejected by modified FMM (agent 1) in the WBC problem. In general, while the performances of original and modified FMM networks were similar, modified FAM was inferior to original FAM. This implied that modified FAM was more susceptible to the effects of the rejection criteria, as compared with modified FMM. This could be owing to the learning algorithms of FAM. In FAM (both original and modified models), the boundaries of the hyper-rectangular prototypes are allowed to overlap with one another. However, in FMM (both original and modified model), overlapped hyperboxes are only allowed for prototypes belonging to the same classes. When overlaps in hyperboxes of different classes occurred, a contraction procedure was activated to eliminate the overlapped regions. Table 3 shows the accuracy rates of the FMM/FAM teams (each comprising three FMM/FAM agents), as well as the overall MACS
ARTICLE IN PRESS A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
(comprising the FMM and FAM teams). It can be easily observed that both FMM/FAM agent teams managed to reduce the numbers of non-predictions considerably. For the FMM team, the maximum numbers of non-predictions were reduced from 20–2 (PID), 85–10 (WBC), 25–5 (glass). As for the FAM team, the maximum numbers of non-predictions were reduced from 13–0 (PID), 11–1 (WBC), and 51–19 (glass). The classification performances of the agent teams were also generally better than individual agents. From Table 3, the benefits of the MACS were clearly demonstrated, i.e., to improve the performances of the agent teams, and, at the same time, to minimize the number of non-predictions. Indeed, the MACS performances were the highest, with all the test samples covered (predicted). As argued earlier, the results of the FMM and FAM teams actually served as useful, intermediate indicators for analyzing the MACS dynamics (especially the number of non-predictions and the coverage of the test samples). From the analysis, the FMM team classified 56% of the test samples while the FAM team covered the remaining test samples for the PID problem. For the WBC problem, the FMM team classified 64% of the test samples while the FAM team classified the remaining 51 samples. For the glass problem, the FMM team covered 52% of the test samples while the FAM team classified the remaining test samples. This analysis clearly showed the effectiveness of the proposed MACS, whereby test samples that could not be handled by one agent team could be successfully classified by another team, hence improvement in the overall performance, as well as reduction in the number of non-predictions. To further evaluate the proposed MACS, its results were compared with those published in the literature, as shown in Tables 4 and 5. In all three problems, the MACS produced the highest test accuracy rates; hence justifying the effectiveness of the proposed model and the trust measurement in tackling pattern classification tasks.
The experiment was repeated 10 times, each with randomized sequences of training data samples. Since the proposed approach needed a prediction data set along with the training and test data sets, 10% of the training data samples were taken as the prediction data set. The obtained results are compared with results published in [38,10,19]. Tables 6 and 7 summarize the overall results of original and modified FMM/FAM. With 10-fold cross-validation, the number of test samples was smaller; hence a smaller number of nonpredictions. It can also be observed that the performances of modified FMM/FAM were inferior to those of original FMM/FAM. This was attributed to the rejection criteria, which resulted in more conservative predictions that satisfied the interference and restrictedness requirements in selecting the winning prototypes in modified FMM/FAM, hence compromised performances. The test accuracy rates of the FMM/FAM agent teams and the overall MACS are listed in Table 8. Similar to the previous study, the agent teams managed to reduce the number of nonpredictions, with stable classification results. The MACS was able to produce the best performances, and, at the same time, to produce a prediction for each test sample. To further examine the effectiveness of the proposed MACS, its results were compared with those published in [38,10,9], as summarized in Table 9. Again, the MACS yielded the best results for the wine and sonar problems using the 10-fold crossvalidation approach. Table 6 Results of the original and modified FMM networks Data set
Table 4 Performance comparison of different methods as published in [13,9] for the PID and WBC problems Method
PID test accuracy (%)
WBC test accuracy (%)
C4.5 C4.5 rules ITI LMDT CN2 LVQ OC1 Nevprop MACS
71.02 71.55 73.16 73.51 72.19 71.28 50.00 68.52 75.82
94.25 94.68 91.14 95.75 94.39 94.82 93.24 95.05 97.43
Table 5 Performance comparison of different method as published in [14,18] for the glass problem Methods
Test accuracy (%)
C4 [14] 1R [14] Fuzzy classifier [18] MACS
63.2 53.8 64.4 70.7
Agents
Original FMM
Modified FMM
Test accuracy (%)
Test accuracy (%)
Non-predictions
Wine
Agent 1 Agent 2 Agent 3
94.72 94.88 94.22
93.16 93.63 93.04
6–9 6–8 6–9
Sonar
Agent 1 Agent 2 Agent 3
75.60 73.85 73.90
72.11 69.13 70.24
4–6 3–7 4–6
5.2. Performance evaluation using the cross-validation approach In this study, two benchmark data sets, i.e., wine and sonar, were tested using the 10-fold cross-validation approach. The wine data set contained 178 samples, each with 13 continuous attributes, with three target classes. The sonar data set contained 208 samples, each with 60 features, with two target classes.
1645
Table 7 Results of the original and modified FAM networks Data set
Agents
Original FAM
Modified FAM
Test accuracy (%)
Test accuracy (%)
Non-predictions
Wine
Agent 1 Agent 2 Agent 3
96.74 96.63 96.64
90.21 91.15 91.44
0–3 0–2 0–2
Sonar
Agent 1 Agent 2 Agent 3
81.10 80.40 80.40
79.94 78.58 79.44
0–1 0–1 0–1
Table 8 Results of the FMM and FAM agent teams as well as the MACS Data set
Method
Test accuracy (%)
Non-predictions
Wine
FMM team FAM team MACS
93.84 95.58 97.33
2–4 0 0
Sonar
FMM team FAM team MACS
78.08 81.30 82.90
2–3 0 0
ARTICLE IN PRESS 1646
A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
Table 9 Performance comparison of different methods as published in [38,10,19] Data set
RBF [8]
C4.5 [10]
Hybrid GMBL [19]
MACS
Wine Sonar
91.19 80.87
94.4 75.4
95.06 76.30
97.32 82.15
Table 10 Results of the bootstrap hypothesis tests Data set
p-Value of test accuracy between FMM and MACS
p-Value of test accuracy between FAM and MACS
PID WBC Glass Wine Sonar
0.0034 0 0 0 0
0 0.0006 0.0006 0.0012 0.0012
and FAM agents, and employs the TNC model for reasoning. Besides, it has been clarified that ‘‘trust’’ is the core element of the TNC model. As such, a novel method for trust measurement has been introduced. The method is based on the recognition and rejection rates of FMM/FAM. To investigate the effectiveness of the proposed MACS and the trust measurement method, five benchmark problems have been evaluated. The results have demonstrated that the MACS is able to outperform a number of machine learning systems published in the literature. Although the results obtained are encouraging, more experiments with real-world data sets from different domains are needed in order to further ascertain the effectiveness of both the proposed MACS and the trust measurement method in real-world applications. In addition to the rejection criteria, other methods for trust measurements can be examined. Instead of FMM/FAM, investigation into the use of other classifiers with the TNC model under varying operating conditions can be conducted, in order to fully vindicate the effectiveness of the proposed MACS. References
5.3. Performance evaluation using the bootstrap hypothesis tests To further ascertain that the proposed MACS performed better original FMM/FAM, a series of hypothesis tests was conducted. The accuracy rates between the MACS and original FMM/FAM were evaluated using the p-values calculated with the bootstrap method [39]. In each test, the null hypothesis that the accuracy rates of the MACS and original FMM/FAM were the same, and the alternative hypothesis claimed that the accuracy rates of original FMM/FAM were lower than those of the MACS. The significance level (a) was set at 0.05 (95% confidence level). This implied that if the p-value was lower than 0.05, the null hypothesis would be rejected, with the alternative hypothesis accepted. As shown in Table 10, all the p-values obtained were lower than the significance level (a ¼ 0.05), thus rejecting the null hypothesis. In other words, there was a significant difference in terms of the accuracy rates between original FMM/FAM and those of the MACS. Therefore, the proposed MACS performed statistically (at the 95% confidence level) better than original FMM/FAM in the five benchmark problems. 5.4. Remarks In general, modified FMM/FAM and their associated agent teams are inferior to, or at most comparable with, original FMM/ FAM. This may seem as a drawback resulted from the use of the rejection criteria in modified FMM/FAM. However, the main objective of this work is to introduce the TNC-based MACS, and to demonstrate its effectiveness in pattern classification. Indeed, as explained earlier, original and modified FMM/FAM as well as the agent teams can be viewed as embedded components to support the overall MACS framework. From the five benchmark problems, the proposed MACS has demonstrated superior performances in comparison with those of the individual agents, agent teams, as well as a number of other methods published in the literature. In summary, the proposed MACS not only is able to produce better results but also to cover all the test samples in the presence of the rejection criteria.
6. Summary In this paper, a novel TNC-based MACS has been proposed. The proposed MACS forms two NN-based agent teams, i.e., the FMM
[1] B. Apolloni, G. Avanzini, N. Cesa-Bianci, G. Ronchini, Diagnosis of epilepsy via backpropagation, in: The International Joint Conference on Neural Networks, 1990, pp. 571–574. [2] Z. Balogh, M. Laclavik, L. Hluchy, Multi agent system for negotiation and decision support, in: The Fouth International Scientific Conference Electronic Computers and Informatics, 2000, pp. 264–270. [3] A. Bargiela, W. Pedrycz, M. Tanaka, Exclusion/inclusion fuzzy classification network, in: The Seveth International Conference on Knowledge-Based Intelligent Information and Engineering Systems, 2003, pp. 1236–1241. [4] M. Beer, M. d’Inverno, N. Jennings, M. Luck, C. Preist, M. Schroeder, Negotiation in multi-agent systems, Knowledge Engineering Review 14 (1999) 285–289. [5] M.E. Bratman, Intention, Plans, and Practical Reason, University of Chicago Press, 1999. [6] G.A. Carpenter, A. Tan, Rule extraction: from neural architecture to symbolic representation, Connection Sci. 7 (1995) 3–27. [7] G.A. Carpenter, S. Grossberg, N. Markuzon, J.H. Reynolds, D.B. Rosen, Fuzzy ARTMAP: a neural network architecture for incremental supervised learning of analog multidimensional maps, IEEE Trans. Neural Networks 3 (1992) 698–713. [8] M. Egmont-Petersen, J.L. Talmon, J. Brender, P. NcNair, On the quality of neural net classifiers, Artif. Intell. Med. 6 (1994) 359–381. [9] P. Eklund, A. Hoang, A performance survey of public domain machine learning algorithms. Technical Report, School of Information Technology, School of Information Technology, Griffith University, 2002. [10] T. Elomaa, J. Rousu, General and efficient multisplitting of numerical attributes, Mach. Learn. 36 (1999) 201–244. [11] B. Gabrys, A. Bargiela, General fuzzy min-max neural network for clustering and classification, IEEE Trans. Neural Networks 11 (2000) 769–783. [12] K. Gwebu, J. Wang, M.D. Troutt, Constructing a multi-agent system: an architecture for a virtual marketplace, in: G. Phillips-Wren, L. Jain (Eds.), Intelligent Decision Support Systems in Agent-Mediated Environments, IOS Press, 2005. [13] A. Hoang, Supervised Classifier Performance on the UCI Data Set, M.Sc. Thesis, Department of Computer Science, University of Adelaide, 1997. [14] R.C. Holte, Very simple classification rules perform well on most commonly used datasets, Mach. Learn. 11 (1993) 63–91. [15] Q. Huang, Q. Zheng, W. Fan, Implementation method for voting of neural networks, in: The IEEE International Conference on Computational Intelligence for Measurement Systems and Applications, 2004, pp. 98–101. [16] D.L. Hudson, M.E. Cohen, Use of intelligent agents in the diagnosis of cardiac disorders, Comput. Cardiol. (2002) 633–636. [17] G. Hui-Min, Z. Jian-Chao, X. Yu-Bin, S. Guo-Ji, Multi agent decision support system, in: The 12th International Conference on Machine Learning and Cybernetics, 2003, pp. 1945–1950. [18] H. Ishibuchi, T. Nakashima, T. Murata, Performance evaluation of fuzzy classifier systems for multidimensional pattern classification problems, IEEE Trans. Syst., Man Cybern. B 29 (1999) 601–618. [19] H. Ishibuchi, T. Yamamoto, T. Nakashima, Hybridization of fuzzy GBML approaches for pattern classification problems, IEEE Trans. Syst. Man Cybern.B 35 (2005) 359–365. [20] H. Kamal, J. Tweedale, U. Pierre, J. Lakhmi, Intelligent decision support system in defence maintenance methodologies, in: The Second International Conference on Emerging Technologies, 2006, pp. 560–567. [21] C. Kelly, M. Boardman, P. Goillau, E. Jeannot, Guidelines for trust in future Atm systems: a literature review. Technical Report 030317–01, European Organisation for Safety of Air Navigation, 2003.
ARTICLE IN PRESS A. Quteishat et al. / Neurocomputing 72 (2009) 1639–1647
[22] A. Likas, Reinforcement learning using the stochastic fuzzy min–max neural network, Neural Process. Lett. 13 (2001) 213–220. [23] E.E. Mangina, S.D.J. McArthur, J.R. McDonald, Commas condition monitoring multi-agent system, Autonomous Agents and Multi-Agent Systems, Vol. 4, 2001, pp. 279–282. [24] E.E. Mangina, S.D.J. McArthur, J.R. McDonald, A. Moyes, A multi agent system for monitoring industrial gas turbine start-up sequences, IEEE Trans. Power Syst. 16 (2001) 396–401. [25] D.J. Newman, S. Hettich, C.L. Blake, C.J. Merz, D.W. Aha, UCI Repository of Machine Learning Databases /http://www.Ics.Uci.Edu/Mlearn/Mlrepository. HtmlS, Irvine, CA: Department of information and computer Science. University of California, 1998. [26] S. Ossowski, A. Fernandez, J. M. Serrano, J.Z. Hernandez, A.M. Garcia-Serrano, J.L. Perez-de-la-Cruz, M.V. Belmonte, J.M. Maseda, Designing multiagent decision support system the case of transportation management, in: The Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004, pp. 1470–1471. [27] S. Ossowski, J.Z. Hernandez, C.A. Iglesias, A. Ferndndez, Engineering agent systems for decision support, in: The Third International Workshop Engineering Societies in the Agents World, 2002, pp. 184–198. [28] Y. Peng, D. Ai, L. Zhuang, Agent-based decision-support framework for credit risk early warning, in: The Sixth International Conference on Intelligent Systems Design and Applications, 2006, pp. 931–936. [29] P.K. Simpson, Fuzzy min–max neural networks—part 1: classification, IEEE Trans. Neural Networks 3 (1992) 776–786. [30] P.K. Simpson, Fuzzy min–max neural networks—part 2: clustering, IEEE Trans. Fuzzy Syst. 1 (1993) 32–45. [31] R. Singh, A. Salam, L. Lyer, Using agents and XML for knowledge representation and exchange: an intelligent distributed decision support architecture, in: The Ninth Americans Conference on Information Systems, 2003, pp. 1854–1863. [32] A. Tolk, An agent-based decision support system architecture for the military domain, in: G. Phillips-Wren, L. Jain (Eds.), Intelligent Decision Support Systems in Agent-Mediated Environments, IOS Press, 2005. [33] J. Tweedale, P. Cutler, Trust in multi-agent systems, in: The 10th International Conference on Knowledge-Based Intelligent Information and Engineering Systems, 2006, pp. 479–485. [34] J. Tweedale, N. Ichalkaranje, C. Sioutis, B. Jarvis, A. Consoli, G. Phillips-Wren, Innovations in multi-agent systems, J. Network Comput. Appl. 30 (2007) 1089–1115. [35] R. Vahidov, B. Fazlollahi, Pluralistic multi-agent decision support system: a framework and an empirical test, Inf. Manage. 41 (2004) 883–898. [36] L. Vuurpijl, L. Schomaker, A framework for using multiple classifiers in a multiple-agent architecture, in: The Third International Workshop on Handwriting Analysis and Recognition, 1998, pp. 1–6. [37] L. Xu, A. Krzyzak, C.Y. Suen, Methods of combining multiple classifiers and their applications to handwriting recognition, IEEE Trans. Syst. Man Cybern. 22 (1992) 418–435. [38] D.S. Yeung, W.Y. Ng, D. Wang, E.C.C. Tsang, X.-Z. Wang, Localized generalization error model and its application to architecture selection for radial basis function neural network, IEEE Trans. Neural Networks 18 (2007) 1294–1305. [39] A.M. Zoubir, D.R. Iskander, Bootstrap Techniques for Signal Processing, Cambridge University Press, 2004.
1647 Anas Quteishat received the BEng (Electronics) degree from Princess Sumaya University of Technology, Jordan, in 2003. He received his MSc degree in Electronic Systems Design from University of Science Malaysia in 2005. Currently he is doing his PhD at University of Science Malaysia, focusing on neural networks, multi-agent systems, pattern classification, and rule extraction.
Chee Peng Lim received the BEng (Electrical) degree from University of Technology Malaysia in 1992, and both the MSc in Engineering (Control Systems) and PhD degrees from University of Sheffield, UK, in 1993 and 1997. He is currently a professor at School of Electrical and Electronic Engineering, University of Science Malaysia. He has published more than 150 technical papers in books, international journals, and conference proceedings. His research interests include soft computing, pattern recognition, medical prognosis and diagnosis, fault detection and diagnosis and condition monitoring. Jeffrey W. Tweedale is a Professional Officer working for Avionics Mission Systems in Air Operations Division of System Sciences Laboratory within Defence Science and Technology Organisation (DSTO), Australia. He has a Grad Dip. (IT), MBA in Business, B. Comp (Hons) degree in Computer Science, a B. IT in Information Systems and a B. Ed in TAFE, and is currently undertaking a PhD at the University of South Australia. His recent work interests include automation, human– computer trust and agent related issues within an airborne mission system.
Lakhmi C. Jain is a Director/Founder of the Knowledge-based Intelligent Engineering Systems (KES) Centre, University of South Australia. He is a fellow of the Engineers Australia. He has initiated a postgraduate stream by research in the KES area. His interests focus on the applications of novel techniques such as knowledge-based systems, virtual systems, multi-agent intelligent systems, artificial neural networks, genetic algorithms, and the application of these techniques.
