A new family of online algorithms for category ranking.
We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stems from recent advances in online learning algorithms. The algorithms we present are simple to implement and are time and memory efficient. We evaluate the algorithms on the Reuters-21578 corpus and the new corpus released by Reuters in 2000. On both corpora the algorithms we present outperform adaptations to topic-ranking of Rocchio's algorithm and the Perceptron algorithm. We also outline the formal analysis of the algorithm in the mistake bound model. To our knowledge, this work is the first to report performance results with the entire new Reuters corpus.
INTRODUCTION
The focus of this paper is the problem of topic ranking for
text documents. We use the Reuters corpus (release 2000)
as our running example. In this corpus there are about a
hundred dierent topics. Each document in the corpus is
tagged with a set of topics that are relevant to its content.
For instance, a document from late August 1996, discusses
a bill by Bill Clinton to increase the minimum wage by a
whole 90 cents. This document is associated with 9 topics;
four of them are labour, economics, unemployment, and
retail sales. This example shows that there is a semantic
overlap between the topics. Given a feed of documents,
such as the Reuters newswire, the task of topic ranking is
concerned with ordering the topics according to their relevance
for each document independently. The framework
that we use in this paper is that of supervised learning. In
this framework we receive a training set of documents each
of which is provided with its set of relevant topics. Given the
labeled corpus, the goal is to learn a topic-ranking function
that gets a document and outputs a ranking of the topics.
In the machine learning community this setting is often
referred to as a multilabel classication problem. The motivation
of most, if not all, of the machine learning algorithms
for this problem stem from a decision theoretic view.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SIGIR'02, August 11-15, 2002, Tampere, Finland.
Namely, the output of the algorithms is a predicted set of
relevant topics and the quality of the predictions is measures
by how successful we are in identifying the set of relevant
topics. In this paper we combine techniques from statistical
learning theory with the more natural goals of information
retrieval tasks. We do so by adopting and generalizing techniques
from online prediction algorithms to the particular
task of topic ranking. Our starting point is the Perceptron
algorithm [8]. Despite (or because of) its age and simplicity
the Perceptron algorithm and its variants have proved to
be surprisingly eective in a broad range of applications in
machine learning and information retrieval (see for instance
[3, 6] and the references therein). The original Perceptron
algorithm has been designed for binary classication prob-
lems. Our family of algorithms borrows the core motivation
of the Perceptron algorithm and largely generalizes it to the
more complex problem of topic ranking. Since the family of
algorithms uses Multiclass Multilabel feedback we refer to
the various variants as the MMP algorithm.
A few learning algorithms for multi-labeled data have
been devised in the machine learning community. Two notable
examples are a multilabel version of AdaBoost called
AdaBoost.MH [10] and a multilabel generalization of Vap-
nik's Support Vector Machines by Elissee and Weston [2].
These two multilabel algorithms take the same general approach
by reducing a multilabel problem into multiple binary
problems by comparing all pairs of labels. Our starting
point is similar as we use an implicit reduction into pairs.
Yet, using a simple pre-computation, MMP is much simpler
to implement and use than both SVM and AdaBoost.MH.
Note, however, that in contrast to AdaBoost.MH and SVM
which were designed for batch settings, in which all the examples
are given in advance, MMP , like the Perceptron, is
used in online settings in which the examples are presented
one at a time.
Our experiments with the two corpora by Reuters suggest
that MMP can oer a viable alternative to existing
algorithms and can be used for processing massive datasets.
2. PROBLEM SETTING
As discussed above, the text processing task in this paper
is concerned with is category or topic ranking. In this problem
we are given access to a stream of documents. Each
document is associated with zero or more categories from
a predened set of topics. We denote the set of possible
categories by Y and the number of dierent topics by k,
In the new distribution of the Reuters corpus
(which we refer to as Reuters-2000) there are 102 dierent
topics while Reuters-21578 consists of 91 dierent topics.
Since there is semantic overlap between the topics a document
is typically associated with more than one topic. More
formally, a document is labeled with a set y  Y of relevant
topics. In the Reuters-2000 corpus the average size of y is
3:2 while in Reuters-21578 the average size is 1:24. We say
that a topic r (also referred to as a class or category) is relevant
for a given document if r is in the set of relevant topics,
y.
In the machine learning community this setting is also often
referred to as a multilabel classication problem. There
are numerous dierent information ltering and routing tasks
that are of practical use for multilabel problems. The focus
of this paper is the design, analysis, and implementation
of category-ranking algorithms. That is, given a document,
the algorithms we consider return a list of topics ranked according
to their relevance. However, as discussed above, the
feedback for each document is the set y and thus the topics
for each document in the training corpus are not ranked but
rather marked as relevant or non-relevant.
Each document is represented using the vector space model
[9] as vectors in R n . We denote a document by its vector
representation
. All the topic-ranking algorithms we
discuss in this paper use the same mechanism: each algorithm
maintains a set of k prototypes,
wk . Analogous
to the representation of documents, each prototype is
a vector,
. The specic vector-space representation
we used is based on the pivoted length normalization of
Singhal et. al. [12]. Its description is deferred to the Sec. 4.2.
The focus of the paper is a new family of algorithms that
builds the prototype from examples, i.e., a corpus S of m
documents each of which is assigned a set of relevant topics,
.
The set of prototypes induce a ranking on the topics according
to their similarity with the vector representation
of the document. That is, given a document  x the inner-product

wk   x induce an ordering of the
relevance level for each topic. We say that topic r is ranked
higher than topic s if
x >
ws
x. Given a feedback,
i.e. the set of relevant topics y of a document  x, we say
that the ranking induced by the prototypes is perfect if all
the relevant topics are ranked higher than the non-relevant
topics. In a perfect ranking any pair of topics r 2 y and
the scores induced by
wr is higher than
that the one induced by
ws ,
ws   x. We can measure
the quality of a perfect topic-ranking by the size of the gap
between the lowest score among the relevant topics to the
highest score among the non-relevant topics,
min r2y
f
f
ws
Adopting the terminology used in learning theory we refer
to the above quantity as the margin of a document  x with respect
to a set of relevant topics y and prototypes
wk .
Clearly, a perfect ranking of a document implies that its
margin is positive. The margin can also be computed when
the prototypes do not induce a perfect ranking. In this case
the margin is negative. An illustration of the margin is given
in Fig. 1. The illustration show the margin in case of a perfect
ranking (left) and a non-perfect one (right). In both
cases there are 9 dierent topics. The relevant topics are
marked with circles and the non-relevant with squares. The
value of the margin is the length of arrow where a positive
values is denoted by an arrow pointing down and a negative

Figure

1: Illustration of the notion of the margin for
a perfect ranking (left) and a non-perfect ranking.
margin by an arrow pointing up. The notion of margin is
rather implicit in the algorithms we discuss in the paper.
However, it plays an important role in the formal analysis
of the algorithms.
3. CATEGORY-RANKING ALGORITHMS
MMP, being a descendant of the Perceptron algorithm,
is an online algorithm: it gets an example, outputs a rank-
ing, and updates the hypothesis it maintains { the set of
prototypes
wk . The update of the prototypes takes
place only if the predicted ranking is not prefect. Online algorithms
become especially handy when the training corpus
is very large since they require minimal amounts of mem-
ory. In the case of batch training (i.e. when the training
corpus is provided in advance and not example by example)
we need to augment the online algorithm with a wrapper.
Several approaches have been proposed for adapting online
algorithms for batch settings. A detailed discussion is given
in [3]. The approach we take in this paper is the simplest
to implement. We run the algorithm in an online fashion on
the provided training corpus and use the nal set of topic
prototypes, obtained after a single pass through the data,
as the topic-ranking hypothesis. We leave more sophisticated
schemes to future research. In the description below,
we omit the index of the document and its set of relevant
topics and denote them as
x and y, respectively.
Given a document
x we dene the error-set of the induced
ranking
wk with respect to the relevance (of topics)
as the set of categories that are inconsistent with the predicted
ranking. Formally, the error-set is dened as
x <
ws   xg :
Clearly, the predicted ranking is not perfect if and only if
E is not empty. The size of E can be as large as (
natural question that arises is what type of loss one should
try to minimize whenever E is not empty. We now describe
three dierent losses that yield a simple and e-cient algo-
rithms. These loss functions stem from learning theoretic
insights and also exhibit good performance with respect to
the common information retrieval performance measures. A
nice property of the three losses is that they can be encapsulated
into a single update scheme of the prototypes.
The rst loss is the indicator function, that is, equals 1 if
another way, this loss simply
counts the number of times the topic-ranking was not per-
fect. The second loss is the size of E. Therefore, examples
which were ranked perfectly suer a zero loss while the rest
Initialize: Set
Loop: For
Obtain a new document
Rank the topics according to:
wk   x i
Obtain the set of relevant topics y i
If the ranking of  x i is not perfect do:
1. For r 2 y i set:
ws   x i
2. For r 62 y i set:
ws   x i
3. Set normalization factor:
r nr ( loss1 )
4. Update for r 2 y
c
5. Update for r 62 y
c
Return:
wk

Figure

2: The topic-ranking algorithm.
of the examples suer losses in proportion to how poorly
the predicted rankings perform in terms of number of disordered
topics. The third loss is a normalized version of the
second loss, namely, it is jEj=(jY yjjyj). Since maximal
size of the error set is jY yjjyj, the third loss is bounded
from above by one. On each document with rank prediction
error MMP moves the prototypes whose indices constitute
the error-set. The prototypes that correspond the set of
relevant topics are moved toward
x and those which correspond
to non-relevant topics are moved away from
x. The
motivation of this prototype-update stems from the Perceptron
algorithm: it is straightforward to verify that this form
of update will increase the value of inner-products between
x and each of the prototypes in the subset of relevant categories
and similarly decrease the rest of the inner-products.
Put another way, this update of the prototypes is geared
towards increasing the ranking-margin associated with the
example and thus reducing the ranking losses above. The
amount by which we move each prototype depends on its
ranking and the type of loss we employ. We dene nr to
be the number topics wrongly ranked with respect to topic
r. If r is the index of a relevant topic r 2 y, then nr is the
number of non-relevant topics ranked above r. Analogously,
if r is the index of a non-relevant topic nr is the number
of relevant topics below r. Each prototype
wr is moved in
the direction of
x and in proportion to nr . Once the values
are computed, we normalize each on of them by
a scaling factor, denoted c. The value of c depends on the
version of the loss that is used. This scaling factor c ensures
that the sum over nr equals the loss we are trying to make
small, that is,
for the rst loss,
for the second loss, and
for the
third loss. To summarize, if the topic ranking is not perfect
each of prototype
wr corresponding to a wrongly ranked
relevant topic is changed to
(nr=c)x and an analogous
modication is made to the wrongly ranked prototypes from
the set of non-relevant topics. The pseudo code describing
the algorithm is given in Fig. 2.
To analyze the performance of the algorithm we again
need to use the notion of margin. Generalizing the notion
of margin from one document to an entire corpus, we dene
the margin, denoted
, of a set of prototypes
wk on a
corpus S as the minimal margin attained on the documents
in S,
min r2y
f
f
ws   xg
For the purpose of the analysis we assume that the total
norm of the prototypes is 1 (
1). This assumption
can be satised by global normalization of the prototypes
that does not change the induced ranking. We are now
ready to state the main theorem which shows that MMP
make a bounded number of mistakes compared to a set of
prototypes that is constructed with hindsight (after obtaining
all the examples) and achieves a perfect ranking on the
corpus.
Theorem 1. [Mistake bound] Let
be an input sequence for MMP where
kg. Denote by Assume that there exists
a set of prototypes
k of unit norm that achieves
a perfect ranking on the entire sequence with margin
S .
Then, MMP obtains the following bounds,
2:
Due to the space restrictions the proof is omitted from
the manuscript.
4. EXPERIMENTS
In this section we describe the experiments we performed
that compare the three variants of MMP with a simple extension
of the Perceptron algorithms and Rocchio's algorithm
We start with a description of the datasets we
used in our experiments.
4.1 Datasets
We evaluated the algorithms on two text corpora. Both
corpora were provided by Reuters.
Reuters-21578: The documents in this corpus were collected
from the Reuters newswire during 1987. The data
set is available from http://www.daviddlewis.com/resources.
Number of
Fraction
of
Data
set
Number of
Fraction
of
Data
set

Figure

3: The distribution of the number of relevant
topics in Reuters-21578 (left) and Reuters-2000.
We used the ModApte version of the corpus and pre-processed
the documents as follows. All words were converted to lower-
case, digits were mapped to a single token designating it is
a digit, and non alpha-numeric characters were discarded.
We also used a stop-list to remove very frequent words. The
number of dierent words left after pre-processing is 27,747.
After the pre-processing the corpus contains 10,789 documents
each of which is associated with one or more topics.
The number of dierent topics in the ModApte version of
Reuters-21578 is 91. Since this corpus is of relatively small
size, we used 5-fold cross validation in our experiments and
did not use the original partition into training and test sets.
While each document in the Reuters-21578 corpus can be
multilabeled, in practice the number of such documents is
relatively small. Over 80% of the documents are associated
with a single topic. On the left hand side of Fig. 3 we show
the distribution of the number of relevant topics. The average
number of relevant topics per document is 1:24.
Reuters-2000: This corpus contains 809; 383 documents
collected from the Reuters newswire in a year period (1996-
08-20 to 1997-08-19). Since this corpus is large we used the
rst two thirds of the corpus for training and the remaining
third for evaluation. The training set consisted of all
documents that were posted from 1996-08-20 through 1997-
04-10, resulting in 521; 439 training documents. The size of
the corpus which was used for evaluation is 287; 944. We
pre-processed as follows. We converted all upper-case characters
to lower-case, replaced all non alpha-numeric characters
with white-spaces, and discarded all the words that
appeared only once in the training set. The number of dier-
ent words that remained after this pre-processing is 225; 329.
Each document in the collection is associated with zero or
more topics. There are 103 dierent topics in the entire cor-
pus, however, only 102 of them appear in the training set.
The remaining category marked GMIL, for millennium is-
sues, tags only 5 documents in the test set. We therefore
discarded this category. Unlike the Reuters-21578 corpus,
each document in the corpus is tagged by multiple topics:
about 70% of the documents are associated with at least
three dierent topics. The average number of topics associated
with each document is 3:20. The distribution of the
number of relevant topics per document appears on the right
hand-side of Fig. 3.
4.2 Document representation
All the algorithms we evaluated use the same document
representation. We implemented the pivoted length normalization
of Singhal et. al. [12] as our term-weighting al-
gorithm. This algorithm is considered to be one of the most
eective algorithms for document ranking and retrieval. We
now brie
y outline the pivoted length normalization. Let
d l
i denote the number of times a word (or term) indexed l
appears in the document indexed i. Let m i denote the number
of unique words appear in in the document indexed i by
l be the number of documents
in which the term indexed l appears. As before, the total
number of documents in the corpus is denoted by m. Using
these denitions the idf weight of a word indexed l is
log(m=u l ). The average frequency of the terms appearing
in document t is,
avg[d l
l d l
and the average frequency of number of unique terms in the
documents is,
Using these denitions the tf weight of a word indexed l
appears in the document indexed t is,
Here slope is a parameter among 0 and 1. We set
0:3 which leads to the best performance at the experiments
reported in [12].
4.3 Algorithms for comparison
In addition to the three variants of MMP we also implemented
two more algorithms: Rocchio's algorithm [7] and
the Perceptron algorithm. As with MMP these algorithms
use the same pivoted length normalization as their vector
space representation and employ the same form of category-
ranking by using a set of prototypes
wk .
Rocchio: We implemented an adaptation of Rocchio's
method as adapted by Ittner et .al [5] to text categoriza-
tion. In this variant of Rocchio the set of prototypes vectors
wk are set as follows,
r
i2Rr
x l
r
x l
where Rr is the set of documents which contain the topic
r as one of their relevant topics and R c r is its complement,
i.e., all the documents for which r is not one of their relevant
topics. Following the parameterization in [5], we set
and
4. Last, as suggested by Amit Singhal in a private
communication, we normalize all of the prototypes to a unit
norm.
Perceptron: We also implemented the Perceptron algo-
rithm. Since the Perceptron algorithm is designed for binary
classication problems, we decomposed the multilabel problem
into multiple binary classication problems. For each
topic r, the set of positive examples constitute the docu-
ments' indices from Rr , and R c r is the set of negative exam-
ples. We then ran the Perceptron algorithm on each of the
binary problems separately and independently. We therefore
obtained again a set of prototypes
wk each of
which is an output of the corresponding output of Perceptron
algorithm.
Round Number.
Averaged
Cumulative
Loss 1
Perceptron
MMP l.1
MMP l.2
MMP l.3
Averaged
Cumulative
Loss 2
Perceptron
MMP l.1
MMP l.2
MMP l.3
Round Number.
Averaged
Cumulative
Loss 3
Perceptron
MMP l.1
MMP l.2
MMP l.3

Figure

4: The round-averaged performance measures as a function of the number of training documents that
were processed for Reuters-21578 : loss1 (left), loss2 (middle) and loss3 (right).
Averaged
Cumulative
Loss 1
Perceptron
MMP l.1
MMP l.2
MMP l.3
Averaged
Cumulative
LossPerceptron
MMP l.1
MMP l.2
MMP l.3
Round Number.
Averaged
Cumulative
LossPerceptron
MMP l.1
MMP l.2
MMP l.3

Figure

5: The round-averaged performance measures as a function of the number of training documents that
were processed for Reuters-2000 : loss1 (left), loss2 (middle) and loss3 (right). A log-scale was used for the
x-axis.
4.4 Feature Selection
For both datasets the number of unique terms after the
pre-processing stage described above was still large: 27; 747
words in the Reuters-21578 and 225; 339 words in Reuters-
2000. Since we used cross-validation for Reuters-21578 the
actual number of unique terms was slightly lower, 25; 061
on the average. Yet, it was still relatively large and therefore
employed feature selection for both corpora. We used
weights of the prototypes generated by the adaptation of
Rocchio's algorithm described above as our mean for feature
selection. For each topic we sorted the terms according
to their weights assigned by Rocchio. We then took for each
topic the maximum between a hundred terms and the top
portion of 2:5% from the sorted lists. This ensures that for
each topic we have at least 100 terms. The combined set
of selected terms is used as the feature set for the various
algorithms and is of size 3; 468 of Reuters-21578 and 9; 325
for Reuters-2000. The average number of unique words per
document in the cross-validated training sets was reduced
from 49 to 37 for Reuters-21578 and from 137 to 121 for
Reuters-2000. After this feature selection stage we applied
all the algorithms on the same representation of documents
which are now restricted to the selected terms.
4.5 Evaluation Measures
Since the paper is concerned with both classical IR methods
and more recent statistical learning algorithms we used
two sets of performance measures to compare the eective-
ness of the algorithms. First, we evaluated each of the algorithm
with respect to the three losses employed by the
variants of MMP. The second set of performance measures
is based on measures used in evaluating document retrieval
systems. Specically, the performance measure we used in
the evaluation are: recall at r, precision at r, one-error,
coverage, average-precision, and maxF1 . We also provide
precision-recall graphs. We now give formal descriptions of
the evaluation measures used in our experiments.
For describing the evaluation measures used in the experiments
we need the following denition. Given a set of prototypes
and xing the example to (x; y), we dene rank(x; r)
as the ranking of the topic indexed r in list of topics sorted
according to the prototypes. Thus, the rank-value of the
top-ranked topic is 1 and of the bottom-ranked topic is k.
The performance measure for the test set is the average value
of each measure over the documents in the set.
Recall The recall value at r is the ratio between the number
of the topics from the set of relevant topics y whose rank is
at most r and the size of the relevant topics y.
Precision The precision value at r is the ratio between the
number of the topics from the set of relevant topics y whose
rank is at most r and the position r.
OneErr The one-error (abbreviated OneErr) takes the values
0 or 1. It indicated whether the top-ranked element
Algorithm loss1  100 loss2 loss3  100
Rocciho
Perceptron 15.71 4.87 3.13
MMP l. 3 19.13 0.92 0.60

Table

1: A comparison of the performance of
the various algorithms on the test-set for different
learning-theoretic performance measures on
Reuters-21578.
Algorithm OneErr  100 Coverage AvgP maxF1
Rocciho 14.48 1.29 0.90 0.85
Perceptron 9.59 4.27 0.91 0.89
MMP l. 3 14.51 0.96 0.90 0.84

Table

2: A comparison of the performance of the
various algorithms on the test-set for dierent retrieval
performance measures on Reuters-21578.
belongs to the set of relevant topics y (zero error) or not
(error of 1),
Therefore, the average OneErr over a test corpus re
ects
the fraction of documents for which the top-ranked topic
was not from the list of relevant topics.
Coverage The coverage value re
ects how far we need to
go down the ranked-list of topics in order to retrieve all the
relevant topics,
For convenience this denition implies that for documents
with a single relevant topic a perfect ranking achieves a coverage
of zero.
AvgP The average precision (abbreviated AvgP), as the
name implies, is the average precision taken at the positions
of the relevant topics,
r2y
The average precision is perhaps the most common performance
measure in document retrieval.
maxF1 The F1 value at r is dened as,
The maxF1 is the maximal F1 value that can be obtained.
For further information on the F1 performance measure see [13].
We would like to note that the there are natural relations
between the learning theoretic losses, loss1 loss3 , and the
retrieval-based performance measures. For instance, whenever
OneErr is 1 then also since if the top-ranked
Algorithm loss1  100 loss2 loss3  100
Rocciho 70.71 12.42 3.33
Perceptron 38.86 10.43 2.64
MMP l. 3 34.57 2.90 0.75

Table

3: A comparison of the performance of
the various algorithms on the test-set for different
learning-theoretic performance measures on
Reuters-2000.
Algorithm OneErr  100 Coverage AvgP maxF1
Rocciho 24.42 9.89 0.73 0.63
Perceptron 6.04 9.45 0.87 0.86
MMP l. 3 6.49 3.98 0.91 0.87

Table

4: A comparison of the performance of the
various algorithms on the test-set for dierent retrieval
performance measures on Reuters-2000.
topic is not one of the relevant topics then clearly the ranking
is not perfect and thus OneErr  loss1 . Also, if
then the Coverage and loss2 coincide.
4.6 Results
Let us rst discuss the performance of the online algorithms
(the variants of MMP and Perceptron) on the training
sets. In Fig. 4 and Fig. 5 we show the performance
with respect to loss1 , loss2 and loss3 for Reuters-21578 and
Reuters-2000 respectively. For each round (new document)
we compute the cumulative loss of of the algorithms divided
by the number of documents processes, i.e., the round number
loss
(i))=M . Note that we used log-scale
for the x-axis. As expected, we can see from the gures
that each version of MMP performs well with respect to the
loss measure it was trained on. In addition, the Perceptron
performs well with respect to loss1 , especially on Reuters-
21578. The relatively good performance of the Perceptron
with respect to loss1 might be attributed to the fact that the
Reuters-21578 corpus is practically single-labeled and thus
loss1 and the classication error used by the Perceptron are
practically synonymous. As we discuss in the sequel, the
performance after most of the documents have been processed
also is highly correlated with the performance of the
algorithms on unseen test data. This type of behavior indeed
agrees with the formal analysis of online algorithms [4].
The performance of the algorithms on the test sets is summarized
in four tables. A summary of the performances
with respect to the learning-theoretic and information retrieval
measures on Reuters-21578 are given in Table 1 and

Table

2, respectively. An analogous summary for Reuters-
2000 is given in Table 3 and Table 4. In addition we also
provide in Fig. 6 precision-recall graphs for both corpora.
The performance of MMP and the Perceptron algorithm
with respect to the learning-theoretic losses is consistent
with their behavior on the test data: each variant of MMP
performs well with respect to the loss it employs in training.
Moving on to retrieval performance measures, we see that
Recall
Precision
Rocciho
Perceptron
MMP l.1
MMP l.2
MMP l.3
Precision
Rocciho
Perceptron
MMP l.1
MMP l.2
MMP l.3

Figure

versus recall (x-axis) graphs for the various algorithms on Reuters-21578 (left)
and Reuters-2000 (right).
with respect to all performance measures, with the exception
of Coverage, the best performing topic-ranking algorithm is
MMP with loss1 . For coverage MMP trained with either
loss2 or loss3 achieve the best performance. We also see
strong correlations between loss1 and OneErr and between
loss2 and Coverage. One possible explanation to the improved
performance of loss1 compared to loss2 and loss3 is
that it gives each document the same weight in the update
while the other losses prefer documents with large number
of relevant topics. We plan to investigate this conjecture,
both theoretically and empirically, in future work.
The Perceptron algorithm performs surprisingly well on
both datasets with respect to most of the performance mea-
sures. The main deciency of the algorithms is its relatively
poor performance in terms of Coverage. It achieves
the worst Coverage value in all cases. This behavior can
also be observed in the precision-recall graphs. While the
precision the Perceptron algorithm for low recall values is
competitive with all the variants of MMP and even better
than the variants that employ loss2 and loss3 on Reuters-
21578, as long as recall is below 0:9. Alas, as the recall
increases the precision of the Perceptron algorithm drops
sharply and for high recall values it exhibits the worst pre-
cision. One possible explanation for this behavior is that
the Perceptron is a tailored for classication and thus the
implicit classication loss (the \hinge" loss) it employs is
insensitive to the induced ranking.
Despite our attempts to implement a state-of-the-art version
of Rocchio that takes into account phenomena like the
length of the documents, Rocchio's performance was the
worst. This is especially surprising since in a head-to-head
comparison of Rocchio with recent variants of AdaBoost [11]
the results of the two algorithms were practically indistin-
guishable, despite the fact that it took two orders of magnitude
more to train the latter. Amit Singhal from Google
oered one possible explanation for this relatively poor per-
formance. Rocchio was originally designed for document re-
trieval. Furthermore, the recent improvements that employ
length normalization were tuned on TREC's document retrieval
tasks. Despite its similarity in nature to document
ranking, the topic ranking problem seems to exhibit dierent
statistical characteristics and might require new adaptations
for topic ranking problems.
5.


In this paper we presented a new family of algorithms
called MMP for topic-ranking which are simple to imple-
ment. The algorithmic approach suggested in this paper attempts
to combine the formal properties of statistical learning
techniques with the eectiveness of practical information
retrieval algorithms. The online framework that we used
to derive MMP makes the algorithm practical for massive
datasets such as the new release of Reuters. We believe that
our experiments show that MMP indeed makes a non-trivial
step toward provably correct and practically eective methods
for IR.
There are quite a few possible extensions and modica-
tions to MMP that might further improve its eectiveness.
One possible extension we are currently exploring a better
fusion of IR-motivated losses such as the average precision
into the core of the algorithm. We have preliminary results
that indicate that such an improvement is plausible. A few
more straightforward, yet powerful, extensions were not discussed
in this paper. In particular, MMP can be incorporated
with kernel-techniques [14, 1]. Other, more robust,
methods for converting MMP to a batch algorithm (see for
instance [3] and the references therein) are also possible and
will be evaluated in future work.

Acknowledgments

Thanks to Amit Singhal for clarications and suggestions on
pivoted-length normalization. Thanks also to Noam Slonim
for discussions, to Ofer Dekel and Benjy Weinberger for their
help in pre-processing the corpora, and to Leo Kontorovich
for comments on the manuscript. We also would like to
acknowledge the nancial support of EU project KerMIT
No. IST-2000-25341 and the KerMIT group members for
useful discussions.
6.



--R

An Introduction to Support Vector Machines.

Large margin classi
On weak learning.
Text categorization of low quality images.
Feature selection
Relevance feedback information retrieval.
The perceptron: A probabilistic model for information storage and organization in the brain.
Developments in automatic text retrieval.
Improved boosting algorithms using con
Boosting and Rocchio applied to text
Pivoted document length normalization.
Information Retrieval.
Statistical Learning Theory.
--TR
On weak learning
Pivoted document length normalization
Feature selection, perception learning, and a usability case study for text categorization
Large margin classification using the perceptron algorithm
Boosting and Rocchio applied to text filtering
Improved Boosting Algorithms Using Confidence-rated Predictions
An introduction to support Vector Machines
Information Retrieval

--CTR
Ryan McDonald , Koby Crammer , Fernando Pereira, Flexible text segmentation with structured multilabel classification, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.987-994, October 06-08, 2005, Vancouver, British Columbia, Canada
Nadia Ghamrawi , Andrew McCallum, Collective multi-label classification, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Shenghuo Zhu , Xiang Ji , Wei Xu , Yihong Gong, Multi-labelled classification using maximum entropy method, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Vaughan R. Shanks , Hugh E. Williams , Adam Cannane, Indexing for fast categorisation, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.119-127, February 01, 2003, Adelaide, Australia
Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
Fernando Ruiz-Rico , Jose Luis Vicedo , Mara-Consuelo Rubio-Snchez, NEWPAR: an automatic feature selection and weighting schema for category ranking, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands
Franca Debole , Fabrizio Sebastiani, An analysis of the relative hardness of Reuters-21578 subsets: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.584-596, April 2005
Efficient Learning of Label Ranking by Soft Projections onto Polyhedra, The Journal of Machine Learning Research, 7, p.1567-1599, 12/1/2006
online learning;category ranking;perceptrons