Why downsample?

Question

Suppose I want to learn a classifier that predicts if an email is spam. And suppose only 1% of emails are spam.

The easiest thing to do would be to learn the trivial classifier that says none of the emails are spam. This classifier would give us 99% accuracy, but it wouldn't learn anything interesting, and would have a 100% rate of false negatives.

To solve this problem, people have told me to "downsample", or learn on a subset of the data where 50% of the examples are spam and 50% are not spam.

But I'm worried about this approach, since once we build this classifier and start using it on a real corpus of emails (as opposed to a 50/50 test set), it may predict that a lot of emails are spam when they're really not. Just because it's used to seeing much more spam than there actually is in the dataset.

So how do we fix this problem?

("Upsampling," or repeating the positive training examples multiple times so 50% of the data is positive training examples, seems to suffer from similar problems.)

Answer 1

Most classification models in fact don't yield a binary decision, but rather a continuous decision value (for instance, logistic regression models output a probability, SVMs output a signed distance to the hyperplane, ...). Using the decision values we can rank test samples, from 'almost certainly positive' to 'almost certainly negative'.

Based on the decision value, you can always assign some cutoff that configures the classifier in such a way that a certain fraction of data is labeled as positive. Determining an appropriate threshold can be done via the model's ROC or PR curves. You can play with the decision threshold regardless of the balance used in the training set. In other words, techniques like up -or downsampling are orthogonal to this.

Assuming the model is better than random, you can intuitively see that increasing the threshold for positive classification (which leads to less positive predictions) increases the model's precision at the cost of lower recall and vice versa.

Consider SVM as an intuitive example: the main challenge is to learn the orientation of the separating hyperplane. Up -or downsampling can help with this (I recommend preferring upsampling over downsampling). When the orientation of the hyperplane is good, we can play with the decision threshold (e.g. signed distance to the hyperplane) to get a desired fraction of positive predictions.

Answer 2

The real problem here is your choice of metric: % accuracy is a poor measure of a model's success on an un-balanced dataset (for the exactly reason you mention: it's trivial to achieve 99% accuracy in this case).

Balancing your dataset before fitting the model is a bad solution as it biases your model and (even worse) throws out potentially useful data.

You're much better off balancing your accuracy metric, rather than balancing your data. For example you could use balanced accuracy when evaluating you model: (error for the positive class + error for the negative class)/2. If you predict all positive or all negative, this metric will be 50% which is a nice property.

In my opinion, the only reason to down-sample is when you have too much data and can't fit your model. Many classifiers (logistic regression for example) will do fine on un-balanced data.

Answer 3

As always @Marc Claesen as a great answer.

I'd just add that the key concept that seems to be missing is the concept of a cost function. In any model you have an implicit or explicit cost of false negatives to false positives (FN/FP). For the unbalanced data described one is often willing to have a 5:1 or 10:1 ratio. There are many ways of introducing cost functions into models. A traditional method is to impose a probability cut-off on the probabilities produced by a model - this works well for logistic regression.

A method used for strict classifiers that do not naturally output probability estimates is to undersample the majority class at a ratio that will induce the cost function you are interested in. Note that if you sample at 50/50 you are inducing an arbitrary cost function. The cost function is different but just as arbitrary as if you sampled at the prevalence rate. You can often predict an appropriate sampling ratio that corresponds to your cost function (it is usually not 50/50), but most practitioners that I've talked to just try a couple of sampling ratios and choose the one closest to their cost function.

Answer 4

Answering Jessica's question directly - one reason for downsampling is when you're working with a large dataset and facing memory limits on your computer or simply want to reduce processing time. Downsampling (i.e., taking a random sample without replacement) from the negative cases reduces the dataset to a more manageable size.

You mentioned using a "classifier" in your question but didn't specify which one. One classifier you may want to avoid are decision trees. When running a simple decision tree on rare event data, I often find the tree builds only a single root given it has difficulty splitting so few positive cases into categories. There may be more sophisticated methods to improve the performance of trees for rare events - I don't know of any off the top of my head.

Therefore using a logistic regression which returns a continuous predicted probability value, as suggested by Marc Claesen, is a better approach. If you're performing a logistic regression on the data, the coefficients remain unbiased despite there being fewer records. You will have to adjust the intercept, $\beta_0$, from your downsampled regression according to the formula from Hosmer and Lemeshow, 2000:

$$\beta_c=\beta_0 - \log\left(\frac{p_+}{1-p_+}\right)$$

where $p_+$ is the fraction of positive cases in your pre-downsampling population.

Finding your preferred spam ID threshold with the ROC can be done by first scoring the complete dataset with the model coefficients traned on the downsampled dataset, and then ranking the records from highest to lowest predicted probability of being spam. Next, take the top $n$ scored records, where $n$ is whatever threshold you want to set (100, 500, 1000, etc.) and then calculate the percentage of false positive cases in the top $n$ cases and the percentage of false negative cases in the remaining lower tier of $N$-$n$ cases in order to find the right balance of sensitivity/specificity that serves your needs.

Answer 5

Of course classifying everything as 'not spam' allows you to say that, given 100 mails, it classifies correctly 99 of them, but it also classifies as 'not spam' the only one labelled as spam (100% False Positive). It turns out that the metric you choose to evaluate the algorithm is not adapt. This video exemplifies the concept.

Roughly speaking, balancing the dataset allows you to weight the misclassification errors. An algorithm that uses an unbalanced training set presumably will not learn to discriminate from the features, because it would not give much importance to the fact that misclassifies the data of the scanty class.

Answer 6

I would not go for either downsampling or upsampling as both tricks the learning algorithm, however, if the data was imbalanced the accuracy measure becomes invalid or uninformative, therefore, it is better to use precision and recall measures, both depends mainly on the TP (the correctly classified spams in your case) this gives a good idea about the real performance of your system in terms detecting spams regardless the number of the negative examples.