A Two-Stage Algorithm in Evolutionary Product Unit Neural Networks for Classification

1 “This is an Accepted Manuscript of an article published in Tallón-Ballesteros, A. J., & Hervás-Martínez, C. (2011). A two-stage algorithm in evolutionary product unit neural networks for classification. Expert Systems with Applications, 38(1), 743-754., available at: https://doi.org/10.1016/j.eswa.2010.07.028” A Two-Stage Algorithm in Evolutionary Product Unit Neural Networks for Classification Antonio J. Tallón-Ballesterosa,*, César Hervás-Martínezb aDepartment of Languages and Computer Systems, University of Seville. Reina Mercedes Avenue. Seville, 41012 Spain bDepartment of Computer Science and Numerical Analysis, University of Córdoba. Campus of Rabanales, Albert Einstein Building. Córdoba, 14071 Spain Abstract This paper presents a procedure to add broader diversity at the beginning of the evolutionary process. It consists of creating two initial populations with different parameter settings, evolving them for a small number of generations, selecting the best individuals from each population in the same proportion and combining them to constitute a new initial population. At this point the main loop of an evolutionary algorithm is applied to the new population. The results show that our proposal considerably improves both the efficiency of previous methodologies and also, significantly, their efficacy in most of the data sets. We have carried out our experimentation on twelve data sets from the UCI repository and two complex real-world problems which differ in their number of instances, features and classes. Keywords Artificial neural networks; Product units; Evolutionary algorithms; Classification; Population diversity. 1. Introduction Maintaining diversity in early generations is a crucial task in evolutionary algorithms (EAs) because it can affect not only the convergence speed but also the quality of the final solution. A diverse population is preferable at the beginning of the * Corresponding author. Tel: +34 954556237; fax: +34 954557139. Email addresses: [email protected] (A.J. Tallón-Ballesteros), [email protected] (C. Hervás-Martínez). 2 algorithm and a more condensed one at the end of the search (Maaranen, Miettinen, & Mäkelä, 2004). However, to date the issue of population initialization has received surprisingly little attention in EA literature while, on the other hand, the topic of operators and the representation of individuals has been amply covered. On a lower abstraction level, we must think about how the individuals that constitute the population are generated. In most cases, as in this paper, in evolutionary computation (EC) a pseudo-random number generator is employed, although it is often expressed as “the population is generated randomly”; the idea behind this kind of generators is to obtain a set of values that imitates a random sequence (Maaranen, Miettinen, & Penttinen, 2007). Another question, associated with diversity throughout the evolutionary process, is: does it create only one population or various populations? The issue of generating various populations has also been discussed previously. Wang et al. (Wang, Zheng, & Tang, 2002) present the idea that some populations undergo the application of different mutation operators; next, all the individuals are mixed and split into several populations, each then undergoing the application of yet another mutation operator. In (De Garis, 1990), an iterative scheme with several fitness functions is proposed, so that the population evolves by means of a GA using the first fitness function, then the resulting population is employed as the current population in a GA that uses the second fitness function and so on. Generally, the populations explore several areas in the search space by means of different seeds. The number of populations may vary and there is no single common accepted value. In the context of artificial neural networks (ANNs), our proposal, which will be described in detail in continuation, diversifies the architecture of the neural network at the beginning of the evolutionary process. The first stage consists of creating two populations with different features (the maximum number of nodes in the hidden layer, so the topology will be different), evolving them with identical parameter values of the EA, for a small number of generations, selecting the best individuals from each population in the same proportion and combining them to constitute a new population. In the second stage, the main loop of the standard EA used will be applied to the new population. In this way, the population has wider diversity due to the different topologies found in the neural networks. The initial short training leads to random individuals to explore possible promising areas in two directions, since there are two different populations. After that, individuals with different topologies coexist and the 3 more suitable ones will remain. To be coherent with our previous work (Tallón- Ballesteros, Gutiérrez-Peña, & Hervás-Martínez, 2007) we have used two populations in the first phase that will be merged into one. In this way we can better analyse previous and current performances. We will compare the accuracy, complexity and efficiency of two previous experiments with a current one for all the problems under consideration. The issue of diversity is very important in EC. Evolution, by definition, requires diversity, which refers to the (genetic) variation in population members (Amor & Rettinger, 2005; Heitkoetter & Beasley, 2001). Diversity is valuable since new areas of the search space are explored, without which the search could remain trapped in a local optimum (Chop & Calvert, 2005). Actually a high diversity implies that the population covers a larger part of this space (Ursem, 2002). A common view of the evolutionary process is that diversity enhances the performance of a population by providing more opportunities for evolution. A homogeneous population offers no advantage for improvement as the entire population is focused in a particular portion of the search space. By contrast, a diverse population will simultaneously sample a large area of search space, providing the opportunity to locate different, potentially better, solutions (Curran & O’Riordan, 2006). Diversity can be considered at different stages, basically in the first steps of evolution or throughout the evolutionary phase. This paper focuses on the former, although there are several papers that consider the latter. A great deal of research has established diversity as a target to promote, maintain or reintroduce into evolving populations of solutions in order to achieve maximum performance (Curran & O’Riordan, 2006). In Amor & Rettinger (2005), there are some references to studies referring to the above aspects. As previously mentioned, diversity can be considered in the evolutionary stage. For instance, with respect to the selection stage, rank scaling (Goldberg, 1989) is a sample. In the replacement phase, several proposals have been put forward, like the hybrid replacement scheme proposed by Lozano et al. (Lozano, Herrera, & Cano, 2008) or crowding methods (Mahfoud, 1995). High diversity does not imply better GA performance; this is closely related to the question of exploration versus exploitation, but enforcing diversity in the early phases of evolution ensures a broad exploration of the search space (Amor & Rettinger, 2005). Our objective is to improve the efficiency (measured by means of the number of evaluations) and efficacy, if possible, of the previous models that have been employed to date by us. The training of databases, which have different numbers of patterns, 4 features and classes, is dealt with by means of ANNs to evaluate the methodology proposed. The computational cost is very high if EAs with different parameter settings are employed for the training of the above-mentioned networks. It is convenient to change the usual way of generating network models and, thus obtain enough diverse ones with respect to the architecture in the first generations of the evolution. So, instead of using the methodology in (Martínez-Estudillo, Martínez-Estudillo, Hervás-Martínez, & García-Pedrajas, 2006) that consists of generating 10*N neural networks randomly with a maximum fixed number of nodes in the hidden layer, sorting them according to their fitness and choosing the best N ones to constitute the initial population, we present the idea of creating two populations. Each population has a different maximum number of nodes in the hidden layer, and is evolved for a small number of generations in order to subsequently merge the best half of individuals of each one into a single population; then we apply the standard evolution process of the EA employed to date for classification by means of product unit neural networks (PUNN) (Martínez-Estudillo, Hervás-Martínez, Gutiérrez-Peña, Martínez-Estudillo, & Ventura-Soto, 2006). In this way, the training time will be reduced because the population will be much more diverse. Moreover it will not be necessary to apply the full evolutionary process to some populations with different numbers of nodes in the hidden layer. Only there is more than one population in the first step of the evolution; next we merge individuals with different topologies into one. This methodology is more recommendable in the case of data sets with a great number of patterns, given that the processing time is very high for a complete configuration with a reasonable number of iterations for a proper number of generations. Logically, it is not usual to carry out experiments with a single configuration but with a number of them, resulting in a computationally-intensive procedure. The advantage of our proposal is that all individuals do not present a fixed architecture, but a flexible topology between two possible ones. The performance will not be so dependent on parameter tuning, in the sense that the maximum number of hidden nodes in an individual can fluctuate between two user-defined values over the course of the evolution. Several runs of the algorithm have been performed to smooth the stochastic character of the EAs using mean values in order to complete a statistical analysis of the results obtained. After presenting the results and the number of EA evaluations with both earlier and current methodologies, there will be an analysis to determine whether the performance of the solutions improves quality-wise with respect to the Correct 5 Classification Ratio (CCR) obtained with our previous methodology, and if the complexity with respect to the number of connections does as well. In order to do this, statistical tests will be used to compare the mean performances of the CCR and the mean number of connections obtained with both the proposed methodology and the standard method. Finally, there will be a comparison of both methodologies, that use PUNN, and other techniques that employ neural networks based on sigmoidal and radial basis functions. There is also a general review of the results obtained with other neural networks or classical/modern machine learning approaches. This paper is organized as follows: Sect. 2 describes some concepts about PUNN and the EA; Sect. 3 presents the description of our proposal; Sect. 4 details the experimentation process; then Sect. 5 shows and analyzes the results obtained; finally, Sect. 6 states the concluding remarks. 2. Methodology 2.1. Product unit neural networks Many different types of neural network architectures have been used, but the most popular one has been the single-hidden-layer feed-forward network. Amongst the numerous algorithms for training neural networks in classification problems, our attention focuses on evolutionary artificial neural networks (EANNs). EANNs have been a key research area in the past decade providing an improved platform for optimizing network performance and architecture (number of hidden nodes and number of connections) simultaneously. Up to now, designing topologies is still very much a human expert’s job. It depends heavily on expert experience and a tedious trial-and-error process. There is no systematic way to automatically design a near-optimal architecture for a given task (Yao, 1999). Design of the optimal architecture for an ANN can be formulated as a search problem in the architecture space where each point represents one. Given some performance (optimality) criteria, e.g., lowest training error, lowest network complexity based on the number of connections, etc., about topologies, the performance level of all of them forms a discrete surface in the space. The optimal topology design is equivalent to finding the highest point on this surface (Yao & Liu, 1997). Miller et al. (Miller, Toddm, & Hegde, 1989) proposed that EC was a very good candidate for searching the space of architectures because the fitness function associated 6 with that space is complex, noisy, non-differentiable, multi-modal and deceptive. Since then, many evolutionary programming methods have been developed to evolve ANNs, for instance, those by (Yao & Liu, 1997) and (Yao, 1999). The methodology employed here consists of the use of an EA as a tool for learning the architecture and weights of a PUNN model (Martínez-Estudillo, Martínez-Estudillo, Hervás-Martínez, & García-Pedrajas, 2006; Martínez-Estudillo, Hervás-Martínez, Gutiérrez-Peña, Martínez-Estudillo, & Ventura-Soto, 2006). This class of multiplicative neural networks comprises such types as sigma-pi networks and product unit networks. Some of the advantages of PUNN are increased information capacity and the ability to form higher-order combinations of inputs (Durbin & Rumelhart, 1989). Besides that, it is possible to obtain upper bounds of the Vapnik-Chervonenkis dimension of PUNN similar to those obtained for sigmoidal neural networks (Schmitt, 2001). Finally, it is a straightforward consequence of the Stone-Weierstrass Theorem to prove that PUNN are universal approximators (Martínez-Estudillo, Martínez-Estudillo, Hervás-Martínez, & García-Pedrajas, 2006). Despite these advantages, product-unit based networks have a major drawback. Networks based on product units (PUs) have both more local minima and more probability of becoming trapped in them (Ismail & Engelbrecht, 2000). The main reason for this difficulty is that small variations in the exponents can cause large changes in the total error surface. Several efforts have been made to carry out learning methods for PUs. Janson and Frenzel (1993) developed a GA for evolving the weights of a network based on PUs with a predefined architecture. The major problem with this kind of algorithm is how to obtain the optimal architecture before-hand (Ismail & Engelbrecht, 2000). Unfortunately, up to the present, the problem of designing a near optimal ANN architecture for an application remains unsolved. Abraham (2004) presents MLEANN (meta-learning EANN), an adaptative computational framework based on evolutionary computation for automatic design of optimal ANNs. However, this paper defines two types of experiments, and it is necessary to supply the number of hidden nodes as a user-specified parameter. The first one is more flexible, in the sense that the topology is indicated with a number of hidden nodes that ranges between 5 and 16. The disadvantage of using an EA in the training of PUNN is that the processing time could be too great with respect to the dimension of the features’ space and to the number of classes in a concrete classification problem under consideration. Thus, our proposal tries to ease and speed up the way of finding a good topology regarding previous works. So, 7 it does not define a fixed architecture, but one that combines individuals that present two different values of hidden nodes. Fig. 1 shows the structure of a PUNN model for a bi-classification problem; this is a three-layer architecture, that is, k nodes in the input layer, m ones and a bias one in the hidden layer and one node in the output layer. The topologies will be indicated by means of the numbers of nodes in each layer from input to output given as a sequence: Number of inputs: number of nodes in the hidden layer: number of nodes in the output layer. So, in Fig. 1 we have a k:m:1 architecture. Fig. 1. Structure of a PUNN model for a bi-classification problem. The transfer function of each node in the hidden and output layers is the identity function. Thus, the functional model obtained by each of the nodes in the output layer is given by: 12 0 11 ( , ,..., ) ji k mw ll k ji ji fxx x x ββ ==  = +   ∑∏ (1) 2.2. Evolutionary algorithm We use an EA to design the structure and learn the weights of PUNN. The search begins with a random initial population and, for each iteration, the population is modified using a population-update algorithm. The population is subjected to the operations of replication and mutation. Crossover is not used due to its potential disadvantages in evolving artificial networks (Angeline, Saunders, & Pollack, 1994; Yao & Liu, 1997). With these features the algorithm falls into the class of evolutionary programming. We have a classification problem and the general scheme of the EA is the following: Fig. 2. Pseudocode of the EA. Next, we are going to explain the main aspects of the EA: 1) Notation, data, input and output parameters and variables We have indicated the keywords in boldface and the functions in italics. Comments are preceded by a double-slash (//). The necessary data is a training set with the instances of a classification problem. The main parameters of the EA are the maximum number of generations (gen) and the number of nodes in the hidden layer (neu). The 8 remaining parameters will be described further on. At the end of the EA, it returns the best PUNN model with neu nodes in the hidden layer. The variables used are the number of the current generation (t), the last generation (last_generation) and two arrays, one with the individuals of the evolving population and the other with the fitness of each individual. 2) Representation of the individuals Regarding the representation of individuals, the EA treats the population like a set of PUNN models. An object-oriented approach has been adopted and the algorithm deals directly with the ANN phenotype. Each connection is specified by a binary value indicating if the connection exists, and a real value representing its weight. As the crossover is not considered, this object-oriented representation does not assume a fixed order between any hidden nodes. All the individuals in the population have the same maximum number of neurons in the hidden layer. The concrete value must be indicated as an EA input and this will clearly affect the performance and complexity of the neural network. Obtaining the optimal value is a challenge. 3) Error and fitness functions We have considered a standard softmax activation function, associated with the g network model, given by: 1 exp ( ) ( ) 1, ..., exp ( ) j jL i i f g jL f = = = ∑ x x x (2) where L is the number of classes in the problem, () j fx is the output of node j for pattern x and () j gx is the probability that this pattern belongs to class j. Taking this into account, a function of cross-entropy error is used to evaluate a network g with the instances of a problem, which is reflected in the following expression: 11 1 ( ) ( ln( ( ))) NL j i ji ij lg y g N= = =−⋅ ∑∑ x (3) and substituting gj defined in (2), 11 1 1 ( ) ( ) ln( exp ( )) NL L j iji ji ij j lg yf f N = = =  =⋅− +   ∑∑ ∑ xx (4) where j i y is the target value for class j with pattern i x ( j i y = 1 if i x ∈ class j and j i y = 0 otherwise), () ji fx is the output value of the neural network for the output neuron j 9 with pattern i x , N the number of patterns and L the number of classes. Observe that softmax transformation produces positive estimates that sum to one and therefore the outputs can be interpreted as the conditional probability of class membership. On the other hand, the probability for one of the classes does not need to be estimated because of the normalization condition. Usually, one activation function is set to zero; in this work () 0 Li f=x and we reduce the number of parameters to estimate. Thus, the number of nodes in the output layer is equal to the number of classes minus one in the problem. Since the EA objective is to minimise the chosen error function, a fitness function is used in the form ( ) 1 () 1 ()Ag lg − = + . 4) Initialisation of the population At the beginning of the EA, 10*N individuals are generated randomly (step 2) by means of a pseudo-random number generator, N being the population size; in the current paper it is equal to 1000. Next, all individuals are evaluated, sorted by decreasing fitness and the best N ones will compose the initial population (steps 3-5). 5) Stop condition The main loop of the EA is repeated until the maximum number of generations (gen) is reached or until the best individual or the population mean fitness do not improve during gen-without-improving generations (20 in this paper). 6) Parametric mutation Parametric mutation changes the value of the model coefficients (step 9) and consists of a simulated annealing algorithm. The severity of a mutation of an individual g in the population is dictated by the temperature ()Tg , given by () 1 (),0 () 1Tg Ag Tg=− ≤< . Parametric mutation is accomplished for each exponent ji w and coefficient l j β of the model with Gaussian noise, where the variance depends on the temperature: 1 ( 1) ( ) ( ) 1, ..., 1, ..., ji ji wt wt t j k i m ξ += + = = (5) 2 ( 1) ( ) ( ) 0, ..., 0, ..., 1 ll jj t t t j ml L β βξ += + = = − (6) where ( ) (0, ( )) kk t N Tg ξα ∈ 1, 2k= , represents a one-dimensional normally distributed random variable with mean 0 and variance ( )· ( ) ktTg α , and t is the t-th generation. It should be pointed out that the modification of the exponents ji w is different from the change of the coefficients l j β , therefore 12 αα << . The effect of a mutation on the 16 Table 6 shows the mean and standard deviation of the CCRG and the number of connections for each data set for a total of 30 runs or iterations. The best results regarding accuracy and complexity (measured in number of connections) appear in boldface for each data set. Table 6 depicts the generalization results obtained with EDD and TSEA methodologies. From the analysis of the data, it can be concluded, from a purely descriptive point of view, that the TSEA method obtains the best result in mean of the CCRG for all data sets. The differences have to be considered to be between the mean value of CCRG obtained with TSEA and the mean values of the two equivalent configurations in EDD. For instance, in Balance the results obtained with configuration 1* with 5-6 neurons surpass configurations 1 and 2 with populations of only 5 or 6 neurons. The mean number of connections often increases in TSEA configurations, corresponding to those where improvements in CCRG results are produced with respect to equivalent configurations. Table 6 Results obtained in fourteen data sets applying EDD and TSEA. Furthermore, another advantage is that approximately 40% fewer evaluations per iteration are needed with TSEA to get results comparable to those previously obtained with EDD. Now in this joint experiment, there are two types of individuals in the same population, with neu and neu+1 nodes without duplicating the total size of the population; in the past, these two experiments were carried out separately. The mean number of evaluations per iteration with EDD is given by: ( ) _ *10 0.9* _ * evalutions EDD pop size pop size gen = + (7) where pop_size is the population size and gen the maximum number of generations. On the other hand, with TSEA the expression is the following: ( ) ( _ *10 0.9* _ *0.1* )*2 0.9* _ *evalutions TSEA pop size pop size gen pop size gen=++ (8) As stated before, only one experiment with TSEA is needed, while two are necessary with EDD. Table 7 shows the mean numerical values of the number of evaluations per iteration for all the data sets concerned in the single TSEA experiment and the two EDD ones, which are equivalent, along with the reduction percentage in the number of evaluations. This percentage ranges from 36% to 39%, depending on the number of generations for each data set. 17 Table 7 Mean number of evaluations per iteration with TSEA and EDD and percentage of reduction. 5.2. Statistical analysis In this section we will perform an ANalysis Of VAriance (ANOVA) for the CCRG, for each data set and determine if there are significant differences between the numbers of nodes considered or the values of 2 α for the underlying models. These two factors are not independent so an analysis will be carried out using all possible pairs (N, A) of the Cartesian product of the two sets. For each pair, or cell, 30 runs of the EA have been performed with different random seeds. Table 6 shows the mean and standard deviation values obtained in these runs. 5.2.1. Accuracy and complexity analysis First of all, hypothesis tests are performed to try to determine the mean effect of each term on the CCRG of the best individuals in the last generation for each run. Tests have been carried out for every factor and for the interaction among factors. A normal distribution can be assumed for all the variables contrasted, because the p-values of the Kolmogorov-Smirnov (K-S) test are over a significance coefficient of 0.05. Thus, the results have been studied by means of an analysis of variance ANOVA II (Dunn & Clark, 1974; Miller, 1981; Snedecor & Cochran, 1980) with the CCRG of the best individuals for each run, and CCR as the test variable. This CCR is obtained independently in 30 runs and depends on two fixed factors and their interaction. The linear model has the form: 1,2,3; 1,2 1,...,30 ijk i j ij ijk CCR N A NA for i j and k µε =+++ + = = = (9) where the parameter µ is the global mean of the model. Ni is the effect on CCR of the i-th level of factor N, the number of nodes in the hidden layer, where N1 = neu, N2 = neu+1 and N3 = (neu, neu+1); Aj is the effect on CCR of the j-th level of factor 2 α , where A1 = 1 and A2 = 1.5; NAij represents the effect of the interaction between different values of the number of nodes and the 2 α . Finally, ε ijk are error variables associated with effects on the CCR, other factors not observed in the experiment and, for those not present in the linear model and/or observation error, measure 18 error, etc. The variation in experimental results from CCR is explained by the effects of different levels in the factors of the model and their interaction. In a second step, if there are significant differences in mean CCRG, a comparison test of CCRG means will be performed for each data set in order to see if the TSEA methodology supplies significantly better values in accuracy (measured in CCR) than EDD. For the A factor, associated with the 2 α value, a student’s t-test was performed in order to ascertain whether the differences in CCR mean between the two different values of 2 α considered were significant. For factor N, there is a multiple comparison test of the average CCR obtained with the three different levels to determine whether there are significant differences. Thus, 90 simulations were done, corresponding to the 30 runs of each level. The p-values, p*, in Table 8 of each term of the linear model show that the number of nodes in the hidden layer significantly affects the CCRG mean in seven data sets at a significance level of 5%, for instance, in the Heart data set p-value=0.008 (see the second column in Table 8). If now the effect of the A factor is taken into consideration, it can be inferred that for the Liver and Pima data sets, there exists a significant effect in the mean of CCR based on 2 α values (p-values 0.035 and 0.001 are lower than 0.050). With respect to interactions among the factors, the fourth column in Table 8, NA, shows that only for the Liver, Waveform and Listeria data sets does a significant effect exist in the mean of the CCR based on that interaction (p-values 0.028, 0.001 and 0.016 are lower than 0.050). In the remaining data sets, the effect of this interaction has been added to the error term and the Snedecor’s F tests have been redone (this situation is indicated in Table 8 with a – sign). Table 8 p-values of the F test of the ANOVA II methodology for the means of the CCRG and the number of connections. Regarding the complexity, a similar analysis of variance ANOVA II with the number of connections has been done. The p-values, p* < 0.050, of factor N in the linear model (see Table 8) indicate that there are significant differences between the mean values of the number of connections for each architecture used for each data set, whereas there are not significant differences in the average of connections depending on 19 the parameter 2 α except for the Balance, Newthyroid and Listeria data sets (p-values are 0.018, 0.003 and 0.001). As for the interaction between the two factors, it is significant for the Heart, Horse, Newthyroid, Pima and Listeria data sets, which indicate that N and α2 values are affected when these act jointly on the mean of the number of connections of network models. Generally speaking, we can conclude that the TSEA methodology improves the CCR values throughout the test set in the majority of the data sets and, for a great deal of them, quite significantly. The number of connections increases in a significant way. 5.3. Product versus sigmoidal units and radial basis function neural networks This section involves a comparison in performance (measured in CCRG) between neural networks based on product units, sigmoidal units and radial basis functions. For this comparison four methodologies have been used: the traditional MLP model (Bishop, 1995) with a learning Back-Propagation method (BP); the RBF model (Howlett & Jain, 2001); the PUs with EDD methodology (EDD); and the PUs with TSEA methodology (TSEA). These methods were run with all the data sets in question. We have used the Weka tool (Witten & Frank, 2005) to run algorithms BP and RBF. The parameters for BP were the following: learning rate 0.3 η = and momentum 0.2 α = . The number of epochs was adjusted in each data set. Regarding the topology of the models (number of hidden nodes), in the case of MLP and RBF we have considered default topology. In EDD and TSEA we deal with the best topology that we have reported in this paper. The number of runs for MLP and RBF was 30. Table 9 includes the results of TSEA, EDD, MLP and RBF methodologies for all data sets. The best results in CCRG for each data set are shown in boldface. Table 9 Results of the comparison with other techniques. From a purely descriptive analysis of the results, it can be concluded that the TSEA method obtains the best result for nine data sets, the RBF methodology yields the highest performance for four data sets, whereas MLP only does so for one data set. Furthermore, the TSEA method obtains the best mean ranking ( 1.57R= ), followed by 20 the EDD method ( 2.64 R= ), and reports the highest mean accuracy ( 87.85%GCCR = ) followed by the EDD method ( 87.38%GCCR = ). The mean accuracy and ranking obtained by the TSEA and EDD are higher than those obtained by MLP and RBF, which confirms the best accuracy of the product units. To determine the statistical significance of the differences in rank observed for each method in the different data sets, a non-parametric Friedman test (Friedman, 1937) has been carried out with the CCRG ranking of the best models as the test variable (since a previous evaluation of the CCRG values results in rejecting the normality and the equality of the variances hypothesis). The null-hypothesis states that all algorithms are equivalent and so their ranks ( iR ) should be equal. The test shows that the effect of the method used for classification is statistically significant at a significance level of 5%, as the confidence interval is 0 0.05 (0, 2.84)CF= = with a F-distribution with 3 and 39 degrees of freedom, and the F-distribution statistical value (Iman & Davenport, 1980) is 0 * 4.08 FC = ∉ . Consequently, we reject the null-hypothesis; thus it implies the existence of significant differences in the performances of all the methods considered. On the basis of this rejection, a post-hoc non-parametric Bonferroni-Dunn test (Hochberg & Tamhane, 1987) was applied with the best performing algorithm TSEA as the control method. The results of the Bonferroni-Dunn test for 0.1 α = and 0.05 α = can be seen in Table 10 using the corresponding critical values for the two-tailed Bonferroni-Dunn test. Table 10 Critical difference values, mean ranking and differences of rankings of the Bonferroni-Dunn test, using TSEA as the control method. The TSEA method obtains a significantly higher ranking of CCRG when compared to all the methods and none of the remaining methods obtain significantly higher rankings when compared to each other. Consequently, the TSEA method obtains a significantly higher performance than the three methods, EDD, MLP and RBF, which justifies the proposal. Therefore, we can conclude that the results obtained by TSEA make it a very competitive method when compared to the other neural network learning schemes previously mentioned. 21 5.4. Results obtained with a variety of classifiers Now, a general review can be made of the results obtained with another kind of neural networks and other machine learning algorithms. In the literature a huge amount of tests have been carried out with some of the data sets here considered. However, in some cases the classifier attribute is different, the number of instances is not the same, since some have been removed, or even the number of features does not match; the result is not included for those situations. The method of cross-validation is different in many papers, so the comparison is not as fair as we would like. Our purpose is to view some of the methods that have been tested with some of the data sets dealt with in the current paper. Regarding neural networks, only those methods using the same number of inputs as ours are considered. These methods are TSEA, EDD, HMOEN_HN (Goh, Teoh, & Tan, 2008), HMOEN_L2 (Goh, Teoh, & Tan, 2008), MLP, RBF and SONG (Inoue & Narishina, 2005). Other classical or modern machine learning algorithms have been included: C4.5 (Quinlan, 1993), k-nearest neighbours (k-NN) (Cover & Hart, 1967; Aha, Kibler, & Albert, 1991), PART (Frank & Witten, 1998) and SVM (Vapnik, 1995). Since, MLP, RBF, C4.5, k-NN, PART and SVM are implemented in Weka tool (Witten & Frank, 2005), the same cross-validation is used as in the current proposal and in our previous work, thus the same instances in each of the partitions; regarding the parameters, the algorithms have been run with the default values. We have reported the best accuracy in k-NN where k is 1, 3, 5, 7 or 9. For the remaining methods cited above, it is not possible to conduct the experiments, because the implementations are not publicly available. There does not exist one method that performs really well with all data sets; depending on the data set, the best classifier belongs to either the neural networks approach or to the classical/modern machine learning. In Table 11 the results are summarized; the best ones in boldface and in italics, the second best ones, as well as the averages of the methods run by us with all data sets. Table 11 Summary of the results in fourteen data sets comparing TSEA to existing works related to neural networks or classical/modern machine learning approaches. 22 6. Conclusions The aim of this paper is to tackle multi-classification problems using neural networks based on product units, but at a lower computational cost than that used in algorithms proposed in previous works. Our basic assumption is that it is good to employ a methodology based on a population with more diverse models regarding network architectures and this produces an improvement in efficiency, mantaining good results. The TSEA is applied to solve fourteen classification problems, twelve from the UCI repository and two real-world problems, with a great deal of variety in the number of instances, features and classes. The results confirm that our approach obtains promising results, achieving a high classification rate level in the data sets at a lower computational cost. Experimental studies have been performed to determine if different values in the number of nodes in the hidden layer and 2 α significantly affect performance. The EA has been run with PUs using, on one hand, the standard EA applying EDD, and on the other hand, TSEA, a method that significantly reduces the computational cost measured by means of the number of EA evaluations. Once we have performed the statistical analysis (see Table 8), we conclude that TSEA maintains enough robust CCRG values and, in a considerable number of data sets, significantly higher ones. In order to analyze performance with respect to efficacy, these two methodologies for the generation of PUNN models have been compared to other network models. The former have sigmoidal basis units and it is a model trained with a BP algorithm (MLP) whereas the latter is model trained with RBF networks. According to the above results, our learning methodology of neural networks, TSEA, is seen to considerably improve efficiency and significantly efficacy in most of the data sets with respect to the EDD methodology. TSEA obtains a significantly better ranking compared to EDD, MLP and RBF. We have also summarized the results obtained with other kinds of neural networks and classical/modern machine learning algorithms. 23 Acknowledgments This work has been partially subsidized by TIN2007-68084-C02-02 and TIN2008-06681-C06-03 projects of the Spanish Inter-Ministerial Commission of Science and Technology (MICYT), FEDER funds and the P08-TIC-3745 project of the "Junta de Andalucía" (Spain). References Abraham, A. (2004). Metalearning evolutionary artificial neural networks. Neurocomputing, 56, 1-38. Aha, D., Kibler, D., & Albert M. K. (1991). Instance-based learning algorithms. Machine Learning, 6, 37- 66. Amor, H. B., & Rettinger, A. (2005). Intelligent exploration for genetic algorithms: using self-organizing maps in evolutionary computation. In Proceedings of the 2005 conference on genetic and evolutionary computation (GECCO 2005) (pp. 1531-1538). Washington DC, USA: ACM. Angeline, P. J., Saunders, G. M., & Pollack, J. B. (1994). An evolutionary algorithm that construct recurrent neural networks. IEEE Transactions on Neural Networks, 5(1), 54-65. Asuncion A., & Newman, D. J. (2007). UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science. <http://www.ics.uci.edu/~mlearn/MLRepository.html>. Beuchat, L. R. (1996). Listeria monocytogenes: incidence on vegetables. Food Control, 7(4-5), 223-228. Bishop, C. M. (1995). Neural networks for pattern recognition. New York: Oxford University Press. Chop, N. E., & Calvert, D. (2005). The chopper genetic algorithm: a variable population genetic algorithm. In Proceedings of the artificial neural networks in engineering conference (ANNIE 2005). St. Louis, MO, USA: Asme Press. Commission, E. (1999). Opinion of the scientific committee on veterinary measures relating to public health on Listeria monocytogenes. <http://www.europa.eu.int/comm/food/fs/sc/scv/out25>. Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21-27. Curran, D., & O’Riordan, C. (2006). Increasing population diversity through cultural learning. Adaptive Behavior, 14(4), 315-338. De Garis, H. (1990). Genetic programming: building artificial nervous systems using genetically programmed neural network modules. In Proceedings of the seventh international conference on machine learning (ML 1990) (pp. 132-139). Austin, Texas, USA: Morgan Kaufmann. Dunn, O. J., & Clark, V. (1974). Applied statistics: Analysis of variance and regression. New York: Wiley. Durbin, R., & Rumelhart, D. (1989). Products units: a computationally powerful and biologically plausible extension to back-propagation networks. Neural Computation, 1(1), 133-142. Fenlon, D. R., Wilson J., & Donachie, W. (1996). The incidence and level of Listeria monocytogenes contamination of food sources at primary production and initial processing. Journal of Applied Microbiology, 81(6), 641-650. 24 Frank, E., & Witten, I. H. (1998). Generating accurate rule sets without global optimization. In Proceedings of the fifteenth international conference on machine learning (ICML 1998) (pp. 144- 151). Madison, Wisconson, USA: Morgan Kaufmann. Friedman, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32(200), 675-701. Goldberg, D. A. (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. Goh, C. K., Teoh, E. J., & Tan, K. C. (2008). Hybrid multiobjective evolutionary design for artificial neural networks. IEEE Transactions on Neural Networks, 19(9), 1531-1548. Heitkoetter, J., & Beasley, D. (2001). The Hitch-Hiker's guide to evolutionary computation. FAQ in comp.ai.genetic, issue 9.1, 4. <http://www.aip.de/~ast/EvolCompFAQ/>. Hervás, C., Silva, M., Gutiérrez P. A., & Serrano, A. (2008). Multilogistic regression by evolutionary neural network as a classification tool to discriminate highly overlapping signals: Qualitative investigation of volatile organic compounds in polluted waters by using headspace-mass spectrometric analysis. Chemometrics and Intelligent Laboratory Systems, 92, 179–185. Hochberg, Y., & Tamhane, A. (1987). Multiple comparisons among means. New York: John Wiley & Sons. Howlett, R. J., & Jain, L. C. (2001). Radial Basis Function Networks 1: Recent Developments in Theory and Applications. Heidelberg, Germany: Springer. Iman, R. L., & Davenport, J. M. (1980). Approximations of the critical region of the Friedman statistic. Communications in Statistics, A9(6), 571-595. Inoue, H., & Narihisa, H. (2005). Self-organizing neural grove and its applications. In Proceedings of the international joint conference on neural networks (IJCNN 2005) (Vol. 2, pp. 1205-1210). Montreal, Quebec, Canada: IEEE. Ismail, A., & Engelbrecht, A. P. (2000). Global optimization algorithms for training product unit neural networks. In Proceedings of the IEEE-INNS-ENNS international joint conference on neural networks (IJCNN 2000), neural computing: new challenges and perspectives for the new millennium (Vol. 1, pp. 132-137). Como, Italy: IEEE. Janson, D.J., & Frenzel, J. F. (1993). Training product unit neural networks with genetic algorithms. IEEE Expert: Intelligent Systems and their Applications, 8(5), 26-33. Kohavi, R. (1995). A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. In Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI 1995) (Vol. 2, pp. 1137-1145). Montreal, Quebec, Canada: Morgan Kaufmann. Lozano, M., Herrera, F., & Cano, J. R. (2008). Replacement strategies to preserve useful diversity in steady-state genetic algorithms. Information Sciences, 178(23), 4421-4433. Maaranen, H., Miettinen, K., & Mäkelä, M. M. (2004). Quasi-random initial population for genetic algorithms. Computers & Mathematics with Applications, 47, 1885-1895. Maaranen, H., Miettinen, K., & Penttinen, A. (2007). On initial populations of a genetic algorithm for continuous optimization problems. Journal of Global Optimization, 37(3), 405-436. 25 Mahfoud, S. W. (1995). Niching methods for genetic algorithms. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, IL, USA. Martínez-Estudillo, A. C., Martínez-Estudillo, F. J., Hervás-Martínez, C., & García-Pedrajas, N. (2006). Evolutionary product unit based neural networks for regression. Neural Networks, 19, 477-486. Martínez-Estudillo, F. J., Hervás-Martínez, C., Gutiérrez-Peña, P. A., Martínez-Estudillo, A. C., & Ventura-Soto, S (2006). Evolutionary product-unit neural networks for classification. In Proceedings of the 7th international conference on intelligent data engineering and automated Learning (IDEAL 2006). Lecture notes in computer science (Vol. 4224, pp. 1320-1328). Burgos, Spain: Springer. Miller, G. F., Toddm, P. M., & Hegde, S. U. (1989). Designing neural networks using genetic algorithms. In Proceedings of the 3rd international conference on genetic algorithms (ICGA 1989) (pp. 379- 384). George Mason University, Fairfax, Virginia, USA: Morgan Kaufmann. Miller, R. G. (1981). Simultaneous Statistical Inference. New York: Wiley. Prechelt, L. (1994). Proben1—A set of neural network benchmark problems and benchmarking rules. Technical Report 21/94. Fakultat für Informatik, Univ. Karlsruhe, Karlsruhe, Germany. Quinlan, J. (1993). C4.5: Programs for Machine Learning. San Francisco, CA: Morgan Kaufmann. Rechenberg, I. (1973). Evolutionsstrategie: optimierung technischer systeme nach prinzipien der biologischen evolution. Stuttgart-Bad Canstatt, Germany: Frommann-Holzboog. Schmitt, M. (2001). On the complexity of computing and learning with multiplicative neural networks. Neural Computation, 14, 241-301. Snedecor, G. W., & Cochran, W. G. (1980). Statistical methods. Ames, Iowa: Iowa State University Press. Tallón-Ballesteros, A. J., Gutiérrez-Peña, P. A., & Hervás-Martínez, C. (2007). Distribution of the search of evolutionary product unit neural networks for classification. In Proceedings of the IADIS internacional conference on applied computing (AC 2007) (pp. 266-273). Salamanca, Spain: IADIS. Tienungoon, S., Ratkowsky, D. A., McMeekin, T. A., & Ross, T. (2000). Growth limits of Listeria monocytogenes as a function of temperature, pH, NaCl, and lactic acid. Applied and Environmental Microbiology, 66(11), 4979-4987. Ursem, R. K. (2002). Diversity-guided evolutionary algorithms. In Proceedings of the 7th international conference on parallel problem solving from nature (PPSN VII). Lecture notes in computer science (Vol. 2439, pp. 462-471). Granada, Spain: Springer. Valero, A., Hervás, C., García-Gimeno, R. M., & Zurera, G. (2007). Product unit neural network models for predicting the growth limits of Listeria monocytogenes. Food Microbiology, 24(5), 452-464. Vapnik, V (1995). The Nature of Statistical Learning Theory. New York: Springer. Wang, L., Zheng, D. Z., & Tang, F. (2002). An improved evolutionary programming for optimization. In Proceedings of the 4th world congress on intelligent control and automation (Vol. 3, pp. 1769- 1773). Shanghai, China: IEEE. Witten, I. H., & Frank, E. (2005). Data Mining: Practical machine learning tools and techniques with Java implementations. San Francisco, CA: Morgan Kaufmann.