1 Supplementary Description of LSDMLO↩︎

1.1 Optimization of Label-Specific Weights↩︎

The label-specific feature weights matrix is obtained by solving the following objective: \[\label{eq:lsd95obj95appendix} \mathop{min}\limits_{\mathbf{W}}\frac{1}{2}\left \| \mathbf{XW}-\mathbf{Y}\right \|_{F}^{2}+\lambda _{1} \left \| \mathbf{W}\right \|_{1} +\frac{\lambda _{2}}{2}tr(\mathbf{XW}\mathbf{\Lambda}(\mathbf{XW})^{\top})\tag{1}\] Although Eq.@eq:eq:lsd95obj95appendix is inherently convex, introducing the \(\ell_{1}\) norm-regularizer renders it a non-smooth optimization challenge. To effectively address this non-smoothness and tackle the \(\ell_{1}\) norm-regularization, We embraces the accelerated proximal gradient (APG) method [@APG]. Within the APG framework, the convex optimization problem Eq.@eq:eq:lsd95obj95appendix is reformulated as:

\[\Theta(\mathbf{W})=\mathop{min}\limits_{\mathbf{W}\in \mathcal{H}} \Phi_{1} +\Phi_{2} \quad\] \[\Phi_{1} =\frac{1}{2}\left \| \mathbf{XW}-\mathbf{Y}\right \|_{F}^{2}+\frac{\lambda _{2}}{2}tr(\mathbf{XW}\mathbf{\Lambda}(\mathbf{XW})^{\top}) \label{Phi1}\tag{2}\] \[\Phi_{2}=\lambda _{1}\left \|\mathbf{W}\right \|_{1}\] where \(\mathcal{H}\) is a real Hilbert space. \(\Phi_{1}\) is the smooth part of \(\Theta\) and satisfies the lipschitz continuity condition, i.e., \((\left \| \triangledown \Phi_{1}(\mathbf{W}_{1}) - \triangledown \Phi_{1}(\mathbf{W}_{2}) \right \|_{F}^{2} \leq L_{\Phi_{1}} \left \| \mathbf{W}_{1}- \mathbf{W}_{2} \right \| )\) ¹. The second term \(\Phi_{2}\) enforces sparsity on \(\mathbf{W}\) using \(\ell_{1}\) norm regularization with a coefficient \(\lambda_{1}\). Rather than minimizing \(\Theta(\mathbf{W})\) directly, proximal gradient algorithms minimize a series of separable quadratic approximations to \(\Theta(\mathbf{W})\), referred to as \(Q(\mathbf{W}, \mathbf{W}^{(t)})\): \[\begin{align} Q(\mathbf{W}, \mathbf{W}^{(t)}) &= \Phi_{1}(\mathbf{W}^{(t)}) + \nabla \Phi_{1}(\mathbf{W}^{(t)})(\mathbf{W} - \mathbf{W}^{(t)}) \\ &\quad + L_{\Phi_{1}} \lVert \mathbf{W} - \mathbf{W}^{(t)} \rVert_{F}^{2} + \Phi_{2}(\mathbf{W}) \end{align}\] Let \(\mathbf{G}^{(t)}= \mathbf{W}^{(t)}-\frac{1}{L_{\Phi_{1}}} \triangledown\Phi_{1}(\mathbf{W}^{(t)})\), where \(\mathbf{W}^{(t)}\) is the result of \(\mathbf{W}\) at the \(t\)-th iteration. \(\mathbf{W}\) can be optimized by:

\[\begin{align} \mathbf{W^*} &= \arg \min_\mathbf{W} Q(\mathbf{W}, \mathbf{W}^{(t)}) \\ &= \arg \min_\mathbf{W} \frac{L_{\Phi_{1}}}{2} \left\| \mathbf{W} - \mathbf{G}^{(t)} \right\|_{F}^{2} + \Phi_{2}(\mathbf{W}) \\ &= \arg \min_\mathbf{W} \frac{1}{2} \left\| \mathbf{W} - \mathbf{G}^{(t)} \right\|_{F}^{2} + \frac{\lambda_{2}}{L_{\Phi_{1}}} \left\| \mathbf{W} \right\|_1 \end{align}\]

The convergence rate can reduce to \(O(t^{-2})\) by employing the setting \(\mathbf{W}^{(t)} = \mathbf{W}_{t} + \frac{b_{t-1}-1}{b_{t}}(\mathbf{W}_{t}-\mathbf{W}_{t-1})\), where \(b_{t}\) satisfies \(b_{t+1}^{2} - b_{t+1} < b_{t}^{2}\). In each iteration, we address it by solving the following optimization problem. \[\mathbf{W}_{t+1}=S_{\varepsilon }\left [ \mathbf{G}^{(t)}\right ]=\mathop{\arg \min}\limits_{\mathbf{W}}\varepsilon \left \| \mathbf{W}\right \|_{1}+\frac{1}{2}\left \| \mathbf{W}-\mathbf{G}^{(t)}\right \|_{F}^{2}\] where \(S_{\varepsilon}\) is the soft-thresholding operator. For each \(w_{ij}\) and \(\varepsilon\) \(>\) 0, the soft-thresholding operation is defined as: \[S_{\varepsilon}[\omega]=\left\{\begin{matrix} \omega - \varepsilon & \quad \text{if} \quad \omega>\varepsilon\\ \omega -\varepsilon & \quad \text{if} \quad \omega<-\varepsilon\\ 0& \quad \text{otherwise} \end{matrix}\right.\] The accelerated proximal gradient algorithm to obtain optimal \(\mathbf{W}\) is summarized in Appendix Algorithm 1.

Proof of Lipschitz Continuity. To prove that \(L_{\Phi_{1}}\) is a Lipschitz constant means to demonstrate that the gradient of the function \(\Phi_{1}\) satisfies the following Lipschitz condition for any \(\mathbf{W}_{1}\) and \(\mathbf{W}_{2}\): \[\left\| \nabla \Phi_{1}(\mathbf{W}_{1}) - \nabla \Phi_{1}(\mathbf{W}_{2}) \right\|_{F}^2 \leq L_{\Phi_{1}} \left\| \mathbf{W}_{1} - \mathbf{W}_{2} \right\|_{F}\] Given \(\Phi_{1}\) as Eq 2 ,its gradient \(\nabla \Phi_{1}(\mathbf{W})\) can be calculated as: \[\begin{align} &\nabla \Phi_{1}(\mathbf{W}) = \\ &\mathbf{X}^{\top}(\mathbf{XW} - \mathbf{Y}) + \lambda_{2} \mathbf{X}^{\top}\mathbf{XW} \mathbf{\Lambda} \end{align}\] Therefore, for any \(\mathbf{W}_{1}\) and \(\mathbf{W}_{2}\), the Frobenius norm of the gradient difference can be expressed as: \[\begin{align} &\left\| \nabla \Phi_{1}(\mathbf{W}_{1}) - \nabla \Phi_{1}(\mathbf{W}_{2}) \right\|_{F}^{2} = \\ & \left\| \mathbf{X}^{\top}\mathbf{X}(\mathbf{W}_{1} - \mathbf{W}_{2}) \right\|_{F}^{2} + \lambda_{2} \left\| \mathbf{X}^{\top}\mathbf{X}(\mathbf{W}_{1} - \mathbf{W}_{2}) \mathbf{\Lambda} \right\|_{F}^{2} \end{align}\] Utilizing properties of matrix norms and the maximum singular value \(\sigma_{\max}\), we obtain: \[\begin{align} &\left\| \nabla \Phi_{1}(\mathbf{W}_{1}) - \nabla \Phi_{1}(\mathbf{W}_{2}) \right\|_{F}^2 \leq \\ &(\sigma_{\max}^{2}(\mathbf{X}^{\top}\mathbf{X}) + \lambda_{2} \sigma_{\max}^{2}(\mathbf{\Lambda}) \left\| \mathbf{W}_{1} - \mathbf{W}_{2} \right\|_{F}^{2} \end{align}\] indicating that the Lipschitz constant \(L_{\Phi_{1}}\) can be defined as: \[L_{\Phi_{1}} = \sqrt{\sigma_{\max}^{2}(\mathbf{X}^{\top}\mathbf{X}) + \sigma_{\max}^{2}\lambda_{2}(\mathbf{\Lambda})} \label{Lipschitz}\tag{3}\]

Computational Complexity. The time complexity of initializing \(\mathbf{W}_0\) and \(\mathbf{W}_1\) is \(O(nd^2 + d^3 + ndq + d^2q)\). The time complexity for calculating label correlation using cosine similarity is \(O(nq^2)\). The initialization of Lipschitz constant \(L_{\Phi_{1}}\) has a time complexity of \(O(d^3 + q^3)\). In the iteration step, the time complexity of calculating the gradient \(\phi_{1}\) is \(O(nd^2 + d^2q + ndq + n^2d + dq^2)\). Therefore, the computational complexity of Appendix Algorithm 1 can be represented as \(O\left(t(nd^2 + d^2q + ndq + n^2d + dq^2) + d^3 +q^3 \right)\), where \(t\) is the number of iterations.

1.2 Demonstrating the Advantage of LSDMLO↩︎

Appendix Figure 2 shows an example of retrieving neighbor instances based on different distances. Only 2 out of 5 neighbors of \(\mathbf{x}_0\) (in the purple circle) are associated with \(l_1\) in Figure (a), while all neighbors defined by the \(l_1\)-specific distance (in the red rectangle) are relevant to \(l_1\) in Figure (b). Similarly, \(l_2\)-specific distance also identifies five neighbors associated with \(l_2\) (in the blue rectangle) in Figure (c). Compared to Euclidean distance, label-specific distance demonstrates enhanced discriminative capability in identifying neighbors assigned to the same label.

We illustrate the advantage of label-specific distance-aware synthetic instance generation used in LSDMLO via the toy dataset in Figure 2. Let \(\mathbf{x}_0\) be the seed instance, and its neighbors defined by Euclidean and \(l_1\)-specific distances are extracted and zoomed in Appendix Figure 3. MLSMOTE, MLBOTE and MLSOL leverage Euclidean distance-based neighbors (\(\mathcal{K}_{\mathbf{x}_0}=\{\mathbf{x}_4, \mathbf{x}_5, \mathbf{x}_8, \mathbf{x}_{9}, \mathbf{x}_{11}\}\)) to create new synthetic instances. MLSMOTE with the ranking strategy assigns a label to a synthetic instance if more than half neighbors are relevant to that label. Thus, all synthetic examples in MLSMOTE are associated with \(l_2\), but none is relevant to \(l_1\). For MLBOTE, \(\mathbf{x}_5\) that has the same label vector as \(\mathbf{x}_s\) is the sole reference example, so all synthetic instances are confined in the line connecting \(\mathbf{x}_s\) and \(\mathbf{x}_5\), as shown in MLBOTE, leading to instance homogeneity and overfitting. MLSOL determines labels of synthetic instances based on their locations, but it may suffer the risk of invalid example generation. As shown in Figure MLSOL, the label vector of \(\mathbf{s}_2\) is the same as its closest instance \(\mathbf{x}_8\) (\([0,0]\)), but the creation of \(\mathbf{s}_2\) fails to alleviate the imbalance for both \(l_1\) and \(l_2\).

On the other hand, the proposed LSDMLO can tackle the limitations of the previous oversampling approaches. As shown in LSDMLO, LSDMLO generates \(\mathbf{s}_1\) and \(\mathbf{s}_3\) associated with both \(l_1\) and \(l_2\), influencing more labels than MLSMOTE and exhibiting more generalization than MLBOTE. Compared to MLSOL, LSDMLO avoids creating useless synthetic examples due to the high quality of the reference candidate set \(\mathcal{K}^1_{\mathbf{x}_s}=\{\mathbf{x}_3, \mathbf{x}_4, \mathbf{x}_5, \mathbf{x}_{7}, \mathbf{x}_{10}\}\). With regard to the synthetic instance \(\mathbf{s}_3\) created based on seed \(\mathbf{x}_s\) and reference \(\mathbf{x}_4\) that have different values with label \(l_2\), MLSOL does not assign \(l_2\) to it, because \(\mathbf{s}_3\) is closer to \(\mathbf{x}_4\) with Euclidean distance. In contrast, LSDMLO considers \(\mathbf{s}_3\) to be associated with \(l_2\), since its closest instance is \(\mathbf{x}_s\) assessed by \(l_2\)-specific distance. Figure l2-specific distance shows that \(\mathbf{s}_3\) is located in the region of \(\mathcal{K}^2_{\mathbf{x}_s}\) (blue rectangle). Therefore, the label assignment of LSDMLO is more effective than MLSOL to guarantee label consistency in the important feature subspace.

2 Supplementary Experiment Setup and Results↩︎

2.1 Hyper-Parameter Settings↩︎

All multi-label sampling methods and classification algorithms adopt parameter configurations recommended in the respective literature. In heuristic methods MLSMOTE_U, MLSMOTE_R, RHwRSMT, MLSOL, MLBOTE and DR-SMOTE, the number of neighbors (\(k\)) is set to 5. MLSMOTE_U and MLSMOTE_R employ ranking and union label assignment strategies respectively. For a fair comparison, the sampling ratio in MLROS, MLSOL, MLONC and AEMLO is set in the same way as in LSDMLO. In MLRUS, the sampling ratio is chosen in \(\{ 0.1, 0.15, \dots, 0.3\}\) for small and medium datasets (\(n \le 5000\)), and is selected from \(\{0.01,0.03, \cdots, 0.09\}\) for large datasets (\(n>5000\)). In MLBOTE, the self borderline sampling ratio \(\alpha_{s}\) is searched in \(\{0.01,0.02, 0.04,0.06,0.08,0.1\}\), cross-borderline selection threshold \(th_{c}=7\), the number of neighbors for borderline identification \(k_{b}=3\), the number of neighbors for borderline and reference selection \(k_{w}=5\), and the number of loops in resampling \(n_{lps}=10\). For AEMLO, the reconstruction loss weight parameters \(\alpha\) and \(\beta\) are searched in \(\{2^{-4}, 2^{-3}, \ldots, 2^{4}\}\).

The base binary and multi-class classifier in BR, RAkEL, CC and COCOA is the C4.5 decision tree. In MLkNN, the number of neighbors is 10. In RAkEL, the size of label subset is 3, and the number of ensemble subsets is \(2q\). The number of coupled labels in COCOA is set as \(\min(q-1,10)\). In C2AE, the learning rate is \(10^{-5}\), the batch size is 32, and the number of epochs is 100.

2.2 Comparison with Learning Label-Specific Features↩︎

Similar to learning label-specific features models [@LLSF], the optimal feature weight matrix \(\mathbf{W}\) obtained in Appendix Algorithm 1 not only indicates the discrimination of features to each label but also can be employed as a multi-label classifier to predict an unseen instance \(\mathbf{x}\) as \(\mathbf{\hat{y}}=\mathbf{W}\mathbf{x}\). We denote the \(\mathbf{W}\)-based classifier as LLSF for simplicity, and its performance is obtained using the same experiment setup described in Section IV-B. As shown in Appendix Figure 4, compared with LLSF, LSDMLO with the two multi-label base learners achieve higher Macro-F results in most cases, indicating the effectiveness of the combination label-specific distance and multi-label oversampling. LSDMLO with COCOA performs better for the smaller dataset (scene), while LSDMLO with C2AE is more effective on larger scale datasets (Corel5k and yahoo-Business1). This shows the flexibility of sampling methods that can be incorporated with the proper multi-label base learner according to the specific characteristics of the dataset.

2.3 Parameter Analysis↩︎

Here we analyze the sensitivity of sampling ratio \(p\). As shown in Figure 5, The performance of LSDMLO improves as \(p\) increases, which demonstrates the effectiveness of augmenting useful synthetic instances on addressing the imbalance issue in multi-label data. However, when \(p\) becomes too large, the excessive generation of synthetic instances may alter the original distribution of the data, leading to the performance decline of LSDMLO. In general, setting \(p\) around 0.06-0.08 is an acceptable choice for larger datasets.

Trade-off parameters \(\lambda_{1}\) and \(\lambda_{2}\) impact the sparsity of \(\mathbf{W}\). Because only features with non-zero weights contribute to label-specific distance computation, the number of non-zero elements in row \(\mathbf{w}_{\cdot j}\) is equal to the number of relevant features for label \(l_j\). Figure 6 illustrates the influence of \(\lambda_{1}\) and \(\lambda_{2}\) on feature sparsity, i.e., the number of features used for label-specific distance calculation. An ascending trend in \(\lambda_{1}\) stresses on \(l_1\) norm of the weight matrix, leading to more sparse features. On the other hand, larger \(\lambda_{2}\) emphasizes the label correlation regularizer, mitigating the sparsity of features.

Furthermore, we analyze the influence of feature sparsity on the performance of LSDMLO combined with COCOA on rcv1subset1 and Corel5k datasets. As shown in Figure 7, the performance increases as the number of label-specific features decreases. The sparser features exclude the impact of irrelevant features, thereby projecting into a more accurate subspace to measure distances between examples. The peak result approaches when 56% and 28% prominent features are retained for label-specific distance calculation on rcv1subset1 and Corel5k datasets, respectively. The performance starts to deteriorate when features become extremely sparse, because filtering more features would overlook potentially crucial information.

2.4 Sampling Time Comparison↩︎

The sampling times of multi-label sampling methods on rcv1subset1 and Corel5k datasets are shown in Figure 8. To ensure a fair comparison, each oversampling method generates \(0.1 \times n\) synthetic instances, and MLRUS deletes \(0.1 \times n\) examples.

MLROS and MLRUS are the two fastest methods, duplicating and removing instances based on label statistics. Two variants of MLSMOTE and MLONC, which involve searching for \(k\)NNs from each minority instance set, exhibit slower sampling procedures than MLROS and MLRUS. In contrast to MLSMOTE, MLSOL necessitates retrieving the nearest neighbor from the entire dataset, resulting in a higher time cost. DR-SMOTE requires identifying reference samples with different label sets for each seed instance, which introduces additional distance calculations and results in higher sampling time than MLSMOTE and MLSOL. RHwRSMT, which decouples some high-scramble instances, consumes more time than MLSMOTE. Most sampling time consumed by LSDMLO is dedicated to acquiring \(\mathbf{W}\) and measuring label-specific nearest neighbors. Although label-specific distance involves calculating partial features, the iterative APG algorithm makes LSDMLO slower than most neighbor-based sampling approaches. AEMLO requires training a deep autoencoder to learn latent representations before generating synthetic instances, which introduces a substantial computational overhead and makes it significantly much slower than LSDMLO. MLBOTE is the most time-consuming method, as it computes the neighborhood for each label when determining the instance type.

2.5 Detailed Results of Sampling Methods↩︎