Noise-Tolerant Instance-Based Learning Algorithms

1 Introduction

Instance-based learning (IBL) algorithms have several notable characteristics. They employ simple represen­ tations for concept descriptions, have low incremental learning costs, have small storage requirements , can pro­ duce concept exemplars on demand, can learn continu­ ous functions [Kibler et al., 1989], and can learn non­ linearly separable categories, IBL algorithms have been successfully applied to such varied tasks as speech recog­ nition [Bradshaw, 1987], handwritten letter identifica­ tion [Kurtzberg, 1987], the cart-and-pole problem [Con­ nell and Utgoff, 1987], power load forecasting [Jabbour et al., 1987], and thyroid disease diagnosis [Kibler and Aha, 1987] . However, they are highly sensitive to noise.

The ability to tolerate noise is a necessity for robust, practical learning methods. Algorithms should demon­ strate graceful degradations in performance when pre­ sented with noisy data. Pruning methods, based on tests of statistical significance, were developed to allow decision tree learning algorithms to tolerate noisy data [Quinlan, 1986, Niblett and Bratko, 1986]. Similar noise­ tolerant methods have been developed for rule learning algorithms [Clark and Niblett, 1987].

·This work was partially supported by a grant from the Hughes AI Research Center, Malibu, CA.

This paper introduces an extension for IBL algo­ rithms, also based on a form of significance testing, that identifies and eliminates noisy concept description in­ stances. We show that the resulting algorithms' classi­ fication accuracies degrade linearly with linear increases in noise in an artificial domain and improves classifica­ tion performance on several complicated domains. We also compare the performances of our algorithms with previous IBL algorithms and an extension of ID3 [Quin­ lan, 1986] that tolerates noise.

2 Instance-Based Learning Algorithms

IBL algorithms induce neither rules, decision trees, nor other types of abstractions . Instead, instance-based con­ cept descriptions are represented solely by a set of in­ stances. In this paper, each instance is represented by a set of attribute-value pairs - a point in the instance space. IBL algorithms incrementally derive their con­ cept descriptions from a sequence of training instances. Classifications are made with respect to the concept de­ scription's extension, which is derived with respect to a similarity function and a classification function .

2.1 A Framework for IBL Algorithms

More precisely, all IBL algorithms consist of the follow­ ing three components:

1. Similarity Function: Given two normalized in­ stances, this yields their numeric-valued similarity.
2. Classification Function: Given an instance i to be classified and its similarity with each saved instance, this yields a classification for i. (In this paper, a classification is expressed as a concept name.)
3. Memory Updating Algorithm: Given the instance being classified and the results of the other two com­ ponents, this updates the set of saved instances and their classification records.

Each instance is normalized to ensure that attributes are assigned equal importance by the similarity function . Assuming that attributes have equal importance is not necessarily correct, but it is a fair approach without prior knowledge of relative attribute saliencies.

All IBL algorithms in this paper define the similar­ ity of two instances as the negation of their Euclidean distance in the instance space. Comparisons of differ­ ent similarity functions is left for future research. These

Table 2: The Growth IBL algorithm: Deriving concept description C from training set T.

• Initialize C to the singleton set ofT's first instance
• V subsequent training instances t E T:
• Find the nearest neighbor n of t in C
• IF ( t is classified correctly by n) THEN discard t ELSE add t to C

algorithms also employ the same algorithm for tolerat­ ing missing attribute values. Calculating the similar­ ity of two instances involves computing their pairwise attribute-value differences. If either value of a pair is missing, then they are assumed to be maximally differ­ ent from each other.

The IBL algorithms described in this paper employ either the nearest neighbor or k-nearest neighbor classi­ fication function. The former classifies an instance as being a member of the same concept as its most similar instance. The latter does the same, but takes a majority vote among its k most similar instances (we set k to 3).

2.2 A Family of IBL Algorithms

The eight IBL algorithms described in this paper, sum­ marized in Table 1, differ primarily in their memory up­ dating functions . The simplest IBL algorithms (Prox­ imity and K-nn) save all training instances. Since most real-world domains exhibit regularities that make them amenable to storage-reducing algorithms, the remain­ ing IBL algorithms save only misclassified training in­ stances (which are assumed to contain additional con­ cept boundary information). Storage-reducing IBL al­ gorithms differ in how they update memory when a training instance is correctly classified. Instance-filtering algorithms discard correctly classified instances while instance-averaging algorithms replace the classifying in­ stance with an average of it and the instance being clas­ sified. The Growth (Table 2) and Disjunctive Spanning [Bradshaw, 1987] IBL algorithms are identical except that the former performs instance-filtering while the lat­ ter does instance-averaging. We will also experiment with the same instance-filtering variant of the K-nn algo­ rithm and noise-tolerant versions for the three storage­ reducing algorithms (NTGrowth, NT Disjunctive Span- Table 3: NTGrowth IBL algorithm: Deriving concept description C from training set T.

• Initialize C to the singleton set ofT's first instance
• V subsequent training instances t E T:
• Find the nearest acceptable neighbor n oft in C
• IF ( t is classified correctly by n) THEN discard t ELSE add t to C
• Update the classification records of all instances in C at least as similar to t as n
• Drop from C those instances that appear to be noisy

ning, and NT K-nn Growth) .

There are several reasons to experiment with these eight algorithms. Variants of the Growth algorithm have recorded excellent classification accuracies and small storage requirements in several task domains [Hart, 1967, Kurtzberg, 1987, Kibler and Aha, 1987] . Bradshaw [1987] reported similar results for his Disjunctive Span­ ning algorithm. However, both algorithms are sensitive to noise. We wanted to extend these storage-reducing al­ gorithms to tolerate noise. Hence we also experimented with NTGrowth and NT Disjunctive Spanning.

Analyses of the k-nearest neighbor algorithm suggest that it is a more accurate classifier than the nearest neighbor algorithm [Duda and Hart, 1973]. However, the noise-sensitive K-nn instance-filtering algorithm (K­ nn Growth) should also benefit from the noise-tolerant extension. Thus, this study also includes three IBL al­ gorithms that use the k-nearest neighbor classification function (K-nn, K-nn Growth, and NT K-nn Growth) .

3 The Noise-Tolerant Extension

The NTGrowth algorithm (Table 3) is a noise-tolerant extension of the Growth algorithm. NT Disjunctive Spanning and NT K-nn Growth are similar extensions of their respective algorithms. These noise-tolerant algorithms differ from their respective storage-reducing algorithms in three respects:

1. they maintain classification records for all saved in­ stances (i .e., the number of correct and incorrect classifications of subsequent training instances),
2. only those saved instances with significantly good classification records are acceptable for use in sub­ sequent classification tasks, and
3. the noise-tolerant algorithms discard those saved in­ stances that appear to be noisy (i.e., those instances whose classification performance is poor after sev­ eral classification attempts).

For each training instance t , classification records are updated for all saved instances that are at least as similar as t's most similar acceptable neighbor. 1

1 During the initial stages of training, none of the saved instances are acceptable. In order to more closely mimic the behavior of the algorithms when at least one instance is ac­ ceptable, only a randomly chosen number of most similar saved instances' classification records are updated.

Proximity ·

· Growth o · · · · · · · -o NTGrowth·--- ..

Figure 2: NTGrowth filters noise better than either Growth or Proximity.

These extensions employ a significance test to decide whether saved instances are acceptable, noisy, or neither . Instances are acceptable if their classification accuracy is statistically significantly greater than their class' ob­ served frequency and dropped if it is statistically signifi­ cantly less. Confidence intervals are constructed around both the instance's current accuracy and its class' cur­ rent frequency. If the accuracy interval's lowest value is greater than the class frequency interval's greatest , then the instance is accepted. Similarly, instances are dropped when their accuracy interval's highest value is less than their class frequency interval 's lowest . Con­ fidence intervals are constructed using formula 5.5-4 in [Hogg and Tanis, 1983, page 296] .

We designed the extensions to make it difficult for an instance to be accepted by employing a high (90%) con­ fidence for acceptance. However, we selected a lower (75%) confidence level for dropping since we would like to drop those instances with even moderately poor clas­ sification accuracies.

4 Benefits of the Extension

We trained Growth and NTGrowth on 250 randomly drawn instances from a 2-dimensional instance space containing one concept . Figure 1 reveals which instances were saved by each algorithm when each training in­ stance's class was mislabeled with a probability of 10%. In this trial, Growth saved 74 instances, 21 of which were mislabeled. The saved noisy instances invariably recorded poor classification accuracies on subsequent training instances. Since NTGrowth accepts only those instances with significantly good classification accura­ cies, we expected it to distinguish the noisy instances from those with good classification records.

In fact, Figure 1 shows that NTGrowth successfully fil­ tered noisy instances from the concept description. All instances accepted by NTGrowth had good classification accuracies (at least a 70% accuracy in this case) . NT­ Growth's performance in this example was typical. Av­ eraged over 50 trials, 28.3% of Growth's saved instances were noisy while only a mere 0.5% of NTGrowth's ac­ cepted instances were mislabeled (Figure 2).

We experimented with the Proximity, Growth, and NTGrowth algorithms on this same instance space. The results (averaged over 50 trials per noise setting) are summarized in Figure 2. Our purpose was to discover how these algorithms' performances and concept descrip­ tions degrade with increasing amounts of noise, which was varied from 0% to 50%. The three dependent vari­ ables were classification accuracy, storage requirements (number of instances in concept descriptions), and the quality of the concept descriptions (the percentage of concept description instances that were mislabeled).

1. Classification Accuracy: While the three algorithms performed equally well with no noise, NTGrowth's accuracy degraded more slowly (linearly) with in­ creasing noise levels.
2. Storage Requirements: The Proximity algorithm saved all training instances. Growth's storage re­ quirements were much lower, asymptoting towards 50%. However, NTGrowth's were significantly lower than Growth's and asymptoted towards zero. This was expected: since none of the saved instance's ac­ curacies were significantly good at high noise levels, NTGrowth accepted only a few of them into the concept description.
3. Concept Description Quality: The percentage of noisy instances in the Proximity algorithm's concept description increased linearly with the noise level. Growth's percentage of noise in the concept descrip­ tion rose far more quickly. However, NTGrowth's filtering effect drastically slowed the influx of noisy instances into its concept description.

In summary, the noise-tolerant extensions assume that the classification records of noisy instances will distin­ guish them from non-noisy instances. Noisy instances will have poor classification accuracies because their nearby neighbors in the instance space will invariably have other classifications.

5 Experiments and Results

NTGrowth's performance degraded more slowly than the other two algorithms in these and other experiments with artificial domains. This encouraged us to test the noise­ tolerant extensions on six more challenging domains to see if these benefits recur during more practical applica­ tions. For comparison purposes, C4, Quinlan's modifica­ tion of ID3 [Quinlan, 1986] that performs pruning, was also tested. The databases' characteristics are given in Table 4. The average results are summarized in Table 5. (We have also included the benchmark algorithm Fre­ quency, which always guesses the class with the highest frequency. This algorithm provides a comparative mea­ sure of the other algorithm's utilities.) The instances chosen for the disjoint training and test sets were always randomly selected from the databases.

The LED Display and Waveform domains [Breiman et al. , 1984] are artificial domains with large amounts of noise (each LED attribute value has a 10% chance of being noisy and all Waveform attribute values contain an added noise factor) . For both domains, the three noise-tolerant extensions easily outperformed their re­ spective unextended algorithms. (However, NT K-nn Growth required 500 LED training instances to reach a

64.7% accuracy.) They also recorded equally good clas­ sification accuracies and incomparably lower storage re­ quirements than their respective all-instance saving al­ gorithms (Proximity and K-nn).

The Cleveland and Hungarian databases consist of cardiological records recorded at the Cleveland Clinic Foundation and Hungarian Institute of Cardiology re­ spectively. These domains contain a great deal of noise; Detrano [1988] reported that his discriminant analysis method for predicting heart disease resulted with accu­ racies of approximately 7S%. The NT algorithms again significantly outperformed the other algorithms.

The voting domain contains small amounts of noise. Therefore the payoff of the noise-tolerant algorithms was smaller than in more noisy domains. Finally, while NT­ Growth and NT Disjunctive Spanning performed well on the primary tumor domain, NT K-nn Growth required more training instances to perform well.

In summary, the noise-tolerant extensions of both the Growth and Disjunctive Spanning algorithms always recorded higher classification accuracies and lower stor­ age requirements than their ancestor algorithms. Also, their classification accuracies were always as good or bet­ ter than Proximity's. However, while NT K-nn Growth always recorded low storage requirements, the average learning curves generated from these experiments indi­ cate it is a much slower learner than its ancestor algo­ rithms. Only when given enough instances was it able to achieve accuracies as good as or better than the K-nn and K-nn Growth algorithms.

NTGrowth, NT Disjunctive Spanning, and C4 recorded the most consistently high classification accu­ racies among the ten algorithms (i.e., NTGrowth was within 3% and the others within 8% of the highest ac­ curacy recorded for each database). This indicates that these two noise-tolerant IBL algorithms should perform well in a large number of database applications .

6 Advantages and Limitations

We suspect that instance-based and decision tree learn­ ing algorithms can learn the same classes of concepts, namely those whose disjuncts have shapes in instance space that can be described by piecewise linear approx­ imations [Kibler and Aha, 1988]. However, IBL algo­ rithms have certain behavioral advantages. First, most decision tree and rule learning algorithms can form only hyper-rectangular approximations of concept boundaries in instance space. After extensive training, these hyper­ rectangular partitions form more detailed approxima­ tions that closely resemble IBL's more general piece­ wise linear approximations. Decision tree algorithms probably learn more slowly when the concepts' bound­ aries are not aligned with the attribute dimensions' axes. In fact, two studies have reported that IBL algorithms learn faster than decision tree algorithms [Shepard, 1983, Aha, 1989]. An extension of the CART decision tree learning algorithm employs linear combinations of at­ tributes (i .e., perceptrons) at its nodes to form piece­ wise linear approximations [Breiman et al., 1984, Section S.2]. However, this extension is expensive, requiring an explicit search for the best hyperplane separator in the instance space for each node's instances. IBL algorithms appear to be more convenient for learning some types of concepts .

Second, IBL algorithms are cost-effective incremental learning methods, requiring only O(III x IAI) attribute examinations to update the concept description for a single instance, where III is the size of the training set and instances are described with IAI attributes. (IBL storage-reducing algorithms require significantly fewer attribute examinations.) In comparison, both C4 and an incremental variant, ID4 [Schlimmer and Fisher, 1986], require at most O(III x IAI 2 ) attribute examinations to incorporate a single instance. IDS, another incremen­ tal variant, [Utgoff, 1988] requires only O(IAI 2 ) exam­ inations plus O(IA I x IAj I x I AI) additional examina­ tions for each pullup, where IA;I and IAil are the sizes of the two attribute domains involved in IDS's pullup process. However, this includes neither the costs for re­ cursive pullups, numeric-value partitioning, nor pruning.

Finally, Aha [1989] indicated that decision tree algo­ rithms build huge trees when learning a set of concept de­ scriptions that have different sets of relevant attributes. Aha presented Bloom, an extension of NTGrowth that addresses this problem by learning the relative attribute relevancies and building an independent concept descrip­ tion for each concept. (This allows Bloom to represent independent, overlapping, graded, and non-exhaustive concept descriptions.) Therefore, a better decision tree strategy may be to build a separate tree for each concept (or set of related concepts) .

C4 recorded higher classification accuracies than NT­ Growth in only two of the six experiments. However , the noise-tolerant IBL algorithms do not summarize their concept descriptions. We are currently working on solu­ tions to this problem, including combining the instance­ based and decision tree approaches, which would allow the IBL algorithms to (1) generate concise concept de­ scription summaries and (2) exploit an instance-indexing hierarchy so that similarities are computed only for a priori-known similar instances, thus further reducing in­ corporation (and classification) costs. The decision tree algorithm would benefit from reduced storage and in­ cremental learning costs. Case-based reasoning index­ ing schemes (e.g., [Bareiss and Porter, 1987]) may like­ wise assist the IBL approach, while our noise-tolerant algorithms could assist in judging the utility of cases. However, our noise-tolerating methods don't distinguish noisy instances from exceptions. While our methods might detect noisy-looking cases, further analyses should be made when this distinction is critical.

7 Conclusions

This paper described a noise-tolerant extension for instance-based learning algorithms. We showed that the NTGrowth algorithm's performance degrades more gracefully, in the presence of noise, than does the perfor­ mance of previous instance-based algorithms. In addi­ tion, the noise-tolerant extensions recorded lower storage requirements and higher classification accuracies than previous instance-based algorithms on several domains (both artificial and real-world). These gains occurred because the noise-tolerant extensions decreased the number of noisy instances used in classification decisions .

The key contribution of this paper was the intro­ duction of a simple voting method, combined with a statistical test, to assist in the detection and removal of noisy instances from concept descriptions. This method , like the pruning of decision trees [Quinlan, 1986, Niblett and Bratko, 1986] and the testing of the quality of CN2's complexes [Clark and Niblett, 1987], is based upon a simple significance test. Our method, which tol­ erates noise by gathering evidence of correctness before employing information for classification decisions, is a representation-independent technique. An amalgama­ tion of IBL algorithms with those that yield compilations (in the forms of rules or decision trees) should result with a superior learning algorithm having lower updat­ ing costs, lower storage requirements, and the ability to present concept descriptions concisely.

Acknowledgements

Thanks to Peter Clark, Doug Fisher, Wayne lba, Pat Langley, Haym Hirsh, Jeff Schlimmer, Jim Wogulis, David Ruby, Marc Albert, and Stephanie Aha for their valuable comments on previous drafts of this paper. We would like to thank M. Zwitter and M. Soklic (Insti­ tute of Oncology, Ljubljana, Yugoslavia) for donating the primary tumor database, Robert Detrano (V.A. Cen­ ter, Long Beach, CA) for the Cleveland database, and Andras J anosi (Hungarian Institute of Cardiology, Bu­ dapest) for the Hungarian database. These are among the 38 databases available from the U .C.I. Repository of Machine Learning Databases.