Robust Multi-label Classification via Preference Learning

Abstract In this paper, we explore how multi-label classification (MLC) tasks can be cast into order structure learning. Our motivation for doing so is to exploit the very rich structure of the orders to improve and robustify MLC learning. We describe formally how MLC can be transformed into an order structure learning and prediction task, and then proceed to study the problem of predicting Bayes-optimal order structures. We then perform some experiments in settings where the use of order structures can be very beneficial: robust MLC in the presence of noisy and imbalanced labels, and making MLC predictions with partial abstention. Similar content being viewed by others Data Availability The 10 data sets used in the empirical study are all publicly available at https://cometa.ujaen.es/datasets/. The source code has been made available at https://github.com/hxtruong6/pre-order-for-mlc. Notes \(\llbracket \cdot \rrbracket \) is the indicator function, i.e., \(\llbracket A \rrbracket = 1\) if the predicate A is true and \(=0\) otherwise. An interesting discussion about the robustness of CLR can be found in (Mello et al., 2022). References Babbar, R., & Schölkopf, B. (2019). Data scarcity, robustness and extreme multi-label classification. Machine Learning,108(8), 1329–1351. https://doi.org/10.1007/s10994-019-05791-5 Barthelemy, J. P., Guenoche, A., & Hudry, O. (1989). Median linear orders: heuristics and a branch and bound algorithm. European Journal of Operational Research,42(3), 313–325. https://doi.org/10.1016/0377-2217(89)90442-6 Bogatinovski, J., Todorovski, L., Džeroski, S., et al. (2022). Comprehensive comparative study of multi-label classification methods. Expert Systems with Applications,203, Article 117215. https://doi.org/10.1016/j.eswa.2022.117215 Cheng, W., Hüllermeier, E., Waegeman, W., et al. (2012). Label ranking with partial abstention based on thresholded probabilistic models. In Proceedings of the 26th international conference on neural information processing systems (NIPS), pp 2501–2509, https://proceedings.neurips.cc/paper/2012/hash/fe2d010308a6b3799a3d9c728ee74244-Abstract.html Chzhen, E., Denis, C., & Hebiri, M. (2021). Minimax semi-supervised set-valued approach to multi-class classification. Bernoulli,27(4), 2389–2412. https://doi.org/10.3150/20-bej1313 Dembczyński, K., Waegeman, W., Cheng, W., et al. (2012). On label dependence and loss minimization in multi-label classification. Machine Learning,88, 5–45. https://doi.org/10.1007/s10994-012-5285-8 Denis, C., & Hebiri, M. (2017). Confidence sets with expected sizes for multiclass classification. Journal of Machine Learning Research,18(102), 1–28. http://jmlr.org/papers/v18/16-596.html. Elkan, C. (2001). The foundations of cost-sensitive learning. In Proceedings of the 17th international joint conference on artificial intelligence (IJCAI), pp 973–978, https://cseweb.ucsd.edu/~elkan/rescale.pdf Fürnkranz, J., & Hüllermeier, E. (2010). Preference learning and ranking by pairwise comparison. In: Preference learning. Springer, p 65–82, https://doi.org/10.1007/978-3-642-14125-6_4 Fürnkranz, J., Hüllermeier, E., Loza Mencía, E., et al. (2008). Multilabel classification via calibrated label ranking. Machine Learning,73, 133–153. https://doi.org/10.1007/s10994-008-5064-8 Grinsztajn, L., Oyallon, E., & Varoquaux, G. (2022). Why do tree-based models still outperform deep learning on typical tabular data? In: Proceedings of the 36th conference on neural information processing systems (NeurIPS) Track on Datasets and Benchmarks, pp 507–520, https://openreview.net/forum?id=Fp7__phQszn Ho, T.K. (1995). Random decision forests. In: Proceedings of 3rd international conference on document analysis and recognition (ICDAR), IEEE, pp 278–282, https://doi.org/10.1109/icdar.1995.598994 Hüllermeier, E., Fürnkranz, J., Cheng, W., et al. (2008). Label ranking by learning pairwise preferences. Artificial Intelligence,172(16–17), 1897–1916. https://doi.org/10.1016/j.artint.2008.08.002 Ke, G., Meng, Q., Finley, T., et al (2017). Lightgbm: a highly efficient gradient boosting decision tree. In: Proceedings of the 31st international conference on neural information processing systems (NIPS), pp 3149–3157, https://papers.nips.cc/paper_files/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html Masson, M. H., Destercke, S., & Denoeux, T. (2016). Modelling and predicting partial orders from pairwise belief functions. Soft Computing,20, 939–950. https://doi.org/10.1007/s00500-014-1553-9 Mello, L.H., Varejao, F.M., & Rodrigues, A.L. (2022). A worst case analysis of calibrated label ranking multi-label classification method. The Journal of Machine Learning Research,23(1):7585–7614. http://jmlr.org/papers/v23/19-918.html Mitchell, J.E., & Borchers, B. (2000). Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm. Springer US, Boston, MA, pp 349–366. https://doi.org/10.1007/978-1-4757-3216-0_14. Moral-García, S., & Destercke, S. (2022). Partial calibrated multi-label ranking. In: International conference on soft methods in probability and statistics. Springer, pp 287–294, https://doi.org/10.1007/978-3-031-15509-3_38. Moral-García, S., Mantas, C. J., Castellano, J. G., et al. (2022). Using credal c4. 5 for calibrated label ranking in multi-label classification. International Journal of Approximate Reasoning,147, 60–77. https://doi.org/10.1016/j.ijar.2022.05.005 Murphy, K.P. (2012). Machine learning: A probabilistic perspective. MIT Press, https://books.google.fr/books/about/Machine_Learning.html?id=NZP6AQAAQBAJ&redir_esc=y Nguyen, V.L., Destercke, S., & Masson, M.H., et al (2018). Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty. In Proceedings of the 27th international joint conference on artificial intelligence (IJCAI), pp 5089–5095, https://doi.org/10.24963/ijcai.2018/706 Nguyen, V. L., & Hüllermeier, E. (2021). Multilabel classification with partial abstention: Bayes-optimal prediction under label independence. Journal of Artificial Intelligence Research,72, 613–665. https://doi.org/10.1613/jair.1.12610 Nguyen, V.L., Yang, Y., & de Campos, C.P. (2023). Probabilistic multi-dimensional classification. In: Proceedings of the 39th conference on uncertainty in artificial intelligence (UAI), pp 1522–1533, https://proceedings.mlr.press/v216/nguyen23b.html Powers, D. (2011). Evaluation: From predcision, recall and f-factor to roc, informedness, markedness & correlation. Journal of Machine Learning Technologies 2(1):37–63. https://bioinfopublication.org/files/articles/2_1_1_JMLT.pdf Read, J., Pfahringer, B., Holmes, G., et al. (2021). Classifier chains: A review and perspectives. Journal of Artificial Intelligence Research,70, 683–718. https://doi.org/10.1613/jair.1.12376 Tarekegn, A. N., Giacobini, M., & Michalak, K. (2021). A review of methods for imbalanced multi-label classification. Pattern Recognition,118, Article 107965. https://doi.org/10.1016/j.patcog.2021.107965 Viappiani, P. (2015). Characterization of scoring rules with distances: application to the clustering of rankings. In: Proceedings of the 24th international conference on artificial intelligence (IJCAI), pp 104–110, https://www.ijcai.org/Proceedings/15/Papers/022.pdf Waegeman, W., Dembczyński, K., & Jachnik, A., et al. (2014). On the bayes-optimality of f-measure maximizers. Journal of Machine Learning Research,15:3333–3388. http://jmlr.org/papers/v15/waegeman14a.html Yiru, Z., Tassadit, B., Yewan, W., et al. (2021). A distance for evidential preferences with application to group decision making. Information Sciences,568, 113–132. https://doi.org/10.1016/j.ins.2021.03.011 Zhang, M. L., Li, Y. K., Liu, X. Y., et al. (2018). Binary relevance for multi-label learning: an overview. Frontiers of Computer Science,12(2), 191–202. https://doi.org/10.1007/s11704-017-7031-7 Zhang, M. L., & Zhou, Z. H. (2014). A review on multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering,26(8), 1819–1837. https://doi.org/10.1109/TKDE.2013.39 Acknowledgements This work was supported by the CPJ in Trustworthy AI (Ref. ANR-R311CHD). This work was also supported by the Office of Naval Research (ONR) and the Office of Naval Research Global (ONRG) under grant number N62909-23-1-2058. The views and conclusions contained herein are those of the authors only and should not be interpreted as representing those of the U.S. Government. Cassio de Campos thanks the support from the Eindhoven Artificial Intelligence Systems Institute, EU European Defence Fund via project KOIOS (EDF-2021-DIGIT-R-FL-KOIOS), and the Dutch Research Council (NWO) via project NGF.1609.242.024. Funding Vu-Linh Nguyen received funding from Agence Nationale de la Recherche; Grant ID ANR-R311CHD. Xuan-Truong Hoang received funding from Office of Naval Research Global; Grant ID N62909-23-1-2058. Cassio de Campos received funding from European Defence Fund; Grant ID EDF-2021-DIGIT-R-FL-KOIOS. Cassio de Campos received funding from Nederlandse Organisatie voor Wetenschappelijk Onderzoek; Grant ID NGF.1609.242.024. Van-Nam Huynh received funding from Office of Naval Research Global; Grant ID N62909-23-1-2058. Author information Authors and Affiliations Contributions V.L.N contributed to Conceptualization, Methodology, Software, Validation, Visualization, Funding acquisition, and Writing – original draft. X.T.H contributed to Methodology, Software, Validation, Visualization, and Writing – original draft. S.D. contributed to Conceptualization, Methodology, and Writing – review & editing. C.D.C contributed to Conceptualization, Methodology, and Writing – review & editing. V.N.H contributed to Conceptualization, Methodology, Funding acquisition, Supervision, and Writing – review & editing. Corresponding author Ethics declarations Conflict of interest We declare that we have no conflict of interest. Ethical Approval We declare that this research did not require Ethics approval. Consent for Publication All the authors of this manuscript consent to its publication. Additional information Editors: Zahraa S. Abdallah, Annalisa Appice, Przemyslaw Biecek, Andrea Tagarelli. Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Appendices Appendix A: Notation and Acronyms Some frequently used notations and acronyms are listed in Table 6. Appendix B: Representation Capacity In the following, we discuss the representation capacity of \(\mathcal {R}_{\text {par}}\) and \(\mathcal {R}_{\text {pre}}\) when being used to model the preference relations in the MLC setting. We shall also discuss the representation capacity of the CLRFootnote 2, which would be interpreted as either a linear order and a partial order of height 2 (or a bipartite graph) (Fürnkranz et al., 2008). 1.1 Partial Orders and Preorders The framework for modeling and predicting partial orders from pairwise belief functions (Masson et al., 2016) is generic and can be easily adapted to the probabilistic setting by basically re-interpreting the pairwise scores as probabilistic scores. Once this is done, the resulting approach can be interpreted as an instantiation of our framework where \(\mathcal {R} = \mathcal {R}_{\text {par}}\) and the BOO (7) is defined under the subset 0/1 accuracy (12) and the conditional probability is defined under the assumption of independence (Masson et al., 2016; Nguyen et al., 2018) on the pairwise preference relations. More precisely, for any \(R \in \mathcal {R}_{\text {par}}\), we define \(\varvec{p}(R \, | \,\varvec{x})\) by using (22). The problem of finding a BOO (7) under different metrics is then followed by what has been investigated in Sect. 3. We now illustrate some potential disadvantages of the use of partial order \(\mathcal {R}_{\text {par}}\) as order structures in the MLC setting, where we only consider the relation \(\lambda _i \bot _R \lambda _j\) rather than both \(\lambda _i \sim _R \lambda _j\) and \(\lambda _i \bot _R \lambda _j\). Intuitively, by considering that both the situations \((y_i,y_j)=(0,0)\) and \((y_i,y_j)=(1,1)\) correspond to the same relation, we tend to lower the chance of including strict preference (i.e., either \(\lambda _i \succ _R \lambda _j\) or \(\lambda _i \prec _R \lambda _j\)). To illustrate this effect, let us take an example where \(\mathcal {L}:=\{\lambda _1, \lambda _2\}\) and In this case, the optimal preorder would be \(\lambda _1 \succ \lambda _2\) with probability 0.49, while the optimal partial order is \(\lambda _i \bot \lambda _j\) with the probability 0.51. From an application perspective, it may also be quite useful to distinguish between the two situations \((y_i,y_j)=(0,0)\) and \((y_i,y_j)=(1,1)\). Let us consider the following (extreme) examples: if \(\lambda _1\) and \(\lambda _2\) encode two diseases, it might be reasonable to treat the two following patients (instances) differently If \(\mathcal {R} = \mathcal {R}_{\text {pre}}\), one would clearly recommend the first patient to go to the hospital for further diagnoses, but not the second patient. However, if \(\mathcal {R} = \mathcal {R}_{\text {par}}\), the two patients would receive the same recommendation/treatment. 1.2 Calibrated Label Ranking The output of CLR (Fürnkranz et al., 2008) can be interpreted as either linear orders or partial orders of height 2 (or bipartite graphs). Although the framework for learning BOOs proposed in Sect. 3 does not cover the approach for learning CLRs based on Ranking by pairwise comparison (RPC) procedure (Fürnkranz et al., 2008) as an instantiation, we would like to provide an extensive discussion on the notion of CLRs and the learning algorithm as it is one of a few existing preference learning approaches which are probabilistic and predict, for each instance, a partial order, i.e., closely related work to ours. While the initial framework of (Fürnkranz et al., 2008) considered a ranking procedure, it also provides the option to turn the resulting complete ranking into a partial order of height 2 (or a bipartite graph) by estimating a threshold \(s_0\) to separate the resulting ranking into two parts, called a set of relevant labels and a set of irrelevant labels, and ignore the strict preference relations \(\lambda _i \succ _R \lambda _j\) for those pairs of labels fall into the same set (Fürnkranz et al., 2008). By definition, the threshold \(s_0\) is the expected number of irrelevant labels associated with \(\varvec{x}\), i.e., In practice, this step was done by employing a Binary Relevance (BR) classifier, i.e., to extract a collection of binary classification data sets, one per label, and train a set of binary classifiers \(\{\varvec{h}_{0,k} \, | \,k \in [K]\}\), one per binary classification data set. For each \(\lambda _k \in \mathcal {L}\), the binary classifier \(\varvec{h}_{0,k}\) is trained on the training data set, which is created by annotating all the instances with \(y^k = 0\) as positive and the remaining instances as negative. Then, for each label \(\lambda _i\), a ranking by pairwise comparison approach is employed to estimate its expected position in the ranking. More precisely, for each label pair \((\lambda _i,\lambda _j)\), CLR follows the learning by pairwise comparison procedure (Hüllermeier et al., 2008) and creates the data set \(\mathcal {D}_{i,j}\) by annotating the instances within \(\mathcal {D}\) using \(c^{1,0}_{i,j}\), \(c^{0,1}_{i,j}\), \(c^{1,1}_{i,j}\) and \(c^{0,0}_{i,j}\), which respectively encode the events \((y^i, y^j) = (1, 0)\), \((y^i, y^j) = (0, 1)\), \((y^i, y^j) = (0, 0)\), and \((y^i, y^j) = (1, 1)\). Then all the instances with the class \(c^{1,1}_{i,j}\) and \(c^{0,0}_{i,j}\) are eliminated from \(\mathcal {D}_{i,j}\). Then any existing probabilistic classifier can be employed to learn \(\varvec{h}_{i,j}\), which produces pairwise information This would be analogous to defining, for each label pair \((\lambda _i,\lambda _j)\), the pairwise information If we interpret the quantity (with abuse of notation) i.e., the expected position of \(\lambda _i\) in the ranking (or the expected number of labels that are dominated by \(\lambda _i\)), CLR can be interpreted as a method that ranks the labels in decreasing order of the expected positions of the labels. This would then suggest a nice way to separate relevant labels from irrelevant, as done in (Fürnkranz et al., 2008), i.e., a label \(\lambda _i \in \mathcal {L}\) will be predicted as relevant if Unfortunately, as shall be illustrated below, CLR may fail to capture the preference relations that differ from the strict preferences. Let us take an example where Yet, the most probable preference relation should be \(\lambda _1 \sim \lambda _2\). The CLR would return the prediction \((y^1,y^2) = (0,0)\) (or the preference relation \(\lambda _1 \bot \lambda _2\)) because and \(s_0 = \left( \varvec{p}^{1,0}_{1,2} + \varvec{p}^{0,0}_{1,2}\right) + \left( \varvec{p}^{0,1}_{1,2} + \varvec{p}^{0,0}_{1,2}\right) = 0.51\). As another example, let us take Clearly, the most probable preference relation should be \(\lambda _1 \sim \lambda _2\). The CLR would return the prediction \((y^1,y^2) = (0,1)\) (or the preference relation \(\lambda _2 \succ \lambda _1\)) because and \(s_0 = \left( \varvec{p}^{1,0}_{1,2} + \varvec{p}^{0,0}_{1,2}\right) + \left( \varvec{p}^{0,1}_{1,2} + \varvec{p}^{0,0}_{1,2}\right) = 0.2\). Again, we see here some issues arising from the fact that CLR considers a framework with limited expressiveness, i.e., the space of complete rankings, when compared to ours. Appendix C: Proofs of Formal Results 1.1 Proof of Proposition 1 A proof is simple and is given for completeness. By definition, we have 1.2 Proof of Proposition 2 A proof is again simple and is given for completeness. Let \(T\in \{T_{\text {pre}}, T_{\text {par}}\}\) and \(\mathcal {R} \in \{\mathcal {R}_{\text {pre}}, \mathcal {R}_{\text {par}}\}\). By definition, we have The last equality holds because \(\llbracket z^l_{i,j} = \bar{z}^l_{i,j} \rrbracket z^l_{i,j} = 1\) iff \(z^l_{i,j} = \bar{z}^l_{i,j} = 1\). Note that the map \(T_{\text {pre}}: \mathcal {Y}\longrightarrow T_{\text {pre}}(\mathcal {Y})\) is bijective and \(\varvec{p}(\bar{R} \, | \,) = 0\) whenever \(\bar{R} \not \in T_{\text {pre}}(\mathcal {Y})\). Therefore, when \(\mathcal {R} = \mathcal {R}_{\text {pre}}\), \(|T^{-1}_{\text {pre}}(R)| = 1\), for any \(R \in \mathcal {R}_{\text {pre}}\). However, when \(\mathcal {R} = \mathcal {R}_{\text {par}}\), by definition, we have \(|T^{-1}_{\text {par}}(R)| \ge 1\). 1.3 Proof of Proposition 3 We first reformulate the target function in (20) as The constraint that, for any preorder \(R \in \mathcal {R}\), each label pair \((\lambda _i,\lambda _j)\) can only have one relation among \(\lambda _i \succ _R\lambda _j\), \(\lambda _j \succ _R\lambda _i\), \(\lambda _i \sim _R\lambda _j\) and \(\lambda _i \bot _R\lambda _j\) is translated into Furthermore, the transitivity property can be encoded using the relation \(r_{i,j} = z^1_{i,j} + z^4_ {i,j}\) and \(r_{j,i} = z^2_{j,i} + z^4_{j,i}\) if \(i < j\) and \(j < i\), respectively. Once the constraints are ensured, we can solve the equivalent problem of optimizing the log version of (C4), which is more computationally convenient, compared to optimizing the original target function (C4). Altogether, a most probable preorder (20) is determined by \(\hat{R} :=\{z^l_{i,j} \, | \,1 \le i < j \le K, 1 \le l \le 4\}\), which is the solution of the optimization problem (23). 1.4 Proof of Proposition 4 We reformulate the target function in (22) as The constraint that, for any preorder \(R \in \mathcal {R}\), each label pair \((\lambda _i,\lambda _j)\) can only have one relation among \(\lambda _i \succ _R\lambda _j\), \(\lambda _j \succ _R\lambda _i\), \(\lambda _i \sim _R\lambda _j\) and \(\lambda _i \nsucc _R \nprec \lambda _j\) is translated into Furthermore, the transitivity property can be encoded using the relation \(r_{i,j} = 1 - z^2_{i,j} - z^3_{i,j}\) and \(r_{j,i} = 1 - z^1_{i,j} - z^3_{i,j}\) if \(i < j\) and \(j < i\), respectively. Once the constraints are ensured, we can solve the equivalent problem of optimizing the log version of (C7). Altogether, a most probable partial order (22) is determined by \(\hat{R} :=\{z^l_{i,j} \, | \,1 \le i < j \le K, 1 \le l \le 3\}\), which is the solution of the optimization problem (29). Appendix D: Estimating Conditional Probabilities 1.1 Preorders When \(\mathcal {R} \subseteq \mathcal {R}_{\text {pre}}\), we use, for each label pair \((\lambda _i, \lambda _j)\), a probabilistic 4-class classifier, to estimate the conditional probabilities (16–19) from the training data. Inspired by what has been done in (Fürnkranz et al., 2008), for each label pair \((\lambda _i,\lambda _j)\), we the learning by pairwise comparison procedure (Hüllermeier et al., 2008) and creates the data set \(\mathcal {D}_{i,j}\) by annotating the instances within \(\mathcal {D}\) using \(c^{1,0}_{i,j}\), \(c^{0,1}_{i,j}\), \(c^{1,1}_{i,j}\) and \(c^{0,0}_{i,j}\). We then train a probabilistic 4-class classifier \(\varvec{h}_{i,j}: \mathcal {X}\longrightarrow \left\{ c^{1,0}_{i,j}, c^{0,1}_{i,j}, c^{0,0}_{i,j}, c^{1,1}_{i,j}\right\} \), which predicts, for each query instance \(\varvec{x}\): 1.2 Partial Orders When \(\mathcal {R} \subseteq \mathcal {R}_{\text {par}}\), we use, for each label pair \((\lambda _i, \lambda _j)\), a probabilistic 3-class classifier, to estimate the conditional probabilities (16, 17, and 21) from the training data. For each label pair \((\lambda _i,\lambda _j)\), we the learning by pairwise comparison procedure (Hüllermeier et al., 2008) and creates the data set \(\mathcal {D}_{i,j}\) by annotating the instances within \(\mathcal {D}\) using \(c^{1,0}_{i,j}\), \(c^{0,1}_{i,j}\), and \(c^{i=j}_{i,j}\), where \(c^{i=j}_{i,j}\) encode the event \(y^i = y^j\). We then train a probabilistic 3-class classifier \(\varvec{h}_{i,j}: \mathcal {X}\longrightarrow \left\{ c^{1,0}_{i,j}, c^{0,1}_{i,j}, c^{i=j}_{i,j}\right\} \), which predicts, for each query instance \(\varvec{x}\): Appendix E: Extension to Other Metrics 1.1 Cost-Sensitive Hamming Accuracies We can generalize the Hamming accuracy (11) as a family of cost-sensitive Hamming accuracies as follows: where \(L=4\) and 3 for \(\mathcal {R}_{\text {pre}}\) and \(\mathcal {R}_{\text {par}}\), respectively, and \(f_{i,j}(\cdot ,\cdot )\) can take 4 possibly different values, one per pair \(( z^l_{i,j}, \hat{z}^l_{i,j} ) \in \{0,1\}^2\). This can be seen as a direct extension of cost-sensitive accuracies for the binary classification task (Elkan, 2001). We have the following rather direct result. Proposition 5 Let \(\mathcal {R} \in \{\mathcal {R}_{\text {pre}}, \mathcal {R}_{\text {par}} \}\). For each query instance \(\varvec{x}\), a BOO (7) of the cost-sensitive Hamming accuracy (E10) is an order structure \(\hat{R} \in \mathcal {R}\) with the highest expected cost-sensitive Hamming accuracy, i.e., with \(L=4\) and 3 for \(\mathcal {R}_{\text {pre}}\) and \(\mathcal {R}_{\text {par}}\), respectively. Proof By definition, we have \(\square \) Clearly, the target function of (23) should be replaced with when finding a BOO of any cost-sensitive Hamming accuracy of the form (E10). 1.2 Other Metrics One might also think of generalizing the so-called family of confusion matrix-derived accuracies (Nguyen & Hüllermeier, 2021; Powers, 2011), which basically gives different rewards for being correct in predicting relevant labels and irrelevant labels, to our setting. This would be done by first introducing the notion of relevant binary relations, denoted by \(\mathcal {Z}_{\text {OS}} \subset \{z^l_{i,j} \, | \,1 \le l \le L, 1 \le i < j \le K\}\). Once \(\mathcal {Z}_{\text {OS}}\) is specified, for each pair of order structures \((R, \hat{R})\), one can construct the confusion matrix by replacing the notions of true positives (negatives) and false positives (negatives) by true relevances (irrelevances) and false relevances (irrelevances), respectively. This would allow one to generalize various confusion matrix-derived accuracies to our setting of predicting order structures. As an illustration, the \(f^{\beta }_{\text {MLC}}\)-measure (40) would be generalized to the setting of preference learning as follows: Similarly, the Jaccard index (41) would also be generalized to the setting of preference learning as follows: where However, the computational complexity of finding BOOs (7) of \(f_{\text {OS}}^{\beta }\) (E13), \(f_{\text {OS}}^{\text {Jac}}\) (E14), and other confusion matrix-derived accuracies remains to be investigated. Reminding that in the standard MLC setting, the divide-and-conquer strategy, which partitions the space of predictions into different groups whose local optimal solutions can be found efficiently by sorting the labels, has been employed to construct polynomial-time algorithms to find BOPs of the MLC \(F_\beta \)-measure (40) in the general setting of label dependence (Waegeman et al., 2014) and various confusion matrix-derived accuracies under the independence assumption (Nguyen & Hüllermeier, 2021). However, as discussed in Sect. 3.3.2, even under the independence assumption, just optimizing (7) in a pairwise way will generally not produce an order structure. Therefore, readers who might be interested in generalizing such algorithms to our setting should ensure the transitivity (3) when determining the local optimal solutions. Appendix F: Experimental Results 1.1 A Preliminary Study on the Runtime This section provides preliminary results on the runtime of our proposals when implemented using GLPK (CVXOPT) and MILP (SciPy), which are generic, open, and free ILP solvers. The runtime of our proposals and competitors, i.e., (BR, CC, CLR, ECC), on the Enron data sets with 53 labels is given in Table 7. The results are computed using 300 randomly selected instances, except for when PR-H-2 and PR-S-2 are implemented using GLPK, where the results are computed using 10 randomly selected instances. \(\mathrm{n/a}^{\dagger }\) means that the run-time exceeds the budget of our computing server. When implemented with MILP, classifiers that opt for pre-orders and partial orders require at most 2.430 seconds to search for optimal order structures. To see how runtime varies as the number K of labels increases, we compute runtime for synthetic MLC problems constructed from the Enron data set. For each number \(K \in \{6, 10, 14, 19, 25, 31, 37, 45\}\), we randomly select a subset \(\mathcal {L}_K \subset \mathcal {L}\), which consists of the 53 labels, to form a synthetic MLC problem with K labels. Then we randomly select a subset of instances and compute the average per-instance prediction time as done for the case \(K=53\), which is reported in Table 7. The results given in Table 8 suggest that the runtime of both GLPK and MILP exhibits polynomial-like trends. This would be partly due to the fact that our ILP problems have sparse constraint matrices. Moreover, GLPK and MILP benefit classifiers opting for partial orders, i.e., (PA-H-2, PA-H, PA-S-2, PA-S), and classifiers opting for pre-orders, i.e., (PR-H-2, PR-H, PR-S-2, PR-S), respectively. 1.2 Additional Results for Section 5 - Predicting binary vectors: Additional results for GpositivePse and PlanPse are given in Table 9. - Predictions with partial abstention: Additional results for GpositivePse and PlanPse are given in Table 10. 1.3 Results for Other Data Sets 1.3.1 Predicting Binary Vectors A summary of the results for predicting binary vectors is given in Table 11. See Tables 12, 13, 14, 15, 16, 17, 18 and 19. 1.3.2 Predictions with Partial Abstention A summary of the results for predictions with partial abstention is given in Table 20. See Tables 21, 22, 23, 24, 25, 26, 27 and 28. 1.4 Average Results The average results across the data sets with random forest are given in Fig. 29. It confirms that classifiers opting for preorders, especially (PR-H, PR-S), consistently outperform (BR, CC, CLR, ECC) in terms of \(f_{\text {MLC}}^{1}\) (40). Moreover, allowing predictions with abstention often leads to impressive improvement in terms of \(f_{\text {MLC}}^{1}\) (40). The results on abstention rates, i.e., ABS (49) and AABS (48), confirm that classifiers opting for preorders can gain competitive improvement in terms of \(f_{\text {MLC}}^{1}\) (40) with significantly lower abstention rates, compared to classifiers opting for partial orders, i.e., (PA-H-2, PA-H, PA-S-2, PA-S). We will only provide the average results across the data sets with LightGBM as the base learner. The results given in Fig. 30 suggest a few consistent trends. In terms of \(f_{\text {MLC}}^{1}\) (40), classifiers opting for preorders, i.e., (PR-H-2, PR-H, PR-S-2, PR-S), consistently outperform (BR, CLR). They are slightly better than CC on noisy data and are competitive with ECC. Allowing predictions with abstention often leads to promising improvement in terms of \(f_{\text {MLC}}^{1}\) (40), but is less impressive compared to the ones achieved with random forests as the base learner. Finally, the results on abstention rates, i.e., ABS (49) and AABS (48), confirm that classifiers opting for preorders can gain competitive improvement in terms of \(f_{\text {MLC}}^{1}\) (40) with significantly lower abstention rates, compared to classifiers opting for partial orders. For both base learners, a similar trend, but a bit less clear, is also observed for \(f_{\text {MLC}}^{\text {mac}}\) (46), which is another balancing metric. The results are omitted to save space. Rights and permissions Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law. About this article Cite this article Nguyen, VL., Hoang, XT., Destercke, S. et al. Robust Multi-label Classification via Preference Learning. Mach Learn 115, 211 (2026). https://doi.org/10.1007/s10994-026-07147-2 Received: Revised: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s10994-026-07147-2