On the optimality of classifier chain for multi-label classification

Publication Type:
Conference Proceeding
Advances in Neural Information Processing Systems, 2015, 2015-January pp. 712 - 720
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
e671f9f6a41eabc8a4b720e62eddde5839ab.pdfAccepted Manuscript version118.91 kB
Adobe PDF
To capture the interdependencies between labels in multi-label classification problems, classifier chain (CC) tries to take the multiple labels of each instance into account under a deterministic high-order Markov Chain model. Since its performance is sensitive to the choice of label order, the key issue is how to determine the optimal label order for CC. In this work, we first generalize the CC model over a random label order. Then, we present a theoretical analysis of the generalization error for the proposed generalized model. Based on our results, we propose a dynamic programming based classifier chain (CC-DP) algorithm to search the globally optimal label order for CC and a greedy classifier chain (CC-Greedy) algorithm to find a locally optimal CC. Comprehensive experiments on a number of real-world multi-label data sets from various domains demonstrate that our proposed CC-DP algorithm outperforms state-of-the-art approaches and the CC-Greedy algorithm achieves comparable prediction performance with CC-DP.
Please use this identifier to cite or link to this item: