An Empirical Study of the Noise Impact on Cost-Sensitive Learning

1 Introduction

Recently, a body of work has been attempted to address cost-related inductive learning issues, with techniques known as cost-sensitive learning (Tan 93, Turney 95, Pazzani et al. 94), where the "cost" could be interpreted as misclassification cost, training cost, and test cost (Turney). Among all different types of costs, the misclassification cost is the most popular one. In general, misclassification cost is described by a cost matrix C, with C(i, j) indicating the cost of predicting that an example belongs to class i when in fact it belongs to class j. With this type of cost, the objective of a CS learner is to form a generalization such that the average cost on previously unobserved instances is minimized. Obviously, this minimal cost is determined by two most important factors: (1) the inductive bias of the underlying CS learner; and (2) the quality of the training data. Existing research has made significant progress in exploring efficient CS learning algorithms (Bradford et al. 98, Zuberk & Dietterich 02, Tan 93, Geibel & Wysotzki 03, Brefeld et. al. 03, Domingos 99, Chan & Stolfo 98, Zadrozny 03, Abe & Zadrozny 04), with assumptions that the input data are noise-free or noise in the datasets is not significant. In datadriven application domains, many potential problems, such as unreliable data acquisition sources, faulty sensors, and data collection errors, will make data vulnerable to errors. It is therefore important to understand how a CS learning algorithm behaves in noisy environments and how to handle data errors in supporting effective CS learning. In this paper, we report our empirical study on the impact of noise on CS learning. It is hoped that our observations will be beneficial to any real-world applications with cost concerns.

The support of the National Science Foundation of China under Grant No.60674109 is acknowledged.

2 Related Work

The problem of learning from noisy data has been a focus of much attention in data mining (Quinlan 86b), and most algorithms have a mechanism to handle noise in the training data. For example, pruning on a decision tree is designed to reduce the chance that the tree is overfitting to noise in the training data (Quinlan 86). In real-world applications, many learning algorithms rely on a data cleaning model for data enhancement (Brodley & Friedl 99). Although the problem of error handling in supervised learning has been well studied, research in the area has been mainly focused on general inductive learning for the minimization of zero-one loss or error rate. In reality, many applications are not only characterized by error rate, but also by various types of costs (Turney), such as misclassification cost and test cost.

Among all different types of costs, the misclassification cost is the most popular one. Assume that examples of a dataset are drawn independently from a distribution, d, with domain X Y C, where X is the input space to a classifier, Y is an output space, and C [0, ) is the importance (misclassification cost) associated with misclassifying that example. The goal of cost-sensitive (CS) learning, from the misclassification cost perspective, is to learn a classifier h: X Y which minimizes the expected cost (Zadrozny 03)

Two important issues determine the minimization of the expected cost: the total number of misclassifications and the cost of each single misclassification. To minimize overall costs, a compromise is often made by sacrificing cheap examples and enhancing the accuracy on classes containing expensive instances. This is distinct from general inductive learning, because the latter is biased towards larger classes (likely the cheap examples in a CS scenario). To enhance a CS learner trained from noisy data environments, Zhu and Wu (04) have proposed a Classification Filter for data cleansing. But the study of CS learners in noisy environments still lacks in-depth empirical and theoretical analysis.

3 Experiment Setting

An empirical study needs a full control over noise levels in the data, so that we can observe the behaviors of the underlying CS learners. For this purpose, we implement two manual corruption mechanisms, Total Random Corruption (TRC) and Proportional Random Corruption (PRC). With TRC, when the users specify an intended corruption level x 100%, we will randomly introduce noise to all classes. I.e., an instance with its label i has an x 100% chance to be mislabeled as another random class (excluding class i). TRC, however, changes the class distribution in the dataset after noise corruption, which raises a big concern in CS Learning, because modifying the class distribution may change the average cost considerably. We then propose PRC, which keeps the class distribution constant during the noise corruption. Given a dataset with Y classes, assume the original class distribution is 1, 2,.., Y, with i Y i =1, where 1 and Y are the percentage of the most and least common classes respectively. For any user specified corruption level, say x 100%, we proportionally introduce random noise to different classes with instances in class i having a ( Y / i) x 100% chance of being corrupted as another random class. That is, we use the least common class as the baseline, and proportionally introduce noise to different classes. It is obvious that the actual noise level in PRC is less (or even much less) than the intended corruption level.

For each experiment, we perform 10 times 3-fold crossvalidation. In each run, the dataset is divided into a training set E and a test set T. We introduce a certain level of noise to E and generate a noisy dataset E . Meanwhile, assuming a noise cleansing technique is able to remove all noisy instances from E , we can therefore build a cleansed dataset E . We observe CS learners trained from E, E , and E to study noise impact (assessed by using T as the test set). The empirical study is made by the observation on three benchmark two-class datasets, Credit Screen Dataset (Credit), Wisconsin Breast Cancer Dataset (WDBC), and Thyroid disease dataset (Sick) (Blake & Merz 98), with their class distributions varying from almost even to extremely biased (as shown in Table 1). We use two-class datasets as our test bed, because a two-class problem can explicitly reveal the impacts of noise and cost-ratio on CS learning, whereas for multiple-class problems, issues such as costs among classes, class distributions, and errors in each class often make it difficult to draw comprehensive conclusions. We use the C5.0 CS classification tree (Quinlan 97) in all experiments.

To assign misclassification cost matrix values, C(i, j), i j, we adopt a Proportional Cost (PC) mechanism: for any two classes i and j (i j), we first check their class distribution i and j. If i j, which means that class j is relatively rarer than i, then C(j, i)=100 and C(i, j) equals to 100 r; otherwise C(i, j)=100 and C(j, i)= 100 r, where r is the cost-ratio, as defined by Eq. (2).

4 Noise Impact

4.1 Misclassification Costs

In Figs. 1 to 2, we report the noise impact on the cost of CS learners trained from the benchmark datasets, where Figs. 1(a) and 1(b), and Figs. 2(a) and 2(b) represent the results from different noise corruption models of the WDBC and Sick dataset respectively. Fig. 2(c) reports the results from the Credit dataset (because the class distributions of the Credit dataset are almost even, we only report its results on the TRC model). In all figures, the first and the second rows of the x-axis represent the intended and actual noise levels in the dataset. The y-axis indicates the average cost of CS classifiers. CS_E and CS_E represent the average cost of a CS classifier trained from E and E (before and after noise cleaning).

As we can see from Figs. 1 to 2, for both noise corruption models, the average cost of a CS classifier proportionally increases with the value of r, even if the dataset is noisefree. This does not surprise us, because we fix the cost of C(i, j) to 100 and set the cost of C(j, i) to 100 r. So raising the value of r will surely increase the average cost. When noise is introduced to the dataset, the average cost will inevitably increase, regardless of the noise corruption model and the value of r. On the other hand, removing noisy instances can keep average costs almost the same as that of the noise-free dataset (E). This indicates that data cleansing is an effective way to reduce the impact of noise on CS learning.

Although noise increases the cost of a CS classifier regardless of the cost-ratio (r), when comparing the results from three r values, we can find that their patterns of increase are different. As shown in Fig. 1(a), Fig. 2(a), and Fig. 2(c), when r is small, increasing noise levels will gradually raise the average cost, and the impacts of noise are less significant for low noise level data. On the other hand, for large r values, introducing a small portion of noise will elevate the average cost greatly, and increasing the noise level further does not show significant extra impacts. However, TRC in Fig. 1(a), Fig. 2(a), and Fig. 2(c) have already changed the class distribution of the dataset, it is not clear that given the same amount of noise in the dataset which one is responsible for the increase of the cost: the change of the class distribution or the large cost-ratio r. We then turn to Fig. 1(b) and Fig. 2(b) for answers, where the class distribution is constant during noise corruption.

As shown in Figs. 1(b) and 2(b), depending on the bias of the class distribution of the dataset, the actual noise level in the dataset is lower (or much lower) than the intended corruption level. For example, in Fig. 2(b), when the intended noise level is 0.1, the actual noise level in the database is just about 0.012 (please refer to Section 3 and Tab. 1 for the reason). At this noise level, the cost increase for r=2 is 0.56 (from 1.91 to 2.47), but for r=10 the increase is about 3.5 (from 5.8 to 9.31). One may argue that this increase may be incurred by increasing the class-ratio r, because raising r will make the minority class more expensive. Nevertheless, even if we assume that the classification accuracy remains the same, we can still see that the average increase from r=10 (3.5/10) is significantly larger than the increase from r=2 (0.56/2). It is obvious that given the same amount of noise in the dataset, even if noise does not change the class distribution, a dataset with a large cost-ratio tends to be more error prone and therefore may receive a large misclassification cost. These observations indicate that when the dataset has a large cost-ratio value, the existence of noise becomes fatal, and a small portion of noise can corrupt the results significantly. Because of its sensitivity to minor data errors, a dataset with a large cost-ratio will experience more difficulties in data cleansing, if the overall goal is to minimize the misclassification cost.

Another interesting finding in Figs. 1 to 2 is that when applying CS learners to a noisy dataset, it seems that the trained CS classifiers have a saturation point in reacting to the actual noise in the dataset, regardless of whether errors change the class distribution or not. When the noise level is below this point, it will continuously impact the CS classifier. But once the noise level is beyond this point, the classifier becomes insensitive to noise. The following analysis will reveal that this saturation point is determined by two most important factors: the class distribution and the costratio r. Given a two-class dataset, assuming its class distribution is 1: 2, with 1 and 2 denoting the distribution of the major class and the minor class respectively. The cost of predicting a minor class instance as the major class is CSmin r, with CSmin indicating the opposite cost (from the major class to the minor class). Assuming that we have built a CS classifier from the dataset and, for a test set T with examples, the classification error rates of this classifier on the whole test set and the major class are and 1 respectively. The error rate for the minor class 2 is the number of incorrectly classified minor class examples divided by the total number of minor class instances, as shown in Eq. (3). Then, the average misclassification cost in T, CSAvg, is denoted by Eq. (4).

(b) WDBC dataset, proportional random noise (PRC)

(a) Sick dataset, total random noise (TRC) (b) Sick dataset, proportional random noise (PRC) (c) Credit dataset, total random noise (TRC) Fig. 2. Impacts of class noise on the average cost of a CS classification algorithm

When the average error rate increases, it normally raises the average misclassification cost CSAvg, with its value bounded by an upper bound given by Eq. (5).

Actually, the upper bound in Eq. (5) is the average cost of predicting all instances belonging to the minor class when r 1/ 2, or predicting all instances belonging to the major class when r < 1/ 2 (which is the optimal solution for a CS classifier with low confidence, because any cost higher than this upper bound is not necessary). It is understandable that CSAvg CSUpper_bound holds most of the time, which eventually produces the inequality denoted by Eq. (6). Since

For two class problems 1+ 2=1, so Eq. (6) becomes

With the inequality in (7), we can finally analyze the relationship between the class distribution 1, 2, the cost ratio r, and the error rate , and reveal the following facts:

1. Given a test set T, the average misclassification error rate of a CS classifier, which is trained from a training set equivalent to T, is bounded by a critical value * defined by Eq. (7). When r 1/ 2, the higher the value of the cost-ratio r, the lower the *, and the more likely the classifier tends to approach the saturation point.
2. In theory, when r < 1/ 2, * becomes 1 1 2 ) 1 1 ( r , which can be approximated as 2. This means that the larger the number of minor class instances (a larger 2), the higher the *, and the less likely the classifier tends to approach the saturation point. However, this conclusion crucially relies on the fact that the underlying CS learner is "optimal" and indeed knows that sticking to the major class will lead to the lowest cost, which is not always the case in reality (as we will analyze next).

From Section 3 and Tab. 1, we know that 1: 2=0.627:0.373 (r > 1/ 2 for any r=2, 5, 10) and CSmin=100 for the WDBC dataset. So according to Eq. (5) CSUpper_bound is 62.7, which is consistent with the results in Fig. 1(a). Now the interesting results come from the results in Fig. 2(a), which also clearly poses a saturation point of the misclassification cost. According to Table 1 and Eq. (5), we know that for the Sick dataset 1: 2=0.94:0.06, so the ratio between 1/ 2 is far larger than the value of r. As a result, the CSUpper_bound should be r CS r 6 ) ( 2 1 min 2 (corresponding to the second item in Eq. (5)). Unfortunately, the results in Fig. 2 (a) indicate that the real CSUp-per_bound we got is about 94, which actually equals the value of having all instances classified into the minor class (the first item in Eq. (5)). In reality, it is understandable that the underlying CS learners are reluctant to stick to the major class for minimal misclassification cost, especially when noise has changed the apriori class distributions significantly. Instead, the CS learners will tend to stick to the minor classes in high uncertainty environments. As a result, the results from this seriously biased dataset are consistent with the conclusion drawn from the first item in Eq. (5).

Based on the above observations, we know that given datasets with the same noise level but a different cost-ratio value r, the larger the cost ratio r, the smaller the value of *, then the dataset is more likely to approach to a saturation point, where the misclassification cost appears to reach the maximum. Meanwhile, class noise does not continuously make an impact on the CS classifier all the time, and after noise reaches a certain level, the CS classifier may simply stick to the minor class. As a result, the impact of the noise in the system becomes constant. Given a dataset with r 1/ 2 (which is pretty common in reality), the higher the cost-ratio, the more likely the classifier tends to do so. For situations r < 1/ 2, the conclusions will also likely hold.

4.2 Classification Accuracies

The above observations conclude that a dataset with a higher cost-ratio is sensitive to data errors, and learners built from such data are most likely cost intensive. This conclusion does not, however, solve the concerns like: (1) why is a learner built from noisy data with large cost-ratio cost intensive? and (2) given any noisy dataset D, if users were able to build both a normal classifier or a CS classifier, which one of them is more trustworthy in identifying noisy examples? Now, let's refer to the theoretical proof and empirical comparisons of the classification accuracies between a normal classifier and a CS classifier for answers.

The following analyses are based on an existing Folk Theorem * (Zadrozny et. al. 03), which states that if we have examples drawn from the distribution:

* It was called "folk theorem" in the literature, because the authors concluded that the result appears to be known, although it has not been published yet.

where d(x,y,c) represents the distribution of the original dataset E, then the optimal error rate classifiers built for newly constructed distribution d are the optimal cost minimizers for data drawn from d. This theorem states that if we sample from the original distribution, d, of dataset E and constructing another distribution d , the efforts which try to learn an optimal error rate classifier on d actually leads to a classifier which optimizes the misclassification cost for d.

THEOREM 1: For a dataset E with a distribution d, assuming we are able to use an optimal learning theory to build a CS (h(t)), and a normal classifier (H(t)) respectively. Then h(t) is inferior to H(t) in terms of the average classification accuracy. That is, Errd(H) Errd(h), where ErrX( ) represents the classification error rate of the classifier on X.

Proof:

Assume a CS classifier h(t) was built from d. Then with the CS learning formula in Eq. (1), the expected cost of h(t) on d can be denoted by Eq. (9).

With the folk theorem in Eq. (8), we know that

pled distribution from d. Then Eq. (9) becomes.

We can transform Eq. (10) as follows.

Because , Eq. (11) becomes } ) , , {( max arg ] [ ) , , ( d c y x c E c c y x d

Because h(t) was built on a biased distribution d sampled from d, therefore Err ; otherwise, there is no need for H(t) to exist (we can directly use h(t) on d for normal classification). Therefore, we have Eq. (14) and the statement of Theorem 1 is true. )) ( ( )) ( ( t h Err t H d d

Now let's turn to the experimental results in Fig. 4 to evaluate whether the empirical results indeed support our theoretical analysis (the meaning of each curve in Fig. 4 is denoted in Fig. 3). In Fig. 4, Ac_Cs_E and Ac_Nm_E indicate the classification accuracies of a normal and a CS classifier trained fromE respectively. As shown in Fig. 4, when the cost-ratio is small (r=2), the differences between the accuracies of the normal and CS classifiers are trivial, with the accuracy of the CS classifier slightly worse. This is understandable, because a CS classifier likely sacrifices the accuracy for minimal costs. When the cost-ratio gets larger (r=5 or higher), the accuracy of the CS classifier becomes significantly worse than the normal classifier. If we compare Fig. 4(a) with Fig. 1(a) and Fig. 4(c) with Fig. 2(a), we can find that this is actually the reason a dataset with a large cost-ratio is more willing to approach to the saturation point. In this situation, a small portion of noise will make the CS classifier ignore the classification accuracy and stick to the "optimal" class.

Theorem 1 together with the results in Fig. 4 clearly indicates that in general situations, a CS classifier is inferior to a normal classifier, in terms of classification accuracy. Because removing mislabeled training examples was shown to lead to a better CS learner (as shown in Figs. 1 to 2), class noise handing for effective CS learning will crucially depend on accurate noise identification mechanisms. As a result, in noisy environments, if we want to adopt a noise identification mechanism for data cleansing, we shall trust a normal classifier rather than a CS classifier, because the former always has a higher accuracy in determining the right class of an instance.

4.3 Misclassification Costs and Accuracies

For a given example Ik, assume we know the probability of each class j, P(j|Ik), the Bayes optimal prediction for Ik is the class i that minimizes the conditional risk (Domingos 99, Duda & Hart 73), as defined by Eq. (15). The conditional risk P(i|Ik) is the conditional probability of predicting instance Ik belongs to class i. According to the Bayesian formula, we can transform Eq. (15) to Eq. (17). The Bayes optimal prediction is guaranteed to achieve the lowest possible overall cost (i.e., the lowest expected cost over all possible examples Ik, weighted by their probabilities P(Ik)).

With Eq. (17), it is clear that C(i, j), P(Ik | j), and j, together with the rule above imply a partition of the example space with j regions, such that class j is the optimal (leastcost) prediction in region j. The goal of cost-sensitive classification is to find the frontiers between these regions, explicitly or implicitly. However, this is complicated by two factors: (1) their dependence on the cost matrix C; and (2) the changes of both likelihood P(Ik | j) and prior probability j of different classes j, caused by the existence of noise. In general, as misclassifying examples of class j becomes more expensive relative to misclassifying others, the region where j should be predicted will expand at the expense of the regions of other classes, even if the class probabilities P(j|Ik) remain unchanged. In noisy environments, the probability of each class j, P(j|Ik), becomes less reliable, due to the reason that noise modifies the likelihood P(Ik|j) and the prior probability j. With Eq. (15), it is understandable that any error introduced to the likelihood P(Ik|j) is going to be magnified by the cost matrix C(i, j) (the CS classifier tends to favor "expensive" classes), even if noise does not change the apriori class distribution j. As a result, the higher the costratio in the dataset, the more sensitive the CS classifier behaves to the data errors.

According to Bayesian formula, we have

where P(Ik | j) is the likelihood of instance Ik, given a particular class j, and P is the sum of all the likelihoods. Assume j=P(j) is the prior probability of class j. Then, Eq. (15) can be transformed as follows:

5 Conclusions

This paper has empirically and theoretically studied the impacts of mislabeled training examples (commonly referred to as class noise) on cost-sensitive learning. We observed behaviors of cost-sensitive learners trained from different noisy environments and assessed their performances in terms of average misclassification cost and classification accuracy. Our quantitative study concludes that the existence of class noise can bring serious troubles (higher misclassification costs and lower classification accuracy) for cost-sensitive learning, especially when misclassifying some classes becomes extremely expensive. Removing noisy instances will significantly improve the performance of a costsensitive classifier learned from noisy environments. Our observations suggest that cost-sensitive learning should be carefully conducted in noisy environments. Comparing to general inductive learning, the success of the cost-sensitive learning crucially depends on the quality of the underlying data, where system performances can deteriorate dramatically in the presence of a small portion of data errors.