Robust High-Dimensional Classification From Few Positive Examples

1 Introduction

Suppose we have a corpus of articles tagged with topics, and we want to predict topic tags for new articles. Each article may have O(105 ) keyword-based features. But there may be only a few articles on any one topic. For example, in a knowledge base of "help articles" at Dell Inc., half the topics had fewer than 9 articles (Figure 1). In such cases, a training set of articles for any single topic will have very few positive examples on that topic, but many negative examples. Similarly, to predict tumor types from genetic data, we may have around 10 positive examples (patients) but O(104 ) features (genes) [Yeang et al., 2001]. Acquiring much more data is infeasibly costly and time-consuming. Similar problems occur in fraud detection [Wei et al., 2013] and cheminformatics [Czarnecki and Rataj, 2015]. For concreteness, consider the following problem which occurs in our experiments:

How do we train a classifier from 5 positive points and 1, 000 negative points with 100, 000 features?

Existing methods mainly focus on the class imbalance. But, as we show empirically, the critical constraint is the extreme scarcity of minority class examples (e.g., only 5 samples in the question above). Sampling-based methods may generate biased samples when these are built from so few minority datapoints. Cost-sensitive methods may overfit to the minority class samples due to the overwhelming cost of misclassifying them. The same applies to complex classifiers. For example, deep-learning methods [Chung et al., 2016] often need orders of magnitude more minority class samples. Simple methods outperform neural classifiers on limited training data [Cunha et al., 2021; Yang et al., 2019].

Our proposed method, called DIRECT, 1 offers a robust and tractable solution to the problem of imbalanced binary classification under extreme data scarcity with no side information. It is, to our knowledge, the first method to focus on this problem. Our approach is based on two ideas. First, we build a robust smooth distribution for the minority class, using only the statistics that can be reliably estimated. This robust distribution succinctly captures what can be inferred and what is uncertain about the true distribution. This makes DIRECT ˙robust to estimation errors, which helps combat the problems of limited sample size. Note that this is different from adversarial robustness, since there is no data corruption involved and the training and test distributions are the same.

1 Our code is available at https://github.com/deepayan12/direct.

Second, we show that DIRECT's expected loss under this robust distribution can be calculated in closed form. This enables DIRECT to bypass sample generation and train in a single-step. In effect, DIRECT optimizes over all possible samples, weighted by their probability. This improves both the speed and accuracy of the classifier.

DIRECT has several other appealing properties. With so few minority samples, cross-validation itself can be a source of error. However, DIRECT is parameter-free, and does not need cross-validation. DIRECT is also fast and easily implementable using any off-the-shelf optimizer.

Finally, we show strong empirical results on six text, two image, one medical, and twenty general UCI datasets. Most tasks have 10, 000 to 100, 000 features. DIRECT is up to 5x-7x better than sampling-based methods, 30-200% better than ensemble methods, 3x-7x better than cost-sensitive SVMs. On most datasets and settings, DIRECT is either comparable or better than existing methods. The most significant gains occur in settings with the fewest minority class samples, where the robustness of DIRECT has the most impact.

The rest of the paper is organized as follows. We present details of DIRECT in Section 2. Empirical results are shown in Section 3. We survey the related literature in Section 4, and conclude in Section 5. Proofs and extra results are provided in the supplementary material.

2 ProposedWork

We are given an imbalanced training dataset D = {(xi, yi)}, where each point i has a feature vector xi ∈ Rp and a class label y ∈ {+1,-1}. We assume, without loss of generality, that the positive class is the minority class. That is, if there are nlo positive points and nhi negative points in D, then nlo ≪nhi. We focus on the setting where the number of features p is large but nlo is small. For example, p = 105 and nlo ≤ 7 for the text classification example of Figure 1. We want a binary classifier with three properties:

• (P1) It should be robust, since estimation errors are unavoidable with small sample sizes.
• (P2) It should not need sampling, since we need many samples to model high-dimensional distributions, and such sampling takes time and makes results variable.
• (P3) It should be parameter-free, since tuning parameters by cross-validation is noisy with so few samples.

Our proposed classifier, called DIRECT (Distribution for Imbalanced data with Robust Estimation of Covariance Technique), achieves this by using a robust kernel density to model the minority class distribution. With an appropriate choice of loss function, we show that the expected loss under the robust density has a closed form. This simplifies the training of DIRECT. Next, we will discuss the robust density, the calculation of the expected loss, and the overall algorithm.

2.1 Robust Minority Class Distribution

To construct the robust distribution, we need statistics that we can reliably estimate even from a few samples. Highorder moments are unreliable because they are sensitive to the distribution's tail, from which we may not have enough samples. Even the sample covariance is unreliable for small nlo and high p. Formally, when nlo/p is fixed but nlo, p → ∞, the sample covariance does not converge to the population covariance matrix [Marcenko and Pastur, 1967]. Hence, our robust distribution uses only the sample mean and a robust covariance estimate.

Our robust covariance estimators are shrinkage estimators [Ledoit and Wolf, 2004; Ledoit and Wolf, 2012]. Given a minority-class data matrix Xlo ∈ Rnlo×p with the singular value decomposition Xlo = USV T , they estimate the covariance as Σlo = V S′V T +q·I. The diagonal matrix S′ contains min(nlo, p) entries (nlo ≪ p for us), and q > 0 is a scalar. Both S′ and q can be calculated optimally to minimize the expected estimation error of Σlo. Hence, unlike regularization, we do not need cross-validation to find the best parameters. Note that we do not explicitly construct Σlo, which has O(p2 ) entries. We only calculate V ∈ Rp×min(nlo,p) , S′ , and q.

Now, we use Σlo to construct a kernel density for the minority class. This places a smooth distribution (a "kernel") centered on each of the minority class points, and averages over them to get an overall density. Our choice for the kernel is against driven by robustness concerns. The kernel distribution should be the distribution with the greatest uncertainty (i.e., the maximum entropy) subject to zero mean (since it is centered on the points) and covariance Σlo. This is just the Gaussian distribution N(0,Σlo) [Cover and Thomas, 2006]. Using the Gaussian kernel, our robust density for the minority class is given by:

where xi is a point from the minority class (yi = +1), φ(.) is the N(0, 1) density, and (V, S′ , q) are discussed above.

We note that kernel density estimates also have a bandwidth parameter. For large p and small nlo, this bandwidth approaches 1 and can be ignored (see Eq. 4.14 and Table 4.1 of [Silverman, 1986]).

2.2 Model-Fitting

Consider a classifier with parameters θ and loss function ℓ(y, x; θ). We must train it using nlo points from the minority class and nhi from the majority class, with nlo ≪ nhi. For the majority class, nhi is large enough that the average loss is a good proxy for the test loss. But for the minority class, nlo is too small, and the average loss can be noisy. So we use the expected loss over the robust distribution (Eq. 1). Hence, we find the model parameters θ to minimize

We can approximate the second term by averaging the loss over samples drawn from p⋆lo (.). However, we can avoid this sampling step by choosing a loss whose expectation has a closed form. In this paper, we choose θ = (c,w) ∈ R×Rp and ℓ(y, x; θ = (c,w)) = max(0, 1 - y · (c +wT x)). In other words, given a feature vector x, our model predicts y = sign(c +wT x) and uses the hinge loss with unit margin to measure accuracy. This loss is convex in θ, so the objective of Eq. 3 is convex too. Furthermore, we can calculate the second term of Eq. 3 in closed form, as shown next (all proofs are deferred to the supplementary material).

Theorem 1.

Here, φ(·) and Φ(·) represent the pdf and cdf of a standard normal respectively.

For intuition, suppose t ≈ 0. Then the expected loss for point i from the positive class becomes si · Φ(si/t) + t · φ(si/t) ≈ si · 1si>0 = max(0, si), which is exactly the hinge loss for i. Thus, for t ≈ 0, we recover the empirical loss. As t increases, the loss increases, as shown below.

Corollary 1. The expected loss over the robust distribution (Eq. 4) is an increasing function of both si and t.

Thus, t = ‖Σ1/2 lo w‖ acts as a regularizer for w. But unlike standard regularization, this is not a norm of w, and we do not need cross-validation to select the regularization penalty. Using Theorem 1, Eq. 3 has a closed-form formula:

Eq. 5 is a convex problem, and we can use any off-the-shelf solver to minimize it. A significant speedup is provided by the following theorem.

Theorem 2. Let (w⋆, c) be the minimizer of Eq. 5. Then w⋆ lies in the subspace spanned by the nlo + nhi vectors {xi}.

Hence, when nlo + nhi ≪ p (as in our case), we can assume w⋆ = ∑i αixi and only search for the optimal α ∈ Rnlo+nhi . This reduces the search space for the convex solver from p dimensions to nlo + nhi dimensions.

2.3 Post-Processing

The process above yields a feature vector w⋆ and an intercept c to minimize the loss function of Eq. 3. However, our overall objective is classification accuracy over a balanced test set. So, in a post-processing step, we adjust the intercept for this objective. In particular, we minimize the expected misclassification:min

Algorithm 1 DIRECT

• 1: function DIRECT(Training set Xlo ∈ Rnlo×p ,Xhi ∈ Rnhi×p )
• 2: Σlo ← robust covariance for minority class (Eq. 2)
• 3: (w⋆, c) ←minimize the convex loss of Eq. 5
• 4: c⋆ ← minimize misclassification loss of Eq. 6
• 5: return (w⋆, c⋆)
• 6: end function

Any off-the-shelf single-variable optimizer can be used to find the minimizer c⋆. Algorithm 1 shows the pseudocode for training DIRECT. This returns the optimal parameters (w⋆, c⋆). Now, given a test point x, DIRECT predicts ˆ y = sign(c⋆ + xT w⋆).

Matching desired properties. DIRECT achieves robustness to limited data (property (P1)) by only using reliable statistics such as the optimal shrinkage covariance. The resulting robust distribution (Eq. 1) reflects these statistics, but also the uncertainty about other moments. DIRECT avoids sampling (property (P2)) by using a closed-form formula for the expected loss under the robust distribution (Theorem 1). This speeds up model-fitting and also avoids the variability of sampling. Finally, DIRECT's only parameters are the shrinkage parameters for the robust covariance Σlo (Eq. 2). We can compute the optimal shrinkage from the data itself, without cross-validation. Thus, we achieve property (P3).

Remark 1. We note that any complex classifier can be trained within our robust framework via sampling. In other words, we can approximate the expected loss (Eq. 3) by sampling from the robust distribution p⋆lo , and use this approximation for parameter-fitting. This retains the robustness to limited data, but loses the speed of DIRECT. Another alternative is available if we want a classifier based on functions of x (say, a finite number of interaction terms). Then, we can construct new feature vectors ˜xi from functions of xi, and use DIRECT on this modified dataset.

3 Experiments

We will discuss three questions: (a) how accurate is DIRECT, (b) how does the accuracy vary with the imbalance ratio and the minority class sample size, and (c) how fast is DIRECT?

Experimental setup. We ran experiments on six text, two image, and one medical dataset, along with 20 UCI datasets (Table 1). In each experiment, we created a training set with nlo positive and nhi negative samples that were randomly chosen from the dataset. All remaining datapoints were used for testing. We ran experiments on 509 unique (dataset, class, nlo, nhi) combinations, each being repeated 30 times.

Note that our focus is on the limited data binary classification problem (as motivated by Figure 1). So, we used nlo ≤ 50 for almost all experiments. Also, we do not consider multiclass classification or specialized feature construction methods. Multiclass learning can be implemented via repeated one-versus-all classification using DIRECT. Specialized features may not be available (e.g., for our medical dataset); when available, they can be used as inputs to DIRECT. Hence, we do not pursue these topics in this paper. The supplementary material has more details about our datasets.

Accuracymetric. Our comparisonmetric is the area under the precision-recall curve (AUPRC), which is the standard accuracy metric for imbalanced binary classification [Davis and Goadrich, 2006]. The AUPRC scores for all 509 experiments are presented in the supplementary material. In this section, we report the lift in AUPRC of DIRECT over competing methods. The lift provides an aggregate measure of the outperformance of DIRECT across all classes for a dataset. The supplementary material also shows alternate metrics such as the balanced accuracy and the G-mean, which show similar patterns as the AUPRC results.

Competing methods. Among data balancing methods, we consider SMOTE [Chawla et al., 2002], ADASYN [He et al., 2008], Borderline-SMOTE [Han et al., 2005], and oversampling with smoothed bootstraps (ROSE) [Menardi and Torelli, 2014]. These are coupled with a linear SVM so that the number of parameters is the same as in DIRECT. Among ensemble methods, we show results using balanced random forests, balanced boosting (RUSBoost), SMOTE with Gradient Boosting (XGBoost), and balanced bagged decision trees [Chen et al., 2004; Seiffert et al., 2010]. We also show results against a cost-sensitive SVM, an imbalanceaware margin classifier (LDAM-RDW) [Cao et al., 2019], and vanilla SVM (SVC).

Cost-sensitive deep learning [Chung et al., 2016] underperformed other baselines even after tuning hyperparameters on the test sets, so we do not show those results. [Cunha et al., 2021] make similar observations about deep learning for limited data. Our code will be made publicly available after incorporating comments from the reviewers.

3.1 Accuracy Comparison

Table 2 shows the trimmed mean of DIRECT's lift in AUPRC. The trimmed statistics are robust to noise due to the limited sample sizes. Detailed results for all 509 problem settings are in the supplementary material.

We see that DIRECT is 5x - 7x better than all SMOTElike methods on the Tumors dataset. For example, with nlo = 5, the median AUPRC over all classes is 0.59 for DIRECT but only 0.07 (close to random) for the SMOTE-based methods. On other datasets, with nlo ≤ 20, DIRECT typically outperforms SMOTE-like methods. When nlo = 50, DIRECT is better for News Search and the two MNIST datasets.

Overall, DIRECT outperforms SMOTE-based methods significantly on several datasets and is comparable otherwise.

DIRECT is 77-145% better than bagging, 50-74% better than random forests, and 30-210% better than boosting for certain settings. The most significant differences are for Arxiv, MNIST (digits), Recipes, and Tumors. The closest competitor is SMOTE with gradient boosting, which is better than DIRECT for 20Newsgroups but is comparable or significantly worse on other datasets (e.g., DIRECT is 180%- 215% better on Dell).

DIRECT is 3x-7x better than cost-sensitive SVMs and 75 - 80% better than ROSE on the Tumors dataset. The closest competitor of DIRECT is ROSE-SVM. But, in most cases, DIRECT is comparable or better than it. DIRECT outperforms LDAM-RDW, showing that for small nlo, the robustness to limited data is more important than margin adaptation. DIRECT also outperforms SVC by a wide margin.

Figure 2 shows the distribution of the lift, instead of just the trimmed mean. It confirms that DIRECT can be much better than other methods but is rarely much worse. The most significant outperformance is for small nlo, where the robustness of DIRECT has the most impact.

3.2 Varying the Training Size

In practical applications such as document tagging (Figure 1), the minority class sample size nlo is often very limited. Our previous experiments focused on such settings. DIRECT's success resulted from its robustness to limited data. Now, we investigate further the relative impact of limited data and the imbalance ratio on DIRECT's accuracy.

Figure 3a shows how DIRECT's AUPRC varies with the size of the training data for the News Search dataset. When nlo = 5, the AUPRC increases only 38% even as nhi increases by a factor of 40. Thus, AUPRC improves in spite of increasing imbalance. But when nhi = 1000, the AUPRC increases quickly with nlo before flattening at nlo = 100. Thus, increasing nlo from 5 to 100 provides a significant benefit, but further reduction in imbalance does not help. The greatest gains occur when both nlo and nhi increase in lockstep.

In our problem setting, the minority class has extreme data scarcity. Here, these results suggest that the limited sample size is the main problem, and not the imbalance. Even a few more minority class samples helps accuracy, but more majority class samples have low marginal benefit. This shows the utility of DIRECT's robustness to limited data.

3.3 Wall-Clock Time

Figure 3b show the wall-clock time for training on the News Search dataset. We observe:

• By avoiding sampling, DIRECT is significantly faster than ROSE and SMOTE with XGBoost, both of which generate new samples for the minority class.
• By being parameter-free, DIRECT is faster than even SVC, which needs cross-validation for choosing the regularization parameter.

DIRECT also outperforms both in terms of accuracy. In testing, DIRECT was 30x faster than balanced bagging and boosting classifiers. This is because DIRECT only calculates a lin-

(a) Change in AUPRC with varying sample size.

(b) Wall-clock times with varying sample size.

Figure 3: Effect of sample sizes on AUPRC and wall-clock time.

ear function for a given test point, while ensemble methods need more complex computations.

4 RelatedWork

We can divide prior work on imbalanced classification into three groups: data modification, ensemble methods, and other techniques. We also discuss robust approaches.

Data modification. SMOTE and its variants create a balanced dataset by generating synthetic samples [Chawla et al., 2002; Han et al., 2005; He et al., 2008]. However, SMOTE's synthetic points always lie within the convex hull of the minority class points. For limited data, these may only lie in a subspace of the feature space. Also, nearest neighbors are costly to compute and lose their intuitive meaning in high dimensions.

ROSE generates samples using a Gaussian kernel with a diagonal covariance [Menardi and Torelli, 2014]. Unlike DIRECT, a diagonal covariance ignores feature correlations. Further, given limited training data, the diagonal covariance may be noisy. Finally, ROSE needs sampling from the highdimensional kernel, unlike DIRECT.

Ensemble methods. These methods combine results from multiple models trained on balanced versions of the imbalanced data. On these balanced datasets, one can train random forests, boosted decision trees, and others [Chen et al., 2004; Seiffert et al., 2010]. But when the training data is limited but the number of features is high, ensemble methods can underperform, as we show empirically.

Cost-sensitive methods. There is work on modifying existing algorithms to allow for different misclassification costs [Chung et al., 2016] or class-specific margins [Cao et al., 2019]. However, cost-sensitive methods (including deep learning) underperform for limited datasets [Cunha et al., 2021]. Recent works also consider semi-supervised imbalanced classification [Yang and Xu, 2020] or use extra supervision [Meng et al., 2018]. We leave the extension of DIRECT to these settings for future work.

Robust algorithms. Robust methods consider uncertainty sets for uncertain or perturbed data or data distributions [Xu et al., 2009; Tzelepis et al., 2018; Mohajerin Esfahani and Kuhn, 2018]. But none of them consider data as limited as ours. Chakrabarti [2021] provides a theoretical justification for similar robust classifiers, but does not account for class imbalance.

5 Conclusions

We considered binary classification problems with imbalanced classes, few samples from the minority class, and high dimensionality. We devised a new algorithm called DIRECT for this extreme setting. DIRECT is simple, parameter-free, and robust to estimation error. In contrast to many existing methods, DIRECT does not need to generate samples. Instead, DIRECT incorporates a smooth estimate of the minority class distribution directly in its loss function. The estimated distribution accounts for correlated features and is robust to estimation error. DIRECT's loss function is convex and easily optimized via off-the-shelf solvers.

We empirically validated DIRECT on several real-world classification tasks on document, image, and gene microarray datasets. DIRECT is often significantly better than existing methods and rarely worse. DIRECT is up to 5x - 7x better than SMOTE-like methods, 30 - 200% better than ensemble methods, 3x - 7x better than cost-sensitive SVMs. The most significant improvements often occur for the smallest sample sizes. That is because DIRECT's robustness to estimation error is most helpful in these settings.

One direction for future work is to extend DIRECT from binary to multiclass and multilabel classification. Since individual one-versus-all classifiers may have different accuracies, we need to calibrate them before combining them. Another is to leverage sparse feature vectors, such as in document classification. Finally, one can extend DIRECT to complex classifiers, e.g., by sampling from the smoothed distribution. This may be useful when there is enough data for the minority class.