Let’s formally define the category imbalance problem then intuitively derive solutions for it!

Currently, I even have been constructing a package to deal with class imbalance in Julia called Imbalance.jl. It took me numerous effort when it comes to reading papers and searching at implementations while constructing the package so I believed it might be helpful to share what I’ve learned concerning the class imbalance problem generally, together with among the hottest algorithms used to tackle it. This includes naive random oversampling, ROSE, SMOTE, SMOTE-Nominal, and SMOTE-Nominal Continuous. For this text we are going to give attention to the primary two.

Before we start with the algorithms, let’s first formally understand class imbalance.

The Class Imbalance Problem

Most if not all machine learning algorithms could be viewed as a type of empirical risk minimization where the target is to search out the parameters θ that for some loss function L minimize:

As an illustration, linear regression takes L to be squared loss, logistic regression takes it to be cross-entropy loss, SVM takes it to be hinge loss, Adaptive boosting takes it to be exponential loss.

The underlying assumption is that if f_θ minimizes this empirical risk over the dataset which could also be viewed as a random sample from the population then it needs to be close enough to the goal function f that we seek the model which minimizes the same amount over the dataset and furthermore the entire population.

In a multi-class setting with K classes, we are able to write the empirical risk as

Class imbalance occurs when some classes have much fewer examples than other classes. On this case, the corresponding terms contribute minimally to the sum which makes it easier for any learning algorithm to search out an approximate solution to the empirical risk that mostly only minimizes over the numerous sums. This yields a hypothesis f_θ which may be very different from the true goal f with respect to the minority classes which will be the most significant for the applying in query.

Conclusively, the next are the conditions where we have now a category imbalance problem:

1 — The points within the training set will not be distributed “fairly” among the many classes; some classes have far less points belonging to them than others.

2— The model doesn’t perform well on points belonging to such minority classes after training.

The degree to which this problem is antagonistic is determined by how essential such minority classes are for the applying. Most frequently they’re far more essential than the bulk class (e.g., classifying fraudulent transactions).

Solving the Class Imbalance Problem

It becomes obvious from the outline of the issue that one treatment is to weight the smaller sums (i.e., those belonging to minority classes) in order that a learning algorithm more easily avoids approximate solutions that exploit their insignificance. It’s often easily possible to switch machine learning algorithms for that purpose; especially after they are explicitly a type of empirical risk minimization and isn’t just such as it for some loss function.

One other approach that attempts to unravel the issue is resampling the info. In its simplest form it could possibly be viewed as such as the cost-sensitive approach of assigning weights. Consider the next algorithm

Given: An imbalanced dataset with K classes and an integer for every class
Wanted: A dataset where data from each class is replicated based on the integer
Operation: Repeat each point at school k, c times, where c is the associated integer

It needs to be obvious by plugging to the sum that that is such as the cost-sensitive approach; recall that minimizing a function is such as minimizing a scalar positive multiple of it.

Random Oversampling

The aforementioned algorithm suffers from a small problem; if class A has 900 examples and sophistication B has 600 examples then there is no such thing as a integer multiple that we are able to use to oversample class B to bring the dataset to exact balance. We will extend the algorithm to cope with replication ratios that aren’t integers by selecting points to copy randomly. As an illustration, if we wish to oversample 300 examples for sophistication B in order that the system is dropped at balance (such as a ratio of 1.5) then we are able to accomplish that by…

1 — Selecting 300 points randomly from class B
2— Replicating those points

This algorithm known as naive random oversampling and what it formally does is:

1 — Compute the needed variety of points to generate for every class (computed from some given ratios)
2— Suppose for sophistication X that number is Nx, then select Nx points randomly with substitute from the points belonging to that class then add them to form the brand new dataset

It needs to be obvious that that is on average such as the aforementioned algorithm and hence, also class-weighting. If the ratio for sophistication X is 2.0 then on average each point shall be picked once by random.

Here’s a random imbalanced dataset that I even have generated for 3 classes (0, 1, 2) which shows a histogram of the classes and a scatter plot of the points before and after oversampling.

Notice that there is no such thing as a visual difference within the two figures in the underside because all generated points are replicas of existing ones.

Lastly note that if as an alternative of randomly selecting examples to copy in minority classes, we randomly selected points to remove in majority classes then then the algorithm becomes naive random undersampling. This obviously has the drawback of losing useful data but sometimes eliminating data from “not so useful” majority classes solves the imbalance problem and results in significantly better performance towards the “far more useful” minority classes. On this and next articles we center our give attention to oversampling methods.

Random Oversampling Examples

It is sensible that we might achieve higher results than naive random oversampling if we slightly naturally added the points for every class by collecting more data in our dataset. As an illustration, suppose that…

• We would like to detect whether a transaction is fraud
• We’ve collected a dataset of 1K fraud transactions and 999K of valid transactions

It needs to be obvious that solving the imbalance problem by collecting one other 998K fraud transactions is much more superior than repeating the prevailing 1K ones 997K times. Specifically, we run a high risk of overfitting to the actual data observed within the latter case.

The truth is clearly that it isn’t generally feasible to gather more data for the minority classes; nonetheless, this sheds the sunshine on that we are able to do something higher than naive oversampling by repeating examples. We all know that any extra data we collect follows the probability distribution of the underlying population of knowledge belonging to the minority class so how about approximating this probability distribution then sampling from it to simulate collecting real examples. That is what the random oversampling examples (ROSE) algorithm does.

It follows then that ROSE tries to estimate the probability distribution P(x|y=k) for every class X after which draws the needed Nx samples from it. It’s well-known that one option to estimate such density is thru kernel density estimation which you’ll derive or intuit ranging from more crude versions corresponding to histogram evaluation. The next describes KDE:

Given: data points x
Wanted: An estimate of P(x)
Operation: Select a kernel function K(x) after which estimate P(x) as

Typically, we wish to have the ability to regulate the size of the kernel function (i.e., squeeze it or spread it) as that may improve the estimate of P(x) so in a more general sense we have now

In essence, what it does is place the kernel function above each point after which sum and normalize all of them so it integrates to 1.

The alternative of the kernel function itself is a hyperparameter; perhapse, one which has been shown to not be so significant so long as it satisfies basic properties corresponding to smoothness and symmetry. A straightforward Gaussian with σ as the size is a standard alternative and which ROSE uses for its KDE.

ROSE samples the Nx points from this distribution by performing the next:

• Select some extent randomly
• Place the Gaussian on it
• Sample one point from the Gaussian

That is similar to random oversampling except that after selecting some extent randomly it places a Gaussian on it and samples the Gaussian to generate the brand new point as an alternative of repeating the chosen point.

On this, ROSE sets the bandwidth h (or more generally the smoothing matrix in higher dimensions which is the covariance matrix parameter in the traditional distribution) using a rule of thumb called Silverman in order that the mean integrated squared error is minimized. Specifically,

where D_σ is a diagonal matrix of the usual deviations of every of the features, d is the variety of features and N is the variety of points.

Within the Imbalance.jl package, that is multiplied by one other constant s to permit optional control of the hyperparameter. For s=1 it’s left as within the paper and for s=0, ROSE becomes such as random oversampling. The next animation produced using the package illustrates the effect of accelerating s on the generated points.

Notice that the unique points don’t move and that as we increase s, the synthetic points generated because of each original point that was randomly chosen is even farther aside from it.

I hope this story has enlightened you with the category imbalance problem in machine learning and the way it could possibly be solved. Let’s consider the algorithms presented within the SMOTE paper for the subsequent story.

Reference:
[1] G Menardi, N. Torelli, “Training and assessing classification rules with imbalanced data,” Data Mining and Knowledge Discovery, 28(1), pp.92–122, 2014.