Multi-Label Adaptive Batch Selection by Highlighting Hard and Imbalanced Samples

Multi-label classification, leverages techniques that harness label correlations to streamline the learning process and navigate complexity through effective use of label relationships [31, 38]. Broadly, these methodologies can be categorized based on the complexity of label correlations they consider: first-order (e.g., BR, MLkNN [3, 37]), second-order (e.g., CLR [12]), and high-order correlations (e.g., CC, RAkEL [24, 33]).

Recently, deep learning has become a successful technique to solve the multi-label classification problem BP-MLL [36] is the first neural network architecture for multi-label learning, which develops a pairwise loss function to explore label dependencies. Deep embedding-based methods have demonstrated effectiveness by using deep neural networks to harmonize the latent spaces of features and labels. For instance, C2AE [34] embeds both feature and label data into deep latent space, employing a label-correlation sensitive loss function for end-to-end label output prediction. MPVAE [1] aligns probabilistic embedding spaces for labels and features, utilizing a decoder to model the joint distribution of output targets based on a multivariate probit model, emphasizing label correlation capture. Several works focus on exploiting deep neural networks to capture label correlations. For instance, PACA [16] creates a latent metric space regulated by label correlation, learning prototypes and metrics for each label, and employs normalizing flows for capturing class label characteristics. HOT-VAE [40] is an attention-based framework for multi-label classification, which innovatively learns high-order label correlations adaptive to feature changes. Additionally, due to the powerful representation learning capability of deep neural networks, it is quite natural to consider the problem of label-specific features in the deep learning scenario. For instance, CLIF [14] merges label semantics learning with the extraction of label-specific features, incorporating a graph autoencoder for semantic relations and a module for disentangling label-specific features. DELA [15] implements a perturbation-based technique for label-specific feature stability within a probabilistically relaxed expected risk minimization framework.

The imbalanced approaches proposed for MLC can be divided into three categories: sampling methods, classifier adaptation, and ensemble approaches [29]. Sampling methods aim to balance the label distribution by either oversampling [7, 19, 30] minority labels or undersampling [8, 23] majority ones, thus aiming to produce the more balanced versions of the training set before training. Classifier adaptation [11] techniques modify existing algorithms to make them more sensitive to label imbalance, often by adjusting decision thresholds or incorporating imbalance-aware loss functions. Ensemble approaches [20] combine multiple models or algorithms to leverage their collective strength, often incorporating mechanisms to specifically address label imbalance, such as weighted voting or selective ensemble training focused on underrepresented labels.

In the field of multi-label learning, the existing batch selection algorithms are only applicable to active multi-label learning tasks [5, 10], which are different from the scope of our multi-label classification. Active multi-label learning aims to progressively select unlabeled samples with the maximum information for manual annotation.

Hard samples are crucial for deep learning as they drive the model to refine its decision boundaries and improve generalization, making the learning process more effective and robust [26, 21, 17]. For example, OHEM (Online Hard Example Mining) [26] focuses on training with hard samples, identified by their high losses, and exclusively using these instances to update the model’s gradients.

Recent studies have pointed out that the performance of deep neural networks depends heavily on how well the mini-batch samples are selected. Meanwhile, it has been verified that neural networks converge faster with the help of intelligent batch selection strategies [6, 18, 27]. Techniques that select mini-batches based on sample difficulty have enhanced network precision and hastened training convergence. For instance, Online Batch Selection [22] boosts training efficiency by ranking samples according to their recent loss values and adjusting their selection probability with an exponential decay based on rank. This approach strategically prioritizes higher-loss samples for upcoming mini-batches. Further, Recency Bias [27] targets samples with fluctuating predictions, using recent history to gauge uncertainty and increase their sampling probability for upcoming batches. Ada-Boundary [28] prioritizes samples near the decision boundary where the model is uncertain, accelerating convergence by focusing on these critical samples. In multi-label settings, the complexity of measuring uncertainty for each label and aggregating these measures significantly increases computational demands. Additionally, the inherent sparsity and inter-label correlations in multi-label datasets can render traditional uncertainty-based selection methods less effective, resulting in suboptimal batch choices.

Let $\mathcal{X}=\mathbb{R}^{d}$ denote the input space and $\mathcal{Y}=\{l_{1},l_{2},\ldots,l_{q}\}$ denote the label space with q labels. A multi-label instance is denoted as $(\mathbf{x}_{i},Y_{i})$, with $\mathbf{x}_{i}\in\mathcal{X}$ as the feature vector and $Y_{i}\subseteq\mathcal{Y}$ indicating the relevant labels set. A binary vector $\mathbf{y}_{i}=[y_{i1},y_{i2},\ldots,y_{iq}]$ of dimension $q$, with elements in $\{0,1\}$, represents the set of labels $Y_{i}$. Here, $y_{ij}=1$ implies that $l_{j}\in Y_{i}$, and $y_{ij}=0$ indicates that $l_{j}\notin Y_{i}$. The objective of multi-label classification is to learn a prediction function $f:\mathcal{X}\rightarrow 2^{\mathcal{Y}}$ based on a dataset $D=\{(\mathbf{x}_{i},Y_{i})|1\leq i\leq n\}$. For any new example $\mathbf{x}_{u}\in\mathcal{X}$, the function predicts a subset of labels $f(\mathbf{x}_{u})\subseteq\mathcal{Y}$ as relevant.

In multi-label data, the metric $IRLbl$ [7] is commonly used to evaluate the level of imbalance for a particular label. Let $C_{j}^{b}$ be the count of samples for which the value of the $j$-th label is $b\in\{0,1\}$. Then the metric $IRLbl$ is defined as:

where $C_{max}^{1}$ denotes the greatest number of instances for any label that is assigned a value of 1. $MeanIR=\frac{1}{q}\sum_{j=1}^{q}IRLbl_{j}$ measures the average imbalance across all labels. Let $L_{m}$ represent the set of minority labels, defined by those labels whose $IRLbl_{j}$ exceeds the $MeanIR$. A label $l_{j}$ is classified as a minority if $IRLbl_{j}>MeanIR$ and as a majority otherwise.

Let $\mathbf{B}\in\mathbb{R}^{n\times q}$ denote a local imbalance matrix, where $B_{ij}$ signifies the local imbalance for instance $\mathbf{x}_{i}$ regarding label $l_{j}$, defined by the proportion of neighboring instances that belong to a different class.

where $\llbracket\pi\rrbracket$ represents the indicator function, which yields 1 if $\llbracket\pi\rrbracket$ is true and 0 otherwise, and $\mathcal{K}_{\mathbf{x}_{i}}$ represents the $k$-nearest neighbors ($k$NNs) of $\mathbf{x}_{i}$ based on the Euclidean distance.

The rank-based batch selection [22] sorts samples by loss, assigns sample selection probabilities based on rank, and selects mini-batches accordingly. Given a dataset of $n$ samples, the probability of selecting the $i$-th sample is:

where $r(\ell_{i})$ denotes the rank of the elements in ascending order within $\bm{\ell}$. Here $\bm{\ell}\in\mathbb{R}^{n}$ is defined as the vector with its $i$-th element representing the model loss of the $i$-th sample. Furthermore, $s_{e}$ represents the selection pressure, influencing the disparity in probabilities between the most and least significant samples.

In multi-label classification neural networks, the loss function usually involves several components. For example, the KL divergence is used by many models [1, 15, 40], to quantify the difference between the distribution of input and latent space. However, this loss function component is not directly related to the classification target. We instead utilize multi-label binary cross-entropy as the loss for rank-based batch selection. The rationale behind this choice and its effectiveness are thoroughly discussed and validated in Section 4.5.

To increase the likelihood of minority label instances being included in batches. we introduce a weight for each instance and incorporate it into $\bm{\ell}$. Let $\mathbf{S}\in\mathbb{R}^{n\times q}$ represent the matrix that captures local imbalance, defined by:

where normalization is applied to the local class imbalance of label $j$ for all instances to emphasize labels with fewer samples. Meanwhile, $\llbracket B_{i^{\prime}j}<1\rrbracket$ is used to exclude the influence of outliers. Further, let $\bm{\epsilon}\in\mathbb{R}^{n}$ be the imbalance vector, with $\epsilon_{i}=\sum_{l_{j}\in L_{m}}S_{ij}\llbracket S_{ij}\neq-1\rrbracket$ for each instance, accumulating local imbalance from non-noisy minority labels. Given a vector $\bm{\alpha}=\left[1,1,\cdots,1\right]\in\mathbb{R}^{n}$, the instance weight vector $\mathbf{w}\in\mathbb{R}^{n}$ is defined as: $\mathbf{w}=\bm{\alpha}+\bm{\epsilon}$. Then, upon combining with $\mathbf{w}$, the loss vector $\bm{\ell}$ can be rewritten as:

where $\odot$ represents the Adam product. It’s important to highlight that $\bm{\ell}$ is solely utilized for determining sample probability in the batch selection and does not contribute to the model’s gradient update process. All data has a chance to be selected during the training process to avoid introducing system bias

In Eq.3, the ranking-based method for sample selection probability tends to magnify small differences, resulting in significant (disproportionate) shifts in rankings and selection probabilities.

A feasible way to circumvent this is to exploit the quantization index [9] to smooth the rank value and limit it within the range of $n$. The quantization function $Q(\ell_{i})$ ¹¹1$\left\lceil\pi\right\rceil$ is upward rounding function is given by:

where $\Delta$ is defined as the adaptive quantization step size, equivalent to $\ell_{max}/n$. Here, $\ell_{max}$ represents the maximum element of $\bm{\ell}$. Combining $Q(\ell_{i})$, the probability of sample selection in multi-label adaptive batch can be rewritten as:

Figure 2 shows the workflow of the model training with adaptive batch selection, the red line indicates adaptability on a batch basis.

Before the training, the set $P$ is initialized to track each sample’s $p(i)$. Meanwhile, the model requires a continuous warm-up phase of $\gamma$ epochs to alleviate the instability caused by initial random initialization. In adaptive batch selection, each sample’s selection probability is linked to its quantization index $q$, calculated by $\bm{\ell}$ using an adaptive step size $\Delta$. Here, $\ell_{max}$ denotes the highest loss among all samples after the previous batch of training ends. After each batch, we adjust the quantization index based on $\bm{\ell}$ and then update $P$ by recalculating each sample’s $p(i)$.

It is well-known that label correlations are significant in multi-label learning. Label correlations can provide additional information, especially when some labels have insufficient training samples. By considering label correlation, we propose a chain-based adaptive batch selection method. First, we select the seed sample based on the selection probability set $P$. Given that $l_{j}$ is the seed sample’s associated label with the maximum $IRLbl$, we employ the adjacency matrix $\mathbf{A}$ to identify the $\left\lceil Card\right\rceil$ ($Card$ represents the label cardinality) labels most closely related to $l_{j}$ ²²2$\mathbf{A}\in\mathbb{R}^{q\times q}$ is the symmetric conditional probability matrix, which measures the co-occurrence relationship between labels, and the definition can be found in the appendix of supplementary materials., constituting the set $L_{c}$. We then define $D_{c}$ as the collection of instances linked to the labels within $L_{c}$. From the second sample onward, selection relies on a new probability set $P_{c}$, defined as $P_{cor}=\left\{p(i)\mid(\mathbf{x}_{i},\mathbf{y_{i}})\in D_{c}\right\}$. The selected sample then becomes the new seed sample for the next round of selection. This process is repeated until it reaches the batch size.

Adaptive batch selection methods typically meet Adam’s convergence standards, assuming their sampling distributions are strictly positive and gradient estimates unbiased. We theoretically demonstrate that our approach meets these key convergence conditions and the Proof can be found in the appendix of supplementary materials.

Table 2 shows the comparative average performance metrics of two different batch selection techniques, adaptive batch selection, and random batch selection, in different models. "Random" denotes the use of random batch selection with "shuffle=True", which refers to the batch selection used by these models. Adaptive batch selection consistently outperformed random selection, achieving the highest rankings across various evaluation metrics in most datasets. This advantage was particularly pronounced in datasets with high imbalance, such as Corel5k, rcv1subset1, rcv1subset2, rcv1subset3, as well as in those with a large number of labels, such as Corel5k, bibtex, and cal500. Adaptive batch selection significantly enhances the performance of embedding-based models like C2AE and models employing sophisticated neural networks, such as the CLIF. These results highlight our method’s broad effectiveness in deep learning models.

The results presented in Table 3, derived from the Wilcoxon signed-ranks test [2] at a 0.05 significance level, conclusively indicate that our adaptive batch selection method outperforms random batch selection with statistical significance.

In this section, we add a ranking batch selection based on BCE loss (named "Hard") as a comparison from the ablation perspective. Compared with the Adaptive method, Hard ignores imbalance weight $\mathbf{w}$ and does not employ the quantization index. Figure 3 illustrates the convergence curves of three distinct batch selection strategies, viewed from the perspectives of epochs, batches, and time, along with the validation set performance curves evaluated using Macro-AUC.

Epoch Perspective: As shown in Figure 3(a), the adaptive batch selection outperforms the other strategies in the scene and bibtex dataset, converging to lower losses with fewer epochs. Hard batch selection method shows improved convergence over random batch methods on the first three datasets but underperforms on the bibtex datatset. The latter may be due to the small difference in training sample loss, failing the loss ranking strategy between samples. The convergence curve of the adaptive batch selection proves the effectiveness of the quantization index. Specifically, we observe that training with random batch, the loss on the bibtex dataset plateaued after only a few epochs. In contrast, adopting adaptive batching allowed the model to break through this "bottleneck", leading to a continued decline in the loss convergence curve.

Batch Perspective: As shown in Figure 3(b), the adaptive batch shows less volatility and a steadier loss reduction during training. In contrast, the hard batch method is more volatile. The random batch method displays moderate volatility. The stability offered by adaptive batch selection is advantageous since large fluctuations, particularly upward ones in the last batch of an epoch, could disrupt the entire training epoch and adversely affect validation performance.

Time Perspective: As shown in Figure 3(c), to evaluate performance gains in training time, we measure the time required to achieve the same training loss levels (based on the minimum training loss achieved by a random batch). For example, on the scene dataset, random batch selection requires approximately 7.8 seconds to reach the minimum loss, while the adaptive batch selection only needs 5.7 seconds. On the scene, rcv1subset1, and bibtex datasets, the adaptive batch reduces training time by 14.1$\%$, 10.8$\%$, and 84.6$\%$, respectively. Although the adaptive batch increases training time by 37.2$\%$ on the yahoo-Business dataset, the overall convergence curve and evaluation metric results suggest that the adaptive batch method offers notable time performance benefits. Despite the extra time needed to compute and adjust the selection probability set during batch selection, this benefit persists.

Validation Perspective: As shown in Figure 4, adaptive batch selection notably enhances model performance. For the scene and rcv1subset1 datasets, all approaches achieve similar Macro-AUC by training’s end. Yet, the adaptive batch method attains peak validation epochs more swiftly than random selection strategies. More importantly, the adaptive batch significantly improved the validation set’s Macro-AUC on both the yahoo-Business1 and bibtex datasets.

Table 4 shows a comparative analysis of adaptive batch selection combining label correlation across different datasets.

The adaptive batch selection considering label correlations, denoted as "AdaC" performs better in datasets with a high cardinality of labels (cal500), but is ineffective in extremely sparse label spaces (Corel5k). This phenomenon arises from richer mutual information and label associations in high-cardinality settings, boosting the application of combing label correlation.

Binary cross-entropy (BCE) loss is a preferred choice for modeling due to its direct measurement of prediction accuracy and has been integrated into the model’s loss functions. Considering imbalanced losses like Asymmetric Loss [25], introduces significant computational overhead. In contrast, BCE loss offers a more streamlined approach, reducing the need for extra loss calculations and thereby conserving computational resources. In section 4.3, while verifying the effectiveness of adaptive batch selection from a global perspective, Figure 5 demonstrates from a more fine-grained perspective that the loss of minority label samples under adaptive batch selection can converge better, which provides evidence support for our approach of focusing on hard minority samples.

Initially, we explore the relationship between the model’s loss and BCE loss by analyzing the Pearson correlation coefficient. Figure 6(a) demonstrates a strong correlation between these two loss metrics. Furthermore, Figure 6(b) the convergence curve of adaptive batch selection with the model’s loss or BCE loss involved in computing $\bm{\ell}$. Both CLIF and DELA models incorporate BCE loss prominently in their loss functions, and giving it more weight than other loss components. This results in similar convergence patterns of the training loss to those seen with adaptive sample selection based on BCE loss. Conversely, C2AE, which does not include BCE loss in its loss function and prioritizes reconstruction loss, shows slower convergence in adaptive batch selection. This slower convergence may be due to the lack of correlation between samples with larger model losses and hard samples under classification tasks.

This section assesses key parameter impacts on our method, particularly selection pressure ($s_{e}$) and batch size variation. Refer to the supplementary appendix for detailed visuals. We conclude that: 1) $s_{e}$ may not expedite the convergence of training losses but improves performance metrics by batch setups. 2) the adaptive selection surpasses random selection for batch sizes 256 and 512, proving its effectiveness.

the index $Q(\bm{\ell}_{i})$ of each instance is bounded by:

Then, the lower bound of $p_{i}\supseteq P(x_{i}|D,s_{e},q)$ is formulated by

Thus, the sampling distribution of multi-label adaptive selection is strictly positive. To ensure a gradient estimate is unbiased, the expected value of the gradient estimate under the sampling distribution must equal the true gradient calculated across the entire dataset. Mathematically, this condition can be expressed as:

where $\nabla L$ is the gradient of the loss with respect to the model parameters, $\nabla L_{\text{true}}$ is the true loss computed over the entire dataset, and $E_{P(x_{i}|D,s_{e},q)}[\cdot]$ denotes the expectation over the sampling distribution. Further, we can assume that if every sample in the training set has a probability of being selected, then the gradient is unbiased. Let us consider the gradient estimate $\tilde{G}$ used in combination with the Adam optimizer. Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, computes adaptive learning rates for each parameter. In its essence, Adam maintains two moving averages for each parameter; one for gradients ($m_{t}$) and one for the square of gradients ($v_{t}$) respectively. These moving averages are estimates of the first moment (the mean) and the second moment (the uncentered variance) of the gradients. The unbiasedness of the gradient estimate $\tilde{G}$, when combined with Adam, can be articulated by analyzing the correction step applied to $m_{t}$ and $v_{t}$. Specifically, the bias-corrected first and second moment estimates are given by:

where $\beta_{1}$ and $\beta_{2}$ are the exponential decay rates for the moment estimates, and $t$ denotes the timestep. The correction factors $(1-\beta_{1}^{t})$ and $(1-\beta_{2}^{t})$ counteract the bias towards zero in the initial time steps, ensuring that $\hat{m}_{t}$ and $\hat{v}_{t}$ are unbiased estimates of the first and second moments. Therefore, given an unbiased gradient estimate $\tilde{G}$, the application of Adam’s bias correction guarantees that the adjusted gradients remain unbiased.