An Experiential Approach to Integrating ANOVA Concepts

This paper presents a data set based on an industrial case study using design of experiments. The data set is pedagogically rich because it has a rather large total sample size from an industrial setting that naturally yields a large third order interaction term. The experiment is a 23 design and is initially presented with no replications. The sample size of the data is then doubled and the analysis repeated, comparing these results with previous results. The process is repeated until eight replications are available for each combination of factors and all parameters are estimated. With eight replications, the analysis shows all main effects and all interactions are statistically significant at the α = 0.05 level. With smaller sample sizes, various main effects and interactions are not found to be statistically significant. Through this presentation the instructor can lead students in discussions about the effect of increased sample sizes, power, statistical significance (or insignificance), interaction terms, Type I and Type II errors as well as the importance and the role of the error term. In addition, students can manipulate the data set in a computer laboratory setting to illustrate many of the concepts inherent in the design of experiments and analysis of variance.

Introduction
Concepts such as power, Type I and Type II errors, model assumptions, statistical significance, statistical non-significance, estimates of the model variance, and the impact these concepts have on interpretation of the data are crucial features for analysis of variance and design of experiments. All too frequently, these concepts are presented in a disjointed fashion without showing their interrelationships.
The authors have found that an "in class discussion" of a data set (based on an industrial case study) which is repetitively presented with progressively larger samples has been a very helpful tool to integrate and synthesize many of these concepts. This discussion occurs after the fundamental concepts, calculations and a few simple examples have been presented to the class. The case is used in an intermediate course in applied statistics with an audience of senior business majors, MBA students and various graduate-level science majors. When it has been used, the reception of the class has been enthusiastic and, although student feedback has been informal, several students have encouraged the authors to continue using such an exercise.

The Industrial Case Setting
A company engaged in the manufacture of large industrial fans recently acquired a smaller competitor that was also engaged in manufacturing fans. However the two companies had very different manufacturing methods and each company championed its method as superior to the other. The merging of the two companies presented an important opportunity to choose "best practices," standardize operations, and reduce inventories. Since many factors were potentially involved and the decision to standardize on a particular process had substantial long run manufacturing and financial ramifications, the authors were contacted to assist in the design and analysis of the experiments.
After much discussion, the company engineers agreed to look at three important factors in the manufacture of the fans: the type of hole in the fan "spyder" (that is, blades), the type of barrel onto which the spyder was placed, and the type of assembly method for these two components. Each of these factors was qualitative in nature and at two levels. Thus the experiments became a straightforward 2 3 design that is presented in most design of experiments texts (Cochran and Cox 1957;Box, Hunter, and Hunter 1978;Hicks 1993). Because of industrial and competitive considerations, company representatives have requested that the precise nature of these factor levels not be presented. The two levels of each factor are simply coded -1 and 1. However, Figure 1 "suggests" the type and nature of the factors.
The single most important metric in measuring the quality of a manufactured fan was the torque (in footpounds) at which the spyder could be broken from the barrel. When the fan blade broke free of the hub, the shaft of the turning motor would rotate but the blades would not. Such a failure had serious ramifications for the large industrial units being manufactured.

The Discussion
The key technique used in this discussion is the use of one data set that is revisited a total of four times (about all that a single class period will allow). Each time the experiment is revisited the sample size is doubled so that the same experiment is done with 8, then 16, then 32, and finally 64 data points. A powerful approach to teaching this material is to allow students to work through the analysis in a computer laboratory, using prepared diskettes containing the datasets. Students can also get the data from the Internet. If the hands-on approach is not practical, the authors recommend that tables containing the data and the analysis be used as a class handout to focus each student's attention on interpretation and synthesis of concepts and to deemphasize the hand calculations necessary to achieve those results.
The first experiment is comprised of one observation for each combination of hole type, assembly method, and barrel design. Table 1 shows the MINITAB® results for ANOVA and the parameter estimates for a sample size of eight. Using the printed cell sample means and the standard set of equations, the class can compute the estimates of each of the model terms that are shown in the table. The three-factor interaction term is used to provide an estimate of the error term with one degree of freedom, a course of action sometimes recommended by statisticians (Montgomery 2001). Using the calculated values for F or the p-values, students will find that only the surface of the barrel is statistically significant at the 0.05 significance level. The instructor might note that when MINITAB® reports pvalues of 0.000 they are not truly "zero" p-values but rather statements that the actual p-values are less than 0.0005.
The instructor can lead discussion concerning the use of the three-way interaction term as a surrogate for the error term. The analyst is, in fact, assuming that the three-way interaction term is not significant. If the assumption is incorrect and the interaction term is large, main effects of substantial size may be "hidden." Since the fans were destroyed in the testing process, the engineers may have been tempted to test a small number of fans. Had they stopped at eight and used the analysis in Table 1, they may have concluded that only the shape of the barrel had a significant effect on the strength of the fan. They could have concluded that neither the shape of the hole in the spyder nor the assembly method was important. Therefore, inventory and equipment using both types of hole and both types of assembly method could have been routinely used to produce fans. The analysis shows that the average breaking torque of the fans using the best barrel shape was 176.25 foot-pounds. This is a good time for the instructor to review Type I and Type II errors. The hypothesis being evaluated is that the treatment effects are equal to zero. If a conclusion is made that an effect is significant when it is not, the analyst has committed a Type I error. The probability of a Type I error, , can be controlled by setting a value of = 0.05, for instance, in conducting the hypothesis test. The pvalues, in the table above, give the probability of obtaining more extreme test results by chance if the null hypothesis was true. A Type II error is committed when the analyst concludes that the treatment effects are zero when an effect actually does exist. Students should understand that the probability of committing a Type II error is , while the probability of identifying a significant effect when there actually is one is 1-(the power of the test). For a given level of , the power to detect real differences depends on the size of the sample taken and the magnitude of the difference that must be detected. At this point the instructor should emphasize that factors and terms displaying p-values larger than 0.05 and judged not statistically significant could actually have a significant effect in producing stronger fans. The sample size may simply not be large enough to detect their actual (non-zero) effect.
The last column in the ANOVA portion of Table 1 gives an approximation of the observed power for the hypothesis test, assuming = 0.05. (SPSS® provides these estimates as optional output.) With the exception of the variable for barrel shape, all power estimates are quite low. For instance, if the observed effect size for the first variable, hole, is a true difference, the null hypothesis would be rejected only 26.6% of the time in repeated experiments of this design. If the power is small, the analyst cannot be confident in a decision not to reject the null hypothesis.
The instructor should next challenge the students to predict what might happen if the sample size is doubled to 16 observations, two at each of the factor combinations. Table 2 gives the results of the MINITAB® analysis for a sample size of 16. Students should note that replicating the experiment allows an estimate of an error term with eight degrees of freedom. The mean squared error is now smaller than in the previous experiment. Doubling the sample size results in an ANOVA showing all main effects to be significant. In addition, the Hole*Assembly interaction is significant at the 0.05 level and so is the three-factor interaction. It is helpful to recalculate the estimates of the model parameters from the larger sample and note that these values are close to but not identical to those calculated from the original sample of eight. Prior to experimentation, the company engineers debated how much of a difference in treatment effects would be of material or practical difference. For instance, a person's fingers can easily exert +/-1.5 footpounds of torque in placing a nut on a bolt. The engineers finally decided that they wanted to detect differences of 10 foot-pounds or more. Each of the main effects in this experiment is estimated at greater than 10 foot-pounds.
The instructor should point out the new estimates for observed power in Table 2 and how they differ from those in Table 1. The Hole*Barrel and Assembly*Barrel interactions are not significant at the = 0.05 level. However, the observed estimates of power for the tests are 0.437 and 0.204, respectively. Since the power is low, the analyst should be wary of a decision not to reject the hypothesis. The instructor should point out, however, that the estimates of effects for all the interaction terms are less than the 10 foot-pounds of force that the engineers wanted to detect. Even if true differences of the magnitudes observed in the interaction effects are detected, they may not be large enough to be considered material differences in the context of the problem. Depending upon the level of class being taught, the instructor might want to point out the availability of tables to determine the appropriate Estimates of the Model Parameters µ = 117.5 A -1 = -11.3 A 1 = 11.3 B -1 = 13.9 B 1 = -13.9 C -1 = -54.3 C 1 = 54.3 AB -1-1 = -7.4 AB -11 = 7.4 AB 1-1 = 7.4 AB 11 = -7.4 AC -1-1 = -3.0 AC -11 = 3.0 AC 1-1 = 3.0 AC 11 = -3.0 BC -1-1 = 1.9 BC -11 = -1.9 BC 1-1 = -1.9 BC 11 = 1.9 ABC -1-1-1 = -4. sample size for analysis of variance given specified levels of , , and the minimum acceptable size of the treatment effect (Nelson 1985). Formulas for calculating power are available for those instructors wishing to include a more rigorous treatment of power (Desu and Raghavarao 1990).

Analysis of Variance
The instructor should again call the students' attention to the estimated means for the various treatment combinations. With the original sample size of eight, only the barrel shape was significant. If the other factors are ignored and the engineers concentrate only on the best setting for barrel shape, the average breaking torque is estimated to be 176.25. The larger sample size of 64 helps identify significant differences for all factors. If the engineers choose the best settings for all factors, the average breaking torque is estimated at 196.25. Although destructive testing was necessary, the larger sample size helped identify a combination of factor settings that substantially improved the strength of the industrial fans. Figures 2 and 3 show plots of the sample means for the eight different factor combinations.  Looking back to the beginning of the exercise when only eight fans were tested, the third-order interaction was used as a surrogate for error in the analysis since the experiment was unreplicated. Because the sum of squares for that interaction was large and there was only one degree of freedom, only one main effect (barrel shape) was significant. In fact, using the large interaction term as error hid the impact that the hole shape and assembly method had in producing a stronger fan. A better practice may have been to combine the interactions terms to serve as error and only screen for main effects in the model as seen in Table 5. All main effects are significant at the = 0.05 level, which is consistent with the findings of the n = 64 experiment. patterns. Although the associated p-values do change moderately, it is rare to have a dramatic difference, and the essential results remain the same. However, the instructor may wish the students to explain the cause of any differences that do occur in their analysis as part of the homework assignment.

Some Other Issues for Discussion
The instructor may also choose to remind the students that assumptions should be checked when using ANOVA techniques. In this case, a Kolmogorov-Smirnov test of normality on the error terms failed to find a significant non-normality. Tests for homogeneity of variances were mixed. Bartlett's Test resulted in a p-value of 0.116, indicating no significant heterogeneity of variances. However, Levene's Test resulted in a p-value of 0.000, indicating that the variances are not the same at all factor levels.
Discussions of these two tests can be found in Montgomery (2001). Box (1954) discusses the robustness of ANOVA to departures from the homogeneity of variances assumption if the sample sizes are equal at all factor levels. In this case, the smallest standard deviation of breaking torques for a factor level is 3.01, while the largest is 8.78. The standard deviations can differ by as much as a factor of three without invalidating the results of the ANOVA analysis.
The instructor could also lead a discussion about other issues, for which information is not available, that may impact the decision. Students might suggest that costs of the various methods be collected and compared. They might suggest that an engineer review the recommended design. Students might ask if breaking torque is the appropriate measure to use and, if so, what value of breaking torque do the customers require. They might explore the existence of other measures of quality that might be appropriate. They should also look at the standard deviation of each of the combinations to determine if the combination of factors that gave the highest breaking strength also resulted in a relatively small standard deviation. A complete discussion of each of these issues will lead to discussion of many more topics in the quality literature and substantially increase the amount of time necessary to complete the exercise. The instructor may wish to assign these topics to small groups of students for further discussion or for short papers.

Summary and Conclusions
The repeated analysis of data based on an industrial case study by successively increasing the total sample size has been found to be a useful tool by the authors in summarizing and unifying many analysis of variance concepts. Concepts such as power, statistical significance, statistical nonsignificance, material differences, Type I and Type II errors, and the effects of sample size are clarified and illustrated progressively.

Getting The Data
The file fadata.dat.txt contains the raw data. The file fandata.txt is a documentation file containing a brief description of the dataset.
Data columns 4, 8, 12, and 16 are the breaking torques in foot-pounds for the various factor combinations Data columns 1 -4 give the results of the experiment with one observation for each factor combination Data columns 5 -8 give the results of the experiment with two replications for each factor combination Data columns 9 -12 give the results for the experiment with four replications for each factor combination Data columns 13 -16 give the results for the experiment with eight replications for each factor combination


Types of Cost in Inductive Concept Learning

Inductive concept learning is the task of learning to assign cases to a discrete set of classes. In real-world applications of concept learning, there are many different types of cost involved. The majority of the machine learning literature ignores all types of cost (unless accuracy is interpreted as a type of cost measure). A few papers have investigated the cost of misclassification errors. Very few papers have examined the many other types of cost. In this paper, we attempt to create a taxonomy of the different types of cost that are involved in inductive concept learning. This taxonomy may help to organize the literature on cost-sensitive learning. We hope that it will inspire researchers to investigate all types of cost in inductive concept learning in more depth.

Introduction
This paper is an attempt to list the different costs that may be involved in inductive concept learning. The paper assumes the standard inductive concept learning scenario. We have a set of cases (i.e., examples, vectors, observations) represented as vectors in an abstract space of features (i.e., tests, measurements, sensor values, attribute values). Each case belongs to a class (i.e., the feature space is partitioned into a finite set of distinct subsets; there is a function mapping from feature space into a finite set of symbols). The learning algorithm generates hypotheses that may be used to predict the class of new cases.
In the following, "cost" should be interpreted in its most abstract sense. Cost may be measured in many different units, such as monetary units (dollars), temporal units (seconds), or abstract units of utility (utils). In medical diagnosis, cost may include such things as the quality of life of the patient, in so far as such things can be (approximately) measured. In image recognition, cost might be measured in terms of the CPU time required for certain computations. We take "benefit" to be equivalent to negative cost.
Often we are uncertain about costs. We can represent this uncertainty with a probability distribution over a range of possible costs. This applies to all of the following costs. In this paper, for ease of exposition, we will assume that we are certain about costs.

Cost of Misclassification Errors
Suppose there are C classes. In general, we may have a C x C matrix, where the element in row i and column j specifies the cost of assigning a case to class i, when it actually belongs in class j. Typically (but not necessarily) the cost is zero when i equals j. In a minor variation on this approach, we may have a rectangular matrix, where there is an extra row for the cost of assigning a case to the unknown (or "too-difficult-for-this-learner") class.

Constant Error Cost
The cost of a certain type of error (the value of a cell in the cost matrix) may be a constant (the same value for all cases). This is the most commonly investigated type of cost; for example, see Breiman et al. (1984) or Hermans et al. (1974).
If the cost is zero if i equals j and one otherwise, then our cost measure is the familiar error-rate measure. If the cost is one if i equals j and zero otherwise, then our cost measure (in this case, our "benefit measure") is the familiar accuracy measure.

Conditional Error Cost
The cost of a certain type of error may be conditional on the circumstances.

ERROR COST CONDITIONAL ON INDIVIDUAL CASE
The cost of a classification error may depend on the nature of the particular case. For example, in detection of fraud, the cost of missing a particular case of fraud will depend on the amount of money involved in that particular case (Fawcett andProvost, 1996, 1997). Similarly, the cost of a certain kind of mistaken medical diagnosis may be conditional on the particular patient who is misdiagnosed. For example, the misdiagnosis may be more costly in elderly patients.
It may be possible to represent this situation with a constant error cost by distinguishing sub-classes. For example, instead of two classes, "sick" and "healthy", there could be three classes, "sick-and-young", "sick-andelderly", and "healthy". This is an imperfect solution when the cost varies continuously, rather than discretely.
2.2.2 ERROR COST CONDITIONAL ON TIME OF CLASSIFICATION In a time-series application, the cost of a classification error may depend on the timing. Consider a classifier that monitors sensors that measure a complex system, such as a manufacturing process or a medical device. Suppose that the classifier is intended to signal an alarm if a problem has occurred or will soon occur. The sensor readings must be classified as either "alarm" or "noalarm". The cost of the classification depends on whether the classification is correct and also on the timeliness of the classification. The alarm is not useful unless there is sufficient time for an adequate response to the alarm (Fawcett and Provost, 1996. Again, it may be possible to represent this situation with a constant error cost by distinguishing sub-classes. Instead of two classes, "alarm" and "no-alarm", there could be "alarm-with-lots-of-time", "alarm-with-a-little-time", "alarm-with-no-time", and "no-alarm". Again, this is an imperfect solution when the cost varies continuously as a function of the timeliness of the alarm.

ERROR COST CONDITIONAL ON CLASSIFICATION OF
OTHER CASES In some applications, the cost of making a classification error with one case may depend on whether errors have been made with other cases. The familiar precision and recall measures, widely used in the information retrieval literature, may be seen as cost measures of this type (van Rijsbergen, 1979). For example, consider an information retrieval task, where we are searching for a document on a certain topic. Suppose that we would be happy if we could find even one document on this topic. If we are given a collection of documents to classify as "relevant" or "not-relevant" for the given topic, then the cost of mistakenly assigning a relevant document to the notrelevant class depends on whether there are any other relevant documents that we have correctly classified.
As another example, in activity monitoring, if you issue an alarm twice in succession for the same problem, the benefit of the second alarm is less than the benefit of the first alarm, assuming both alarms are correct classifications (Fawcett and Provost, 1999). This is related to Section 2.2.2.

ERROR COST CONDITIONAL ON FEATURE VALUE
The cost of making a classification error with a particular case may depend on the value of one or more features of the case.

Cost of Tests
Each test (i.e., attribute, measurement, feature) may have an associated cost. For example, in medical diagnosis, a blood test has a cost. Turney (1995a) points out that we can only rationally determine whether it is worthwhile to pay the cost of a test when we know the cost of misclassification errors. If the cost of misclassification errors is much greater than the cost of tests, then it is rational to purchase all tests that seem to have some predictive value. If the cost of misclassification errors is much less than the cost of tests, then it is not rational to purchase any tests.

Constant Test Cost
The cost of performing a certain test may be a constant. Each test has a different cost, but the cost of a given test is the same for all cases (Núñez, 1988(Núñez, , 1991Tan, 1991aTan, , 1991bTan, , 1993.

Conditional Test Cost
The cost of performing a certain test may be conditional on the circumstances surrounding the test.

TEST COST CONDITIONAL ON PRIOR TEST
SELECTION The cost of performing a certain test on a given patient may be conditional on the previous tests that have been chosen for the patient. For example, a group of blood tests ordered together may be cheaper than the sum of the costs of each test considered by itself, since the tests share common costs, such as the cost of collecting blood from the patient (Turney, 1995a).

TEST COST CONDITIONAL ON PRIOR TEST RESULTS
The cost of performing a certain test on a patient may be conditional on the results of previous tests. For example, the cost of a blood test is conditional on the patient's age. Thus a blood test must be preceded by a "patient-age" test, which determines the cost of the blood test.

TEST COST CONDITIONAL ON TRUE CLASS OF CASE
The cost of performing a certain test on a patient may be conditional on the correct diagnosis of the patient. For example, the cost of an exercise stress test on a patient may be conditional on whether the patient has heart disease. The stress test could cause heart failure, which adds to the total cost of the test.

TEST COST CONDITIONAL ON TEST SIDE-EFFECTS
The cost of performing a certain test on a patient may be conditional on possible side-effects of the test. For example, some patients are allergic to the dies that are used in certain radiological procedures. One side-effect of such a radiological test is an allergic reaction, which may increase the cost of the test.

TEST COST CONDITIONAL ON INDIVIDUAL CASE
The cost of performing a certain test may depend on idiosyncratic properties of the individual case.

TEST COST CONDITIONAL ON TIME OF TEST
The cost of performing a certain test may depend on the timing of the test.

Cost of Teacher
Suppose we have a practically unlimited supply of unclassified examples (i.e., cases, feature vectors), but it is expensive to determine the correct class of an example. For example, every human is a potential case for medical diagnosis, but we require a physician to determine the correct diagnosis for each person. A learning algorithm could seek to reduce the cost of teaching by actively selecting cases for the teacher. A wise learner would classify the easy cases by itself and reserve the difficult cases for its teacher.
If a learner has no choice in the cases that it must classify, then it can only rationally determine whether it should pay the cost of a teacher when it knows the cost of misclassification errors. A rational learner would, for each new case, calculate the expected cost of classifying the case by itself versus the cost of asking a teacher to classify the case. This scenario can be handled by using a rectangular cost matrix, as we discussed in Section 2.
In a more interesting scenario, the learner can explore a (possibly infinite) set of unclassified (unlabelled) examples and select examples to ask the teacher to classify. This kind of learning problem is known as active learning. In this scenario, we can rationally seek to minimize the cost of the teacher even when we do not know the cost of misclassification errors, if we assume that asking the teacher costs more than a correct classification (otherwise you would always ask the teacher) but less than an incorrect classification (otherwise you would never ask the teacher). However, we may be able to make better decisions if we have more information about the cost of misclassification errors.

Constant Teacher Cost
In the simplest situation, the cost of asking a teacher to classify a case is assumed to be the same for all cases. This is the usual assumption in the active learning literature (Cohn et al., 1995(Cohn et al., , 1996Krogh and Vedelsby, 1995;Hasenjager and Ritter, 1998).

Conditional Teacher Cost
In a more complex situation, the cost of asking a teacher to classify a case may vary with the circumstances of the case. For example, the cost may increase with the complexity of the case. On the other hand, the teacher may choose to penalize the student for asking the class of a trivial case.

Cost of Intervention
Suppose we have data from a manufacturing process. Each feature might be a measurement of an aspect of the process, while the classes might be different types of products. A learning algorithm could induce rules that predict the type of product, given the corresponding features. Suppose we wish to intervene in the manufacturing process, to make more of one type of product. We could give the induced rules a causal interpretation.
For example, assume that we have a continuous process, such as petroleum distillation. Suppose a rule says, "If sensor A has a value greater than B, then the yield of product type C will increase." If this rule has causal significance, then we may be able to increase the amount of product type C by intervening in the process so that sensor A consistently has a value greater than B. There may be a cost associated with this intervention. Each feature may have a corresponding cost, where the cost represents the effort required to intervene in the manufacturing process at the particular point represented by the feature (Verdenius, 1991). This is somewhat different from the idea of assigning a cost to a feature based on the effort required to measure the feature. Instead, the cost represents the effort required to manipulate the process in order to alter the feature's value.

Constant Intervention Cost
In the simplest scenario, the cost of intervention for a given feature is the same for all cases (Verdenius, 1991).

Conditional Intervention Cost
In a more complex scenario, the cost of intervention for a feature may depend on the particular case (for a continuous process, "observation" may be a more appropriate term than "case"). For example, if a sensor is observed to be near its average value, it may be relatively easy to manipulate the process in order to move the average up or down slightly. However, if the sensor is observed to be far from its average value, it may be quite difficult to move it even further from its average value (van Someren et al., 1997).

Cost of Unwanted Achievements
When we are dealing with the scenario described in Section 5, where induced rules are used to intervene in a causal process, the nature of misclassification error cost changes. Suppose a rule says, "If sensor A has a value greater than B, then the yield of product type C will increase." If we are using this rule to make predictions, then there is a misclassification error cost associated with incorrect predictions. If we are using this rule to intervene in a manufacturing process, then there is a similar cost associated with "unwanted achievements" (van Someren et al., 1997).
Suppose that the rule makes successful predictions for 90% of the cases for which the antecedent of the condition ("sensor A has a value greater than B") is satisfied. If we can give the rule a causal interpretation, then we may expect that, if we manipulate the process so that sensor A is always greater than B, then the yield of product type C will increase 90% of the time. The remaining 10%, where our manipulation fails to increase the yield of product type C, are a cost of using this rule. These 10% are "unwanted achievements" of the rule (van Someren et al., 1997). (The terminology "unwanted achievements" seems somewhat odd, but this is the terminology used in van Someren et al., 1997, and we are reluctant to confuse the issue by introducing new terminology.)

Constant Unwanted Achievement Cost
If the cost of unwanted achievements is constant, then we can use a cost matrix, as with the cost of misclassification errors (Section 2).

Conditional Unwanted Achievement Cost
The cost of unwanted achievements may vary with factors such as the market demand for the unwanted achievement, the cost of disposing of the unwanted achievement, the cost of repairing or refining the unwanted achievement, or the quantity of the unwanted achievement.

Cost of Computation
Computers are a limited resource, so it is meaningful to consider the cost of computation. The various types of computational complexity are essentially different forms of cost that we may wish to take into account.
We may distinguish the cost of computation by whether it is static or dynamic, or by whether it is incurred during training or during testing.

Static Complexity
A computer program, considered as a static object, has a measurable complexity.

SIZE COMPLEXITY
The size complexity of a computer program may be measured in several ways, such as the number of lines of code, or the number of bytes. Since the code takes up memory space in the computer, there is clearly a corresponding cost. Turney (1995b) shows how it is possible, under certain circumstances, to treat size complexity as a kind of test cost (Section 3). In this case, each feature that is to be measured corresponds to a block of code that computes the feature.
The cost of measuring a feature is proportional to the size of the corresponding block of code. The goal is to minimize the total size of the code, which is approximately the same as minimizing the total cost of the features. (It is only approximate, because blocks of code can combine in non-additive ways.) 7.1.2 STRUCTURAL COMPLEXITY The structural complexity of a computer program might be measured by the number of loops in the program, the depth of nesting of the loops, or the number of recursive function calls. Structural complexity has a cost; for example, software with high structural complexity is more difficult for software engineers to maintain.

Dynamic Complexity
The dynamic complexity of a program is the execution time or memory space consumed by the program. Unlike static complexity, dynamic complexity is a function of the input to the program. 7.2.1 TIME COMPLEXITY Time complexity may be measured in many different ways. Even with a specific architecture, there are many possible choices. For example, the time complexity of a Turing machine might be measured by the number of movements of the read/write head, by the number of direction changes of the read/write head, or by the number of state transitions of the finite state machine.
For example, a learning algorithm that discovers new features may take into account the time complexity of calculating the new features (Fawcett, 1993). In this example, time complexity is a kind of test cost (Section 3).

SPACE COMPLEXITY
The space complexity of a program is the amount of memory it requires for execution with a given input. Clearly memory has a cost. There are well-known (in the theory of computational complexity) trade-offs between time complexity and space complexity.

Training Complexity
The cost of computational complexity may be incurred during training, when the algorithm is learning to classify.

Testing Complexity
The cost of computational complexity may be incurred during testing, when the algorithm is making predictions.
Case-based reasoning, for example, typically has a low dynamic complexity during training, but a high dynamic complexity during testing. On the other hand, neural networks typically have a high dynamic complexity during training, but a low dynamic complexity during testing.

Cost of Cases
There is often a cost associated with acquiring cases (i.e., examples, feature vectors). Typically a machine learning researcher is given a small set of cases, and acquiring further cases is either very expensive or practically impossible. This is why many papers are concerned with the "learning curve" (performance as a function of the sample size) of a machine learning algorithm.

Cost of Cases for a Batch Learner
Suppose that we plan to use a batch learning algorithm to build a model that will be embedded in a certain software system. The model will be built once, using a set of training data. The software system will perform some task, using the embedded model, a certain number of times over the operational lifetime of the system. For a given learning algorithm, if we can estimate (1) the learning curve (the relation between training set size and misclassification error rate), (2) the expected number of classifications that the learned model will make when embedded in the operational system, over the lifetime of the system, (3) the cost of misclassification errors, and (4) the cost of acquiring cases for training data, then we can calculate the combined cost of training (building the model) and operating (using the model) as a function of training set size. We can then optimize the size of the training set to minimize this combined cost .
Alternatively, an adaptive learning system, given (1) the expected number of classifications that the learned model will make when embedded in the operational system, (2) the cost of misclassification errors, and (3) the cost of acquiring cases for training data, could adjust its learning curve (fast but naïve versus slow but sophisticated) and training set size to optimize the combined cost of training and operating.

Cost of Cases for an Incremental Learner
Suppose that we plan to use an incremental learning algorithm to build a model that will be embedded in a certain software system. Unlike the batch learning scenario, the model will be continuously refined over the operational lifetime of the system. However, it is likely that the software system cannot be operationally deployed without any training. We must decide how many training cases we should give to the incremental learner before it becomes sufficiently reliable to deploy the software system. To make this decision rationally, we need to assign a cost to acquiring cases for training data. The situation is similar to the batch learning situation, except that we suppose that the misclassification error rate will continue to decrease after the software system is deployed.

Human-Computer Interaction Cost
There is a human cost to using inductive learning software. This cost includes finding the right features for describing the cases, finding the right parameters for optimizing the performance of the learning algorithm, converting the data to the format required by the learning algorithm, analyzing the output of the learning algorithm, and incorporating domain knowledge into the learning algorithm or the learned model.

HCI Cost of Data Engineering
By "data engineering", we mean the steps required to prepare the data so that they are suitable for a standard inductive concept learning algorithm. This includes finding the right features and converting the data to the required format. Although there has been some discussion of the issues involved in data engineering (Turney et al., 1995), we are not aware of any attempt to measure the HCI costs involved in data engineering.

HCI Cost of Parameter Setting
Most learning algorithms have a number of parameters that effect their performance, often by adjusting their bias. There is a cost involved in determining the best parameter settings. Often cross-validation is used to set the parameters (Breiman et al., 1984). Again, we are not aware of any attempt to measure the HCI costs of parameter setting.

HCI Cost of Analysis of Learned Models
There is a human cost associated with understanding induced models, which is particularly important when the aim of inductive concept learning is to gain insight into the physical process that generated the data, rather than to predict the class of future cases. This is often discussed in the decision tree induction literature, where it is (crudely) measured by the number of nodes in the induced decision tree (Mingers, 1989).

HCI Cost of Incorporating Domain Knowledge
Several researchers have examined ways of embedding domain knowledge in a learning algorithm (Opitz and Shavlik, 1997). It has often been observed, in the context of expert system construction, that acquiring domain knowledge from a domain expert is a major bottleneck. We suppose that it would also be a bottleneck in the context of inductive concept learning, but we are not aware of any attempt to measure the cost.

Cost of Instability
When an induced model is used to gain understanding of the underlying process that generated the data, it is important that the model should be stable (Turney, 1995c;Domingos, 1998). By stability, we mean that, if two batches of data are generated from the same physical process, then the two corresponding induced models should be similar. If the two models are dissimilar, the learning algorithm is unstable. This is related to the scientific principle that experiments should be repeatable. Stability may be seen as a benefit and instability as a cost.
Stability may be increased by acquiring more data (using a larger training set) or by increasing the bias of the learning algorithm (Turney, 1995c). Acquiring more data can be costly (Section 8). Increasing the bias of an algorithm can increase the misclassification error rate (Section 2), unless the bias is suitable for the given learning task. Domingos (1998) presents a meta-learning algorithm, CMM, that can be used to trade off accuracy (Section 2), comprehensibility (Section 9.3), and stability.

Conclusion
In this paper, we have presented a taxonomy of types of cost in inductive concept learning. It is our hope that this taxonomy may serve to organize the literature on costsensitive learning and to inspire research into underinvestigated types of cost.
We do not claim that this taxonomy is complete or unique. No doubt we have omitted important types of cost, and certainly other researches would prefer other taxonomies.
As we worked on this paper, it gradually became clear to us that the cost of misclassification errors occupies a unique position in the taxonomy. All of the other costs that we have discussed here can only be rationally evaluated in the context of the misclassification error cost (for the cost of intervention, the unwanted achievement cost is analogous to the misclassification error cost).
In decision theory (Pearl, 1988) and in the uncertainty in artificial intelligence literature (Pipitone et al., 1991), test costs are generally considered in conjunction with misclassification error costs. However, in the inductive concept learning literature, it is striking that this has largely been overlooked. For example, before Turney (1995a), all of the papers on inductive concept learning with test costs did not consider test costs in the context of misclassification error costs (Núñez, 1988(Núñez, , 1991Tan, 1991aTan, , 1991bTan, , 1993). Yet, if all test costs are greater than the misclassification error cost, then it is never rational to do any tests; and if the misclassification error cost is much greater than the cost of any test, then it is rational to do all of the tests, unless you are certain that they are irrelevant.
Similarly, as far as we know, none of the papers on active learning (Cohn et al., 1995(Cohn et al., , 1996Krogh andVedelsby, 1995, Hasenjager andRitter, 1998) consider the misclassification error cost, although we must know something about the misclassification error cost in order to rationally determine whether to pay the cost of the teacher.