Inductive Learning in Less Than One Sequential Data Scan

1 Introduction

Most recent research on scalable inductive learning over very large dataset focuses on eliminating memory-constraints and reducing the number of sequential data scans (or the total number of times that the training file is accessed from sec­ ondary storage), particularly for decision tree construction. State-of-the-art decision tree algorithms (SPRINT [Shafer et al., 1996], RainForest [Gehrke et at., 1998], and later BOAT [Gehrke et at., 1999] among others) still scan the data multiple times, and employ rather sophisticated mechanisms in implementation. Most recent work [Hulten and Domingos, 2002] applies Hoeffding inequality to decision tree learning on streaming data in which a node is reconstructed iff it is sta­ tistically necessary. Besides decision tree, there hasn't been much research on reducing the number of data scans for other inductive learners. The focus of this paper is to propose a general approach for a wide range of inductive learning algo­ rithms to scan the dataset less than once from the secondary storage. Our approach is applicable not only to decision trees but also to other learners, e.g., rule and naive Bayes learners.

Ensemble of classifiers has been studied as a general ap­ proach for scalable learning. Previously proposed meta­ learning [Chan, 1996] reduces the number of data scans to 2. However, empirical studies have shown that the accuracy of the multiple model is sometimes lower than respective sin­ gle model. Bagging [Breiman, 1996] and boosting [Freund and Schapire, 1997] are not scalable since both methods scan the dataset multiple times. Our proposed method scans the Shaw-Hwa Lo Statistics Department, Columbia University New York, NY 10027

slo®stat.columbia.edu

dataset less than once and has been empirically shown to have higher accuracy than a single classifier.

Based on averaging ensemble, we propose a statistically­ based multiple model inductive learning algorithm that scans the dataset less than once. Previous research [Fan et at., 2002b] on averaging ensemble has shown that it is more efficient and accurate than both bagging and meta-learning. In this paper, we apply Hoeffding inequality to estimate the probability that the partial and complete models are equal in accuracy. When the probability is higher than a threshold, the algorithm stops model construction and returns the cur­ rent model, resulting in less than one sequential scan of the dataset. Our objective is completely different from [Hulten and Domingos, 2002] on determining whether to change the shape of a decision tree. Unlike previous research [Hulten and Domingos, 2002; Gehrke et al., 1999], our algorithm is not limited to decision tree, but is applicable to a wide range of inductive learners. When it is applied to decision tree learning, the accuracy is higher than a single decision tree. Another advantage is that the ensemble reduces the asymp­ totic complexity of the algorithm besides scanning less data. One important distinction is that we are interested in reduc­ ing sequential scan from secondary storage. Once the data can be held entirely in memory, the base learning algorithm is allowed to scan the data in memory multiple times.

2 One Scan

We first describe a strawman algorithm that scans the data set exactly once, then propose the extension that scans the data set less than once. The strawman algorithm is based on probabilistic modeling.

2.1 Probabilistic Modeling

Suppose p( ei lx) is the probability that X is an instance of class fi. In addition, we have a benefit matrix b[fi', fi] that records the benefit received by predicting an example of class ei' to be an instance of class ei. For traditional accuracy­ based problems, Vi, b[l'i, l'i] = 1 and Vi' f. i, b[fi', l'i] = 0. For cost-sensitive application such as credit card fraud detec­ tion, assume that the overhead to investigate a fraud is $90 and y(x) is the transaction amount, then b[fraud, fraud] = y(x) - $90 and b[-.fraud, fraud] = -$90. Using benefit matrix and probability, the expected benefit received by predieting x to be an instance of class f; is

Based on optimal decision policy, the best decision is the la­ bel with the highest expected benefit:

Assuming that f(x) is the true label of x, the accuracy of the decision tree on a test data set ST is

For traditional accuracy-based problems, A is always normal­ ized by dividing ISTI; for cost-sensitive problems, A is usu­ ally represented in some measure of benefits such as dollar amount. For cost-sensitive problems, we sometimes use "to­ tal benefits" to mean accuracy.

2.2 The Strawman Algorithm

The strawman algorithm is based on averaging ensemble [Fan et al., 2002b]. Assume that a data setS is partitioned into K disjoint subsets Si with equal size. A base level model Ci is trained from each Si. Given an example x, each classi­ fier outputs individual expected benefit based on probability Pi(f;,lx)

The averaged expected benefit from all base classifiers is therefore

We then predict the class label with the highest expected re­ turn as in Eq[2].

The obvious advantage is that the strawman algorithm scans the dataset exactly once as compared to two scans by meta-learning and multiple scans by bagging and boosting. In previous research [Fan et al., 2002b], the accuracy by the strawman algorithm is also significantly higher than both meta-learning and bagging. [Fan et al., 2002b] explains the statistical reason why the averaging ensemble is also more likely to have higher accuracy than a single classifier trained from the same dataset.

3 Less Than One Scan

The less-than-one-scan algorithm returns the current ensem­ ble with k ( < K) number of classifiers when the accuracy of current ensemble is the same as the complete ensemble with high confidence. For a random variable y in the range of R = a - b with observed mean of Y after n observations, without any assumption about the distribution of y, Hoeffd­ ing's inequality states that with probability ~ p, the error of Y to the true mean is at most

For finite population of size N, the adjusted error is

The range R of expected benefit for class label f; can be found from the index to the data, or predefined. When k base models are constructed, the Hoeffding error fk can be computed by using Eq[8]. For data example x, assume than E(falx) is the highest expected benefit and E(fblx) is the second highest, Ek (fa) and fk ( fb) are the Hoeffding errors. If E(falx)-~:k(fa) > E(fblx)+~:k(fb) or E(falx)-E(fblx) > Ek(fa) + Ek(fb), with confidence~ p, the prediction on x by the complete multiple model and the current multiple model is the same. Otherwise, more base models will be trained. The algorithm is summarized in Algorithm 1.

Scan of validation set SV

If an example x satisfies the confidence p when k classifiers are computed, there is no utility to check its satisfaction when more classifiers are computed. This is because that an ensem­ ble with more classifiers is likely to be a more accurate model. In practice, we can only read and keep one example x from the validation set in memory at one time. We only read a new instance from the validation set if the current set of classi­ fiers satisfy the confidence test. In addition, we keep only the predictions on one example at any given time. This guaran­ tees that the algorithm scans the validation dataset once with nearly no memory requirement.

Training Efficiency

The extra overhead of the Hoeffding-based less than one scan algorithm is the cost for the base classifiers to predict on the validation set and calculate the statistics. All these can be done in main memory. As discussed above, we can predict on one example from the validation set at any given time. As­ sume that we have k classifiers at the end and n is the size of the validation set, the total number of predictions is approx­ imately n~k on average. The calculation of both mean and standard deviation can be done incrementally. We only need to keep I: Xi and I: X[ for just one example at anytime and calculate as follows:

The average number of arithmetic operation is approximately 3 X n~k .

The problem that the proposed algorithm solves is one in which the training set is very large and the 110 cost of data scan is the major overhead. When 110 cost is the bottleneck, the extra cost of prediction and statistical analysis is mini­ mum.

4 Experiment

In empirical evaluation, we first compare the accuracy of the complete multiple model (one scan as well as less than one scan) and the accuracy of the single model trained from the same data set. We then evaluate the amount of data scan and accuracy of the less than one scan algorithm as compared to the one scan models. Additionally, we generate a dataset with biased distribution and study the results of the less than one scan algorithm.

4.1 Datasets

The first one is the well-known donation data set that first ap­ peared in KDDCUP'98 competition. Suppose that the cost of requesting a charitable donation from an individual x is $0.68, and the best estimate of the amount that x will donate is Y(x) . Its benefit matrix is:

As a cost-sensitive problem, the total benefit is the total amount of received charity minus the cost of mailing. The data has already been divided into a training set and a test set. The training set consists of 95412 records for which it is known whether or not the person made a donation and how much the donation was. The test set contains 96367 records for which similar donation information was not published un­ til after the KDD'98 competition. We used the standard train­ ing/test set splits to compare with previous results. The fea­ ture subsets were based on the KDD'98 winning submission.

To estimate the donation amount, we employed the multiple linear regression method.

The second data set is a credit card fraud detection prob­ lem. Assuming that there is an overhead $90 to dispute and investigate a fraud and y(x ) is the transaction amount, the fol­ lowing is the benefit matrix:

As a cost-sensitive problem, the total benefit is the sum of recovered frauds minus investigation costs. The data set was sampled from a one year period and contained a total of 5M transaction records. We use data of the last month as test data (40038 examples) and data of previous months as train­ ing data (406009 examples).

The third data set is the adult data set from UCI repository. For cost-sensitive studies, we artificially associate a benefit of $2 to class label F and a benefit of $1 to class label N, as summarized below:

We use the natural split of training and test sets, so the re­ sults can be easily replicated. The training set contains 32561 entries and the test set contains 16281 records.

4.2 Experimental Setup

We have selected three learning algorithms, decision tree learner C4.5, rule builder RIPPER, and naive Bayes learner. We have chosen a wide range of partitions, K E {8, 16, 32, 64, 128, 256}. The validation dataset SV is the complete training set. All reported accuracy results were run on the test dataset.

4.3 Experimental Results

In Tables 1 and 2, we compare the results of the single classi­ fier (which is trained from the complete dataset as a whole), one scan algorithm, and the less than one scan algorithm. We use the original "natural order" of the dataset. Later on in Section 4.4, we use a biased distribution. Each data set under study is treated both as a traditional and cost-sensitive prob­ lem. The less than one scan algorithm is run with confidence p = 99.7%.

Accuracy Comparison

The baseline traditional accuracy and total benefits of the sin­ gle model are shown in the two columns under "single" in Tables 1 and 2. These results are the baseline that the one scan and less than one scan algorithms should achieve. For the one scan and less than one scan algorithm, each reported result is the average of different multiple models with K rang­ ing from 2 to 256. In Tables 1 and 2, the results are shown in two columns under accuracy and benefit. As we compare the respective results in Tables 1 and 2, the multiple model either significantly beat the accuracy of the single model or have very similar results. The most significant increase in both ac­ curacy and total benefits is for the credit card data set. The total benefits have been increased by approximately $7,000"' $10,000; the accuracy has been increased by approximately 1% "' 3%. For the KDDCUP'98 donation data set, the total C45

benefit has been increased by $1400 for C4.5 and $250 for NB.

We next study the trends of accuracy when the number of partitions K increases. In Figure 1, we plot the accuracy and total benefits for the credit card data sets, and the total benefits for the donation data set with increasing number of partitions K . C4.5 was the base Ieamer for this study. As we can see clearly that for the credit card data set, the multiple model consistently and significantly improve both the accuracy and total benefits over the single model by at least 1% in accuracy and $40000 in total benefits for all choices of K. For the donation data set, the multiple model boosts the total benefits by at least $1400. Nonetheless, when K increases, both the accuracy and total benefits show a slow decreasing trend. It would be expected that when K is extremely large, the results will eventually fall below the baseline.

Another important observation is that the accuracy and to­ tal benefit of the less than one scan algorithm are very close to the one scan algorithm. Their results are nearly identical.

Data Scan

In both Tables 1 and 2, we show the amount of data scanned for the less than one scan algorithm. It ranges from 40% (0.4) to about 70% (0.7). The adult dataset has the most amount of data scanned since the training set is the smallest and it requires more data partitions to compute an accurate model. C4.5 scans more data than both RIPPER and NB. This is be­ cause we generate the completely unpruned tree for C4.5, and there are wide variations among different models.

In Table 3, we compare the differences in accuracy and amount of training data when the validation set is either read completely by every classifier (under "Batch") or sequentially only by newly computed base classifiers (under "Seq") (as discussed in Section 3). Our empirical studies have found that "Batch" mode usually scans approximately 1% to 2% more training data, and the models computed by both methods are nearly identical in accuracy. The extra training data from the C45

"batch" method is due to the fact that some examples satis­ fied by previously learned classifiers have high probability, but may not necessarily be satisfied by more base classifiers. However, our empirical studies have shown that the differ­ ence in how the validation set is handled doesn't significantly influence the final model accuracy.

4.4 Biased Distribution

When a data is biased in its distribution, the less than one scan algorithm need to scan more data than uniform distri­ bution to produce an accurate model. With the same amount of datascan, it may not have the same accuracy as uniform distribution. We have created a "trap" using the credit card dataset. We sorted the training data with increasing transac­ tion amount. The detailed results are shown in Table 4(a) and (b). The accuracy (and total benefits) in Table 4(a) are nearly identical to the results of "natural distribution" as reported in Tables 1 and 2. However, the amount of datascan by the less than one scan algorithm is over 0.9 as compared to approxi­ mately 0.6 for natural distribution. As shown in Table 4(b), when the datascan is less than 0.9 (the confidence is not satis­ fied and less one scan will continue to compute more model), the total benefits are much lower. When distribution is biased, the variations in base classifiers' prediction are wider. It re­ quires more data to compute an accurate model imd the less than one scan algorithm is performing in the correct way.

4.5 Training Efficiency

We recorded both the training time of the batch mode sin­ gle model, and the training time of both the one scan al­ gorithm and less than one scan algorithm plus the time to classify the validation set multiple times and statistical es­ timation. We then computed serial improvement, which is the ratio that the one scan and less than one scan algo­ rithm are faster than training the single model. In Figure 2, we plot results for the credit card dataset using C4.5. Our C45

training data can fit into the main memory of the machine. Any single classifier algorithm that reduces the number of data scan [Shafer et al., 1996; Gehrke et al., 1998; 1999; Hulten and Domingos, 2002] will not have training time less than this result. As shown in Figure 2, both one scan and less than one scan algorithm are significantly faster than the single classifier, and the less than one scan algorithm is faster than the one scan algorithm.

5 Related Work

To scale up decision tree learning, SPRINT [Shafer et al., 1996] generates multiple sorted attribute files. Decision tree is constructed by scanning and splitting attribute lists, which eliminates the need for large main memory. Since each at­ tribute list is sorted. for a data file with f attributes and N examples, the total cost to produce the sorted lists is f · O(N ·log(N)). External sort is used to avoid the need for main memory. Each attribute list has three columns-a unique record number, the attribute value and the class label; the to­ tal size of attribute lists is approximately three times the size of the original data set. When a split takes places at a node, SPRINT reads the attribute lists at this node and breaks them into r sets of attribute lists for r child nodes, for a total of f file read and r · f file writes. Later, RainForest [Gehrke et al., 1998] improves the performance of SPRINT by pro­ jecting attribute list on each unique attribute value into an AVC-set. The complete AVC-sets of all attributes are called AVC-group. When the AVC-group can be held in main mem­ ory, the selection of predictor attribute can be done efficiently. To construct the initial AVC-group, it incurs the same cost as SPRINT to construct initial attribute lists plus one more scan over the sorted lists to project into AVC-sets. Whenever a split happens, RainForest has to access the data file again and reconstruct the AVC-group for child nodes. The exact num­ ber of read and write is based on variations of RainForest that is chosen. In the best scenario where the AVC-group of ev­ ery node in the tree fit in memory, the RF-read version still has to scan the whole data once at each level of the tree and write it into r files. When this condition is not met, Rain­ Forest solves the problem by multiple read and write. More recently, BOAT [Gehrke et al., 1999] constructs a "coarse"

Table 4: Performance of less than one scan under biased dis­ tribution

tree from a data sample that can fit into main memory. The splitting criterion in each node of the tree is tested against multiple decision trees trained from bootstrap samples of the sampled data. It refines the tree later by scanning the com­ plete data set, resulting in a total of two complete data read.

Meta-learning [Chan, 1996] builds a tree of classifiers and combine class label outputs from base classifiers. It is based on heuristics and the total number of datascan is two. The im­ provements by our methods are in many folds. We combine probabilities instead of class labels. The combining technique is straightforward and can estimate the final accuracy prior to full construction. The total amount of sequential scan is less than once. There is a strong statistical reason to support why the multiple model method works [Fan et al., 2002b] . Besides meta-learning, both bagging [Breiman, 1996] and boosting [Freund and Schapire, 1997] have been shown to have higher accuracy than a single model. However, bagging and boosting scan the dataset many times, and are not scal­ able for large dataset. Previous research [Fan et al., 2002b] has shown the our combining method is more accurate than bagging.

One earlier work to use Hoeffding's inequality is online ag­ gregation [Hellerstein et al., 1997] to estimate the accuracy of aggregate queries. When the confidence about the accuracy of the partial query is sufficient, the user can terminate the query to avoid a complete scan. One recent work using Ho­ effding inequality is on building decision tree from streaming data [Hulten and Domingos, 2002]. They keep the number of examples that satisfy or fail the predicate of a node in the tree. When it is confident that the current node is not accu­ rate for the new data, it will be reconstructed. One limitation of [Hulten and Domingos, 2002] is that it is only applicable to decision tree learning. Our ensemble method using Ho­ effding's inequality is applicable to a wide range of induc­ tive learners. Empirically, we have applied it to decision tree, rule Ieamer as well as naive Bayes Ieamer. Beside its gen­ erality, the proposed one scan and less than one scan algo­ rithms have been shown to have potentially higher accuracy than the single model (existing approaches are single model method [Hulten and Domingos, 2002; Gehrke et al., 1999; Shafer et al., 1996; Gehrke et al., 1998]). Another advantage is the asymptotic complexity using the less than one scan al­ gorithm is approximately k · 0( R) while computing a sin­ gle model is still O(n). Our empirical studies have shown that both the one scan and less than one scan algorithms are significantly faster than learning a single model. In previous work [Fan et al., 2002a], we have used Central limit theo­ rem (CLT) to implement a concept of progressive modeling where we estimate the range of accuracy of the final model. The learning stops when the estimated accuracy of the final falls within a tolerable range with confidence p. CLT requires the data distribution to be uniform. Hoeffding inequality has a different implication, in which we estimate the probability that the partial and final models are exactly the same.

6 Conclusion

In this paper, we propose two scalable inductive learning al­ gorithms. The strawman multiple model algorithm scans the data set exactly once. We then propose a less than one scan extension based on Hoeffding's inequality. It returns a partial multiple model when its accuracy is the same as the com­ plete multiple model with confidence 2: p. Since Hoeffding inequality makes no assumption about the data distribution, the advantage of this method is that the data items can be re­ trieved sequentially. We have also discussed how to sequen­ tially read the validation set exactly once using minimal mem­ ory. We have evaluated these methods on several data sets as both traditional accuracy-based and cost-sensitive problems using decision tree, rule and naive Bayes learners. We have found that the accuracy of all our methods are the same or far higher than the single model. The amount of data scan by the less than one scan algorithms range from 0.45 to 0.7 for the original natural distribution of data. For a significantly biased dataset, the amount of datascan by the less than one scan al­ gorithm is over 0.9. It needs extra data to resolve the bias in data distribution in order to compute an accurate model. In addition, our empirical studies have shown that both methods are significantly faster than computing a single model even when the training data can be held in main memory, and the less than one scan algorithm is faster than the one scan algo­ rithm.