arXiv:1410.0640v3 [] 6 Oct 2014

Term-Weighting Learning via Genetic Programming for
Text Classification
Hugo Jair Escalantea,∗, Mauricio A. Garcı́a-Limóna , Alicia Morales-Reyesa ,
Mario Graffb , Manuel Montes-y-Gómeza , Eduardo F. Moralesa
a

Computer Science Department,
Instituto Nacional de Astrofı́sica, Óptica y Electrónica,
Luis Enrique Erro 1, Puebla, 72840, Mexico
b
División de Estudios de Postgrado
Facultad de Ingenierı́a Eléctrica
Universidad Michoacana de San Nicolás de Hidalgo, México

Abstract
This paper describes a novel approach to learning term-weighting schemes
(TWSs) in the context of text classification. In text mining a TWS determines the way in which documents will be represented in a vector space
model, before applying a classifier. Whereas acceptable performance has been
obtained with standard TWSs (e.g., Boolean and term-frequency schemes),
the definition of TWSs has been traditionally an art. Further, it is still a difficult task to determine what is the best TWS for a particular problem and it
is not clear yet, whether better schemes, than those currently available, can
be generated by combining known TWS. We propose in this article a genetic
program that aims at learning effective TWSs that can improve the performance of current schemes in text classification. The genetic program learns
how to combine a set of basic units to give rise to discriminative TWSs. We
report an extensive experimental study comprising data sets from thematic
and non-thematic text classification as well as from image classification. Our
study shows the validity of the proposed method; in fact, we show that TWSs
learned with the genetic program outperform traditional schemes and other
Corresponding author.
Email addresses: hugojair@inaoep.mx (Hugo Jair Escalante),
mauricio.garcia.cs@gmail.com (Mauricio A. Garcı́a-Limón), a.morales@inaoep.mx
(Alicia Morales-Reyes), mgraffg@gmail.com (Mario Graff), mmontesg@inaoep.mx
(Manuel Montes-y-Gómez), emorales@inaoep.mx (Eduardo F. Morales)
∗

Preprint submitted to Elsevier

October 8, 2014

TWSs proposed in recent works. Further, we show that TWSs learned from
a specific domain can be effectively used for other tasks.
Keywords: Term-weighting Learning, Genetic Programming, Text Mining,
Representation Learning, Bag of words.
2000 MSC: code 68T10,
2000 MSC: 68T20
1. Introduction
Text classification (TC) is the task of associating documents with predefined categories that are related to their content. TC is an important and
active research field because of the large number of digital documents available and the consequent need to organize them. The TC problem has been
approached with pattern classification methods, where documents are represented as numerical vectors and standard classifiers (e.g., naı̈ve Bayes and
support vector machines) are applied (Sebastiani, 2008). This type of representation is known as the vector space model (VSM) (Salton and Buckley,
1988). Under the VSM one assumes a document is a point in a N-dimensional
space and documents that are closer in that space are similar to each other (Turney and Pantel,
2010). Among the different instances of the VSM, perhaps the most used
model is the bag-of-words (BOW) representation. In the BOW it is assumed
that the content of a document can be determined by the (orderless) set of
terms1 it contains. Documents are represented as points in the vocabulary
space, that is, a document is represented by a numerical vector of length equal
to the number of different terms in the vocabulary (the set of all different
terms in the document collection). The elements of the vector specify how
important the corresponding terms are for describing the semantics or the
content of the document. BOW is the most used document representation
in both TC and information retrieval. In fact, the BOW representation has
been successfully adopted for processing other media besides text, including,
images (Csurka et al., 2004), videos (Sivic and Zisserman, 2003), speech signals (S.Manchala et al., 2014), and time series (Wanga et al., 2013) among
others.
A crucial component of TC systems using the BOW representation is the
1

A term is any basic unit by which documents are formed, for instance, terms could be
words, phrases, and sequences (n-grams) of words or characters.

2

term-weighting scheme (TWS), which is in charge of determining how relevant a term is for describing the content of a document (Feldman and Sanger,
2006; Altyncay and Erenel, 2010; Lan et al., 2009; Debole and Sebastiani,
2003). Traditional TWS are term-frequency (TF ), where the importance of a
term in a document is given by its frequency of occurrence in the document;
Boolean (B ), where the importance of a term in document is either 1, when
the term appear in the document or 0, when the term does not appear in
the document; and term-frequency inverse-document-frequency (TF-IDF ),
where the importance of a term for a document is determined by its occurrence frequency times the inverse frequency of the term across the corpus
(i.e., frequent terms in the corpus, as prepositions and articles, receive a low
weight). Although, TC is a widely studied topic with very important developments in the last two decades (Sebastiani, 2008; Feldman and Sanger,
2006), it is somewhat surprising that little attention has been paid to the
development of new TWSs to better represent the content of documents for
TC. In fact, it is quite common in TC systems that researchers use one or
two common TWSs (e.g., B, TF or TF-IDF ) and put more effort in other
processes, like feature selection (Forman, 2003; Yang and Pedersen, 1997),
or the learning process itself (Agarwal and Mittal, 2014; Aggarwal, 2012;
Escalante et al., 2009). Although all of the TC phases are equally important, we think that by putting more emphasis on defining or learning effective
TWSs we can achieve substantial improvements in TC performance.
This paper introduces a novel approach to learning TWS for TC tasks.
A genetic program is proposed in which a set of primitives and basic TWSs
are combined through arithmetic operators in order to generate alternative
schemes that can improve the performance of a classifier. Genetic programming is a type of evolutionary algorithm in which a population of programs is
evolved (Langdon and Poli, 2001), where programs encode solutions to complex problems (mostly modeling problems), in this work programs encode
TWSs. The underlying hypothesis of our proposed method is that an evolutionary algorithm can learn TWSs of comparable or even better performance
than those proposed so far in the literature.
Traditional TWSs combine term-importance and term-document-importance
factors to generate TWSs. For instance in TF-IDF, TF and IDF are termdocument-importance and term-importance factors, respectively. Term-document
weights are referred as local factors, because they account for the occurrence
of a term in a document (locally). On the other hand, term-relevance weights
are considered global factors, as they account for the importance of a term
3

across the corpus (globally). It is noteworthy that the actual factors that define a TWS and the combination strategy itself have been determined manually. Herein we explore the suitability of learning these TWSs automatically,
by providing a genetic program with a pool of TWSs’ building blocks with
the goal of evolving a TWS that maximizes the classification performance
for a TC classifier. We report experimental results in many TC collections
that comprise both: thematic and non-thematic TC problems. Throughout
extensive experimentation we show that the proposed approach is very competitive, learning very effective TWSs that outperform most of the schemes
proposed so far. We evaluate the performance of the proposed approach under different settings and analyze the characteristics of the learned TWSs.
Additionally, we evaluate the generalization capabilities of the learned TWSs
and even show that a TWS learned from text can be used to effectively represent images under the BOW formulation.
The rest of this document is organized as follows. Next section formally
introduces the TC task and describes common TWSs. Section 3 reviews
related work on TWSs. Section 4 introduces the proposed method. Section 5 describes the experimental settings adopted in this work and reports
results of experiments that aim at evaluating different aspects of the proposed approach. Section 6 presents the conclusions derived from this paper
and outlines future research directions.
2. Text classification with the Bag of Words
The most studied TC problem is the so called thematic TC (or simply
text categorization) (Sebastiani, 2008), which means that classes are associated to different themes or topics (e.g., classifying news into “Sports” vs.
“Politics” categories). In this problem, the sole occurrence of certain terms
may be enough to determine the topic of a document; for example, the occurrence of words/terms “Basketball”, “Goal”, “Ball”, and “Football” in a
document is strong evidence that the document is about “Sports”. Of course,
there are more complex scenarios for thematic TC, for example, distinguishing documents about sports news into the categories: “Soccer” vs. “NFL”.
Non-thematic TC, on the other hand, deals with the problem of associating
documents with labels that are not (completely) related to their topics. Nonthematic TC includes the problems of authorship attribution (Stamatatos,
2009), opinion mining and sentiment analysis (Pang et al., 2002), authorship
verification (Koppel and Schler, 2004), author profiling (Koppel et al., 2002),
4

among several others (Reyes and Rosso, 2014; Kiddon and Brun, 2011). In
all of these problems, the thematic content is of no interest, nevertheless,
it is common to adopt standard TWSs for representing documents in nonthematic TC as well (e.g., BOW using character n-grams or part-of-speech
tags (Stamatatos, 2009)).
It is noteworthy that the BOW representation has even trespassed the
boundaries of the text media. Nowadays, images (Csurka et al., 2004), videos (Sivic and Zisserman,
2003), audio (S.Manchala et al., 2014), and other types of data (Wanga et al.,
2013) are represented throughout analogies to the BOW. In non-textual data,
a codebook is first defined/learned and then the straight BOW formulation
is adopted. In image classification, for example, visual descriptors extracted
from images are clustered and the centers of the clusters are considered as
visual words (Csurka et al., 2004; Zhang et al., 2007). Images are then represented by numerical vectors (i.e., a VSM) that indicate the relevance of
visual words for representing the images. Interestingly, in other media than
text (e.g., video, images) it is standard to use only the TF TWS, hence motivating the study on the effectiveness of alternative TWSs in non-textual
tasks. Accordingly, in this work we also perform experiments on learning
TWSs for a standard computer vision problem (Fei-Fei et al., 2004).
TC is a problem that has been approached mostly as a supervised learning
task, where the goal is to learn a model capable of associating documents to
categories (Sebastiani, 2008; Feldman and Sanger, 2006; Agarwal and Mittal,
2014). Consider a data set of labeled documents D = (xi , yi ){1,...,N } with N
pairs of documents (xi ) and their classes (yi ) associated to a TC problem;
where we assume xi ∈ Rp (i.e., a VSM) and yi ∈ C = {1, . . . K}, for a problem with K−classes. The goal of TC is to learn a function f : Rp → C from
D that can be used to make predictions for documents with unknown labels,
the so called test set: T = {xT1 , . . . , xTM }. Under the BOW formulation, the
dimensionality of documents’ representation, p, is defined as p = |V |, where
V is the vocabulary (i.e., the set all the different terms/words that appear
in a corpus). Hence, each document di is represented by a numerical vector
xi = hxi,1 . . . , xi,|V | i, where each element xi,j , j = 1, . . . , |V |, of xi indicates
how relevant word tj is for describing the content of di , and where the value
of xi,j is determined by the TWS.
Many TWSs have been proposed so far, including unsupervised (Sebastiani,
2008; Salton and Buckley, 1988; Feldman and Sanger, 2006) and supervised
schemes (Debole and Sebastiani, 2003; Lan et al., 2009), see Section 3. Unsupervised TWSs are the most used ones, they were firstly proposed for
5

information retrieval tasks and latter adopted for TC (Sebastiani, 2008;
Salton and Buckley, 1988). Unsupervised schemes rely on term frequency
statistics and measurements that do not take into account any label information. For instance, under the Boolean (B) scheme xi,j = 1 if f term
tj appears in document i and 0 otherwise; while in the term-frequency
(TF ) scheme, xi,j = #(di , tj ), where #(di , tj ) accounts for the times term
tj appears in document di . On the other hand, supervised TWSs aim at
incorporating discriminative information into the representation of documents (Debole and Sebastiani, 2003). For example in the TF-IG scheme,
xi,j = #(di , tj ) × IG(tj ), is the product of the TF TWS for term tj and
document di (a local factor) with the information gain of term tj (IG(tj ),
global factor). In this way, the discrimination power of each term is taken
into account for the document representation; in this case through the information gain value (Yang and Pedersen, 1997). It is important to emphasize
that most TWSs combine information from both term-importance (global)
and term-document-importance (local) factors (see Section 3), for instance,
in the TF-IG scheme, IG is a term-importance factor, whereas TF is a termdocument-importance factor.
Although acceptable performance has been reported with existing TWS,
it is still an art determining the adequate TWS for a particular data set; as
a result, mostly unsupervised TWSs (e.g., B, TF and TF-IDF ) have been
adopted for TC systems (Feldman and Sanger, 2006; Aggarwal, 2012). A first
hypothesis of this work is that different TWSs can achieve better performance
on different TC tasks (e.g., thematic TC vs. non-thematic TC); in fact, we
claim that within a same domain (e.g., news classification) different TWSs
are required to obtain better classification performance on different data sets.
On the other hand, we notice that TWSs have been defined as combinations
of term-document weighting factors (which can be seen as other TWSs, e.g.,
TF ) and term-relevance measurements (e.g., IDF or IG), where the definition of TWSs has been done by relying on the expertise of users/researchers.
Our second hypothesis is that the definition of new TWSs can be automated.
With the aim of verifying both hypotheses, this paper introduces a genetic
program that learns how to combine term-document-importance and termrelevance factors to generate effective TWSs for diverse TC tasks.

6

3. Related work
As previously mentioned, in TC it is rather common to use unsupervised
TWSs to represent documents, specifically B, TF and TF-IDF schemes are
very popular (see Table 1). Their popularity derives from the fact that these
schemes have proved to be very effective in information retrieval (Salton and Buckley,
1988; Baeza-Yates and Ribeiro-Neto, 1999; Turney and Pantel, 2010) and
in many TC problems as well as (Sebastiani, 2008; Feldman and Sanger,
2006; Agarwal and Mittal, 2014; Aggarwal, 2012; Aggarwal and Zhai, 2012).
Unsupervised TWSs mainly capture term-document occurrence (e.g., term
occurrence frequency, TF ) and term-relevance (e.g., inverse document frequency, IDF ) information. While acceptable performance has been obtained with such TWSs in many applications, in TC one has available labeled documents, and hence, document-label information can also be exploited to obtain more discriminative TWSs. This observation was noticed
by Debole & Sebastiani and other authors that have introduced supervised
TWSs (Debole and Sebastiani, 2003; Lan et al., 2009).
Supervised TWSs take advantage of labeled data by incorporating a discriminative term-weighting factor into the TWSs. In (Debole and Sebastiani,
2003) TWSs were defined by combining the unsupervised TF scheme with the
following term-relevance criteria: information gain (TF-IG), which measures
the reduction of entropy when using a term as classifier (Yang and Pedersen,
1997); χ2 (TF-CHI ), makes an independence test regarding a term and the
classes (Sebastiani, 2008); and gain-ratio (TF-GR) measuring the gain-ratio
when using the term as classifier (Debole and Sebastiani, 2003). The conclusions from (Debole and Sebastiani, 2003) were that small improvements
can be obtained with supervised TWSs over unsupervised ones. Although
somewhat disappointing, it is interesting that for some scenarios supervised
TWSs were beneficial. More recently, Lan et al. proposed an alternative
supervised TWS (Lan et al., 2009), the so called TF-RF scheme. TF-RF
combines TF with a criterion that takes into account the true positives
and true negative rates when using the occurrence of the term as classifier.
In (Lan et al., 2009) the proposed TF-RF scheme obtained better performance than unsupervised TWSs and even outperformed the schemes proposed in (Debole and Sebastiani, 2003). In (Altyncay and Erenel, 2010) the
RF term-relevance factor was compared with alternative weights, including
mutual information, odds ratio and χ2 ; in that workRF outperformed the
other term-importance criteria.
7

Table 1 shows most of the TWSs proposed so far for TC. It can be observed that TWSs are formed by combining term-document (TDR) and term
(TR) relevance weights. The selection of what TDR and TR weights to use
rely on researchers choices (and hence on their biases). It is quite common
to use TF as TDR, because undoubtedly the term-occurrence frequency carries on very important information: we need a way to know what terms a
document is associated with. However, it is not that clear what TR weight
to use, as there is a wide variety of TR factors that have been proposed. The
goal of TRs is to determine the importance of a given term, with respect
to the documents in a corpus (in the unsupervised case) or to the classes
of the problem (in the supervised case). Unsupervised TRs include: global
term-frequency, and inverse document frequency (IDF) TRs. These weights
can capture word importance depending on its global usage across a corpus,
however, for TC seems more appealing to use discriminative TRs as one can
take advantage of training labeled data. In this aspect, there is a wide variety
of supervised TRs that have been proposed, including: mutual information,
information gain, odds ratio, etcetera (Aggarwal and Zhai, 2012).
Table 1: Common term weighting schemes for TC. In every TWS, xi,j indicates how
relevant term tj is for describing the content of document di , under the corresponding
TWS. N is the number of documents in training data set, #(di , tj ) indicates the frequency
of term tj in document di , df (tj ) is the number of documents in which term tj occurs,
IG(tj ) is the information gain of term tj , CHI(tj ) is the χ2 statistic for term tj , and T P ,
T N are the true positive and true negative rates for term tj (i.e., the number of positive,
resp. negative, documents that contain term tj ).
Acronym Name
B
Boolean

Formula
xi,j = 1{#(t ,d )>0}
i j

TermFrequency
TF - Inverse
Document
Frequency
TF - Information Gain

xi,j = #(ti , dj )

TFCHI

TF square

xi,j = #(ti , dj ) ×
CHI(tj )

TF-RF

TF - Relevance
Frequency

TF
TFIDF
TF-IG

Chi-

xi,j = #(ti , dj ) ×
)
log( df N
(tj )
xi,j =
IG(tj )

xi,j

=

#(ti , dj ) ×

#(ti , dj ) ×

TP
)
log(2 + max(1,T
N)

Description
Indicates
the
prescense/abscense
of
terms
Accounts for the frequency
of occurrence of terms
An TF scheme that penalizes the frequency of terms
across the collection
TF scheme that weights
term occurrence by its information gain across the
corpus.
TF scheme that weights
term occurrence by its χ2
statistic
TF scheme that weights
term occurrence by its χ2
statistic

Ref.
(Salton and Buckley,
1988)
(Salton and Buckley,
1988)
(Salton and Buckley,
1988)
(Debole and Sebastiani,
2003)

(Debole and Sebastiani,
2003)
(Lan et al., 2009)

The goal of a supervised TR weight is to determine the importance of a
given term with respect to the classes. The simplest, TR would be to estimate the correlation of term frequencies and the classes, although any other
8

criterion that accounts for the association of terms and classes can be helpful
as well. It is interesting that although many TRs are available out there, they
have been mostly used for feature selection rather than for building TWSs for
TC. Comprehensive and extensive comparative studies using supervised TRs
for feature selection have been reported (Altyncay and Erenel, 2010; Forman,
2003; Yang and Pedersen, 1997; Mladenic and Grobelnik, 1999). Although
not being conclusive, these studies serve to identify the most effective TRs
weights, such weights are considered in this study.
To the best of our knowledge, the way we approach the problem of learning TWSs for TC is novel. Similar approaches based on genetic programming to learn TWSs have been proposed in (Cummins and O’Riordan, 2006,
2007, 2005; Trotman, 2005; Oren, 2002; Fan et al., 2004a), however, these researchers have focused on the information retrieval problem, which differs significantly from TC. Early approaches using genetic programming to improve
the TF-IDF scheme for information retrieval include those from (Trotman,
2005; Oren, 2002; Fan et al., 2004a,b). More recently, Cummins et al. proposed improved genetic programs to learn TWSs also for information retrieval (Cummins and O’Riordan, 2006, 2007, 2005).
Although the work by Cummins et al. is very related to ours, there are
major differences (besides the problem being approached): Cummins et al.
approached the information retrieval task and defined a TWS as a combination of three factors: local, global weighting schemes and a normalization
factor2 . The authors designed a genetic program that aimed at learning a
TWS by evolving the local and global schemes separately. Only 11 terminals, including constants, were considered. Since information retrieval is an
unsupervised task, the authors have to use a whole corpus with relevance
judgements (i.e., a collection of documents with queries and the set of relevant documents to each query) to learn the TWS, which, once learned, could
be used for other information retrieval tasks. Hence they require a whole
collection of documents to learn a TWS. On the other hand, the authors
learned a TWS separately, first a global TWS was evolved fixing a binary
local scheme, then a local scheme was learned by fixing the learned global
weight. Hence, they restrict the search space for the genetic program, which
2

Recall a local factor incorporates term information (locally) available in a document,
whereas a global term factor takes into account term statistics estimated across the whole
corpus. In information retrieval it is also common to normalize the vectors representing a
document to reduce the impact of the length of a document.

9

may limit the TWSs that can be obtained. Also, it is worth noticing that the
focus of the authors of (Cummins and O’Riordan, 2006, 2007, 2005) was on
learning a single, and generic TWS to be used for other information retrieval
problems, hence the authors performed many experiments and reported the
single best solution they found after extensive experimentation. Herein, we
provide an extensive evaluation of the proposed approach, reporting average performance over many runs and many data sets. Finally, one should
note that the approach from (Cummins and O’Riordan, 2006, 2007, 2005) required of large populations and numbers of generations (1000 individuals and
500 generations were used), whereas in this work competitive performance is
obtained with only 50 individuals and 50 generations.
4. Learning term-weighting schemes via GP
As previously mentioned, the traditional approach for defining TWSs has
been somewhat successful so far. Nevertheless, it is still unknown whether
we can automatize the TWS definition process and obtain TWSs of better
classification performance in TC tasks. In this context, we propose a genetic
programming solution that aims at learning effective TWSs automatically.
We provide the genetic program with a pool of TDR and TR weights as
well as other TWSs and let a program search for the TWS that maximizes
an estimate of classification performance. Thus, instead of defining TWSs
based on our own experiences on text mining, we let a computer itself to build
an effective TWS. The advantages of this approach are that it may allow to
learn a specific TWS for each TC problem, or to learn TWSs from one data
set (e.g., a small one) and implement it in a different collection (e.g., a
huge one). Furthermore, the method reduces the dependency on users/dataanalysts and their degree of expertise and biases for defining TWSs. The
rest of this section describes the proposed approach. We start by providing a
brief overview of genetic programming, then we explain in detail the proposal,
finally, we close this section with a discussion on the benefits and limitations
of our approach.
4.1. Genetic programming
Genetic programming (GP) (Langdon and Poli, 2001) is an evolutionary
technique which follows the reproductive cycle of other evolutionary algorithms such as genetic algorithms (see Figure 1): an initial population is
created (randomly or by a pre-defined criterion), after that, individuals are
10

selected, recombined, mutated and then placed back into the solutions pool.
The distinctive feature of GP, when compared to other evolutionary algorithms, is in that complex data structures are used to represent solutions
(individuals), for example, trees or graphs. As a result, GP can be used for
solving complex learning/modeling problems. In the following we describe
the GP approach to learn TWSs for TC.

Figure 1: A generic diagram of an evolutionary algorithm.

4.2. TWS learning with genetic programming
We face the problem of learning TWSs as an optimization one, in which
we want to find a TWSs that maximizes the classification performance of a
classifier trained with the TWS. We define a valid TWS as the combination
of: (1) other TWSs, (2) TR and (3) TDR factors, and restrict the way in
which such components can be combined by a set of arithmetic operators.
We use GP as optimization strategy, where each individual corresponds to a
tree-encoded TWS. The proposed genetic program explores the search space
of TWSs that can be generated by combining TWSs, TRs and TDRs with

11

a predefined set of operators. The rest of this section details the components of the proposed genetic program, namely, representation, terminals
and function set, genetic operators and fitness function.
4.2.1. Representation
Solutions to our problem are encoded as trees, where we define terminal
nodes to be the building blocks of TWSs. On the other hand, we let internal
nodes of trees to be instantiated by arithmetic operators that combine the
building blocks to generate new TWSs. The representation is graphically
described in Figure 2.

Figure 2: Representation adopted for TWS learning.

4.2.2. Terminals and function set
As previously mentioned, traditional TWSs are usually formed by two factors: a term-document relevance (TDR) weight and a term-relevance (TR)
factor. The most used TDR is term frequency (TF ), as allows one to relate
documents with the vocabulary. We consider TF as TDR indicator, but also
we consider standard TWSs (e.g., Boolean, TD, RF ) as TDR weights. The
decision to include other TWSs as building blocks is in order to determine
whether standard TWSs can be enhanced with GP. Regarding TR, there
are many alternatives available. In this work we analyzed the most common and effective TR weights as reported in the literature (Sebastiani, 2008;
12

Altyncay and Erenel, 2010; Lan et al., 2009; Debole and Sebastiani, 2003;
Forman, 2003) and considered them as building blocks for generating TWSs.
Finally we also considered some constants as building blocks. The full set
of building blocks (terminals in the tree representation) considered is shown
in Table 1, whereas the set of operators considered in the proposed
method
√
2
(i.e., the function set) is the following: F = {+, −, ∗, /, log2 x, x, x }, where
F includes operators of arities one and two.
Table 2: Terminal set.
Variable
W1
W2
W3
W4
W5
W6
W7
W8
W9
W10
W11
W12
W13
W14
W15
W16
W17
W18
W19
W20
W21
W22

Meaning
N, Constant matrix, the total number of training documents.
kV k, Constant matrix, the number of terms.
CHI, Matrix containing in each row the vector of χ2 weights for the terms.
IG, Matrix containing in each row the vector of information gain weights for the terms.
T F − IDF , Matrix with the TF-IDF term weighting scheme.
T F , Matrix containing the TF term-weighting scheme.
F GT , Matrix containing in each row the global term-frequency for all terms.
T P , Matrix containing in each row the vector of true positives for all terms.
F P , Matrix containing in each row the vector of false positives.
T N, Matrix containing in each row the vector of true negatives.
F N, Matrix containing in each row the vector of false negatives.
Accuracy, Matrix in which each row contains the accuracy obtained when using the term as classifier.
Accuracy Balance, Matrix containing the AC Balance each (term, class).
BNS, An array that contains the value for each BNS per (term, class).
DF req, Document frequency matrix containing the value for each (term, class).
F M easure, F-Measure matrix containing the value for each (term, class).
OddsRatio, An array containing the OddsRatio term-weighting.
P ower, Matrix containing the Power value for each (term, class).
P robabilityRatio, Matrix containing the ProbabilityRatio each (term, class).
M ax T erm, Matrix containing the vector with the highest repetition for each term.
RF , Matrix containing the RF vector.
T F × RF , Matrix containing T F × RF .

In the proposed approach, a TWS is seen as a combination of building blocks by means of arithmetic operators. One should note, however,
that three types of building blocks are considered: TDR, TR and constants.
Hence we must define a way to combine matrices (TDR weights), vectors
(TR scores) and scalars (the constants), in such a way that the combination
leads to a TWS (i.e., a form of TDR). Accordingly, and for easiness of implementation, each building block shown in Table 1 is processed as a matrix
of the same length as the TWS (i.e., N × |V |) and operations are performed
element-wise. In this way a tree can be directly evaluated, and the operators
are applied between each element of the matrices, leading to a TWS.
TDRs are already matrices of the same size as the TWSs: N × |V |. In
the case of TRs, we have a vector of length |V |, thus for each TR we generate
a matrix of size N × |V | where each of its rows is the TR; that is, we repeat
N times the TR weight. In this way, for example, a TWS like TF-IDF can
13

be obtained as T F × IDF , where the × operator means that each element
tfi,j of TF is multiplied by each element of the IDF matrix idfi,j and where
idfi,j = log( dfN(tj ) ) for i = 1, . . . , N, all TRs were treated similarly. In the case
of constants we use a scalar-matrix operator, which means that the constant
is operated with each element of the matrix under analysis.
Estimating the matrices each time a tree is evaluated can be a time consuming process, therefore, at the beginning of the search process we compute
the necessary matrices for every terminal from Table 1. Hence, when evaluating an individual we only have to use the values of the precomputed matrices
and apply the operators specified by a tree.
4.2.3. Genetic operators
As explained above, in GP a population of individuals is initialized and
evolved according to some operators that aim at improving the quality of the
population. For initialization we used the standard ramped-half-and-half
strategy (Eiben and Smith, 2010), which generates half of the population
with (balanced) trees of maximum depth, and the other half with trees of
variable depth. As genetic operators we also used standard mechanisms: we
considered the subtree crossover and point mutation. The role of crossover
is to take two promising solutions and combine their information to give rise
to two offspring, with the goal that the offspring have better performance
than the parents. The subtree crossover works by selecting two parent solutions/trees (in our case, via tournament) and randomly select an internal
node in each of the parent trees. Two offspring are created by interchanging
the subtrees below the identified nodes in the parent solutions.
The function of the mutation operator is to produce random variations in
the population, facilitating the exploration capabilities of GP. The considered
mutation operator first selects an individual to be mutated. Next an internal
node of the individual is identified, and if the internal node is an operator
(i.e., a member of F ) it is replaced by another operator of the same arity. If
the chosen node is a terminal, it is replaced by another terminal. Where in
both cases the replacing node is selected with uniform probability.
4.2.4. Fitness function
As previously mentioned, the aim of the proposed GP approach is to
generate a TWS that obtains competitive classification performance. In this
direction, the goodness of an individual is assessed via the classification performance of a predictive model that uses the representation generated by the
14

TWS. Specifically, given a solution to the problem, we first evaluate the tree
to generate a TWS using the training set. Once training documents are represented by the corresponding TWS, we perform a k−fold cross-validation
procedure to assess the effectiveness of the solution. In k−fold cross validation, the training set is split into k disjoint subsets, and k rounds of training
and testing are performed; in each round k − 1 subsets are used as training
set and 1 subset is used for testing, the process is repeated k times using a
different subset for testing each time. The average classification performance
is directly used as fitness function. Specifically, we evaluate the performance
of classification models with the f1 measure. Let T P , F P and F N to denote
the true positives, false positives and false negative rates for a particular class,
P
P
precision (P rec) is defined as T PT+F
and recall (Rec) as T PT+F
. f1 -measure
P
N
rec×Rec
.
is simply the harmonic average between precision and recall: f1 = 2×P
P rec+Rec
The average across classes is reported (also called, macro-average f1 ), this
way of estimating the f1 -measure is known to be particularly useful when
tackling unbalanced data sets (Sebastiani, 2008).
Since under the fitness function k models have to be trained and tested for
the evaluation of a single TWS, we need to look for an efficient classification
model that, additionally, can deal naturally with the high-dimensionality of
data. Support vector machines (SVM) comprise a type of models that have
proved to be very effective for TC (Sebastiani, 2008; Joachims, 2008). SVMs
can deal naturally with the sparseness and high dimensionality of data, however, training and testing an SVM can be a time consuming process. Therefore, we opted for efficient implementations of SVMs that have been proposed
recently (Zhang et al., 2012; Djuric et al., 2013). That methods are trained
online and under the scheme of learning with a budget. We use the predictions of an SVM as the fitness function for learning TWSs. Among the methods available in (Djuric et al., 2013) we used the low-rank linearized SVM
(LLSMV) (Zhang et al., 2012). LLSVM is a linearized version of non-linear
SVMs, which can be trained efficiently with the so called block minimization
framework (Chang and Roth, 2011). We selected LLSVM instead of alterative methods, because this method has outperformed several other efficient
implementations of SVMs, see e.g., (Djuric et al., 2013; Zhang et al., 2012).
4.3. Summary
We have described the proposed approach to learn TWSs via GP. When
facing a TC problem we start by estimating all of the terminals described in
Table 1 for the training set. The terminals are feed into the genetic program,
15

together with the function set. We used the GPLAB toolbox for implementing the genetic program with default parameters (Silva and Almeida, 2003).
The genetic program searches for the tree that maximizes the k−fold cross
validation performance of an efficient SVM using training data only. After a
fixed number of generations, the genetic program returns the best solution
found so far, the best TWS. Training and test (which was not used during the
search process) data sets are represented according to such TWS. One should
note that all of the supervised term-weights in Table 1 are estimated from
the training set only (e.g., the information gain for terms is estimated using
only the labeled training data); for representing test data we use the precomputed term-weights. Next, the LLSVM is trained in training data and
the trained model makes predictions for test samples. We evaluate the performance of the proposed method by comparing the predictions of the model
and the actual labels for test samples. The next section reports results of
experiments that aim at evaluating the validity of the proposed approach.
5. Experiments and results
This section presents an empirical evaluation of the proposed TWL approach. The goal of the experimental study is to assess the effectiveness of
the learned TWSs and compare their performance to existing schemes. Additionally, we evaluate the generalization performance of learned schemes,
and their effectiveness under different settings.
5.1. Experimental settings
For experimentation we considered a suite of benchmark data sets associated to three types of tasks: thematic TC, authorship attribution (AA,
a non-thematic TC task) and image classification (IC). Table 3 shows the
characteristics of the data sets. We considered three types of tasks because
we wanted to assess the generality of the proposed approach.
Seven thematic TC data sets were considered, in these data sets the goal
is to learn a model for thematic categories (e.g., sports news vs. religion
news). The considered data sets are the most used ones for the evaluation
of TC systems (Sebastiani, 2008). For TC data sets, indexing terms are the
words (unigrams). Likewise, seven data sets for AA were used, the goal in
these data sets is to learn a model capable of associating documents with
authors. Opposed to thematic collections, the goal in AA is to model the

16

Table 3: Data sets considered for experimentation
Text categorization
Data set
Classes Terms Train Test
Reuters-8
8
23583
5339
2333
Reuters-10
10
25283
6287
2811
20-Newsgroup
20
61188
11269
7505
TDT-2
30
36771
6576
2818
WebKB
4
7770
2458
1709
Classic-4
4
5896
4257
2838
CADE-12
12
193731 26360 14618
Authorship attribution
Data set
Classes Terms Train Test
CCA-10
10
15587
500
500
Poetas
5
8970
71
28
Football
3
8620
52
45
Business
6
10550
85
90
Poetry
6
8016
145
55
Travel
4
11581
112
60
Cricket
4
10044
98
60
Image Classification
Data set
Classes Terms Train Test
Caltech-101
101
12000
1530
1530
Caltech-tiny
5
12000
75
75

writing style of authors, hence, it has been shown that different representations and attributes are necessary for facing this task (Stamatatos, 2009).
Accordingly, indexing terms in AA data sets were 3-grams of characters, that
is, sequences of 3-characters found in documents, these terms have proved to
be the most effective ones in AA (Stamatatos, 2009; Escalante et al., 2011;
Luyckx and Daelemans, 2010). Finally, two data sets for image classification, taken from the CALTECH-101 collection, were used. We considered
the collection under the standard experimental settings (15 images per class
for training and 15 images for testing), two subsets of the CALTECH-101
data set were used: a small one with only 5 categories and the whole data
set with 102 classes (101 object categories plus background) (Fei-Fei et al.,
2004). Images were represented under the Bag-of-Visual-Words formulation
using dense sift descriptors (PHOW features): descriptors extracted from
images were clustered using k−means, the centers of the clusters are the visual words (indexing terms), images are then represented by accounting the
occurrence of visual words, the VLFEAT toolbox was used for processing
images (Vedaldi and Fulkerson, 2008).
The considered data sets have been partitioned into training and test
subsets (the number of documents for each partition and each data set are
shown in Table 3). For some data sets there were predefined categories, while
17

for others we randomly generated them using 70% of documents for training
and the rest for testing. All of the preprocessed data sets in Matlab format
are publicly available3 .
For each experiment, the training partition was used to learn the TWS,
as explained in Section 4. The learned TWS is then evaluated in the corresponding test subset. We report two performance measures: accuracy, which
is the percentage of correctly classified instances, and f1 measure, which assesses the tradeoff between precision and recall across classes (macro-average
f1 ), recall that f1 was used as fitness function (see Section 4).
The genetic program was run for 50 generations using populations of 50
individuals, we would like to point out that in each run of the proposed
method we have used default parameters. It is expected that by optimizing
parameters and running the genetic program for more generations and larger
populations we could obtain even better results. The goal of our study, however, was to show the potential of our method even with default parameters.
5.2. Evaluation of TWS Learning via Genetic Programming
This section reports experimental results on learning TWSs with the genetic program described in Section 4. The goal of this experiment is to assess
how TWSs learned via GP compare with traditional TWSs. The GP method
was run on each of the 16 data sets from Table 3, since the vocabulary size
for some data sets is huge we decided to reduce the number of terms by using
term-frequency as criterion. Thus, for each data set we considered the top
2000 more frequent terms during the search process. In this way, the search
process is accelerated at no significant loss of accuracy. In Section 5.3 we
analyze the robustness of our method when using the whole vocabulary size
for some data sets.
For each data set we performed 5 runs with the GP-based approach, we
evaluated the performance of each learned TWS and report the average and
standard deviation of performance across the five runs. Tables 4, 5, and 6
show the performance obtained by TWSs learned for thematic TC, AA and
IC data sets, respectively. In the mentioned tables we also show the result
obtained by the best baseline in each collection. Best baseline is the best TWS
we found (from the set of TWSs reviewed in related work and the TWSs in
Table 1) for each data set (using the test-set performance). Please note that
3

http://ccc.inaoep.mx/ hugojair/TWL/

18

under these circumstances best baseline is in fact, a quite strong baseline for
our GP method. Also, we would like to emphasize that no parameter of
the GP has been optimized, we used the same default parameters for every
execution of the genetic program.
Table 4: Classification performance on thematic TC obtained with learned TWSs and the
best baseline.
PG- Avg.
Best baseline
Data set
f1
Acc.
f1
Acc.
Baseline
+
Reuters-8
90.56+
1.43
91.35
1.99
86.94
88.63
TF
−
−
+
Reuters-10
88.21+
2.69
91.84
1.01
85.24
93.25
TFIDF
−
−
20-Newsgroup 66.23+
67.97+
59.21 61.99
TF
− 3.84
− 4.16
TDT-2
96.95+
96.95+
95.20 95.21
TFIDF
− 0.41
− 0.57
WebKB
88.79+
89.12+
87.49 88.62
B
− 1.26
− 1.30
+
Classic-4
94.75− 1.08 95.42+
94.68 94.86
TF
− 0.67
CADE-12
41.03+
53.80+
39.30 41.89
TF
− 4.45
− 4.0

From Table 4 it can be seen that, regarding the best baseline, different
TWSs obtained better performance for different data sets. Hence evidencing
the fact that different TWSs are required for different problems. On the
other hand, it can be seen that the average performance of TWSs learned
with our GP outperformed significantly the best baseline in all but one result
(accuracy for Reuters-10 data set). The differences in performance are large,
mainly for the f1 measure, which is somewhat expected as this was the
measure used as fitness function (recall f1 measure is appropriate to account
for the class imbalance across classes); hence showing the competitiveness of
our proposed approach for learning effective TWSs for thematic TC tasks.
Table 5: Classification performance on AA obtained with learned TWSs and the best
baseline.
PG- Avg.
Best baseline
Data set
f1
Acc.
f1
Acc.
Baseline
+
CCA-10
70.32+
2.73
73.72
2.14
65.90
73.15
TF-IG
−
−
+
Poetas
72.23+
1.49
72.63
1.34
70.61
71.84
TF-IG
−
−
+
Football
76.37+
9.99
83.76
4.27
76.45
83.78
TF-CHI
−
−
Business 78.08+
83.58+
73.77
81.49 TF-CHI
− 4.87
− 1.57
+
Poetry
70.03+
7.66
74.05
7.38
59.93
76.71
B
−
−
+
Travel
73.92+
10.26
78.45
6.72
71.75
75.32
TF-CHI
−
−
Cricket
88.10+
92.06+
89.81 91.89 TF-CHI
− 7.12
− 3.29

From Table 5 it can be seen that for AA data sets the best baseline
19

performs similarly as the proposed approach. In terms of f1 measure, our
method outperforms the best baseline in 5 out of 7 data sets, while in accuracy our method beats the best baseline in 4 out of 7 data sets. Therefore,
our method still obtains comparable (slightly better) performance to the best
baselines, which for AA tasks were much more competitive than in thematic
TC problems. One should note that for PG we are reporting the average performance across 5 runs, among the 5 runs we found TWSs that consistently
outperformed the best baseline.
Table 6: Classification performance on IC obtained with learned TWSs and the best
baseline.
PG- Avg.
Best baseline
Data set
f1
Acc.
f1
Acc. Baseline
+
Caltech-101 61.91+
1.41
64.02
1.42
58.43
60.28
B
−
−
+
Caltech-tiny 89.70+
2.44
91.11
2.36
85.65
86.67
TF
−
−

It is quite interesting that, comparing the best baselines from Tables 4
and 5, for AA tasks supervised TWSs obtained the best results (in particular
TF-CHI in 4 out of 7 data sets), whereas for thematic TC unsupervised
TWSs performed better. Again, these results show that different TWSs are
required for different data sets and different types of problems. In fact, our
results confirm the fact that AA and thematic TC tasks are quite different,
and, more importantly, our study provides evidence on the suitability of
supervised TWSs for AA; to the best of our knowledge, supervised TWSs
have not been used in AA problems.
Table 6 shows the results obtained for the image categorization data sets.
Again, the proposed method obtained TWSs that outperformed the best
baselines. This result is quite interesting because we are showing that the
TWS plays a key role in the classification of images under the BOVWs approach. In computer vision most of the efforts so far have been devoted to the
development of novel/better low-level image-descriptors, using a BOW with
predefined TWS. Therefore, our results pave the way for research on learning TWSs for image categorization and other tasks that rely in the BOW
representation (e.g. speech recognition and video classification).
Figure 3 and Table 7 complement the results presented so far. Figure 3 indicates the difference in performance between the (average of) learned TWSs
and the best baseline for each of the considered data sets. We can clearly
appreciate from this figure the magnitude of improvement offered by the
learned TWSs, which in some cases is too large.
20

12
f

1

Difference in performance

10

Accuracy

8
6
4
2
0

Catech−tiny

Cricket

Travel

Poetry

Business

Caltech−101

Data set

Poetas

CCA

Football

CADE12

Classic4

Web−KB

TDT−2

20−Newsgroup

Reuters−10

−4

Reuters−8

−2

Figure 3: Difference in performance between learned TWSs and best baseline per each
data set, values above zero indicate better performance obtained by the TWSs.

Table 7, on the other hand, shows a more fair comparison between our
method and the reference TWSs: it shows the average performance obtained
by reference schemes and the average performance of our method for thematic
TC, AA and IC data sets. It is clear from this table that in average our
method performs consistently better than any of the reference methods in
terms of both accuracy and f1 measure for the three types of tasks. Thus,
from the results of this table and those from Tables 4, 5, and 6, it is evident
that standard TWSs are competitive, but one can take advantage of them
only when the right TWS is selected for each data set. Also, the performance
of TWSs learned with our approach are a better option than standard TWSs,
as in average we were able to obtain much better representations.
Summarizing the results from this section, we can conclude that:
• The proposed GP obtained TWSs that outperformed the best baselines
in the three types of tasks: thematic TC, AA and IC. Evidencing the
generality of our proposal across different data types and modalities.
Larger improvements were observed for thematic TC and IC data sets.
In average, learned TWSs outperformed standard ones in the three
types of tasks.
21

Table 7: Average performance on thematic TC obtained with learned TWSs and the
baselines.
Thematic TC
AA
IC
TWS
f1
Acc.
f1
Acc.
f1
Acc.
TF
76.60
79.53
62.17
72.43
68.86
71.54
B
77.42
79.73
66.07
76.76
71.22
72.78
TFIDF
61.69
76.17
40.88
55.26
62.27
67.56
TF-CHI
71.56
75.63
68.75
73.69
65.38
67.45
TF-IG
64.22
69.00
68.96
74.91
66.02
67.93
PG-worst 77.81
81.19
66.47
74.84
74.30
75.67
PG-Avg. 81.01 83.63 75.58 79.75 75.81 77.07
PG-best
82.88
85.81
81.37
83.98
76.97
78.18

• Our results confirm our hypothesis that different TWSs are required
for facing different tasks, and within a same task (e.g., AA) a different TWS may be required for a different data set. Hence, motivating
further research on how to select TWS for a particular TC problem.
• We show evidence that the proposed TWS learning approach is a
promising solution for enhancing the classification performance in other
tasks than TC, e.g., IC.
• Our results show that for AA supervised TWS seem to be more appropriate, whereas unsupervised TWS performed better on thematic TC
and IC. This is a quite interesting result that may have an impact in
non-thematic TC and supervised term-weighting learning.
5.3. Varying vocabulary size
For the experiments from Section 5.2 each TWS was learned by using only
the top 2000 most frequent terms during the search process. This reduction
in the vocabulary allowed us to speed up the search process significantly,
however, it is worth asking ourselves what the performance of the TWSs
would be when using an increasing number of terms. We aim to answer such
question in this section.
For this experiment we considered three data sets, one from each type of
task: thematic TC, AA, and IC. The considered data sets were the Reuters8 (R8) for thematic TC, the CCA benchmark for AA, and Caltech-101 for
IC. These data sets are the representative ones from each task: Reuters-8
is among the most used TC data sets, CCA has been widely used for AA
as well, and Caltech-101 is the benchmark in image categorization For each
22

of the considered data sets we use a specific TWS learned using the top2000 most frequent terms (see Section 5.2), and evaluate the performance
of such TWSs when increasing the vocabulary size: terms were sorted in
ascending order of their frequency. Figures 4, 5, and 6 show the results of
this experiment in terms of f1 measure and accuracy (the selected TWS is
shown in the caption of each image).
R8

R8
1

1
0.9

0.9

0.8

0.8
0.7
Accuracy

0.6
0.5

1

f measure

0.7

0.4
0.3
0.2
0.1
0
10

TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP
20

0.6
TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP

0.5
0.4
0.3
30

40

50
60
70
Percentage of features

80

90

0.2
10

100

20

30

40

50
60
70
Percentage of features

80

90

100

√
Figure
4: Classification performance on the Reuters-8 data set for the TWS: W5 −
√
log W19
when increasing the number of considered terms. The left plot shows results in
W21
terms of f1 measure while the right plot shows accuracy performance.

f

CCA− Sthatis
0.8

0.78

0.78
0.76
TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP

0.74
0.72
0.7
0.68
10

Accuracy

0.76

1

measure

CCA (Sthatis)
0.8

20

30

40

50
60
70
Percentage of features

TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP

0.74
0.72
0.7

80

90

0.68
10

100

20

30

40

50
60
70
Percentage of features

80

90

100

Figure 5: Classification performance on the CCA data set of the TWS: W4 − (W22 + W5 )
when increasing the number of considered terms.

Different performance behavior can be observed in the different data sets.
Regarding Figure 4, which shows the performance for a thematic TC data
set, it can be seen that the TWS learned by our method outperformed all
other TWSs for any data set size. Hence confirming the suitability of the
proposed method for thematic TC.
Figure 5, on the other hand, behaves differently: the proposed method
outperforms all the other TWSs only for a single data set size (when 20%
23

Caltech−101
0.7

0.6

0.6

0.5

0.5
Accuracy

f1 measure

Caltech−101
0.7

0.4
TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP

0.3
0.2
0.1
0
10

20

30

40

50
60
70
Percentage of features

80

90

0.4
TF
B
TFIDF
TF−RF
TF−CHI
TF−IG
GP

0.3
0.2
0.1
0
10

100

20

30

40

50
60
70
Percentage of features

80

90

100

Figure
6: Classification performance on the Caltech-101 data set of the TWS:
rq
p√
W17 −
W22 when increasing the number of considered terms.

of the terms were used). In general, our method consistently outperformed
TF-CHI and TF-IG TWSs, and performs similarly as TF-IDF, but it was
outperformed by the TF-RF TWS. This result can be due to the fact that for
this AA data set, the genetic program learned a TWS that was suitable only
for the vocabulary size that was used during the optimization. Although,
interesting, this result is not that surprising: in fact, it is well known in AA
that the number of terms considered in the vocabulary plays a key role on the
performance of AA systems. AA studies suggest using a small amount of the
most-frequent terms when approaching an AA problem (Stamatatos, 2009;
Escalante et al., 2011; Luyckx and Daelemans, 2010). Results from Figure 5
corroborate the latter and seem to indicate that when approaching an AA
problem, one should first determine an appropriate vocabulary size and then
apply our method. One should note, however, that our method outperforms
the other TWSs for the data set size that was used during the optimization,
and this is, in fact, the highest performance that can be obtained with any
other TWS and data set size combination.
Finally, Figure 6 reports the performance of TWSs for the Caltech-101
data set under different data set sizes. In this case, the learned TWS outperforms all other TWSs when using more than 20% and 30% in terms of
f1 measure and accuracy, respectively. The improvement is consistent and
monotonically increases as more terms are considered. Hence showing the
robustness of the learned TWS when increasing the vocabulary size for IC
tasks. Among the other TWSs, TFIDF obtains competitive performance
when using a small vocabulary, this could be due to the fact that when considering a small number of frequent terms the IDF component is important
24

for weighting the contribution of each of the terms.
Summarizing the results from this section we can conclude the following:
• TWSs learned with our method are robust to variations in the vocabulary size for thematic TC and IC tasks. This result suggests, we can
learn TWSs using a small number of terms (making more efficient the
search process) and evaluating the learned TWSs with larger vocabularies.
• Learned TWSs outperform standard TWSs in thematic TC and IC
tasks when varying the vocabulary size.
• For AA, TWSs learned with our proposed approach seem to be more
dependent on the number of terms used during training. Hence, when
facing this type of problems it is a better option to fix the number of
terms beforehand and then running our method.
5.4. Generalization of the learned term-weights
In this section we evaluate the inter-data set generalization capabilities
of the learned TWSs. Although results presented so far show the generality
of our method across three types of tasks, we have reported results obtained
with TWSs that were learned for each specific data set. It remains unclear
whether the TWSs learned for a collection can perform similarly in other
collections, we aim to answer to this question in this section.
To assess the inter-data set generalization of TWSs learned with our
method we performed an experiment in which we considered for each data
set a single TWS and evaluated its performance across all the 16 considered
data sets. The considered TWSs are shown in Table 8, we named the variables with meaningful acronyms for clarity but also show the mathematical
expression using variables as defined in Table 2.
Before presenting the results of the experiments it is worth analyzing the
type of solutions (TWSs) learned with the proposed approach. First of all,
it can be seen that the learned TWSs are not too complex: the depth of
the trees is small and solutions have few terminals as components. This is
a positive result because it allows us to better analyze the solutions and,
more importantly, it is an indirect indicator of the absence of the over-fitting
phenomenon. Secondly, as in other applications of genetic programming, it
is unavoidable to have unnecessary terms in the solutions, for instance, the
subtree: div(pow2(TF-RF),pow2(TF-RF))), (from TWS 2) is unnecessary
25

Table 8: Considered TWSs for the inter-data set generalization experiment for each data
set. In column 2 each TWS is shown as a prefix expression, the names of the variables
are self-explanatory. Column 3 shows the mathematical expression of each TWS using the
terminal set from Table 2.
Text categorization

ID

Data set

Learned TWS

1

Reuters-8

-(sqrt(TFIDF),div(log2(sqrt(ProbR)),RF))

2

Reuters-10

sqrt(div(pow2(sqrt(TFIDF)),div(pow2(TFRF),pow2(TF-RF))))

3

20-Newsg.

Formula
√
√
log W19
W5 −
W21
v √
u ( W )2
u
5
u W2
t
22
sr

sqrt(sqrt(div(TF,GLOBTF)))

4

TDT-2

sqrt(×(sqrt(sqrt(TFIDF)), sqrt(×(sqrt(TFIDF),IG))))

5

WebKB

div(TF-RF,+(+(+(RF,TF-RF),FMEAS),FMEAS))

6
7

Classic-4
CADE-12

×(ProbR,TFIDF)
div(TF,sqrt(log2(ACCU)))

qp

2
W22
W6
W7

√

W5 ×

p√

W5 × W4
W22
(((W21 +W22 )+W16 )+W16 )

W5 × W19
√ W6
log W12

Authorship attribution
ID
8
9
10

Data set
CCA-10
Poetas
Football

Learned TWS
-(IG,plus(TF-RF,TFIDF))
-(-(RF,TF-RF),TF-IDF)
div(TF-RF,pow2(ODDSR))

Formula
W4 − (W22 + W5 )
(W21 − W22 ) − W5

11
12

Business
Poetry

minus(TF-RF,PROBR)
div(TF,log2(div(TF,log(TF-RF))))

W22 − W19

W22
W2
17

log

13

Travel

14

Cricket

ID

Data set

15

Caltech101
Caltechtiny

16

+(-(TF-RF,-(-(TF-RF,-(TFRF,POWER)),POWER)),TF)
×(IG,TF-RF)
Image Classification
Learned TWS
sqrt(sqrt(-(ODDSR,sqrt(sqrt(TF-RF)))))

(W22 − ((W22 − (W22 − W18 )) −
W18 )) + W6
W4 × W22
Formula
rq
p√
W17 −
W22
√

sqrt(-(TF-RF,ACBAL))

W6
W6
log W22

W22 − W13

because it reduces to a constant matrix; the same happens with the term
pow2(sqrt(TFIDF)). Nevertheless, it is important to emphasize that this type
of terms do not harm the performance of learned TWSs, and there are not
too many of these type of subtrees. On the other hand, it is interesting
that all of the learned TWSs incorporate supervised information. The most
used TR weight is RF, likewise the most used TDR is TFIDF. Also it is
interesting that simple operations over standard TWSs, TR and TDR weights
results in significant performance improvements. For instance, compare the
performance of TF-RF and the learned weight for Caltech-101 in Figure 6.
By simply subtracting an odds-ratio from the TF-RF TWS and applying
scaling operations, the resultant TWS outperforms significantly TF-RF.
The 16 TWSs shown in Table 8 were evaluated in the 16 data sets in order
to determine the inter-data set generality of the learned TWSs. Figure 7
shows the results of this experiment. We show the results with boxplots,

26

where each boxplot indicates the normalized4 performance of each TWSs
across the 16 data sets, for completion we also show the performance of the
reference TWSs on the 16 data sets.

1

f1 measure

0.9

0.8

0.7

0.6

Catech−tiny

Cricket

Travel

Poetry

Business

CCA

Poetas

Caltech−101

Learned TWSs

Football

Classic4

CADE12

TDT−2

Web−KB

20−NewsG.

Reuters−8

Reuters−10

TF−GI

TF−RF

TF−CHI

TF−IDF

B

TF

0.5

Figure 7: Heatmap that shows the performance of TWSs (rows 7-22) from Table 8 in the 16
data sets (x axis) considered in the study. For completion, we also show the performance
of standard TWSs (rows 1-6).

It can be seen from Figure 7 that the generalization performance of
learned TWSs is mixed. On the one hand, it is clear that TWSs learned for
thematic TC (boxplots 7-13) achieve the highest generalization performance.
Clearly, the generalization performance of these TWSs is higher than that
of traditional TWSs (boxplots 1-6). It is interesting that TWSs learned for
a particular data set/problem/modality perform well across different data
sets/problems/modalities. In particular, TWSs learned for Reuters-10 and
TDT-2 obtained the highest performance and the lowest variance among all
4

Before generating the boxplots we normalized the performance on a per-data set basis:
for each data set, the performance of the 16 TWSs was normalized to the range [0, 1], in
this way, the variation in f1 -values across data sets is eliminated, i.e, all f1 values are in
the same scale and are comparable to each other.

27

of the TWSs. On the other hand, TWSs learned for AA and IC tasks obtained lower generalization performance: the worst in terms of variance is the
TWS learned for the Poetry data set, while the worst average performance
was obtained by the TWS learned for the Football data set. TWSs learned for
IC are competitive (in generalization performance) with traditional TWSs.
Because of the nature of the tasks, the generalization performance of TWSs
learned from TC is better than that of TWSs learned for AA and IC. One
should note that these results confirm our findings from previous sections:
(i) the proposed approach is very effective mainly for thematic TC and IC
tasks; and, (ii) AA data sets are difficult to model with TWSs.
Finally, we evaluate the generality of learned TWSs across different classifiers. The goal of this experiment is to assess the extend to which the learned
TWSs are tailored for the classifier they were learn for. For this experiment,
we selected two TWSs corresponding to Caltech-tiny and Caltech-101 (15
and 16 in Table 8) and evaluated their performance of different classifiers
across the 16 data sets. Figure 8 shows the results of this experiment.
It can be seen from Figure 8 that the considered TWSs behaved quite
differently depending on the classifier. On the one hand, the classification
performance when using naı̈ve Bayes (Naive), kernel-logistic regression (KLogistic), and 1−nearest neighbors (KNN ) classifiers degraded significantly.
On the other hand, the performance SVM and the neural network (NN) was
very similar. These results show that TWSs are somewhat robust across
classifiers of similar nature as SVM and NN are very similar classifiers: both
are linear models in the parameters. The other classifiers are quite different
to the reference SVM and, therefore, the performance is poor5 . It is interesting that in some cases the NN classifier outperformed the SVM, although
in average the SVM performed better. This is a somewhat expected result
as the performance of the SVM was used as fitness function.
According to the experimental results from this section we can draw the
following conclusions:
• TWSs learned with the proposed approach are not too complex despite
their effectiveness. Most of the learned TWSs included a supervised
component, evidencing the importance of taking advantage of labeled
5

One should note that among the three worse classifiers, KNN, Naive and KLogistic,
the latter obtained better performance than the former two, this is due to the fact that
KLogistic is closer, in nature, to an SVM.

28

1

0.6

0.4

Catech−tiny

Data set

Caltech−101

Cricket

Travel

Poetry

Poetas
Poetas

Business

CCA

Football

CADE12

TDT−2

Web−KB

20−Newsgroup

Reuters−10

0

Reuters−8

0.2

CCA

KNN
Naive
SVM
KLogistic
Neural
Classic4

f1 − measure

0.8

1

0.6

0.4

Catech−tiny

Cricket

Travel

Poetry

Caltech−101

Data set

Business

Football

Web−KB

TDT−2

20−Newsgroup

Reuters−10

0

Reuters−8

0.2

CADE12

KNN
Naive
SVM
KLogistic
Neural
Classic4

f1 − measure

0.8

Figure 8: Classification performance of selected TWSs across different classifiers, f1 measure is reported. The plot at the top is a TWS learned for Caltech-tiny, while the bottom
plot shows the performance for a TWS learned for Caltech-101.

documents.
• TWSs offer acceptable inter-data set generalization performance, in
particular, TWSs learned for TC generalize pretty well across data
sets.
• We showed evidence that TWSs learned for a modality (e.g., text /
images) can be very competitive when evaluated on other modality.
• TWSs are somewhat robust to the classifier choice. It is preferable
29

to use the classifier used to estimate the fitness function, although
classifiers of similar nature perform similarly.
6. Conclusions
We have described a novel approach to term-weighting scheme (TWS)
learning in text classification (TC). TWSs specify the way in which documents are represented under a vector space model. We proposed a genetic
programming solution in which standard TWSs, term-document, and term
relevance weights are combined to give rise to effective TWSs. We reported
experimental results in 16 well-known data sets comprising thematic TC,
authorship attribution and image classification tasks. The performance of
the proposed method is evaluated under different scenarios. Experimental
results show that the proposed approach learns very effective TWSs that outperform standard TWSs. The main findings of this work can be summarized
as follows:
• TWSs learned with the proposed approach outperformed significantly
to standard TWSs and those proposed in related work.
• Defining the appropriate TWS is crucial for image classification tasks,
an ignored issue in the field of computer vision.
• In authorship attribution, supervised TWSs are beneficial, in comparison with standard TWSs.
• The performance of learned TWSs do not degrades when varying the
vocabulary size for thematic TC and IC. For authorship attribution
a near-optimal vocabulary size should be selected before applying our
method.
• TWSs learned for a particular data set or modality can be applied
to other data sets or modalities without degrading the classification
performance. This generalization capability is mainly present in TWSs
learned for thematic TC and IC.
• Learned TWSs are easy to analyze/interpret and do not seem to overfit
the training data.

30

Future work directions include studying the suitability of the proposed
approach to learn weighting schemes for cross domain TC. Also we would
like to perform an in deep study on the usefulness of the proposed GP for
computer vision tasks relying in the Bag-of-Visual-Words formulation.
References
Agarwal, B., Mittal, N., 2014. Text classification using machine learning
methods-a survey. In: Proceedings of the Second International Conference
on Soft Computing for Problem Solving (SocProS 2012). Vol. 236 of Advances in Intelligent Systems and Computing. pp. 701–709.
Aggarwal, C. C., 2012. Mining Text Data. Springer, Ch. A Survey of Text
Classification Algorithms, pp. 163–222.
Aggarwal, C. C., Zhai, C. (Eds.), 2012. Mining Text Data. Springer.
Altyncay, H., Erenel, Z., 2010. Analytical evaluation of term weighting
schemes for text categorization. Pattern Recognition Letters 31, 1310–
1323.
Baeza-Yates, R., Ribeiro-Neto, B., 1999. Modern Information Retrieval.
Addison-Wesley.
Chang, K. W., Roth, D., 2011. Selective block minimization for faster convergence of limited memory large-scale linear models. In: ACM SIGKDD
Conference on Knowledge Discovery and Data Mining.
Csurka, G., Dance, C. R., Fan, L., Willamowski, J., Bra, C., 2004. Visual
categorization with bags of keypoints. In: International workshop on statistical learning in computer vision.
Cummins, R., O’Riordan, C., 2005. Evolving general term-weighting schemes
for information retrieval: Tests on larger collections. Artificial Intelligence
Review 24, 277–299.
Cummins, R., O’Riordan, C., 2006. Evolving local and global weighting
schemes in information retrieval. Information Retrieval 9, 311–330.
Cummins, R., O’Riordan, C., 2007. Evolved term-weighting schemes in information retrieval: An analysis of the solution space. Artificial Intelligence.
31

Debole, F., Sebastiani, F., 2003. Supervised term weighting for automated
text categorization. In: Proceedings of the 2003 ACM Symposium on Applied Computing. SAC ’03. ACM, New York, NY, USA, pp. 784–788.
URL http://doi.acm.org/10.1145/952532.952688
Djuric, N., Lan, L., Vucetic, S., Wang, Z., 2013. Budgetedsvm: A toolbox
for scalable svm approximations. Journal of Machine Learning Research
14, 3813–3817.
Eiben, A. E., Smith, J. E., 2010. Introduction to Evolutionary Computing.
Natural Computing. Springer.
Escalante, H. J., Montes, M., Villasenor, L., 2009. Particle swarm model selection for authorship verification. In: Proceedings of the 14th Iberoamerican Congress on Pattern Recognition. Vol. 5856 of LNCS. Springer, pp.
563–570.
Escalante, H. J., Solorio, T., y Gomez, M. M., 2011. Local histograms of
character n-grams for authorship attribution. In: Proceedings of the 49th
Annual Meeting of the Association for Computational Linguistics. pp. 288–
298.
Fan, W., Fox, E. A., Pathak, P., Wu, H., 2004a. The effects of fitness functions on genetic programming based ranking discovery for web search.
Journal of the american Society for Information Science and Technology
55 (7), 628–636.
Fan, W., Gordon, M. D., Pathak, P., 2004b. A generic ranking function
discovery framework by genetic programming for information retrieval. Information Processing and Management.
Fei-Fei, L., Fergus, R., Perona, P., 2004. Learning generative visual models
from few training examples: an incremental bayesian approach tested on
101 object categories. In: IEEE. CVPR 2004, Workshop on GenerativeModel Based Vision.
Feldman, R., Sanger, J., 2006. The Text Mining Handbook Advanced Approaches in Analyzing Unstructured Data. ABS Ventures.
Forman, G., 2003. An extensive empirical study of feature selection metrics
for text classification. J. of Mach. Learn. Res. 3, 1289–1305.
32

Joachims, T., 2008. Text categorization with support vector machines:
Learning with many relevant features. In: Proceedings of ECML-98. Vol.
1398 of LNCS. Springer, pp. 137–142.
Kiddon, C., Brun, Y., 2011. That’s what she said: Double entendre identification. In: Proceedings of the 49th Annual Meeting of the Association for
Computational Linguistics. pp. 89–94.
Koppel, M., Argamon, S., Shimoni, A. R., 2002. Automatically categorizing
written texts by author gender. Literary and Linguistic Computing 17 (4),
401–412.
Koppel, M., Schler, J., 2004. Authorship verification as a one-class classification problem. In: Proceedings of the 21st International Conference on
Machine Learning. p. 62.
Lan, M., Tan, C. L., Su, J., Lu, Y., 2009. Supervised and traditional term
weighting methods for automatic text categorization. Trans. PAMI 31 (4),
721–735.
Langdon, W. B., Poli, R., 2001. Foundations of Genetic Programming.
Springer.
Luyckx, K., Daelemans, W., 2010. The effect of author set size and data size
in authorship attribution. Literary and Linguistic Computing, 1–21.
Mladenic, D., Grobelnik, M., 1999. Feature selection for unbalanced class
distribution and nave bayes. In: Proceedings of the 16th Conference on
Machine Learning. pp. 258–267.
Oren, N., 2002. Re-examining tf.idf based information retrieval with genetic
programming. In: SAICSIT.
Pang, B., Lee, L., Vaithyanathan, S., 2002. Thumbs up, sentiment classification using machine learning techniques. In: Proceedings of the Conference
on Empirical Methods in Natural Language Processing (EMNLP). pp. 79–
86.
Reyes, A., Rosso, P., 2014. On the difficulty of automatically detecting irony:
Beyond a simple case of negation. Knowledge and Information Systems
40 (3), 595–614.
33

Salton, G., Buckley, C., 1988. Term-weighting approaches in automatic text
retrieval. Information Processing and Management, 513–523.
Sebastiani, F., 2008. Machine learning in automated text categorization.
ACM Computer Surveys 34 (1), 1–47.
Silva, S., Almeida, J., 2003. Gplab-a genetic programming toolbox for matlab. In: Proceedings of the Nordic MATLAB conference. pp. 273–278.
Sivic, J., Zisserman, A., 2003. Video google: A text retrieval approach to object matching in videos. In: International Conference on Computer Vision.
Vol. 2. pp. 1470–1477.
S.Manchala, Prasad, V. K., Janaki, V., 2014. GMM based language identification system using robust features. International Journal of Speech
Technology (2014) 17:99105 17, 99–105.
Stamatatos, E., 2009. A survey of modern authorship attribution methods.
Journal of the American Society for Information Science and Technology
60 (3), 538–556.
Trotman, A., 2005. Learning to rank. Information Retrieval 8, 359–381.
Turney, P., Pantel, P., 2010. From frequency to meaning: Vector space models
of semantics. Journal of Artificial Intelligence Research 37, 141–188.
Vedaldi, A., Fulkerson, B., 2008. VLFeat: An open and portable library of
computer vision algorithms.
Wanga, J., Liub, P., Shea, M. F., Nahavandia, S., Kouzanid, A., 2013. Bag-ofwords representation for biomedical time series classification. Biomedical
Signal Processing and Control 8 (6), 634–644.
Yang, Y., Pedersen, J. O., 1997. A comparative study on feature selection
in text categorization. In: Proceedins of the 14th International Conference
on Machine Learning. pp. 412–420.
Zhang, J., Marszablek, M., Lazebnik, S., Schmid, C., 2007. Local features and
kernels for classification of texture and object categories: A comprehensive
study. International Journal of Computer Vision 73 (2), 213–238.

34

Zhang, K., Lan, L., Wang, Z., Moerchen, F., 2012. Scaling up kernel svm on
limited resources: A low-rank linearization approach. In: Proceedings of
the 15th International Conference on Artificial Intelligence and Statistics
(AISTATS).

35

