Proceedings of the Third NTCIR Workshop

Experiment on Pseudo Relevance Feedback Method
Using Taylor Formula at NTCIR-3 Patent Retrieval Task
Kazuaki KISHIDA
Surugadai University* / National Institute of Informatics*698 Azu, Hanno, Saitama 357-8555 Japankishida@surugadai.ac.jp

Abstract
Pseudo relevance feedback is empiricallyknown as a useful method for enhancing retrieval
performance. For example, we can apply the
Rocchio method, which is well-known relevance
feedback method, to the results of an initial searchby assuming that the top-ranked documents are
relevant a priori. In this paper, for searching
NTCIR-3 patent test collection through pseudo
feedback, we try to employ two relevance feedback mechanism; (1) the Rocchio method, and (2)a new method that is based on Taylor formula oflinear search functions. The test collection consists of near 700,000 records including full text ofJapanese patent materials. Unfortunately, effectiveness of our pseudo feedback methods was not
empirically observed at all in the experiment. Oneof the reasons may be that all words from the
documents to be assumed as relevant were usedwithout any selection process.
Keywords: Pseudo relevance feedback, Patent
retrieval, Rocchio method

1

Introduction

Relevance feedback is widely recognized as aneffective method for improving retrieval effectiveness in the context of interactive IR. As often
pointed out, it is difficult for users to represent
her/his own information needs into a well-defined
set of search terms or statements. The resulting
short or poor queries would bring them only unsatisfactory results. However, if a few relevant
documents happen to be found by the search, we
could automatically or manually extract some
useful terms from the documents, and add them tothe initial search expression. It is obviously expected that search effectiveness of the second
search using the extended query will be improved
significantly. This is a basic idea of relevance
feedback.
Inevitably, for executing automatic relevance© 2003 National Institute of Informatics

feedback, the system has to obtain relevance information, i.e., relevant or irrelevant documents,from the users interactively. However, some researchers have tried to employ relevance feedback
techniques with no relevance information. The
main purpose is to enhance search performance of
retrieval models such as vector space without interaction between system and users for relevance
information. The technique is usually called
pseudo relevance feedback (or automatic relevance feedback), in which a standard feedback
method (e.g., Rocchio method) is applied by assuming that top-ranked documents searched by
the initial search are relevant a priori.
The purpose of the paper is to examine effectiveness of pseudo relevance feedback empiricallyby using the patent test collection of NTCIR-3. In
particular, we attempts to compare search performance of the traditional Rocchio method withthat of an alternative method proposed by Kishida[1]. Kishida[1] has reported that the alternative method outperforms slightly the Rocchio
method in an experiment of normal relevance
feedback mechanism (not pseudo feedback) employing NTCIR-1 test collection, which consistsof about 330,000 bibliographic records of proceedings at conferences held in Japan[2]. We try
to ascertain if the method has a positive effect in
the case of pseudo relevance feedback.
The rest of this paper is organized as follows.
In Section 2, the Rocchio method and the alternative method proposed by Kishida[1] will be introduced. In Section 3, outline of retrieval experiment using NTICIR-3 patent test collection
will be shown. Finally, we will discuss the experiment results and implications in Section 4.

2 Relevance Feedback Methods
2.1 Rocchio method
The most typical approach to relevance feedback would be so-called the Rocchio method [3],which is based on the vector space model. The

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

basic idea of this method is to add an average
weight of each term within the set of relevant
documents to the original (or initial) query vector,
and to subtract an average weight within the set ofirrelevant ones from the vector.
We denote a document vector by

d i = ( wi1 ,..., wiM ) T where wij is a weight ofa termt j within the document di , and theoriginal

query

vectorq = ( wq1 ,..., wqM ) T

wqj is a weight of a term t j within thequery ( M is total number of distinct terms in thecollection and T indicates transposition). A
q is obtained by themodified query vector ~whereformulaβγ~q = αq +di −∑∑ di (1)D1 i:di ∈D1
D0 i:di ∈D0
where D1 is the set of relevant documents, D0
is the set of irrelevant documents, and α ， β ，and γ are constants.
It has been empirically shown that the performance of the Rocchio method is fairly good [4],and in recent, many researchers have examined
the method directly or indirectly [5-8]. Also, due
to its effectiveness and simplicity, the Rocchio
method has also been applied in other researchareas, for example, image retrieval [9] or text
categorization [10].

2.2 Feedback method using Taylor formulaof retrieval function
Kishida[1] has proposed an alternative relevance feedback method, which is suitable for thesituation that the degree of relevance is given as anumerical value, not dichotomous value (i.e.,
relevance or not), from actual users. Also, as another feature, Kishida[1] has suggested that themethod is able to be applied to the Okapi formula[11] rationally as well as vector space model.
According to Kishida[1], details of the method
will be explained in the rest of this section.
2.2.1 Retrieval model based on linear matching
functionIn the vector space model, typical formulas fordetermining the term weights wij and wqj arerespectively,

wij = log xij + 10
. , and(2)()

wqj = (log x qj + 10. ) log N n j ,(3)

xij is frequency of term t j within the
document di , xqj is frequency of term t j

where

within the query, n j is the number of documents
including term t j , andN is the total numberof documents in the database [12]. For calculating
the degree of similarity between a document vector di and the query vector q , a cosine formula is normally used such thatsi = ∑ j =1 wij wqj

∑

M

w2
w 2 , (4)j =1 ij ∑ j =1 qj

MM

where si is a numerical score indicating thesimilarity or relevance probability of the document di given a query. The cosine formula (4) isa matching function of the vector model.
On the other hand, in the case of the Okapi
formula,3.0 xijM 
si = ∑ j =1  (0.5 + 1.5 l l ) + xiijN − n j + 0.5 , (5)× x qj log
n j + 0.5 
whereli = ∑ j =1 xij ，and l = N −1 ∑i =1 li ,MNi.e., li is document length, and l is the average within the database. The formula (5) is one
version of Okapi formula, and it should be notedthat there are some different formulas according
to its way of setting its parameters.
Kishida[1] has shown that we can represent
uniformly these retrieval models as a linear function of vector,s = f (b) = Ab
(6)where s = ( s1 ,..., sN )T

f is a linear func→ R N ×1 ) and A is ation of vector ( f : R
N × M matrix of which element aij is,

M ×1

aij = (log xij + 10
. )∑ (log x + 10. )
M

2

ij

j =1

(7)
in the case of vector space model (see (2) and (4)),
ora ij =

3.0 xij(8)(0.5 + 1.5 l i l ) + xij

in the case of Okapi formula (see (5)).
Also, b is a M dimensional vector ofwhich element b j （ j = 1,..., M ）is defined as

b j = wqj
where

∑

M
j =1

wqj2

(9)

(

wqj = (log x qj + 10. ) log N n j

the case of vector space model (see (3)), or) inProceedings of the Third NTCIR Workshop

b j = x qj log

N − n j + 0.5(10)

n j + 0.5

in the case of Okapi formula.
The most important thing is that the two very
well known formulas for calculating documentscores in ranked output can be represented into afairly simple unified form (6).
2.2.2 Use of Taylor formula
In ranked output, documents are sorted in decreasing order of their scores si ( i = 1,..., N ).

si is assumed to indicate
the degree of relevance. In other words, si is toThis means that eachbe expected as an estimate of ‘true’ value of relevance degree ri . Let r = ( r1 ,..., rN ) be a vector
representing the true relevance degree. By using
these notations, we can describe operationally the
purpose of retrieval system as “an estimation of avector s that is the closest to the vector r
given a search request.”
Of course, r is unknown in real situations,but it is possible to get information on a part of r
through relevance feedback process. For example,
if the user replies a set of scores indicating each
degree of relevance for top-ranked n documents
after an initial search, the scores allow us to estimate a part of r corresponding to the n documents.
We denote the set of top-ranked n documents by X and a part of r corresponding to
the set X by rX . In similar with (6), we candefine thats X = f X (b) = A X b ,(11)T

where A X is a n × M matrix and s X is ann dimensional vector, of which elements are
aij and si respectively, where d i ∈ X→ R n ×1 ). If we establish a distancemeasure φ between rX and s X , the purpose( fX:R(13)
where K is a residual term (see Harville[13]). If
we employ (11) and assume that rX is equal to~f X (b ) according to our target condition (12),

we obtain~b = b + A −X1 (r X − s X ) .

(14)(see Appendix for details).
The equation (14) contains an abnormal inverse

A −1
X , which is a M × n matrix and−1
A X A X = I M where I M is a M × M ma-

matrixtrix of which all diagonal elements are 1 and others are 0. Using singular value decomposition(SVD), the transpose matrix of A X can be rep-

A TX = UΛV T

U isa M × n orthogonal matrix, Λ is a n × n diagonal matrix and V is a n × n orthogonal
resented

as

where

matrix. By employing the decomposition, we canfinally represent (14) as~
b = b + UΛ−1 V T (r X − s X ) .

(15)
This is a final formula of our relevance feedback
algorithm. For convenience, we call the algorithm
the Taylor formula based method.

3 Outline of Retrieval Experiment
3.1 Test Collection
We use the patent test collection prepared for
NTCIR-3 project [14], which consists of over
690,000 records containing full text of Japanese
patent materials. All 31 queries in Japanese wereused for the experiment in this paper.

M ×1

of relevance feedback can be formally describedas follows: the relevance feedback aims at calcu-~

lating b such that~b = arg min φ (r X , s X )b= arg min φ (r X , f X (b)) .
(12)b~Then b is to be used for the second search.
~
The approach to calculating b suggested in
Kishida[1] is to focus on the difference between
the initial document scores f X (b) and the~f X (b ) , and to apply Taylor~
formula for obtaining a vector function f X ( b ) ,secondary scoresi.e.,∂ f X (b) ~~f X (b ) = f X (b) +(b − b) + K∂ bT

3.2 Procedure and type of runs
The procedure of the experiment is as follows:(a) Initial search: two initial search runs are carried out, i.e., the first is based on vector spacemodel from (2) to (4) and the second is Okapi
formula (5). We denote the initial search runs
by VECTOR and OKAPI, respectively.
(b) Query modification by pseudo relevance
feedback; initial queries are modified by assuming that top-ranked n documents ofeach initial run are relevant. In this paper we
set n = 10 .
(i) In the case of vector space model, theRocchio method (1) is applied. The run isdenoted as ROCCHIO.
(ii) In the case of the Okapi formula, theTaylor formula based method (15) is em-

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

ployed. We denote this run TAYLOR.
(c) Second search: each modified query is used
for the second run.
(i) In the case of ROCCHIO, modified queries are matched with document vectors
by cosine formula (4).
(ii) In the case of TAYLOR, the linear function (6) is used for matching operation.
Furthermore, we discern two kinds of run according to query (topic) fields used for run; (I)<ARTICLE> and <SUPPLEMENT> fields and(II) <DESCRIOTION> and <NARRATIVE>
fields. As a result, in the experiment, six runs in
total were executed as shown in Table 1. It should
be noted that Okapi-none runs (i.e., normal Okapi
formula without any feedback) were added as abaseline for evaluating pseudo feedback methods.
Table 1 Search runs in the experiment
Topic fields
initial run feedback<A><S>* <D><N>**
OKAPI
TAYLOR
Run1
Run2
VECTOR ROCCHIO
Run3
Run4
OKAPI
none
Run5
Run6
*<A>:<ARTICLE>, <S>:<SUPPLEMENT>**<D>:<DESCRIPTION>,<N>:<NARRATIVE>

3.3 Implementation of pseudo relevance
feedback method
As to the Rocchio method, we can directly use(1) for pseudo relevance feedback by assumingthat the set of top-ranked n documents equals
with D1 , and D0 is empty. In the experiment,
we suppose α = 8 , β = 16 and γ = 0 .
In the case of Taylor formula based method,
we need to determine the value of variable ri inthe equation (15), which means ‘true’ degree of
relevance ( i = 1,..., n ). A simple way is to assume a simple linear function such that(16)
ri = Asi + B ,and to estimate each relevance degree ri fromthe corresponding document score si calculated
for the initial search.

let rmax ands max be the maximum valuesof ri and si in the set of top-ranked ndocuments, respectively. Similarly, the minimum
values of ri and si are denoted as rmin ands min , respectively. Thus, the constants A and
B in (16) are determined as a solution of equations,rmax = As max + B.
 rmin = As min + B(17)

It is easy to show that

A = (rmax − rmin ) /( s max − s min ) ,(18)

B = ( s max rmin − rmax s min ) ( s max − s min ) .(19)To employ this method for estimating constants,
we have to determine values of rmax and rmin ,but there is no reasonable way in the context ofpseudo feedback. Thus, as a trial, we set thatrmax = 2 × s max

andrmin = s max

inexperiment.
In both of the Rocchio method and Taylor formula based method, no tern selection that extracts‘useful’ words from the n documents according
to its weight is executed.

3.4 Segmentation of Japanese text
The patent test collection for NTCIR-3 basically consists of documents written in Japanese
language, and query statements are also in Japanese. As well known, Japanese text has no explicit
boundary between terms unlike English. Thus weneed to segment the text into a set of terms
automatically for indexing documents and query.
In this paper, each term is identified through an
operation of matching strings in the text withentries included in a machine-readable dictionary.
We used the dictionary of ChaSen [15] andselected as an index term the longest entry
matched with a portion of text (longest-matching
method). Also, two heuristic rules were applied
additionally; (A) unmatched string is decomposed
according to change of type of characters, and (B)for identifying compound words as content-bearing terms, a pair of adjacent two terms

Table 2 Average precision and R-precision of each run
initial run
feedback
Average precision
R-precision
OKAPI
TAYLOR
0.11520.1421VECTORROCCHIO
0.12810.1565
OKAPI
none
0.12820.1565<DESCRIPTION>OKAPITAYLOR
0.13700.1820<NARRATIVE>
VECTORROCCHIO
0.15810.1896
OKAPI
none
0.15830.1813
Note: The values in the table are calculated based on both of relevant and partially relevant documents.
Topic Fields<ARTICLE><SUPPLEMENT>theProceedings of the Third NTCIR Workshop

pair of adjacent two terms identified by dictionary
matching or rule (A) is automatically combined
into a compound word.
In the experiment, index terms were extracted
from only title and claim fields in the text of eachdocument. This means that full text included in
the records was not used for search. However, it isanticipated that most of important terms are contained in the title and claim fields. In the term ofsubject search, limiting the fields for indexing
does not necessarily cause low performance.

3.5 The System
In the experiment, all tasks were executed on a
personal computer SONY VAIO PCV-LX53/BP(CPU:1.50GHz, MEMORY:256MB, HDD:80GB)
using Microsoft Visual C++ on Windows XP.
For executing runs, an inverted file of indexing
term and some other files were constructed using
the technique of B-tree.

TAYLOR and ROCCHIO

0.9
0.8

ROCCHIO

0.7

TAYLOR

0.6
0.5
0.4
0.3
0.2
0.1
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

tically significant differences between any pairs of
runs. However, performance of Taylor formulabased method may be slightly low.

4.3 Topic-by-topic analysis
Figure 1 is a plot of values of average precisionby topic. We can compare the Taylor formulabased method (OKAPI-TAYLOR) and the Rocchio method (VECTOR-ROCCHIO) with normal
Okapi formula (OKAPI-none), in level of each
topic. It should be noted that, in Figure 1, squareindicates ROCCHIO and circle TAYLOR.
Figure 1 shows that for most of topics, normal
Okapi formula with no pseudo feedback outperforms the Rocchio method and Taylor formulabased method although there are a few topics forwhich the Rocchio and Taylor dominate.

4.4 Discussion
Adding all words that appear in 10 top-ranked
documents would cause the failure of our pseudo
feedback technique. We should have attempted to
select significant words by a method proposed in
the literatures on pseudo relevance feedback. A
simple method would be to add only some
top-ranked words in the decreasing order of term
weights (e.g., tf-idf). Another method is to assume‘irrelevant’ documents as well as relevant ones
and to take both sets of documents into account in
the process of pseudo feedback.
Unfortunately, the failure prevents us fromcomparing empirically effectiveness of the Taylor
formula based method with that of traditional
Rocchio method. As shown in Table 2, it seems
that there is no statistically significant difference
between the two methods within the range of results obtained from our experiment.

OKAPI-none

5
Figure 1 Topic-by-topic analysis(average precision)

4

Results and Discussion

4.1 Basic Statistics
In our indexing phase, 697,262 records were
processed and average length of documents is393.32.

4.2 Overall Performance
Table 2 shows search performance of each run.
Unfortunately, pseudo relevance feedback using
relevance feedback techniques has no effect on
the performance. It seems that there are no statis-

Concluding remarks

An alternative feedback method based on
Taylor formula proposed by Kishida [1] has
unique characteristics as follows;(a) the method is suitable when the degree of
relevance is represented as a continuous value,
not dichotomous value.
(b) the method is applicable to a large class of
retrieval models including vector spacemodel and the Okapi weighting.
As to (b), in the model, equation for calculating
document score has to be a linear function ofquery vectors.
As discussed above, the new method did notwork well as a method for pseudo relevance
feedback in the experiment. Further study would
be needed for applying such relatively complicated methods to pseudo relevance feedback.

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

Acknowledgement
The author would like to appreciate organizersof NTICR-3 patent retrieval task for preparing avaluable test collection.

References[1] K. Kishida. Feedback method for document
retrieval using numerical values on relevance
given by users. In IPSJ SIG Notes
Fundamental Infology, No.61, pages 189-196,
2001. (In Japanese)[2] N. Kando, and T. Nozue eds. Proceedings ofthe First NTCIR Workshop on Research inJapanese Text Retrieval and Term Recognition.
Tokyo, National Center for Scientific Information Systems. http://www.nii.ac.jp/ntcir/[3] J. J. Rocchio, J.J. Jr. Relevance feedback in
information retrieval. In G. Salton ed., The
SMART Retrieval System: Experiments in
Automatic Document Processing, Englewood
Cliffs, New Jersey, Prentice-Hall, pages
313-323, 1971.
[4] G. Salton, and C. Buckley. Improving retrieval
performance by relevance feedback. Journalof the American Society for Information Science, 41(4): 288-297, 1990.
[5] P. Sarinivasan. Query expansion and MEDLINE. Information Processing and Management, 32(4): 431-443, 1996.
[6] J. H. Lee. Combining the evidence of different
relevance feedback methods for information
retrieval. Information Processing and Management, 34(6): 681-691, 1998.
[7] R. Mandala, T. Tokunaga and H. Tanaka.
Query expansion using heterogeneous thesauri.
Information Processing and Management, 36,361-378, 2000.
[8] Makoto Iwayama. Relevance feedback with asmall number of relevance judgments: incremental relevance feedback vs. Document clustering. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 10-16, 2000.
[9] G. Ciocca and R. Schettini, R. A relevance
feedback mechanism for content-based image
retrieval. Information Processing and Management, 35: 605-632, 1999.
[10] Marie-Francine Moens and Jos Dumortier.
Text categorization: the assignment of subject
descriptors to magazine articles. Information
Processing and Management, 36(6):841-861,
2000.
[11] S. Robertson, et al. Okapi at TERC-3. In D.K.
Harman ed. Overview of the Third Text Retrieval Conference (TREC-3), pages 109-126,

1995.
[12] C. Buckley, J. Allan and G. Salton. Automatic routing and ad-hoc retrieval using
SMART: TREC2. In D.K. Harman ed. The
Second Text Retrieval Conference (TREC2) ,pages 45-55, 1994.
[13] D. A. Harville. Matrix Algebra from a Statistician’s Perspective. New York, Springer, 1994.
[14]http://research.nii.ac.jp/ntcir/workshop/patent/[15] Y. Matsumoto, A. Kitauchi, T. Yamashita, Y.
Hirano, H. Matsuda and M. Asahara. Japanesemorphological analysis system ChaSen version
2.0 manual 2nd ed. Technical Report
NAIST-IS-TR99009, NAIST, 1999.
http://cl.aist-nara.ac.jp/lab/nlt/chasen/

Appendix
If we assume a linear function (11), then∂ f X (b) ∂ ( A X b)=
= AX ,∂bT∂bT

which is a well known result in the field of linear
algebra [13]. Therefore (11) becomes that~~f X (b ) = f X (b) + A X (b − b)(it should be noted that K = 0 ).

rX is~equal to f X ( b ) and noting that f X (b) = s X ,~rX = s X + A X (b − b)(this assumption means that φ = 0 ), we can obBy following our assumption thattain~
A X ( b − b) = r X − s X .

(A.1)
The equation (14) is easily derived from (A.1).
By using singular value decomposition we canobtain thatA TX = UΛV T . The transposition is

( ) (
T

)

T

A X = A TX = UΛV T = VΛU T (A.2)
because U and V are orthogonal matrixesand Λ is a diagonal matrix. Substituting (A.2)
into (A.1), we finally obtain that~VΛU T (b − b) = rX − s X~b − b = UΛ−1V T (rX − s X )~∴ b = b + UΛ−1 V T (r X − s X ) .

The last equation is equivalent to (15).