Decision functions for chain classifiers based on Bayesian networks for multi-label classification

• We study the expressive power of binary relevance and chain classifier with BN.
• We find polynomial expression for the decision functions of the two methods.
• We bound the expressive power of both methods.
• We prove that chain classifiers are indeed more expressive than binary relevance.

Multi-label classification problems require each instance to be assigned a subset of a defined set of labels. This problem is equivalent to finding a multi-valued decision function that predicts a vector of binary classes. In this paper we study the decision boundaries of two widely used approaches for building multi-label classifiers, when Bayesian network-augmented naive Bayes classifiers are used as base models: Binary relevance method and chain classifiers. In particular extending previous single-label results to multi-label chain classifiers, we find polynomial expressions for the multi-valued decision functions associated with these methods. We prove upper boundings on the expressive power of both methods and we prove that chain classifiers provide a more expressive model than the binary relevance method.