Online Harmonizing Gradient Descent for Imbalanced Data Streams One-Pass Classification

1 Introduction

Many real-world applications require learning models to quickly react to and learn from rapidly growing data, such as ad placement [Varnali, 2021], social media analysis [Zhou et al., 2020], intrusion detection [Sovilj et al., 2020] and industrial fault diagnosis [Zhou et al., 2022]. Mining data streams thus attracts the attention of intensive research, and a family of techniques called online learning has emerged. Online learning is advantageous for its efficiency and effectiveness, which can make a decision after observing an instance and then further update based on the revealed true label. It provides an opportunity to solve many practical applications where data arrives sequentially while decisions need to be made immediately. Many online learning algorithms have been actively proposed in the literature, including Online Gradient Descent (OGD) [Zinkevich, 2003], Passive Aggressive (PA) [Crammer et al., 2006] Confidence Weighted Classifier [Dredze et al., 2008] etc.

Despite extensive online learning algorithms, most methods are inappropriate to deal with skew-distributed classes because they favor samples from majority classes and, accordingly make wrong decisions for those from minority classes. This is unacceptable when misclassifying the minority class samples may lead to severe problems, such as fault diagnosis, disease diagnosis, etc. In this situation, combining both issues of online learning and class imbalance learning, new challenges and research topics arise.

Various approaches have been proposed to deal with the class imbalance problem. The two most prominent directions include resampling and reweighting. Resampling ensures an equal number of instances within a data chunk by reducing the number of instances frommajority classes (undersampling), generating new instances of minority classes (over-sampling) or both [Wang and Pineau, 2016], [Lu et al., 2019], [Bernardo et al., 2020], [Klikowski and Wo´zniak, 2022]. Reweighting amends the importance of classes by assigning either uneven costs [Wang et al., 2013a], [Zhao et al., 2018], [Zhang et al., 2019], [Loezer et al., 2020] or imbalance ratio [Yu et al., 2018]. Combination of resampling and reweighting approaches is also among the most popular methods to solve this problem [Wang and Pineau, 2016], [Zyblewski et al., 2021]. While being intuitive and working reasonably well, an important thing is that these methods inevitably involve heuristic data buffer design, sampling rate selection or empirical cost determination, limiting their easy implementation to practical applications.

Different from the underlying assumptions of previous works on instance number inequality or cost asymmetry, this paper assumes that the class imbalance can be implied by the imbalance of the gradient. We analyze the validity of this assumption experimentally in the overall online learning stage. Further, the online harmonizing gradient descent (OHGD) is proposed, which attempts to balance the magnitude of gradients that occur by different classes. With ensuring the gradient balance, it avoids the bias of the proposed method in favor of majority classes and achieves balanced online learning. Specifically, OHGD requires no data-buffer, extra parameters, nor prior knowledge. It also handles imbalanced data streams the same way that it would handle balanced data streams, which facilitates its easy implementation. We analyze the theoretical regret bound made by the OHGD and extensively examine its empirical performance on several benchmarks, compared with state-of-the-art online imbalance learning algorithms. We elaborate on our contributions below.

• Motivation. We assume that the class imbalance can be implied by the imbalance of gradients and analyze the validity of this assumption experimentally.
• Method. We propose an easy-to-implement online harmonizing gradient descent (OHGD) method for imbalanced data stream one-pass classification.
• Theoretical guarantee. We prove that OHGD enjoys a satisfying sub-linear regret bound on top of a few common and mild assumptions.
• Experimental results. Extensive experimental results demonstrate the high efficiency and effectiveness of OHGD 1 .

The rest of this paper is organized as follows. Section 2 briefs related works on class imbalance and online learning. Section 3 formulates the problem, describes the proposed methods and analyzes the theoretical bounds. Extensive experimental results and discussion are given in Section 4. Finally, Section 5 concludes this paper.

2 RelatedWork

This section provides a brief overview of related works on online learning and class imbalance learning.

2.1 Online Learning

In the setting of online learning, data are sequentially received and models need to commit to an immediate decision at each round. Then the decision model will suffer a loss and the loss is used to update model parameters based on some criterion. Many online learning problems can be formulated as an Online Convex Optimization task [Hoi et al., 2021]. In the following, we introduce its basics and one of the most popular algorithms, Online Gradient Descent.

Let xt ∈ ℜd denotes the t-th sample whose true label is denoted as yt ∈ {-1,+1} in an infinite data stream D. Considering a classifier in a convex set wt ∈ W at the tround, it makes a prediction on sample xt as ˆ yt =wtxt. The performance is usually measured by a convex loss function Lt(wt|xt, yt), such as hinge loss or logistic loss, which are surrogate losses for 0-1 error. The overall goal is to minimize the regret between the cumulative mistake of wt and that of one best fixed decision w∗ :

One of the most well-known online learning algorithms would be the Online Gradient Descent, an online version of Stochastic Gradient Descent in convex optimization. OGD

1 More information about the codes and supplementary can be found in https://github.com/Kan9594/OHGD.

takes a step from the current model toward the steepest descent direction of the current loss function based on the loss on an instance xt. This gives wt+1 = wt - λ∇Lt(wt), where wt ∈ W is the model in the t-th round and λ is the learning rate. In [Zinkevich, 2003], OGD achieves sublinear regret O(√T ) for any data stream D on convex loss functions with bounded gradients.

2.2 Learning with Imbalanced Data

Many approaches in the literature have been proposed to deal with the class imbalance problem in the setting of batch learning. The approaches can be roughly categorized into three categories: data-level [Chawla et al., 2002], [Razavi-Far et al., 2021], algorithm-level [Sun et al., 2007], [Zong et al., 2013], [Zhang et al., 2018], [Wang et al., 2021] as well as hybrid methods [Galar et al., 2011]. However, learning imbalanced data streams is more challenging. Unlike batch learning, which assumes all training data is available in memory, online learning assumes data is observed sequentially and rapidly updated. Many efforts design data buffers to store continuous data. Once a full buffer is formed, they treat each of them as an imbalance dataset and many conventional data preprocessing methods can be adopted to modify the distribution, such as online SMOTE [Wang and Pineau, 2016], [Lu et al., 2019], [Bernardo et al., 2020], [Klikowski and Wo´zniak, 2022]. An even stricter scenario is that learning paradigms need to respond immediately to an instance and discard it, i.e. one-pass classification. In this situation, re-weighting or costsensitive strategy [Wang et al., 2013a], [Zhao et al., 2018], [Zhang et al., 2019], [Loezer et al., 2020] could be much more feasible since it can deal with instances one by one, requiring no data buffer. Some attempts at ensemble learning also achieve convincing performance, which re-samples instances sequentially [Wang and Pineau, 2016], [Wang et al., 2013b], [Wang et al., 2014]. Unfortunately, these works inevitably involve heuristic weighting parameter design, prior cost determination or sampling rate selection, which limits their generalization on many practical applications. With improper weighting parameters, such a strategy may also cause a reverse bias towards the minority class.

3 Methodology

This section presents the core idea of gradient reweighting for imbalanced online learning. We first start with the problem formulation of online learning on imbalanced data streams, and then propose a gradient reweighting strategy to solve the gradient asymmetry between the majority class and the minority one. We also provide the theoretical analysis on the soundness of the proposed strategy.

3.1 ProblemFormulation

The Eq.1 indicates that each sample in the data stream D contributes equally to the regret of the model. This symmetrical treatment may result in bias toward samples in majority classes (labeled as -1) which incur larger accumulative loss values than those of samples from minority classes (labeled as +1). Many works attempt to resample datasets or assign larger weights to minority samples and thus maintain a more balanced distribution. Instead, this paper claims that the imbalance of examples can be implied by the imbalance of gradient and tries to sustain the balance by keeping the harmonizing gradient magnitude accumulated by diverse classes.

In many online learning methods, it is common to update model parameters by iteratively taking a gradient step. In its fundamental form, parameters at t-th iteration are forced to move towards the steepest descent direction of the loss at wt:

where λt is the learning rate. We then define the gradient imbalance in the following.

Definition 1. Denoting the gradient norm of the t-th sample as Gt = ‖∇Lt(wt|xt, yt)‖2 , the accumulative gradient norm of negative samples and positive samples before t-th round is Gn = ∑ti∈I(yi=-1) ‖∇Li(wi|xi, yi)‖2 and Gp = ∑ti∈I(yi=+1) ‖∇Li(wi|xi, yi)‖2 , respectively. In this situation, the gradient imbalance (GI) can be measured by:

Clearly, a larger GI value denotes a more heavily imbalanced data stream. I(yi=-1) denotes the dataset where the label of the i-th sample is negative. In the following, we use I(-) for simplicity.

Based on the above definition, Fig.1 shows the gradient imbalance when applying OGD to the ijcnn1 dataset. We varied the imbalance ratio (IR) from 1 to 39. As we can see, the positive gradient norms are overwhelmed by the negative gradient norms at the very beginning of the learning procedure. This implies that the OGD performs a greater number of gradient descent actions guided by negative samples, resulting in overfitting to the majority class. Moreover, a larger imbalance ratio would result in a higher gradient imbalance. In contrast, when the dataset is in a balanced distribution (the blue line), the gradient imbalance fluctuates around 1.

In this situation, this paper attempts to harmonize the gradient imbalance during the learning procedure, corresponding to a weighted gradient descent step:

Such that

Compared with the conventional OGD in Fig.1b, this strategy (Online Harmonizing Gradient Descent, OHGD) encourages the gradient ratio to fluctuate around 1 (red line). This means that each class contributes equally to the learning model.

3.2 Online Harmonized Gradient Descent

We first define the response of a learning model to t-th instance as:

It reflects the expected gradient descent magnitude when a model learns the instance xt. The reason behind adding the loss value factor is the different contribution of each sample. Thus, we reshape the gradient to down-weight/up-weight easy/difficult instances, putting more focus on the hard, misclassified instances.

Then the weight αt for the gradient at this iteration can be formulated by:

where the parameter ρt = N tn N tp is the imbalance ratio of the negative to positive instance number at the t-th iteration. Applying the weights to Eq.4, the harmonized gradients become:

Finally, we summarize the pseudo-code of the proposed OHGD in Algorithm.1. This paper adopts the widely used hinge loss. It is easy to observe that the time complexity of OHGD is O(Td), which scales linearly with the number T of instances in the data stream D as well as the dimensionality d of instances.

Remarks. In some real-world online cases, the imbalance ratio can shift over time. To dynamical capture the imbalance ratio, we can use exponential smoothing ρt = ηρt-1 + (1 - λ)I(-), where η ∈ (0, 1) is a pre-defined time decay factor. By doing so, the older data affect the class ratio less with time, so that the model can follow the imbalance change quickly.

3.3 Theoretical Justification

In this section, we provide the theoretical analysis that gives the sublinear regret bound achieved by OHGD. To ease our discussion, we denoteMas the prediction error indexes set: M = {t|L(wt) > 0}. Similarly, we denote M tp and M tn as Algorithm 1 The Proposed Online Harmonized Gradient Descent Algorithms.

Input: learning rate λt;

• 1: Initialize α0 = 1
• 2: for t = 1, · · · , T do
• 3: Receive an instance: xt ∈ ℜd ;
• 4: Predict ̂ yt ;
• 5: Receive the true label yt;

6: Calculate the weight αt using Eq.7;

• 7: Incur the loss Lt(wt|xt, yt)
• 8: if Lt > 0 then

9: Update the model using Eq.8.

• 10: end if
• 11: end for

Output: wT+1;

the number of misclassified positive and negative instances before t-th round, respectively. M T = |M| =M T p +M T n is the total number of misclassified instances in data stream D. We begin the analysis with the following assumptions.

Assumption 1. Let (x1, y1), (x2, y2), · · · , (xT , yT ) be the data stream D, where yi ∈ {-1, +1} and ‖xi‖ ≤ 1 for all t. The imbalance ratio is stationary ρ = N T n N T p ≥ 1.

Assumption 2. The decision domain W contains the origin 0, and its diameter is bounded by D, i.e.,

Corollary 1. Under these assumptions, for the hinge loss L(wi) = max(0, 1 - yiwixi), we have 0 ≤ L(wi) ≤ (D + 1).

We also provide the following lemma that would facilitate the theoretical analysis.

Lemma 1. The sum of the re-weighting parameter αt has an upper bound:

The proof details of Lemma 1 can be found in the supplementary.

Theorem 1. By adaptively setting λt = √ D+1 ρMtn+Mtp , for any w∗ ∈ ℜd , the following regret bound holds for the proposed

OHGD on the data stream D:

where the ϵ denotes the minimum of αt.

Proof. Due to the convexity of the loss function, the following inequality holds for any w:

Since we defined the harmonized gradient descent updating wt+1 = wt - αtλt∇Lt(wt) in Eq.5, then we have:

Accordingly,

By summing over T and using Eq.12, we can get:

Let ϵ denotes the minimum of αt. Since ‖wt‖2 < D and ‖∇Lt‖ ≤ 1, we have:

Individually analyzing the two terms:

For the second term:

Combining Eq.17 and Eq.18,we get the regret bound:

In this setting, OHGD achieves an O(√T) regret bound. This completes the proof.

Remarks. The proposed OHGD enjoys an O(√T) performance by setting an adaptive learning rate. It can be influenced by the weighting parameter α. To avoid αt = 0, one can initialize the response R0 = 1 and set ρ0 = Nn/Np = 1/1 at the beginning. In terms of the implementation, we can force αt to be in [10-2 , 102 ] in order to achieve the satisfied sub-linear regret bound.

Regarding easy implementation, we provide another choice for selecting the learning rate, and the algorithm performs well.

Theorem 2. By dynamically setting λt = 1/√t, for any w∗ ∈ ℜd , the following regret bound holds for the proposed OHGD on the data stream D:

where the ϵ denotes the minimum of αt.

Proof. Recall Eq.16:

In this setting, OHGD achieves an O(√T) regret bound. This completes the proof.

Remarks. Similar to the Theorem.1, the proposed OHGD enjoys a satisfiedO(√T) regret when we set λt = 1/√t. Setting the learning rate λt as a constant cannot promise a sub-linear regret but it can also achieve satisfied classification performance as some previous works discussed [Wang et al., 2013a]. More detailed derivation for Theorems 1-2 can be found in our supplementary.

Note that although the imbalance ratio ρ is assumed to be constant in these theorems, it is easy to infer that the regret is also sub-linear even if ρt changes, as long as ρt has an upper bound.

4 Experimental Results

In this section, we evaluate the performance of the proposed OHGD for imbalanced data streams, using public benchmark datasets. The implementations of this work can be found in https://github.com/Kan9594/OHGD.

4.1 Settings

Datasets. Twenty-four datasets from the UCI repository and KEEL with different imbalance ratios were selected as the test rigs for performance evaluation. Table.1 summarizes the details of the selected datasets, including the number of instances (#Instance), the dimensionality of features (#Fea) as well as the imbalance ratio (IR = #Majority/#Minority). More details can be found in the UCI 2 and KEEL 3 websites.

2 http://archive.ics.uci.edu/ml/index.php

3 https://sci2s.ugr.es/keel/datasets.php

The TestedMethods. We compared our OHGD algorithms with various online learning algorithms for imbalanced data streams, including cost-sensitive online learning [Wang et al., 2013a] (CSOGD), cost-sensitive online ensemble learning [Wang and Pineau, 2016] [Du et al., 2021] (onlineAdaC2, onlineCSB2, onlineUnderOverBagging, onlineRUSBoost, onlineEffectiveBagging) and resampling based online ensemble learning [Wang et al., 2013b], [Wang et al., 2014] (onlineUnderBagging, onlineOverBagging, onlineWeightedUnderBagging, onlineWeightedOverBagging). As the purpose of the experiments is to make fair comparisons among different online algorithms, we chose OGD as the base learners of ensemble learning. The number of base learners M was set as 10. The learning rate ηt was set as 1/√t. Other parameters were set as the original work suggested. Note that our method does not require any additional parameter settings for imbalance learning. The supplementary summarizes the characteristics of different methods.

Although our method focuses on one-pass data stream learning, we still compared it with some chunk based methods, including HDWE [Grzyb et al., 2021] and KNORAE2 [Zyblewski et al., 2021]. The number of base learners M was set as 10 and other parameters were set as the original works suggested.

Metrics. As the data distributions are highly skewed, we adopted AUC value, G-MEANS and F1 Score to evaluate the performance of each algorithm, instead of accuracy. Each algorithm on each dataset was conducted 10 times, and we reported its mean and standard deviation.

4.2 Parameter Sensitivity

We first show that the proposed algorithm achieves consistently satisfying classification performance without any additional parameter tuning. Fig.2 illustrates the performance variation of algorithms under different parameter settings. Due to the length limitation, we only provide the performance on the dataset ijcnn1 in terms of AUC. More results can be found in the supplementary. Since no hyper-parameters are required in OHGD, its performance curves are horizontal lines. From these figures, we can observe that the performance of competitors depends heavily on the selection of hyper-parameters. Although they prevail over the proposed algorithm in some cases, it is quite tricky to determine precise parameters for different practical situations. On the contrary, OHGD is elegantly formulated without many hyperparameters to tune, allowing for easy implementation in practical applications.

4.3 Performance Comparison

Applying all algorithms for classifying all datasets in terms of AUC, G-mean and F1 score, we provide the performance comparison of different methods. Here, we present the results of the a8a dataset, and additional results can be found in the Supplementary. We calculate and summarize the average ranks over all three performance metrics in Fig.3. As we can observe, the proposed OHGD is ranked as the best method on average over all datasets since it outperforms other competitors in terms of each performance measure In order to provide a certain reassurance and validate the results and analysis, we employ a non-parametric statistical test, the Wilcoxon signed-rank test, to examine whether the proposed method is significantly better than competitors. The results are shown with stars on the algorithm names in Fig.3. Particularly, the star over the name indicates that the performance of OHGD significantly differs from the corresponding methods at the significance level α = 0.05. As we can see, in most cases, OHGD significantly outperforms other competitors in terms of AUC, F-measure and G-mean. Similar observations also can be found in the comparisons with the chunk-based methods (Figure.(4)).

4.4 Average Accumulative Loss Analysis

We proceed to analyze the theoretical performance of OHGD in this sub-section. Particularly, we present the Average Accumulative Loss to show the regret trends:

Figure.5 illustrates the AvgLoss trends of OHGD on the datasets a8a and ijcnn. We observe that all the curves decrease rapidly and generally converge to a constant, which shows agreement with our O(√T ) regret convergence expectations in the Theorem.2.

4.5 Rationality of Gradient Imbalance

We also verify the rationality of our motivation in this paper, i.e. gradient imbalance. Recalling the defined gradient imbalance in Eq.3, to further measure it over the learning procedure, we modify it as GI Index (GII):

A smaller GII clearly indicates a more harmonizing gradient ratio over the online classification procedure. We report the rank of the GII obtained by one-pass algorithms in the Figure.6, as we did in the previous sections. Not surprisingly, the rank in terms of the GII generally agrees with those in terms of classification metrics, indicating that ensuring the gradient ratio can indeed improve learning performance under imbalanced data streams.

4.6 Time Efficiency

Table.3 provides the overall time cost of each algorithm on the 24 datasets. Generally speaking, the algorithms can be divided into two groups: one that includes a single classifier and the other that includes multiple classifiers. Not surprisingly, ensemble learning algorithms require more time for learning. This relates to two aspects. 1) Ensemble learning algorithms are required to update more classifiers when training a received instance. 2) Ensemble learning algorithms adopt a resampling strategy for imbalanced data streams and they may update an instance several times if this instance needs to be over-sampled. Compared with the ensemble learning methods, the re-weighting strategy (OHGD, CSOGD) is much more efficient because it only updates weighting parameters at each round. The OHGD costs slightly more computational time because it is required to calculate the gradient norm. However, it is still generally efficient.

5 Conclusion

Different from the previous assumptions on instance number imbalance or cost imbalance, this paper experimentally shows that the imbalance of instances can be implied by the imbalance of gradient. Then, we designed a weighted gradient descent step to harmonize the gradient imbalance and proposed the Online Harmonizing Gradient Descent, a solution to the class imbalance problem in the setting of online learning. The OHGD achieves satisfied O(√T ) regret bound with the time horizon. The proposed method was examined in 24 public datasets and compared with several SOTA methods. The encouraging experimental results show the competitive performance on online imbalance learning. Future work could extend the current model to multiclass problems.