Empirical Term Weighting
Kyoji UMEMURA Yoshiyuki TAKEDA Michiko TANAKA Lin FENG Eiko YAMAMOTO
Toyohashi University of Technology
Toyohashi Aichi 441-8580 Japanulab@ss.ics.tut.ac.jp

Abstract
Our system used an empirical method for estimating term weights directly from relevance judgements,
avoiding various standard but potentially troublesome
assumptions. It is common to assume, for example,that weights vary with term frequency ( ) and inverse
document frequency ( ) in a particular way, e.g., 
 , but the fact that there are so many variantsof this formula in the literature suggests that there remains considerable uncertainty about these assumptions. Our method is a kind of regression method
where labeled relevance judgements are fit as a lin
ear combination of (transforms of) ,  , etc. Training methods not only improve performance, but also
extend naturally to include additional factor, that isburstiness. The proposed histogram-based training
method provides a simple way to model complicatedinteractions among factors such as and  .

1

Introduction

An empirical method for estimating term weights
directly from relevance judgements is proposed by[7]. The method is designed to make as few assumptions as possible. It is a kind of regression [4] [1]
where labeled relevance judgements are fit as a lin
ear combination of (transforms of) ,  , etc., but
avoids potentially troublesome assumptions by introducing histogram methods. Terms are grouped into
bins. Weights are computed based on the number of
relevant and irrelevant documents associated with eachbin. The resulting weights usually lie between and  
 , which is a surprise; standard formulas like
would assign values well outside this range.
Under the vector space model, the score for a document  and a query is computed by summing acontribution for each term over an appropriate set ofterms, . is often limited to terms shared by both the
document and the query (minus stop words), though
not always (e.g, query expansion).

 

!#"

 

$





 


Under the probabilistic retrieval model, documents arescored by summing a similar contribution for eachterm .
%&' 

 $/  ( !#")( *,+.-  $/ (-In this work, we use 0 to refer to term weights.
%# $1!#")0  %

This paper will start by showing how to estimate 0
from relevance judgements. Three parameterizations
will be considered: (1) fit-G, and (2) fit-B, which introduces burstiness. We are also interested in the interpretations of the parameters.
In this report, we have borrowed the description
from [7], since our system uses the method describedin the paper. The following description is essentiallysame as [7] except the description of query expansion.

2

Supervised Training

The statistical task is to compute 0 2 , our best estimate of 0 , based on a training set. This paper will use
supervised methods where the training materials not
only include a large number of documents but also a
few queries labeled with relevance judgements.
We have chosen bigram (2 characters) for term.
Though properly segmented words will be another obvious choice, we are interested in bigram system.
To make the training task more manageable, it iscommon practice to map the space of all terms into alower dimensional feature space. In other words, instead of estimating a different 0 2 for each term in thevocabulary, we can model 0 2 as a function ofand and various other features of terms. In this way, allof the terms in a bin are assigned the weight, 0 2 . The
 
common practice, for example, of assigning3: a term3 : a document3

 

$ : term freq = # of instances of in  

 : doc freq = # of docs  with

3


 

4576

398 : # of documents in collection
3



 

A@

 : inverse document freq: : ( *#+<;>=B ?

C    (  : # of relevant documents  with
 
C
$D3 C    (  : # of irrelevant documents  with
 
C
$D
3
3

FE   : standard notion of frequency in corpus 
based NLP: FE  1
$;"&J A@? A@ is large.
39G)  : burstiness: G) HI6 iff
;>=?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
21
25

Description (function of term )

 
&
   & ( PQR # ( docs  with
$DK  &( %6,R # & ( docs  with  $DL6



 
   & ( PMQR # & ( docs  with
$DKM  &( PNQR # & ( docs  with  $DKN



 
   & ( POQST1R # & ( docs  with
$U5KO  &( PQR # & ( docs  with  $DK



 
   & ( %6,R # & ( docs  with
$DL6  &( PMQR # & ( docs  with  $DKM   & ( PNQR # & ( docs  with  $DKN
  &&( POQST1R # ( docs  with  $U5KO





# ( docs #  ( docs  freq of term in corpus: FE  1
4
;
8
# docs  in collection = = # docs  with  $U576
where: D (description), E (query expansion)
burstiness: G

Table 3. Training file schema: a recordof 25 fields is computed for each term
(ngram) in each query in training set.

Table 1. Notation





12.89
10.87
9.79
8.96
7.75
6.82
5.78
4.74
3.85
2.85
1.78
0.88



K

-0.37
-0.49
-0.86
-0.60
-0.34
-1.26
-0.83
-0.84
-0.60
-1.02
-1.33
-0.16



L6

9.73
8.00
7.36
6.26
4.62
3.94
3.16
2.46
1.58
1.00
-0.06
0.17



KM

11.69
9.95
9.38
7.99
5.82
6.05
5.17
3.91
2.76
1.72
1.05
0.19



9N



12.45
11.47
10.63
8.99
6.62
7.59
5.77
4.54
3.57
2.55
2.46
-0.10

Table 2. Empirical estimates of 0 2 as afunction ofand  . Terms are as
signed to bins based on  . The columnlabeled  is the mean  for the terms
in each bin. 0 2 is estimated separately foreach bin and each value, based on thelabeled relevance judgements.

5KO

13.59
12.06
10.88
9.41
7.98
8.98
7.00
5.58
4.55
3.96
4.50
-0.37

weights can be interpreted as grouping all terms with

the same  into a bin and assigning them all the sameV 
 . Cooper and his colleagues at
weight, namely
Berkeley [4] [1] have been using regression methods to
fit 0 2 as a linear combination of  , ( *<  and various other features. This method is also grouping terms
into bins based on their features and assigning similar weights to terms with similar features. In general,term weighting methods that are fit to data are more
flexible than weighting methods that are not fit to data.
Instead of multiple regression, though, we choose
a more empirical approach. Parametric assumptions,when appropriate, can be very powerful (better estimates from less training data), but errors resulting
from inappropriate assumptions can outweigh the benefits. In this empirical investigation of term weighting we decided to use conservative non-parametric histogram methods to hedge against the risk of inappropriate parametric assumptions.
Terms are assigned to bins based on features suchas  , as illustrated in table 2. (Later we will also use
G and/or   in the binning process.) 0 2 is computed
separately for each bin, based on the use of terms in
relevant and irrelevant documents, according to the labeled training material.
The estimation method starts with a training filewhich indicates, among other things, the number of
relevant and irrelevant documents for each term ineach training query, . That is, for each and , we

C

C
are are given     (  and     (  , where  & C( is the number of relevant documents 

C

C
with  $W
, and     (  is the num-



C

ber of irrelevant documents  with  4X
.
The schema for the training file is described in table
3. From these training observations we wish to obtaina mapping from bins to 0 s that can be applied to unseen test material. We interpret 0 as a log likelihood
ratio:
0 2 ZY \[D



U

</ !Y(
2 \[D( *,+ - ! Y
</ 
(
- 2 \ [DZY ][U ^/  ( `_( * + ZY][D  ( 
8 aPbdc
2



a
-0.95
-0.98
-0.15
0.53
1.32

b
0.05
0.69
0.78
0.81
0.77

Table 4. Regression coefficients formethod fit-G. This table approximates the  
2 _7p S Y  .
data in table 1 with 0oNote that both the intercepts, p   , and
the slopes, Y$  , increase with
(with aminor exception for Y$ O^ST ).

where the numerator can be approximated as:
-2

tf
0
1
2
3
4+





where  Z Y \ [D & (   is
 ZY\[D & ( 



`R

6

/Y

][

/ !#e]fAgh   ( 




2.1

Interpolating Between Bins

Similarly, the denominator can be approximated as:
-

2 ZY

][U

^/ ( *,+

( `_

 ZY

][D  ( 
8 2 aPbdc






where  Z Y \ [D & (   is


 ZY

\[D

& (   `R

/Y

6
][

/ !#e]fAgh  (   

8 2 abZc is an estimate of the total number of relevant doc-

uments. Since some queries have more relevant documents than others, 8i2 aPbdc is computed by averaging:8i
2 abZc R

/Y

6
\[

/ !#e]fAg

8iabZc

To ensure that 8 2 aPbdc S 8 2 aPbdc  8 , where 8 is the number of documents in the collection, we define 8 2 abdc R
8:8 2 aPbdc

This estimation procedure is implemented with thesimple awk program in figure 2. The awk program
reads each line of the training file, which contains aline for each term in each training query. As describedin table 3, each training line contains 25 fields. The
first five fields contain     (   for five values of, and the next five fields contain     (   for
the same five values of . The next two fields contain 8 aPbdc and 8 aPbdc . As the awk program reads each ofthese lines from the training file, it assigns each termin each training query to a bin (based on j ( *#+  lk ,nm
except when 6 ), and maintains running sumsof the first dozen fields which are used for computing




abdc
and 8 2 abdc for !Y \[D & (  ,  ZY \[D  ( , 82five values of . Finally, after reading all the training
material, the program outputs the table of 0 2 s shownin table 2. The table contains a column for each of the
five values and a row for each of the dozen  bins.

Recall that the task is to apply the 0 2 s to new unseen
test data. One could simply use the 0 2 s in table 2 asis. That is, when we see a new term in the test material, we find the closest bin in table 2 and report thecorresponding 0 2 value. But since the  of a term in
the test set could easily fall between two bins, it seems
preferable to find the two closest bins and interpolate
between them. We use linear regression to interpolatealong the  dimension, as illustrated in table 4. Table 
2 _rpsS Y  .
4 is a smoothed version of table 2 where 0q
Y
There are five pairs of coefficients, p and , one foreach value of .
Note that interpolation is generally not necessary on


the
dimension because
is highly quantized. As
tm
O , which it usually is, the closest bin islong asan exact match. Even when
5uO , there is very little
room for adjustments if we accept the upper limit of
m

02
 .


Although we interpolate along the  dimension,interpolation is not all that important along that dimension either. Figure 1 shows that the differences between the test data and the training data dominate theissues that interpolation is attempting to deal with. The
main advantage of regression is computational conve nience; it is easier to compute pQS Y  than to performa binary search to find the closest bin.
Previous work [4] used multiple regression techniques. Although our performance is similar with thesame number of parameters. We believe that it is saferand easier to treat each value ofas a separate regression for reasons discussed in table 5. In so doing,
we are basically restricting the regression analysis tosuch an extent that it is unlikely to do much harm (or
2 vt alsomuch good). Imposing the limits of wv 0q
serves the purpose of preventing the regression fromwandering too far astray.

awk ’function log2(x) {return log(x)/log(2)}$21 ˜ /ˆD/ { N = $14; df=$15;# binning ruleif(df < 100) {bin = 0}else {bin=int(log2(df))};docfreq[bin] += df;
Nbin[bin]++;# average df(t,rel,tf), df(t,irrel,tf)
for(i=1;i<=12;i++) n[i,bin]+=$i }END {for(bin in Nbin) {nbin = Nbin[bin]Nrel = n[11,bin]/nbin
Nirrel = N-Nrel
idf = -log2((docfreq[bin]/nbin)/N)
printf("%6.2f ", idf)
for(i=1;i<=5;i++) {if(Nrel==0) prel = 0
else prel = (n[i,bin]/nbin)/Nrelif(Nirrel == 0) pirrel = 0
else pirrel = (n[i+5,bin]/nbin)/Nirrel
if(prel <= 0 || pirrel <= 0) {printf "%6s ", "NA" }else {
printf "%6.2f ", log2(prel/pirrel)} }print ""}}’
Figure 2. awk program for computing 0 2 s.

tf
0
1
2
3
4
5



Y  

-0.95
-0.98
-0.15
0.53
1.32
1.32

0.05
0.69
0.78
0.81
0.77
0.77

p 



p + S

Z+  (  *< 6xS

-4.1
-1.4
0.18
1.3
2.2
2.9




YZ+

0.66
0.66
0.66
0.66
0.66
0.66

Table 5. A comparison of the regression
coefficients for method fit-G with comparable coefficients from the multiple re 
2 up + S Y +  S  + ( *< 6yS
gression: 0w
Y

+
+
+
}{ ~~ andN{  .
where p z:hO&{|6 ,The differences in the two fits are particz ; note that Y$ ^ularly large whenis negligible (0.05) and YZ+ is quite large(0.66). Reducing the number of parameters from 10 to 3 in this way increases thesum of square errors, which may or may
not result in a large degradation in precision and recall. Why take the chance?

tf
0
1
2
3
4+

B=0
a
b
-0.05 -0.00
-1.23
0.63
-0.76
0.71
0.00
0.69
0.68
0.71

B=1
a
b
-0.61 0.02
-0.80 0.79
-0.05 0.79
0.23 0.82
0.75 0.83

Table 6. Regression coefficients formethod fit-B. Note that the slopes andintercepts are larger when G 6 than
when G r (except whenr ). Eventhough 0 2 usually lies between 0 and  ,
2 v , just to makewe restrict 0 2 to v 0
sure.

3

Burstiness

Table 6 is like tables 4 but the binning rule not only
uses  , but also burstiness ( G ). Burstiness [3][5][2]is intended to account for the fact that some very good
keywords such as “Kennedy” tend to be mentioned
quite a few times in a document or not at all, whereas
less good keywords such as “except” tend to be mentioned about the same number of times no matter what
the document is about. Since “Kennedy” and “except” have similar  values, they would normally receive similar term weights, which doesn’t seem right.

Kwok [6] suggested average term frequency, p




FE
Z,
 , be used as a tie-breaker for cases like 
$ is the standard nothis, where FE   ;tion of frequency in the corpus-based NLP. Table 6
shows how Kwok’s suggestion can be reformulated inour empirical framework. The table shows the slopes
and intercepts for ten regressions, one for each combi
nation ofand G ( G 6 iff p$
is large. That is,G L6 iff FE  !  r6#{ N:&{ O    ).

4

Summary

Our system uses an empirical histogram-based supervised learning method for estimating term weights,
0 2 . Terms are assigned to bins based on features such as
inverse document frequency, and burstiness. A differ
ent 0 2 is estimated for each bin and eachby counting the number of relevant and irrelevant documents
associated with the bin and value. Regression techniques are used to interpolate between bins, but care istaken so that the regression cannot do too much harm(or too much good).
We are also interested in the interpretation of theweights. Empirical weights tend to lie between 0 and . We find these limits to be a surprise given that  
standard term weighting formulas such as generally do not conform to these limits. In addition, wefind that 0 2 generally grows linearly with  , and thatthe slope is between 0 and 1. We interpret the slope
as a statistical shrink. The larger slopes are associatedwith very robust conditions. It is interesting to compare histogram methods with multiple regression thattries to account for all of the interactions at once in asingle multiple regression.
Even though selecting the effective parameters isstill a kind of art, this framework gives a systematic
way to handle them. We have shown that this assumption re-invent standard practice, we are encouraged with this result.

Acknowdedgement
Authors thank Kenneth W. Church, AT&T, to provide the fundamental framework used in our system.
This development is supported by Sumitomo Electric.

References[1] A. Chen, F. C. Gey, K. Kishida, H. Jiang, and
Q. Liang. Comparing multiple methods for japaneseand japanese-english text retrieval. In NTCIR Workshop
1, pages 49–58, Tokyo Japan, Sep. 1999.
[2] K. W. Church. Empirical estimates of adaptation: The
chance of two noriegas is closer to  than  . In
Coling-2000, pages 180–186, 2000.
[3] K. W. Church and W. A. Gale. Poisson mixture. Natural
Language Engineering, 1(2):163–190, 1995.
[4] W. S. Cooper, A. Chen, and F. C. Gey. Full text retrieval
based on probabilistic equation with coefficients fitted
by logistic regressions. In The Second Text REtrieval
Conference(TREC-2), pages 57–66, 1994.
[5] S. M. Katz. Distribution of content words and phrases
in text and language modelling. Natural Language Engineering, 2(1):15–59, 1996.
[6] K. L. Kwok. A new method of weighting query terms
for ad-hoc retrieval. In SIGIR96, pages 187–195,
Zurich, Switzerland, 1996.
[7] K. Umemura and K. W. Church. Empirical term weighting and expansion frequency. In ACL SIGDAT, pages
117–123, 2000.

10

12

Train

2

6
4

4
3

0

lambda

8

4
3

3
0 2
1
3
4 0
4
1
2

0

2
1
0

4
3
2
1
0

2

4
3
2
1
0

4
3
2
1

0

4

4
3
2

2
1

1

4
3
2
1

0

0

0

6

4
3
2

4
3
2
1

4
3

4
3
2

2

1

1

1

0

8

0

0

0

10

12

IDF

Test
12

4

6
4
2
0

lambda

8

10

3
2

3
4
3
4
2
1
2
1 0
0

0

4
3
2
1
0

2

4
3
2
1
0

4
3
2
1
0

4

4
3
2

4
3
2
1

4
3
2
1

4
3
2

3
4
2

1

1

0

0

4
3
2
1

2
3
4

4
3
2

1

1

1

1
0

0

6

0

8

0
10

0

0

0
12

IDF

Figure 1. Empirical weights, 0 2 . Top
panel shows values in previous table.
Most points fall between the dashed lines
2  and upper limit of(lower limit of 0}
2 X ). The plotting character denotes0n. Note that the line with
KO is abovethe line withN , which is above theline withM , and so on. The higherlines have larger intercepts and larger
slopes than the lower lines. That is, when  
2 _p .S Y  , with separate
we fit 0q
regression coefficients, p   and Y$  ,
for each value of , we find that both



p 
 and Y$ increase with .