When a sample belongs to more than one label from a set of available classes, the classification problem (known as multi-label classification) turns to be more complicated. Text data, widely available nowadays in the world wide web, is an obvious instance example of such a task. This paper presents a new method for multi-label text categorization created by modifying the Error-Correcting Output Coding (ECOC) technique. Using a set of binary complimentary classifiers, ECOC has proven to be efficient for multi-class problems. The proposed method, called ML-ECOC, is a first attempt to extend the ECOC algorithm to handle multi-label tasks. Experimental results on the Reuters benchmarks (RCV1-v2) demonstrate the potential of the proposed method on multi-label text categorization.
Text Categorization (TC), also known as document classification, plays a key
role in many information retrieval (IR) -based systems and natural language
processing (NLP) applications. First research on TC goes back to Maron’s [
The traditional classification problem in pattern recognition refers to assigning any incoming sample to one of two (binary problem) or more (multi-class problem) distinct predefined classes. An even more complex scenario - called multi-label classification - is one in which the classes have overlap between each other. TC or automatically labeling natural language texts with thematic categories from a predefined set is one such task. An instance document or web page about ”Persian carpet exhibition” can belong to both ”economy” and ”art” categories. Despite its multi-label nature, the majority of research studies on TC have considered it as single-label task by assigning the samples into only one of the existing classes. However, this approach simplifies the task and handles it using a huge bibliography of learning algorithms, yet failing to provide a complete solution to multi-label TC.
There are two main approaches in the literature to deal with multi-label
classification: (i) Problem transformation approaches which transform the
multilabel problem into one or more single-label problems, and (ii) Algorithm
adaptation approaches which extend specific learning algorithms in order to handle the
multi-label task directly. Although many approaches have been proposed based
on different kinds of classifiers and architectures over a variety of application
domains, there is no clear winner method over the rest (see [
Classifier ensembles (also known as Multiple Classifier Systems) is a paradigm
based on the divide-and-conquer strategy to deal with complex classification
problems. The main idea is to use an ensemble of simple base-classifiers, each
applied to a sub-task, instead of hiring a single classifier expected to take care of
the entire task. This strategy typically improves a classification system in terms
of stability and classification accuracy (bias-variance reduction). Bootstrap
aggregating (i.e., bagging) is a machine learning technique that combines a number
of base-classifiers, each trained on a set of bootstrap samples of the original data
[
This paper proposes a method for multi-label TC called ML-ECOC created by extending the ECOC strategy. ML-ECOC modifies the coding/decoding phases of the standard ECOC algorithm making it suitable to the multi-label problems. This modification includes setting up new rules in both coding and decoding phases to avoid the occurrence of any inconsistency while handling multi-label data. Experiments on the text mining problem of Multi-Label Text Categorization (ML-TC) show a good performance of the proposed ML-ECOC. Comparissons to the state-of-the-art methods from different perspectives are carried out and the obtained results are analysed in detail.
The rest of this paper is organized as follows: the standard ECOC algorithm presented in section 2, the proposed ML-ECOC algorithm is presented in section 3 with full details, section 4 presents the analysis of experimental results on Reuter’s version 2 datasets and the comparisons with the state-of-the-art methods from litrature. Last section concludes the paper and discusses some directions of future work. 2
ECOC is a classifier ensemble method inspired by signal transmission in information theory used to safely send and receive the data. Besides its error-correcting capability to recover the errors made in each sub-problem classification level, ECOC has the advantage of decomposing a multi-class problem into some binary sub-problems (dichotomies) in machine learning concept. Each sub-problem is tackled by a dichotomizer and the final solution for the multi-class problem is created by aggregating the results of the dichotomizers (divide-and-conquer principle). For this reason, ECOC performs well particularly on the problems with large number of classes for which other classifiers normally have difficulties.
Given a classification problem with Nc classes, the main idea of ECOC is to create a binary/ternary codeword for each class. Arranging the codewords as rows of a matrix, we define a codematrix M , where M ∈ {−1, 0, +1}Nc×L and L is the code length (coding phase). From a learning point of view, M specifies Nc classes to train L dichotomizers, f1...fL. A classifier fl is trained according to the column M (., l). If M (i, l) = +1 then all examples of class i are positive, if M (i, l) = −1 then all its examples are negative supper-class and, finally, if M (i, l) = 0 none of the examples of class i participate in the training of fl.
Let y = [y1...yL], yl ∈ {−1, +1} be the output vector of the L classifiers in the ensemble for a given input x. In the decoding phase, the class output that maximizes the similarity measure s (e.g. the Hamming distance) between y and row M (j, .) (its codeword) is selected:
Class Label = ArgM ax S(y, M (j, .)) (1)
The ECOC matrix codifies the class labels in order to achieve different
partitions of classes, considered by each dichotomizer. The main coding strategies can
be divided into problem-independent (or fixed) and problem-dependent. Most
popular pre-designed problem-independent codeword constructions satisfy the
requirement of high separability between rows and columns in order to increase
error-correcting capability and diversity between dichotomies. These strategies
include: 1vsA, using Nc dichotomizers, each trained to discriminate a given class
from the rest of classes; random techniques, which can be divided into the
denserandom, consisting of a binary matrix with high distance between rows with
estimated length of 10 log2 Nc bits per code, and the sparse-random strategy based
on the ternary symbol and with the estimated length of about 15 log2 Nc. 1vs1 is
one of the most well-known coding strategies, with Nc(Nc − 1)/2 dichotomizers
including all combinations of pairs of classes [
The first application of ECOC algorithm on TC dates back to 1999 [
The reason that all these works are limited to single-label assumption is that
an inconsistency would occur otherwise in ECOC classification while applying
to multi-label data. For instance, imagine a document d belongs to a label set
[
Although the single-label assumption may be true in some TC applications, it certainly limits the application of ECOC to real-world multi-label cases. This is the point where ECOC algorithm requires a major modification to be applicable to multi-label problems. In the following, we introduce the ML-ECOC method to address any multi-label problem without any constraint and restricting assumption.
The main idea of ML-ECOC is to generate a codeword for each category of a TC task with only +1 (positive class) and 0 (don’t care) bits. Unlike standard ECOC algorithm, where at least one +1 and one −1 bits are required at each column to define a dichotomy, to be non-zero is all ML-ECOC needs for a column. A classifier defined according to each column of the ML matrix and used to calculate degree of membership of d into a super-class which includes one or more categories. The inconsistency in the dichotomizing process is avoided by defining only positive class and neutral set which can not have any overlapping area. It is worth noting that a document belongs to ith positive class if and only if at least one of its labels from the label set is in the ith super-class. A document d (Figure 2) either should belong to positive class of ith column or its neutral set. For instance, d is a member of 2, 3, 4, 5, 6, 7 and 8 positive class sets while should be considered as neutral for 1st and 9th.
Subsequently, it is obvious that this modification requires also different decoding strategy, since standard Euclidean or Hamming distances with ArgM ax labeling are not applicable anymore. Let us suppose a predicted codeword yd = [y1...yL], 0 ≤ yl ≤ +1} is a string assigned to document d (each bit representing the output of a classifier i.e. Pl(+1 | d)). The posterior probability of each class using ML-ECOC is calculated as follows: 1
L P(cN | d) =
X Pl(+1 | d)M (N, l) | M (N, .) | l=1 (2)
For each document, ML-ECOC sorts categories by score and assigns YES to each of the t top-ranking categories. Parameter t is an integer ranging from 1 to the number of categories Nc whose value can be either specified by the user or automatically tuned using a validation set. It should be noted that when t = 1, this multi-label assignment turns into the standard single-label TC with ArgM ax rule. Obviously, it is just typical thresholding strategy adopted to MLECOC and the other existing throsholding methods can be applied. The generic ML-ECOC is summarized in Algorithm 1. The success of the ML-ECOC idea can be attributed to following three factors: 1. Unlike the standard TC approaches trying directly to discriminate different classes, ML-ECOC transfers the entire class space to many super-classes, which are not necessarily carrying meaningful concepts, by mixing them . This is helpful particularly to deal with what is called in the literature Data sparsity. This Algorithm 1 ML-ECOC.
Input: Xt, Tt training set, Xe, Te testing set and f learning algorithm. Training:
- generate a binary codemtrix M Nc×L which Nc is the number of categories and L varies with coding strategy.
- for i-th column in M :
build (create) one-class set made of Ti+ and Ti∗ supper-classes (positive and neutral sets respectively)
train i-th classifier fi with i-th training set Testing: - apply Xe on entire set of fis - create a codeword which i-th bit is fi(Xe) = Pi(+1 | Xe) - calculate the posterior probability for each class using Eq. 2 - use multi-label decoding to predict label set Output: ω¯ = [c¯p, c¯q, c¯r] is a measure for how much data we have for a particular dimension/entity of the model. A dataset is sparse if the number of samples for each class is not enough for a classifier to discriminate it from the rest which is normally the case in the TC problem. Therefore, mixing categories by ML-ECOC decomposing, not only used to define new class-boundaries which might provide additional information in final decision making, but also provides new one-class problems with more samples per positive class (in the case each super-class has more than one category). For instance, each super-class in first dichotomy of Figure 2 is made of 3 categories.
2. No matter which TC approach is chosen, a class-label is assigned to a document if its corresponding classifier fires. In fact, when a category is wrongly detected, there is no any efficient way to go back and fix it without the increase of the algorithm complexity and computational cost. However, in ML-ECOC there is no dedicated classifier for each category and decisions are made by consensus of all classifiers. Therefore, because of its error-correcting capability, even if some errors occur in the bit level, the final decision can still be reliable.
3. Another important issue arising while dealing with TC refers to classimbalanced datasets where there is no balance between the positive and negative set of a category. This problem can badly affect the learning process particularly in the Local Classifier per Category approach when a category stands against the rest. ML-ECOC keeps more balance between two resulted positive classes and neutrals by having chance of including more than one class in the positive class set. For instance Sparse-random method can possibly include more than one category in a positive class resulting into more balanced data. Consequently, efficient learning of the class boundaries by classifiers results in more accurate prediction. 4
For the text categorization experiments, we have chosen two commonly used multi-label datasets i.e. the Reuters (RCV1-V2) and TMC2007. A brief description of each is given below.
RCV1-V2: Reuters Corpus Volume1-Version2 is a large-scale dataset for text
classification task. It is based on the well known benchmark dataset for text
classification, the Reuters (RCV1) dataset. We use the topics full set 3 that
contains (804,414) news articles. Each article is assigned to a subset of the 103
topics. A detailed description of the RCV1 dataset can be found in [
TMC2007: This is the dataset used for the SIAM 2007 competition organized
by the text mining workshop held in conjunction with the 7th SIAM
International Conference on Data Mining [
In the applications using text categorization as the core task, the
computational efficiency is crucial because of very large number of features, classes and
samples. Therefore, the need for designing a simple and fast classification system
is important. There are many research studies using different kinds of classifiers
such as k-nearest neighbors (kNN), support vector machines (SVM), artificial
neural networks (ANN), bayesian methods and rocchio classifiers [
For the experiments presented in the current paper, we used centroid-based classifiers as the ECOC dichotomizers. This means that the prototype vector or centroid vector (μi+) is computed for super-class Ti+ as: μi+ =
1 | Ti+ |
X d d∈Ti+ S(d, μi+) =
d · μi+ || d || || μi+ || classif ication accuracy =
n 1
X I(ωd = ω¯d) n d=1 where I(true) = 1 and I(f alse) = 0 and n is the number of documents in a dataset. This is a very strict evaluation measure as it requires the predicted set to be an exact match for the true set in the label set no matter if a classifier makes a mis-classification at only one category or the entire set.
where | Ti+ | denotes the cardinality of set Ti+, i.e. the number of documents that belong to positive set in the i-th individual and d is a training document.
In the testing step, we calculate the similarity of a document d to each centroid by the cosine measure,
This similarity can be regarded as the posterior probability of the dichotomizer and used for i-th bit of the predicted codeword y¯d.
Consequently, the evaluation of methods to handle multi-label data requires different measures than those used for traditional single-label classification. Various measures are traditionally being used for evaluation of multi-label classification (particularly for document and text applications) such as classification accuracy, precision, recall and F1. These are defined below.
precision = 1 XNc T Pci Nc ci=1 T Pci + F Pci and recall = 1 XNc T Pci Nc ci=1 T Pci + F Nci (3) (4) (5) (6) where T P , F P and F N stand for the true positive, false positive and false negative for each category, respectively. The F1-score which considers both the precision and recall of the test set is formulated as:
F 1 = 2precision.recall precision + recall where an F 1 score reaches its best value at 1 and worst score at 0.
We have compared the results of the proposed method with some of commonly used TC algorithms. The standard multi-label TC methods used as baseline methods are the big-bang (global method) and Local Classifier per Category (LCC). For all these methods, centroid-based classifiers with the same parameters have been implemented. As shown in Table 2, the proposed ML-ECOC using Dense random and 2vsA codes outperforms the standard TC approaches on the selected datasets by obtaining the maximum F1 scores. One can note that the results for 2vsA code for rcv1v2 data is missing. This is because of large number of classes of RCv1v2 data which make building ECOC classifier unfeasible.
To give more detailed information, Figure 3 shows precision-recall curves corresponding to ML-ECOC and LCC approaches. Because of the superior performance on ML-TC datasets, the LCC approach is used for assessing the comparative performance of ML-ECOC. As clearly shown, the proposed ML-ECOC is able to obtain slightly better results on RCv1-v2 while always winning on TMC2007 data. (7) An extension of the ECOC algorithm called ML-ECOC is proposed to tackle multi-label TC problems. To avoid the inconsistency in coding step, the proposed ML-ECOC method decomposes a multi-label problem into some complementary one-class sub-problems unlike the standard ECOC which builds dichotomies. Multi-label relationship is taken into account in the testing phase by using a novel decoding strategy adopted for ECOC algorithm. Experimental results on Reuters datasets confirm the potential of the proposed ML-ECOC on multi-label classification with large number of categories.
Recently, some studies [
Acknowledgments. Camelia Chira acknowledges the support of Grant PN II TE 320, Emergence, auto-organization and evolution: New computational models in the study of complex systems, funded by CNCS Romania.