Abstract
Abstract: This work addresses the problem of overfitting the training data. We suggest smoothing the decision boundaries by eliminating border instances from the training set before training Artificial Neural Networks (ANNs). This is achieved by using a variety of instance reduction techniques. A large number of experiments were performed using 21 benchmark data sets from UCI machine learning repository, the experiments were performed with and without the introduction of noise in the data set. Our empirical results show that using a noise filtering algorithm to filter out border instances before training an ANN does not only improve the classification accuracy but also speeds up the training process by reducing the number of training epochs. The effectiveness of the approach is more obvious when the training data contains noisy instances.
Introduction
This work addresses an important problem in the field of machine learning, which is the problem of overfitting. This is a common problem for machine learning algorithms that use a variable sized-representation of hypotheses, such as Artificial Neural Networks (ANNs) and decision trees. Overfitting has a negative effect on classification accuracy; it simply means that although the classifier's error measured on the training data is small, the classification error measured on new instances, unseen during training, is high. It is the classification error on unseen instances what matters, since the main objective of machine learning is to be able to deal with new situations. This is what makes overfitting an important issue in machine learning.
Overfitting occurs in two situations: when the training set contains noisy instances and when the training instances are not good representatives of the instance space [14] . Both of these situations are common in real life applications. Real life data sets are rarely free of noise. Noise occurs when an instance is wrongly assigned to a different class than its correct one. Also, real life data sets usually contain a small subset of the instance space which makes them less likely to be good representatives of the instance space.
In this work, we suggest eliminating border instances which tend to be noisy instances or hard-to-learn untypical instances. This should help in smoothing the edges to avoid overfitting and speed-up the training process. Although, we believe that this is a general approach that may improve the classification accuracy of not only ANN, but also of decision trees, our experiments and results, reported in this work, are limited to ANN.
This work is a more elaborate work than the one presented in [8] , focusing in particular on training data sets that may contain noisy instances.
The suggested method smoothes the decision boundary by eliminating the idiosyncrasies of the training set by filtering out near-border instances from the training set, as these instances are a major source of overfitting. We do this by applying an instance reduction algorithm [20] on the training set to eliminate near-border instances before we train an ANN. The aim of using an instance reduction algorithm as a pre-training phase is to smooth the decision boundary and thus makes it less likely for an ANN to overfit the training data. By removing border instances, the effect of noise can be reduced or even eliminated, as most noisy instances would lie near the borders. 1a shows the decision boundaries in the presence of border instances where some of them could be noisy instances. Training an ANN to classify the Os and the Xs is equivalent to finding a line that separates the Os from the Xs (as this is a linear separable problem). This is a much harder job for the points in Fig. 1a than it is for the points in Fig. 1b which has the border instances eliminated. Finding a line that separates the Os from the Xs in Fig. 1a requires more training epochs, which increases the chances of overfitting and reduces classification accuracy for new instances.
To test the effectiveness of the proposed method on improving the classification accuracy and the training speed of ANN, we used 21 data sets from UCI machine learning repository [6] . We performed two sets of experiments: in the first set, we used the data sets without any modifications; in the second set, however, we introduced some noise, and experimented with different noise ratios.
The results show substantial improvement in both classification accuracy and learning speed, reflected as a reduction in the number of training epochs, when noise filtering algorithms were used to preprocess the training data.
The rest of this paper is organized as follows: Section 2 reviews the problem of overfitting and the typical methods for dealing with it. Section 3 reviews the instance reduction algorithms we use in this work. In section 4, we discuss the results of smoothing the decision boundary in terms of classification accuracy and speed of training. Section 5 presents our conclusions.
Typical Methods for Dealing with Overfitting
Overfitting is an important issue that was addressed in different ways in the literature. In decision tree learning, for example, there are two main methods: either to stop growing the tree when further growing is not based on statistically significant data, or to grow the full tree and then prune it. There are two main pruning techniques: reduced error pruning and rule post pruning [15] . Reduced error pruning avoids overfitting by pruning the resulting tree bottom up as long as that pruning does not increase the classification error. In rule post pruning, the tree is first converted into rules and then the rules are independently pruned.
In ANNs, overfitting is avoided using two main methods [14] . The first exploits the fact that overfitting usually occurs as a result of overtraining, therefore, it is natural to try to avoid overfitting by avoiding overtraining. Overtraining occurs when the ANN is trained for a large number of epochs. One approach to determine a good number of epochs is by using a validation set which is taken from the training set before training begins. The validation set is used during training to decide when we should stop training. When the error, measured using the validation set, stops declining and starts growing, we stop training and record the number of epochs at which the error started to grow. To determine the validation set, the data set is usually randomly split into 3 equal parts. The described process is repeated three times (3-fold cross validation) using one partition as a validation set each time. The average number of training epochs is then computed. Then, an ANN is trained on the whole training set, including the validation set, for the computed average number of epochs. In this way, overtraining and consequently overfitting are less likely to occur.
The other approach is called weight decaying [14] ; it simply pulls the weights towards zero. The intuition behind this is that overfitting does not occur early in the training process but rather occurs late in the training process. This is because at the beginning the weights are initialized to small random numbers close to zero. This means that the neural network at this stage has not yet been affected by the idiosyncrasies of the training data. It is when the weights grow in size, probably due to overtraining, that the neural network becomes affected by the idiosyncrasies of the training data. Therefore, decreasing the weights or pulling them towards zero helps avoid overfitting.
As can be seen, the discussed approaches for overfitting avoidance depend on the nature of the learning algorithm. However, the approach we discuss in this work is independent of the learning algorithm, making it suitable for any machine learning algorithm that may overfit the training set, such as decision trees, classification rules, or neural networks.
Instance Reduction Techniques
Instance reduction algorithms have been extensively studied in the context of Instance-Based Learning (IBL) [2] . Instance-based learners are lazy in the sense that they do little work during training, deferring most of the work to the classification stage. During training, they simply store the training data and when a new instance is to be classified, they search their memory for the most similar instance(s) and use the class with the majority of votes as the predicted class for the new instance. Their accuracy tends to increase as the training set size increases but this comes at a cost in terms of their memory requirement and classification time. For this reason, a wide variety of instance reduction techniques [1, 2, 7, 9, 10, 11, 16, 17, 18, 19, 20] were developed in an attempt to alleviate these drawbacks by identifying and retaining the most relevant instances only. Wilson and Martinez [20] compare between many instance reduction techniques that may be used to reduce the number of instances needed for IBL. Some instance reduction algorithms may help in removing hard-to-learn, near-border instances that may cause overfitting.
Instance reduction techniques can be categorized into pure instance reducers and noise filters. Pure instance reducers are much more effective in reducing the size of the training set than noise filters [20] . They tend to keep a small proportion of the training set consisting of a few center instances. An instance is considered to be a center instance if it has the same class as that of the majority of its k nearest neighbors; otherwise it is considered a border instance. Noise filtering algorithms, on the other hand, are less effective at reducing the size of a training set; they tend to retain the majority of center instances and remove near-border instances that are close to instances that belong to other classes (enemy instances).
Border instances tend to be noisy instances or untypical, hard-to-learn instances. Due to the negative effect of noisy instances on the classification accuracy, even some pure instance reduction algorithms include a noise filtering stage, e.g., DROP3 and DROP5 [20] . We call these techniques instance reducers with noise elimination.
In the following subsections, we review the instance reduction techniques we use in this work categorized into noise filters, pure instance reducers, and instance reducers with noise elimination.
Noise filters
The following three algorithms for removing border instances and retaining center instances are used in our experiments.
The Edited Nearest Neighbor algorithm (ENN):
This algorithm removes an instance if it does not agree with the majority of its k nearest neighbors (with k = 3, typically). This edits out noisy instances as well as near-border cases, leaving smoother decision boundaries. It also retains all internal points, which keeps it from discarding most training examples [18] . Therefore, it is ineffective as a reduction algorithm. This algorithm was shown by [20] to retain on average 83.34% of the original data set. In our experiments, using 21 data sets (before inserting noisy instances), it retained on average 85.49% of the original data set.
The Repeated ENN (RENN):
This algorithm applies the ENN algorithm repeatedly until all remaining instances are consistent with the majority of their k-neighbors (have the same class), which widens the gap between classes and smoothes the decision boundary even further (compared to the ENN). This algorithm was shown by [20] to retain on average 80.92%. It retained on average 83.92% of the 21 data sets we used in our experiments. It is not a huge reduction but as would be expected it retains fewer instances compared to the ENN.
3. ALL-kNN: ALL-kNN [17] extends ENN in another way. This algorithm makes k iterations. At the ith iteration, it flags as bad any instance that is not classified correctly by its i nearest neighbors. After completing all iterations, the algorithm removes all instances flagged as bad. This algorithm was shown by [20] to retain on average 77.44%. In our experiments, it retained on average 80.76% of the 21 data sets we used. Again, it is not a huge reduction since it eliminates only the border instances however it eliminates more instances than ENN and RENN.
Instance reducers
We included these two algorithms in our experiments because they are among the most effective instance reduction algorithms; they retain a very small proportion of the training data and maintain a relatively good classification accuracy when used with the kNN algorithm [20] .
Encoding Length (ELGrow):
This algorithm [7] begins with a growing phase that takes each instance in the training set (T) and adds it to the reduced set if that results in a lower cost than not adding it. After all instances are seen, pruning is done, where each instance in the reduced set is removed if doing so lowers the cost of the classifier. This algorithm was shown by [20] to retain on average 1.83% of the data sets and in our experiments it retained on average 2.02% of the considered data sets.
2. Encoding Length (Explore): This algorithm [7] begins by growing and pruning the reduced set (S), using the ELGrow method, and then performs 1000 mutations to try to improve the classifier. Each mutation attempts adding an instance to S, removing one from S, or swapping one in S with one in T-S, and keeps the change if it does not increase the cost of the classifier. The generalization accuracy of the Explore method (as an IBL) is quite good empirically, and its storage reduction is much better than most other reduction algorithms. According to [20] , this algorithm retains on average 2.01% of the original data set. In our experiments, it retained on average 2.26% of the considered data sets. It is, therefore, one of the most effective instance reduction algorithms.
Instance reducers with noise filtering
Due to their obvious negative effect on the accuracy of IBL, even some instance reducer algorithms which tend to retain border instance, do that after a noise filtering stage. Two such techniques were considered in this work.
DROP3:
This algorithm [20] has a high accuracy and a reasonable storage reduction. It uses a noise-filtering pass, such as ENN, before starting to remove noisy instances. The algorithm starts by sorting S on an attempt to remove the centre points before the border points. The instances are sorted by distance to their nearest enemy (nearest neighbor with a different class). So instances far away from their nearest enemy are removed first. This removes center points and retains border points; this makes sense only because noisy instances are removed in the first stage. According to [20] this algorithm retains on average 14.31% of the original data set. In our experiments, it retained on average 16.85% of the considered data sets.
DROP5:
This algorithm [20] considers removing first the instances that are nearest to their nearest enemy, and proceeds outward. This serves as a noise-reduction pass, but will also cause most internal points to be removed as well. After this pass, the furthest-to-nearest pass is performed repeatedly until no further improvement can be made. This algorithm was shown by [20] to retain on average 16.09% of the original data set. In our experiments, it retained on average 17.86% of the considered data sets.
Training ANN using the reduced sets
We believe that border instances are the primary cause of overfitting; after all, even human beings find untypical examples confusing and difficult to learn. Therefore, it is natural to assume that these instances would require a large number of training epochs and possibly leading to overfitting and thus a reduction in classification accuracy. If this hypothesis is true then, eliminating such instances before training an ANN should help reduce the number of training epochs and the likelihood of overfitting. This is especially true if the border instances are noisy instances which they tend to be.
To verify this hypothesis, we conducted two sets of experiments, in the first, we used the original data sets without any modifications; in the second, we modified the training sets so that they contain some noisy instances. The experiments were performed on 21 benchmark data sets obtained from the UCI machine learning repository [6] . We trained ANNs on the whole training sets as well as on the reduced sets produced using the discussed instance reduction algorithms. Each algorithm was applied on each training set to obtain a reduced set. Each reduced set, in addition to the full set, was used to train 4 ANNs that differ only in the number of neurons in the hidden layer.
Each ANN used is a 2-layer network with biases. The hidden layer consists of sigmoid units, while the output layer consists of linear units. Levenberg Marquardt algorithm [12, 13] , as implemented in MATLAB , was used to train each ANN. The Mean Square Error (MSE) [3] was used as the performance function.
The number of neurons in the input layer is equal to the number of attributes in the data set and the number of neurons in the output layer is equal to the number of classes (number of class attribute values) in the data set. Each data set was used to train ANNs with 2, 3, 5, and 10 neurons in the hidden layer. We used 10-fold cross validation in all experiments [4, 14] . Therefore, in total, the full set and each reduced set was used in 40 experiments. The figures in the tables below show the average results of the 40 experiments for the full set and for each reduced set.
In each experiment, we determined the number of training epochs using a validation set that consists of one third of the training data. The ANN was trained on two thirds of the training set until the error on the validation set starts rising. This procedure was repeated three times (3-fold cross validation) swapping each time the validation set by another third of the training instances. The number of training epochs performed before the error on the validation set starts rising was recorded each time. Finally, the ANN was trained on the whole training set for the average number of training epochs with an upper limit of 10000 epochs as a maximum.
The results of using noise-free training sets
In this section, we present the results we obtained using the full sets and the reduced sets without deliberately inserting any noisy examples. Fig. 2 summarizes the results in terms of the classification accuracy of the neural networks. The figure shows the average classification accuracy obtained on the 21 data sets while Tab. I shows the average classification accuracy for each benchmark data set obtained using the 4 ANNs (with 2, 3, 5, and 10 hidden neurons).
It is clear from Fig. 2 that training neural networks on the reduced sets obtained using noise filtering techniques gave the best results. The average classification accuracy obtained by the noise filtering algorithms ALL-kNN, ENN, and RENN is 71.13%, 71.35% and 71.68% respectively, while the average classification accuracy obtained using the full training set is only 67.87%.
ALL-kNN, ENN, and RENN gave better results (compared to the full set) on 18, 18, and 17 data sets out of the 21 data sets used respectively. These figures are
Fig. 2 Accuracy per reduction algorithm over all data sets.
shown in boldface in Tab. I. ALL-kNN, ENN, and RENN gave worse results only on 3, 3 and 4 data sets respectively.
In fact, the three algorithms gave significantly better results than the full set on 13 data sets, shown in boldface and with an asterisk in the table, at 99% significance level and a degree of freedom of 39 (since every data set was used in 40 experiments; i.e. 10 fold cross validation with four structures of 2, 3, 5, and 10 neurons in the hidden layer). ALL-kNN, ENN, and RENN gave significantly worse results on only 2, 1, and 2 data sets, respectively. These figures are marked with an asterisk in the table. On the remaining data sets the results were neither significantly better nor significantly worse.
This may sound surprising given the fact that no noisy examples were deliberately inserted, but in fact it is not. These algorithms remove near-border instances and these instances tend to be either noisy instances or untypical hard-to-learn instances. In either case, they are not good representatives of the instance space, and this is evident by the improvement in accuracy we obtained.
On the other hand, the average classification accuracy, obtained using the pure instance reduction techniques, i.e. ELGrow and Explore, are 48.78% and 50.75% respectively, which are much worse than the results obtained using the full sets. This is expected because they retain a very small proportion of the data sets. It seems that some of the instances they remove are typical instances that are useful for training the ANNs. The accuracy achieved EL-Grow, which is 48.78%, may seem worse than a random selection, but this would be the case only if all data sets contained only two class values (Boolean functions), but this is not always the case in the used data sets. 
Tab. I Accuracy achieved by the ANNs on the full and reduced sets for the used data sets.
The classification accuracy of DROP3 and DROP5 are 55.17% and 55.37%. These algorithms are less effective at reducing the size of the data sets than Explore and ELGrow. They retain more examples than Explore and ELGrow, which explains why they gave better classification results. We believe that their results are not as good as those obtained by noise filters because they do remove some center instances which hurts the accuracy.
In short, our results indicate that the more training examples we present to the neural network the better accuracy we obtain. The only exception is when the noise filtering algorithms are used. They obviously reduce the size of the training sets, but at the same time, increase the classification accuracy.
The next issue to consider is the number of training epochs. If removing border instances makes learning easier, then it should reduce the number of training epochs. Fig. 3 summarizes the results in terms of required training epochs for the neural networks averaged over the used 21 data set, while Tab. II shows the average number of epochs needed to train the neural network for each benchmark data set to reach an acceptable low error. The results show that pure instance reduction techniques have the best results in reducing the number of epochs. The average number of epochs needed on the reduced sets produced by DROP3, DROP5, ELGrow and Explore, are 1787.45, 2302.22, 134.97, and 163.47, respectively. These are huge reductions compared to the average number of epochs required on the full training sets which is 6406.58. They represent 28%, 36%, 2.1% and 2.55% of the number of epochs required to train the full data sets. This is expected since these algorithms produce really small data sets, making it a lot easier for the ANNs to learn or even memorise the training instances without extracting the important features necessary to classify new instances, and hence the reduction in accuracy.
However, the noise filtering algorithms (ALL-kNN, ENN and RENN) also achieved impressive results of 3497.15, 3615.41, and 3253.89 epochs, respectively. These figures represent 54.58%, 56.43%, and 50.79% of the number of epochs required on the full data sets. This is a substantial reduction by all means, confirming that learning became much easier after removing the border instances using these noise filtering algorithms. This reduces the training time not only because the number of epochs is smaller, but also, because at each epoch the ANN is presented with a smaller number of training instances.
The results of using noisy training sets
In this section, we discuss the results of applying reduction algorithms on noisy data sets. We deliberately inserted noise in the same 21 data sets that we used in the last section. Noise was inserted by changing the class of randomly chosen instances. We inserted 5%, 10% and 20% noise in each data set and re-performed the experiments described above. Namely, we applied the 7 reduction techniques on each noisy set and used the resulting reduced set for training the ANNs. We also used the full noisy data sets for training the ANNs for the sake of comparison. Again, we used ANNs with 2, 3, 5 and 10 hidden neuron in the hidden layer.
Tab. III shows the average classification accuracy we obtained using all ANNs trained using every data set with and without noise (0% noise, repeated from Tab. I for the ease of reference).
The results show that the accuracies of the ANNs trained using the full and the reduced sets degrades as the noise ratio increases, however, the noise filtering algorithms were consistent in giving better results than the full noisy sets regardless of the noise ratio. This is a clear indication that applying the noise filtering algorithms actually does remove some noisy instances and thus improves the classification accuracy.
Fig. 3 Required number of epochs per reduction algorithm over all data sets.
The results show that the noise filtering algorithms were especially effective for small to moderate noise ratios. In fact, with 5% noise ratio, they gave better accuracy than the noise-free data sets and for 10% noise ratio they gave almost the same classification accuracy as the noise-free data sets. They only gave worse results than the noise-free data sets results with 20% noise ratio. This is understandable because these algorithms become less effective at eliminating noisy instances when there is a large number of them. This suggests that there is some room for further improvement.
It also shows that the RENN algorithm is the best noise filtering algorithm among the considered algorithms for our purpose of ANN training. Recall that the RENN repeatedly applies the ENN, until we are left with the instances that agree with the majority of their neighbors. This explains why it gave better results than the ENN; it was simply able to eliminate more noisy instances but it too found it more difficult to remove all noisy instances when there were many of them. Note that the ALL-kNN was even less effective than ENN. This is surprising because according to [20] , ALL-kNN gave better results in terms of storage reduction and classification accuracy than ENN and RENN when used with the kNN algorithm. Fig. 4 shows the difference in the achieved accuracy between the ANNs trained using the full data sets with 0%, 5%, 10% and 20% noise and ANNs trained using the reduced sets. It is evident from the figure that as the noise ratio increases, the effectiveness of the noise filtering algorithms becomes more apparent (i.e. the gap in accuracy between the ANNs trained on the full noisy sets and ANNs trained on the reduced sets increases). Again, the best noise filtering algorithm, for our purposes, is RENN. On the other hand, the ANNs trained on the full data set has better accuracy than the ANNs trained on the reduced sets produced using DROP3, DROP5, ELGrow, and Explore. The increase in the number of training epochs is another indication that noisy examples do actually make learning more difficult. Tab. IV shows that they increase the number of required training epochs. Tab. IV shows the average number of training epochs with and without noise (0% noise, repeated from Tab. II for the ease of reference). Note that the number of required training epochs tends to increase as the noise ratio increases. The noise filtering algorithms proved to be effective at reducing the number of training epochs. It is true that pure instance reduction algorithms DROP3, DROP5, ELGrow and Explore require even fewer training epochs but this came at the expense of the classification accuracy as is evident from Tab. III. The noise filtering algorithms, on the other hand, maintain a good balance between accuracy and training speed. With respect to the number of training epochs, RENN emerged, once again, as the winner requiring only 43.23% of training epochs required on the full noisy data sets. The other two noise filtering algorithms ALL-kNN and ENN required 47.74% and 52% of the training epochs required on the full sets. Tab. IV The number of training epochs required for noisy data sets.
Conclusions
Our empirical results confirmed our hypothesis that eliminating border instances makes learning easier since these instances represent either noisy or untypical hardto-learn instances. This was evident because we obtained better classification accuracy when we trained the ANNs after eliminating these border instances. Also, training required substantially smaller number of epochs which means less training time. Training require less time, also, because at each epoch an ANN is presented with fewer examples. ALL-kNN, ENN, and RENN proved to be very effective algorithms at eliminating border instances. They proved to be especially effective when the training sets contained a small to moderate noise ratios. RENN proved to be the best algorithm in achieving better classification accuracy and, at the same time, requiring the smallest number of training epochs and thus increasing the training speed. On the other hand, pure instance reduction techniques such as DROP3, DROP5, ELGrow, and Explore, gave bad classification results.

{'paper_id': '54597280', 'title': 'Smoothing decision boundaries to avoid overfitting in neural network training', 's2_url': 'https://api.semanticscholar.org/CorpusID:54597280', 'source': 'S2ORC'}