What is the root cause of the class imbalance problem?

Question

I've been thinking a lot about the "class imbalance problem" in machine/statistical learning lately, and am drawing ever deeper into a feeling that I just don't understand what is going on.

First let me define (or attempt to) define my terms:

The class imbalance problem in machine/statistical learning is the observation that some binary classification(*) algorithms do not perform well when the proportion of 0 classes to 1 classes is very skewed.

So, in the above, for example, if there were one-hundred $0$ classes for every single $1$ class, I would say the class imbalance is $1$ to $100$, or $1\%$.

Most statements of the problem I have seen lack what I would think of as sufficient qualification (what models struggle, how imbalanced is a problem), and this is one source of my confusion.

A survey of the standard texts in machine/statistical learning turns up little:

• Elements of Statistical Leaning and Introduction to Statistical Learning do not contain "class imbalance" in the index.

• Machine Learning for Predictive Data Analytics also does not contain"class imbalance" in the index.

• Murphy's Machine Learning: A Probabilistic Perspective does contain "class imbalance* in the index. The reference is to a section on SVM's, where I found the following tantalizing comment:

  It is worth remembering that all these difficulties, and the plethora of heuristics that have been proposed to fix them, fundamentally arise because SVM's do not model uncertainty using probabilities, so their output scores are not comparable across classes.

This comment does jive with my intuition and experience: at my previous job we would routinely fit logistic regressions and gradient boosted tree models (to minimize binomial log-likelihood) to unbalanced data (on the order of a $1\%$ class imbalance), with no obvious issues in performance.

I have read (somewhere) that classification tree based models (trees themselves and random forest) do also suffer from the class imbalance problem. This muddies the waters a little bit, trees do, in some sense, return probabilities: the voting record for the target class in each terminal node of the tree.

So, to wrap up, what I'm really after is a conceptual understanding of the forces that lead to the class imbalance problem (if it exists).

• Is it something we do to ourselves with badly chosen algorithms and lazy default classification thresholds?
• Does it vanish if we always fit probability models that optimize proper scoring criteria? Said differently, is the cause simply a poor choice of loss function, i.e. evaluating the predictive power of a model based on hard classification rules and overall accuracy?
• If so, are models that do not optimize proper scoring rules then useless (or at least less useful)?

(*) By classification I mean any statistical model fit to binary response data. I am not assuming that my goal is a hard assignment to one class or the other, though it may be.

Answer 1

An entry from the Encyclopedia of Machine Learning (https://cling.csd.uwo.ca/papers/cost_sensitive.pdf) helpfully explains that what gets called "the class imbalance problem" is better understood as three separate problems:

1. assuming that an accuracy metric is appropriate when it is not
2. assuming that the test distribution matches the training distribution when it does not
3. assuming that you have enough minority class data when you do not

The authors explain:

The class imbalanced datasets occurs in many real-world applications where the class distributions of data are highly imbalanced. Again, without loss of generality, we assume that the minority or rare class is the positive class, and the majority class is the negative class. Often the minority class is very small, such as 1%of the dataset. If we apply most traditional (cost-insensitive) classifiers on the dataset, they will likely to predict everything as negative (the majority class). This was often regarded as a problem in learning from highly imbalanced datasets.

However, as pointed out by (Provost, 2000), two fundamental assumptions are often made in the traditional cost-insensitive classifiers. The first is that the goal of the classifiers is to maximize the accuracy (or minimize the error rate); the second is that the class distribution of the training and test datasets is the same. Under these two assumptions, predicting everything as negative for a highly imbalanced dataset is often the right thing to do. (Drummond and Holte, 2005) show that it is usually very difficult to outperform this simple classifier in this situation.

Thus, the imbalanced class problem becomes meaningful only if one or both of the two assumptions above are not true; that is, if the cost of different types of error (false positive and false negative in the binary classification) is not the same, or if the class distribution in the test data is different from that of the training data. The first case can be dealt with effectively using methods in cost-sensitive meta-learning.

In the case when the misclassification cost is not equal, it is usually more expensive to misclassify a minority (positive) example into the majority (negative) class, than a majority example into the minority class (otherwise it is more plausible to predict everything as negative). That is, FN > FP. Thus, given the values of FN and FP, a variety of cost-sensitive meta-learning methods can be, and have been, used to solve the class imbalance problem (Ling and Li, 1998; Japkowicz and Stephen, 2002). If the values of FN and FP are not unknown explicitly, FN and FP can be assigned to be proportional to p(-):p(+) (Japkowicz and Stephen, 2002).

In case the class distributions of training and test datasets are different (for example, if the training data is highly imbalanced but the test data is more balanced), an obvious approach is to sample the training data such that its class distribution is the same as the test data (by oversampling the minority class and/or undersampling the majority class)(Provost, 2000).

Note that sometimes the number of examples of the minority class is too small for classifiers to learn adequately. This is the problem of insufficient (small) training data, different from that of the imbalanced datasets.

Thus, as Murphy implies, there is nothing inherently problematic about using imbalanced classes, provided you avoid these three mistakes. Models that yield posterior probabilities make it easier to avoid error (1) than do discriminant models like SVM because they enable you to separate inference from decision-making. (See Bishop's section 1.5.4 Inference and Decision for further discussion of that last point.)

Hope that helps.

Answer 2

Anything that involves optimization to minimize a loss function will, if sufficiently convex, give a solution that is a global minimum of that loss function. I say 'sufficiently convex' since deep networks are not on the whole convex, but give reasonable minimums in practice, with careful choices of learning rate etc.

Therefore, the behavior of such models is defined by whatever we put in the loss function.

Imagine that we have a model, $F$, that assigns some arbitrary real scalar to each example, such that more negative values tend to indicate class A, and more positive numbers tend to indicate class B.

$$y_f = f(\mathbf{x})$$

We use $F$ to create model $G$, which assigns a threshold, $b$, to the output of $F$, implicitly or explicitly, such that when $F$ outputs a value greater than $b$ then model $G$ predicts class B, else it predicts class A.

$$ y_g = \begin{cases} B & \text{if } f(\mathbf{x}) > b \\ A & \text{otherwise}\\ \end{cases} $$

By varying the threshold $b$ that model $G$ learns, we can vary the proportion of examples that are classified as class A or class B. We can move along a curve of precision/recall, for each class. A higher threshold gives lower recall for class B, but probably higher precision.

Imagine that the model $F$ is such that if we choose a threshold that gives equal precision and recall to either class, then the accuracy of model G is 90%, for either class (by symmetry). So, given a training example, $G$ would get the example right 90% of the time, no matter what is the ground truth, A or B. This is presumably where we want to get to? Let's call this our 'ideal threshold', or 'ideal model G', or perhaps $G^*$.

Now, let's say we have a loss function which is:

$$ \mathcal{L} = \frac{1}{N}\sum_{n=1}^N I_{y_i \ne g(x_i)} $$

where $I_c$ is an indicator variable that is $1$ when $c$ is true, else $0$, $y_i$ is the true class for example $i$, and $g(x_i)$ is the predicted class for example $i$, by model G.

Imagine that we have a dataset that has 100 times as many training examples of class A than class B. And then we feed examples through. For every 99 examples of A, we expect to get $99*0.9 = 89.1$ examples correct, and $99*0.1=9.9$ examples incorrect. Similarly, for every 1 example of B, we expect to get $1 * 0.9=0.9$ examples correct, and $1 * 0.1=0.1$ examples incorrect. The expected loss will be:

$ \mathcal{L} = (9.9 + 0.1)/100 = 0.1 $

Now, lets look at a model $G$ where the threshold is set such that class A is systematically chosen. Now, for every 99 examples of A, all 99 will be correct. Zero loss. But each example of B will be systematically not chosen, giving a loss of $1/100$, so the expected loss over the training set will be:

$ \mathcal{L} = 0.01 $

Ten times lower than the loss when setting the threshold such as to assign equal recall and precision to each class.

Therefore, the loss function will drive model $G$ to choose a threshold which chooses A with higher probability than class B, driving up the recall for class A, but lowering that for class B. The resulting model no longer matches what we might hope, no longer matches our ideal model $G^*$.

To correct the model, we'd need to for example modify the loss function such that getting B wrong costs a lot more than getting A wrong. Then this will modify the loss function to have a minimum closer to the earlier ideal model $G^*$, which assigned equal precision/recall to each class.

Alternatively, we can modify the dataset by cloning every B example 99 times, which will also cause the loss function to no longer have a minimum at a position different from our earlier ideal threshold.

Answer 3

Note that one-class classifiers don't have an imbalance problem as they look at each class independently from all other classes and they can cope with "not-classes" by just not modeling them. (They may have a problem with too small sample size, of course).

Many problems that would be more appropriately modeled by one-class classifiers lead to ill-defined models when dicriminative approaches are used, of which "class imbalance problems" are one symptom.

As an example, consider some product that can be good to be sold or not. Such a situation is usually characterized by

class         | "good"                        | "not good"
--------------+-------------------------------+------------------------------------------
sample size   | large                         | small
              |                               |
feature space | single, well-delimited region | many possibilities of *something* wrong 
              |                               | (possibly well-defined sub-groups of
              |                               |    particular fault reasons/mechanisms) 
              |                               | => not a well defined region, 
              |                               | spread over large parts of feature space
              |                               |
future cases  | can be expected to end up     | may show up *anywhere* 
              | inside modeled region         | (except in good region)

Thus, class "good" is well-defined while class "not-good" is ill-defined. If such a situation is modeled by a discriminative classifier, we have a two-fold "imbalance problem": not only has the "not-good" class small sample size, it also has even lower sample density (fewer samples spread out over a larger part of the feature space).

This type of "class imbalance problem" will vanish when the task is modeled as one-class recognition of the well-defined "good" class.

Answer 4

Tongue slightly in cheek - the root cause of the class imbalance problem is calling it the class imbalance problem, which implies that the class imbalance causes a problem. This is very rarely the case (and when it does happen the only solution is likely to be to collect more data). The real problem is practitioners (and algorithm developers) not paying attention to the requirements of the application. In most cases it is a cost-sensitive learning problem in disguise (where the degree of imbalance is completely irrelevant to the solution, it depends only on the misclassification costs) or a problem of a difference in the distribution of patterns in the training set and in the test set or operational conditions (for which the degree of imbalance is again essentially irrelevant - the solution is the same as for balanced datasets).

We should stop talking about class imbalance being a problem as it obscures the real problems (e.g. cost-sensitive learning) and prevents people from addressing them.