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.