ML Anthology

Scaling Multi-Label Conformal Prediction with Label Interactions for a Large Number of Labels

Ghassan Najjar, Céline Berthou, Héléna Vorobieva
ECML-PKDD 2025 pp. 111-128
doi:10.1007/978-3-032-06109-6_7 /ecmlpkdd/2025/najjar2025ecmlpkdd-scaling/

Abstract

Multi-label classification is the task where a single instance may belong to multiple classes simultaneously. The Label Powerset approach (LP) allows to apply Inductive Conformal Prediction (ICP) on multi-label classification tasks, by considering each label set as a single class and by assigning a non-conformity score to each of them. The construction of the prediction set $\mathcal {C}$ C requires selecting all the label sets –represented as binary vectors– that satisfy a given conformity criterion. Since the number of possible outputs is exponentially growing with the number of classes, constructing $\mathcal {C}$ C by testing the conformity criterion on all cases is unaffordable. We propose an algorithm that efficiently computes $\mathcal {C}$ C , even in the difficult case where the non-conformity score involves label interactions. It is based on a customized partial order relation on the set of binary vectors coupled with a monotone lower bound of the non-conformity score. Our tests confirm the algorithm’s efficiency, even with a high class count.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Najjar et al. "Scaling Multi-Label Conformal Prediction with Label Interactions for a Large Number of Labels." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025. doi:10.1007/978-3-032-06109-6_7

Markdown

[Najjar et al. "Scaling Multi-Label Conformal Prediction with Label Interactions for a Large Number of Labels." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025.](https://mlanthology.org/ecmlpkdd/2025/najjar2025ecmlpkdd-scaling/) doi:10.1007/978-3-032-06109-6_7

BibTeX

@inproceedings{najjar2025ecmlpkdd-scaling,
  title     = {{Scaling Multi-Label Conformal Prediction with Label Interactions for a Large Number of Labels}},
  author    = {Najjar, Ghassan and Berthou, Céline and Vorobieva, Héléna},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2025},
  pages     = {111-128},
  doi       = {10.1007/978-3-032-06109-6_7},
  url       = {https://mlanthology.org/ecmlpkdd/2025/najjar2025ecmlpkdd-scaling/}
}