Multi-label classification

{{Short description|Classification problem where multiple labels may be assigned to each instance}}

In machine learning, multi-label classification or multi-output classification is a variant of the classification problem where multiple nonexclusive labels may be assigned to each instance. Multi-label classification is a generalization of multiclass classification, which is the single-label problem of categorizing instances into precisely one of several (greater than or equal to two) classes. In the multi-label problem the labels are nonexclusive and there is no constraint on how many of the classes the instance can be assigned to. The formulation of multi-label learning was first introduced by Shen et al. in the context of Semantic Scene Classification,Xipeng Shen, Matthew Boutell, Jiebo Luo, and Christopher Brown, "[https://research.csc.ncsu.edu/picture/publications/papers/ei5307-22.pdf Multi-label Machine Learning and Its Application to Semantic Scene Classification]", In Proceedings of IS&T/SPIE's Sixteenth Anaual Symposium on Electronic Imaging: Science and Technology (EI 2004), San Jose, California, USA, January 2004, pages 188--199. Matthew R. Boutell, Jiebo Luo, Xipeng Shen and Christopher M. Brown, "[https://research.csc.ncsu.edu/picture/publications/papers/pr04.pdf Learning Multi-label Scene Classification"], in Pattern Recognition, Volume 37, Issue 9, 2004, pages 1757-1771. and later gained popularity across various areas of machine learning.

Formally, multi-label classification is the problem of finding a model that maps inputs x to binary vectors y; that is, it assigns a value of 0 or 1 for each element (label) in y.

Problem transformation methods

Several problem transformation methods exist for multi-label classification, and can be roughly broken down into:

=Transformation into [[binary classification]] problems=

The baseline approach, called the binary relevance method,Jesse Read, Bernhard Pfahringer, Geoff Holmes, Eibe Frank. [https://doi.org/10.1007%2Fs10994-011-5256-5 Classifier Chains for Multi-label Classification]. Machine Learning Journal. Springer. Vol. 85(3), (2011). 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 (OvA) and one-vs.-rest (OvR) 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 (i.e. positive or negative for a particular label) are input as features to subsequent classifiers. Classifier chains have been applied, for instance, in HIV drug resistance prediction.{{cite journal|last1=Heider|first1=D|last2=Senge|first2=R|last3=Cheng|first3=W|last4=Hüllermeier|first4=E|date=2013|title=Multilabel classification for exploiting cross-resistance information in HIV-1 drug resistance prediction|journal=Bioinformatics|volume=29|issue=16|pages=1946–52|doi=10.1093/bioinformatics/btt331|pmid=23793752|doi-access=free}}{{cite journal|last1=Riemenschneider|first1=M|last2=Senge|first2=R|last3=Neumann|first3=U|last4=Hüllermeier|first4=E|last5=Heider|first5=D|date=2016|title=Exploiting HIV-1 protease and reverse transcriptase cross-resistance information for improved drug resistance prediction by means of multi-label classification|journal=BioData Mining|volume=9|pages=10|doi=10.1186/s13040-016-0089-1|pmc=4772363|pmid=26933450|doi-access=free}} Bayesian network has also been applied to optimally order classifiers in Classifier chains.{{Cite journal|last1=Soufan|first1=Othman|last2=Ba-Alawi|first2=Wail|last3=Afeef|first3=Moataz|last4=Essack|first4=Magbubah|last5=Kalnis|first5=Panos|last6=Bajic|first6=Vladimir B.|date=2016-11-10|title=DRABAL: novel method to mine large high-throughput screening assays using Bayesian active learning|journal=Journal of Cheminformatics|volume=8|pages=64|doi=10.1186/s13321-016-0177-8|pmid=27895719|pmc=5105261|issn=1758-2946 |doi-access=free }}

In case of transforming the problem to multiple binary classifications, the likelihood function reads $L=\prod_{i=1}^n (\prod_k (\prod_{j_k}(p_{k,j_k}(x_i)^{\delta_{y_{i,k},j_k}})))$

where index $i$ runs over the samples, index $k$ runs over the labels, $j_k$ indicates the binary outcomes 0 or 1, $\delta_{a,b}$ indicates the Kronecker delta, $y_{i,k}\in {0,1}$ indicates the multiple hot encoded labels of sample $i$ .

=Transformation into [[Multiclass classification|multi-class classification]] problem=

The label powerset (LP) 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 [0 0 0], [1 0 0], [0 1 0], [0 0 1], [1 1 0], [1 0 1], [0 1 1], and [1 1 1] where for example [1 0 1] denotes an example where labels A and C are present and label B is absent.{{Cite journal|last1=Spolaôr|first1=Newton|last2=Cherman|first2=Everton Alvares|last3=Monard|first3=Maria Carolina|last4=Lee|first4=Huei Diana|date=March 2013|title=A Comparison of Multi-label Feature Selection Methods using the Problem Transformation Approach|journal=Electronic Notes in Theoretical Computer Science|volume=292|pages=135–151|doi=10.1016/j.entcs.2013.02.010|issn=1571-0661|doi-access=free}}

=[[Ensemble learning|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 (corresponding to a single label in the multi-label problem). 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 (often referred to as the discrimination threshold{{Cite web|url=http://www.scikit-yb.org/en/latest/api/classifier/threshold.html|title=Discrimination Threshold — yellowbrick 0.9 documentation|website=www.scikit-yb.org|access-date=2018-11-29}}) 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 {{mvar|k}}-labelsets (RAKEL) 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.{{cite conference |last1=Tsoumakas |first1=Grigorios |first2=Ioannis |last2=Vlahavas |title=Random {{mvar|k}}-labelsets: An ensemble method for multilabel classification |conference=ECML |year=2007 |url=http://talos.csd.auth.gr/tsoumakas/publications/C19.pdf |access-date=2014-07-26 |archive-url=https://web.archive.org/web/20140729055455/http://talos.csd.auth.gr/tsoumakas/publications/C19.pdf |archive-date=2014-07-29 |url-status=dead }} 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

Some classification algorithms/models have been adapted to the multi-label task, without requiring problem transformations. Examples of these including for multi-label data are

k-nearest neighbors: the ML-kNN algorithm extends the k-NN classifier to multi-label data.{{cite journal |first1=M.L. |last1=Zhang |first2= Z.H. |last2= Zhou |title=ML-KNN: A lazy learning approach to multi-label learning |journal=Pattern Recognition |volume=40 |issue=7 |year=2007 |doi=10.1016/j.patcog.2006.12.019 |pages=2038–2048|bibcode=2007PatRe..40.2038Z |citeseerx=10.1.1.538.9597 |s2cid=14886376 }}
decision trees: "Clare" is an adapted C4.5 algorithm for multi-label classification; the modification involves the entropy calculations.{{cite journal |first1=Gjorgji |last1=Madjarov |first2=Dragi |last2=Kocev |first3=Dejan |last3=Gjorgjevikj |first4=Sašo |last4=Džeroski |title=An extensive experimental comparison of methods for multi-label learning |journal=Pattern Recognition |volume=45 |issue=9 |year=2012 |doi=10.1016/j.patcog.2012.03.004 |pages=3084–3104|bibcode=2012PatRe..45.3084M |s2cid=14064264 }} 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.{{cite journal|last2=Hsu|first2=Chang-Ling|last3=Chou|first3=Shih-chieh|year=2003|title=Constructing a multi-valued and multi-labeled decision tree|journal=Expert Systems with Applications|volume=25|issue=2|pages=199–209|doi=10.1016/S0957-4174(03)00047-2|first1=Yen-Liang|last1=Chen}}{{Cite journal|last1=Chou|first1=Shihchieh|last2=Hsu|first2=Chang-Ling|date=2005-05-01|title=MMDT: a multi-valued and multi-labeled decision tree classifier for data mining|journal=Expert Systems with Applications|volume=28|issue=4|pages=799–812|doi=10.1016/j.eswa.2004.12.035}}{{Cite journal|last1=Li|first1=Hong|last2=Guo|first2=Yue-jian|last3=Wu|first3=Min|last4=Li|first4=Ping|last5=Xiang|first5=Yao|date=2010-12-01|title=Combine multi-valued attribute decomposition with multi-label learning|journal=Expert Systems with Applications|volume=37|issue=12|pages=8721–8728|doi=10.1016/j.eswa.2010.06.044}}
kernel methods for vector output
neural networks: BP-MLL is an adaptation of the popular back-propagation algorithm for multi-label learning.{{cite conference |first1=M.L. |last1=Zhang |first2= Z.H. |last2= Zhou |title=Multi-label neural networks with applications to functional genomics and text categorization |conference=IEEE Transactions on Knowledge and Data Engineering |volume=18 |year=2006 |pages=1338–1351 |url=http://cse.seu.edu.cn/people/zhangml/files/Multi-label%20neural%20networks%20with%20applications%20to%20functional%20genomics%20and%20text%20categorization.pdf}}

Learning paradigms

Based on learning paradigms, the existing multi-label classification techniques can be classified into batch learning and online machine learning. Batch learning algorithms require all the data samples to be available beforehand. It trains the model using the entire training data and then predicts the test sample using the found relationship. The online learning algorithms, on the other hand, incrementally build their models in sequential iterations. In iteration t, an online algorithm receives a sample, x_t and predicts its label(s) ŷ_t using the current model; the algorithm then receives y_t, the true label(s) of x_t and updates its model based on the sample-label pair: (x_t, y_t).

Multi-label stream classification

Data streams are possibly infinite sequences of data that continuously and rapidly grow over time.{{Cite book|date=2007|editor-last=Aggarwal|editor-first=Charu C.|title=Data Streams|volume=31|doi=10.1007/978-0-387-47534-9|isbn=978-0-387-28759-1 |series=Advances in Database Systems }} Multi-label stream classification (MLSC) is the version of multi-label classification task that takes place in data streams. It is sometimes also called online multi-label classification. The difficulties of multi-label classification (exponential number of possible label sets, capturing dependencies between labels) are combined with difficulties of data streams (time and memory constraints, addressing infinite stream with finite means, concept drifts).

Many MLSC methods resort to ensemble methods in order to increase their predictive performance and deal with concept drifts. Below are the most widely used ensemble methods in the literature:

Online Bagging (OzaBagging{{Cite journal|last=Oza|first=Nikunj|date=2005|title=Online Bagging and Boosting|journal=IEEE International Conference on Systems, Man and Cybernetics|hdl=2060/20050239012|hdl-access=free}})-based methods: Observing the probability of having K many of a certain data point in a bootstrap sample is approximately Poisson(1) for big datasets, each incoming data instance in a data stream can be weighted proportional to Poisson(1) distribution to mimic bootstrapping in an online setting. This is called Online Bagging (OzaBagging). Many multi-label methods that use Online Bagging are proposed in the literature, each of which utilizes different problem transformation methods. EBR, ECC, EPS,{{Cite book|last1=Read|first1=Jesse|last2=Pfahringer|first2=Bernhard|last3=Holmes|first3=Geoff|title=2008 Eighth IEEE International Conference on Data Mining |chapter=Multi-label Classification Using Ensembles of Pruned Sets |date=2008-12-15|url=http://dl.acm.org/citation.cfm?id=1510528.1511358|publisher=IEEE Computer Society|pages=995–1000|doi=10.1109/ICDM.2008.74|isbn=9780769535029|hdl=10289/8077|s2cid=16059274}} E_BRT,{{Cite journal|last1=Osojnik|first1=Aljaź|last2=Panov|first2=PanăźE|last3=DźEroski|first3=Sašo|date=2017-06-01|title=Multi-label classification via multi-target regression on data streams|journal=Machine Learning|volume=106|issue=6|pages=745–770|doi=10.1007/s10994-016-5613-5|issn=0885-6125|doi-access=free}} E_BMT, ML-Random Rules{{Cite journal|last1=Sousa|first1=Ricardo|last2=Gama|first2=João|date=2018-01-24|title=Multi-label classification from high-speed data streams with adaptive model rules and random rules|journal=Progress in Artificial Intelligence|volume=7|issue=3|pages=177–187|doi=10.1007/s13748-018-0142-z|s2cid=32376722|issn=2192-6352}} are examples of such methods.
ADWIN Bagging{{Cite journal|last1=Read|first1=Jesse|last2=Bifet|first2=Albert|last3=Holmes|first3=Geoff|last4=Pfahringer|first4=Bernhard|date=2012-02-21|title=Scalable and efficient multi-label classification for evolving data streams|journal=Machine Learning|volume=88|issue=1–2|pages=243–272|doi=10.1007/s10994-012-5279-6|issn=0885-6125|doi-access=free}}-based methods: Online Bagging methods for MLSC are sometimes combined with explicit concept drift detection mechanisms such as ADWIN{{Citation|last1=Bifet|first1=Albert|title=Learning from Time-Changing Data with Adaptive Windowing|date=2007-04-26|work=Proceedings of the 2007 SIAM International Conference on Data Mining|pages=443–448|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611972771.42|isbn=9780898716306|last2=Gavaldà|first2=Ricard|citeseerx=10.1.1.215.8387|s2cid=2279539 }} (Adaptive Window). 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{{Cite book|last1=Büyükçakir|first1=Alican|last2=Bonab|first2=Hamed|last3=Can|first3=Fazli|title=Proceedings of the 27th ACM International Conference on Information and Knowledge Management |chapter=A Novel Online Stacked Ensemble for Multi-Label Stream Classification |date=2018-10-17|publisher=ACM|pages=1063–1072|doi=10.1145/3269206.3271774|isbn=9781450360142|arxiv=1809.09994|s2cid=52843253}}-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 (GOOWE-ML) 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{{Cite book|last1=Xioufis|first1=Eleftherios Spyromitros|last2=Spiliopoulou|first2=Myra|last3=Tsoumakas|first3=Grigorios|last4=Vlahavas|first4=Ioannis|date=2011-07-16|title=Dealing with concept drift and class imbalance in multi-label stream classification|url=http://dl.acm.org/citation.cfm?id=2283516.2283659|publisher=AAAI Press|pages=1583–1588|doi=10.5591/978-1-57735-516-8/IJCAI11-266|isbn=9781577355144}} : 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 (skewness in the relevant and non-relevant examples) to be handled.

Statistics and evaluation metrics

Considering $Y_i$ to be a set of labels for $i^{th}$ data sample (do not confuse it with a one-hot vector; it is simply a collection of all of the labels that belong to this sample), the extent to which a dataset is multi-label can be captured in two statistics:

Label cardinality is the average number of labels per example in the set: $\frac{1}{N} \sum_{i=1}^N |Y_i|$ where $N$ is the total number of data samples;
Label density is the number of labels per sample divided by the total number of labels, averaged over the samples: $\frac{1}{N} \sum _{i=1}^N \frac$
Y_i
L
where $L = \bigcup_{i=1}^N Y_i$ , the total number of available classes (which is the maximum number of elements that can make up $Y_i$ ).

Evaluation metrics for multi-label classification performance are inherently different from those used in multi-class (or binary) classification, due to the inherent differences of the classification problem. If {{mvar|T}} denotes the true set of labels for a given sample, and {{mvar|P}} the predicted set of labels, then the following metrics can be defined on that sample:

Hamming loss: the fraction of the wrong labels to the total number of labels, i.e. $\frac{1}$
N|\cdot |L
\sum_{i=1}^
N
\sum_{j=1}^
L
\operatorname{xor}(y_{i,j}, z_{i,j}), where $y_{i,j}$ is the target, $z_{i,j}$ is the prediction, and $\operatorname{xor}(\cdot)$ is the "Exclusive, or" operator that returns zero when the target and prediction are identical and one otherwise. This is a loss function, so the optimal value is zero and its upper bound is one.
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, $\frac$
T \cap P
T \cup P
, where $P$ and $T$ are sets of predicted labels and true labels respectively.
Precision, recall and $F_1$ score: precision is $\frac$
T \cap P
P
, recall is $\frac$
T \cap P
T
, and $F_1$ is their harmonic mean.{{cite conference |last1=Godbole |first1=Shantanu |first2=Sunita |last2=Sarawagi|author2-link= Sunita Sarawagi |title=Discriminative methods for multi-labeled classification |conference=Advances in Knowledge Discovery and Data Mining |year=2004 |pages=22–30 |url=http://www.godbole.net/shantanu/pubs/multilabelsvm-pakdd04.pdf}}
Exact match (also called Subset accuracy): is the most strict metric, indicating the percentage of samples that have all their labels classified correctly.

Cross-validation in multi-label settings is complicated by the fact that the ordinary (binary/multiclass) way of stratified sampling will not work; alternative ways of approximate stratified sampling have been suggested.{{cite conference |last1=Sechidis |first1=Konstantinos |first2=Grigorios |last2=Tsoumakas |first3=Ioannis |last3=Vlahavas |title=On the stratification of multi-label data |conference=ECML PKDD |year=2011 |pages=145–158 |url=http://lpis.csd.auth.gr/publications/sechidis-ecmlpkdd-2011.pdf}}

Implementations and datasets

Java implementations of multi-label algorithms are available in the [http://mulan.sourceforge.net/ Mulan] and [http://meka.sourceforge.net/ Meka] software packages, both based on Weka.

The scikit-learn Python package implements some [http://scikit-learn.org/stable/modules/multiclass.html multi-labels algorithms and metrics].

The [http://scikit.ml/ scikit-multilearn] Python package specifically caters to the multi-label classification. It provides multi-label implementation of several well-known techniques including SVM, kNN and [http://scikit.ml/api/skmultilearn.html#module-skmultilearn.problem_transform many more]. The package is built on top of scikit-learn ecosystem.

The binary relevance method, classifier chains and other multilabel algorithms with a lot of different base learners are implemented in the R-package [https://mlr-org.github.io/mlr/articles/tutorial/multilabel.html mlr]Philipp Probst, Quay Au, Giuseppe Casalicchio, Clemens Stachl, Bernd Bischl. [https://journal.r-project.org/archive/2017/RJ-2017-012/index.html Multilabel Classification with R Package mlr]. The R Journal (2017) 9:1, pages 352-369.

A list of commonly used multi-label data-sets is available at the [http://mulan.sourceforge.net/datasets.html Mulan website].