S.: Trading off speed and accuracy in multilabel classification

Abstract. In previous work, we devised an approach for multilabel clas-sification based on an ensemble of Bayesian networks. It was character-ized by an efficient structural learning and by high accuracy. Its short-coming was the high computational complexity of the MAP inference, necessary to identify the most probable joint configuration of all classes. In this work, we switch from the ensemble approach to the single model approach. This allows important computational savings. The reduction of inference times is exponential in the difference between the treewidth of the single model and the number of classes. We adopt moreover a more sophisticated approach for the structural learning of the class subgraph. The proposed single models outperforms alternative approaches for mul-tilabel classification such as binary relevance and ensemble of classifier chains.