Threshold Moving for Online Class Imbalance Learning with Dynamic Evolutionary Cost Vector
Authors: Peijia Qin
Shuxian Li
Xiaoqun Liu
Zubin Zheng
Siang Yew Chong
Venue: Accepted by TMLR ()

Abstract: Existing online class imbalance learning methods fail to achieve optimal performance because their assumptions about enhancing minority classes are hard-coded in model parameters. To learn the model for the performance measure directly instead of using heuristics, we introduce a novel framework based on a dynamic EA called Online Evolutionary Cost Vector (OECV). By bringing the threshold moving method from the cost-sensitive learning paradigm and viewing the cost vector as a hyperparameter, our method transforms the online class imbalance issue into a bi-level optimization problem. The lower layer utilizes a base online classifier for rough prediction, and the upper layer refines the prediction using a threshold moving cost vector learned via a dynamic evolutionary algorithm (EA). OECV benefits from both the efficiency of online learning methods and the high performance of EA, as demonstrated in empirical studies against state-of-the-art methods on thirty datasets. Additionally, we show the effectiveness of the EA component in the ablation study by comparing OECV to its two variants, OECV-n and OECV-ea, respectively. This work reveals the superiority of incorporating EA into online imbalance classification tasks, while its potential extends beyond the scope of the class imbalance setting and warrants future research attention. We release our code for future research.

Published in Transactions on Machine Learning Research (09/2024)
Threshold Moving for Online Class Imbalance Learning with Dynamic Evolutionary Cost Vector
Peijia Qin
ginp22021 @mail.sustehhhcom edu.cc
Deportment of Computer Science and Engineering,
Southern University of Science and Technology, Shenzhen, China
Shuxian
lisn@maill sustech. edu.cc
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China Department of Computer Science, Hong Kong Baplist Universily, Hong Kong SAR, China
Xiaoqun Liu
Liurq2021 @mmail.sstech.edde edu.ccm
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Zubin Zheng
thengab2021@maill.cc sustech. edu.cn
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Siang Yew Chong
chongsy@sussech.eeue edu.cn
Deportment of Computer Science and Engineering, Southern Universily of Science and Technology, Shenzhen, China
Reviewed OpenReview: https: openreview. net/ pet/formm? id= EIPnUofed9
Abstract
Existing online class imbalance learning methods fail to achieve optimal performance because their assumptions about enhancing minority classes are hard-coded in model parameters. To learn the model for the performance mcasure directly instead of using hcuristics, we introduce novel framework based on dynamic EA called Online Evolutionary Cost Vector (ORCV). By bringing the threshold moving method from the cost-sensitive learning paradigm and viewing the cost vector a hyperparameter, online class imbalance issue into bi-level optimization problem. The lower layer utilizes base online classifier for rough prediction, and the upper layer refines the prediction using a threshold moving cost vector learned via a dynamic evolutionary algorithm (EA). OECV benefits from both the efficiency online learning methods and the high performance of EA, as demonstrated in empirical studies against state-of- state-of-the-arr methods on thirty datasets. Additionally, show the effectiveness of the EA component in the ablation study by comparing OECV to its two variants, OECV-n and OECV-ea, respectively. This work reveals the superiority of incorporating EA into online imbalance classification tasks, while its potential extends beyond the scope of the class imbalance setting and warrants future rescarch attention. We relcase our code for future research.
method transforms the
1 Introduction
Online learning from streaming data is common in real-world applications, facing more challenges than oflline learning due to limited time and memory resources. Online class imbalance learning involves scenarios
https///ghhaabomm//a/aeee///

---

Published in Transactions on Machine Learning Research (09/2024)
where minority classes have notably fewer samples than the majority classes, which can detrimentally affect predictive performance, particularly for minority classes. Current efforts fall into three categories: data-level, algorithm-level, and ensemble approaches. Data-level methods use oversampling and undersampling to rebalance the datasets. Ensemble methods commonly work together with data-level algorithms by randomly resampling incoming data points for each base learner. Algorithm-level approaches react differently to samples from different classes, addressing the tendency to neglect the minority classes.
While designed differently, the three types of methodology all focus on how to efficiently utilize class imbalance information (e.g., imbalance ratio and data distribution) to handle the imbalance issue. However, to our knowledge, they all rely on assumptions about the expected enhancement level for minority classes, which are ad hoc and hard-coded in model parameters. For instance, cost-sensitive algorithms,, one kind of algorithm- level approach, assign different costs for misclassifying classes based on the class size or performance. But determining optimal costs remains challenging (Liu & Zhou, 2010). In this article, we aim to explore how to achieve optimality concerning any given performance metric directly without making ad hoc assumptions. This problem can extend beyond the scope of class imbalance, but we focus on an imbalanced learning setting for simplicity. Gradient- based optimization methods become impractical if we set the non-differentiable evaluation metric as objective. Unfortunately, in fact, a wide range of metrics are non-diffcrentiable since they require form of step loss function (e.g., counting the number of true positives), which is intractable. This includes accuracy, precision, recall, F1 score, and other comprehensive metrics such as G-mean and balanced accuracy. In an online setting, corresponding prequential evaluation Gama et al. (2014) of the above metrics is used, while the nonfiiffernntiabblity remains. Therefore, we focus on gradient-free optimization methods in this work, particularly the family of EAs (EAs). EAS have been widely studied for classification tasks such genetic programming (Espejo et al., 2009), learning classifier systems (Sigaud & Wilson, 2007), and cvolution of neural networks (Rocha et al., 2007). Besides, recent studies have attempted to leverage EA to assist conventional algorithms in offline class imbalance learning problems (Pei et al., 2023). However, applying EAS to online class imbalance learning remains unexplored and challenging due to time and space constraints in streaming learning. More specifically, evolving classifiers on a large scale and accessing the entire dataset are impossible. Besides, the dynamic enviromment of concept. drift may exist compared to offline learning. To this end, we have to examine a fundamental question: How can we create an online learner that combines two essential traits? That is, it should update fast under dynamic environment like cxisting online models while also learning efficiently with non-differentiable objectives similar to EAs.
We propose a novel framework named Online Evolutionary Cost Vector (OECV) to answer this question. OECV is conceptualizod as a bi-level optimization problem, with a probabilistic online classifier in the lower layer and a light cost vector in the upper layer. The classifier extracts useful information from data to provide a rough prediction while the cost vector refines the decision boundary. In the case of concept drift, especially the prior drift where class size changes, dynamic EA is applied to track optimal cost vectors using recent samples contained in fixed-size buffer. The most crucial difference between our dynamic EA and traditional EA is that it can track the optimal cost vector in a non-stationary environment by maintaining population diversity instcad of converging to a certain solution. The computation cost of evolution is drastically reduced since the cost vector to be optimized is light (proportional to the number of classes). In this way, our approach can learn with non-differentiable objectives under dynamic environments and update in a few computation efforts.
The motivation for formulating OECV as bi-level architecture is highly inspired by the threshold moving method (Kukar et al., 1998; Zhou & Liu, 2005; Sheng & Ling, 2006; Voigt et al., 2014; Hancock et al., 2022) from the paradigm of cost-sensitive learning. The gist of the threshold moving is weighting the probabilistic prediction by the cost vector, which contains the relative cost of misclassifying each class. While the cost vector used in our method acts the same way as that in threshold moving methods, it is usually predefined in the context of cost-sensitive learning. The key point in understanding our motivation is viewing the cost vector as set of hyperparameters in a class imbalance setting. This would interpret OECV as an online hyperparameter optimization (HPO) method built upon the threshold moving method. The straightforward way of sctting the hyperparameter in class imbalance learning is to set it inversely proportional to the class size, which, however, is not guaranteed to be an optimal solution. OECV, the other hand, manages to optimize the hyperparameters using a dynamic EA on the fly. In viewing OECV as an instance of HPO,
2

---

Published in Transactions on Machine Learning Research (09/2024)
its two levels correspond to searching parameters and hyperparameters separately, where parameters (base classifier) give rough prediction and hyperparameters (cost vector) refine the prediction. This effectively unifies online class imbalance learning and EAs within a cohesive framework.
The main contributions of this paper are listed as follows:
1. This study is the first to explore the problem of online class imbalance learning using an EA approach. The novel approach OECV unifies EA and online class imbalance learning within a bi-level optimization framework by applying a threshold moving cost vector, effectively addressing the performance-rcsource trade-off.
We present novel dynamic EA to learn the cost vector under potential concept drift adaptively and incorporate specific prior knowledge about class imbalance guide evolutionary learning.
3. We study the superiority and efficiency of OECV across thirty real-world datasets. Empirical results show its ability to significantly outperform state-of-the-art (SOTA) methods and confirm the effectiveness of the EA component.
The remainder of this article is organized as follows. Section presents related work. Section 3 details our proposed method. Experimental setup and results are discussed in Section 4. The paper is concluded in Scction 5.
2
Related Work
Our article related to online class imbalance learning, threshold moving methods and EA approaches for addressing class imbalance problems.
2.1
Online Class Imbalance Learning
Approaches to address online class imbalance problems can typically be classified into three categories, as mentioned in the introduction: data-level, algorithm-level, and ensemble-based methods.
2.1.1 Data-level Methods
Sampling methods work by oversampling and/or undersampling to rebalance data. SMOTE (Chawla et al., 2002) is a synthetic minority over-sampling technique used to balance the class distribution by gemerating new instances of the minority class. In online learning, it has been adopted in Online SMOTE (Wang & Pineau, 2016), which oversamples using training samples within a sliding window. C-SMOTE (Bernardo et al., 2020) addresses binary class imbalance by actively detecting concept drift via ADWIN (Bifet & Gavalda, 2007), change detector with sliding detection window, and applying SMOTE to the minority class in the sliding window. The ignorance of class distribution information results in their sub-optimal performance. OS-CCD based on classification contribution degree is proposed in Jiang et al. (2021), generating synthetic samples via classification contribution degree. SRE (Ren el al., 2019) introduces a select beleseion resampling mechanism to handle complex data distributions by considering recent sample properties. However, the resampling procedures of OS-CCD and SRE are both based on clustering, being sensitive to hyperparameters. While showing promising performance, these methods mostly targeted the binary class imbalance problem and needed to maintain sliding window to reserve relevant training samples, increasing the memory burden.
2.1.2 Algorithm-level Methods
Algorithm--lvel approaches work by modilying the training process. Qin et al. (2021) employs active learning to select the most important samples to train the classifier. Online one-class Support Vector Machines (Klikowski & Woćniak, 2020) is kind of ono-class classifier that creates a model for each class and achieves a one-class decomposition of multi-class problems. Other algorithm-level methods apply cost-sensitive learning methods, which assign varying costs for misclassifying classes belonging to different classes to reduce the
3

---

Published in Transactions on Machine Learning Research (09/2024)
dominating inftuence of majority classes, with the common assumption that minority classes incur higher costs. Ksieniewicz (2021) introduces Prior Imbalance Compensation (PIC) for batch learning of imbalanced data streams, which adjusts the decision made by the classifier using class prior probability to compensate for the minority classes. Yan et al. (2017) trains multiple classifiers with various cost matrices and makes predictions by adaptive ensembling. However, it is confined to binary class cases and challenging to extend to multi-class scenarios due to the exponential growth in the number of candidate cost matrices. Other related works (Wang et al., 2021; Ding et al., 2018; Qin et al., 2021) in cost-sensitive methods are based on the weighted extreme learning machine (WELM, Zong et al. (2013)), which is super efficient single hidden layer neural network with weighting strategy for class imbalance. WOS-ELM (Wang et al., 2021) integrates a weighting strategy akin to WELM with an online sequential extreme learning machine (OSELM, Huang et al. (2005)). WOS-ELMK (Ding et al., 2018) incorporates kernel mapping, addressing the non-optimal hidden node issue present in WOS-ELM. AI-WSELM (Qin et al., 2021) integrates active learning to significantly roduce labeling costs, demonstrating satisfactory performance compared to existing WELM variants. Despite their promising performance, the weight stralegies within this family are explicilly tailored for ELM, limiting their generalizability to other online learning models. In the literature, class sizes are frequently utilized to determine weight strategy. However, this approach does not ensure an optimal weighting schedule.
2.1.3 Ensemble Methods
Ensemble methods, such MOOB, MUOB (Wang et al., 2016), KUE (Cano & Krawezyk, 2020), ROSE (Cano & Krawezyk, 2022), and BEDCOE (Li al., 2023), effectively tackle the problem by combining resampling techniques. MOOB and MUOB leverage time-decay class size to determine training times. Specifically, the training time for each base classifier is determined by sampling from a Poisson distribution, whose parameter is set according to the class size. The diversity is maintained by random training times on a sample for each base classifier. Kappa Updated Ensemble (KUE) combines online and block-based ensemble approaches and uses Kappa statistics to determine dynamic weighting and select base classifiers. After that, Cano & Krawezyk (2022) proposes an advanced method called ROSE to improve the robustness of KUE by employing adaptive self-tuning, adjusting its parameters, and ensembling the line-up dynamically. To directly deal with class imbalance, ROSE computes the imbalance ratio of each class based on recent samples to derive the training times of each sample. BEDCOE considers potential complex data distribution compared to other works and introduces a borderline enhanced strategy and a disjunct cluster-based oversampling for synthetic sample generation. Despite the improved performance achieved by using multiple base classifiers, the ensemble methods entail a tradc-off between the diversity of the ensemble and training time.
2.1.4
Common Issues of Existing Methods
We note that the hcuristic designs cxist in all three categories, and several examples are listed below.
First, some methods suggest the imbalance ratio solely determines the imbalance status and do resampling (Wang& & Pineau, 2016; Wang et al., 2016; Bernardo et al., 2020) or design cost schemes (Zong et al., 2013; Wang et al., 2021) based on the estimated online imbalance ratio. However, this is not unique indicator of class imbalance. Other information, such as data dist.ributio,, is also helpful.
Another common assumption is generating synthetic samples around minority instances helps with learning, including Ren et al. (2019), Jiang et al. (2021) and Li et al. (2023). However, this only holds when the minority data is well-clustered and sufficiently discriminative. If the training data is extremely imbalanced or with many corrupted labels, the minority class would be poorly represented and lack a clear structure. In this case, working under this assumption severely jeopardizes the performance.
Additionally, to use the estimated imbalance status such imbalance ratio or data distribution from clustering, existing works predefine a certain functional form of the relation between imbalance status and training scheme. For instance, WELM (Zong et al., 2013) assumes the cost of misclassifying a class is inversely proportional to its class size. Similarly, MOOB and MUOB (Wang et al., 2016) suppose the training time of one class should be sampled from a Poisson distribution with the imbalance ratio as a parameter. However, the concrete functional form of using imbalance status cannot be exhausted. Besides, none of them have theoretically justified that the proposed functional form could lead to optimality with respect to certain
4

---

Published in Transactions on Machine Learning Research (09/2024)
minority
majority
refined boundary
original boundary
concept drift
time
Figure 1: Illustration of the working mechanism cost vector. The cost vector pushes the decision boundary towards the majority, and the dynamic EA ensures the adaplability of the cost. vector for potential concept drift.
performance metric, especially considering that data distribution becomes highly skewed and varies time. Therefore, propose to optimize the performance metric directly without fully relying the estimated imbalance status.
2.2 Threshold Moving Method
The threshold moving method (Kukar et al., 1998; Zhou Liu, 2005; Sheng & Ling, 2006; Voigt al., 2014; Hancock et al., 2022) is a common technique in cost-sensitive learning. It trains classifier on the original dataset and prioritizes classes with higher misclassification costs during prediction, using a predefined cost matrix. Formally, denote the cost matrix as My, where 1 S i,j C, to represent the cost of misclassifying class i to class j. Here C' is the nunber of classes. Let O,, where 1 S i S C, represent the probabilistiie output with Ei=1 O = 1 and 0 S O S 1. The prediction is arg max, O in the threshold moving method comparing to arg max; O, in standard classifiers, where O2 is calculated according to
0 = Σ M. n Σ 1=1
M2)), = mp;0;
(1)
0 and 0 < O2 S 1. A cost vector v, ES Mij (1 < C) of lower complexity O(C) can be used in place of the matrix. The cost vector represents the misclassification cost of class i and adjusts the decision boundary toward less costly classes, making it harder to misclassify samples with higher costs. In this paper, the threshold moving is adapted to online class imbalance learning by enabling the cost matrix/ cedurx/vecttr vector to be learnable in two novel ways, namely OECV-n and OECV, so that it can respond to the current stream behavior (Fig. 1) rather than being predefined. The baseline OECV-n designed with time-decay class size, while the main algorithm OECV finds the optimal cost vector based on OECV-n and EA.
Here 17 is normalization term such that Of
2.3 EA for Class Imbalance Learning
Recent studies (Pei et al., 2023) have shown the potential of EA in addressing class imbalance, while most of the existing literature remains confined to offline scenarios. In Perry et al. (2015), a genetic algorithm (GA) is used to optimize a class-dependent cost matrix for the weighted updating of a classifier. Sun et al. (2006) introduces a cost-sensitive boosting algorithm that employs GA optimize a class-dependent cost vector. ECSB (Lemnaru & Potolea, 2017) uses GA to optimize class-dependent cost matrix and classifter parameters simultaneously. GA is also applied to identify an optimal subset of instances in the majority class (Drown et al., 2009; Khoshgoftaar et al., 2010). In a cost-sensitive SVM method proposed in Cao et al. (2013), the misclassification cost ratio is optimized using particle swarm optimization. Furthermore, differential evolution (DE) has also been tried to optimize Llass-dependen cost matrices for cost-sensitive deep belief networks (Zhang al., 2018; 2016). EA also utilized to support data-level methods. For instance, Jiang et al. (2016) introduces GASMOTE, GA-basod SMOTE approach that optimizes sampling rates for minority class instances.
5

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 1: Training Procodures of Proposed OECV
Input:
Classifier H6-1, class size Q2,1, training sample (X,, ye), evolutionary frequency f. optimal cost voctor v", cost vector population V, buffer B
Output: Prediction Dt
Generate rough probabilistic prediction P. using H
Produce refined prediction pž as final prediction Øt using Ps and v by Equ. 1.
Update H to HP by its own rule.
Update class size 44 + S2 according to Equ. 3.
Add the sample (Xt: 1/) to B. if t mod f == then Evolve V by Alg. 2 with Ω4 B and HG, and update V and v based on evolution result.
return 9t
There are significant challenges to adapting these methods to online settings. Unlike offline learning, which receives all training data upfront, online learning lacks this comprehensive data overview. Besides, the model must continuously and rapidly adapt to potential concept drift rather than converging. To our knowledge, only Wang & Wang (2023) has adopted a similar idea of EA in online class imbalance learning. It picks base classifiers of different parameter configurations with the highest performance so far. However, characteristics of class imbalance in Wang Wang (2023) are only used by the original resampling method, and the class imbalance issue is not handled by EA directly. Besides, it is currently tailored for binary classification tasks, making it unsuitable for multi-class scenarios.
3 Online Evolutionary Cost Vector (OECV)
In this section, we introduce Online Evolutionary Cost Vector (OECV) to illustrate the EA-based cost vector learning approach. Section 3.1 outlines the overall training process. Section 3.2 reformulates the problem into bi-level optimization. Section 3.3 gives the baseline algorithm OECV-n, and Section 3.4 gives the EA-based algorithm OECV.
3.1 Overall Test-then-train Process of OECV
In a data stream {(X,, X, E Rd represents data and y/. E {1,..., C} represents the class label. C' is the total number of classes. Uneven class prior distribution leads to class imbalance, and concept drift necessitates the algorithm to adapt to ever-changing data distribution. X, arrives strictly one by one, being predicted firstly by the latest classifier HL-1, and then refined using the cost vector v give the final prediction P P is used together with true label yt that comes before + to update classifier HC H.C. This process is known as the test-then-train process.
We present OECV in Alg. 1. At the beginning of the data stream, the cost vector population V is initialized randomly. At time step i, the model (H(_)- v"), where HC represents the latest online classifier, and v* denotes the optimal cost vector discovered by EA up to time t t- 1, undergoes initial testing as depicted in Lines 1-2. Here, the online classifier offers an initial prediction, which then refined by the cost vector. The classifier HC updates by its own rule in Line 3. The class size Ω and fixed-size buffer B are updated in Lines 4-5, respectively. Cost vector population V evolves within the if statement (Lines 6-7) to yield new population along with optimal cost vector y*, We detail OECV in subsequent subsections individually.
3.2 Bi-level Optimization
Due to the impracticality a full evolution, our framework only evolves partially and breaks down both the model and the problem into two layers (See Fig. 2). The lower layer, being an ouline classifier, offers a rough probabilistic prediction and updates by its own rule on the fly. The upper layer, being a cost vector, refines the rough prediction and undergoes dynamic optimization process via dynamic EA. The training data for

---

Published in Transactions on Machine Learning Research (09/2024)
Add sample (K,Y))
Original Sample X
Update per sample
M Mie
Probabilistic prediction
Mid probabilistic classifier after updating at time step Max cost vector after updating time step?
Buffer BB
(A)
Update per samples
Ngr-1 Hiz
Refined probabilistic prediction Mas X (X))
Pop out outdateed sample
G-mean
Mar (X.)
predict
oversampling by of?
Figure 2: Illustration of OFCV as bi-level optimization problem (Section 3.2). The lower layer consists of a probabilistic classifier, while the upper layer is a cost vector (Section 2.2). A fixed-size buffer is maintained as the training data for the upper level. The cost vector is learned by a dynamic EA at frequency f on the oversampled buffer, using G-mean for objective evaluation (Section 3.4).
updating the cost vector come from fixed-size buffer B, which is augmented by simple oversampling trick resulting in a larger buffer B' to enhance data diversity. As shown in the left part of Fig. 2, we denote the first and upper layers as H1. and H2,s, respectively. The complete model is denoted by Hr {H1.t. H2,). The lower-level problem is to minimize a loss function & (HH;; X Vt), which assesses the probabilistic prediction loss computed for each sample in the stream. The upper-level problem involves minimizing a non-diffcrentiabll performance metric P(: Hi,), Wr), which measures the refined prediction error based on the solution Hi. of the lower layer. The learning process of the upper layer occurs at fixed frequency f instead of updating every time for computational efficiency. Importantly, the lower layer updates solely based its own rule, and optimizing the upper layer does not affect the lower layer. The overall optimization problem is stated as
min (2(H2, H7,)) H2.1
(2)
s.t. Hj,r i = arg min f (H1; Xe,
Hi.
Note that the optimization of the lower level does not depend the upper level in the sense that Hi, does not depend on H2.1.
In this study, Hi is parameterized as an online classifier H. along with its training loss & adapted from existing work. HC may not consider the specific characteristics of the performance metric (c.g., class imbalance) to be optimized. H2 is parameterized as a cost vector v, and the choice & varies depending on specific needs, such as G-mean or balanced accuracy. In this way, only the upper layer metric-specific. Tn the following subsections, we only focus on the learning strategies for the cost vector.
We notice that the upper level and the lower level essentially optimized the overlapping source of data, where the classifier (lower level) uses all data until time f, and the cost vector (upper level) uses past sample stores in B. Intuitively, this may result in overfitting in a bi-level optimization problem. In offline bi-level optimization, a better choice to use distinct training and validation datasets to train the two levels. However, it is more tricky in our online setting since the samples come the form of a stream. We did not add additional design for simplicity. In fact, the oversampling technique on B, which, although not specifically proposed to handle this problem but proposed to enhance the optimization of the cost vector, may also help. Specifically, this can alleviate the overfitting of overlapping data sources at two levels by introducing diversified data via interpolation, making the data used for the upper level more diversified compared to the lower level.
Remark 1
Remark 2 Several trade-offs exist in the design of OECV. The first is introducing the updating frequency of cost vector and population size handle the trade-off between time consumption and performance. Intuitively, small updating frequency f will allow better performance, and in the extreme case where f f= 1, the updating frequencies of both levels align, which would achieve the best performance. However, this comes
7

---

Published in Transactions on Machine Learning Research (09/2024)
with high computation costs since updating the cost vector is generally slower than the classifier. Conversely, intermittent updating of the cost vector allows faster training while may incur sub-optimality due to the mismatching of optimization speed of two levels. Similarly, large population size can increase the probability of finding the optimal solution but would induce high updating costs and is not favored in online learning. Another trade-off between memory consumption and performance, handled by the oversampling rate and buffer size. In practice, large memory allows a large buffer, and an oversampling trick may not be necessary in this case, which is equivalent to setting oversampling rate r 1. In contrast, the oversampling trick can reduce the storage requirement and enhance the data diversity but induces higher time consumption. Additionally, it may come with issues if label noise exists in B; the labels of augmented buffer B' are likely to be corrupted as well and result in performance degradation.
Fortunately, the choice of hyperparameters is straightforward and relatively robust within a certain range. In experiments, we set the hyperparameters to make the algorithm as fast as possible while still making improvements compared to basclines. The same set of hyperparameters is used without heavy fine-tuning, which already enables OECV outperform be on par with baseline methods over wide range of datasets. See also Appendix E for empirical analysis on the sensitivity of hyperparameters above.
3.3 Learning Cost Vector with Time Decay Class Sizes
The first approach OECV-n(naive) employs time-docay class sizes (Wang al., 2018) Ω4 {wi,) at time continuously track the imbalance status over time using predefined time decay factor X:
What = AwI.t-1 + (1 - A) T(y: = k)
OSASI
(3)
where wkee represents the size of the k-th class at time step t, and is the indicator function. Cost matrix Mij and cost vector iú are then determined heuristically as follows:
M3
Mij
(4)
Wi.t
In other words, the prediction probability of a class will be scaled up if it is a relative minority class (in the sense of adaptively estimated class size w) and scaled-down otherwise. The loss function remains untouched in threshold moving, but the prediction probabilities are scaled by v. It can adapt to current stream behavior by passively changing the imbalance status. However, optimal performance is not guaranteed the dependency on the heuristic form of the cost matrix well as the choice of x. The detailed training procedure of OECV-n is similar to that of OECV, by just removing all the use of evolution and replacing v* in Alg. 1 by the cost vector determined by Equ. 4
3.4 Learning Cost Vector with Dynamic EA
Compared to designing solely with timo-decay class size, EAS can find cost vectors that optimize performance measures directly. The evolution process along two related tricks of the resulting OECV are illustrated follows. The complete algorithm is summarized in Alg. 2.
3.4.1 Evolution
Chromosome Encoding: A cost vector (h) is encoded into a chromosome straightfoorwaddyy with the C-dimensional vector being the chromosome.
The chance of passing genetic information subsoquent generations relies on the fitness of cost. vector. Recent samples are retained in a fixed-size bufler B for fitness caleulation. B is enlarged into B' by oversampling before being used for fitness evaluation. Specifically, classification using the latest classifier H. on B', resulting in the set of rough probabilistic predictions
Fitness Calculation:
first do
(pa)le 18' For each (A),, refines the rough predictions give set of final predictions (p. (*( [5) (k) |8|
(p, 18 along with the set of true labels (8:) then used to calculate performance metric
8

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 2: Cost Vector Evolution
Input: Buffer B, cost vector population V, online classifier HC, number of neighbors k, sampling rate r, size of prior population m
Output: Optimal cost vector v", cost vector population V
Maintain population diversity and integrate prior knowledge
Generate human-designed cost vector VA using ft by Equ. 4.
Create prior population { based on Va using Eqn. 5, and add to V.
// Oversampling for data diversity
Initialize augmented buffer B' with samples from B. for X, in B do
for r 1 times do
Find k nearest neighbors of X, and randomly select X; from them.
Generate new sample using Equ. 6 with a ~ (0, 1), and add it to B'.
// Evolution
Produce rough probabilistic prodiction {p:), = for each sample in B' using H.
B
For each v(k), produce refined predictions {p. (k) N== using {p:) (Eqn. 1).
Calculate fitness ((k) for v(k) based on {p, 1=1 and true labels (v:) [89)
(k) [B']
14 Evolve V for one generation by crossover and mutation using ( k=l
15 Determine the optimal solution v" by comparing fitness.
16 return v
as the fitness ((8) of v()) With the set of fitness ( the optimal individual (cost vector) can be determined straightlorwardly. Note the performance metric used here the correspouding offline metric (e.g., G-mean) instead of the online metric (e.g.. online G-mean) so that the fitness calculation is not affected by the order of samples in B².
Genetic Operator: EA employs genetic operators to produce new cost vectors by crossover and mutation based the fitness value of individuals. Any single objective genetic operator may be applied in the current framework.
If the generation of new cost vectors at Line 14 in Alg. 2 is removed, while the selection of the optimal individual in Line retained, we get a comparison algorithm OECV-ca as demonstrated the ablation study. In this case, OECV-ca can be used show whether OECV works by finding better individuals with evolution instead of simply relying the buffered data to select. good solution from large number of candidates.
3.4.2 Maintain Population Diversity and Integrate Prior Knowledge
The cost vector designed by time-decay class size as in OECV-n can be used to guide EA. This benefits OECV by integrating the prior knowledge of imbalance status and preventing it from converging to fixed optimal solution. Specifically, we add m different cost vectors [m(0)m Ja randomly generated from va. (Eqn. 4):
v = VA + W
Wy ~ Uj 0,
(5)
Recall in the definition of cost vector (Eqn. 1), we require each dimension of (11 = be in [0, 1] and sum up to 1. Therefore, each dimension of (() is clipped to [0, 1] and re-normalized. {y(i) )m are then merged with the previous population to form the initial population for later evolution. After a fixed frequency f, the prior
population is mixed in, and the population evolves over one generation.
Analogous the approach with time decay class size in spirits, the dynamic EA also acts passively counter the effect of concept drift, iee, not detect the concept drift directly. Although this may not be the best choice
9

---

Published in Transactions on Machine Learning Research (09/2024)
in more complicated scenarios, it would be sufficient for dass-prior drift. How to adapt to more complicated drift scenarios is beyond the scope of this work.
3.4.3 Oversampling for Data Diversity
To ensure accurate fitness calculation, an oversampling trick for enhancing data diversity is applicd to B to create an augmented buffer B', Specifically, we expand B to r times of its original size by generating r samples {(x,), Mt M= (r N4) for each (X,, E B:
x = X1 + a (x; X1),
= Yt
(6)
where a 1) and X is randomly selected from is nearest neighbors of X
3.4.4 Computational Complexity Analysis
We are aware of the potential high computational complexity induced by EAs, including time complexity and space complexity. A formal analysis is provided in this subsection. See also Appendix A for an empirical runtime comparison.
Memory Complexity Analysis Denote the population size as V and buffer size as |B. OECV requires the storage of a bulfer of data of size O( x (d + 1)) where d denotes the number of features, i.e., we count. the mumber of stored samples times the number of features plus one (for the class label). Since temporary synthesized samples augmented buffer B' can be processed one by one without storing everything in the memory, whose memory consumption is then negligible, the oversampled data is not taken into account for the extra storage.
Time Complexity Analysis The overall time complexity of OECV is linear to the length of the stream, being the same as existing works such as Wang et al. (2016), Qin et al. (2021), and Li et al. (2023). In each time step, the time complexity includes the training cost of both the classifier and the cost vector. The updating of the classifier a constant and depends on its own rules. For updating of the cost vector, the oversampling on B takes O(BB] x (r 1)) time. Then, [V] individuals perform prediction and evaluation on B' that takes O(VI x B x r) time total. The crossover, mutation, and selection operations are based on fitness, being method-depon dependent.. It generally takes O(VI) and is much faster than the fitness calculated in the last step. Summarize and simplify the above steps, and recall the updating of the cost vector occurs al frequency of f, we find the overall time complexity can be represented O (TT]VIIBI) stream, where T is the length of the stream.
) for the whole data
While EAs are well-known for their high computational cost (mainly from fitness evaluation), our scheme of applying the cost vector in a post hoc way allows for a much more efficient fitness evaluation. To see this, a forward calculation for prediction is enough to give the fitness, which is attributed to the decoupling of two layers where the training of the classifier is totally independent of the cost vector. Therefore, we only need to evaluate how well the cost vectors correct the current well-trained classifier without any retraining of the classifier. This drastically decreases the time for fitness calculation and makes OECV practical.
3.4.5 Storage Requirement
We are aware that the extra storage requirement in the form fixed-size buffer is a weakness in our current. method. However, certain storage requirements are generally acceptable in the literature, especially widely used in data-level methods (Sec. 2.1.1). The resampling and clustering processes necessitate extra storage similar to ours. For example, Qin et al. (2021), Ren et al. (2019), Cano & Krawczyk (2022), and Wang & Pincan (2016) all require certain storage in the form of a sliding window or chunk. Despite the extra storage burden, it is usually constant and would not increase with the length of the stream. This is practical in many real-world scenarios, such as online edge machine learning, where the stream can be infinitely large, but certain storage (while limited) is accessible. However, additional storage is unavailable, an adaptive generative model can be used to generate samples to replace the buffer. In this work, we focus on the current. extra storage scheme for simplicity.
10

---

Published in Transactions on Machine Learning Research (09/2024)
For fair comparison in empirical studies, take AI-WSELM (Qin al., 2021) (Sec. 4.2) and SmoteOB (Wang & Pineau, 2016) (Appendix F) that require extra storage as compared methods. The extra storage of two methods is set to be larger or comparable than OECV. Additional explorations on whether the performance enhancement is induced by extra data and the influence of the buffer size are also presented in Sec. 4.3 and Appendix E.3.
4 Experimental Studies
This section evaluates OFCV from several aspects: comparison with SOTA methods, the effectiveness of F.,, and the inner working mechanism.
4.1 Experimental Setup
We use 30 datasots in total as summarized in Table 1, including 10 streaming datasets (Elec, Abrupt, Gradual, Incrementall, Luxembourg, NOAA, Ozone, Airlines, Covtype, Incremental2, available in the USP-DS repository, Souza al. (2020)) and 20 real-world offine datasets (remaining 20 datasets in Table 1, available in the Keel repository, Derrac et al. (2015)). The 20 offline datasets are processed in streaming way to simulate online scenarios. The overall static imbalance ratio for each dataset illustrates the severity of class imbalance, while fluctuation of class imbalance ratio throughout the online learning scenario exisls.
Although our method does not require an offline warm start, we use the initial 30% samples of each stream for model initialization in an offline fashion, following the setting in Li et al. (2023). The initialization samples are further split into two datasets in equivalent sizes for training the classifier and the cost. vector separately. In this stage, the cost vector population evolves 10 generations to give an initial population for later online training. The buffer size [B] for OECV is fixed at 200 samples, and the oversampling rate is set to 5 for all datasets. Offline G-mean is used for fitness evaluation the augmented buffer. The cost vector evolves every 5 sample (i.e., f= 5); with the number of individuals set to 25. We employ DE//best/1/ (Opara & Arabas, 2019) as the genetic operator. The implementation of EAs is easy by directly adopting the existing Python packages (such as geatpy 2 used in our experiments). All the hyperparameters related to genetic operators are set to the default values of the existing implementation without tuning. Specifically, the scaling factor of DE set to 0.5, and exponential crossover is applied with the probability of crossover set to 0.7.
We compare with four SOTA online multi-class imbalance learning methods: MOOB, MUOB (Wang et al., 2016), AI-WSELM (Qin et al., 2021), and BEDCOE (Li et al., 2023). The total number of base learners is set to 10, following (Wang et al., 2016; Li et al., 2023). All methods adhere to the test-then-tres process of online learning. Multilayer perceptron serves as the base classifier for all methods, except AI-WSELM, which does not need a base classifier, following the setup in Wang et al. (2016). We set the chunk size (akin to our buffer) of AI- WSELM to be 300, higher than our extra storage of 200. Prequential G-mean with a fading factor of 0.99 is selected as performance metrics, following Wang et al. (2018) and Li al. (2023). Mean performance across 10 runs is evaluated on the remaining samples after the initialization number. Friedman tests (Demšar, 2006) are used to compare competing methods across datasets statistically. The null hypothesis (H0) posits that all models are equivalent in terms of the predictive performance metric. The alternative hypothesis (H1) suggests that at least one pair of methods differs significantly. If HO is rejected, the Conover test (Conover & Iman, 1979) is conducted as the post-hoc test.
4.2 Performance Comparison
We can see from Table 2(a) that in terms of G-mean, OECV performs the best in 14 out of 30 datasets and the 2nd best in 8 datasets. Friedman tests at significance level 0.05 reject HO with p-value 1.11 x 10-3 showing a significant difference between mods Average ranks (avgRank) across datasets are reported to show how well each method performs compared to others across datasets. The average rank of OECV is 1.967, being the best. Post-hoc tests are then conducted to detect whether OECV has a significant difforence
11

---

Published in Transactions on Machine Learning Research (09/2024)
Table 1: Overview of the dataset. *# Data" denotes the total number of samples within this dataset, F#Fe denotes the number of features, "# Class" denotes the number of classes, and IR denotes the overall static imbalance ratio being computed as the ratio between the largest and smallest class sizes.
Dataset
# Data #Fea # #Class
Dataset
#Data # Feaa # Class
IR.
Dataset
# #Data #Fea #Class
IR
Elec
5000
8
2
1.6
Abalonel
2338
8
2
39.3
Winl
691
11
2
68.1
Abrupt
5000
33
4.0
Abalone2
1622
8
2
49.7
Win2
1599
11
2
29.2
Gradual
5000
33
6
171.2
Carl
1728
6
2
24.0
Win3
656
11
2
35.4
Incrementall
5000
33
1.0
Car2
1728
2
25.6
Win4
1482
11
2
58.3
Luxembourg
1901
31
1.06
Kddeup
2225
41
2
100.1
Win5
900
11
2
44.0
NOAA
5000
8
2
2.4
Kr
2901
6
2
26.6
Yeast
947
8
2
30.6
Ozone
2534
72
14.8
Segment
2308
19
2
6.0
Yeast2
1484
8
10
92.6
Airlines
5000
7
2
2.1
Shuttlel
3316
9
2
66.7
Yeast3
1484
8
2
8.1
Covtype
5000
54
7.0
Shuttle2
1829
13.9
Yeast4
1484
8
2
32.7
Incrementa12
5000
33
6
25.4
Thyroid
720
21
3
39.2
Yeast5
1484
8
2
41.4
from the competitors, for which OECV is chosen as the control method. Post-hoc comparisons show that OFCV can significantly putperfor all of the competitors.
We can draw two observations on when the OECV can gain an advantage or not from Table and Table 2. Firstly, we notice that when the number of classes is large, e.g., on Gradual, Incrementall, and Yeast2 datasets, our method generally does not perform the best compared to other baselines. Further analysis of the Spearman correlation (Fieller et al., 1957) shows correlation coefficients of 0.49 (moderate) between the number of classes and the value of rank on the 30 datasets (the higher the rank, the worse the performance), being positively correlated. This verifies that our method generally performs better when a small number of classes are presented. This is reasonable since the complexity of the cost vector equals the number of classes, and a larger cost vector is intuitively more difficult to find its optimal solution within limited time and memory. remedy for this issue deserves a more complicated algorithm design and is left to the future. Secondly, find our method performs better when the stream is highly skewed, ie., with large imbalance ratio. For example, on datasets Win3, Win4, and Win5, our method performs the best among baselines with larger margin. Similarly, analysis of the Spearman correlation shows correlation coelficients of -0.29 (weak) between the imbalance ratio and the value of rank on the 30 datasets, being negatively correlated, which confirms our conjecture that a highly imbalancod stream favors OECV. We speculate, in this case, the ad hoc imbalance estimation, such as the time-decay imbalance ratio (which used in MOOB, MUOB, and BEDCOF), can not capture the complicated overall imbalance status well. This downgrades the performance of baselines by using a misleading imbalance indicator. In contrast, our method seeks an optimal cost vector directly with respect to the performance metric without consulting heuristically estimated imbalance status. This explains why OFCV outperforms other methods under high imbalance.
4.3 Ablation Study
Two comparison models OFCV-n and OECV-ea have been built in Section 3.3 and Section 3.4, which differ from OECV by just the way on learning cost vector. They are employed here to study the effectiveness of EA. We would expect the performance of OECV, with the full assistance of evolutionary optimization, to be the best. The performance of OFCV-ea should be in the middle since while evolution is not used, several candidates of cost vectors are still under considcration for selecting the best one using buffered data. The performance of OECV-n should be the worst because only an inbalance ratio is used. If this occurs, we can conclude that the EA used for optimizing the cost vector is crucial for dealing with class imbalance, and extra data in the buffer is not the determinative reason for performance improvement.
Table 2(b) shows the result in terms of G-mean. The three methods are compared to each other, with Wilcoxon signed rank tests (Wilcoxon, 1992) used to determine there are significant differences between them. We can see that the average rank of OECV (1.333) is better than that of OECV-n (2.467) and OECV-ca (2.2). Wilcoxon signed rank test rejects HO with p-value 0.0036 and 9.62 x 10-5, respectively, meaning OFCV is significantly superior to OFCV-n and OECV-ea. In comparison between OFCV-ea and
12

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Performance comparison in terms of G-mean (%). Each entry is the meantsst performance across 10 runs. The best performance on each dataset is highlighted in bold, and the 2nd best performance is highlighted in italics. The last row lists the average ranks (avgRank) of each model across datasets in each subtable. Part (a) compares SOTA methods and the proposed OECV. A significant difference against OECV is highlighted in yellow. Part (b) reports the ablation results between variants of OECV.
(a) Performance comparison
(b) Ablation studies
Dataset
AT-WSELM
MOOB
MUOB
BEDCOE
OECV
OECV-n
OFCV
OFCV-ea
Elec
78.2+:1.6
90.910.2
88.7+004
95.5++0.1
83.7+t0.9
83.1
83.7+0.99
83.6::0.9
Abrupt
66.211144
60.24:1.7
60.41:222
60.0+1044
62.810.6
62.0+10.7
62.8:1066
62.61:0.9
Gradual
0.0
22.4+9.1
0.1+0.33
34.8+20.4
8.544.2
15.8+2.5
8.5=4.2
4.3+2.8
Incrementall
46.0+0.7
53.8+0.6
48.5+2.0
52.9+0.4
46.4+..5
45.9+1.2
46.4+1.5
46.2+1.2
Luxembourg
85.5+22.4
100.0+0.0
100.0#0.0
100.0+0.0
100.0+0.0
100.0
100.0+0.00
100.0+0.0
NOAA
71.310.88
65.310.77
64.610.6
68.210..7
73.110.5
73.010.5
73.110.5
72.910.5
Ozone
65.01:2.9
72.311.8
78.0=0.6
70.6
77.111.7
718819
77.111.7
76.1111.6
Airlines
50.8+1.0
34.642.88
47.6+1.6
50.6+0.4
51.8+0.9
50.7+0.5
51.8+0.9
51.74-0.8
Covtype
0.0+0.00
65.4+0.8
0.0+0.00
64.6+1.2
28.6+1.5
38.7+1.1
28.6+1.5
26.6+1.3
Incremental2
0.8+0.2
30.8
0.9
40.9+1.6
15.6+1.6
21.2+1.8
15.6=1.6
13.0=1.0
Abalonel
43.645.2
55.0+0..9
64.5+3.8
59.1=0.8
67.8+4.3
55.723.0
67.8+4.33
59.0+5.7
Abalone2
48.019.3
4.6:0..0
26.8+8.2
33.2+0.0
38. 7.6
25.6#0.1
38.727.6
33.1
Carl
80.412..
33.314..
56.314.9
44.5.1..0
78.212.2
77.013.11
78.212.2
77.512.0
Car2
96.511299
74.910.7
79.813.7
74.41155
96.111..0
94.111.2
96.1111.0
95.210.9
Kddcup
78.1+11.8
100.0+0.0
95.9+3.5
100.0+0.0
100.0+0.0
100.0
100.0+0.0
100.0+0.0
Kr
94.3+1.7
94.4+0.7
90.5+1.8
90.2+0.7
94.7+1.3
91.5+0.88
94.7+1.3
92.
Segment
98.7#0.4
98.910.1
93.010.6
99.010.0
99.110.1
99.120.1
09.1
99.410.11
Shuttle1
100.0#0.0
99.410.6
97.911.7
99.0#10.9
99.910.0
99.910.0
99.910.0
99.9=1.00
Shuttle2
99.410011
99.6110.0
99.8-0.1
99.710.1
99. 7..00.0.0
99.711.00
99.710.00
99.6-10.0
Thyroid
29.01111.0
38.912.7
0.6.0.0
2..2
71.6.1..5
68.5133.
71.611.5
73.6.12.2
Winl
29.1134.1
6.8.1..0
6.8L0.00
36.51.364
80.611..2
79.910.1
80.611.2
80.6.0..
Win2
39.0+4.8
15.4+5.1
62.0=5.0
27.3+1.4
59.248.6
48.1#0.9
59.243.6
49.6+
Win3
26.2+11.3
22.1+2.4
19.6+10.0
26.5+2.8
79.9+1.2
39.0#4.22
79.9+1.2
60.6 12.9
Win4
9.741007
13.2111.6
16.719.5
27.711.6
50.611..7
18.927.7
50.615.7
29.11
Win5
22.8119.3
32.814.7
11.0#4.2
14.7=10.0
53.317.11
53.315.6
53.317.1
41.017.4
Yeastl
47.8+8.0
32.0+0.5
36.1
33.24-4.1
18.9
16.5+0.9
48.0+18.9
15.5+10.2
Yeast2
28.0+6..0
0.140.11
0.0+0.00
8.8+44.2
0.2.00.4
0.0.5..0
0.240044
0.0.:..0
Yeast3
81.5+2.3
89.2+0.3
89.8=1.2
87.5
87.8+1.0
85.0#1.1
87.8+1.0
86,8+0.8
Yeast4
72.916.6
86.5+0.8
82.4+9.5
71.742.8
81.7+5.7
68.3+4.0
81.745.7
75.0+3.7
Yeastō
70.3
64.1+1.9
51.747.1
53.1+3.0
86.5+1.7
84.8t0.1
86.5+1.7
81.8+2.8
avgRank 3.35
3.133
3.517
3.033
1.967
2.467
1.333
2.2
OECV-n, the average rank of OECV-ea (2.2) is better than OECV-n (2.467), but the Wilcoxon signed rank test fails to reject HO with p-value 0.178, meaning there is no significant difference between OECV-ea and OECV-n. From the comparison betwoen OECV and OECV-n, we see that climinating the whole EA stratogy would significantly decline performance. Additionally, we can see from the comparison between OECV-ca and ORCV, as well as OFCV-ea and OFCV-n, that the extra data does not play a determinative role. This is because OECV-ea also uses extra data in finding optimal cost vector with the performance set the objective of performance metric, but it does not perform significantly better than OECV-n and performs significantly worse than OECV. This implies that il is the EA instead of extra data making OECV outperform compared methods.
4.4 Further Discussions
We explore two related questions to assess the working mechanism of OFCV.
13

---

Published in Transactions on Machine Learning Research (09/2024)
1.0
OCCV-n OCCV-e> OPTY
100
Imbaiance rabro diference
Imbalance retio
0.23
0.30
OCCV
OCCV
Impatoncc Ratt
20
0.0
0.6
0.00
0
250
500
750
1000 1250 Time step
1900
1750
250
500
750
1250 Time step
1000
1500
1750
250
1250 1500 1750 500
750
1000
"Ime step
Figure 3: Prequential G-mean, imbalance ratio, and standard deviation of fitness of the population in dataset Ozone. The higher the standard deviation, the greater the diversity. Imbalance ratio is calculated by time-decay class sizes (Eqn. 3).
1.0
12
OFEV-48 OE1V
CECV- CPCV
0.0-
imoslance Febro
weight robo U
0.2
WA
0.0
1500
2000
1500 2000
3500
step
Figure 4: Prequential G-mean, imbalance ratio, and weight ratio in dataset Airlines. Imbalance ratio is calculated by time-decay class sizes (Equ. 3).
4.4.1 Analysis Population Diversity
We explore whether OECV can maintain population diversity over time instead of converging. The population diversity enables ORCV to track the optimal cost vector instead of converging to certain solution. We present the standard derivation of individual fitness in Fig. 3 with a further analysis of the Spearman correlation (Fieller et al., 1957). The result shows correlation cocfficients of 0.594 (moderate) and 0.629 (strong) between the absolute difference of imbalance ratios (i.e., the absolute value of the difference between two neighboring class imbalance ratios) and standard deviation (std) of fitness of OECV and OECV-ca, respectively, being positively correlated. It also shows a high correlation coefficient of 0.869 between the std of fitness of OECV and OECV-ea. We can draw two conclusions: 1) The diversity adapts to data stream behavior. This means OECV and OECV-ea expand the exploration of new cost vectors (high std) during concept drift where the imbalance ratio changes drastically while adopting temporary clitists by leveraging learned knowledge about class imbalance (low std) during the steady stream where the imbalance ratio is stable. 2) Despite similar diversity and changing behavior, OECV outperforms OECV-ea. This indicates the superiority of EA in that it can maintain population of cost vectors with higher quality under the same diversity.
4.4.2 Analysis EA-based Cost Vector
We explore how the cost vector found by the EA outperforms the one determined solely by the imbalance ratio. We define the weight ratio (WR) as dg to visualize the cost vector in a binary classification scenario in Fig. 4. Here, v; represents the i-th dimension of the cost. vector. Analogous to the imbalance ralio, the WR serves as a belief of the imbalance level indicated by the cost vector. We analyze the Spearman correlation between the WR of three variants and the imbalance ratio, yiclding correlation coefficients 0.971, 0.897, and 0.887 for OECV-n, OECV-ca, and OECV respectively, indicating strong correlations. This means the cost vectors found by FAA also reflect the beliefs about. class imbalance, while some of these beliefs are
14

---

Published in Transactions on Machine Learning Research (09/2024)
sacrificed to seek more appropriate values of the cost vector in finding the optimal solution. Besides, Fig. 4 illustrates the challenge of finding the optimal solution by ad hoc assumptions: While OECV outperforms that of OECV-n, the WR of OECV fluctuates compared to OECV-n. This suggests that relying solely on the imbalance ratio insufficient for identifying the best cost vector. The dynamic EA addresses this limitation by directly setting the performance measure as the objective and avoiding heuristic reliance.
5 Conclusion
This article introduces a novel approach Online Evolutionary Cost Vector (OECV) to tackle the online class imbalance issue by eliminating heuristic assumptions on class imbalances widely used in existing methods. OECV instead manages to optimize performance on any specified performance metrics directly, achieved by adopting a dynamic EA. The model is explicitly deconstructed into two layers: an online classifier for rough probabilistic prediction and a cost vector for refining the decision boundary. The cost vector the only part subject to the dynamic EA for directly optimizing specific performance metrics. This bi-level architecture is motivated by viewing the cost vector as hyperparameter in the threshold moving method and the EA approach to fine-tune the hyperparameter. A dynamic EA is employed to track the optimal cost vector over time. Cost vectors designed by class size are integrated into the prior population to sustain population diversity and integrate prior knowledge. To enhance data diversity, an oversampling trick is used to augment. the buffer and attain more beneficial evolutionary results. Empirical studies demonstrate the validity and efficiency of our approach. Analysis of the working mechanism reveals how OECV can generate a superior cost vector compared to the human-designed counterpart.
The potential of the OECV framework extends beyond the class imbalance setting and has further exploration values in various other classification lasks. High performance across broad range of metrics unrelated to class imbalance could be achieved with only slight adjustments to the cost vector. For instance, OECV can simultancously serve multi-objective purposes by optimizing for multiple metrics, including accuracy, recall, and F1-score. Another future work is to handle the potential label noise. Specifically, when there exist corrupted labels, the samples in the augmented buffer will also contain corrupted labels, which may degrade the optimization of cost vectors and deserve further specific design.
References
Alessio Bernardo, Heitor Murilo Gomes, Jacob Montiel, Bernhard Pfahringer, Albert Bifet, and Emanuele Della Valle. C-smote: Continuous synthetic minority oversampling for evolving data streams. In 2020 IEFE International Conference on Big Data (Big Data), pp. 483-492. IEEE, 2020.
Albert Bifet and Ricard Gavalda. Learning from time-changing data with adaptive windowing. In Proceedings of the 2007 SIAM international conference on data mining, pp. 443-448 SIAM, 2007.
Alberto Cano and Bartosz Krawczyk. Kappa updated ensemble for dristing data stream mining. Machine Learning, 109:175 218, 2020.
Alberto Cano and Bartosz Krawezyk. Rose: robust online self-adjusting ensemble for continual learning on imbalanced drifting data streams. Machine Learning, 111(():2561 2599, 2022.
Peng Cao, Dazhe Zhao, and Osmar Zaiane. An optimized cost-sensitive svm for imbalanced data learning. In Pacific-Asia conference knowledge discovery and data mining, pp. 280-292 Springer, 2013.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-351 2002.
William Jay Conover and Ronald Iman. On multiple-comparisons procedures. Los Alamos Sci. Lab. Tech. Rep. LA-7677-MS, 1:14, 1979.
Janez Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research, 7:1-30, 2006.
15

---

Published in Transactions on Machine Learning Research (09/2024)
J Derrac, S Garcia, L Sanchez, and F Herrera. Keel data- mining software tool: Data set repository, integration of algorithms and experimental analysis framework. J. Mull. Valued Log. Soft Compul, 17:255 287,,-27, 2015.
Shuya Ding, Bilal Mirza, Zhiping Lin, Jiuwen Cao, Xiaoping Lai, Tam V Nguyen, and Jose Sepulveda. Kernel based online learning for imbalance multiclass classification. Neurocomputing, 277:139-148, 2018.
Dennis Drown, Taghi M Khoshgoftaar, and Naeem Seliya. Evolutionary sampling and software quality modeling of high-ass high-assurance systems. IEEE Transactions on Systems, Man, and Cyberneties Part A: Systems and Humans, 3065)1007711177; 2009.
Pedro G Espejo, Sebastián Ventura, and Francisco Herrera. A survey the application of genetic programming to classification. IEEE Transactions on Systems, Man, and Cybernetics, Part C' (Applications and Reviews), 10(2):121-144) 2009.
Edgar C Fieller, Herman O Hartley, and Egon S Pearson. Tests for rank correlation coefficients. i. Biometrika, 44(3/4):40 1814 1957.
João Gama, Indré Zliobaité, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM compuling surveys (CSUR), 46(4):1 37, 2014.
John Hancock, Justin M Johnson, and Taghi M Khoshgoftaar. A comparative approach to threshold optimization for classifying imbalanced data. In 2022 IEFE 8th International Conference on Collaboration and Internet Computing (CIC), pp. 135 142. IEEE, 2022.
Guang-Bin Huang, Nan-Ying Liang, Hai-Jun Rong, Paramasivan Saratchandran, and Narasimhan Sundarara- jan. On-line sequential extreme learning machine. Compulational Intelligence, 2005:232 237, 2005.
Kun Jiang, Jing Lu, and Kuiliang Xia. A novel algorithm for imbalance data classification based on genetic algorithm improved smote. Arabian journal for science and engineering, 41:3255-3260 2016.
Zhenhao Jiang, Tingting Pan, Chao Zhang, and Jie Yang. A new oversampling method based on the classification contribution degree. Symmetry, 13(2):194, 2021.
Taghi M Khoshgoftaar, Naeem Seliya, and Dennis J Drown. Evolutionary data analysis for the class imbalance problem. Intelligent Data Analysis, 14(1):69-8) 88, 2010.
Jakub Klikowski and Michal Woéniak. Employing one-class svm classifier ensemble for imbalanced data stream classification. In Computational Science ICCS 2020: 20th International Conference, Amsterdam, The Netherlands, June 3 5, 2020, Proceedings, Part IV 20, pp. 117 127. Springer, 2020.
Pawel Ksieniewicz. The prior probability in the batch classification of imbalanced data streams. Neurocom- puting, 452:309-316, 2021.
Matjaz Kukar, Igor Kononenko, et al. Cost-sensitive learning with neural networks. In ECAI, volume 15, pp. 88-94. Citeseer, 1998.
Camelia Lemnaru and Rodica Potolea. Evolutionary cost-sensitive balancing: A generic method for imbalanced classification problems. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation VT, pp. 194-209. Springer, 2017.
Shuxian Li, Liyan Song, Yiu-ming Cheung, and Xin Yao. Bedcoe: Borderline enhanced disjunct cluster based oversampling ensemble for online multi-class imbalance lcarning. In ECAI 2023: 26th European Conference on Arlificial Intelligence, September 30- October 4, 2023, Kraków, Poland, Including 12th Conference on Prestigious Applications of Intelligent Systems (PATS 2023): Proceedings, pp. 1414-1421. IOS Press BV, 2023.
Xu- Ying Liu and Zui-Hua Zhou Learning with cost intervals. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 403 412, 2010.
16

---

Published in Transactions on Machine Learning Research (09/2024)
Karol R. Opara and Jaroslaw Arabas. Differential evolution: A survey of theoretical analyses. Swarm and evolulionary compulation, 44:546-588 558, 2019.
Wenbin Pei, Bing Xue, Mengjie Zhang, Lin Shang, Xin Yao, and Qiang Zhang. A survey on unbalanced classification: How can evolutionary computation help? IEEE Transactions on Evolutionary Computation, 2023.
Todd Perry, Mohamed Bader-Bl-Den, and Steven Cooper. Imbalanced classification using genetically optimized cost sensitive classifiers. In 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 680-687. IEEE, 2015.
Jiongming Qin, Cong Wang, Qinhong Zou, Yubin Sun, and Bin Chen. Active learning with extreme learning machine for online imbalanced multiclass classification. Knowledge-Bart Based Systems, 231:107385, 2021.
Siqi Ren, Wen Zhu, Bo Liao, Zeng Li, Peng Wang, Keqin Li, Min Chen, and Zejun Li. Selection- resampling ensemble algorithm for nonstationary imbalanced stream data learning. Knowledge-Bar Based Systems, 163:705-722, 2019.
Miguel Rocha, Paulo Cortez, and José Neves. Evolution of neural networks for classification and regression. Neurocomputing, 70(16-18):2809-2555 2816, 2007.
Victor S Sheng and Charles X Ling. Thresholding for making classifiers cost-scnsitive. In Aeai, volume 6, pp. 476-480 481, 2006.
Olivier Sigand and Stewart W Wilson. Learning classifier systems: survey. Soft Computing, 11:1065-1078, 2007.
Vinicius MA Souza, Denis M dos Reis, Andre G Maletzke, and Gustavo EAPA Batista. Challenges in benchmarking stream learning algorithms with real-world data. Data Mining and Knowledge Discovery, 34: 1805-1858, 2020.
Yanmin Sun, Mohamed S Kamel, and Yang Wang. Boosting for learning multiple classes with imbalanced class distribution. In Sirth international conference on dala mining (ICDM pp. 592 602. IEFE, 2006.
Tobias Voigt, Roland Fried, Michael Backes, and Wolfgang Rhode. Threshold optimization for classification in imbalanced data in a problem of gamma-ray astronomy. Advances in Data Analysis and Classification, 8:195-216, 2014.
Boyu Wang and Joelle Pineau. Online bagging and boosting for imbalanced data streams. IEEE Transactions Knowledge and Data Engineering, 28(12):3355 :3333)33333366 3366, 2016.
Liwen Wang, Yicheng Yan, and Wei Guo. Ensemble online weighted sequential extreme learning machine for class imbalanced data, streams. In 2021 2nd International Symposium on Computer Engineering and Intelligent Communications (ISCEIC), pp. 81 86. IEEE, 2021.
Shuo Wang, Leandro L Minku, and Xin Yao. Dealing with multiple classes in online class imbalance lcarning. 2016.
In IJCAI, pp.
Shuo Wang, Leandro L Minku, and Xin Yao. A systematic study of online class imbalance learning with concept drift. IEEE transactions on neural networks and learning systems, 29(10)44802 4822-44400--481 2018
Zhaoyang Wang and Shuo Wang. Online automated machine learning for class imbalanced data streams. In 2023 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2023.
Frank Wilcoxon. Individual comparisons by ranking methods. In Breakthrrough in Statistics: Methodology and Distribution, pp. 196-202. Springer, 1992.
Yan Yan, Tianbao Yang, Yi Yang, and Jianhui Chen. A framework of online learning with imbalanced streaming data. In Proceedings of the A AATT Conference on Artificial Intelligence, volume 31, 2017.
17

---

Published in Transactions on Machine Learning Research (09/2024)
Chong Zhang, Kay Chen Tan, and Ruoxu Ren. Training cost-sensitive deep belief networks imbalance data problems. In 2016 international joint conference on neural networks (IJCNN), pp. 4362-4367. IEEF, 2016.
Chong Zhang, Kay Chen Tan, Haizhou Li, and Geok Soon Hong. A cost-sensitive deep belief network for imbalanced classification. IEEE transactions neural networks and learning systems, (0(1):109-122 2018.
Zhi-Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on knowledge and data engineering, 18(1):63-77, 2005.
Weiwei Zong, Guang-Boe Bin Huang, and Yiqiang Chen. Weighted extreme learning machine for imbalance learning. Neurocomputing, 101:229-22 222, 2013.
A Running Time Comparison
Since EA known for high time complexity, we conduct a runtime comparison to show the practicality of OECV along with the theoretical analysis in Soc. 3.4.4. All experiments are benchmarked on a server configured with IRt)l(R) Xeo Gold 6338 CPU @ 2.00GHz. The geometric mean of runtime across datasets is reported in the case of varying runtime scales across datasets. Specifically, suppose N datasets are used,
we report / VI t, where f; represents the runtime on the i-th dataset. Two key observations can be made from the results in Table 3. Firstly, while some methods exhibit significantly shorter runtimes, such as MUOB and OFCV-n, this comes at the expense of their inferior performance, as evidenced in Table 2(a). Secondly, our approach demonstrates remarkable efficiency, as OECV achieves the best rank with tolerable runtime compared to other SOTA methods. This validates the time efficiency and practicality of OECV despite integrating F.A.
B Performance Comparison in Terms of Balanced Accuracy
In Table 4 (a), we include performance comparison in terms of balanced sccuracy, complementary to the results in Section 4.2. We can see from Table 4 that in terms of balanced accuracy, OECV performs the best in 12 out of 30 datasets and the 2nd best in 8 data sets. Friedman lests (Demsar, 2006) at the significance level 0.05 reject HO with the p-value 4.21 x 10-3, showing that there is a significant difference between methods. The average rank of OECV 2.167, being the best. Post-hoe tests are then conducted to investigate whether OECV has a significant difference from the competitors, for which OECV is chosen as the control method. Post-hoe comparisons show that OECV significantly outperform all of the competitors except BEDCOE, where the p-value is 0.052, being only marginally higher than 0.05, We conjecture this is because the optimization objective is set to G-mean instead of balanced accuracy in OECV, making the algorithm not aware of this performance metric.
C Ablation Studies in Terms of Balanced Accuracy
Table 4 (b) shows the predictive performance of the three models in terms of balanced accuracy, complementary to the results in Section 4.3. Then, the three methods are compared to each other, with Wilcoxon signed rank tests (Wilcoxon, 1992) used to determine if there are significant differences between them.
We can see that in terms of balanced accuracy, the average rank of OECV (1.55) is better than that of OECV-n (2.233) and OECV-ea (2.217). Wilcoxon signed rank test rejects HO with p-value 0.042 and 4.98 x 4 respectively, meaning OECV is significantly superior to OECV-n and OECV-ea. This indicates that eliminating the EA strategy would significantly decline predictive performance in terms of balanced accuracy, showing its effectiveness.
We follow a similar procedure to compare OECV-ea and OECV-n. In terms balanced accuracy, the average rank of OECV-ca (2.217) better than OECV-n (2.233). Wilcoxon signod-rank test fails reject HO with p-value 0.838, meaning there is no significant difference between OECV-ca and OECV-n. This indicates that using extra samples in the buffer is solely insufficient to find significantly better cost vector. In other words,
18

---

Published in Transactions on Machine Learning Research (09/2024)
Table 3: Comparison between methods in terms of runtime in seconds. The geometric mean of runtime is shown in the last row.
Dataset Elec
AI-WSELM
MООB
MUOB
BEDCOE
OECV-n
OECV
OECV-ea
6.9
49.8=1.4
22.5+0.6
134.2+3.4
6.510.1
47.5+0.3
53.6+3.99
Abrupt
13.3+2.6
51.2=115
11.240.2
292.8420.3
6.540.3
81.443.4
75.5+1.2
Gradual
13.0=3.2
52.920.4
5.110.1
212.8#5.1
6.720.2
110.3420.5
74.9=1.4
Incrementall
15.1#3.2
49.7=0.2
16.2+0.4
383.445.8
6.5+0.2
101.5+299
76.1+1.2
Luxembourg
5.340.1
16.4=0.1
12.610.1
28.240..5
2.540.3
38.0+2.1
27.6100.7
NOAA
10.0+0.2
48.4-0.2
23.8+0.2
307.8+13.2
7.0+0.7
53.9+0.66
49.6+0.77
Ozone
8.0+0.11
38.5-1.7
6.340.3
139.4456.7
4.510.1
55.9
42.7=0.7
Airlines
12.9
49.0=0.9
25.8+0.3
364.246.4
7.340.5
52.8+0.6
47.1=0.4
Covtype
27.8+1..3
58.7=1.0
5.3+0.0
252.7+4.7
7.3+0.2
115.4+1.7
80.6+1100
Incremental2
17.5+0.5
62.4-0.7
5.6+0.0
379.0+7.1
7.2+0.2
107.5+3.2
75.1+0.9
Abalonel
2.400.0
24.2=0.4
4.0.0.22
73.413.1
3.310.1
25.110.4
22.7=0.3
Abalone2
16+0..0
16.0=0.4
2.5
52.2+1.6
2.40022
17.420.6
15.6
Carl
1.6+0.0
22.5=0.8
4.6+0.88
76.5+5.0
2.5+0.1
18.3+0.3
16.4+0.2
Car2
1.640.0
21.3=0.4
3.740.6
46.210.7
2.510.1
18.6+0..5
16.310.1
Kddcup
7.3+0.3
21.1=0.2
3.1+0.11
36.410.8
3.310.1
43.942.4
31.910..6
Kr
3.810.1
36.4=0.8
5.740.4
65.910.8
4.320.2
30.8
27.420.3
Segment
6.3+0.2
31.1-0.6
8.940.3
52.6+1.8
3.5+0.4
41.41888
29.4+0.8
Shuttlel
6.440.4
39.0=1.2
6.0.0.55
55.410.9
4.940.2
38.1
32.5+0.4
Shuttle2
3.820.2
22.9=0.6
4.5
31.910.8
2.840.6
21.240.3
17.7=0.2
Thyroid
2.0
10.1=0.1
1.010.1
37.1
1.240.3
12.240.8
8.520.3
Winl
1.5+0.1
7.7+0.2
0.9+0.1
19.4+0.3
1.0+0.2
8.4+0.3
6.8+0.1
Win2
3.6+0.2
17.0=0.9
3.0+0.2
64.6+11.2
2.340.2
18.6++0.5
15.5++0.2
Win3
1.40.11
8.120.4
1,240.4
23.241.1
1.040.1
7.5+0.3
6.410.1
Win4
3.310.1
16.7=0.4
2.240.4
37.2+1.0
2.1
17.0=#0.3
14.3+0.1
Win5
2.010.11
11.1=0.6
1.310.1
27.7#0.9
1.340.1
10.4+0.3
8.7
Yeastl
1.9+0.1
13.1-088
1.7+00.3
36.5+0.8
1.4+0.1
10.2+0.3
9.2+001
Yeast2
3.2+0.1
22.5=0.5
1.8:0..3
150.245.2
2.130.3
20.7+:0.4
15.8+0.11
Yeast3
3.1
17.6=0.3
4.7+0.2
57.5#1.0
2.1+0.1
15.7+0.2
14.5#0.1
Yeast4
3.1
17.7=0.5
2.4+0.2
40.410.6
2.340.6
15.6+0.2
14.3+0.2
Ycast5
3.0+0.1
17.4=0.4
2.3+0.3
42.5+0077
2.1+0.2
15.9+0.55
14.2+0.1
G-mean time
4.501
24.471
4.378
75.8
3.074
28.517
23.66
although our method uses extra data, this is not the determinative reason why OECV outperform SOTA methods.
D Continuous Performance Throughout Time
Figure presents performance comparisons over various time steps on two representative datasets in terms of G-mean and balanced accuracy. Similar patterns were observed in other datasets. We that OECV consistently outperforms most other methods across most time steps in terms of both G-mean and balanced accuracy. This demonstrates the continuous effectiveness of our approach in improving performance over time.
For ablation studics, we demonstrate continuous performance over time in Figure in terms G-mean and balanced accuracy. We notice removing the evolutionary cost vector strategy leads a continual decline in performance across most test steps. As result, assert that using EA is crucial in approach.
19

---

Published in Transactions on Machine Learning Research (09/2024)
Table Performance comparison in terms of balanced accuracy (%). Each entry is the meantstd performance across 10 runs. The best performance on each dataset highlighted bold, and the 2nd best performance is highlighted in italies. The last row lists the average ranks (avgRank) of each model across datasets each subtable. Part (a) reports the comparison between SOTA methods and the proposed OECV. A significant difference against OECV is highlighted in yellow. Part (b) reports the ablation results between variants of OECV.
(a) Performance comparison
(b) Ablation studies
Dataset
AI-WSELM MOOB
MUOB
BEDCOE
OECV
OECV-n
OECV
OBCV-ea
Elec
79.5
91.0#0.2
88.9#0.4
95.5+0.1
84.2+0.9
83.7=0.4
84.2+0.9
84.140.8
Abrupt
68.2+1.1+
65.940.6
67.8+0.6
63.7+0.3
64.6+0.6
64.4+0.7
64.6=0.6
64.7=0.8
Gradual
34.110.4
63.110.4
20.210.8
64.111.3
52.31110
59.210.9
52.311.0
50.611.11
Incrementall
48.5:10.6
58.610.4
58.110.6
54.7:0..4
48.211.3
47.911.1
48.211..3
48.011.11
Laxembourg
85.6+2.4
100.0+0.0
100.0+0.0
100.0+0.00
100.0+0.0
100.0
100.0+0.0
100.0+0.0
NOAA
72.0+007
66.040.6
64.9+0.6
69.0++0.6
73.2+00.5
73.1
73.2+0.5
73.0+0..5
Ozone
67.74:2.2
71.9411.3
78.3-0.6
71.11:10
1.6
73.6+1.4
77.4+1.6
7..74
Airlines
51.6+00.6
51.6+0.5
51.1+0.7
51.7
52.2+0.8
51.6#0.6
52.2+0..8
52.2=0.9
Covtype
21.1#2.9
70.6+0.4
16.4+3.0
70.
38.6+1.1
50.1#1.1
98.6#1.1
33.9+1.2
1ncremental2
30.110.5
49.310.4
25.21199
49.411.0
40.0.10.6
43.210.6
40.010.6
36.410.7
Abalone1
60.6.1..33
65.610.6
66.512.9
68.010.5
71.912.5
65.81114
71.912.5
07.212.7
Abalone2
61.0+33.3
51.6+0.2
45.2+3.4
56.2+0.2
54.2+3311
54.0++0.3
54.2+3.1
54.4+1.8
Carl
82.1422.5
53.741.11
62.4+6.0
57.4+2.2
79.0+2.1
79.1+2.4
79.0+2.1
78.8+1.7
Car2
96.712.6
77.340.5
81.213.7
77.7=1111
9..
94.9#1.1
96.211.0
95.310.9
Kddcup
83.517.3
100.0#0.0
96.113.3
100.0:0.00
100.0+0.0
100.0=0.0
100.0+0.0
100.010.0
Kr
94.511.6
94.4+0.7
91.0#1.6
90.6+10.7
94.7#1.2
91.820.7
94.711.2
98.511.2
Segment
98.710.4
98.910.1
93.310..6
99.010.0
99.1100.1
99.110.11
99.110.1
99.4110.1
Shuttle1
100.010..0
99.410.6
98.011.7
99.1110.9
99.910.0
99.910.0
99.910.0
99.9110.0
Shuttle2
99.4+0.1
99.6+0.0
99.8=0.1
99.7
09.0
99.7+0.0
99.7+0.00
99.6+0.0
Thyroid
54.644.6
53.942.8
34.7+0.0
63.9+1.9
75.0+1.55
73.1=2.7
75.0=1.5
77.1+2.1
Winl
62.6114.6
53.010.1
53.410.0
65.5
83.3
83.510.1
83.310.5
83.810.6
Win2
54.911177
51.010.9
65.0=2.5
52.6110.6
64.6122.0
60.320.4
64.612.0
59.7+1.2
Win3
52.4+2.8
51.8++0.8
51.5++3.5
52.1+110
8..
56.1+2.2
80.2+1.2
66.0+7.7
Wind
52.7++1.8
59.8+4.6
50.1+2.3
54.400.5
59.5+-4-4
51.2+1.3
59.5+444
51.1+2.2
Win5
55.545.00
53.342.0
19.4+1.3
19.6.1.33
58.5
63.812.7
58.513388
54.8-14.3
Yeast
60.1+3.7
56.740.4
53.1
57.1+1.0
59.0+7.7
53.2+0.8
59.0+7.7
51.6+0.7
Yeast2
45.7+2.7
39.4+2.6
10.8+1.7
01.2
39.9+1.1
40.0+1.7
19.9=1.1
36.4+1.7
Yeast3
82.311..0
89.310.3
90.1-1.0
87.8.10.3
87.91100
85.511.
87.911.0
87.0.0.7
Yeast4
76.714..8
88.910.8
84.617.4
76.712.0
83.414..3
73.813.0
83.414.3
78.512.7
Yeast5
75.3+2.4
73.5+1.1
65.8+4.3
66.1+119
8..8+1.6
85. 0..
86.8+1.6
83.2+-2.2
avgRank
3.1
3.1
3.717
2.917
2.167
2.233
1.55
2.217
E Hyperparameter Analysis
To balance the performance and computational cost, we introduced few hyperparameters in OECV. The role of each hyperparameter is straightforward and does not need heavy fine-tuning. In this section, we provide a detailed discussion on the sensitivity of population size, oversampling rate, buffer size, and the updating frequency of the cost. vector. We also investigate the influence of the pre-training ratio. Note the pre-training stage is necessary in our method and is added to make fair comparison since Li et al. (2023) requires pre-training setup. The ratio of 30% in the main experiments is chosen randomly and set to be the same for all compared methods without any tuning.
E.1 Population Size
We include a further experiment on the sensitivity of population size setting in OECV. Fixing the other original hyperparameter settings of OECV, manually alter only the population size (i.e., number of
20

---

Published in Transactions on Machine Learning Research (09/2024)
10-
64
DEDCOC
BECCGE
HOOE
N603
3000
(a) NOAA in G-mean
(b) Yeast5 in G-mean
wite 600LINO
24
CoCV
DEDV
HOCE
65-
MO0S
MU00
300
30.00
1000
2000
2300
3000
350
200
400
600
2000
(c) NOAA in class-wise acc.
(d) Yeast5 in class-wise acc.
Figure 5: Continuous performance comparison throughout time on representative datasets in terms of G-mean and balanced accuracy.
0BCV
1.0
09
04
00
1200
(a) Ozone in G-mean
(b) Yeast5 G-mean
1.00
1.0
0.0
0.00
0.20
000
1750
(c) Ozone in class-wise acc.
(d) Yeast5 in class-wise acc.
Figure 6: Continuous performance comparison ablation studies throughout time on representative datasets terms of G-mean and balanced accuracy.
21

---

Published in Transactions on Machine Learning Research (09/2024)
Table 5: Performance comparison between OECV with different population size in terms of G-mean (%) on the left and balancod accuracy (%) on the right. Each entry is the meantstd performance across 10 runs. The best performance on each dataset is highlighted in bold, and the 2nd best performance is highlighted in italics. The last two rows list the average ranks (avgRank) of each model across datascts, well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
Pop-25
Pop-50
Pop-100
Pop-200
Pop-25
Pop-50
Pop-100
Pop-200
Elec
83.7+77.8
83.947..
83.8=7.9
84.147.9
83.7+7.8
83.94
83.8=7.9
84.1:7.99
Abrupt
62.8:133.5
63.2.13.5
63. 13.14.3.6
63.11:3.6
62.8:33.5
63.2.13.5
63.11:3.6
63.11-3.6
Gradual
8.5+15.66
13.2+19.8
24.8+22.6
5.5=12.5
8.5+15.6
13.2+19.3
24.8++3.6
5.5+12.5
Incrementall
46.4=5.4
46.1+5.7
46.2#5.6
46.8+5.4
46.4+5.4
46.1=5.7
46.2=5.6
46.8=5.4
Luxembourg
100.0=0.0
100.0=0.0
100.0=0.0
100.0=0.0
100.0=0.0
100.0=0.0
100.0+0.0
100.0=0.0
NOAA
73.1=4.0
73.013.9
72.913.9
73.014.0
73.114.0
73.013.9
72.9=3.9
73.014.0
Ozone
77.115.6
77.815.9
77.316.0
77.0=5.99
77.115.6
77.815.9
77.316.0
77.015.99
Airlines
51.8+4477
51.7++4.7
51.8+4.8
51.8+4.77
51.8+4.7
51.7+4.7
51.8+4.8
51.8+4.7
Covtype
28.6+11.4
36.0+184
19.0+18.4
40.3+18.1
28.6+15.4
36.0+18.4
39.0+
40.3+18.1
Incremental2
15.6=19.5
17,2#19.4
18.5+17.1
20.5=19.3
15.6=19.5
17.2#19.4
18.5+17.1
20.5+19.3
Abalone1
67.8+16.6
66.8+16.8
67.4=16.7
71.9#15.3
67.8+16.6
66.8+16.8
67.4=16.7
71.9+15.3
Abalone2
88.7#24.4
51.8=20.2
38.2#22.2
38.1=20.2
38.7#24.4
51.8+20.2
38.2=22.2
18.12
Carl
78.21.9.9
78.119.8
78.519.9
77.6
78.219.9
78.119.8
78.519.9
17.6
Car2
96.1122.0
96.2.2.0
95.811.
95.911.7
96.112.0
96.2.2.0
95.8-1.9
95.911.7
Kddcup
100.0+0.0
94.9+10.9
100.0
98.1
100.0
94.9+10.9
100.0+0.1
98.1+4.5
Kr
94.7+2.8
93.843.7
93.6+3.7
95.1+22.1
94.7+2.8
93.8+3.7
93.6-3.7
95.1+2.1
Segment
09.120.6
99.120.6
99.210.6
99.0=0.6
99.120.6
99.120.6
99.210.6
09.0
Shuttlel
99.9=0.2
98.116.1
99.910.2
99.8=0.4
99.910.2
98.116.1
99.9
99.810.44
Shuttle2
99.7
99.611066
99.610.6
99.7-10.6
99.7-1.66
99.6-1.66
99.6-0.6
99.7.10.6
Thyroid
71.6119.2
74.4119.7
74.5
76.8
71.6119.2
74.4
74.31
76.8.10..3
Winl
80.6
84.5
10.3
81.9115.7
80.6118.5
84.5.13.8
10.4
81.9115.7
Win2
59.2+15.2
58.8+12.2
61.9+11.3
12.8
59.2+15.2
58.8+12.2
61.9+11.3
60.1+12.8
Win3
79.9+8.2
81.5-6.2
80.8+6.6
80.3=6.6
79.9+8.2
81.5+6.2
80.8+6.6
80.3+6.6
Win4
50.61.0.0
64.4111.9
46.6125.6
49.4-:25.5
50.6120.0
64.4111.9
46.6=25.6
49.4125.5
Win5
53.3+14.0
59.019.9
57.5
62.8
53.3114.0
59.019.9
57.5=13.3
62.8-100.4
Yeastl
28.0
21.14.2.6
19.24-26.1
53.64-22.7
48.04:29.4
21.14
19.2-26.1
53.6-
Yeast2
0.2.13.0
0.142..2
0.0=0.0
0.0+0.99
0.2433.0
0.14-2.2
0.0-1.00
0.04-0.9
Yeast3
87.8=3.2
86.5
86.6#4.0
87.2
87.8+3.2
86.5
86.6-4.0
87.2
Yeast4
81.7+13.8
86.915..6
86.5
89.7#4.2
81.7=13.8
86. 56.
86.5=9.7
89.7+4.22
Yeastō
8.8
86.6
86.2+5.0
85.5#5.0
86.5+5.8
86.6+4488
86.2=5.0
85.5#5.0
AvgRank
2.583
2.467
2.6
2.35
2.583
2.467
2.6
2.35
Time cost
x1
x1.11
x1.30
x1.73
x1
x1.11
x1.30
x1.73
individuals) to get four comparison methods: Pop-25 (original setting), Pop-50, Pop-100, Pop-200, standing for OECV with a population size of 25, 50, 100, and 200, respectively. The detailed comparison setting remains the same as in the main paper experiments. We report the performance in terms of G-mean in Table (a) and the performance in terms of balanced accuracy Table (b).
The result shows that increasing the population size would not boost performance significantly, however, the time complexity increases correspondingly. This can be because the problem scale is commonly small in online learning setting, mcaning a small number of individuals can alrcady find good enough cost vector. We conclude that OECV is not. sensitive to this hyperparaneter in a certain range. This is also why we only applied a relatively small population size in our main experiment: this setting can significantly improve performance compared to bascline methods while not incurring long updating delay. In offline learning, where the problem scale is much larger, especially when the number of classes is larger, a large population size should be applied. We leave the exploration of our method in offline setting to future work.
22

---

Published in Transactions on Machine Learning Research (09/2024)
Table 6: Performance comparison between OECV with different oversampling rate in terms of G-mean (%) on the left and balanced accuracy (%) on the right. Each entry is the mean performance across 10 runs. The best performance on each dataset is highlighted in bold, and the 2nd best performance is highlighted in italics. The last two rows list the average ranks (avgRank) of each model across datascts, well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
r=
==3
T=5
7=1
T=3
7 T=
Elec
83.84 7.4
83.917.7
83.7-7.8
64.3
84.4+6.7
84.2-6.8
Abrupt
62.3.13.4
62.64.3.6
62.8.13.5
61.1122.2
64.5+2.2
64.6:12.2
Gradual
8.5+15.5
8.5+15.6
8.5+15.6
52.3+4.7
52.3+4.6
52.3+4.6
Incrementall
46.2+5.6
46.2+5.6
46.4+5.4
47.9+4.3
48.0+4.2
48.2+4.1
Luxembourg
100.0=0.0
100.0#0.0
100.0=0.0
100.0=0.0
100.0=0.0
100.0=0.0
NOAA
72,81:4.0
72.913.9
73.114.00
73.013.8
73.013.6
73.213.8
Ozone
75.215.8
76.615.8
77.115.6
75.915.7
76.915.8
77.415.6
Airlines
51.6++5.0
51.744.7
51.8+4.77
52.143399
52. 14:377
52.2+3.6
Covtype
28.24:15.2
28.3+
28.6+15.4
38.7+13.9
38.5+13.9
13.6
Incremental2
19.7
15.9:19.5
15.6=19.5
40.1=6.0
40.0
40.0
Abalonel
63.0#19.2
66.8+16.7
67.8#16.6
69.5+8.8
71.3+8.0
71.947.9
Abalone2
29.8+24.9
37.1+24.4
38.7=24.4
51.9+9.8
53.6t9.6
54.2+9.8
Carl
77.611..8
78.119.9
78.2.9.9
78.817.0
79.0.7..1
79.017.0
Car2
89.21110.9
96.712.7
96.112.0
90.315.9
96.811.6
96.212.0
Kddcup
100.0=0.0
100.0+0.0
100.0+0.0
100.0
100.0=0.0
100.0+0.0
Kr
91.143.5
93.9+..7
94.7+22.8
91.5+3.1
94.0+2.6
94.7+2.7
Segment
99.410.5
99.210.6
99.1=0.6
99.4-0.55
99.210.6
99.1=0.6
Shuttlel
99.9-0.1
99.910.2
99.910.2
99.9:0.1
99.911.2
99.9
Shuttle2
99.7-1.66
99.710.66
99.7-10.6
99.7-0.66
99.7-1.66
99.7-10.6
Thyroid
72.8
12.0119.1
71.6
76.619.0
75.518.7
75.0
Winl
81.0-18.7
80.6118.5
80.6118.5
83.9
83.4115.2
83.2-15.2
Win2
56.7+15.4
15.3
59.2+15.2
63.4+7.6
63.0+7.5
64.6+7.8
Win3
80.5+8.4
80.847.6
79.9=8.2
81.0+8.4
81.247.8
80.2-8.3
Win4
48.81:209
50.2120.1
50.61200.0
59.6110.5
59.5
59.51
Win5
49.9114.4
53.1413.9
53.3114.0
57.3210.6
58.6110.2
50.3
Yeast:
12.14:11.0
27.6+29.1
48.04:2944
57.7417.5
59.1+18.0
Yeast2
0.2.3..0
0.2433.0
0.2.33.0
39.9
39.914.7
39.9
Yeast3
86.5+3.3
87.8+3.6
87.
86.7+2.9
87.9
87.9+2.8
Yeast4
80.1+13.7
79.5=14.7
81.7+13.8
82.147.9
81.6#8.3
83.4+7.9
Yeast5
84.4+8.5
83.9=7.8
86.5+5.8
85.8+7.4
84.6#6.9
86.8+5.6
avgRank
2.4
1.967
1.633
2.2
1.8
Time cost
x1
x3.43
x4.20
x1
x3.43
x4.20
E.2
Oversampling Rate
We can show the influence of the oversampling rate in OECV by manually altering only r get three comparison methods: comparison setting remains the same in the main paper experiments. We report the performance in terms of G-mean in Table 6 (a) and the performance in terms of balanced accuracy in Table 6 (b).
1 (i.e., no oversampling),
3, and 5 (original setting). The detailed
The result shows that increasing the oversampling rate would boost performance constantly, however, the time complexity also increases. Intuitively, a larger r enhances the sample diversity and allows a more accurato fitness evaluation but makes the fitness evaluation slower. One can use larger to get further performance improvement, but is good enough to make the fitness evaluation both accurate and efficient.
23

---

Published in Transactions on Machine Learning Research (09/2024)
Table 7: Performance comparison between OECV with different buffer size in terms of G-mean (%) on the left and balanced accuracy (%) on the right. Each entry the meantstd performance across 10 runs. The best performance on each dataset highlighted in bold, and the 2nd best performance is highlighted in italics. The last two list the average ranks (avgRank) of each model across datasets, as well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
[ =
[ 100
B 200
[ = 50
= 100
[ 200
Elec
87.
7.4
83.7+7.8
873
86.2
84.2=6.8
Abrupt
62.7:33.2
62.31334
62.8.13.5
64.6-12.3
61.2.12.11
64.6:12.2
Gradual
8.2+14.9
15.2
8.5+15.6
52.144.7
52.1+4.7
52.3+4.6
Incrementall
46.0+5.2
46.0+5.5
46.4+5.4
47.7t4.0
47.7t4.1
48.2+4.1
Luxembourg
100.0=0.1
100.0+0.0
100.0=0.0
100.0=0.1
100.0=0.0
100.0=0.0
NOAA
71.3::3.9
72.4133.8
73.114.00
71.413.6
32.513.5
73.213.8
Ozone
74.616.11
75.615.9
77.115.6
75.515.8
76.215.9
77.415.6
Airlines
51.8+4.88
52.144.8
51.8+4.7
52.2+3.7
52.5+3.7
52.2+-3.6
Covtype
26.31:14.2
27.5+
28.6+15.4
37.5+1344
37.9
38.6+13.9
Incremental2
15.5+19.0
15.3+19.3
15.6#19.5
39.0#5.6
39.5
40.0=5.9
Abalonel
58.9218.8
59.7+19.6
67.8=16.6
66.7=7.8
67.218.6
71.947.9
Abalone2
23.0#22.4
29.5+21.4
38.7=24.4
50.4=7.5
50.5+7.0
54.2+9.8
Carl
75.6.19.1
76.919.6
78.219.9
77.115.9
77.966.6
79.017.0
Car2
97.511..7
94.313.0
96.112.0
97.511.77
94.413.0
96.212.0
Kddcup
100.0=0.0
100.0+0.0
100.0+0.0
100.0=0.0
100.0=0.0
100.0+0.0
Kr
93.8+2.8
91.0+3.5
94.7+22.8
98.0+2.6
91.243.2
94.7+2.77
Segment
98.910.7
99.110.6
99.1+0.66
98.920.7
99.111..6
99.1+0..6
Shuttlel
99.9
99.910.2
99.910.2
99.9:0.22
99.911.2
99.9:1.22
Shuttle2
99.7-1.66
99.6.0.6
99.7-10.6
99.7-1.66
99.6-0.6
99.7-10.6
Thyroid
56.3111.7
69.
79.6
63.719.11
70.2111.2
75.0
Winl
79.9119.9
80.4118.9
10.5
83.2115.9
83.3
83.3115.2
Win2
56.1
55.2+15.6
59.2+15.2
64.21:.0
61.9+8.0
64.6+7.8
Win3
69.8+12.0
79.1
79.9+8.2
71.4+11.3
79.5+.9.0
8..
Win4
39.9124.2
50.0120.8
50.61200.0
56.6+10.4
60.4110.0
50.5110.2
Win5
52.1114.9
52.8113.9
53.3114.0
59.4=10.3
58.119..
58.5+10.3
Yeast:
11.74:28.1
42.3426.8
48.04:29.4
58.34 15.8
56.6+11.2
59.0+11.4
Yeast2
0.2.3..0
0.24:3.0
0.2.13.0
39.9
39.914.7
39.9
Yeast3
84.2#4.33
86.0+4.2
87.8+3.2
84.523.8
86.2+3.8
87.9+2.8
Yeast4
76.1
77.5+16.1
81.7+13.8
79.5+8.9
80.3+8.4
83.4+7.9
Yeast5
82.0+7.9
65.0+6.6
86.5+5.8
82.947.4
85.4+
86.8+5.6
avgRank
2.533
2.15
1.317
2.417
2.167
1.417
Time cost
x1
x1.28
x1.77
x1
x1.28
x
E.3
Buffer Size
We can show the influence of the buffer size [B] in OECV by manually altering only the buffer size to get three comparison methods: |B] 50, |B| 100, and [B] 200 (original setting). The detailed comparison setting remains the same in the main paper experiments. We report the performance in terms of G-mean in Table 7 (a) and the performance in terms of balanced accuracy in Table 7 (b).
The result. shows that increasing the bufler size would boost performance constantly, however, both the time complexity and storage complexity increase. Intuitively, a larger buffer makes more samples available to the cost vector and allows a more accurate fitness evaluation but makes the fitness evaluation slower. One can use a larger buffer to get further performance improvement, but [ 200 is good enough make the fitness evaluation both accurate and efficient.
24

---

Published in Transactions on Machine Learning Research (09/2024)
Table Performance comparison between OECV with different updating frequency of cost vector terms of G-mean (%) on the left and balanced accuracy (%) on the right. Each entry is the mean performance across 10 runs, The best performance on each dataset highlighted bold, and the 2nd best performance is highlighted in italics. The last two rows list the average ranks (avgRank) of cach model across datasets, well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
f=5
f f= 10
f=
f=
f= 10
f= 20
Elec
83.7-7.8
837
83.6+7.6
6..
84.116.7
84.11666
Abrupt
3.5
62.8:14.1
62.6-11.6
64.6-1..2
64.6412.0
64.5=2211
Gradual
8.5+15.6
4.5=8.1
11.0#13.6
52.3+4.6
50. 40.33
43.1=6.6
Incrementall
46.4=5.4
46.1+5.5
46.1
48.2+4.1
48.0t4.0
47.9=4.1
Luxembourg
100.0=0.0
100.0#0.0
100.0=0.00
100.0=0.0
100.0=0.0
100.0#0.0
NOAA
73.1-1..0
72.914.1
72.714.0
73.213.8
73.013.8
72.8=3.7
Ozone
77.1-5.66
77.115.8
76.825.8
77.415.6
77.315.8
77.1=5.8
Airlines
51.8+:4.7
51.8+4.7
51.7+448
52.2+3.6
52.243.6
52.1-3.7
Covtype
28.6+:5.4
28.1+15.7
37.8+18.4
38.6+
37.5+13.5
46.4+8.4
Incremental2
15.6=19.5
12.4=15.3
13.5#16.6
40.0=5.9
28.6+8.6
27.4=10.2
Abalonel
67.8
69.7#14.9
65.4=184
71.917.9
72.9
69.8=9.1
Abalone2
38.7=24.4
39.9+22.4
50.7=20.7
54.819.8
53.618.8
55.6+14.5
Carl
78.2.19.9
77.419.9
76.6
79.017.0
78.317.1
77.517.5
Car2
96.112200
96.311.7
97.111.0
96.212.0
96.411.7
97.211.00
Kddcup
100.0=0.0
100.0
95.6+9.7
100.0
100.0
96.1-8.1
Kr
94.7+22.8
96.1+2.3
1..
94.7+22.7
96.1+2.2
95.
Segment
99.1-:0.6
99.110.6
99.1
99.1-0.66
99.110.6
99.1+0.55
Shuttlel
99.
99.910.2
98.4=5.1
99.9:0.22
99.910.2
98.5=4.4
Shuttle2
99.7-1.66
99.710.6
99.6-10.6
99.7-0.66
99.7-1.66
99.6-0.6
Thyroid
71.611192
72.8
72.9119.6
75.019..1
76.2.19.5
76.219.7
Winl
80.5
79.9118.6
74.412488
83.3
82.7L15.
75.6
Win2
59.2=15.2
59.2+15.2
57.7+15.0
64.6+7.8
64.247.8
63.3-7.7
Win3
79.9+8.2
80.6+7.1
81.3+6.99
80.2+8.3
81.0+
81.7+7.1
Win4
50.61.20.0
46.7+20.3
63.7.15.9
59.5
56.319.3
67.2110.9
Win5
53.3=14.0
49.8
50.3
58.5+10.3
56.219.5
56,819.5
Yeast:
28.0-2994
25.6
16.0-221.2
59.0+18.4
57.04
55.1=17.3
Yeast2
0.2.13.0
0.0.L..6
0.0+
39.9
30.04:5.0
28.6=5.9
Yeast3
87.8=3.2
3..
87.1=3.3
87.9+2.8
87.9+
87.2-2.8
Yeast4
81.7+13.8
87.219.5
86.6+5.5
83.4+7.9
87.8+5.9
86.0
Yeast5
86.5-5.88
5.2
83.4+6.6
86.8+5.6
86.9t
84.0=6.2
avgRank
1.717
2.0
2.283
1.617
1.95
2.433
Time cost
x2.57
x1.36
x1
x2.57
x1.36
x1
E.4 Updating Frequency
We can show the influence of the updating frequency f of the cost vector in OECV by manually altering only the f to get three comparison methods: f = (original setting), f= 10, and = 20. The detailed comparison setting remains the same in the main paper experiments. We report the performance in terms of G-mean in Table 8 (a) and the performance in terms of balanced accuracy in Table 8 (b).
The result shows that decreasing the update would boost performance constantly, however, the time complexity increases. Intuitively, a smaller f makes the updating frequency more aligned with the classifier in the lower layer. This reduces the probability of updating delay and a sub-optimal solution. One can use smaller f get further performance improvement, but f 5 is good enough, and we pick this value save the runtime of OFCV.
25

---

Published in Transactions on Machine Learning Research (09/2024)
Table 9: Performance comparison between OECV with different pretrain ratio in terms of G-mean (%) on the left and balancod accuracy (%) on the right. Each entry is the meantstd performance across 10 runs. The best performance on each dataset is highlighted in bold, and the 2nd best performance is highlighted in italics. The last two rows list the average ranks (avgRank) of each model across datascts, well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
Ratio 0
Ratio =
Ratio = 0.3
Rafio 0
Ratio = Ratio 0.3
Elec
83.347.1 6.9
83.
8..0=665
83.8-6.77
64.2+6.8
Abrupt
65.419.6
61.848.2
6..8-3.5
67.0-7.66
61.413.11
64.642.2
Gradual
14.7=25.2
7.9415.4
8.5=15.6
52.6=10.8
51.3+4.77
52.3t4.6
Incrementall
51.1=9.7
48.2+5.4
46.4+5.4
53.0=8.8
49.6t4.6
48.2+4.1
Luxembourg
95.2+11.0
97.9+4.0
100.0+0.0
95.4+10.2
97.9+
100.0+0.0
NOAA
63.1155.7
69.514411
73.114.0
63.714.6
69.713.7
73.213.8
Ozone
77.219.1
75.31999
77.1=5.6
77.618.0
76.217.2
77.425.6
Airlines
50.9+4.3
49.943.7
51.8+4.7
51.2+3.7
50.3+3.4
5..2+3.6
Covtype
27.24.3.8
25.7+-20.5
28.6+15.4
35.8+26.8
35.7422.8
38.6+13.9
Incremental2
19.7=23.2
14.2420.5
15.6=19.5
10.9
41.317.2
40.0
Abalone1
12.9=10.6
67.1+9.8
67.8
73.419.8
69.0#5.6
71.077.9
Abalone2
16.7#15.4
51.8+12.2
38.7+24.4
51.9=9.1
54.917.6
54.249.8
Carl
56.717.5
71.517.1
78.219.9
57.217.1
72.116.6
79.017.0
Car2
77.7114.77
92.812.5
96.112.0
78.8110.9
92.912.5
96.212.0
Kddcup
98.9+2.5
97.4+10.1
100.0+0.0
98.9+2.4
97.9+5.99
100.0+0.0
Kr
91.5+10.7
93.94.3.9
94.7+2.8
91.7+10.1
94.04-3.5
94.7++2.7
Segment
93.4+10.3
98.810.6
99.110.66
93.749.3
98.810.6
99.1
Shuttlel
98.315.7
99.2+0.9
99.911.22
98.425.3
99.2+0.9
99.910.2
Shuttle2
99.7.0.6
99.6100.5
99.7.0.66
99.7-0.66
99.6410.5
99.7
Thyroid
51.7116.0
54.3122.3
71.6.19.2
55.719.77
74.717.3
75.0.9..1
Winl
71.1118.9
88.2111.9
80.61
74.4112.2
88.8111.0
83.3
Win2
62.2+11.3
49.8+17.5
59.2-15.5 15.2
63.3
55.4+7.1
64.6+7.8
Win3
62.8+20.7
27.6+28.8
79.9+8.2
64.4+19.0
53.9+12.4
80.2+8.3
Win4
46.5123.5
37.81-29.9
50.61100.0
55.6115.8
57.6113.2
59.5
Win5
60.4:13.4
29.9129.0
58.3=14.0
62.4-12.7
51.7=16.1
58. 10.3
Yeast1
64.119.6
12.6416..8
28.0-29.4
65.448.6
50.8:55.9
59.04
Yeast2
5.119.11
0.7477.0
0.243..0
25.4+10.5
39.04:5.3
39.914.77
Yeast3
86.0+8.1
85.2+6.5
87.8+3.2
86.317.4
85.4+6.0
87.9+2.8
Yeast4
92.248.8
93.412.99
81.7
92. 8.1
93.5+2299
83.4+7.9
Yeast5
78.5+18.5
50.7+33..
86.5+5.8
78. 16.9
65.2+13.7
86.8+5..6
avgRank
1.917
2.467
1.617
2.117
2.367
1.517
Time cost
x1.27
x1.17
x
x1.27
x1.17
x1
E.5
Pre-training Ratio
We can show the influence of the ratio of the dataset for pretraining in OECV by manually altering only the pretraining ratio to get three comparison methods: Ratio (begin from scratch), Ratio 0.1, and Ratio 0.3 (original setting). The detailed comparison setting remains the same as in the main paper experiments. Note the model evaluated only on the remaining stream after the pretraining stage. We report the performance in terms of G-mean in Table 9 (a) and the performance in terms of balanced accuracy in Table 9 (b).
The result does not. show an obvious relation between the pretraining ratio and performance in our mod. Indeed, this hyperparameter not an essential part of our method, and OECV can start from scratch (Ratio- 0). The hyperparameter is retained to align with the compared method Li al. (2023), and choosing a proper ratio and setting it equally to all compared methods is enough to make the comparison fair, as did in the main experiment.
26

---

Published in Transactions on Machine Learning Research (09/2024)
F More Experimental Comparison with Comparable Storage Budget
Except for the bascline AI-WSEIM (Qin et al., 2021), which also requires extra storage as the same as ours, the other three baselines MOOB, MUOB (Wang et al., 2016) and BEDCOE (Li et al., 2023), do not have this requirement. In this section, We compare with an additional baseline named Online SMOTE Bagging (SmoteOB) (Wang & Pineau, 2016) that also uses extra storage to demonstrate the superiority OECV when the compared method enjoys comparable or even higher storage requirements. The SmoteOB oversamples using training samples within sliding window, and we set the size of the sliding window to 100 for each larger than ours.
class (i.e., at least 200 samples to be stored for all classes), being equal
We report the performance in terms of G-mean in Table 10 (a) and the performance in terms of balanced accuracy in Table 10 (b). We can draw the observation that QECV outperforms SmoteOB with similar time cost. An analysis analogous to the main paper can explain that our method performs better in cases where few classes are presented, and the stream highly imbalanced. This illustrates that our method can not only outperform baselines with no extra storage requirement but also outperform baselines with extra storage used, verifying the effectiveness of OECV.
27

---

Published in Transactions on Machine Learning Research (09/2024)
Table 10: Performance comparison between OECV and SmoteOB in terms of G-mean (%) on the left and balanced accuracy (%) the right. Fach entry is the meantssd performance across 10 runs. The best performance on each dataset is highlighted in bold, and the 2nd best performance is highlighted in italics. The last two rows list the average ranks (avgRank) of each model across dalasels, well as the relative average time costs.
(a) G-mean
(b) Balanced accuracy
Dataset
OECV
SmoteOB
OECV
SmoteOB
Elec
83.7+0.9
87.5 + 0.4
84.2+0.9
87.9 + 0.5
Abrupt
62.8+0.66
51.4 + 13.0
64.6=0.6
62.5 + 0.9
Gradual
8.5+:4.2
8.7 + 4.6
47.4 52.3+1.0
Incrementall
46.41115
51.4 + 0.7
48.2+1.3
55.4 + 0.7
Luxembourg
100.0::0.0
99.6 + 0.2
100.010.0
99.6 = 0.2
NOAA
61.6 0.3 73.1+0..5
73.210.5
66.1 0.3
Ozone
77.1::1.7
77.7 + 1.7
77.411.
78.4 1.4
Airlines
51.8++0.9
35.6 1.9
49.2 52.2+0.8
Covtype
28.6+1..5
51.0 3.5
38.6+1.1
63.3
Incremental2
15.6+1.6
1.2
40.0+0.6
43.3
Abalonel
67.8114.3
57.1 1.7
62.8 71.912.5
Abalone2
38.717.6
41.0 + 1.9
54.213.1
57.0 1 0.9
Carl
78.24:2.2
89.8 +
79.0+2.1
90.2 + 1.8
Car2
96.141.0
78.8 + 2.7
96.2+1.0
81.7 -
Kddcup
71.9 100.0:0.0
0.7
78.8 0.6 100.0+0.0
Kr
94.7+1.3
88.2 + 1.6
94.7=1.2
89.4 1..414
Segment
99.110.1
95.3 1 0.5
99.110.1
95.4 1
Shuttle1
99.910.0
99.9 1 0.1
99.910.0
99.9 1 0.1
Shultle2
99.710.0
99.5 1 0.1
99.710.0
99.5 + 0.1 0.1
Thyroid
71.6+1.5
52.1 + 0.5
75.0+1.5
59.8 + 0.4
Winl
70.4 80.6+1.2
24.3
83.3+0.5
79.5 + 10.3
Win2
59.213.6
51.7 0.6
64.612.0
60.8 = 0.4
Win3
62.5 79.911.2
1.0
80.2+1.2
66.3 0.7
Wind
50.615.7
68.3 1
59.5144
72.2 + 2.1
Win5
53.317.1
78.7 1 0.4
58.513.8
80.0 1 0.3
Yeastl
48.0+18.9
55.5 + 1.3
59.0=7.7
58.3 + 1.0
Yeast2
0.2+0.4
9.8 7.4
39.9+1.1
44.1 + 1.2
Yeast3
87.8+1.0
84.7 + 0.5
87.9+1.0
86.6 + 0.5
Yeast4
81.715.7
93.1 + 0.2
83.414..3
93.2 + 0.2
Yeast5
86.511.7
83.0 + 1.0
86.8+1.6
83.6 + 0.9
avgRank
1.42
1.58
1.38
1.62
Time cost
x.33
X
x x1.2
x1
28


Reviews:
[{"review_id": "sruhDHjWUU", "reviewer": "Reviewer_gCJ4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nA simple (i.e., naive) hybrid approach to enhance the performance of online class imbalance learning.\n\nComparison on 30 datasets are performed.\n\nWeaknesses:\n\nThe proposed approach requires a huge buffer to keep validation data for evaluating the performance. I looks like contradicting to the standard setting of online learning.\n\nRelated to the above point, it is not clear whether the comparison with the baseline approaches is fair. Do they also use such huge memory?\n\nThough the performance is evaluated on 30 datasets, the analysis is missing. Therefore, when and why the proposed approach is promising/not promising over the other baselines are not clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses online class imbalance learning. The proposed approach employes the threshold moving method (Section 2), where the output of the model prediction is modified by a predefined weights in the standard approaches. In the proposed approach, this weights are optimized during the training by utilizing an evolutionary approaches. The proposed approach works as follows. The baseline classifier is trained independently of the weighting scheme, by using online stream data. The weight vector is optimized so that the validation performance is maximized, where the validation performance is measured by keeping online data in a buffer and evaluating the performance on them. The proposed approach is compared with several baselines on 30 datasets. The reported results show its promising performance over the compared approaches.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "P3 “ These methods heavily rely on ad hoc heuristics and hyperparameters, like safety degree (Jiang et al., 2021), sampling rate (Wang & Pineau, 2016), borderline factor, and disjunct factor (Ren et al., 2019), which potentially hinder optimal performance.” As I am not familiar with these approaches, I could not get from what is written how complicated it is to choose a reasonable parameter. As this is one of the main motivation of the proposed approach, please elaborate on it.\n\nP5 “The overall bi-level optimization problem is stated as  …” It is wrong. The lower level loss is defined by ell_1, whereas the upper level is defined by ell_2.\n\nMoreover, although the authors say that the resulting problem is a bi-level optimization problem, as the lower level optimization is independent of the upper level, it looks like just a single layer optimization with a dynamic objective where the objective is changing due to the training of the classifier. \n\nP6 “In other words, the model faces heavier penalties for misclassifying class i to class j as class j gets larger or class i gets smaller. ” I am confused here. If I understand correctly, the cost function is untouched and only the output of the model is modified by M.\n\nP8 “The buffer size |B| for OECV is fixed at 200 samples, and the oversampling rate is set to 3 for all datasets” It is contradicting the setting of online learning from streaming data described in Section 3.1. 200 out of the dataset size of at most 5000 (less than 2000 for for half of the datasets tested in this paper)  is definitely not a small buffer. And it is even enlarged by the factor of 3, which already amount to the size of the whole dataset of several test datasets. If one can have such a huge buffer, why not use thse buffer to learn a lower level classifier? Isn’t it possible to easily approximate the approaches for offline class imbalance learning by using such a buffer? Do the compared approaches listed in Section 4.1 use the same amount of memory? Please compare the memory usage and execution time as well as the performance.\n\nP9 How are the datasets splited to the training and test datasets? How many data for each? Doesn’t the proposed approach overfit to the \n\nP10 Though the proposed approach is compared with baselines on a large number of datasets, analysis is missing. When the proposed approach is promising over the other approaches and when it is not?", "broader_impact_concerns": "no concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WUPanfU4rO", "reviewer": "Reviewer_rcK9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper studies an important problem of online imbalanced learning, and proposes a reasonable mechanism to address this problem that relies on bi-level optimization using EA\n- The paper is in general well-written, structured and presented\n\nWeaknesses:\n- In the experiments, there seem to be some arbitrary decisions that are loosely justified. For example, the initial 30% samples of each stream are used for model initialization in an offline fashion. How is this rate decided? More importantly, what is the impact of this initial sample size and 'pre-training' mechanism in the overall effectiveness of the proposed method? The same question applied to other decisions such as the buffer size and the oversampling rate. Are these data-dependent, method-dependent? What is the impact these would have on the performance of OECV?\n- Some ablation studies seem to be missing, in particular those related to the hyper-parameters mentioned in the previous item\n- In the experiments, no analysis are provided in terms of the computational cost (memory or computation), with respect to other SOTA methods. How expensive, computationally, would running the proposed OECV be? This is extremely important considering the well-known cost of EA algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Online Evolutionary Cost Vector (OECV), a method that aims at handling imbalaced scenarios in online learning using evolutionary algorithm (EA). The paper proposes a dynamic EA to adaptively learn the cost vector in the presence of concept drift, which unifies EA and online class imbalance learning within a bi-level optimization framework by applying a cost vector. The first layer, an online classifier, offers a rough probabilistic prediction and updates by its own rule. The second layer, a cost vector, refines the rough prediction and undergoes a dynamic optimization process via dynamic EA. OECV performance is tested on 30 real-world datasets, in comparison to four state-of-the-art (SOTA) methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please add ablation studies for hyperparameters such as the samples used for initilization, buffer size and oversampling rate, and make some conclusions related to the impact of those on the performance of your method\n- Please justify all your technical decisions (such as those related to the hyperparameters mentioned in the previous item) as you present your main experiments\n- Please provide results on the computational cost of the proposed method compared to others", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yMoIxorTBN", "reviewer": "Reviewer_MURu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The use of evolutionary algorithms to cast the class imbalance problem as a hyperparameter optimization problem is an interesting and novel approach that can be applied to a wide range of performance metrics\n\n2. The experimental results show that the approach generally outperforms the SOTA baselines and the ablations studies show that the gains are indeed due to the use of evolutionary algorithms.\n\nWeaknesses:\n\n1. The mismatch in the update frequencies of the upper and lower-level optimization problems may lead to sub-optimal choices of the cost vector (since the classifier is updated more frequently).\n\n2. The oversampling approach appears to be a) susceptible to overfitting if the same samples from the buffer $\\mathcal{B}$ are used to train the classifier and then added to $\\mathcal{B'}$ to update the cost vector, and b) susceptible to noise in the class labels since the effect of erroneous labels will be amplified by the generated samples in (5) (if the original sample is corrupted then all the generated samples will also be corrupted since they have the same label).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel online learning framework that can handle class imbalance and concept drift by updating a cost vector using evolutionary algorithms. The authors model the online learning task as a bi-level optimization problem where the lower-level optimization involves minimizing a normal classification loss while the upper-level optimization involves learning a cost vector using evolutionary algorithms to correct classifier predictions in the presence of data drift. The algorithm is empirically validated on 30 real world datasets and compared with 4 SOTA baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please comment on the weaknesses above. I do not see them as dealbreakers but if my concerns are valid I would like to see them at least discussed in the paper.\n\n2. Consider adding examples of the kind of online performance metrics (especially non-differentiable ones) that could be considered, in paragraph 2 of the introduction.\n\n3. Can you explain how what is \"ad-hoc\" about the heuristics chosen by the related works cited in Section 2.1.1 and why these could hinder the performance?\n\n4. The cost-vector based correction for class imbalance appears to assume that the classifier is well-calibrated (misclassified samples will be corrected if their predicted class probabilities are low). Will this actually be the case in online settings where the classifier is trained with a small number of samples and so may become overconfident? Can any calibration approaches (like Platt scaling) be used to address this issue?\n\n5. There is a reference to Line 16 in Algorithm 2 in Section 3.4.1 but the algorithm block only has 15 lines. Please fix this.\n\n6.While the comparisons between OECV-ea and OECV as well as OECV-n and OECV-ea seem to suggest that extra data does not play a determinative role, it isn't clear if it is at all useful. Will it be possible to add a version which uses the evolutionary algorithm but does not use the extra data to see if having the extra data makes any material difference?\n\n7.Why is high correlation between standard deviation and class imbalance a good thing?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel approach to the class imbalance problem in online learning environments by introducing the Online Evolutionary Cost Vector (OECV). This method transforms the class imbalance challenge into a bi-level optimization problem, which combines an online classifier with a dynamic evolutionary algorithm to adaptively learn a cost vector. The approach is validated on 30 datasets, showing promising results against four state-of-the-art (SOTA) baselines.

Overall, the paper makes a valuable contribution to the field of online learning with class imbalance, particularly by incorporating evolutionary algorithms into the process. While the original paper raised several concerns, particularly around hyperparameter sensitivity, computational costs, overfitting, the authors have made significant efforts to address these issues raised by the reviewers. 

However, one reviewer still questions the large buffer size requirement, so it would be helpful for the authors to discuss this issue further in the final version.
Decision: Accept (poster)