Classifiers: A Theoretical and Empirical Study

1 Introduction

Systems for learning classification trees [Quinlan, 1986; Cestnik et al., 1987] are common in machine learning, statistics and pattern recognition. Despite these suc­ cesses, the study presented here is not motivated by a view that tree classifiers are inherently superior to other learning systems (see for instance, the argument against so-called universal learning algorithms in [Bun­ tine, 1990b]). Rather, this study is motivated by the view that tree learning is an ideal benchmark problem for studying learning theories. The problem is used here to gain insight into generic problems in empirical learning, and to explore a general strategy for designing learning algorithms.

First, current tree learning methods are mature in that many modifications have been suggested in recent years, but little real gain has been made 1 . There are now many different tree learning methods and none clearly superior [Mingers, 1989]. The systems have stood the test of time and are now widely used for benchmarking and compar­ ative studies. If an algorithm design strategy yields a superior tree learning algorithm despite this tough com­ petition, it is likely the strategy will be successful on other learning tasks.

·Research Institute for Advanced Computer Science

1 Except, perhaps, in the area of learning strictly logical rules where recent techniques learn new terms; but the focus of this paper is primarily learning noisy or uncertain con­ cepts, where gains have been more incremental.

Second, tree learning is a common meeting ground for the different areas of inquiry outside of AI that have learning theories of some form or another such as classi­ cal statistics [Breiman et al., 1984] and minimum encod­ ing approaches [Rissanen, .1989]. This provides a rare opportunity to contrast these different learning theories theoretically as well as empirically. Comparative studies conducted to date in AI have provided little understand­ ing about generic principles of algorithm design, partly because comparisons have been made of algorithms that use different knowledge representations, and compar­ isons have largely ignored the theoretical principles on which the algorithms were based.

Finally, classification trees have been the framework in which a number of discoveries have been made in ma­ chine learning: the overfitting problem (related to the accuracy-complexity tradeoff and Ockham's razor) , in­ cremental algorithms [Schlimmer and Granger Jr.,1986], and interactive induction [Shapiro, 1987]. The learn­ ing problem tree systems tackle is difficult enough to be considered "unlearnable," yet simple enough so not requiring the specialized machinery to learn relations or do constructive induction. In this spirit, this study presents a number of additional discoveries about prob­ lems generic to empirical learning.

This paper reviews the Bayesian development of a sys­ tem for learning tree classifiers, from the theoretical ba­ sis, through the hacking required to make the system work, to comparative results with other systems. The development is presented as a generic algorithm design strategy in the second section, and the results discussed in the third section. More detail of the statistical as­ pects of the system can be found in [Buntine, 1990a; Buntine, 1990c]. Because of the large number of differ­ ent trials and data sets that were used, full detail of the results are reported elsewhere [Buntine, 1990c].

This paper also discusses some insights that have come out of this study: an emerging trend in machine learning towards the use of multiple models [Kwok and Carter, 1990; Garns, 1989; Jacobs et al., 1991], a generic method to overcome the problem of repeated restructuring in incremental learning [Crawford, 1989], and a better un­ derstanding of learning theories and their role in helping us design learning algorithms. These are discussed in the fourth section.

We can now design algorithms for many other super­ vised and model learning tasks given just a probabilistic representation for the kind of knowledge to be learned. As an illustration, a method is outlined in the fifth section for learnin~ Bayesian networks [Lauritzen and Spiegelhalter, 1988J, a common representation in medical expert systems. This is a model learning task. The de­ sign strategy can also be applied to other learning tasks such as probabilistic rule systems, n-gram models (such as bigram and trigram models) used in speech recogni­ tion and natural language, and the function-finding task that is the basis of scientific discovery algorithms. The strategy has also been applied to analyse the training of feed-forward neural networks [Buntine and Weigend, 1991], where popular heuristic procedures for cost func­ tions and network pruning were found to conform well to corresponding methods developed from Bayesian first principles.

2 The Algorithm Design Strategy

The algorithm design. strategy presented here is based on approximating Bayesian decision theory. The justifica­ tion for Bayesian decision theory comes from fundamen­ tal principles of how uncertain reasoning should be done [Berger, 1985]. The theory applies widely in inference and plausible reasoning and its use is continually ex­ panding in AI. But there is not a single "Bayesian learn­ ing algorithm," as some people mistakenly believe when they learn about Bayesian classifiers [Tou and Gonzalez, 1974]. Rather, Bayesian decision theory presents com­ putational guidelines on how learning should be done for many different learning problems, including for instance, improving an approximate theory using data.

The basic tenet of Bayesian decision theory is that if we do not know something with reasonable certainty, then we should look at some reasonable and mutually ex­ clusive alternatives and weigh them up, to help us make a "representative" decision. A reasonable alternative is one we currently have high subjective belief in. I will first explain how this applies to trees [Buntine, 1990a], to introduce the notation. This is done for the two-class problem with discrete tests at nodes, but easily extends to the multi-class problem, and adjustments for real­ valued tests at nodes exist [Buntine, 1990c, Sec.6.5.5]. The formulation is sufficiently general so that it could just as well be applied to other models such as proba­ bilistic rules, Bayesian networks, or one of many other knowledge representations that have a probabilistic in­ terpretation.

Class probability trees have a vector of class proba­ bilities at their leaves [Breiman et al., 1984], and they represent a conditional probability distribution of class value conditioned on example value. A particular class probability tree can be represented by its discrete com­ ponent T, the tree structure given by the shape of the tree and the tests at the leaves, and its continuous component 8, the leaf class probabilities. This gives the conditional probability distribution Pr( c'l x', T, 8), which is the like­ lihood function for the class probability tree specified by T and 8 for the training example (c', x').

Suppose we are given a training sample of examples z and their classes c, together with a new example x' whose class we wish to predict. If the goal is to mini­ mize errors in prediction (other utility functions can be handled similarly), decision theory says we should choose the class c' to maximize the posterior class probability Pr(c' I x',z,C). Using the tree model, this is the pos­ terior average of the class probabilities predicted for c' from all possible class probability trees:

where the summations are over the space of all poBBible tree structures T, and

Formula (1) simply says to average the class predictions made for each tree structure, where Pr(T I z, C), the posterior probability ofthe tree structure T, is the weight used in the averaging process. In this formula, Pr(T, 8) is the prior on the space of class probability trees, and Pr(cl z, T, 8) the likelihood of the training sample.

The algorithm design strategy is based on designing a heuristic procedure to find a single structure or set of structures that can be used to approximate Formula (1). This is described by the following 6 steps, and Table 1 gives the results of the analysis.

1. Precisely define the form of knowledge to be learned by representing it in terms of a parameterized likelihood function. A particular parameterization is referred to as a model which has a structural (discrete) and a continu­ ous component as described for trees.
2. Develop a prior over the structural and contin­ uous components of the model. The form of the prior should be flexible enough so that it can be chan~ed from application to application. In [Buntine, 1990aJ, a range of priors are presented for trees. One is given in the table. The prior on the tree structures, Pr(T), is not given but could, for instance, be assumed uni­ form. The prior on the continuous component is a product of symmetric beta distributions over the prob­ abilities 8. The function B(n, m) given there is the beta function found in many mathematical handbooks. B(n,m) ~ 1/(n+ m) ·1/C;:+m.

3. Given a training sample Sample, determine a suitably efficient way of computing or approximating the posterior of the structural component of the model. See [Buntine and Weigend, 1991] for an approximation in the more complex domain of feed-forward neural networks.

4. Devise a heuristic search procedure for searching the space of structures to find structures with high posterior. A simple one-ply lookahead procedure can be tried, which corresponds to the standard tree growing algorithm [Quinlan, 1986], although two-ply or three­ ply versions could also be tried. Start with the trivial structure, the empty tree. Then consider extending the structure by a single ply, which for trees means growing a single node by adding a test with leaves at the outcomes of the test. A heuristic measure to evaluate the qual­ ity of the new growth is given in the table. To prevent overflow /underflow, this measure has to be calculated in log-space. The measure behaves similarly to Quin­ lan's information gain heuristic, but has some correction terms for multivalued attributes and small samples. This heuristic can also be used as a stopping rule [Cestnik et al., 1987].

5. Given a training sample Sample and a structure T, determine a formula or approximation for the poste­ rior expected values of the parameters 8, as required for Formula ( 1).

6. Devise a procedure for approximating the sum­ mation of Formula ( 1) by a small set of high posterior structures. Several suggestions are given below. This is currently an active area of research.

Minimum encoding approaches [Rissanen, 1989; Wal­ lace and Freeman, 1987] to supervised learning and the so-called "most probable model" (Bayesian) approach are first-order approximations to Formula ( 1), because they attempt to find a single high posterior structure. Step 6 in the design strategy above is the main improve­ ment suggested here, because it suggests how to improve on this.

There are three techniques for performing Step 6. These correspond to different ways of estimating the sum in Formula ( 1):

• Smoothing: The sum can be computed in closed form if it is restricted to the set of tree structures obtained by pruning a large tree structure in all possible ways. A linear time algorithm is given in [Buntine, 1990c, Lemma 6.5.1]. This is called smoothing because it is equivalent to smoothing out the class probabilities at the leaf of a tree by averaging them with some class probabilities from interior nodes of the tree.
• Averaging: The sum can be approximated by search­ ing for and storing many dominant terms, i.e. many high posterior trees structures. We can build multi­ ple tree structures, and combine them together effi­ ciently in an AND-OR representation called option trees. Growing option trees and then applying a similar summation process to smoothing is called tree averaging.
• Multiple Models: The sum can be approximated by using importance sampling and Monte Carlo esti­ mation. That is, a few tree structures are gener­ ated in approximate proportion with their posterior (this is done using the tree growing heuristic [Bun­ tine, 1990a]), and their class probability vectors uni­ formly averaged.

3 Experimental Results

Reimplementations of CART [Breiman et al., 1984], C4 [Quinlan, 1988], and a generic minimum encoding approach were compared with the Bayesian approaches 2 · The algorithms were applied to 12 different data sets with a range of characteristics. These included Quin­ lan's hypothyroid and XD6 data [Quinlan, 1988], the CART digital LED problem [Breiman et al., 1984], three medical domains made available by Bratko's induction group [Cestnik et al., 1987], and a variety of other data sets from the Irvine Machine Learning Database such as "glass," "voting records," "hepatitus," and "mush­ rooms." Data sets where divided into training/test pairs, a classifier was built on the training sample and the ac­ curacy, predicted accuracy, and mean square error esti­ mated on the test sample. This was done for 20 random trials of the training/test pair, and for 4 different train­ ing set sizes, and significance of difference between two algorithms was checked using the paired t-test.

Of the algorithms tried, a generic minimum encod­ ing approach, (re-)CART, (re-)C4, Bayesian smoothing and Bayesian averaging, the averaging approach using a uniform prior on tree structures was the only approach that consistently produced the best predictions. In most cases it was pairwise significantly better than all other non-Bayesian approaches at the 5% level. Bayesian av­ eraging with a two-ply lookahead during growing yielded improvement in predictive accuracy averaged over 20 tri­ als as often as high as 2-3%, sometimes more. With a one-ply lookahead, the improvement is not as dramatic but still significant. One has to be cautious in interpret­ ing this result, however, because option trees are more than just a single decision tree, they effectively involve an extension of the model space. Also the growing of option trees sometimes involved extra orders of magni­ tude in time and space. Although this only occurred for small samples, or where trees were inappropriate for the learning problem (like XD6 which is a DNF concept poorly expressed using a tree). Certainly the Bayesian approaches are competitive, and they appear to be su­ perior for smaller samples.

For many of the data sets, it was appropriate to se­ lect a prior that had stronger ·preference towards smaller trees. When this was done, Bayesian smoothing of a single tree gave good predictions, often as good as the Bayesian averaging with one-step lookahead. This is use­ ful because we would not always wish to go to the com­ putational expense of Bayesian averaging, or we may re­ quire just a single tree for explanatory purposes.

A second point of comparison of the algorithms is the parameters available when driving the algorithms. CART and C4 have default settings for their parame­ ters. With CART, heavy pruning can be achieved using the 1-SE rule rather than the 0-SE rule. The number of partitions to use in cross validation cost complexity pruning can also be changed, but the effect of this is unclear, especially since leaving-one-out cross validation cost complexity pruning gives poor predictive accuracy. The minimum encoding approaches are (according to the purist) free of parameters. However, these approaches often strongly overprune, so Quinlan and Rivest [ Quinlan and Rivest, 1989] introduce a parameter that al­ lows lighter pruning. So all approaches Bayesian and non-Bayesian have parameters that allow more or less pruning. These can be set depending on the amount of structure believed to exist in the data. In the fuller Bayesian approach with option trees and Bayesian aver­ aging, choices available also allow greater search during growing and fuller elaboration of the available optional trees. These parameters have the useful property that predictive accuracy (or some other utility measure) and computational expense are on average monotonic in the value of the parameter. The parameter setting allows improved predictive accuracy at computational expense.

2 The tree algorithms were written in C and integrated with an experiment control package. The entire suite is avail­ able from the author.

4 Discussion

4.1 Multiple models

Machine learning research, as with classical statistics and minimum encoding methods, has been largely concerned to date with trying to find the best single tree, the best non-redundant rule set, or the best relational rule ex­ plaining the data.

Several researchers have now reported being able to significantly improve learning performance by instead working with multiple models. This is an approximate method for doing the averaging presented in Section 2, and is different from the technique of combining inde­ pendent sources of knowledge multiplicatively, using the probability formula for independence (the basis of "id­ iot" Bayes classifiers).

K wok and Carter used a heuristic approximation to Bayesian decision theory [Kwok and Carter, 1990]; they built multiple decision trees and when processing a new example, processed it with each tree individually and av­ eraged the multiple class predictions. Gams discussed the notion of "redundant knowledge" [Gams, 1989], where he weighs up the predictions of several overlap­ ping rules when classifying a new example. Jacobs et al. present another approach that does adaptive mixing of multiple feed-forward networks [Jacobs et al., 1991]. A survey of some related theoretical work in "aggregrating learning strategies" and "weighted majority" is given in [Haussler et al., 1991].

Suggested modifications to learning algorithms rarely perform consistently better (see for instance [Mingers, 1989]). The most striking thing about the use of multiple models is that it does appear to give consistently better performance, and can often be implemented as a control module on top of an existing algorithm.

4.2 Incremental learning algorithms

Incremental learning applies when new training exam­ ples are continually being supplied and we wish to up­ date our current hypothesis( es) given the few additional examples. The contrasting approach is batch learning where examples are supplied in one batch. The major approach for developing an incremental algorithm is to modify a batch learning algorithm. This has the advan­ tage that the long sequence of theoretical and empirical work that led to the development of the algorithm is not wasted. Some algorithms, however, are designed to be incremental from the beginning [Gennari et al., 1990]. These algorithms can suffer from order-sensitivity [Lan­ gley and McKusick, 1990], which is an incremental man­ ifestation of the overfitting problem, a problem which is largely solved for batch algorithms.

There are two broad cases where a batch algorithm can be easily converted to an incremental algorithm. In the first case, Bayesian classifiers and many classical sta­ tistical methods are naturally incremental because they are calculated from simple summary statistics such as means and variances that are readily updated with ad­ ditional data. These summary statistics are an example of sufficient statistics, discussed in most advanced statis­ tical texts. In the second case, Perceptrons, most neural net methods, Autoclass [Cheeseman et al., 1988], and many classical statistical clustering algorithms use itera­ tive convergence methods. These are not naturally incre­ mental, because their performance is generally poor with only one iteration of the training sample. But because of their iterative nature, they can be easily modified to form incremental versions. For instance, one could add the new training data to the next iteration.

Some batch algorithms do not lend themselves nat­ urally to incremental versions. In these cases, as done with trees [Schlimmer and Granger Jr., 1986], the batch learning algorithm is differentiated. That is, an incre­ mental algorithm is designed that attempts to do the least amount of work to modify a tree given new data so that it looks as if the tree was constructed from the entire training sample using the corresponding batch al­ gorithm. Crawford reports this leads to the problem of repeated restructuring [Crawford, 1989]. This occurs in trees when some subtree is repeatedly restructured dur­ ing incremental updating due to vacillation in what is currently considered the "best" test at the root of the subtree. This occurs particularly with learning noisy concepts (earlier incremental studies looked at logical concepts). The Bayesian methods offer a generic rem­ edy for this problem. Essentially, we only restructure if we strongly believe the new substructure will be bet­ ter, rather than immediately restructuring the moment some new substructure seems slightly better. The loga­ rithm of the lookahead measure given in Table 1 returns a measure whose units are in log-odds. So one can easily implement an algorithm that only changes the current test at a node if there is another test that has a good log-odds (e.g. > 1.0) of being better. This would prevent vacillation, and experiments show it does not unduly ef­ fect predictive accuracy.

4.3 Comparisons of learning theories

A basic tool of learning theory in pattern recognition and computational learning theory is uniform conver­ gence. If a sample size is large enough, uniform con­ vergence theory provides bounds on the predictive per­ formance of classifiers learned by minimizing empirical error [Vapnik, 1982]. In practice when sample sizes are not large enough, one needs to make a tradeoff between the complexity of the hypothesis chosen and the accuracy of the fit to the data. Here, uniform convergence meth­ ods give less guide, only asymptotic (i.e. large sample)

theory regarding their performance (see, for instance, the principle of structural risk minimization in [Vapnik, 1982]). These techniques have no theoreticaljustification that they will provide good average-case performance on smaller samples. Some experimental comparisons are given in [Buntine, 1990c]. Learning theoreticians are now using Bayesian methods [Haussler et al., 1991] to analyse the smaller sample case, as suggested earlier by Buntine [Buntine, 1989].

Statisticians overcome these overfitting problems with a variety of resampling techniques (as applied to trees, see [Breiman et al., 1984; Crawford, 1989]) that have good intuition and performance, but again only have asymptotic theory. The tree experiments (using cross­ validation) show these techniques work well, however they can overprune, so do not have the consistency of the full Bayesian approach when sample sizes are smaller. They are quick to code in many cases and hence offer a viable alternative.

Only Bayesian decision theory is able to claim that it is the most rational alternative in the information poor environment of learning from smaller samples [Berger, 1985]. Minimum encoding approaches [Rissanen, 1989] are sometimes touted as alternatives, however they are, mathematically, an interpretation of the Bayesian "most probable model" approach, which itself is an approxima­ tion to Bayesian decision theory [Wallace and Freeman, 1987; Buntine, 1990c]. Experiments support this approx­ imation view, and also indicate the minimum encoding approximation can degrade significantly as the sample size decreases. This happens because the encoding meth­ ods do not consider multiple models, as suggested here.

In Bayesian theory, priors are viewed as assumptions that are essential when making inference from limited information such as a small training sample. Uniform convergence theory constrains samples so they are large enough to make the effect of the prior assumptions neg­ ligible [Buntine, 1990c, Lemma 4.2.1]. According to Bayesian theory, methods applied to smaller samples have implicitly built in particular assumptions which correspond to a choice of prior. Breiman et al. 's cost complexity pruning with cross validation and the 0SE rule, for instance, favors smaller trees. And the various minimum encoding approaches [R.issanen, 1989; Quinlan and Rivest, 1989] have a very strong preference towards smaller trees. Bayesian methods differ in that they make these unavoidable prior assumptions explicit, allowing them to be specified by the user, or providing fairly objective assumptions as a fall-back.

5 Learning Bayesian Networks

To illustrate the algorithm strategy again, I will outline the development of an algorithm for learning Bayesian networks. This yields a one-step lookahead heuristic search algorithm, with smoothing on the final structure. The algorithm is analogous to the tree algorithms just presented. A similar method has been independently de­ veloped and implemented by Herskovits and Cooper and they report good experimental results [Cooper and Her­ skovits, 1991]. The different approach of Geiger et al. is concerned with learning networks from known dependency information [Geiger et al., 1990] (for instance, as extracted from a large sample) so is not relevant to the problem of learning from a smaller sample when depen­ dency information is uncertain.

Bayesian networks in their simplest formulation spec­ ify dependence properties between variables by using a directed acyclic graph. They describe probabilistic mod­ els useful for non-directed classification. Figure 1 shows

a simple Bayesian network. The set of variables that have outgoing arcs to a variable are called the parents of the variable. These parents specify the network struc­ ture. Each variable also has an associated conditional probability table which gives probabilities for different values of the variable given values of its parent variables. For instance for the graph in the figure, we need values for Pr(eia), Pr(dia, b), Pr(gie, d), etc. The parent struc­ ture and the conditional probabilities specify the model, as given by the likelihood function in Table 2. For ease of presentation, the learning algorithm presented here as­ sumes variables are binary; this can be easily extended to multivalued or to real-valued variables.

The following notation is used. A Bayesian network consists of a set of binary discrete variables X where each variable :z: E X has a set of parent variables n~. Assume variables take the values 1 or 2. For instance, for the graph in the figure, lle = {a}, lld = {a, b}, etc. The set of values for the cartesian product of variables in n~ is v(IT~). The number of examples in the fraining sample Sample with :z: = i and n~ = j is n~=ili, assuming every example in Sample has variable values fully specified. The conditional probabilities for variables are given by the probabilities() as specified in the likelihood function in Table 2.

The learning algorithm is developed analogously to the tree learning algorithm. The corresponding results of the Bayesian analysis are given in Table 2. The net­ work model has a structural component n, the parent function, and a continuous component 8, the conditional probabilities. The prior on the continuous component is similar to the tree prior. A form for Pr(IT) is not given in the table; it could be chosen to be uniform, or take some other simple form. A one-step lookahead heuristic search procedure for growing a high posterior structure can be developed analogous to the tree case. Start with the trivial structure where no variables have parents, and repeatedly add a new parent to maximize the posterior at each stage. Notice the adding of parents also has to be constrained so that the resultant graph has no cycles. A suitable heuristic measure for lookahead is given in the table. This gives the increase in posterior due to making y a parent of :z:. Notice the lookahead values calculated for a variable :z: remain unchanged if a new parent has just been added to another variable :z:'. This means at each cycle when choosing the next best parent to add, little recalculation needs to be done.

Acknowledgements

Thanks to Ross Quinlan especially, also Padhraic Smyth, Peter Cheesen'um and Robin Hanson. University of Strathclyde and Turing Institute provided some support.