Flexibly Exploiting Prior Knowledge in Empirical Learning

1 Introduction

When human expertise is nonexistent or very weak rela­ tive to a particular domain/task, and when data is plen­ tiful, machine induction from data may be the only rea­ sonable approach to task automation. In contrast, when expertise is strong, then encoding the expert 's model or domain theory via traditional knowledge acquisition strategies may be the best approach. In fact , this human expertise may stem from induction over a much larger data sample than is available at the time task automa­ tion is undertaken.

In many cases, however , conditions are indeterminate as to whether sole reliance on machine induction or hu­ man expertise is most appropriate: human expertise may not be 'perfect' and/or data may not be as plentiful as desired . In cases where some data is available and human expertise is less than perfect, an advantageous strategy may be to exploit both in an appropriate way.

There is a growing body of work that combines model­ based or domain-theory knowledge with empirical learn­ ing from data. Clark and Matwin [1993] assume that

Doug Fisher

Computer Science Department Vanderbilt University Nashville, Tennessee 37235

U.S. A. dfisher@vuse.vanderbilt.edu

an analyst-specified model mediates empirical learning ­ the rules derived from a machine-induction system are accepted as long as they do not contradict the biases found in the model. Evans and Fisher [1994] employ a similar strategy - a human analyst may specify 'weak' rules (e.g., when printing-plant humidity is low, a certain kind of printing error known as banding is more likely to occur). If inductively-derived rules indicate an opposite trend, then the learning system's default strategy is to reject the rule derived through induction. In the case of both these approaches, the model or domain theory is deemed correct in its characterization of the domain task, though it may not be a very deep characterization. Inductive learning is used to flesh out rules that are con­ sistent with the model (e.g., by selecting the particular numeric thresholds that distinguish 'high' from 'moder­ ate' and 'low'), or discovering rules relevant to a part of the domain space that are not addressed by the model or weak domain theory at all.

In the approaches above , if the data contradicts the model, then the implicit assumption is that the data are noisy or unrepresentative - drawn from a very small subspace of the data. Other approaches, known as the­ ory revision methods [Ourston , 1991] [Towell et al. , 1990] may give more credence to the data. In these systems , contradictions result in a revision of the domain theory to bring it in line with the data. Drastal et al. [1989], Rendell and Seshu [1990], and Ortega [1994] suggest an alternative strategy that loosely couples empirical learn­ ing and model-based reasoning: the data is augmented by 'features' that are actually intermediate terms of the domain theory and which are deemed true of a datum by deductive application of the domain theory. Induc­ tion is then performed over this augmented data set. If domain-theory-derived features are included in rules derived inductively, then this suggests a rough consis­ tency between the model and data; model features may be viewed as somewhat better predictors than 'raw' fea­ tures because noise is mitigated. If model features are not referenced in a resultant classifier, this may speak to imperfections in the model and/or this behavior may stem from an unrepresentative data sample. In both cases model-derived features may not look as informa­ tive as 'raw' features relative to the available data.

This paper describes a strategy that augments data with domain-theory-derived 'features', but unlike previous work, we bias an adaptation of C4.5[Quinlan, 1993] to select domain-theory based features even when this conflicts somewhat with C4.5's original bias to select the most 'informative' feature as computed over the data. The intent is to guard against the possibility of unrepre­ sentative data. However, the domain-theory preference bias may be overridden if C4.5's original bias is suffi­ ciently opposed to the domain-theory preference bias. The intent here is to acknowledge that there may be some imperfections in the domain theory. Our experi­ ments vary imperfection in a model , the representative­ ness of data, and the the veracity with which model­ derived features are preferred.

2 Implementing a Flexible Domain-Theory Preference Bias

The approach described in this paper was motivated by our attempts to inductively build classifiers of faults of the Reaction Control System (RCS) of the Space Shuttle. A mixed qualitative/quantitative model for fault predic­ tion was available [Robinson, 1993], as well as simulated data representing system faults and normal behavior. For each available datum, the model was used to pre­ dict the fault. This prediction was added as a 'feature' to the datum, as were various intermediate computa­ tions made by the model for the data point. The data points augmented in this way were then given to C4.5, which constructed a classifier that predicted either a sys­ tem's fault or normal operation. If the model were 'per­ fect' then we would expect that C4.5 would build a tree that only tested the model-based final prediction. Such a tree would indicate that if a new datum were encoun­ tered (represented by readings of various pressures and temperatures and other observables), then one should simply simulate the model on this datum and use the model-based final prediction. In the case of certain im­ perfections, a decision tree that tested various 'raw' fea­ tures, as well as various model-based features might be constructed.

To our initial surprise, C4.5 consistently constructed trees that never or rarely referenced any model-based features. Rather than taking this as evidence of signifi­ cant model imperfection or that the model added little or no information above and beyond that implicit in the raw features, aN ASA analyst familiar with this applica­ tion indicated that the simulated data used for training was unrepresentative or skewed - it represented a very small subspace of the RCS description space.

This work motivated an approach that weakly biases our adaptation of C4.5 to select model-based features . In particular, for purposes of this paper we assume a propositional domain theory used for classification that is acyclic and directed from the observable propositions to a final classification. A partial description of the per­ fect domain theory for the audiology domain used in our experiments is shown in Figure 1 as a tree. The do­ main theory is a set of rules, each one consisting of a set of conditions together with the classification predicted by the rule. In Figure 1 the antecedents of a rule are listed at the leaves of the tree. Each condition is an attribute-value pair (e.g., Air= Profound). There may be several rules that predict a particular classification, as illustrated by the several possible rules leading to each classification (e.g., OTITIS- MEDIA) in Figure 1.

We characterize model features extracted from a the­ ory of this type according to their distance in the theory hierarchy to the final model prediction:

• Level 0: Model prediction feature. We generate a single model prediction feature. Its value is the final prediction made by the rule interpreter (using the rules of the given theory).
• Level 1: Intermediate concept features. One of these features is generated for each possible clas­ sification in the theory. Each intermediate concept feature corresponds to a logical OR of the rules that predict particular classifications.
• Level 2: Rule features. Features of this type are generated for each rule in the theory. A rule feature follows from the logical AND of its antecedents.
• Level 3: Raw Features. Each rule antecedent is a binary test as to whether an attribute takes a par­ ticular value on an example. Raw features , whether rule antecedents or not, are observable and are ini­ tially the exclusive means of representing data.

To bias C4.5 towards model features closer in the hi­ erarchy to the final model prediction, we order features according to their level number from the model predic­ tion feature, through intermediate concept features, to rule features, and raw features. At each step during in­ duction, our variation of C4.5 chooses a feature of small­ est level number, unless a statistically-significant better feature (in terms of C4.5's information score) of larger level number is found. Hence, C4.5 will choose the model prediction feature unless sufficient evidence is present in the data to refute this choice.

Thus, we bias our inductive algorithm toward the model prediction feature and other features closer to it (of small level number). In a situation where we have a reasonably accurate model, and the available data is unrepresentative we expect our model-biased method to work better than a default strategy of choosing the feature of highest information value according to the avail­ able data (e.g., as in the standard C4.5). Nonetheless , if the data sufficiently contradicts the model, the model­ bias can be abandoned and, should we choose, the model can be revised accordingly.

3 Using Domain-Theory Bias with Hypothesis Testing

The major difference between the original and our vari­ ation of C4.5 is the manner in which a feature is selected for each node of a decision tree. C4.5 selects the fea­ ture with the highest information value according to the information gain ratio measure. Rat?er than sele~ting the feature with the highest informatwn value outnght, our variation of C4.5 requires that this value be statis­ tically significantly higher than the information valu~ of all features preceding it in a feature preference rankmg like that described in the previous section. Put in an­ other way we select the highest feature in a preference ranking that has an information score not significa_ntly worse than any feature lower in the preference rankmg.

The above procedure is implemented by the function SelectFeature(N ode), shown in Figure 2, where Fp is the feature preference ranking 1 ; D is the set of train­ ing data associated with the current node; info(Fj , D) is the value of C4.5's information measure for feature Y when . evaluated on the set of data D ; and F1 is the li~t of the features sorted in descending order according to this measure. SelectFeature( Node) initially chooses the feature with highest information value (i.e. , first fea­ ture in F[). However this feature is not accepted unless its information value is significantly higher than all fea­ tures of higher preference, according to the Fp ranking. If so the candidate feature is selected. Otherwise, the high~r preference feature found beco'"?es t~e ~ew can~i­ date. The procedure is repeated until a sigmficant dif­ ference is found or the F1 list is exhausted.

There is also a minor difference between the classifi­ cation procedure of our system and the standard C4.5 algori thm for the situations where there is insufficient data to select a test for a particular node of the tree. As a purely data driven system, the best C4.5 can do is to predict the most common class present in the current node. Instead, since we assume our model is better than no information, we use the prediction of our prior model.

The critical component of the function SelectFea­ ture is the SignificantlyBetter(fcand, fpref, D) fun~­ tion , shown in Figure 3. This function returns true If the information value of feature f cand is estimated to be significantly higher than that of fp re f , according t.o a given level of statistical significance SigLevel. This is done by testing the null hypothesis that the difference between the information values of f cand and fpr ef is zero. If this null hypothesis can be rejected with 1- SigLevel confidence Significantly Better concludes that ! cand is significantly better than f pr ef .

1 In the current implementation the ranking is a total or­ dering: featu.res are sorted in ascending according to lev~! number. The ranking of features within a level number IS arbitrary.

If the form of the probability distribution associated with C4.5's information measure is known and its pa­ rameters can be calculated, then traditional statistical theory can be used to test significance. This could be done for the information gain measure, since Musick et al. [Musick et al. , 1993] prove that this measure is nor­ mally distributed and provide explicit formulas for the parameters ofthis distribution. However , the form of the distribution for the default measure used in C4.5, infor­ mation gain ratio, is not known. Fortunately, Bootstrap Methods [Efron and Gong, 1983], allow for estimates of significance levels of arbitrary statistics when the form and parameters of the underlying distribution are not known [Noreen, 1989] . This is the method implemented in the function Significantly Better.

In Efron's Bootstrap methods an unknown complete population P is estimated by repeated uniform subsam­ pling with replacement from an available sample D of P. From D we obtain a set of bootstrap subsamples PB = {D1 ... DNB }, where NB is a prespecified number of subsamples. Each Di (with 1 ::; i ::; N B) is very likely to contain some duplicates and be missing some observations from D , with the result that the values of info(fj , Di) for each feature Fj will likely be different on each bootstrap subsample Di. Under some additional as­ sumptions, we then proceed as if the bootstrap samples were obtained from the actual population P .

SignificantlyBetter uses two different bootstrap methods described by Noreen [1989] : the Normal Ap­ proximation Method , and the Shift Method. Figure 3 shows the computation of some quantities used in the above methods: Dif fn , the difference in information value between f cand and f pre f computed on the set of training data D; J.Lp 8 , the mean of our statistic of in­ terest (difference in the information value between f cand and /pr ef) over the the bootstrap samples; and <7p 8 , the standard deviation of our statistic of interest over the bootstrap samples.

The Normal Approximation Method operates under the assumption that the sampling distribution of the statistic of interest (difference in the information value of f can d and /pr ef) under the null hypothesis (no differ­ ence) is normally distributed with mean zero and same variance as in the bootstrap samples. This assumption is used to calculate PVN, the probability under the Nor­ mal assumption that a value of our statistic higher than or equal to Diffn could have been obtained by chance. To calculate PVN, we use <7p 8 and the probability func­ tion/tables for a standard normal distribution.

The Shift Method assumes that the sampling distribu­ tion of the statistic of interest on the complete popula­ tion P has the same shape, but different mean, than the sampling distribution over the bootstrap samples PB. To determine the corresponding PVs, the probability un­ der the Shift assumption that a value equal or higher than Diffn could have been obtained by chance, we count the number of times that the value of the statis­ tic on bootstrap samples is higher than a shift criterion (Cs = Diffn +J.Lp 8 ) , and divide that count by the number of subsamples N B. ·

We only decide that the feature fcand is significantly better than /pref if it is significantly better according to both the Normal Approximation Method and the Shift Method. Significantly Better is computationally quite expensive. However, during the selection of most fea­ tures this needs to be done very few times. If the feature with the highest initial information value is the feature of highest preference, Significantly Better never needs to be computed. When other features are initially selected, only the features with higher preference are checked. As soon as one significant difference is computed, no other significance computation is necessary. For the sake of efficiency, the case where two or more insignificant dif­ ferences could account for a single significant difference is not considered. Our interest is not in precise compu­ tations of significance, but rather , the qualitative effect of significance testing on the selection of attributes m C4.5, while retaining a reasonable level of efficiency.

4 Experimental Design

To test our approach, we conducted experiments with the audiology dataset from the UCI (University of Cal­ ifornia at Irvine) Machine Learning repository. This database contains 226 examples from 24 classes . Each example is described by 67 discrete features.

For each of the 30 learning trials of our experiments , a test set of 76 examples and a disjoint training set of 150 examples were randomly and uniformly selected. Be­ cause we want to test the robustness of various strategies in the face of unrepresentative data, we sorted the train­ ing examples according to their Euclidian distance from a randomly selected datum. The training set was fur­ ther divided into subsets which contain the first 10, 20 , 35, 55, 80, 110, and 150 (i.e., all) examples of the sorted training set. Decision trees are learned for each of these subsets of training data.

The dependent variables of interest are predictive ac­ curacy and the level (as illustrated in Figure 1) of the root feature of the decision trees learned under different conditions. Due to the recursive nature of decision tree induction, we expect that the tendencies observed at the root can be extrapolated to other nodes of the tree.

The independent variables are the size of the training set , the significance level used for hypothesis testing in our variation of C4.5, and the degree of model imper­ fection . Note that while varying the size of the training set we are also varying its degree of skewedness: be­ cause training data are ordered based on Euclidean dis­ tance, small samples tend to be drawn from a small por­ tion of the data description space; the larger the train­ ing dataset, the higher the proportion of the complete data set it covers, and thus the more representative it becomes. For the largest data set of 150 examples all skewedness disappears since all 150 examples were randomly chosen from the complete data set. We present results from skewed sampling, as this tends to repre­ sent 'worst ' case conditions for our learning system. We have also experimented wit4 traditional sampling (for all training sizes), thus allowing us to better tease apart the influence of skew and training set size, though this pa­ per does not elaborate on this issue. Significance levels of 50%, 25%, 10%, and 1% are varied to indicate increasing confidence in the quality of our models.

We follow Mooney's approach [Mooney, 1993] for gen­ erating theories of varying degrees of imperfection. A perfect theory, i.e., one that correctly classifies 100% of all audiology examples, was first constructed by running C4.5 on the complete data set of audiology examples with all pruning disabled. This theory (named fOO) con­ tained 86 rules with an average of 7.79 antecedents per rule . Imperfect theories (named f55, f1 010, f2525, and !5050) were generated by randomly adding and then ran­ domly deleting a percent of all conditions from the rules of the perfect theory (a corresponding 5%, 10%, 25%, and 50%). This results in contaminated theories wither­ rors both of omission and of commission. The accuracies over the complete data set of the imperfect theories f55, /1010, !2525, and f5050 are 89%, 65%, 46%, and 21%, respectively. For comparison, the accuracy obtained if we always predict the most frequent class in the dataset is 21%.

5 Experimental Results

Figure 4 2 shows results from a baseline study. The curve labeled sk-c45 shows the results of standard C4.5 on skewed trials with 'raw' features only. The rest of the curves in this figure show the accuracy and root fea­ ture level for C4.5 3 when model features are added to the description of the data, but no preference ordering or hypothesis testing is done. We can see that accuracy improves significantly (over sk-c45) when a domain the­ ory is exploited, even for a low quality theory such as f5050. These results compare favorably to other systems tested on this domain [Mooney, 1993] [Ourston, 1991] .

An interesting fact illustrated in Figure 4 is that the number of training examples required for C4.5 with a domain theory ( sk-fxx curves) to produce an accuracy equivalent to the corresponding theory alone seems to be inversely proportional to the quality of the theory, the two extremes being f5050 (0 training examples required to reach 21% accuracy) and fOO (all training examples required to reach 100% accuracy). Ideally, however , the accuracy of our system should be equal or better than the accuracy of the model alone, or the C4.5 learning algorithm alone. This only occurs for large enough or representative enough training data sets. This behavior is not unique to our system: it can be observed in the published learning curves shown for some systems that combine analytical and empirical learning[Pazzani and Kibler, 1992] [Ourston, 1991] . As we will see, signifi­ cance testing of ranked features appears to mitigate this undesirable behavior.

Figure 4 gives a good indication of the type of features selected with theories of varying quality. Standard C4.5 can only access raw features (level 3). C4.5 with features from a perfect model (i.e, fOO) chooses almost exclusively (but not always) the model prediction feature (level 0). With lower quality theories , C4.5 gradually chooses fea­ tures of greater level numbers . However, for the perfect model , there should be no reason to choose any feature other than the model prediction feature . This does not happen due in part to a known bias of the information gain ratio against features with many values (In the au­ diology domain the model prediction feature has 24 pos­ sible values, other model features are binary, and raw features have few values). However, as we will see next, this problematic bias can be mitigated with the use of significance testing.

Figure 5 shows the effects of significance testing of ranked features when C4.5 is augmented with features from a perfect model. Rather than the 150 examples needed before, hypothesis testing of ranked features re­ sults in 100% accuracy with only 80 examples when using a 50% significance level, or with just 35 examples when using more strict significance levels (25%, 10%, or 1%) . This figure also shows how the average root feature level is gradually reduced with stricter significance levels.

2 Tables corresponding to the graphs in this paper, con­ taining means and standard deviations , can be found at http://www. vuse. vanderbilt .edu/Ndfisher /techreports /ijcai95-tables . ps

3 Here we use ftandard C4.5 for learning. For testing we use the classification procedure described in section 2, i.e., predicting with the model rather than the most frequent class at leaves of the decision tree where there is insufficient data for further decomposition.

Perfect domain theories are an interesting boundary case, but most interesting theories are imperfect. The graphs of Figure 6 illustrate how stricter levels of sig­ nificance achieve our objective of biasing C4.5 toward features of smaller level number using the f1 010 domain theory. This figure also shows that the accuracy ob­ tained with the f1 010 imperfect theory improves consis­ tently with stricter levels of significance testing (50%, 40%, 10%) for any size of the training set, including the complete training set of 150 examples. In addition, while with no significance testing (or the almost equiv­ alent significance testing at the 50% level) at least 55 examples are needed to obtain better accuracies than the f1 010 theory alone, with stricter levels of significance testing only 20 examples are required. For the 1% sig­ nificance level, accuracy is better than other significance levels when the training sets contains less than 110 ex­ amples, and worse when the training set contains more than 110 examples. Thus, at least in this domain, there is a breakeven point for significance levels that depends both on the quality of the model and the size of the training set, after which stricter significance levels are detrimental. In our experiments, the size of the train­ ing sets corresponds to increasing quality in the available data in the sense that they are better representatives of the complete population, both due to the sheer amount of data and due to the fact that the skewedness effect we introduced in the training set tends to diminish as the size of the trainings sets are increased.

Figure 6: Average accuracy and root feature level of deci­ sion trees learned with features from the f1 010 imperfect model under varying levels of significance

For lower quality theories , similar behavior is ob­ served: with increasingly strict significance levels, accu­ racy improves when the training set contains few exam­ ples, and decreases with training sets that contain many examples. Thus, for every combination of model quality (i.e., amount of contamination in the model) and data quality (level of skewedness and number of training ex­ amples) there is an optimal level of significance between the extremes of 50% and 0% in this domain. However, the choice of a beneficial but perhaps non-optimal sig­ nificance level is not difficult . Significance levels only seem to become detrimental for large data sets when we use significance levels stricter than 10%. Values between

50% and 10% always seem to improve accuracy (perhaps non-optimally) for any size of the training set. Thus, ex­ pert intuition about the trustworthiness of an existing model with respect to the available can be incorporated into our learning algorithm to obtain additional perfor­ mance improvements.

6 Concluding Remarks

In this paper we address a situation that we believe to be of practical interest: learning whenever we have a model believed to be of good quality, but imperfect nev­ ertheless, together with a set of data of unknown rep­ resentativeness and quality. We present a method that attempts to take advantage of both the model and the data, plus our prior knowledge about the quality of the model. Our method biases empirical learning in a flex­ ible manner, such that model-based features, or more generally preferred features based on some a priori deter­ mined preference ordering, are selected unless sufficient refuting evidence appears in the data. The amount of ev­ idence required is determined by statistical significance, and is set by the user according to his/her confidence in the quality of the available model.

Our experimental results show that when features gen­ erated from a model are simply added to the description of the data, accuracy is increased to a degree propor­ tional to the quality of the model. However, some prob­ lems with this simple approach are illustrated by the fact that perfect models only result in perfect accuracy with large or very representative sets of training exam­ ples. If significance testing with a preference ordering is used with a perfect model our system becomes more robust in the presence of skewed data: few examples are then needed to obtain perfect accuracy. Further, with imperfect models of good quality we obtain additional increases in accuracy for any number of training exam­ ples.

Although significance testing has been used previously in machine learning methods, such as for the pruning of decision trees [Quinlan, 1986], our use of this concept for flexibly introducing prior knowledge bias in empirical learning seems to be novel.

Acknowledgements

This research was supported by a grant from NASA Ames Research Center (NAG 2-834) to Doug Fisher. We thank Deepak Kulkarni and Peter Robinson for early dis­ cussion on initial strategies that led to those described here.