Advanced search
1 file | 258.47 KB

An analysis of chaining in multi-label classification

Author
Organization
Abstract
The idea of classifier chains has recently been introduced as a promising technique for multi-label classification. However, despite being intuitively appealing and showing strong performance in empirical studies, still very little is known about the main principles underlying this type of method. In this paper, we provide a detailed probabilistic analysis of classifier chains from a risk minimization perspective, thereby helping to gain a better understanding of this approach. As a main result, we clarify that the original chaining method seeks to approximate the joint mode of the conditional distribution of label vectors in a greedy manner. As a result of a theoretical regret analysis, we conclude that this approach can perform quite poorly in terms of subset 0/1 loss. Therefore, we present an enhanced inference procedure for which the worst-case regret can be upper-bounded far more tightly. In addition, we show that a probabilistic variant of chaining, which can be utilized for any loss function, becomes tractable by using Monte Carlo sampling. Finally, we present experimental results confirming the validity of our theoretical findings.

Downloads

  • KERMIT-C1-WW26.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 258.47 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Dembczyński, Krzysztof, Willem Waegeman, and Eyke Hüllermeier. 2012. “An Analysis of Chaining in Multi-label Classification.” In Frontiers in Artificial Intelligence and Applications, ed. Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, and Peter Lucas, 242:294–299. Amsterdam, The Netherlands: IOS Press.
APA
Dembczyński, Krzysztof, Waegeman, W., & Hüllermeier, E. (2012). An analysis of chaining in multi-label classification. In L. De Raedt, C. Bessiere, D. Dubois, P. Doherty, P. Frasconi, F. Heintz, & P. Lucas (Eds.), Frontiers in Artificial Intelligence and Applications (Vol. 242, pp. 294–299). Presented at the 20th European conference on Artificial Intelligence (ECAI 2012), Amsterdam, The Netherlands: IOS Press.
Vancouver
1.
Dembczyński K, Waegeman W, Hüllermeier E. An analysis of chaining in multi-label classification. In: De Raedt L, Bessiere C, Dubois D, Doherty P, Frasconi P, Heintz F, et al., editors. Frontiers in Artificial Intelligence and Applications. Amsterdam, The Netherlands: IOS Press; 2012. p. 294–9.
MLA
Dembczyński, Krzysztof, Willem Waegeman, and Eyke Hüllermeier. “An Analysis of Chaining in Multi-label Classification.” Frontiers in Artificial Intelligence and Applications. Ed. Luc De Raedt et al. Vol. 242. Amsterdam, The Netherlands: IOS Press, 2012. 294–299. Print.
@inproceedings{3132158,
  abstract     = {The idea of classifier chains has recently been introduced as a promising technique for multi-label classification. However, despite being intuitively appealing and showing strong performance in empirical studies, still very little is known about the main principles underlying this type of method. In this paper, we provide a detailed probabilistic analysis of classifier chains from a risk minimization perspective, thereby helping to gain a better understanding of this approach. As a main result, we clarify that the original chaining method seeks to approximate the joint mode of the conditional distribution of label vectors in a greedy manner. As a result of a theoretical regret analysis, we conclude that this approach can perform quite poorly in terms of subset 0/1 loss. Therefore, we present an enhanced inference procedure for which the worst-case regret can be upper-bounded far more tightly. In addition, we show that a probabilistic variant of chaining, which can be utilized for any loss function, becomes tractable by using Monte Carlo sampling. Finally, we present experimental results confirming the validity of our theoretical findings.},
  author       = {Dembczy\'{n}ski, Krzysztof and Waegeman, Willem and H{\"u}llermeier, Eyke},
  booktitle    = {Frontiers in Artificial Intelligence and Applications},
  editor       = {De Raedt, Luc and Bessiere, Christian and Dubois, Didier and Doherty, Patrick and Frasconi, Paolo and Heintz, Fredrik and Lucas, Peter},
  isbn         = {9781614990987},
  language     = {eng},
  location     = {Montpellier, France},
  pages        = {294--299},
  publisher    = {IOS Press},
  title        = {An analysis of chaining in multi-label classification},
  url          = {http://dx.doi.org/10.3233/978-1-61499-098-7-294},
  volume       = {242},
  year         = {2012},
}

Altmetric
View in Altmetric
Web of Science
Times cited: