Tree-Based Dynamic Classifier Chains
  Classifier chains are an effective technique for modeling label dependencies
in multi-label classification. However, the method requires a fixed, static
order of the labels. While in theory, any order is sufficient, in practice,
this order has a substantial impact on the quality of the final prediction.
Dynamic classifier chains denote the idea that for each instance to classify,
the order in which the labels are predicted is dynamically chosen. The
complexity of a naive implementation of such an approach is prohibitive,
because it would require to train a sequence of classifiers for every possible
permutation of the labels. To tackle this problem efficiently, we propose a new
approach based on random decision trees which can dynamically select the label
ordering for each prediction. We show empirically that a dynamic selection of
the next label improves over the use of a static ordering under an otherwise
unchanged random decision tree model. % and experimental environment. In
addition, we also demonstrate an alternative approach based on extreme gradient
boosted trees, which allows for a more target-oriented training of dynamic
classifier chains. Our results show that this variant outperforms random
decision trees and other tree-based multi-label classification methods. More
importantly, the dynamic selection strategy allows to considerably speed up
training and prediction.
