Approaches to Imbalanced Classes

I had a listener named Scott write in after listening to our episode called The Library Problem and ask an interesting question. In this episode, I explained how using machine learning to predict whether or not a book would be returned has an imbalanced dataset. The vast majority of transactions at the library are "good" ones, meaning the patron brings the book back. Worse, the truly interesting class you'd like to predict and avoid (i.e. books that won't be returned) has the minority of examples in your training set.

Part of the problem here is that you have a limited number of examples that a machine learning algorithm can "study" to learn from. If given 100 examples of Rembrandt paintings, one might assume person could start accurately identifying other Rembrandts. If given only a single painting, the observer might not appreciate the unique features that separate Rembrandt from other artists. In the episode I suggested that a useful approach would be to weight your training data appropriately to emphasize the importance of the minority cases. This is pretty easy to do with most ML software, and some even do this automagically.

In addition to weighting, oversampling and stratified sampling are techniques that one could apply, but I find weighting to be the most common in practice. However, the weighting only helps with the tuning of the algorithm. It doesn't actually address the problem that the examples you have might not be expressive enough to demonstrate the underlying data generating process?

If that last sentence sounded great to you, skip this and the next four paragraphs. Every one else, let's dive deeper. I'm using specific language that is common in the algorithmic and statistical literature which might seem foreign or confusing to the casual reader. The first thing to understand is the idea of a Data Generating Process (DGP). To appreciate the meaning of a DGP, you have to think very mechanically about the world.

Everything is a system. Clearly an automobile is a system - a set of components that perform specific functions towards the objective of converting input signals from the steering wheel and pedals to adjustments in the rotation and angle of the wheels. Alfréd Rényi stated that "a mathematician is a machine for turning coffee into theorems". In a factory setting, I might be interested in the number of boxes that roll off the assembly line per day. I probably care about the mean and variances of this statistic. Those values are probably sufficient for my needs. I can, in some sense, ignore the DGP. It's a complicated process of new hires, sick days, inconsistency between workers, slow downs in other parts of the process, etc. At the end of the day, I might not need or want to understand every mechanical element of the factory that goes into the number of units that get completed each day, but I do understand that the factory as an entire system is my DGP.

From the library's perspective, it's Patrons generate checkouts and after some delay, typically return their books. What makes an individual patron return their book on a given day? Perhaps I returned my last book on Tuesday at 11am because I had a downtime between two appointments small enough that it didn't make sense to go back to the office, but big enough that I could swing by the library which was on the way. TMI!

The library doesn't have access to the individual schedules of patrons or their decision making processes. At best, maybe one day libraries could somehow get access to all our digital calendars. That would be an interesting ML problem - predict whether or not someone is going to complete a task on their to-do list based on the data found on their calendar! The library has a very limited view into the features that could yield a 99% accurate prediction. The DGP is simply too complex.

A complex DGP doesn't mean the problem is hopeless. My library problem is hard, because its requesting predictions about specific transactions. A more practical problem might be for the library to ask for a prediction about the total number of lost books in a given period. This doesn't require the individual items be predicted, just the global number. That's a much easier problem. However, it's still trying to learn a statistical model about a DGP for which it can never know the true systematic mechanism.

Scott wrote in with a novel suggestion for addressing class imbalance - why couldn't the imbalanced be addressed by generating more negative examples? If the algorithm is hungry for stolen books, why not generate a few fictitious cases and include them in the training set? The core problem here is the potential for a model to not generalize. Here's why.

In some problems the DGP is known, or closely known. Many ecological models, I'm told, are pretty accurately expressed in a set of stochastic equations. In video games, the DGP process is implicitly defined - it's the game's engine. If and when the DGP can be confidently simulated, the idea of producing more false examples can often be a productive one. I have to confess, in my life, I've never encountered a situation where I was applying ML yet knew a great deal about the DGP. These problems are certainly out there, so your mileage may vary.

If the underlying DGP is a bit of a mystery, then any fake examples you want to produce are going to be produced by some randomization process which is user defined. Whatever code you write to create fake examples is going to follow some set of rules (i.e. your source code). Even if you introduce randomization, that randomization is a choice you are making which may or may not conform to the actual DGP.

As a result, the introduction of generated minority case examples is likely to create a model which has been trained to do a good job recognizing your fake data algorithm. There is no guarentee this model will generalize to the real world. The success applying this model to the real world will depend entirely on how close the true DGP is to the fake DGP. If you already had a good understanding of the DGP for library returns, you could probably build a better solution without the use of ML.

Although I won't cover it in this blog post, I'd feel incomplete if I didn't include a final mention of adversarial learning. This idea is not particularly new, but has gained some recent surges of interest, especially in deep learning. The idea of adversarial learning is to first train a classifier to decide some particular problem. Next, generate a second model whose optimization objective is to create fake data which is capable of tricking the first classifier. If you can produce examples that don't fit the actualy class being learned, but are able to fool the classifier, then the first classifier can possibly be trained again to improve it's ability to distinguish between fake and real examples. This process can be iterative. A lot of great work has been done in this area that we hope to cover in future posts and episodes.