In recent years, there has been increasing interest in using text classi ers for retrieving and ltering infomation from web sources. As the numbers of categories in this kind of software applications can be high, Error correcting Output Coding (ECOC) can be a valid approach to perform multi-class classi cation. This paper explores the use of ECOC for learning text classi ers using two kinds of dichotomizers and compares them to each corresponding monolithic classi er. We propose a simulated annealing approach to calculate the coding matrix using an energy function similar to the electrostatic potential energy of a system of charges, which allows to maximize the average distance between codewords |with low variance. In addition, we use a new criterion for selecting features, a feature (in this speci c context) being any term that may occur in a document. This criterion de nes a measure of discriminant capability and allows to order terms according to it. Three di erent measures have been experimented to perform feature ranking / selection, in a comparative setting. Experimental results show that reducing the set of features used to train classi ers does not a ect classi cation performance. Notably, feature selection is not a preprocessing activity valid for all dichotomizers. In fact, features are selected for each dichotomizer that occurs in the matrix coding, typically giving rise to a di erent subset of features depending on the dichotomizers at hand.
Multi-class classi cation consists of assigning a given pattern x to a category
taken from a prede ned set, say c 2 C, with C = fc1; c2; c3; : : : ; cmg. Several
approaches have been devised to directly handle multi-class problems (e.g.,
decision trees [
An alternative approach to solve multi-class learning task is to adopt
ErrorCorrecting Output Coding (ECOC). Error correcting codes are widely used in
data transmission, being in charge of correcting errors when messages are
transmitted through a noisy channel. A simple encoding strategy in data transmission
is to add extra bits to any given message, so that the receiver will be typically
able to correct it in presence of noise. A variation of this this basic principle is
applied with success in the eld of machine learning, to improve the performance
of multi-class classi ers. The basic ECOC strategy is to assign a binary string of
length n (i.e., a codeword) to each category, trying to separate as much as
possible each codeword from the others. The set of codewords can also be viewed as
a coding matrix, in which binary classi ers are related to columns, whereas
categories are related to rows. Hence, the i-th classi er will consider samples taken
from the j-th category as negative or posative depending on the value, i.e., 1
or 1, found at position hi; ji of the coding matrix. This approach was rst used
in the NETtalk system [
Since the rst ECOC has been designed, many experiments have shown that, to achieve a good generalization capacity, codewords must be well separated, which implies that the corresponding binary classi ers are trained on di erent subsets of data. The most commonly used distance measure is the Hamming distance. Given two vectors x and y, with components xi; yi 2 f 1; +1g, the Hamming distance d(x; y) is de ned as: d(x; y) = n X jxi i=0 2 yij (1)
In the training phase n binary classi ers are trained with samples relabeled in accordance with the coding matrix, say . The trained classi ers have an output vector y, yj being the output of the corresponding j-th binary classi er. The decoding strategy is to assign to the output vector y the category that corresponds to the closest codeword. In symbols (with !j = codeword of the j-th category and d = adopted distance function): arg min d(!j ; y) j (2) (3) (4)
ECOC were used successfully in many application areas. It was shown that
randomly generated matrices often perform well, sometimes even better than
those generated by heuristic methods. Random codes were theoretically studied
in [
Although maximizing the distance between any pair of codewords helps to
remove individuals classi cation errors, still decoding errors may occur [
T q arg min qj
j
An interesting class of ECOC coding is BCH (from R. C. Bose and D. K.
Ray-Chaudhuri), which form a class of cyclic error-correcting codes constructed
using nite elds. The key feature of this type of coding is the precise control
of correctable symbols. An example of algorithm for generating BHC codes is
described in [
A characteristic of text categorization problems is the high dimensionality of the feature space. Each document is typically represented using a bag of words. Each word being a base vector that generates the space of features, a document can be represented as linear combination of these base vectors. A major problem is that there can be hundreds of thousands of terms even for small text collections. The amount of words is prohibitively high for many learning algorithms. Hence, reducing the original space without losing accuracy is highly desirable.
Many methods to reduce the dimensionality of the feature space have been
devised. Most of the methods select words according to their score obtained
by means of a suitable performance measure devised to check to which extent
the word at hand is in agreement (or disagreement) with the category under
analysis. 2 [?] and Information Gain (IG) (e.g., [?]) are well known measures
used to perform feature (i.e., word) ranking . Yang and Pedersen [
The remainder of this paper is organized into ve sections: Section 2 describes the proposed approach for code optimization; Section 3 introduces a selection method based on the con guration of the coding matrix; Section 4 explains the real dataset used and the experimental settings; Section 5 reports and discusses experimental results and Section 6 ends the paper. 2
In this section, we propose a method based on simulated annealing (SA) to
optimize the coding matrix. SA is a very robust algorithm, often able to nd a
global optimum and less likely to fail on di cult tasks [
The standard SA algorithm starts with an initial temperature T = T0 and moves randomly in the neighborhood of the current tentative solution !. SA is a local search algorithm, whose strategy consists of always accepting any new solution improves the current one. However to avoid local minima, SA may also accept worse solutions, with a probability inversely proportional to the current value of the temperature T . The convergence of the algorithm is guaranteed by decreasing T as the search goes on. The search continues until the maximum iterations has been performed or no relevant changes has been observed between two consecutive steps.
A solution in the neighborhood of ! is calculated by the neighbor function, described by Equation 5 (with z uniform random variable and p1, p2, p3 given constants). In the speci c setting of searching for the (sub)optimal ECOC coding matrix, a neighbor is generated from ! i) randomly changing a bit from 1 to 1 or vice versa with probability p1, ii) adding a column vector with probability p2, or iii) removing a random column vector with p3 neighbor(!) = 8< cahdadnagerarnamdodmomcolyluambnitvoecft!or toif!z < ipf 1z < p2 : remove a random column vector from ! if p3 > z > p2 (5)
In the proposed variant of the SA algorithm, the cost function is analogous to the potential energy of a particle system of electric charges, and is de ned by Equation 6, where !i and !j are codewords of .
m m f (!) = X X The ECOC optimization method which makes use of SA will be denoted as SAE, hereinafter. Moreover, SAE which makes use of classi ers of type hxi will be denoted SAEhxi. 3
As text categorization has a very high feature space (a typical order of magnitude is 10; 000), a feature selection method is needed. Our approach is enforced after having found the coding matrix, as in our view each individual binary classi er should have its proper subset of features.
Many selection methods are based on the estimation of words probability, class probability and the joint probability of words and classes. These methods are usually computed considering only the corpus of documents, independently from the way classi ers group the data. This is reasonable if the adopted kind of classi er is inherently multi-class (e.g., NB classi ers). However, an ECOC classi er actually embodies a set of n dichotomizers (being n the length of the codewords). In particular, given a dichotomizer gj , a category ci can be considered as source of negative or positive samples, depending on which symbol appears at position hi; ji of the coding matrix ( 1 for negative samples and 1 for positive samples). This is the reason why performing feature selection for each individual dichotomizer appears a reasonable choice. To help the reader better understand the whole process, let us summarize the whole procedure: 1. the coding matrix is calculated; 2. The given set of samples, say S, is split in two sets (i.e., S+ and S ), in accordance with the content of the coding matrix; 3. Features are ordered in descending order starting from the highest score; 4. The set of features is reduced by selecting the rst K features (where K is a given constant).1
Feature ranking has been performed according to three measures of discriminant capability, which will be described in the next subsection. 1 Typical values of K range from 5% to 40% of the original feature space dimension. 3.1
Three measures of discriminant capability have been experimented to perform feature ranking: 2, IG, and . The rst and the second measures are well known. Let us spend few words on the method denoted as . It originates from the proposal of Armano [?], focused on the de nition of an unbiased 2two-dimensional measure space, called ' . In particular, ' has been devised to measure the so-called characteristic capability, i.e., the ability of the feature at hand of being spread (' = 1) or absent (' = 1) over the given dataset. Conversely, has been devised to measure the so-called discriminant capability, i.e., the ability of the feature at hand of being in accordance ( = 1) or in discordance ( = 1) with the category under investigation. It is worth pointing out that the actual discriminant capability of a feature can be made coincident with the absolute value of , as the ability of separating positive from negative samples is high when j j 1, regardless from the fact that the feature is highly covariant or highly contravariant with the given category.
Focusing on the selected measure (i.e., ), let us recall its de nition: = tp f p (7) where tp and f p are respectively true and false positive rates of the main class.
A de nition of this measure in the event that samples are a corpus of documents and features the terms (or words) found in the corresponding dictionary, is the following:
#(t; c) #(t; c) (t; c) = (8)
jcj jcj where t denotes a word and c a category. Moreover, #(t; c) and #(t; c) denote the number of documents belonging to the main (c) or to the alternate (c) category in which t appears, respectively. Of course, jcj is the number of documents of the main category and jcj the number of documents of the alternative category. 4
In all the experiments, base binary classi er were of two kinds: NB and SVM [
For each dataset we rst processed the text of each document by removing puntuaction and stopwords. 3 For each experiment, we split the dataset at hand in two randomly-selected subsets (70% for training and 30% for testing). Classi cation accuracy has been used as performance measure. For each test, we ran 10 experiments using di erent data samples, then we computed mean and variance of the corresponding accuracies. 5 5.1
To show the advantages of ECOC classi ers whose codeword matrix has been optimized with SA, accuracy is reported together with the one obtained with 3 As for stopwords, we used two di erent blacklists, one for the Italian and one for the English language, as part one corpus of documents (i.e., the one concerning libraries) is in Italian. the corresponding base classi ers. Table 1 reports experimental results (the best results are highlighted in bold). In particular we observed that: { ECOC classi ers generally perform better than base classi ers. However, better results are obtained with base classi ers in the four universities dataset. Let us also note that improvements are not statistically signi cant for the library dataset. These two data sets have in common the fact of being highly unbalanced. { There are signi cant di erences between the performance of the SVM and NB classi ers and this di erence a ects also the performance of the corresponding ECOC classi ers.
In these experiments we imposed the same length of the codeword for all ECOC classi ers (i.e., 63 bits). Algorithms have been con gured as follows: { Random (RA): Random values 1 and 1 of the matrix bits are chosen with the same probability; { BHC: the minimum value of the corrective capacity is chosen equals to t = 6, so that the minimum distance between codewords is d = 2t + 1 = 12; { SA: The initial matrix state is obtained by using the algorithm RA. relevant parameters have been set as follows: T0 = f0=5, Tmin = 0:01, L0 = 30, and N = 100.
We used the same training partition of the data set to train the ECOC matrices obtained with three di erent algorithms. We ran ten experiment computing the mean and variance of the accuracy, Table 2 shows experimental results. We calculated also the mean ( ) and standard deviation ( ) between pairs of codewords for a matrix of size 100 104, the matrix calculated by the RA algorithm has = 49:96 and = 5:9, whereas the one calculated by the SA algorithm has = 50:48 and = 2:77. We observed that { SA reduces the gap between minimum distance and maximum distance of codeword pairs, increases the minimum and the mean distance reducing the variance. { SAE can achieve better performance than others for most of the datasets. Selection the best terms able to ensure a good performance in terms of time and memory consumption plays a fundamental role in text classi cation, in particular when the selected corpus contains many documents and / or the corresponding dictionary is contains many words. This section reports a comparative assessment of the selected score functions. Table 3 reports experimental results, the best results being highlighted in bold. In particular, we found that the ordering among score function (from the best downwards) is the following: 2, and IG. In this paper a novel approach for building ECOC classi ers has been proposed. The corresponding algorithm is based on simulated annealing, whose energy function is anologous to the potential of a system of charges. Experimental results show that in the con guration of minimum energy the distances between codewords have high mean and low variance. A method for feature extraction based on the coding matrix has also been presented, three score functions for selecting words have been compared. As for future work, more detailed experiments will be made on the ability of score functions to guarantee good classi cation performance. In particular, the generalized version of , able to deal with unbalanced datasets, will be experimented in a comparative setting.