Classifier chains
Classifier chains is a machine learning method for problem transformation in multi-label classification. It combines the computational efficiency of the Binary Relevance method while still being able to take the label dependencies into account for classification. Problem transformation. Several problem transformation methods exist. One of them is the Binary Relevance method (BR). Given a set of labels formula_1 and a data set with instances of the form formula_2 where formula_3 is a feature vector and formula_4 is a set of labels assigned to the instance. BR transforms the data set into formula_5 data sets and learns formula_5  binary classifiers formula_7 for each label formula_8. During this process the information about dependencies between labels is not preserved. This can lead to a situation where a set of labels is assigned to an instance although these labels never co-occur together in the data set. Thus, information about label co-occurrence can help to assign correct label combinations. Loss of this information can in some cases lead to a decrease in classification performance. Another approach, which takes into account label correlations, is the Label Powerset method (LP). Each combination of labels in a data set is considered to be  a single label. After transformation a single-label classifier formula_9 is trained where formula_10 is the power set of all labels in formula_11. The main drawback of this approach is that the number of label combinations grows exponentionally with the number of labels. For example, a multi-label data set with 10 labels can have up to formula_12 label combinations. This increases the run-time of classification. The Classifier Chains method is based on the BR method and it is efficient even on a big number of labels. Furthermore, it considers dependencies between labels. Method description. For a given a  set of labels formula_1 the Classifier Chain model (CC) learns formula_5 classifiers as in the Binary Relevance method. All classifiers are linked in a chain through feature space. Given a data set where the formula_15-th instance has the form formula_16 where formula_17 is a subset of labels, formula_18 is a set of features. The data set is transformed in formula_5 data sets where instances of the formula_20-th data set has the form formula_21. If the formula_20-th label was assigned to the instance then formula_23 is formula_24, otherwise it is formula_25. Thus, classifiers build a chain where each  of them learns binary classification of a single label. The features given to each classifier are extended with binary values that indicate which of previous labels were assigned to the instance. By classifying new instances the labels are again predicted by building a chain of classifiers. The classification begins with the first classifier formula_26 and proceeds to the last one formula_27 by passing label information between classifiers through the feature space. Hence, the inter-label dependency is preserved. However, the result can vary for different order of chains. For example, if a label often co-occur with some other label , then only instances of the label which comes later in the chain will have information about the other one in its feature vector. In order to solve this problem and increase accuracy it is possible to use ensemble of classifiers. In Ensemble of Classifier Chains (ECC) several CC classifiers can be trained with random order of chains (i.e. random order of labels) on a random subset of data set. Labels of a new instance are predicted by each classifier separately. After that, the total number of predictions or "votes" is counted for each label. The label is accepted if it  was predicted by a percentage of classifiers that is bigger than some threshold value.