Multi-label classification

Problem transformation methods

• Transformation into binary classification problems: the baseline approach, called the binary relevance method, amounts to independently training one binary classifier for each label. Given an unseen sample, the combined model then predicts all labels for this sample for which the respective classifiers predict a positive result. Although this method of dividing the task into multiple binary tasks may resemble superficially the one-vs.-all and one-vs.-rest methods for multiclass classification, it is essentially different from both, because a single classifier under binary relevance deals with a single label, without any regard to other labels whatsoever. A classifier chain is an alternative method for transforming a multi-label classification problem into several binary classification problems. It differs from binary relevance in that labels are predicted sequentially, and the output of all previous classifiers are input as features to subsequent classifiers. Classifier chains have been applied, for instance, in HIV drug resistance prediction. Bayesian network has also been applied to optimally order classifiers in Classifier chains.
• Transformation into multi-class classification problem: The label powerset transformation creates one binary classifier for every label combination present in the training set. For example, if possible labels for an example were A, B, and C, the label powerset representation of this problem is a multi-class classification problem with the classes , , , , , , . where for example denotes an example where labels A and C are present and label B is absent.
• Ensemble methods: A set of multi-class classifiers can be used to create a multi-label ensemble classifier. For a given example, each classifier outputs a single class. These predictions are then combined by an ensemble method, usually a voting scheme where every class that receives a requisite percentage of votes from individual classifiers is predicted as a present label in the multi-label output. However, more complex ensemble methods exist, such as committee machines. Another variation is the random -labelsets algorithm, which uses multiple LP classifiers, each trained on a random subset of the actual labels; label prediction is then carried out by a voting scheme. A set of multi-label classifiers can be used in a similar way to create a multi-label ensemble classifier. In this case, each classifier votes once for each label it predicts rather than for a single label.

  Adapted algorithms

• k-nearest neighbors: the ML-kNN algorithm extends the k-NN classifier to multi-label data.
• decision trees: "Clare" is an adapted C4.5 algorithm for multi-label classification; the modification involves the entropy calculations. MMC, MMDT, and SSC refined MMDT, can classify multi-labeled data based on multi-valued attributes without transforming the attributes into single-values. They are also named multi-valued and multi-labeled decision tree classification methods.
• kernel methods for vector output
• neural networks: BP-MLL is an adaptation of the popular back-propagation algorithm for multi-label learning.

  Learning paradigms

Multi-label stream classification

• Online Bagging -based methods: Observing the probability of having K many of a certain data point in a bootstrap sample is approximately Poisson for big datasets, each incoming data instance in a data stream can be weighted proportional to Poisson distribution to mimic bootstrapping in an online setting. This is called Online Bagging. Many multi-label methods that use Online Bagging are proposed in the literature, each of which utilizes different problem transformation methods. EBR, ECC, EPS, E_BRT, E_BMT, ML-Random Rules are examples of such methods.
• ADWIN Bagging-based methods: Online Bagging methods for MLSC are sometimes combined with explicit concept drift detection mechanisms such as ADWIN. ADWIN keeps a variable-sized window to detect changes in the distribution of the data, and improves the ensemble by resetting the components that perform poorly when there is a drift in the incoming data. Generally, the letter 'a' is used as a subscript in the name of such ensembles to indicate the usage of ADWIN change detector. E_aBR, E_aCC, E_aHT_PS are examples of such multi-label ensembles.
• GOOWE-ML-based methods: Interpreting the relevance scores of each component of the ensemble as vectors in the label space and solving a least squares problem at the end of each batch, Geometrically-Optimum Online-Weighted Ensemble for Multi-label Classification is proposed. The ensemble tries to minimize the distance between the weighted prediction of its components and the ground truth vector for each instance over a batch. Unlike Online Bagging and ADWIN Bagging, GOOWE-ML utilizes a weighted voting scheme where better performing components of the ensemble are given more weight. The GOOWE-ML ensemble grows over time, and the lowest weight component is replaced by a new component when it is full at the end of a batch. GOBR, GOCC, GOPS, GORT are the proposed GOOWE-ML-based multi-label ensembles.
• Multiple Windows : Here, BR models that use a sliding window are replaced with two windows for each label, one for relevant and one for non-relevant examples. Instances are oversampled or undersampled according to a load factor that is kept between these two windows. This allows concept drifts that are independent for each label to be detected, and class-imbalance to be handled.

  Statistics and evaluation metrics

• Label cardinality is the average number of labels per example in the set: ;
• Label density is the number of labels per sample divided by the total number of labels, averaged over the samples: where.

• Hamming loss: the fraction of the wrong labels to the total number of labels, i.e., where is the target and is the prediction. This is a loss function, so the optimal value is zero.
• The closely related Jaccard index, also called Intersection over Union in the multi-label setting, is defined as the number of correctly predicted labels divided by the union of predicted and true labels,, where and are sets of predicted labels and true labels respectively.
• Precision, recall and score: precision is, recall is, and is their harmonic mean.
• Exact match : is the most strict metric, indicating the percentage of samples that have all their labels classified correctly.

Implementations and datasets