Some Formal Analysis of Rocchio''s Similarity-Based Relevance Feedback Algorithm.
Rocchio's similarity-based Relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In spite of its popularity in various applications there is little rigorous analysis of its learning complexity in literature. In this paper we show that in the binary vector space model, if the initial query vector is 0, then for any of the four typical similarities (inner product, dice coefficient, cosine coefficient, and Jaccard coefficient), Rocchio's similarity-based relevance feedback algorithm makes at least i>n mistakes when used to search for a collection of documents represented by a monotone disjunction of at most i>k relevant features (or terms) over the i>n-dimensional binary vector space &lcub;0, 1&rcub;i>n. When an arbitrary initial query vector in &lcub;0, 1&rcub;i>n is used, it makes at least (i>n mistakes to search for the same collection of documents. The linear lower bounds are independent of the choices of the threshold and coefficients that the algorithm may use in updating its query vector and making its classification.
Introduction
Research on relevance feedback in information retrieval has a long history
(Baeza-Yates and Ribeiro-Neto, 1999; Frakes and Baeza-Yates,
1992; Ide, 1971b; Ide, 1971a; Raghavan and Wong, 1986; J.J. Rocchio,
Salton, 1989). It is regarded as the most popular query reformation
strategy (Baeza-Yates and Ribeiro-Neto, 1999). The central idea
of relevance feedback is to improve search performance for a particular
query by modifying the query step by step, based on the user's
judgments of the relevance or irrelevance of some of the documents
retrieved. In the vector space model (Salton, 1989; Salton et al., 1975),
The extended abstract of this paper was published in Proceedings of the Eleventh
International Symposium on Algorithms and Computation (ISAAC'00), Lecture
Notes in Computer Science 1969, pages 108-119, Springer-Verlag, December, 2000.
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
Z. Chen and B. Zhu
both documents and queries are represented as vectors in a discretized
vector space. In this case, relevance feedback is essentially an adaptive
supervised learning algorithm: A query vector and a similarity are used
to classify documents as relevant and irrelevant; the user's judgments of
the relevance or irrelevance of some the classied documents are used as
examples for updating the query vector as a linear combination of the
initial query vector and the examples judged by the user. Especially,
when the inner product similarity is used, relevance feedback is just a
Perceptron-like learning algorithm (Lewis, 1991). It is known (J.J. Roc-
chio, 1971) that there is an optimal way for updating the query vector
if the sets of relevant and irrelevant documents are known. Practically
it is impossible to derive the optimal query vector, because the full sets
of the relevant and irrelevant documents are not available.
There are many dierent variants of relevance feedback in information
retrieval. However, in this paper we only study Rocchio's similarity-based
relevance feedback algorithm (J.J. Rocchio, 1971; Ide, 1971a;
Salton, 1989). In spite of its popularity in various applications, there
is little rigorous analysis of its complexity as a learning algorithm in
literature. This is the main motivation for us to investigate the learning
complexity of Rocchio's similarity-based relevance feedback algorithm.
Wong, Yao and Bollmann (Wong et al., 1988) studied the linear structure
in information retrieval. They designed a very nice gradient descent
procedure to compute the coe-cients of a linear function and analyzed
its performance. In order to update the query vector adaptively, their
gradient descent procedure must know the user preference which is in
practice the unknown target to be learned by an information retrieval
system. More discussions of their gradient descent procedure will be
given in section 5.1.
The main contribution of our work in this paper is that linear lower
bounds on classication mistakes are proved for the algorithm when
any of the four typical similarities (inner product, dice coe-cient,
cosine coe-cient, and Jaccard coe-cient) listed in (Salton, 1989) is
used. Technically, our work in this paper is enlightened by the work
in (Kivinen et al., 1997) on lower bounds of the Perceptron algorithm.
Precisely, we borrow the method developed in (Kivinen et al., 1997) for
constructing an example sequence with pairwise constant inner prod-
ucts. We extend the method to cope with other similarities besides inner
product. We also design a new method for selecting trial sequences and
prove in a uniform way our lower bounds for Rocchio's similarity-based
relevance feedback algorithm.
It should be pointed out that the lower bounds established in this
paper for Rocchio's similarity-based relevance feedback algorithm is
based on the following worst case considerations: The user acts as an
Some Formal Analysis of Rocchio's Algorithm 3
adversary to the algorithm; the algorithm is required to precisely search
for the collection of all documents relevant to the given search query;
and the algorithm is allowed to receive one document example judged
by the user as relevance or irrelevant at each step 1 . In practical applications
, in contrast to the above worst case considerations, the user in
general may not act as an adversary to the algorithm; the algorithm
is usually required to search for a short list of top ranked documents
relevant to the given search query; and at each step of the similarity-based
relevance algorithm, the user may judge a few documents as
relevance feedback to the algorithm. In other words, the appropriate situation
in real-world information retrieval applications would be a kind
of \sympathetic oracle" model, where the user is not an adversary to the
information retrieval system but a \sympathetic judge" who provides
the most useful possible information in order to help the system help
him/her to accomplish his/her work. Hence, our lower bounds proved in
this paper for Rocchio's similarity-based relevance feedback algorithm
may not aect the algorithm's eective applicability to the real-world
problems despite of their theoretical signicance. The formal analysis
of the algorithm helps us understand the nature of the algorithm well
so that we may nd new strategies to improve its eectiveness or design
new algorithms for information retrieval. Recently, we have made
some progress along this line in (Chen, 2001). We have designed two
types of multiplicative adaptive algorithms for user preference retrieval
with provable better performance: One has better performance than
Rocchio's algorithm in learning a class of linear classiers over non-binary
vector space. The other boosts the usefulness of an index term
exponentially, while the gradient descent procedure in (Wong et al.,
1988) boosts the usefulness of an index term linearly.
We refer the readers to the work of (Salton and Buckley, 1990;
Lewis, 1991) for discussions of the Perceptron-like learning nature of the
similarity-based relevance feedback algorithm. It was stated in (Lewis,
1991) that the most important future direction for research in information
retrieval is likely to be machine learning techniques which can
combine empirical learning with the use of knowledge bases.
This paper is organized as follows. In section 2, we give a formal presentation
of Rocchio's similarity-based relevance feedback algorithm.
In section 3, we prove several technical lemmas based on the techniques
developed in (Kivinen et al., 1997). In section 4, we prove linear
lower bounds for Rocchio's similarity-based relevance feedback algorithm
with any of the four typical similarities listed in (Salton, 1989).
This last restriction is not critical to the proof of the lower bounds, but it would
make the analysis easier.
4 Z. Chen and B. Zhu
In section 5 we give some discussions of our result and also show that
Rocchio's algorithm can be used to learn many other target document
classes. We conclude the paper and list several open problems in section
6.
2. Rocchio's Similarity-Based Relevance Feedback
Algorithm
Let R be the set of all real values, and let R + be the set of all non-negative
real values. Let n be a positive integer. In the binary vector
space model in information retrieval (Salton, 1989; Salton et al., 1975),
a collection of n features or terms T are used to represent
documents and queries. Each document d is represented as a vector
such that for any i, 1  i  n, the i-th component
of v d is one if the i-th feature T i appears in d or zero otherwise. Each
query q is represented by a vector v
any i, 1  i  n, the i-th component of v q 2 R is a real value used to
determine the relevance (or weight) of the i-th feature T i . Because of
the unique vector representations of documents and queries, for convenience
we simply use d and q to stand for their vector representations
v d and v q , respectively.
A similarity in general is a function m from R n  R n to R + . A
similarity m is used to determine the relevance closeness of documents
to the search query and to rank documents according to such close-
ness. In the binary vector space model of information retrieval (Salton,
1989; Salton et al., 1975; Baeza-Yates and Ribeiro-Neto, 1999), to retrieve
relevant documents for a given query vector q with respect to
a similarity m, the system searches for all the documents d, classies
those with similarity values m(q; d) higher than an explicit or implicit
threshold as relevant, and returns to the user a short list of relevant
documents with highest similarity values. This information retrieval
process is in fact determined by a linear classier, as dened later in
this section, which is composed of a query vector q, a similarity m, and
a real-valued threshold .
Unfortunately, in the real-world information retrieval applications,
usually an ideal query vector cannot be generated due to many factors
such as the limited knowledge of the users about the whole document
collection. A typical example is the real-world problem of web search.
In such a case, the user may use a few keywords to express what
documents are wanted. However, it is nontrivial for both the user and
a web search engine to precisely dene the collection of documents
wanted as a query vector composed of a set of keywords. The alternative
Some Formal Analysis of Rocchio's Algorithm 5
solution to the query formation problem is, as stated in (Salton, 1989),
to conduct searches iteratively, rst operating with a tentative query
formation (i.e., an initial query vector), and then improving formations
for subsequent searches based on evaluations of the previously retrieved
materials. This type of methods for automatically generating improved
query formation is called relevance feedback, and one particular and
well-known example is Rocchio's similarity-based relevance feedback
(J.J. Rocchio, 1971; Ide, 1971a; Salton, 1989).
Rocchio's similarity-based relevance feedback algorithm works in a
step by step adaptive renement fashion as follows. Starting at an initial
query vector q 1 , the algorithm searches for all the documents d such
that d is very close to q 1 according to the similarity m, ranks them by
m(q; d), and nally presents a short list of the top ranked documents
to the user. The user examines the returned list of documents and
judges some of the documents as relevant or irrelevant. At step t  1,
assume that the list of documents the user judged is x
the algorithm updates its query vector as q
where the coe-cients  t j
the algorithm uses the updated query vector q t and the similarity m
to search for relevant documents, ranks the documents according to
m, and presents the top ranked documents to the user. In practice, a
threshold  is explicitly (or implicitly) used to select the highly ranked
documents. Practically, the coe-cients  t j
may be xed as
(Baeza-Yates and Ribeiro-Neto, 1999; Salton, 1989). The following four
typical similarities were listed in (Salton, 1989): For any q; x 2 R n ,
dice coefficient
To make the above denitions valid for arbitrary q and x, we dene
that the similarity between two zero vectors is zero, i.e.,
It should be pointed out that the cosine similarity m 3 is nothing but
the inner product similarity m 1 when the vectors are normalized. It is
also easy to show that Jaccard similarity m 4 is a strictly monotonic
6 Z. Chen and B. Zhu
transformation of the dice similarity m 2 . This implies that both the inner
product similarity and the cosine similarity may achieve equivalent
classication for any document document with respect to the given
query vector. The subtle, but important, dierence between the two
similarities is that dierent rank values may be obtained for a document
with respect to the given query vector so that dierent \ranking gaps"
are obtained between documents. For example, when the rank gap
between documents x and y based on the inner product similarity m 1 is
0:8; the rank gap based on the similarity m 3 may
be Analogously, the above analysis applies
to the dice similarity and the Jaccard similarity. Dierent rank gaps between
pairs of documents based on dierent similarities dene dierent
user preference structures of the documents, hence dierent document
groups or clusters may be obtained. Therefore, dierent information
retrieval performances might be achieved for dierent similarities. In
other words, if the performance of an information retrieval system is not
concerned, then cosine and inner product similarities may be regarded
as two equivalent similarities, and so may Jaccard and dice similarities.
In (Wong et al., 1988) user preference was studied in terms of structures
of weak order and, in particular, linear order. In designing an adaptive
information retrieval system, the system performance is denitely not
a negligible factor. To our best knowledge, we do not know any provable
theoretical results about in
uences of the dierent similarities on
the performance of the similarity-based relevance feedback. Our linear
lower bounds proved in this paper tell us that in the worst case, the
four dierent similarities have the same aect on the performance of
Rocchio's relevance feedback. But we do not know what the result will
be in the average case.
As stated in (Baeza-Yates and Ribeiro-Neto, 1999), the main advantage
of the relevance feedback is its simplicity and good results.
The simplicity is due to the fact that the modied term weights (query
vector components) are computed directly from the set of retrieved
documents. The good results are observed experimentally and are due
to the fact that the modied query vector does re
ect a portion of the
intended query semantics.
The similarity-based relevance feedback algorithm is essentially an
adaptive supervised learning algorithm from examples (Salton and Buck-
ley, 1990; Lewis, 1991). The goal of the algorithm is to learn some
unknown classier to classify documents as relevant or irrelevant. The
learning is performed by modifying (or updating) the query vector that
serves as the hypothetical representation of the collection of all relevant
documents. The method for updating the query vector is similar to the
Some Formal Analysis of Rocchio's Algorithm 7
Perceptron algorithm. We given the necessary formal denitions in the
following.
DEFINITION 1. Let m from R n  R n to R + be a similarity. A
classier with respect to m over the n-dimensional binary vector space
f0; 1g n is a triple (q; ; m), where q 2 R n is a query vector, and
R is a threshold. The classier (q; ; m) classies any documents
d)  or irrelevant otherwise. The clas-
sier m) is called a linear classier with respect to the similarity
if m is a linear function from R n R n to R + .
For simplicity, we may just call (q; ; m) a classier, or a linear
classier when m is linear. The following are examples of classiers:
In particular, (q is a linear classier but the other three are
not, because m 1 is linear and m i are not linear for
DEFINITION 2. An adaptive supervised learning algorithm A for
learning a target classier (q; ; m) over the n-dimensional binary vector
space f0; 1g n from examples is a game played between the algorithm
A and the user in a step by step fashion, where the query vector q and
the threshold are unknown to the algorithm A, but the similarity m
is. At any step t  1, A gives a classier (q m) as a hypothesis
to the target classier to the user, where q t 2 R n and t 2 R. If
the hypothesis is equivalent to the target, then the user says \yes" to
conclude the learning process. Otherwise, the user presents an example
such that the target classier and the hypothesis classier
dier at x t . In this case, we say that the algorithm A makes a mistake.
At step t + 1, the algorithm A constructs a new hypothetical classier
m) to the user based on the received examples x
The learning complexity (or the mistake bound) of the algorithm A is
in the worst case the maximum number of examples that it may receive
from the user in order to learn some classier.
If the readers are familiar with on-line learning from equivalence
queries (Angluin, 1987; Littlestone, 1988), then an adaptive supervised
8 Z. Chen and B. Zhu
learning algorithm as dened above is a proper on-line learning algorithm
for learning the class of classiers from equivalence queries
over the n-dimensional binary vector space. We now give the formal
denition of Rocchio's similarity-based relevance feedback algorithm.
DEFINITION 3. Rocchio's similarity-based relevance feedback algorithm
is an adaptive supervised learning algorithm for learning any
classier m) over the n-dimensional binary vector space f0; 1g n
from examples. Let q 1 be the initial query vector. At any step t  1,
the algorithm presents a classier (q m) as its hypothesis to the
target classier to the user, where t 2 R is the threshold, and the
query vector q t is modied as follows. Assume that at the beginning of
step t the algorithm has received a sequence of examples x
then the algorithm uses the following modied query vector q t for its
next classication:
are called additive updating factors.
Please note that our denition above is a generalized version of
Rocchio's original algorithm. In our denition, any function m from
R n R n to R + can be used as a similarity; arbitrary real values can be
used in computing the updated query vector; and nally our denition
allows adaptive learning until the target is obtained.
REMARK 4. We would like to give the following remarks about Roc-
chio's similarity-based relevance feedback algorithm.
(a) In the above denition, Rocchio's similarity-based relevance feed-back
algorithm can use any real-valued threshold and any real-valued
additive updating factors at each step. But in practice the
additive updating factors  t j
may be xed as 1 (or 0:5) to promote
the relevance of relevant examples and 1 (or 0:5) to demote the
irrelevance of irrelevant examples (Baeza-Yates and Ribeiro-Neto,
1999; Salton, 1989).  t 0
is usually set to 1. Also in practice the
threshold is usually implicitly used for selecting a short list of top
ranked documents.
(b) For the purpose of the worst case analysis of the mistake bounds
of the algorithm, in the denition we only allow the algorithm to
receive one example at each step. We consider that the user acts
as an adversary to the algorithm and that the algorithm is required
Some Formal Analysis of Rocchio's Algorithm 9
to precisely learn (or search for) the target linear classier. In
practical applications, in contrast to the above worst case consid-
erations, at each step the algorithm may receive several examples
from the user; the user in general may not act as an adversary
to the algorithm; and the algorithm is usually required to search
for a short list of top ranked relevant documents. Hence, our lower
bounds proved in this paper may not aect the algorithm's eective
applicability to the real-world problems. The formal analysis of the
algorithm helps us to understand its nature well so that we may be
able to nd new strategy to improve its eectiveness or to design
new algorithms for information retrieval.
(c) When the similarity m is the inner product of two vectors, then
Rocchio's algorithm is similar to Rosenblatt's Perceptron algorithm
(Rosenblatt, 1958).
We will use the sets of documents represented by monotone disjunctions
of relevant features to study the mistake bounds of Rocchio's
algorithm. The e-cient learnability of monotone disjunctions of relevant
features (or attributes) has been extensively studied in machine
learning (for example, (Littlestone, 1988)). Although very simple in for-
mat, monotone disjunctions are very common ways of expressing search
queries, especially in the case of web search. All existing popular search
engines support disjunctions of keywords as search query formations.
For any k with 1  k  n, classiers can be dened to precisely classify
a monotone disjunction of at most k relevant features
i.e., to precisely classify whether any given document satises the monotone
disjunction of (2) or not. If we choose a vector u 2 R n such that
all its components are zero except that those at positions i are
one, then it is easy to verify that for any d 2 f0; 1g n , each of the
following four expressions is a necessary and su-cient condition for
deciding whether d satises (2):
kn
Z. Chen and B. Zhu
This implies that (u; 1
are all respectively classiers for (2).
3. Technical Lemmas
The technique used in (Kivinen et al., 1997) to prove linear lower
bounds for the Perceptron algorithm (or, in general, linear additive
on-line learning algorithms) is the construction of an example sequence
l )) with pairwise constant inner products
such that for any given initial query vector (or weight vector as used in
(Kivinen et al., 1997)) and any linear classier with the inner product
similarity, if the initial query vector and the linear classier dier on the
sequence B, then the Perceptron algorithm makes one mistake at one
of the two examples in every pair of B. In other words, each pair of the
sequence B preserves the classication dierence of the linear classier
and the initial query vector for the Perceptron algorithm when the
examples in B are used to update the query vector. It was shown in
(Kivinen et al., 1997) that row vectors of Hadamard matrices can be
used to construct the required example sequence B. We will borrow the
above technique from (Kivinen et al., 1997) to prove linear lower bounds
for Rocchio's similarity-based relevance feedback algorithm. However,
one must note that when a similarity (for example, the Jaccard coefcient
similarity) other than the inner product similarity is used, the
pairs of the sequence B as used in (Kivinen et al., 1997) may not still
preserve the classication dierence of the target classier (which may
not necessarily be linear) and the initial query vector. The rotation
invariant concept (Kivinen et al., 1997) is in general not applicable to
learning algorithms with a non-zero initial query vector, nor applicable
to non-rotation variants of the linear additive learning algorithms.
Therefore, we need to design new methods for constructing example
sequences that are applicable to Rocchio's similarity-based relevance
feedback algorithm with arbitrary initial query vector and any of the
four similarities dened in section 2.
In the following we extend Denition 7 given in (Kivinen et al., 1997)
to deal with any similarity.
DEFINITION 5. Let the sequence
l )), where
z 0
t and z 00
t are in f0; 1g n for all t. Let q 1 2 R n be a query vector, m a
similarity, and (u; ; m) a classier. Dene q
R. We say that the
query vector q t and the classier (u; ; m) dier on the sequence B
Some Formal Analysis of Rocchio's Algorithm 11
with respect to m if either
We now prove a weaker version of Lemma 8 in (Kivinen et al., 1997)
in which only the initial query vector (or weight vector in their term)
is required to dier from the target linear classier on the example
sequence, whereas we require that all the query vectors (the initial
one and the updated ones) dier from the target classier which in
general may not be linear. We do not use the pairwise constant inner
product property, because we may not have such a property for other
similarities.
LEMMA 6. Let m from R n R n to R + be a similarity and let q 1 2 R n
be the initial query vector. Let the sequence
l ));
where z 0
t and z 00
t are in f0; 1g n for all t. For any classier (u; ; m)
over the domain f0; 1g n , if q t , which is as dened in Denition 3, and
m) dier on B with respect to m for
similarity-based relevance feedback algorithm makes at least l mistakes
for learning the classier (u; ; m).
Proof. Let A be Rocchio's similarity-based relevance feedback algorithm
for learning (u; ; m). Consider the trial sequence
in which x t 2 fz 0
t g, and y t is the classication value of x t determined
by the unknown target classier (u; ; m) for In other
words, y m) classies x t as relevant or y
At any step t with 1  t  l, the hypothesis of the algorithm A is
m) with
according to expression (1) of Denition 3. By the assumption, q t and
m) dier on the sequence B with respect to m. That is, we
have either m(q t ; z
or In the rst
case, if t  m(q t ; z 0
t ), the adversary chooses x
t . In this case,
i.e., the target classier classies x
t as irrelevant, but
the hypothesis issued by A classies it as relevant, thus A makes a
Z. Chen and B. Zhu
mistake. If t > m(q t ; z 0
t ), the adversary chooses x
t . In such a
case, y i.e., the target classier classies x
t as relevant,
but the hypothesis issued by A classies it as irrelevant, thus again
A makes a mistake. In the second case of m(q t ; z 0
t ), with the same manner we can show that
the learning algorithm A makes a mistake at either z 0
t or z 00
t . Therefore,
A makes l mistakes on the trial sequence S. This means that A makes
at least l mistakes for learning the unknown target classier (u; ; m).We now follow the approach in (Kivinen et al., 1997) to construct
example sequences from row vectors of Hadamard matrices. Such sequences
are essentially applicable to Rocchio's similarity-based relevance
feedback algorithm when the zero initial vector is used, but not
when a non-zero initial vector is used. Let I n be the identity matrix of
order n.
DEFINITION 7. A Hadamard matrix H n of order n is an n  n
matrix with elements in f1; 1g, such that
H n is normalized if the rst row and the rst column consist of ones
only.
The above (2) implies that any two distinct rows (or columns) of a
H n are orthogonal. Normalized Hadamard matrices can be constructed
as follows. Let (1). For any
Two examples of Hadamard matrices are given as follows.
Some Formal Analysis of Rocchio's Algorithm 13
The following property follows from (3) and (4).
PROPOSITION 8. For be the t-th row of the
normalized Hadamard matrix H n for
DEFINITION 9. Let positive integers d and
k. For be the t-th row of the normalized Hadamard
. We dene BH to be the sequence ((z 0
where
z 0
z 00
PROPOSITION 10. Let positive integers d
and k and let
be the sequence as dened
in Denition 9. For any i and j with 1
Proof. We only prove (a), because (b) and (c) can be coped with
similarly. By Proposition 8,
h is
Similarly,
is 2
14 Z. Chen and B. Zhu
h is
We now introduce a new method for constructing example sequences
that are applicable to Rocchio's similarity-based relevance feedback
algorithm with any of the four similarities and an arbitrary initial query
vector. We expand a Hadamard matrix by adding rows and columns
with zeroes, and exchange rows and columns of the expanded matrix
according to the initial query vector. The new method is given in the
proof of Proposition 11.
PROPOSITION 11. Given any positive integers
d and k, for any query vector q 2 f0; 1g n , there is a sequence
such that v 0
t and v 00
t are in f0; 1g n for
and the sequence satises all the three properties given
in Proposition 10 with each occurrence of 2 d replaced by 2 d 1 and
each occurrence of z replaced by v, respectively. Furthermore, we have
q has at least 2 d 1 zero components or m 1 (q; v
Proof. Given any vector
for positive integers d and k, we have
This means that we can choose 2 d 1 components of q, denoted by
, such that they are either all one or all zero. Dene the

is the 2 d 1  2 d 1 Hadamard matrix. We move the rst
of C n to the rows
, respectively. This process
can be achieved through a sequence of exchanges of two rows. In other
words, there is an n  n transformation matrix A such that AC n does
the work and AA . We now move the rst 2 d 1 columns of AC n
Some Formal Analysis of Rocchio's Algorithm 15
to the columns
, respectively. Similarly, this process can be
achieved through a sequence of exchanges of two columns. Moreover,
does the work. Now, for any j with 1
row of AC n A T . Then, for 1  s  2 d 1 , the
component of d i j
denoted by x i s
is in fact the s-th component
of the j-th row of the Hadamard matrix H 2 d 1 . In other words, d i j
has all zero components except these 2 d 1 components x i s
forming a
subvector that is the same as the j-th row of H 2 d 1 . We nally construct
j from d i j
by changing all its 1 components to zero and keeping all
its other components. We also construct v 00
j from d i j
by changing all its
1 components to one and all its one components to zero, and keeping
all the other components. In other words, v 0
are constructed as
follows:
We rst construct z 0
j and z 00
j from the 2 d 1 2 d 1 Hadamard matrix
as in Denition 10.
We construct v 0
j by adding n 2 d 1 zero components to the end of
z 0
j and then moving the rst 2 d 1 components of z 0
through exchanging columns.
Similarly, we construct v 00
j by adding n 2 d 1 zero components to
the end of z 00
j and then moving the rst 2 d 1 components of z 00
j to
exchanging columns.
Hence, Proposition 11 follows from Proposition 8 in a manner similar
to Proposition 10. 2
In the following two lemmas we show that the sequence BH enables
the query vector q t to preserve m 1 similarity for any pair of z 0 t and
z 00
t in BH when the zero initial query vector is used, and the sequence
enables the query vector q t to preserve m 1 similarity for any
pair of v 0
t and v 00
t in D(q 1 ) when the arbitrary initial query vector q 1
is used.
LEMMA 12. For positive integers k and d, let BH
be the sequence dened in Denition 9. Let
where the initial query vector q
2 R, and
g. Then,
Z. Chen and B. Zhu
Proof. For any 1  j < t  2 d , for x
(b) and (c) we have m 1
For
for any 1  t  2 d ,
LEMMA 13. Let positive integers k and d. Given
any initial query vector q 1 2 f0; 1g n , let D(q 1 ) be the sequence given
in Proposition 11, and
g. Then,
q 1 has at least 2 d 1 zero components.
Proof. For any 1
g, by Proposition
11, properties similar to (b) and (c) of Proposition 10 hold for the
sequence D(q 1 ). Hence, we have m 1
any 2  t  2 d 1 , we have by Proposition 11
Some Formal Analysis of Rocchio's Algorithm 17
Thus, for any 2  t  2 d 1 has at
least 2 d 1 zero components, then again by Proposition 11 we have
The following lemma allows us to choose examples in some subdomain
to force a learning algorithm to make mistakes.
LEMMA 14. Given n > k 1  0, there is an adversary strategy that
forces any adaptive supervised learning algorithm to make at least k 1
mistakes for learning the class of disjunctions of at most k 1 variables
from fx i 1
g over the binary vector space f0; 1g n . Moreover,
the adversary chooses examples in the vector space with nonzero values
only for variables in fx i 1
g.
Proof. For any given adaptive supervised learning algorithm, at any
step t for 1  t  k 1, the adversary uses the example x t to defeat the
learning algorithm as follows, where x t has all zero components except
that its i t -th components is one: If the learning algorithm classies x t
as relevant, then the adversary classies it as irrelevant, otherwise the
adversary classies it as relevant. 2
One may easily note that the strategy we used above to prove
Lemma 14 can be generalized to prove the following fact: Any given
adaptive supervised learning algorithm makes at least n mistakes to
learn the class of disjunctions of at most n variables from fx
over the binary vector space f0; 1g n , because the algorithm can be
forced to make one mistake to determine whether or not each of the
n variables is in the target disjunction of at most n variables. Unfor-
tunately, one must note that this kind of strategy cannot be used to
prove that an adaptive supervised learning algorithm (such as Rocchio's
algorithm) makes at least n mistakes for learning a disjunction of at
most k variable when k is less than n, especially, when k is a small
constant. That is the reason why we must design sophisticated methods
in this paper to prove linear lower bounds for Rocchio's algorithm for
learning disjunctions of at most k variables, where k can be any value
between 1 and n. For example, k can be 1, 3, log n, or n. Disjunctions
of a small number of variables are the common ways for users to specify
their information needs. For example, in the real-world of web search,
the number of keywords used in a query session is usually very small.
The problem of learning disjunctions of a small number of variables
Z. Chen and B. Zhu
has been studied by many researchers (see, for example, the work in
(Littlestone, 1988)).
Careful readers may have observed that we do not rule out the choice
of in the decomposition of Proposition 8 to
Lemma 13 in this section. When
14 can be simply used to prove linear lower bounds for any adaptive
supervised learning algorithm (such as Rocchio's algorithm) to learn
disjunctions of at most variables over the binary vector space.
However, as we pointed out in the above paragraph, for any k such that
must reply on the choice of d 6= 0 in the decomposition
of to prove our linear lower bounds. For example, in the
case of with the choice of d 6= 0 such that d we can prove
that Rocchio's algorithm makes at least mistakes for learning
disjunctions of one variable when the zero initial query vector is used.
As we will show in the next section, the proof is accomplished through
the construction of 2 d pairs of examples from row vectors of Hadamard
Once again, the strategy of Lemma 14 or the like is not
applicable at all to the case of learning disjunctions of one variable, nor
to the case of learning disjunctions of a small number of variables.
4. Linear Lower Bounds
We are now ready to prove linear lower bounds for Rocchio's similarity-based
relevance feedback algorithm when any of the four typical similarities
is used. Throughout this section, we let
two positive integers d and k, and let u be the vector in f0; 1g n such
that its rst component is one, its last k 1 components have all k 1
or fewer ones (however, these one-components are not specied at this
point), and all other components are zero. Given any query vector
be its 2 d 1 components such that they
are either all zero or all one. Dene u(q 1 ) to be the vector in f0; 1g n
such that its i 1 -th component is one, its i j -th components are all zero
among the remaining n 2 d 1 components
there are at most k 1 one components (again, setting which of these
components to be one is not determined at this point). Note that both
respectively a monotone disjunction of at most k
relevant features. We use E(u) and E(u(q 1 )) to denote the monotone
disjunctions represented by u and u(q 1 ), respectively.
LEMMA 15. Let
2 d) be the example sequence
dened in Denition 9. For any similarity m i , 1  i  4, there
Some Formal Analysis of Rocchio's Algorithm 19
is a 2 R such that the query vector
and the classier dier on BH with respect to m i for
are arbitrary values in R, and x
g.
Proof. As noted in section 2,
1=
are respectively classiers for
the monotone disjunction E(u) of at most k relevant features. It follows
from Denition 9 that the rst component of z 0
t is one, the rst of z 00
is zero, and the last k components of each of both z 0
t and z 00
t are all
zero for 1  t  2 d . Hence, for any 1  t  2 d , we have by Propositionm 1 (u; z 0
kn
By Lemma 12 and the above (8) and (12), for any 1  t  2 d , q t and
the classier (u; 1=2; dier on the sequence BH with respect to m 1 .
For the similarity m 2 , for any t  2 we have by Proposition 10 and
Lemma 12
For
Because z 00 according to the
denition. Thus, for 1  t  2 d , we have
hence by (9) and (12) the query vector q t and the classier (u; 2=(k
dier on the sequence BH with respect to m 2 .
Z. Chen and B. Zhu
For the similarity m 3 , for any t  2 we have by Proposition 10 and
Lemma 12
For as for the similarity m
according to the denition. Thus,
(12) the query vector q t and the classier (u; 1=
dier on the
sequence BH with respect to m 3 .
Finally, for the similarity m 4 , for any t  2 we have by Proposition
For
Thus, for 1  t  2 d , we have m 4
and (12) the query vector q t and the classier (u; 1=(k
dier on the sequence BH with respect to m 4 . 2
LEMMA 16. Given any initial query vector
) be the example sequence dened in Proposition
11. For any similarity m i , 1  i  4, there is a 2 R such that
the query vector
and the classier dier on D(q 1 ) with respect to m i for
are arbitrary values in R, and x
g.
Moreover, if q 1 has at least 2 d 1 zero components, then q 1 and
dier with respect to m i , too.
Some Formal Analysis of Rocchio's Algorithm 21
Proof. The proof is the same as what we just did for Lemma 15, but
we need to replace u by u(q 1 ), z by v, and 2 d by 2 d 1 , respectively. We
also need to use Proposition 11 and Lemma 13 to complete our proof.We now prove the following main results in this paper.
THEOREM 17. Let positive integers d
and k. For any given similarity m i with
similarity-based relevance feedback algorithm makes at least n mistakes
for learning the class of monotone disjunctions of at most k relevant
features over the binary vector space f0; 1g n , when the initial query
vector and the similarity m i are used.
Proof. Let A be the Rocchio's similarity-based relevance feedback
algorithm with the similarity m i and the initial query vector q
We analyze the number of mistakes that A must make in learning
E(u), the disjunction of at most k relevant features represented by u.
As we noted before, there is a 2 R such that the classier
classies E(u), i.e., it is logically equivalent to E(u). By Lemma 15, the
classier and the query vector q t with 1  t  2 d dier on
the example sequence
d) with respect to
the similarity m i . Thus, by Lemma 6, the adversary can use examples
from BH to force the algorithm A to make 2 d mistakes. Note that the
last k 1 components of all examples in BH are zero and the last
components of u are unspecied but may have at most k 1 one
components. Hence, by Lemma 14, the adversary can further force A
to make at least k 1 mistakes to learn the values of the last k 1
components of u. Putting all together, A makes at least 2 d
mistakes for learning E(u). 2
THEOREM 18. Let positive integers d and k.
For any given similarity m i with similarity-based
relevance feedback algorithm makes at least (n+k 3)=2 mistakes
for learning the class of monotone disjunctions of at most k relevant
features over the binary vector space f0; 1g n , when an arbitrary initial
query vector q 1 2 f0; 1g n and the similarity m i are used. Moreover, if
the initial query vector q 1 has at least 2 d 1 zero components, then the
algorithm makes at least (n mistakes.
Proof. Let A be the Rocchio's similarity-based relevance feedback
algorithm with the similarity m i and the arbitrary initial query vector
We analyze the number of mistakes that A must make
in learning E(u(q 1 )), the disjunction of at most k relevant features
represented by u(q 1 ). As we noted before, there is a 2 R such that the
22 Z. Chen and B. Zhu
classier classies E(u(q 1 )), i.e., it is logically equivalent
to E(u(q 1 )). By Lemma 16, the classier (u(q 1 and the query
vector q t with 2  t  2 d dier on the example sequence D(q 1
respect to the similarity m i . If q 1
has at least 2 d 1 zero components, then the classier and q 1 also dier
with respect to m i . Thus, by Lemma 6, the adversary can use examples
from D(q 1 ) to force the algorithm A to make 2 d 1 1 mistakes, or 2 d 1
mistakes if q 1 has at least 2 d 1 zero components. Note that there are
positions such that the components of all examples
in D(q 1 ) at those positions are zero, and the components of u at those
components are unspecied but may have at most k 1 one components.
Hence, by Lemma 14, the adversary can further force A to make at
least k 1 mistakes to learn the values of the components of u at those
positions. Putting all together, A makes at least 2 d 1
(n+k 3)=2 mistakes for learning E(u); and if q 1 has at least 2 d 1 zero
components, A makes at least 2 d 1 mistakes. 2
The lower bounds obtained in Theorems 17 and are independent
of the choices of the threshold and coe-cients that Rocchio's
similarity-based relevance feedback algorithm may use in updating its
query vector and in making its classication.
5. Discussions
5.1. The Gradient Descent Procedure
As pointed out in (Wong et al., 1988), one primary concern in information
retrieval is to ensure that those documents more relevant to the
user information needs are ranked ahead of those less relevant ones.
This means that a ranking is acceptable if it can guarantee that less
preferred documents will not be listed in front of the more preferred
ones (such a ranking is called an acceptable ranking in (Wong et al.,
1988)). Let  denote the user preference relation over the document
vector space. Wong, Yao and Bollmann designed a very nice gradient
descent procedure to compute the query vector q satisfying
d  d
is called the dierence vector for documents d and d 0 .
Gradient Descent Procedure. The procedure is outlined as follows

(i) Choose an initial query vector q 0 and let
Some Formal Analysis of Rocchio's Algorithm 23
(ii) Let q k be the query vector in the k-th step. Identify the set of
dierence vectors
is a solution vector), terminate the procedure.
(iii) Let
b:
back to step (ii).
The above gradient descent procedure is a very nice adaptive algorithm
for computing the query vector. However, it must know the
user preference relation  ahead of the time and perform exhaustive
search to identify the set (q k ) at step (ii). The exhaustive search is
of exponential time complexity. In practice and in a machine learning
setting, the user preference relation  is the unknown target that must
be learned by an information retrieval system. In this sense, the gradient
descent procedure is not an adaptive learning process. On the other
hand, Rocchio's similarity-based relevance feedback algorithm formally
dened in section 2 is an adaptive learning algorithm without a priori
knowledge of the user preference. The updating process for the query
vector at each iteration is of linear time complexity.
5.2. Learning Other Document Classes
In this paper, we study the learning of a document class represented
by a monotone disjunction of index features (or terms) with Rocchio's
algorithm. In fact, Rocchio's algorithm can be easily used to learn other
target document classes such as the class represented by a conjunction
of disjunctions of index features (or terms). Conjunctions of disjunctions
are the most common forms for search queries as constructed
by humans. We give several examples here. From those examples we
know that the lower bounds proved in previous section on the learning
performance of Rocchio's algorithms hold for those learning cases.
Example 1 (Learning Arbitrary Disjunctions). An arbitrary
disjunction is a general case of monotone disjunctions and may have
negated index features in it. A negated index feature in a disjunction
means that the feature should not occur in the desired documents. Let
_    _
be an arbitrary disjunction. Let z document vector
that makes g false, i.e., g(z must have z
Z. Chen and B. Zhu
1. We can use z to transform g into
a monotone disjunction
Please also note that the same z can be used to transform f back into
g in the following manner
The above transformation methods tell us that g can be learned as
follows. First, use Rocchio's algorithm with an initial query vector q
to learn g. When a document vector judged by the
user as irrelevant, then one can use this z to transform any obtained
document vector
continue the learning. With this kind of transformation, the algorithm
actually learns the function f . But as we observed before, f can be easily
transformed into g with the document vector z. The above process
implies that learning an arbitrary disjunction with Rocchio's algorithm
has the same performance as learning a monotone disjunction.
Example 2 (Learning Monotone Conjunctions). Let
be a monotone conjunction, i.e., all index features occurred in g are
positive. The negation of g is a disjunction
_    _
Note that the vector z can be used to transform  g into a
monotone disjunction
and to transform f back into  g
Hence, to learn g we only need to learn its negation
g, and by example
1 this can be done with Rocchio's algorithm.
Example 3 (Learning Arbitrary Conjunctions). Let
be an arbitrary conjunction. The negation  g of g is
_    _
Some Formal Analysis of Rocchio's Algorithm 25
which is an arbitrary disjunction. To learn g we only need to learn
its negation  g, and by Example 1 this can be done with Rocchio's
algorithm.
Example 4 (Learning Disjunctions of Conjunctions). Let
be a disjunction of conjunctions, G i is a conjunction for 1  i  s.
Using the virtual variable technique developed in (Maass and Warmuth,
1998), one can learn G as follows: Introduce one new input variable
(virtual variable) for each of the possible 3 n conjunctions that can be
constructed from variables x . When the values of x are
known, then the value of each virtual variable is easy to be determined.
With the help of virtual variables, G is a monotone disjunction and thus
can be learned with Rocchio's algorithm.
Example 5 (Learning Conjunctions of Disjunctions). Let
be a conjunction of disjunctions, F i is a disjunction for 1  i  s.
Because the negation of F is a disjunctions of conjunctions, as in
Example 4 the virtual variables technique developed in (Maass and
Warmuth, 1998) can be used to learn the negation of F and hence F
itself.
5.3. A Remark on the Optimal Criterion of Rocchio's
Algorithm
According to (J.J. Rocchio, 1971; Salton, 1989), the construction of
an ideal query vector would target to maximize the average query-document
similarity for the relevant documents and at the same time
minimize the average of the query-document similarity for the irrelevant
documents. It is known in (J.J. Rocchio, 1971; Salton, 1989) that under
appropriate assumptions such an ideal query vector has the form
(R
Rel
Nonrel
where R and N R are the assumed number of relevant and irrelevant
documents, and the summations range over the sets of normalized
relevant and irrelevant documents, respectively. However, the optimal
query vector cannot be adopted in practice, because the sets of relevant
and irrelevant documents with respect to the queries are not known
26 Z. Chen and B. Zhu
before an exhaustive search. Recall that the gradient descent procedure
in (Wong et al., 1988) has a similar problem. On the other hand, the
optimal query vector can be adaptively approached in the following
(see (Salton, 1989)):
where R 0 is the set of documents judged by the user as relevant by the
end of iteration i, and N 0 is the set of documents judged as irrelevant. In
the above two approximation formulas, 1
,  and  are updating
factors (or coe-cients). In our formalization of Rocchio's algorithm
given in section 2, arbitrary updating factors are allowed. The lower
bounds we have proved are in fact independent of the choices of the
updating factors. That is, our lower bounds hold even if 1
and 1
are used as updating factors.
5.4. Counting Arguments
For any k with 1  k  n, given any disjunction of k variables
it is easy to know that there are 2 n k documents in the binary vector
space f0; 1g n that are irrelevant to Q, i.e., the vectors of those documents
make Q false; and that there are 2 n 2 n k documents that
are relevant to Q, i.e., the vectors of those documents make Q true.
When k is small, say 3 is a huge value for a very large n.
That is, there are a huge number of documents that are irrelevant to Q.
One might ask whether or not this kind of observation helps us to nd
some simple ways to prove linear lower bounds for Rocchio's algorithm.
For example, an adversary could, in response to almost any formulated
query, produce some document which matches the query to some degree
but it not relevant. As a matter of fact, this sort of idea is in essence an
example of the decision tree technique developed in (Littlestone, 1988)
to prove lower bounds for general learning algorithms:
In the decision tree, each inner node is labeled with a document
vector in the binary vector space f0; 1g n .
There are two edges leaving each inner node, labeled \relevant"
and \irrelevant", respectively.
Some Formal Analysis of Rocchio's Algorithm 27
Each leaf is labeled with a disjunction of at most k variables in
such a way that the disjunction at the leaf is consistent with all
the labels along the path leading from the root to the leaf ( the
number of inner nodes along this path is the depth of the leaf).
Assume that the depth of every leaf of the decision tree is at least
t. Then, the mistake bound of any learning algorithm for learning
disjunctions of at most k variables is at least t. Readers can refer
(Littlestone, 1988) for the proof of this statement.
The decision tree technique is useful because it reduces the problem
of proving a lower bound for every learning algorithm to the problem
of constructing a single decision tree with the required depth. The
latter can usually be done through counting arguments to estimate the
depth of the decision tree. To our best knowledge, (Maass and Turan,
1994) is the best article to prove lower bounds for learning a threshold
gate, a general case of a disjunction of at most k variables. The article
presents several powerful counting arguments to estimate the depth
of decision tree for the class of threshold gates. Unfortunately, those
counting arguments do not help us to obtain linear lower bounds for
Rocchio's algorithm. The reason is that there are not many monotone
disjunctions of at most k binary variables. One can easily nd out that
the number of monotone disjunctions of at most k binary variables is
The least depth of the decision tree for the class of monotone disjunctions
of at most k binary variables is log 2 C(k). For example,
log
log
log
log 2 C(k) < log 2 C(n) < n; for any k < n:
Therefore, counting arguments cannot yield linear lower bounds for
Rocchio's algorithm when k is much less than n, especially when k is
a small constant. For example, when the lower bound produced
by the counting argument is just log 2 n. However, the non-counting
technique that we use is this paper can yield linear lower bounds for
Rocchio's' algorithm for any k with 1  k  n, even
recall that disjunctions of a small number of variables are the common
28 Z. Chen and B. Zhu
ways for users to specify their information needs. For example, in the
real-world of web search, the number of keywords used in a query
session is usually very small. The problem of learning disjunctions of a
small number of variables has been studied by many researchers (see,
for example, the work in (Littlestone, 1988)).
6. Conclusions and Open Problems
Rocchio's similarity-based relevance feedback algorithm is one of the
most popular query reformation method in information retrieval and
has been used in various applications. It is essentially an adaptive
supervised learning algorithm from examples. However, there is little
rigorous analysis of its learning complexity. In this paper we prove
linear lower bounds for Rocchio's similarity-based relevance feedback
algorithm when any of the four typical similarities listed in (Salton,
1989) is used. Because the linear lower bounds are proved with the worst
case analysis, they may not aect the algorithm's eective applicability
to the real-world problems. The lower bounds help us understand the
nature of the algorithm well so that we may nd new strategies to improve
the eectiveness of Rocchio's algorithm or design new algorithms
for information retrieval. One possible way is to use the Winnow2
(Littlestone, 1988) algorithm as an alternative for the similarity-based
relevance feedback algorithm in applications of information retrieval.
For example, in our recent research on building real-time intelligent
web search engines (Chen et al., 2000; Chen and Meng, 2000), we used
a tailored version of Winnow2.
We list the following open problems for future research.
Problem 1. The lower bound in Theorem holds for an arbitrary
initial query vector q 1 2 f0; 1g n . Choosing a zero-one initial query
vector is a very common practice in applications. For example, in web
search an initial zero-one query vector may be constructed with the
query words submitted by the user. When the initial query vector q 1 is
chosen from R n , we can prove the same lower bound with the similar
but tedious approach for the similarities But we do
not know whether the same lower bound still holds for m 4 .
Problem 2. In this paper we have proved linear lower bounds for
Rocchio's similarity-based relevance feedback algorithm in the binary
vector space. We do not know whether our approach can be extended
to study the learning complexity of Rocchio's algorithm in arbitrary
discretized vector space.
Problem 3. The linear lower bounds we have established for Roc-
chio's algorithm in the binary vector is based on the worst-case anal-
Some Formal Analysis of Rocchio's Algorithm 29
ysis. It would be very interesting to analyze the average-case learning
complexity of Rocchio's algorithm. We feel that this problem is very
challenging, because any nontrivial average case analysis will reply
on realistic models of document distribution, index term distribution,
and the user preference distributions as well. We feel that it is not
easy to model those distributions nor to analyze the complexity under
those distributions. The probabilistic corpus model proposed in
(Papadimitrious et al., 2000) may shed some light on this problem.
Problem 4. Although it follows from our linear lower bounds that
the Winnow2 algorithm (Littlestone, 1988) has better worst case learning
complexity, the authors do not know any provable theoretical analysis
of the average learning complexity about the Winnow2 algorithm,
nor about the similarity-base relevance feedback algorithm. More pre-
cisely, we do not know whether the Winnow2 algorithm performs better
in average than the Rocchio's similarity-based relevance feedback
algorithm.

Acknowledgements

In early 1997, Dr. Stanley Sclaro asked the rst author whether the
relevance feedback algorithm can be used to help the user search for
the desired World Wide Web documents with about two dozens of
examples judged by the user. At the time, his research group implemented
ImageRover (Taycher et al., 1997; Sclaro et al., 1997), an
image search engine from the user's relevance feedback, while the author
and his colleagues started to build intelligent search tools (such
as Yarrow (Chen and Meng, 2000), WebSail (Chen et al., 2000) and
Features (Chen et al., 2001)) with the help of information retrieval and
machine learning techniques. Dr. Sclaro's question together with the
authors' own research on building intelligent web search tools inspired
the work in this paper. The authors would also acknowledge that the
example sequence selection method developed in (Kivinen et al., 1997)
for proving linear lower bounds for the Perceptron algorithm is the key
to the breakthrough of our proofs. Without knowing the method it
would take longer for the authors to nish the work in this paper.
We thank three anonymous referees and the journal editor, Professor
Paul B. Kantor, for their critical and valuable questions and comments
for helping us to revise this paper. We thank one referee for informing
us the reference (Wong et al., 1988).
Z. Chen and B. Zhu



--R

Queries and concept learning.
Modern Information Retrieval.
Multiplicative adaptive algorithms for user preference retrieval.
Yarrow: A real-time client site meta search learner

WebSail: From on-line learning to web search
IEEE Press
Information Retrieval: Data Structures and Algorithms.


Relevance feedback in information retrieval.
The Smart Retrieval System - Experiments in Automatic Document Processing

The perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant.

Learning in intelligent information retrieval.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm


Information and Computation
Latent semantic indexing: A probabilistic analysis.
A critical analysis of the vector space model for information retrieval.
The perceptron: A probabilistic model for information storage and organization in the brain.
Automatic Text Processing: The Transformation

A vector space model for automatic indexing.

Cascia M and Sclaro
Linear structures in information retrieval.


--TR

--CTR
Ying Liu , Dengsheng Zhang , Guojun Lu , Wei-Ying Ma, A survey of content-based image retrieval with high-level semantics, Pattern Recognition, v.40 n.1, p.262-282, January, 2007
relevance feedback;similarity;supervised learning;lower bound;vector space